• 代码随想录算法训练营第二天| 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II

  ---

  代码随想录算法训练营第二天

  • • 977.有序数组的平方
    • 209.长度最小的子数组
    • 59.螺旋矩阵II

  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. 当排序数组中既包括正数，又包括负数时，应该先遍历数组，计算出负数的个数，然后利用双指针，left表示负数的个数，初始化为**-1**，right表示非负数的索引，right=left+1；
  4. 循环条件：left>=0 or right < len(nums)
     • left < 0 时，按照思路1排序
     • right > len(nums)，按照思路2排序
     • 否则比较left和right元素绝对值的大小，取绝对值小的元素，同时对该元素的索引进行操作(left-=1 或 right+=1)

  代码

  #  !/usr/bin/env  python
  #  -*- coding:utf-8 -*-
  # @Time   :  2022.10
  # @Author :  hello algorithm!
  # @Note   : https://leetcode.cn/problems/squares-of-a-sorted-array/
  from typing import List
  
  
  class Solution:
      def sortedSquares(self, nums: List[int]) -> List[int]:
          result = []
          left = -1
          length = len(nums)
          for i in range(length):
              if nums[i] < 0:
                  left += 1
              else:
                  break
          right = left + 1
          while right < length or left >= 0:
              if right >= length:
                  result.append(nums[left] ** 2)
                  left -= 1
              elif left < 0:
                  result.append(nums[right] ** 2)
                  right += 1
              elif abs(nums[right]) > abs(nums[left]):
                  result.append(nums[left] ** 2)
                  left -= 1
              else:
                  result.append(nums[right] ** 2)
                  right += 1
  
          return result
  
  
  if __name__ == '__main__':
      nums = [-4, -1, 0, 3, 10]
      s = Solution()
      print(s.sortedSquares(nums))
  
  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
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41

  209.长度最小的子数组

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

  找出该数组中满足其和 ≥ target 的长度最小的 连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0 。

  示例1

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

  思路

  1. 双指针+滑动窗口进行解决
  2. 初始化left,right = 0,0,sub_array_len = inf
  3. 循环条件：right
  4. sum += nums[right]
  5. 循环条件，而非if条件，当[left,right]区间元素之和sum>target时，left += 1,sum-=nums[left],sub_array_len = min(sub_array_len, right - left + 1)
  6. right += 1

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/minimum-size-subarray-sum/
from math import inf
from typing import List


class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        length = len(nums)
        left = 0
        right = 0
        sum = 0
        sub_array_len = inf
        while right < length:
            sum += nums[right]
            while sum >= target:
                sub_array_len = min(sub_array_len, right - left + 1)
                sum = sum - nums[left]
                left += 1
            right += 1
        if sub_array_len == inf:
            sub_array_len = 0
        return sub_array_len


if __name__ == '__main__':
    s = Solution()
    target = 10
    nums = [1, 4, 4]
    print(s.minSubArrayLen(target, nums))

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
30
31
32
33
34

59.螺旋矩阵II

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

示例

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

输入：n = 1
输出：[[1]]

思路

本题为模拟题，需要注意点如下：

1. 模拟四个方向，依次是右，下，左，上四个方向
2. 分别转loop=n//2圈，其中n为奇数时，result[n//2][n//2]=n
3. 第i圈的起点为i,i,终点为n-i-1

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/spiral-matrix-ii/
from typing import List


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        result = []
        for i in range(n):
            temp = []
            for j in range(n):
                temp.append(0)
            result.append(temp)
        loop = n // 2
        num = 1
        for i in range(loop):
            # 右方向模拟
            for j in range(i,n-i-1):
                result[i][j] = num
                num += 1

            # 下方向模拟
            for j in range(i,n-i-1):
                result[j][n-i-1] = num
                num += 1

            # 左方向模拟
            for j in range(n - i - 1, i,-1):
                result[n - i - 1][j] = num
                num += 1

            # 上方向模拟
            for j in range(n - i - 1, i, -1):
                result[j][i] = num
                num += 1
        if n % 2:
            result[loop][loop] = n*n

        return result


if __name__ == '__main__':
    n = 1
    s = Solution()
    print(s.generateMatrix(n))

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49