代码随想录算法训练营第一天| LeetCode704 二分查找、27移除元素
今日学习的文章链接:
题目链接:
● 自己看到题目的第一想法
这题我会,但是还没明白卡尔说的循环不变量是什么意思。
我的固定思路就是,target比中间值大,左指针右移到mid+1;target比中间值小,右指针左移到mid-1;
代码:
class Solution { public int search(int[] arr, int target) { //数组不重复才可以用二分法 int i = 0; int j = arr.length - 1; int mid = 0; while (i <= j) { mid = (i + j) / 2; if (target > arr[mid]) { i = mid + 1;//左指针右移 } else if (target < arr[mid]) { j = mid - 1;//右指针左移 } else { return mid; } } return -1; } }
● 看完代码随想录之后的想法
1.原来还有一种思路是不把右边界的值算进来,这样对于在左区间的元素,右指针移动到mid;对于右区间的元素,左指针移动到mid+1
2.循环不变量规则:区间的定义就是不变量,那么在循环中坚持根据查找区间的定义来做边界处理
3.在计算mid值得时候为了防止大整数的溢出可以把运算转成减法
修改后的代码如下
mid = i + (j-i) >> 1;//减法不会溢出,而且就是说移位运算符效率高一些
● 自己实现过程中遇到哪些困难
溢出
● 今日收获,记录一下自己的学习时长
1h
● 今日学习的文章链接
题目链接:
● 自己看到题目的第一想法
感觉很简单,但是写的时候出现了bug,经过调试发现每次移动了元素之后,指针的位置要重置一下
class Solution { public int removeElement(int[] arr, int val) { int count = 0; for (int i = 0; i < arr.length-count; i++) { if (arr[i] == val) { for (int j = i; j < arr.length - 1-count; j++) { arr[j] = arr[j + 1];//移动元素 } count++; i--; } } return arr.length - count; } }
● 看完代码随想录之后的想法
这道题用两层循环其实会有一些冗余的操作,实际上如果只移动需要移动的元素就好了;利用快慢指针可以完成这样的思路。
快指针用来判断当前元素是否属于新数组,慢指针用来把当前元素加入到新数组;于是,当快指针指向的元素是需要删除元素的时候,快指针就会跳过这个元素,直到找到下一个需要被加入的元素,慢指针就会把这个元素加入到新数组中,所以慢指针代表的就是新数组所具有的所有元素。
可以发现,思考的时候反过来想会比较顺畅,也即考虑当前是否为新数组的元素,是的话就加入,不是的话就跳过。要从结果集的角度思考,不要从排除集的角度思考。
因为慢指针代表的就是我们要求的结果集,快指针就是用来排除结果集之外的元素的
class Solution { public int removeElement(int[] arr, int target) { int slow = 0; //快指针寻找新数组的元素 //快指针找到了需要加入新数组的元素后,慢指针更新新数组的内容 for (int fast = 0; fast < arr.length; fast++) { if (target != arr[fast]) { arr[slow] = arr[fast]; slow++;//slow右移,该元素被加入到新数组当中 } //如果快指针指向的元素是要删除的元素,那么快指针往后移动 //慢指针不动,在下一轮的操作当中慢指针将会更新当前位置的值 } //最后慢指针会停在新数组之外 return slow; } }
● 自己实现过程中遇到哪些困难
快慢指针的思想很难一次想通,如果长时间不做很容易又忘记这个思路,需要反复练习
● 今日收获,记录一下自己的学习时长
1.5h
热门相关:一品侍卫 凤逆天下:腹黑魔君妖娆后 苏医生,你笑起来很好看 魔葫 我有一个进化点