数组2
Task
977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结
建议大家先独立做题,然后看视频讲解,然后看文章讲解,然后在重新做一遍题,把题目AC,最后整理成今日当天的博客
拓展题目可以先不做
977.有序数组的平方
题目建议: 本题关键在于理解双指针思想
题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解: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
视频讲解: https://www.bilibili.com/video/BV1QB4y1D7ep
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
代码
//先找到大于0的点,再往两边拓宽
func sortedSquares(nums []int) []int {
i := 0
n := len(nums)
for ;i < n; i++{
if nums[i] > 0{
break
}
}// [0,i-1] [i,n-1]
ans := make([]int,0,n)
for l,r := i-1, i; l >= 0 || r < n; {
if l < 0 {
ans = append(ans,nums[r]*nums[r])
r++
}else if r >= n {
ans = append(ans,nums[l]*nums[l])
l--
}else if nums[l] * nums[l] > nums[r] * nums[r]{
ans = append(ans,nums[r] * nums[r])
r++
}else{
ans = append(ans,nums[l] * nums[l])
l--
}
}
return ans
}
//双指针,两边轮流加答案
func sortedSquares(nums []int) []int {
m := len(nums)
ans := make ([]int,m)
l := 0
r := m-1
idx := 0
for l <= r{
if(nums[l]*nums[l]>nums[r]*nums[r]){
ans[m-1-idx] = nums[l]*nums[l]
idx++
l++
}else{
ans[m-1-idx] = nums[r]*nums[r]
idx++
r--
}
}
return ans
}
//first half get smallest number and then two direction
209.长度最小的子数组
题目建议: 本题关键在于理解滑动窗口,这个滑动窗口看文字讲解 还挺难理解的,建议大家先看视频讲解。 拓展题目可以先不做。
题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解: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
视频讲解:https://www.bilibili.com/video/BV1tZ4y1q7XE
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组
[numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
代码
//left and right two pointers and if less than target extend right,if larger than and len longer than extend left
func minSubArrayLen(target int, nums []int) int {
//l and r two pointer , move r until >=target,then update len,then move l until < target
m := len(nums)
l := 0
r := 0
tempval := 0
ans := math.MaxInt32
for r < m {
for r < m && tempval < target {
tempval += nums[r]
r++
}// get most right
for l < m && tempval >= target{
ans = min(r-l,ans)
tempval -= nums[l]
l++
}
}
if ans > m{
return 0
}else{
return ans
}
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
59.螺旋矩阵II
题目建议: 本题关键还是在转圈的逻辑,在二分搜索中提到的区间定义,在这里又用上了。
题目链接:https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解:https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解:https://www.bilibili.com/video/BV1SL4y1N7mV/
总结
题目建议:希望大家 也做一个自己 对数组专题的总结
文章链接:https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html
func generateMatrix(n int) [][]int {
t := 0
b := n-1
l := 0
r := n-1
idx := 1
mat := make([][]int,n)
for k := range mat {
mat[k] = make([]int,n)
}
for idx <= n*n {
for i := l; i <= r; i++{
mat[t][i] = idx
idx++
}
t++
for j := t; j <= b; j++{
mat[j][r] = idx
idx++
}
r--
for i := r; i >= l; i-- {
mat[b][i] = idx
idx++
}
b--
for j := b; j >= t; j-- {
mat[j][l] = idx
idx++
}
l++
}
return mat
}