代码随想录二刷复习 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
}