Day2 第一章 数组part02

滑动窗口定义所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们想要的结果。在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。那么滑动窗口如何用一个for循环来完成这个操作呢。首先要思考 如果用一个for循环那么应该表示 滑动窗口的起始位置还是终止位置。如果只用一个for循环来表示 滑动窗口的起始位置那么如何遍历剩下的终止位置此时难免再次陷入 暴力解法的怪圈。所以 只用一个for循环那么这个循环的索引一定是表示 滑动窗口的终止位置。与双指针的区别双指针是关心两个点首位的数滑动窗口关心的是区间内的停止条件及左右指针外层循环的停止条件永远是「右指针走到头」而不是左右指针都走到头。右指针负责遍历完所有可能性所以它走到头才停左指针只负责优化当前窗口所以它跟着条件走条件没了它就停。左指针永远是被右指针拖着走的绝不会自己跑到终点。长度最小的子数组题目给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。 示例 输入s 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。思路left right都在最左边然后右指针往右搜索直到窗口内的数满足条件然后记录长度则左窗口-1并且记录下长度直到不满足条件然后右指针再往右搜索往复直到右指针到达最优侧结束。代码#版本一滑动窗口法 class Solution: def minSubArrayLen(self, s: int, nums: List[int]) - int: l len(nums) left 0 right 0 min_len float(inf) cur_sum 0 #当前的累加值 while right l: cur_sum nums[right] while cur_sum s: # 当前累加值大于目标值 min_len min(min_len, right - left 1) cur_sum - nums[left] left 1 right 1 return min_len if min_len ! float(inf) else 0注意点1. 他的赋值学习一下float(inf)2. 最后一句是条件表达式return min_len if min_len ! float(inf) else 0A if 条件 else B 条件成立就取 A不成立就取 B题目链接209. 长度最小的子数组 - 力扣LeetCode螺旋矩阵II题目给定一个正整数 n生成一个包含 1 到 n^2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]思路本题并不涉及到什么算法就是模拟过程但却十分考察对代码的掌控能力。代码class Solution: def generateMatrix(self, n: int) - list[list[int]]: # 1. 初始化 n*n 矩阵和四个边界 matrix [[0] * n for _ in range(n)] top, bottom, left, right 0, n - 1, 0, n - 1 num 1 # 当前要填入的数字 target n * n # 总共需要填的数字个数 # 2. 只要还有数字没填完就继续转圈 while num target: # ① 上边从左到右 → for col in range(left, right 1): matrix[top][col] num num 1 top 1 # 上边界下移 # ② 右边从上到下 ↓ for row in range(top, bottom 1): matrix[row][right] num num 1 right - 1 # 右边界左移 # ③ 下边从右到左 ← for col in range(right, left - 1, -1): matrix[bottom][col] num num 1 bottom - 1 # 下边界上移 # ④ 左边从下到上 ↑ for row in range(bottom, top - 1, -1): matrix[row][left] num num 1 left 1 # 左边界右移 return matrix题目链接59. 螺旋矩阵 II - 力扣LeetCode区间和题目58. 区间和第九期模拟笔试 题目描述 给定一个整数数组 Array请计算该数组在每个指定区间内元素的总和。 输入描述 第一行输入为整数数组 Array 的长度 n接下来 n 行每行一个整数表示数组的元素。随后的输入为需要计算总和的区间下标ab b a直至文件结束。 输出描述 输出每个指定区间内元素的总和。 输入示例 5 1 2 3 4 5 0 1 1 3 输出示例 3 9 提示信息 数据范围 0 n 100000就是先给一个数字比如说5那么数组就是[1, 2, 3, 4, 5]然后再给一个区间比如说0 1那么就是从0到1在比如说4 9那么就是从4到9思路前缀和用空间换时间记录下每一次sum到值比如说sum3就是前三个数和sum10就是前10个数的和那么我们求区间4 9那就是sum10-sum4代码import sys input sys.stdin.read def main(): data input().split() index 0 n int(data[index]) index 1 vec [] for i in range(n): vec.append(int(data[index i])) index n p [0] * n presum 0 for i in range(n): presum vec[i] p[i] presum results [] while index len(data): a int(data[index]) b int(data[index 1]) index 2 if a 0: sum_value p[b] else: sum_value p[b] - p[a - 1] results.append(sum_value) for result in results: print(result) if __name__ __main__: main()两个学习的点1. input函数改成input sys.stdin.read然后注意 data input().split()有个括号2. print函数print(\n.join(map(str, result)))就是先map(str, result))把int改成str然后\n.join(map(str, result))[3, 9]→3\n9题目链接58. 区间和第九期模拟笔试开发商购买土地题目题目描述 在一个城市区域内被划分成了n * m个连续的区块每个区块都拥有不同的权值代表着其土地价值。目前有两家开发公司A 公司和 B 公司希望购买这个城市区域的土地。 现在需要将这个城市区域的所有区块分配给 A 公司和 B 公司。 然而由于城市规划的限制只允许将区域按横向或纵向划分成两个子区域而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争你需要找到一种分配方式使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。 注意区块不可再分。 输入描述 第一行输入两个正整数代表 n 和 m。 接下来的 n 行每行输出 m 个正整数。 输出描述 请输出一个整数代表两个子区域内土地总价值之间的最小差距。 输入示例 3 3 1 2 3 2 1 3 1 2 3 输出示例 0 提示信息 如果将区域按照如下方式划分 1 2 | 3 2 1 | 3 1 2 | 3 两个子区域内土地总价值之间的最小差距可以达到 0。 数据范围 1 n, m 100 n 和 m 不同时为 1。思路还是利用区间和的思路这里成为前缀和将每一行直接累加然后比较差值先横着切然后竖着切最后得出差值最小的代码def main(): import sys input sys.stdin.read data input().split() idx 0 n int(data[idx]) idx 1 m int(data[idx]) idx 1 sum 0 vec [] for i in range(n): row [] for j in range(m): num int(data[idx]) idx 1 row.append(num) sum num vec.append(row) # 统计横向 horizontal [0] * n for i in range(n): for j in range(m): horizontal[i] vec[i][j] # 统计纵向 vertical [0] * m for j in range(m): for i in range(n): vertical[j] vec[i][j] result float(inf) horizontalCut 0 for i in range(n): horizontalCut horizontal[i] result min(result, abs(sum - 2 * horizontalCut)) verticalCut 0 for j in range(m): verticalCut vertical[j] result min(result, abs(sum - 2 * verticalCut)) print(result) if __name__ __main__: main()题目链接44. 开发商购买土地第五期模拟笔试最后两道题前缀和和区间和核心本质只要题目涉及“连续子数组/子矩阵的元素之和”无论它是让你“查询”还是让你“枚举分割点”底层数学原理都是前缀和。什么时候使用出现“和”连续一段子区间连续重复查询就可以想到前缀和总结数组部分数组经典题目二分法这道题目呢考察数组的基本操作思路很简单但是通过率在简单题里并不高不要轻敌。可以使用暴力解法通过这道题目如果追求更优的算法建议试一试用二分法来解决这道题目暴力解法时间复杂度O(n)二分法时间复杂度O(logn)在这道题目中我们讲到了循环不变量原则只有在循环中坚持对区间的定义才能清楚的把握循环中的各种细节。二分法是算法面试中的常考题建议通过这道题目锻炼自己手撕二分的能力。双指针法双指针法快慢指针法通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。暴力解法时间复杂度O(n^2)双指针时间复杂度O(n)这道题目迷惑了不少同学纠结于数组中的元素为什么不能删除主要是因为以下两点数组在内存中是连续的地址空间不能释放单一元素如果要释放就是全释放程序运行结束回收内存栈空间。C中vector和array的区别一定要弄清楚vector的底层实现是array封装后使用更友好。双指针法快慢指针法在数组和链表的操作中是非常常见的很多考察数组和链表操作的面试题都使用双指针法。滑动窗口本题介绍了数组操作中的另一个重要思想滑动窗口。暴力解法时间复杂度O(n^2)滑动窗口时间复杂度O(n)本题中主要要理解滑动窗口如何移动 窗口起始位置达到动态更新窗口大小的从而得出长度最小的符合条件的长度。滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。如果没有接触过这一类的方法很难想到类似的解题思路滑动窗口方法还是很巧妙的。模拟行为​​​​​​​模拟类的题目在数组中很常见不涉及到什么算法就是单纯的模拟十分考察大家对代码的掌控能力。在这道题目中我们再一次介绍到了循环不变量原则其实这也是写程序中的重要原则。相信大家有遇到过这种情况 感觉题目的边界调节超多一波接着一波的判断找边界拆了东墙补西墙好不容易运行通过了代码写的十分冗余毫无章法其实真正解决题目的代码都是简洁的或者有原则性的大家可以在这道题目中体会到这一点。前缀和​​​​​​​前缀和的思路其实很简单但非常实用如果没接触过的录友也很难想到这个解法维度所以 这是开阔思路 而难度又不高的好题。​​​​​​​总结图片