代码随想录算法训练营第一天| LeetCode704 二分查找、27移除元素

 Leetcode704:二分查找

今日学习的文章链接:

代码随想录 (programmercarl.com)

 

题目链接:

704. 二分查找 - 力扣(LeetCode)

●  自己看到题目的第一想法

这题我会,但是还没明白卡尔说的循环不变量是什么意思。

我的固定思路就是,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:移除元素

●  今日学习的文章链接

代码随想录 (programmercarl.com)

题目链接:

27. 移除元素 - 力扣(LeetCode)

●  自己看到题目的第一想法

感觉很简单,但是写的时候出现了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

热门相关:一品侍卫   凤逆天下:腹黑魔君妖娆后   苏医生,你笑起来很好看   魔葫   我有一个进化点