电影资源网站开发,网站建设app,永康企业网站建设公司,北京网站设计网站设计公司价格目录 二分查找1. 前提条件#xff1a;2. 二分查找边界 2.移除元素有序数组的平方长度最小的子数组59.螺旋矩阵II54. 螺旋矩阵 二分查找 参考链接 https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF 1. 前提条件#xff1a;
数… 目录 二分查找1. 前提条件2. 二分查找边界 2.移除元素有序数组的平方长度最小的子数组59.螺旋矩阵II54. 螺旋矩阵 二分查找 参考链接 https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF 1. 前提条件
数组为有序数组无重复元素因为一旦有重复元素使用二分查找法返回的元素下标可能不是唯一的。
2. 二分查找边界
[left, right]区间while (left right) 要使用 因为left right是有意义的所以使用 if (nums[middle] target) right 要赋值为 middle - 1因为当前这个nums[middle]一定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1
func search(nums []int, target int) int {high : len(nums)-1low : 0for low high {mid : low (high-low)/2if nums[mid] target {return mid} else if nums[mid] target {high mid-1} else {low mid1}}return -1
}区间[left, right)while (left right)这里使用 ,因为left right在是没有意义的 if (nums[middle] target) right 更新为 middle因为当前nums[middle]不等于target去左区间继续寻找而寻找区间是左闭右开区间所以right更新为middle即下一个查询区间不会去比较nums[middle]
func search(nums []int, target int) int {high : len(nums)low : 0for low high {mid : low (high-low)/2if nums[mid] target {return mid} else if nums[mid] target {high mid} else {low mid1}}return -1
}2.移除元素 参考链接 https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE 数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖。 所以不可以删除只能将等于val的值移到后面最后的结果返回数组满足条件的前半部分即可
func removeElement(nums []int, val int) int {left, right : 0, len(nums)-1for left right {if nums[left] val {nums[left] nums[right]right--} else {left}}return left
}
顺便从二分法学以致用【关于 left right 和 left right 的选择问题】
func removeElement(nums []int, val int) int {left, right : 0, len(nums)for left right {if nums[left] val {nums[left] nums[right-1]right--} else {left}}return left
}有序数组的平方 参考链接 https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC 双指针法 数组其实是有序的 只不过负数平方之后可能成为最大数了。 那么数组平方的最大值就在数组的两端不是最左边就是最右边不可能是中间。 此时可以考虑双指针法了i指向起始位置j指向终止位置。 定义一个新数组result和A数组一样的大小让k指向result数组终止位置。 如果A[i] * A[i] A[j] * A[j] 那么result[k–] A[j] * A[j]; 。 如果A[i] * A[i] A[j] * A[j] 那么result[k–] A[i] * A[i]; 。
func sortedSquares(nums []int) []int {n : len(nums)i, j, k : 0, n-1, n-1ans : make([]int, n)for i j {lm, rm : nums[i]*nums[i], nums[j]*nums[j]if lm rm {ans[k] lmi} else {ans[k] rmj--}k--}return ans
}长度最小的子数组 参考链接 https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE 给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。 示例 输入s 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 滑动窗口
func minSubArrayLen(target int, nums []int) int {if len(nums) 0 {return 0}slow, fast : 0, 0sum : nums[0]minLen : len(nums) 1for fast len(nums) {if sum target {minLen min(minLen, fast-slow1)//还要记住改变sum的值否则就会带着sum7这个结果一直循环sum sum - nums[slow]slow} else if sum target {fastif fast len(nums) {sum sum nums[fast]}} }if minLen len(nums)1 {return 0}return minLen
}59.螺旋矩阵II 给定一个正整数 n生成一个包含 1 到 n^2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 参考链接 https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE 每画一条边都要坚持一致的左闭右开或者左开右闭的原则这样这一圈才能按照统一的规则画下来
//左开右闭
func generateMatrix(n int) [][]int {top, bottom : 0, n-1left, right : 0, n-1num : 1tar : n * nmatrix : make([][]int, n)for i : 0; i n; i {matrix[i] make([]int, n)}for num tar {for i : left; i right; i {matrix[top][i] numnum}topfor i : top; i bottom; i {matrix[i][right] numnum}right--for i : right; i left; i-- {matrix[bottom][i] numnum}bottom--for i : bottom; i top; i-- {matrix[i][left] numnum}left}return matrix
}
54. 螺旋矩阵 给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。 输入matrix [[1,2,3],[4,5,6],[7,8,9]] 输出[1,2,3,6,9,8,7,4,5] func spiralOrder(matrix [][]int) []int {result : []int{}//矩阵先考虑条件if len(matrix) 0 || len(matrix[0]) 0 {return result}m, n : len(matrix), len(matrix[0])left, right, top, bottom : 0, n-1, 0, m-1for left right top bottom {// 从左到右for i : left; i right; i {result append(result, matrix[top][i])}// 从上到下for i : top 1; i bottom; i {result append(result, matrix[i][right])}// 从右到左确保有多行// 在螺旋顺时针遍历矩阵的过程中从右到左的遍历应该在确保存在多行的情况下进行。如果只有一行那么从右到左的遍历就没有意义因为在上一步已经从左到右遍历过了。因此通过 if top bottom 进行判断可以确保在有多行的情况下才进行从右到左的遍历。// 比如 6-7的过程因为经过一轮之后top1bottom1此时6-7是从左到右不需要从右到左下面的left right同理if top bottom {for i : right - 1; i left; i-- {result append(result, matrix[bottom][i])}}// 从下到上确保有多列if left right {for i : bottom - 1; i top; i-- {result append(result, matrix[i][left])}}leftright--topbottom--}return result
}
