首页 > 其他分享 >[代码随想录]Day02-数组part02

[代码随想录]Day02-数组part02

时间:2023-07-27 22:45:57浏览次数:46  
标签:遍历 nums int Day02 part02 随想录 lens ++ res

题目:977. 有序数组的平方

思路:

一开始的思路是从中间向两边扩:

  1. 找到第一个大于等于0的位置r;判断nums[r]是否大于等于0,如果不是赋值为len(nums)表示不在范围内了。
  2. l的位置在r的左侧因此l = r - 1
  3. 只要l>=0或者r<len(nums)满足一个就可以继续;遍历时要保证数组不能越界

说实话维护起来有些复杂了,但是逆向思考一下,既然可以从中间向两边扩那是否可以从两边向中间缩?当然可以!

  1. l初始位置0,r初始位置len(nums)
  2. 每次判断l和r位置上的数谁更大,放在结果数组的尾部即可。

代码1:

从两边向中间缩

func sortedSquares(nums []int) []int {
    lens := len(nums)
    res := make([]int,lens) // 结果长度为lens
    l, r := 0, lens-1
    for i := lens - 1; i >= 0 ; i-- { // 逆序
        a, b := nums[l]*nums[l], nums[r]*nums[r]
        if a > b { // 大的放在后面
            res[i] = a
            l++
        }else {
            res[i] = b
            r--
        }
    }
    return res
}

代码2:

从中间向两边扩

func sortedSquares(nums []int) []int {
    l, r := 0, 0
    lens := len(nums)
    res := []int{}
    for i:=0 ; i < lens; i++ {  // 找到第一个大于等于0的位置
        if nums[i] >= 0 {
            r  = i
            break
        }
    }
    if nums[r] < 0 { // 如果nums[r] < 0 说明全是负数
        r = lens
    }
    l = r - 1 // l在r的左侧开始
    for l >= 0 || r < lens { // 只要有一个满足就可以继续
        if l == -1 {
            res = append(res, nums[r] * nums[r])
            r++
        }else if r == lens{
            res = append(res, nums[l] * nums[l])
            l--
        }else if -nums[l] < nums[r] { // 正序找小的放在前面
            res = append(res, nums[l] * nums[l])
            l--
        }else {
            res = append(res, nums[r] * nums[r])
            r++
        }
    }
    return res
}

参考:

文章讲解

视频讲解

题目:209. 长度最小的子数组

思路:

209.长度最小的子数组

滑动窗口说白了就是高级版的双指针法,滑动窗口无非就是双指针的同时还要维护两个指针中间部分元素的某个特定条件,比如本题是两个指针中间的元素和。

本题的几个要点:

  1. l和r都是从0开始出发
  2. 如果滑动窗口内元素和小于target右指针向右(如果左指针向右只会变得更小)
  3. 如果滑动窗口内元素和大于等于target左指针向右,直到不再满足该条件

因为题目要找的是最少元素,因此当滑动窗口内元素和第一次大于等于target时再向右移动右指针就没有意义了;此时向右移动左指针看是否可以减少元素的同时满足条件。

代码:

滑动窗口

func minSubArrayLen(target int, nums []int) int {
    l := 0
    sum := 0
    res := 1000000 // 长度
    for r := 0 ; r <len(nums); r++ { // 遍历右窗口
        sum += nums[r]
        for sum >= target { // 左窗口向右
            res = min(res, r - l + 1)
            sum -= nums[l]
            l++
        }
    }
    if res == 1000000 {
        return 0
    }
    return res
}

func min(a,b int) int { // 返回较小的值
    if a < b {
        return a
    }
    return b
}

参考:

文章讲解

视频讲解

题目:59. 螺旋矩阵 II

思考:

把矩阵看成多个圆,每次遍历一个圆,遍历一次的过程是:

image-20230727221857056

  1. top上部,从left遍历到right
  2. right右侧,从top-1遍历到bottom
  3. bottom下部,从right-1遍历left
  4. left左侧,从bottom+1遍历到top-1

之后就是分治思想每次重复上述步骤就行了;当只剩下一行或者一列的时候就不要继续四次遍历了,两次即可。比如上面图两次遍历上、右就完成了填充,如果四次遍历的话第三次的遍历(绿色)会覆盖掉第一次遍历的结果(红色),所以这里加了一个if判定。

代码:

