首页 > 其他分享 >【随想录day2】LeetCode209长度最小的子数组 | LeetCode59螺旋矩阵

【随想录day2】LeetCode209长度最小的子数组 | LeetCode59螺旋矩阵

时间:2024-09-13 23:45:57浏览次数:11  
标签:matrix 随想录 day2 LeetCode59 range num 数组 offset 长度

LeetCode209长度最小的子数组

1、题目:

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0
示例:

输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
提示:

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

2、代码

2.1 Python版

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        sum = 0
        i = 0
        j = 0
        subl = 0
        result = float('inf')
        while j < len(nums):
            sum += nums[j]
            while sum >= target:
                subl = j - i + 1
                result = min(result, subl)
                sum -= nums[i]
                i += 1
            j += 1
        return result if result != float('inf') else 0

2.2 C++版

3、总结

1、在使用双指针法的时候,j作为双指针的右下标来遍历整个列表
2、在j老实前进的过程中,i作为左下标的收紧区间来找到最小长度的子串。中间时时更新,找到一个小了一点的长度值就喜新厌旧地丢弃原来的长度。而它的初始化长度是老实巴交的float('inf'),一个注定被抛弃的存在。因为如果他不被抛弃,那就意味着我们遍历整个数组的努力是徒劳。而即便他幸运地,或者不幸地没有被抛弃,他也终究不会被返回。我们毫无发现时,函数将返回0,略带失望。
3、双指针法就是这样的,有时候我觉得他不如暴力法。在暴力法中,作为子集两端的下标i和j相伴走到最后,哪怕是徒劳。返回0的失望与他们无关。我喜欢后一个故事,但是效率让我们选择前者。

LeetCode

1、题目:

给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

2、代码

2.1 Python版

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        startx, starty = 0, 0
        loop, mid = n // 2, n//2
        num = 1
        matrix = [[0] * n for _ in range(n)]    

        #range取的是左闭右开区间
        for offset in range(1, loop + 1):
            for i in range(starty, n - offset):
                matrix[startx][i] =  num
                num += 1
            for i in range(startx, n - offset):
                matrix[i][n - offset] = num
                num += 1
            for i in range(n - offset, starty, -1):
                matrix[n - offset][i] = num
                num +=1
            for i in range(n - offset, startx, -1):
                matrix[i][starty] = num
                num += 1
        
            startx += 1
            starty += 1

        if n % 2 != 0:
            matrix[mid][mid] = num
    
        return matrix

2.2 C++版

3、总结

1、循环不变量,重复的相遇发生在每一个转角,我希望邂逅你,而这也是事实。
2、晕了,待补

参考资料

https://programmercarl.com/0209.长度最小的子数组.html#算法公开课
https://programmercarl.com/0059.螺旋矩阵II.html#其他语言版本

标签:matrix,随想录,day2,LeetCode59,range,num,数组,offset,长度
From: https://www.cnblogs.com/jchen2022/p/18411662

相关文章

  • 代码随想录算法训练营,9月13日 | 654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索
    654.最大二叉树题目链接:654.最大二叉树文档讲解︰代码随想录(programmercarl.com)视频讲解︰最大二叉树日期:2024-09-13想法:根据昨天中后序列构造二叉树的经验,要找到数组中的最大值的位置,可以设置两个指针表示子树的范围(左闭右开)Java代码如下:classSolution{publicTreeNo......
  • 重生之我在代码随想录刷算法第一天 | 704.二分查找、27.移除元素
    参考文献链接:代码随想录本人代码是Java版本的,如有别的版本需要请上代码随想录网站查看。704.二分查找力扣题目链接解题思路这道题明确规定了数组是有序并且不重复的,要在这样的数组中寻找一个给定值的位置不由得让我想起来以前的数学知识二分查找。所以很快确定了思路......
  • 代码随想录算法 - 二叉树3
    题目1513.找树左下角的值给定一个二叉树的根节点root,请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7提示:二叉树的节点个数的范围是[1,104]-......
  • Day2|209.长度最小的子数组|59.螺旋矩阵II|区间和|开发商购买土地
    209.长度最小的子数组59.螺旋矩阵II 209.长度最小的子数组classSolution{publicintminSubArrayLen(inttarget,int[]nums){intfastIndex=0;intslowIndex=0;intsums=0;intresult=Integer.MA......
  • 代码随想录突击版刷题
    704.二分查找https://leetcode.cn/problems/binary-search/description/ 59.螺旋矩阵II https://leetcode.cn/problems/spiral-matrix-ii/description/、参考题解写出54.螺旋矩阵 https://leetcode.cn/problems/spiral-matrix/description/classSolution{public:......
  • B. 【20省选十联测day2】bitrev
    B.【20省选十联测day2】bitrev求\(\sum_{i-1}^Rpopcount(i+g(i))\),其中\(g(i)\)表示把\(i\)的二进制(不含前导\(0\))reverse得到的数。\(R\le10^{14}\)。显然这种东西我们会想到数位DP。于是正解是一个很恶心的数位DP。首先我们要按枚举有效位数\(x\),显然\(x=1\)......
  • 代码随想录算法训练营,9月12日 | 513.找树左下角的值,112. 路径总和,106.从中序与后序遍
    513.找树左下角的值题目链接:513.找树左下角的值文档讲解︰代码随想录(programmercarl.com)视频讲解︰找树左下角的值日期:2024-09-12想法:1.迭代:用层序遍历,遍历每层时记录下第一个节点的值,到最后一层就是要求的值;2.递归:根据最大的深度来找目标值。Java代码如下://迭代classSolut......
  • 图论篇--代码随想录算法训练营第五十七天打卡| 最小生成树问题
    题目链接:53.寻宝(第七期模拟笔试)题目描述:在世界的某个区域,有一些分散的神秘岛屿,每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路,方便运输。不同岛屿之间,路途距离不同,国王希望你可以规划建公路的方案,如何可以以最短的总公路距离将所有岛屿联通起来(注意:这......
  • NOIP2024集训Day27 DP常见模型4 - 树形
    NOIP2024集训Day27DP常见模型4-树形E.[COCI2014-2015#1]Kamp首先只考虑一个点,发现如果回到原来位置是比较好搞的,就每次走完子树的里面要的就上来,如果子树里面没有要走的就不走。(大概是\(f_x=\sumf_y+2\cdote_x\),因为要走过去走回来,注意\(y\)要保证子树里面有人)......
  • 【题解】Solution Set - NOIP2024集训Day27 树形 dp
    【题解】SolutionSet-NOIP2024集训Day27树形dphttps://www.becoder.com.cn/contest/5521「HDU4661」MessagePassing「BZOJ3935」Rbtree「ARC101E」RibbonsonTree「AGC034E」CompleteCompress「COCI2014.10」Kamp「SCOI2015」小凸玩密室「AGC008F」Black......