代碼随想錄刷題記錄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找到要移除的元素，把後面的都往前移動一格。

這兩道題目之前都做過，都有點印象，是以今天還是比較順利的。