算法训练营day1 | 704二分查找，27移除元素， 34， 35

已经找到工作，但希望再试试春招，距离春招还剩两个月，加油。

这两道题都刷过很多遍了，没什么好说的直接过。

704

本以为刷了很多次没想到还是做错了，有些小细节要注意。

这里是迭代式的，函数式的也不难。

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] > target){
                r = mid - 1;//这里一开始写的是mid,由于我是取等于所以不能是mid
            }
            else if(nums[mid] < target){
                l = mid + 1;
            }
        }
        return -1;
    }
}

27

双指针没什么说的。

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int i = 0, j = 0;
        while(j < len){
            if(nums[j] == val){
                j++;
                continue;
            }
            nums[i++] = nums[j++];
        }
        return i;
    }
}

刷一下34和35，直接刷代码随想录的时候从来没有刷过拓展题。

34

最开始的想法是通过二分找到一个答案后，往左右两边找到边缘的坐标，但发现这样在极端情况下时间复杂度是o(n)，所以还是正常地通过两个二分，一个找左端点一个找右端点吧。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int r = nums.length - 1, l = 0;
        int ansl = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] >= target){
                if(nums[mid] == target){
                    ansl = mid;
                }
                r = mid - 1;
            }else{
                l = mid +1;
            }
        }
        
        int ansr = ansl;
        r = nums.length - 1;l = 0;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] > target){
                
                r = mid - 1;
            }else{
                if(nums[mid] == target){
                    ansr = mid;
                }
                l = mid +1;
            }
        }

        return new int[]{ansl, ansr};
    }
}

35

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int ans = -1, mid = -1;
        while(l <= r){
            mid = (l + r) / 2;
            if(nums[mid] == target){
                ans = mid;
                break;
            }
            if(nums[mid] > target){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        if(ans == -1){
            if(nums[mid] > target){
                return mid;
            }else{
                return mid + 1;
            }
        }
        return ans;
    }
}

 今天是12.12做的事12.11的任务，明天要补进度了

今天的还算比较简单，加油！

男朋友帮我加了一个洛谷题，好难已经做完了明天再补充细节吧T-T

R194137083