Day 1 | 704. 二分查找, 27. 移除元素, 977.有序数组的平方

Summary:

總時長: 通勤1hrs看影片+2hrs解題

心得:看完影片覺得自己懂了，換成自己動手寫的時候還是想了好一陣子

第一題感覺自己還是沒有完全懂Binary Search的影片，晚點再把大師兄的影片再刷一次

第三題一開始把left跟index弄混了，以為要用原本的陣列回傳，是我自己搞錯了

704. 二分查找

題目

[文章]++https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html++

影片

class Solution {
    public int search(int[] nums, int target) {
        int min = 0;
        int max = nums.length;
        int center = (min+max)/2; 
        
        for(int i = 0; i < nums.length;i++){
            center = (min+max)/2;
            if(nums[center]<target){
                min= center;
            }else if(nums[center]>target){
                max = center;
            }else if(nums[center]==target){
                return center;                
            }
        }
        return -1;
    }
}

分析: 我一開始寫的如上

首先for迴圈幾乎沒有用到，應該用while即可，條件改成 left小於right

這樣就喪失了用二分查找的本意，調整後如下:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;         
        
        while(left<right){
            int middle= (left+right)/2;
            System.out.println("middle:"+middle);
            if(nums[middle=target){
                return middle;                
            }else if(nums[middle]<target){
                left= middle+1;
            }else if(nums[middle]>target){
                right = middle;
            }
        }
        return -1;
    }
}

27. 移除元素

題目

文章

影片

class Solution {
    public int removeElement(int[] nums, int val) {     
        int slow = 0;   
        for(int fast = 0;fast<nums.length;fast++){
            if(nums[fast]=val){
                nums[slow=nums[fast];
                slow++;                                
            }
        }
        return slow;
    }
}

977.有序数组的平方

題目

文章

影片

class Solution {
    public int[] sortedSquares(int[] nums) {   
        int left = 0;
        int right = nums.length-1;         
        int index =nums.length-1;
        int[] result = new int[nums.length];
        while(right>=left){
            if(nums[left]*nums[left]>nums[right]*nums[right]){
                result[index]=nums[left]*nums[left];
                left++;                
            }else{
                result[index]=nums[right]*nums[right];
                right--;
            }
            index--;
        }
        return result;
    }
}