做网站后期费用,去长沙旅游攻略及费用,互联网服务网站建设目的,h5动态页面怎么做的前言#xff1a;因为学校的算法考试让我认识了卡哥#xff0c;为了下学期冲击大厂实习的理想#xff0c;我加入了卡哥的算法训练营#xff0c;从今天开始我每天会更新自己的刷题笔记#xff0c;与大家一起打卡#xff0c;一起共勉#xff01; Day 1
01. 二分查找 … 前言因为学校的算法考试让我认识了卡哥为了下学期冲击大厂实习的理想我加入了卡哥的算法训练营从今天开始我每天会更新自己的刷题笔记与大家一起打卡一起共勉 Day 1
01. 二分查找 No. 704
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
1.1 笔记 二分法基本上每个学过算法的人都遇到过这个问题它的思路和代码都很简单但是写的时候经常出错主要是因为下面两点 外层的 while 的区间是多少我检测完 middle 的值之后更新区间是否应该包含这个 middle 我们在代码提交通过后可能就没有考虑过这个问题或者说随便改改通过了也扔一边了今天来具体的解决一下这个问题。 首先我们要清楚搜索区间很多朋友会感觉很简单这不就是一开始定义的 left 和 right 吗其实我们还要考虑这两个数的区间是左闭右闭、左闭右开亦或是左开右闭这才是影响我们上面两个问题的关键因素。
按照比较好理解的左闭右闭举例[right, left]也就是我们的搜索区间是左闭右闭的举个例子[1, 1] 是有意义的所以 while 中 right 和 left 是可以取到相等的因为在左闭右闭的前提下这样取是有意义的。
那来解决第二个问题新的区间是否应该包含 middle同样来检验这个区间的合理性如果包含 middle 的话比如说我们通过计算发现nums[mid] 的值要大于target这时候就需要往左边去遍历也就是比 nums[mid] 小的部分但这时候有如果按照左闭右闭的区间其实是包含了这个 nums[mid] 的元素的这就违背了我们去比它小的部分查找的初衷所以在这种情况下要取 mid 1
1.2 代码
class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length - 1;// 左闭右闭的情况while(left right) {int mid left right;if (nums[mid] target) {// 向左边查找元素right mid - 1;} else if (nums[mid] target) {left mid 1;} else {return mid;}}return -1;}
}
1.3 其他情况
剩下的还有左闭右开和左开右闭的情况这时候我们仍然考虑区间的准确性比如这时候 [1, 1) 就没有数学意义了所以我们的 while 中不能再取等于。
以左闭右开为例子来看这个问题这时候如果说 nums[mid] 比目标值要大的话向左边查找这时候写出区间来就是 [left, mid) 还是上面的那个考虑这时候因为搜索的区间不包含 mid 所以是可以加等于号的。
看到这里兴致冲冲的去写代码提交发现报错了这是什么问题呢 while(left right) {int mid (int)((left right) / 2.0 0.5);if (nums[mid] target) {// 向左边查找元素right mid;} else if (nums[mid] target) {left mid 1;} else {return mid;}}因为这时候你的眼里只有这个 while 函数没有注意到当是开区间的时候 right 是可以等于 nums[length] - 1 的修改后的代码就是这样的
class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length;while(left right) {int mid (left right) / 2;if (nums[mid] target) {// 向左边查找元素right mid;} else if (nums[mid] target) {left mid 1;} else {return mid;}}return -1;}
}
写到这里又有顿悟的感觉自己去试了试左开右闭的情况不就是把 left -1 如何把下面的 1 去掉就好了。
一提交又报错了。。。
这又是什么原因呢为什么上面两种情况没有出现问题呢
首先出现了时间超时肯定是这个 left 卡在了 mid 每次继续都卡在这个位置
这时候关注到这个 mid 的计算方法很容易发现是向下取整的在左闭右闭的情况下左右都不会取到这个 mid 所以不用考虑卡住的情况左开右闭的情况下虽然右区间可以取到 mid 但向下取整是保证这个右边界是一直向左靠拢的但如果是左区间向下取整的话就有可能会出现卡住的情况
举个例子 那为了保证不卡住解决方法就是更改这个 mid 为向上取整这样就能保证左区间是持续向右的了。
class Solution {public int search(int[] nums, int target) {int left -1;int right nums.length - 1;// 左闭右闭的情况while(left right) {int mid (int)((left right) / 2.0 0.5);if (nums[mid] target) {// 向左边查找元素right mid - 1;} else if (nums[mid] target) {left mid;} else {return mid;}}return -1;}
}
OK通过
02. 移除元素 No. 27
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
2.1 笔记
这个题目主要考察我们对数组结构的理解暴力的解法也很容易想出来就是我们遇到了等于 val 的元素的话就将这个数组整体向前移动一位这时候最后一个元素就变为我们不需要的元素所以遍历的结尾要减去 1同时还需要注意的问题就是如果两个连续都是不需要的元素的话要将 i 仍然保留在当前位置左相同的操作否则就会漏删元素。
2.2 代码
class Solution {public int removeElement(int[] nums, int val) {int len nums.length;int N nums.length;for (int i 0; i N; i) {// 循环遍历数组if (nums[i] val) {len--;N--;for (int j i; j nums.length - 1; j) {nums[j] nums[j 1];} }if (nums[i] val) {i--;}}return len;}
}2.3 拓展 —— 双指针法
这道题可以通过双指针思想来解决这个问题设置一个快慢指针快指针去遍历这个数组取到不为 val 的元素后将快指针的内容赋值给慢指针然后将慢指针加一这样一直循环直到数组结尾快指针中取到的元素的个数就是结果数组的元素总数当快指针遍历完数组后慢指针指向的最后一个元素就是结果数组的最后一个元素所以我们返回慢指针的索引也是最终的结果。
class Solution {public int removeElement(int[] nums, int val) {int len 0;int slow 0;for (int fast 0; fast nums.length; fast) {if (nums[fast] ! val) {len;nums[slow] nums[fast];slow;}}return len; // return slow;}
}