func generateMatrix(n int) [][]int {
    res := make([][]int,n) // 行数row
    for i := range res {
        res[i] = make([]int,n) // 列数col
    }
    left,right,top,bottom := 0, n-1, 0, n-1 // 初始的边界
    cnt := 1 
    for left <= right && top <= bottom {
        for col := left ; col <= right; col ++ {
            res[top][col] = cnt
            cnt++
        } // 填充上部
        for row := top + 1; row <= bottom; row ++ {
            res[row][right] = cnt
            cnt++
        }// 填充右侧
        if left < right && top < bottom { // 在长宽不相等的情况下,如果只剩下一行或者一列只需要上面两步即可完成。
            for col := right - 1; col >= left; col-- {
                res[bottom][col] = cnt
                cnt++
            }// 填充下部
            for row := bottom - 1; row > top; row-- {
                res[row][left] = cnt
                cnt++
            }// 填充左侧
        }
        // 边界向中心靠
        left++ 
        right--
        top++
        bottom--
    }
    return res
}

参考:

文章讲解

视频讲解

标签:遍历,nums,int,Day02,part02,随想录,lens,++,res
From: https://www.cnblogs.com/wtcsky/p/17586305.html

相关文章

  • [代码随想录]Day01-数组part01
    题目:704.二分查找思路:二分查找一般是在有序的数组中查找指定的值,单纯的查找值,把数组跑一遍的复杂度为O(n)。二分查找每次把范围缩小一半,我们每次都去中间的值,有以下三种情况:如果mid位置的值比target大,那么target应该在mid左侧的位置(由小到大排序情况下)如果mid位置的值比t......
  • 代码随想录算法训练营第一天| LeetCode 704. 二分查找、LeetCode 27. 移除元素
    704.二分查找    题目链接:https://leetcode.cn/problems/binary-search/   视频链接:https://www.bilibili.com/video/BV1fA4y1o715     文章讲解:https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html    卡哥的题目建......
  • day02Java的概念
    day02Java的概念一、入门案例详解如何开发一个Java程序需求:输出HelloWorld!!!新建文本文档,命名为HelloWorld,将后缀名.txt修改为.java(创建一个Java文件)在Java文件中创建类语法:class类名{}EXclassDemo{}在类中添加main方法main方法也叫主方法,是程序的入口p......
  • 代码随想录算法训练营第三十六天| 198.打家劫舍 213.打家劫舍II 337.打家劫舍III
     198.打家劫舍 要求:给定一个nums,要求取得最大值,但是不可以选择两个相邻的数dp定义:dp[n],取到第N个数字的时候,最大值递推公式:取:nums[i]+dp[j-2]不取:nums[i-1];代码:1//在两个数字不相邻的情况下,得到的最大金额2//思路:3//dp[n]第N个数字时的最大金额数4......
  • 代码随想录-链表-C++总结
    代码随想录(programmercarl.com)这次复习的主要目的还是熟练c++的基本语法知识,顺带过一下链表的典型题目印象深刻直接没做出来的有7.链表相交,没有想到先过一遍求出两条链表的长度,然后通过长度差的信息来get交点做的时候写出bug的有3.设计链表,涉及的基础思想还是比较多的,需......
  • html学习day02
    HITML学习Day02一、媒体属性视频属性<video></video>属性:src:资源路径controls:控制条autoplay:自动播放音频属性<audio></audio>属性src:资源路径controls:控制条autoplay:自动播放二、页面结构元素名描述header标记头部区域的内容(用......
  • 代码随想录贪心专题-day1
    35.分发糖果n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:每个孩子至少分配到1个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果,计算并返回需要准备的最少糖果数目。思路:本题这......
  • 代码随想录训练营 Day01- 数组(上)
    概述第一天主要学习的是数组相关的内容,相关学习的内容包括数组的基本特性的学习,二分搜索方法的学习。数组特点数组的基本特点包括:下标从0开始内存连续性(Java中定义数组需要直接声明其空间大小)数组元素不可以删,只能覆盖ArrayList底层是数组实现,其实际上应该叫一......
  • 代码随想录算法训练营第三十三天| 1049. 最后一块石头的重量 II 494. 目标和 474.一
    1049.最后一块石头的重量II思路:因为含有两个石头的相撞,所以需要把dp的目标值改成sum/2,然后取得这个目标值的最大值,然后对sum-2*target代码:1//要求:有多个石头,两两撞击,取得剩下的石头的最小值2//——》一定要碰到最后一个3//注意:4//1,x==y:两个粉碎,x<y:y=......
  • 代码随想录算法训练营第57天 | ● 647. 回文子串 ● 516.最长回文子序列 ● 动
     第九章 动态规划part17●  647. 回文子串  ●  516.最长回文子序列●  动态规划总结篇 今天 我们就要结束动态规划章节了,大家激不激动!!!   详细布置   647. 回文子串    动态规划解决的经典题目,如果没接触过的话,别硬想 直接看题解。https:......