首页 > 其他分享 >代码随想录Day2 | LeetCode 209. 长度最小的子数组、LeetCode 59. 螺旋矩阵 II、KamaCoder 44. 开发商购买土地

代码随想录Day2 | LeetCode 209. 长度最小的子数组、LeetCode 59. 螺旋矩阵 II、KamaCoder 44. 开发商购买土地

时间:2024-09-17 17:45:35浏览次数:10  
标签:59 matrix idx int res 随想录 range LeetCode left

LeetCode 209. 长度最小的子数组

子数组是一个连续的,很容易想到滑动窗口

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        windowSum = 0
        left, right = 0, 0
        res = float('inf')
        while right < len(nums):
            push = nums[right]
            windowSum += push
            right += 1

            while windowSum >= target:
                res = min(res, right - left)
                pop = nums[left]
                windowSum -= pop
                left += 1
        return res if res != float('inf') else 0

拓展

如果 nums 数组中包含负数,则窗口扩大时元素和不见得就增大,窗口缩小时元素和不见得就减小,这种情况就不能单纯使用滑动窗口技巧了,可能需要混合动态规划和单调队列来做。

862. 和至少为 K 的最短子数组

LeetCode 1425. 带限制的子序列和

LeetCode 53. 最大子数组和

这里给出的是滑动窗口解法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        windowSum = 0
        res = float("-inf")
        left = right = 0
        while right < len(nums):
            push = nums[right]
            windowSum += push
            right += 1
            
            res = max(res, windowSum)

            while windowSum < 0:
                pop = nums[left]
                windowSum -= pop
                left += 1

        return res 

LeetCode 59. 螺旋矩阵 II

模拟题,做这一题之前可以先试试 LeetCode 54. 螺旋矩阵

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[None for _ in range(n)] for _ in range(n)]
        idx = 1
        a, b, x, y = 0, 0, n - 1, n - 1
        for _ in range(n ** 2):
            for j in range(b, y + 1):
                matrix[a][j] = idx
                idx += 1
            a += 1
            for i in range(a, x + 1):
                matrix[i][y] = idx
                idx += 1
            y -= 1
            for j in range(y, b - 1, -1):
                matrix[x][j] = idx
                idx += 1
            x -= 1
            for i in range(x, a - 1, -1):
                matrix[i][b] = idx
                idx += 1
            b += 1
        return matrix

LeetCode 54. 螺旋矩阵

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix) - 1, len(matrix[0]) - 1
        x, y = 0, 0
        res = []
        while x <= m and y <= n:
            for j in range(y, n + 1):
                if x <= m and y <= n:
                    res.append(matrix[x][j])
            x += 1
            for i in range(x, m + 1):
                if x <= m and y <= n:
                    res.append(matrix[i][n])
            n -= 1
            for j in range(n, y - 1, -1):
                if x <= m and y <= n:
                    res.append(matrix[m][j])
            m -= 1
            for i in range(m, x - 1, -1):
                if x <= m and y <= n:
                    res.append(matrix[i][y])
            y += 1
        return res          

KamaCoder 44. 开发商购买土地

前缀和思想

import sys

