求职 力扣刷题 60天--day 2_找工作 力扣题

这里是引用

12. 数组

12.1 977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
1
2
3
4

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
1
2

思路

左右指针加双端队列，向中间靠，l = r的时候退出循环，当 l >= 0 的时候 l 不动。

核心思路，nums数组的平方和从两端到中间越来越小（特殊情况，nums[0] >= 0， 这个时候，平方和最小的在最左侧） ，左右指针，谁的平方更大，谁先加入双端队列。

代码：

from collections import deque
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 左右指针加双端队列，向中间靠，l = r的时候退出循环，当 l >= 0 的时候 l 不动
        l, r = 0, len(nums) - 1
        res = deque()
        while l <= r:
            if nums[l] < 0:
                if nums[r] > -nums[l]:
                    res.appendleft(nums[r]**2)
                    r -= 1
                else:
                    res.appendleft(nums[l]**2)
                    l += 1
            else:
                res.appendleft(nums[r]**2)
                r -= 1
        return list(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

12.2 209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

思路：

双指针， 注意双指针可以使用for循环，也可以快慢指针，fast每次动一个，slow 循环直到sum_value < target

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 双指针， 快慢指针
        n = len(nums)
        min_length = n + 1
        slow, fast = 0, 0
        sum_value = 0 

        while fast < n:
            sum_value += nums[fast]
            while sum_value >= target:
                length = fast - slow + 1
                min_length = min(min_length, length)
                sum_value -= nums[slow]
                slow += 1
            fast += 1
        return min_length if min_length <= n else 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

12.3 59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

思路

四个边界：l, r, b, t

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0] * n for i in range(n)]
        l, r ,b ,t = 0, n - 1, 0, n - 1 
        value = 1

        while True:
            for j in range(l, r + 1):
                res[b][j] = value
                value += 1
            b += 1
            for i in range(b, t + 1):
                res[i][r] = value
                value += 1
            r -= 1
            for j in range(r, l - 1, -1):
                res[t][j] = value
                value += 1
            t -= 1
            for i in range(t, b - 1, -1):
                res[i][l] = value
                value += 1
            l += 1
            
            if value > n ** 2:
                return res 
            elif value == n ** 2:
                res[l][b] = value
                return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29