Polaris-hzn8

二维子矩阵的和 原题链接：https://leetcode.cn/problems/O4NDxx/ 给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。 1.二维前缀和1234567891011121314151617181920class NumMatrix {public: vector<vector<int>> prefix; NumMatrix(vector<vector<int>>& matrix) { /* 初始化前缀和数组 */ if (matrix.size() == 0) return; int m = matrix.size(); int n = matrix[0].size(); prefix.assign(m + 1, vector<int>(n + 1, 0)); //prefix.resize(m + 1, vector<int>(n + 1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j]; } int sumRegion(int x1, int y1, int x2, int y2) { /* 利用前缀和数组进行面积和su ...

左右两边子数组和相等 原题链接：https://leetcode.cn/problems/tvdfij/solutions/ 给你一个整数数组 nums ，请计算数组的中心下标。 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于最左端，那么左侧数之和视为0，因为在下标左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标返回-1 1.前缀和12345678910111213141516171819202122class Solution {public: int pivotIndex(vector<int>& nums) { int ans = INT32_MAX; int len = nums.size(); //1.初始化前缀和数组 int *prefix = new int[len + 10](); for (int i = 1; i <= len; ++i) prefix[i] = prefix[i - 1] + nums[i - 1]; //2.开始计算首先处理首位两种特殊情况 if (prefix[len] - prefix[1] == 0) return 0; if (prefix[len - 1] == 0) ans = min(ans , len - 1); //3.处理一般情况 for (int i = 1; i < len - 1; ++i) { if (prefix[i] == prefix[len] - prefix[i + 1]) ans = min(ans, i); } return ans == INT32_MAX ? -1 : ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 2.前缀和优化利用一些简单的数学知识知识，可以对前缀和的思路进行进一步的优 ...

0和1个数相同的子数组 原题链接：https://leetcode.cn/problems/A1NYOS/ 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 1.暴力枚举123456789101112131415class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; for (int j = 0; j < nums.size(); ++j) { int sum = 0; for (int i = j; i >= 0; --i) { if (nums[i] == 1) sum++; else sum--; if (sum == 0) ans = max(ans, j - i + 1); } } return ans; }}; 程序超时，看来这题对时间复杂度的要求很高，需要牺牲空间复杂度换时间复杂度降低。 2.前缀和+哈希 在预处理前缀和时，将 nums[i] 为 0 的值当做 −1 处理 从而将问题转化为：如何求得最长一段区间和为 0 的子数组，使用哈希表来记录某个前缀和出现的最小下标是多少。 12345678910111213141516171819202122class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; int len = nums.size(); //1.前缀和数组初始化 int *prefix = new int[len + 10](); for (int i = 1; i <= nums.size(); ++i) prefix[i] = pref ...

和为k的子数组 原题链接：https://leetcode.cn/problems/QTMn0o/ 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数， 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len < nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int n = i; n < j; ++n) sum += nums[n]; if (sum == k) ans++; } } return ans; }}; 所有用例成功输出结果，但由于时间复杂度太高，导致程序超时， 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出边界值，尝试更新答案： 1234567891011121314151617class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len <= nums.size(); ++len) { int sum = 0; for (int i = 0; i < len; ++i) sum += n ...

搜索综合问题（上） 1. 2.OJ81：小明回家（广搜） 3.OJ538：图的遍历 4.OJ402：奇怪的电梯（广搜） 5.OJ530：警察找车（广搜）* 6.OJ531：奇怪的电视

搜索走地图问题 1.OJ535： 2.OJ397： 3.OJ536： 4.OJ396： 5.OJ398: OJ400：奇怪的象棋游戏OJ401：奇怪的象棋游戏升级版OJ303：矩阵距离（一）