def find(matrix):
    m, n = len(matrix), len(matrix[0])
    preSum_matrix = [[None for _ in range(n)] for _ in range(m)]
    preSum_matrix[0][0] = matrix[0][0]
    for i in range(m):
        for j in range(n):
            up = preSum_matrix[i - 1][j] if i - 1 >= 0 else 0
            left = preSum_matrix[i][j - 1] if j - 1 >= 0 else 0
            left_up = preSum_matrix[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0
            preSum_matrix[i][j] = matrix[i][j] + up + left - left_up
    res = float('inf')
    for i in range(m - 1):
        if res == 0:
            return 0
        res = min(res, abs(preSum_matrix[m - 1][n - 1] - preSum_matrix[i][n - 1] * 2))
    for j in range(n - 1):
        if res == 0:
            return 0
        res = min(res, abs(preSum_matrix[m - 1][n - 1] - preSum_matrix[m - 1][j] * 2))
    return res
        
if __name__ == "__main__":
    lines = sys.stdin.read().strip().splitlines()
    idx = 0
    res = []
    while idx < len(lines):
        m, n = map(int, lines[idx].strip().split())
        idx += 1
        matrix = []
        for _ in range(m):
            line = list(map(int, lines[idx].strip().split()))
            matrix.append(line)
            idx += 1
        res.append(str(find(matrix)))
    sys.stdout.write("\n".join(res))

标签:59,matrix,idx,int,res,随想录,range,LeetCode,left
From: https://www.cnblogs.com/li508q/p/18417346

相关文章

  • 【LeetCode Hot 100】5. 最长回文子串
    题目描述考虑回文字符串的特点,从左往右和从右往左读都是一样的,就是说字符串成了“轴对称”。要求一字符串的最长回文子串,我们可以遍历每个字符,求以该字符为轴对称中心的最长对称子串(或者以该字符和下一个字符为中间两个字符的对称子串),在所有这样的子串中长度最长的那个就是我们要......
  • leetCode2:两数相加(链表)
    题目:给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字0之外,这两个数都不会以0开头。思路:遍历两个链表,逐位相加,还要加上进位结......
  • Leetcode 85. 最大矩形
    1.题目基本信息1.1.题目描述给定一个仅包含0和1、大小为rowsxcols的二维二进制矩阵,找出只包含1的最大矩形,并返回其面积。1.2.题目地址https://leetcode.cn/problems/maximal-rectangle/description2.解题方法2.1.解题思路动态规划+单调栈,可以参考Leetcode84.柱......
  • Leetcode 297. 二叉树的序列化与反序列化
    1.题目基本信息1.1.题目描述序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序......
  • Leetcode 952. 按公因数计算最大组件大小
    1.题目基本信息1.1.题目描述给定一个由不同正整数的组成的非空数组nums,考虑下面的图:有nums.length个节点,按从nums[0]到nums[nums.length-1]标记;只有当nums[i]和nums[j]共用一个大于1的公因数时,nums[i]和nums[j]之间才有一条边。返回图中最大连通组件的大小......
  • Leetcode 19.删除链表的倒数第第N个结点
    1.题目基本信息题目:给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。地址:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/2.解题方法2.1.解题思路使用快慢指针2.2.解题步骤第一步,初始化快指针为head,慢指针指向一个哑结点,哑结点......
  • 代码随想录算法训练营,9月17日 | 669. 修剪二叉搜索树,108.将有序数组转换为二叉搜索树,5
    669.修剪二叉搜索树题目链接:669.修剪二叉搜索树文档讲解︰代码随想录(programmercarl.com)视频讲解︰修剪二叉搜索树日期:2024-09-17想法:节点为空返回空,值在中间时,继续递归左右两边,小于时递归右子树,大于时递归左子树Java代码如下:classSolution{publicTreeNodetrimBST......
  • Leetcode 2183. 统计可以被 K 整除的下标对数目
    1.题目基本信息1.1.题目描述给你一个下标从0开始、长度为n的整数数组nums和一个整数k,返回满足下述条件的下标对(i,j)的数目:0<=i<j<=n-1且nums[i]*nums[j]能被k整除。1.2.题目地址https://leetcode.cn/problems/count-array-pairs-divisible-by-k......
  • Leetcode—815. 公交路线【困难】(unordered_map+queue)
    2024每日刷题(163)Leetcode—815.公交路线bfs实现代码classSolution{public:intnumBusesToDestination(vector<vector<int>>&routes,intsource,inttarget){if(source==target){return0;}unordered_map<......
  • 代码随想录Day15 动态规划--2
    01背包理论基础01背包是有一个背包有M的容量给我们N个物品每个物品有自己的价值我们需要装进背包里尽可能获得最大的价值分析题目把背包想象成一个二维数组先遍历每个物品放入背包里面dp数组的含义表示的就是背包所含有的价值当我们遍历物品1的时候我们要开始更新背包......