本文主要是介绍day2 | 数组 part-2 | 977 有序数组的平方、209 长度最小的子数组、59 螺旋矩阵 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今日任务
- 977 有序数组的平方 (题目: . - 力扣(LeetCode))
- 209 长度最小的子数组 (题目: . - 力扣(LeetCode))
- 59 螺旋矩阵 II (题目:. - 力扣(LeetCode))
有序数组的平方 (双指针)
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
想法:
这个题目猛一看其实挺简单的,直接计算所有平方,因为有负整数,还需要再排下序.就可以了,但是要求了有 o(n)的要求,肯定是让整点花活的.
问题:
想到要用到双指针,写代码时采用了快慢双指针,但是没想好处理下一步,如何使数据平方后保存,当时一直纠结在原数组上去处理,想着快慢指针将负数取反和大于 0 的数对比替换(因为是非递减嘛,即数字是递增或相等的),一直卡在这了. 后面看了讲解,才想起我不必在原数组上去操作的(🥲🥲)
解决思路:
创建一个和原数组等长的新数组、使用首尾双指针,计算对比平方之后的值得大小、将大的值插入新数组的尾部(因为非递减的属性,即使左侧是负数,平方之后也可能会是最大的值)、移动指针、循环....
func sortedSquares(nums []int) []int {result := make([]int,len(nums))left,right,k := 0,len(nums)-1,len(nums)-1// for k >= 0{ // 这两个循环条件都可以for left <= right{if nums[left]*nums[left] >= nums[right]*nums[right] {result[k] = nums[left] * nums[left]left ++} else {result[k] = nums[right]*nums[right]right --}k --}return result
}
长度最小的子数组 (双指针 窗口滑动)
找出该数组中满足其总和大于等于 target
的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0
。
想法:
.....看到题没想法,暴力的写法(双重 for 循环)都未写,直接看了题解
问题:
滑动窗口 即快慢双指针,好像不难理解,但是呢对于快慢指针该如何移动要想透彻,还有就是如何统计窗口的大小(小数组的值)
解决思路:
创建一个快慢指针,快指针往前走,同时计算身后元素的累加结果(第一个 for 循环),直到累加结果大于等于目标值了,就先停下来,等一等我们的慢指针(for 循环),这时计算 slow 和 fast 之间的距离,以及就累加结果减去 slow 对应的元素,看看当前窗口的值是否能够大于目标值....
func minSubArrayLen(target int, nums []int) int {slow, fast := 0, 0// 搞一个大于数组的值,这个用来存放我们发现的符合条件的数量result := len(nums)+1var res []intsum := 0for ; fast < len(nums); fast++ {// 就是先移动快指针sum += nums[fast]// 如果 fast 移动到某一步骤,后面的元素大于等于目标值了,则开始移动慢指针,// 确认一下最少几个元素可满足for sum >= target {l := fast - slow + 1// 保存最小的子数组长度if l < result {result = lres = nums[slow : fast+1]}sum -= nums[slow]slow++}}// 要判断一下这个值,没有符合条件的子数组时,要返回 0if result > len(nums){return 0}fmt.Println(res)return result
}
螺旋矩阵 II (有点抽象)
给你一个正整数 n
,生成一个包含 1
到 n2
所有元素,且元素按顺时针顺序螺旋排列的 n x n
正方形矩阵 matrix
。
想法:
看到题目时,完全没思路,想不出如何去给一个二维数组这样子赋值.......
问题:
起初看了几个题解,其中讲的比较多的什么确定 4 条边的边界,l、r、b、t ,但是看的云里雾里,,,
解决思路:
首先要理解 4 条边界是什么意思....待我总结一下
图片来自题解:. - 力扣(LeetCode)
func generateMatrix(n int) [][]int {sum := n * nresult := make([][]int, n)for i := 0; i < n; i++ {result[i] = make([]int, n)}k := 1l := 0r := n - 1t := 0b := n - 1// 每个边界 这里遵循的是左闭右闭for k <= sum {for i := l; i <= r; i++ {// 行固定,修改列result[t][i] = kk++}t++for i := t; i <= b; i++ {// 列固定,修改行result[i][r] = kk++}r--for i := r; i >= l; i-- {// 行固定,修改列,result[b][i] = kk++}b--// for i := r; i >= t; i-- { // 这个地方写的有问题,但是也碰巧过了for i := b;i >= t; i -- {// 列固定,修改行result[i][l] = kk++}l++}return result
}
这篇关于day2 | 数组 part-2 | 977 有序数组的平方、209 长度最小的子数组、59 螺旋矩阵 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!