首页 > 其他分享 >代码随想录day2| 977,209,59

代码随想录day2| 977,209,59

时间:2022-11-23 08:45:06浏览次数:47  
标签:977 count 59 nums int Sum 随想录 range offset

977.

暴力法:整个数组平方,然后再nums.sort(),时间复杂度O(nlogn) 空间复杂度O(1)

双指针法:从两头开始遍历,l,r指向当前有可能的最大值,i象征着新数组对应的位置,从大到小,时间复杂度:O(n), 空间复杂度:O(n)

 

 209.

暴力法:两层for循环,第一个是起始位置,第二个是终止位置,把所有数组的情况都遍历一遍,找到最小的数组长度

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if nums == None or len(nums) == 0:
            return 0
        if nums[0] >= target:
            return 1

        minimum = float("inf")
        for i in range(len(nums)):
            subarray_sum = 0
            for j in range(i,len(nums)):
                subarray_sum += nums[j]
                if j - i < minimum and subarray_sum == target:
                    minimum = j - i + 1
                
        if minimum == float("inf"):
            return 0
        else:
            return minimum

滑动窗口:类似于双指针,取两个指针中间的集合,所以叫滑动窗口

重点一:j指向终止位置,i起始位置动态移动——一个for循环的思路才能解决

重点二:【精华】如何移动起始位置

——当集合元素和>=s 说明符合条件,收集其长度后,i可以往后移动,缩小集合范围看下一个集合是否符合条件

result = float('inf') 先取最大值 之后才能取所有集合里的最小值

i=0

for(j=0,j<=nums.size-1,j++)

Sum+=nums[j]

Sum>=s 这里的逻辑是while 持续更新

subL=j-i+1
result = min(result,subL)

Sum=Sum-nums[i]

i++

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # 定义一个无限大的数
        res = float("inf")
        Sum = 0
        i = 0
        for j in range(len(nums)):
            Sum += nums[j]
            while Sum >= s:
                res = min(res, j-i+1)
                Sum -= nums[i]
                i += 1
        return 0 if res==float("inf") else res

59.螺旋矩阵

循环不变量:

[) 或者 [] 坚持一个原则,左闭右开 坚持到底

我们不去处理每条边的最后一个节点,把最后一个节点留给下一条边

这样转一圈,坚持左闭右开的原则,每一个点都会遍历到

每一条边的处理规则要统一——循环不变量

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        nums = [[0] * n for _ in range(n)]
        startx, starty = 0, 0               # 起始点
        loop, mid = n // 2, n // 2          # 迭代次数、n为奇数时,矩阵的中心点
        count = 1                           # 计数

        for offset in range(1, loop + 1) :      # 每循环一层偏移量加1,偏移量从1开始
            for i in range(starty, n - offset) :    # 从左至右,左闭右开
                nums[startx][i] = count
                count += 1
            for i in range(startx, n - offset) :    # 从上至下
                nums[i][n - offset] = count
                count += 1
            for i in range(n - offset, starty, -1) : # 从右至左
                nums[n - offset][i] = count
                count += 1
            for i in range(n - offset, startx, -1) : # 从下至上
                nums[i][starty] = count
                count += 1                
            startx += 1         # 更新起始点
            starty += 1

        if n % 2 != 0 :            # n为奇数时,填充中心点
            nums[mid][mid] = count 
        return nums

 

标签:977,count,59,nums,int,Sum,随想录,range,offset
From: https://www.cnblogs.com/cassiehao/p/16917131.html

相关文章