[数据结构与算法]代码随想录刷题记录day01

day01

leetcode：704 二分查找

思想：

二分法的思想比较好理解，主要就是边界问题不好处理。比如说while(left<right)还是while(left<=right),还有mid的取值问题 。主要思路或者说方法论就是坚持循环不变量原则，也就是在while循环中坚持的不变量。即一开始就确定[left,right] 还是[left,right)。

区别：

• [left,right] 当left=right的时候，比如说[1,1]这个区间是合法的，所以while(left<=right);mid不是要找的元素下标的 时候，left=mid+1；right=mid-1，因为下一个搜索区间不包含mid；
• [left,right) 当left=right的时候，[1,1)这个区间就没有值可取了，所以while(left<right); 要寻找中间左边区间的时候 right=mid,因为根据这个区间的定义，mid不被搜索到；要寻找中间右边区间的时候left=mid+1,左闭

代码实现

左闭右闭写法

public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int mid=left+(right-left)/2;

            if(nums[mid]<target){
                //中间的数比目标值小 要找到数字还在右边
                left=mid+1;
            }
            else if(nums[mid]>target){
                //中间的数比目标值大 要找的数字在中间左边
                right=mid-1;
            }
            else{
                return mid;
            }

        }
        return -1;
}

左闭右开写法

public int search(int[] nums, int target) {
		int left=0;
        int right=nums.length;

        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                //中间的数比目标值小 要找到数字还在右边
                left=mid+1;
            }
            else if(nums[mid]>target){
                //中间的数比目标值大 要找的数字在中间左边
                right=mid;
            }
            else{
                return mid;
                }
        }
        return -1;
}

leetcode：27.移除元素

思想：

1.暴力法 遇到target值以后，将后面的元素都往前移动一格。同时 i–，遍历值退一格,size–;size用来记录数组的大小

2.双指针法：快慢指针，慢指针指向当前要被替换元素的位置，快指针去寻找目标值

代码

暴力法：

public int removeElement(int[] nums, int val) {
	int size=nums.length;
        for(int i=0;i<size;i++){
            if(nums[i]==val){
                for(int j=i+1;j<nums.length;j++){
                    nums[j-1]=nums[j];//把后面的元素往前移动一个
                }
                i--;
                size--;
            }
        }
        return size;
}

双指针法：

public int removeElement(int[] nums, int val) {
		int left=0;
        int right=0;

        for(;right<nums.length;right++){
            //如果不是目标值
            if(nums[right]!=val){
                nums[left]=nums[right];
                left++;
            }
           
        }
        return left;
}

在返回left还是left+1的时候没考虑清楚，left始终指向的下一个等待被替换的元素，所以只需要返回left就好。

总结

比较重要的两个思想：循环不变量（控制每轮遍历的区间）、快慢指针（快指针去找符合条件的元素，慢指针在原地等待，找到了，两个一起前进）。

在做27 移除元素的时候暴力法也卡了一下，主要思想就是i找到要移除的元素，把后面的都往前移动一格。

这两道题目之前都做过，都有点印象，所以今天还是比较顺利的。