part1

704.二分查找

分析

>> 位运算 等于 模2

---

• 如果target一直大于nums[mid]，l会向右移动(变大)
• 如果target一直小于nums[mid]，r会向左移动(变小)
• 如果target等于nums[mid]，返回mid

---

定义区间:

1. 决定了出循环的条件
   • 左闭右闭 有[x,x]情况，那么这个情况不应出循环，也就是l==r时，也就是r>l时才出循环
   • 左开右闭 不应该有(x,x]情况，那么这个情况应该出循环，也就是r>=l出循环，左闭右开同理
   • 左开右开 应该要有(x-1, x+1)情况，否则中间x的值永远取不到，也就是r-l == 2, 那么r-l <= 1出循环
2. 决定了能不能触摸到边界值，触摸不到mid应该给下一个边界，触摸到了下一个边界在mid左右，而不是mid本身
   • mid碰不到左边界l = mid
   • mid碰不到右边界r = mid
   • mid能碰到左边界l = mid+1
   • mid能碰到右边界r = mid-1

代码

// 左闭右闭
func search1(nums []int, target int) (ans int) {
	// 定义左右区间 [l, r]
	l, r := 0, len(nums)-1

    // 左闭右闭 mid都会被碰到
	// 最后 l>r 时 遍历出区间
	for l <= r {
		mid := l + (r-l)>>1
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}

	return -1
}

// 左闭右开
func search2(nums []int, target int) (ans int) {
	// 定义左右区间 [l, r)
	l, r := 0, len(nums)

    // 左闭右开 mid只会被左碰到
	// 最后 l == r 时 遍历出区间
	for l < r {
		mid := l + (r-l)>>1
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			l = mid + 1
		} else {
			r = mid
		}
	}

	return -1
}

// 左开右闭
func search3(nums []int, target int) (ans int) {
	// 定义左右区间 (l, r]
	l, r := -1, len(nums)-1

    // 左开右闭 mid只会被右碰到
	// 最后 l >= r 时 遍历出区间
	for l < r {
		// 向上取整避免死循环
		mid := l + (r-l+1)>>1
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			l = mid
		} else {
			r = mid - 1
		}
	}

	return -1
}

// 左开右开
func search4(nums []int, target int) (ans int) {
	// 定义左右区间 (l, r)
	l, r := -1, len(nums)

    // 左开右开 mid碰不到两边
	// 最后 r-l <= 1 时 遍历出区间
	for r-l > 1 {
		mid := l + (r-l)>>1
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			l = mid
		} else {
			r = mid
		}
	}

	return -1
}

27.移除元素

分析

1. 同向双指针，快慢之分
2. 快指针寻值，慢指针改值

代码

func removeElement(nums []int, val int) int {
	s, f := 0, 0
	length := len(nums) - 1

	// 快指针超出数组长度，终止循环
	for f <= length {
		// 快指针值不等于val，慢指针值等于快指针值
		// 快指针值等于val，忽略数组的值
		if nums[f] != val {
			nums[s] = nums[f]
			s++
		}
		f++
	}

	return s

}

977.有序数组的平方

分析

1. 相向双指针，相碰循环结束，同时寻值
2. 不递减数列，考虑负数，比大小，大的先放，所以从列表尾向列表头插数据

代码

func sortedSquares(nums []int) []int {
	l, r := 0, len(nums)-1
	i := len(nums) - 1

	out := make([]int, len(nums))
	for l <= r {
		// nums[s] nums[f] 平方 比大小
		lq, rq := nums[l]*nums[l], nums[r]*nums[r]
		if lq < rq {
			out[i] = rq
			r--
		} else {
			out[i] = lq
			l++
		}
		i--
	}
	return out
}

总结

1. 区间划分
2. 双指针