2024-05-28-代码随想录-Day2-数组2

other

Posted by berlinfog on May 28, 2024

数组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
}