代码随想录二刷复习 day1 704二分查找 27 移除元素 977 有序数组的平方

代码如下 

func search(nums []int, target int) int {

           left := 0 

           right := len(nums)-1

           for left <= right {

               middle := (left+right)/2

               if target < nums[middle] {  //因为上面的判断条件是left <= right，所以左右两个边界的值最后都能取到，而此时如果取 right = middle ，那么就会造成再次取到nums[middle]这个值，但是target < nums[middle]这个已经判断过了，所以要取   right = middle-1

                     right = middle-1

               }else if target > nums[middle]{

                    left = middle+1

               }else {

                   return middle

       

         } 

           return -1 

}

左闭右开区间 

func search(nums []int, target int) int {

           left := 0 

           right := len(nums)

           for left < right {

               middle := (left+right)/2

               if target < nums[middle] { //因为是左闭右开的区间所以是取不到右边界的值的，所以在初始右边界为 len(nums) 

                     right = middle

               }else if target > nums[middle]{

                    left = middle+1

               }else {

                   return middle

               }

           } 

           return -1 

}

               }

        小结 ： left <= right 和 left < right 的区别 。举例 ，middle  = (left+right)/2 

如果是left <= right ，那么左和右可以取到4,4这样的区间，此时middle也为4，即middle 等于右边界 。如果是 left < right ，那么就取不到4,4这样的区间，只能取到4,5这个区间，此时middle值也为4.此时就取不到右边界  

27 移除元素 

代码如下 

func removeElement(nums []int, val int) int {

         slow := 0 

         for  fast := 0 ; fast < len(nums) ; fast++ { //遍历双指针，快指针负责遍历整个数组，慢指针负责收集删除元素后的数组元素 ，原则是如果与删除元素不相同的元素，放入慢指针指向的数组，慢指针向后移一位 

             if nums[fast] != val {

                 nums[slow] = nums[fast]

                 slow++

             }

         }

         return slow 

}

第一遍写的时候还想了一段时间，第二遍刷直接就写出来了。感觉自己的算法能力确实进步了一点。

977 有序数组的平方 

代码如下

思路： 定义一个结果数组，开始遍历原数组，因为原数组是非递减，所以平方后的最大值只会在两边产生，此时从左右两边依次遍历原数组，将左右两边的数的平方进行比较，并将平方和大的数放入新的数组中 

func sortedSquares(nums []int) []int {

             res := make([]int,len(nums))

             k := len(nums)-1

             left := 0 

             right := len(nums)-1 

             for left <= right {

                 if nums[left]*nums[left] < nums[right]*nums[right] {

                           res[k] = nums[right]*nums[right] 

                           

                           right-- 

                 }else {

                     res[k] = nums[left]*nums[left]

                    

                     left++

                 }

                 k--

             }

             return res 

}