搜索综合问题（下） 1.OJ541：相遇问题*（深搜） 2.OJ542：奶酪 3.LeetCode417：太平洋大西洋水流问题 4.LeetCode529：扫雷游戏 5.LeetCode934：最短的桥 6.LeetCode967：连续差相同的数字 7.LeetCode752：打开转盘锁 8.LeetCode127：单词接龙 9.层板等分衣柜==题目描述==：给定一个高度为2000mm的柜子空间，以及n个层板距离柜子底部的高度，满足移动层板位置使得层板等分衣柜空间，求所有移动层板的顺序。（层板号自下而上一次排列1、2、3、….n层板需要考虑空间位置，不能跨层板移动） 要求：1 ≤ n ≤ 10、输出结果需要按照从小到大的顺序输出。 1234567891011input:n = 3, zs = 50, 60, 1000output:3 2 1input:n = 4, zs = 50, 600, 700, 1000output:1, 4, 3, 24, 1, 3, 24, 3, 1, 24, 3, 2, 1 ==思路分析==： 看起来就是每个层板都可以移到到任意位置，但只移动一次，同时不能跨越另一个板移动。 有多种移动方案，题目要求你输出所有方案，并且按从小到大输出。 就是一般你优先尝试移动序号低的版，看看能不能让它移到均分高度的地方。 比如n=3，zs=50,60,1000。 柜子被分割成4部分，位置应该是500、1000、1500， 由于c3板子在1000这个位置，c2、c1是移动不到500这个位置的， 所以先移动c3到1500，再移动c2到1000，最后移动c1到500。 这样就等分了柜子高度了。 这题其实就是先根据板子数量，找出等分位置。 然后依次从序号小的那个板子开始判断能否移到到某个等分位置。 不行的话，就判断下一个。 复杂度不超过n^2，n小于10，可以直接遍历求解。 但是也要考虑一种情况，就是例1里面，如果c2先移动到500，那么c1移动不到1000的， 导致问题解不了了，这种情况也要考虑。 像这个C1开始在50，要移动到500但是50-500之间有C2，不能动，1开头的都不行， 然后再试C2,C2也不行，1000被C3占据， ...

递归与排列组合问题 1.OnlineJ240：图形打印Tags：递归 当 n 为 1 时，图形如下图： 1X 当 n 为 2 时，图形如下图： 123X X X X X 当 n ≥ 2 时，图形规律如下： 123图形n-1 图形n-1 图形n-1图形n-1 图形n-1 给定 n 组数据，输出每组数据对应的图形。 输入： 输入共 n+1 行，前 n 行每行一个数，表示要输出的图形的大小，最后一行输入 −1 代表程序结束。（1 ≤ n ≤ 7） 输出： 每输入一个数输出一组图形，并在图形后的下一行输出一个 −。 注意，图形后应补齐空格。 123451234-1 1234567891011121314151617181920212223242526272829303132333435363738394041424344X-X X X X X-X X X X X X X X X X X X X X X X X X X X X X X X X-X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X ...

和大于等于target的最短子数组 原题链接：https://leetcode.cn/problems/2VG8Kg/ 给定一个含有 n 个正整数的数组和一个正整数 target ， 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。 如果不存在符合条件的子数组，返回 0 。 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314151617181920class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int flag = 0; int ans = nums.size(); //遍历滑动窗口的大小 for (int len = 1; len <= nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int k = i; k < j; ++k) sum += nums[k]; if (sum >= target && len <= ans) { ans = len; flag = 1; } } } if (!flag) return 0; return ans; }}; 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出 ...

乘积小于K的子数组 原题链接：https://leetcode.cn/problems/ZVAVXX/ 1.静态滑动窗口 维护一个mul乘积 对乘积进行 * / 操作 当是当滑动窗口的长度len 非常大时， 乘积mul可能会超出数据范围 如果多个 0 ~ 1000 范围的num[i]相乘 可能超出 int 数据范围 这种方法非常容易超出int的数据范围 认定为失败的方法 123456789101112131415161718class Solution {public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { if (k == 0) return 0; int ans = 0; //遍历滑动窗口的长度 for (int len = 1; len <= nums.size(); ++len) { int mul = 1; int flag = 1; for (int i = 0; i < len; ++i) mul *= nums[i]; if (mul < k) ans++; for (int i = 1; i + len <= nums.size(); ++i) { mul /= nums[i - 1]; mul *= nums[i + len - 1]; if (mul < k) ans++; } } return ans; }}; 2.动态滑动窗口 从前往后处理所有的nums[i]，使用变量i、j代表窗口的左右端点（静态窗口弊端完美解决），使用变量mul记录当前窗口的乘积， 当 mul>=k 时，我们考虑将左端点i右移，同时消除左端点元素 nums[i] 对 mul 的贡献，直到mul>=k不再满足 这样就可以得到每个右端点 nums[i] 的最远左端 ...