Leetcode704：二分查找
今日学习的文章链接：
题目链接：
● 自己看到题目的第一想法
这题我会，但是还没明白卡尔说的循环不变量是什么意思。
我的固定思路就是，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
LeetCode27：移除元素
● 今日学习的文章链接
题目链接：
● 自己看到题目的第一想法
感觉很简单，但是写的时候出现了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
标签：arr,27,int,元素,随想录,mid,数组,移除,指针 From： https://www.cnblogs.com/xiaoni2023/p/17899228.html