网站服务器迁移,开发软件平台,wordpress 架构原理,成都到西安需要隔离吗目录 209. 长度最小的子数组1、题目描述2、思路3、code4、复杂度分析 LC59 螺旋矩阵 II1、题目描述2、思路3、code4、复杂度分析 209. 长度最小的子数组
题目链接#xff1a;209
1、题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于… 目录 209. 长度最小的子数组1、题目描述2、思路3、code4、复杂度分析 LC59 螺旋矩阵 II1、题目描述2、思路3、code4、复杂度分析 209. 长度最小的子数组
题目链接209
1、题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0。 示例 1 输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 2、思路
1️⃣ 暴力法两个for循环嵌套时间复杂度 O ( n 2 ) O(n^2) O(n2) 2️⃣ 题目基本是根据连续子序列的情况不断调节子序列的起始和终止位置滑动窗口 模板
3、code
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:# 找一个数组的满足条件的最短或者最长连续子数组滑动窗口minlen float(inf)start 0sum_sub 0for end in range(0,len(nums)):sum_sub nums[end]while sum_sub target:minlen min(minlen, end-start1)sum_sub - nums[start]start 1if minlen len(nums):return minlenelse:return 04、复杂度分析
时间复杂度 每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)空间复杂度没有创建数组 O ( 1 ) O(1) O(1)
LC59 螺旋矩阵 II
题目链接59
1、题目描述 给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 示例 1 2、思路
要控制每次循环的区间范围循环不变量 按照左闭右开的原则来画一圈大家看一下
3、code
class Solution:def generateMatrix(self, n: int) - List[List[int]]:# 首先先初始化一个全是0的nxn二维矩阵mat [[0 for _ in range(n)] for _ in range(n)]# 定义每一圈的起始点坐标start_x 0start_y 0# 定义表示不同圈的每一条边的倒数第二个节点的偏移量# 比如第1圈是j (n-1) - 1# 第2圈就是j (n-1) - 2offset 1# 定义要往矩阵中填入的数count 1loop n //2# 循环开始for time in range(0,loop):# 填充上行从左到右:横坐标不变且是start_x纵坐标从start_y到(n - 1) - 1for j in range(start_y, n - offset):# 因为range“顾头不顾腚”所以可以少写一个-1mat[start_x][j] countcount 1# 填充右列从上到下横坐标从start_x到(n-1)-offset纵坐标不变且是上行最后一个元素的坐标加一(j n - offset) # 此时到达了上行的倒数第二个元素(start_x,j (n-1)-offset)# 那么右列的第一个元素就是(start_x,n - offset)for i in range(start_x, n - offset):mat[i][n - offset] countcount 1# 填充下行从右到左横坐标不变是上列最后一个元素的横坐标加一(i n - offset)纵坐标从上一次的j n - offset 一直减到start_y 1for j in range(n - offset, start_y, -1):mat[n - offset][j] countcount 1# 填充左列从下到上横坐标从上一次的i n - offset一只减到start_x 1纵坐标不变就是上一行最后一个元素的纵坐标减一start_yfor i in range(n - offset, start_x, -1):mat[i][start_y] countcount 1# 更新起始点坐标start_x 1start_y 1offset 1mid n // 2if n%2 ! 0:mat[mid][mid] count return mat 4、复杂度分析
1️⃣ 时间复杂度 n / 2 ∗ 4 ∗ ( n − k ) n 2 n/2 * 4 *(n-k) n^2 n/2∗4∗(n−k)n2 2️⃣ 空间复杂度1
