977. 有序数组的平方 - 力扣（LeetCode）
以下思路为经典反例
思路:因为刚做过27. 移除元素 - 力扣（LeetCode），所以第一时间就想到了用快慢指针做这道题，思路很简单，同样也是两个指针，快指针负责遍历，慢指针负责收集，不过这次要求返回一个vector，所以我们要新建一个cnt大小的vector并且赋值为-1（因为前面的数据经过平方以后不可能小于0，这边为了与下面的a[slow++]配合，其实这不是不要的，只是比较简单明了），后面快指针遇到和慢指针一样的就忽略，和慢指针不一样的就让慢指针收集，这样就保证慢指针中收集到的都是不重复的数字
我的AC代码
(虽然AC了，但貌似会错意了，阴差阳错，题目不要求数字不重复)
// 时间复杂度O(n + nlog n) 空间复杂度O(n) class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int cnt = nums.size(); for(int i = 0; i < cnt; ++i) { nums[i] = nums[i] * nums[i]; } sort(nums.begin(), nums.begin() + cnt); vector<int>a(cnt,-1); int slow = 0; int fast = 0; for(fast = 0; fast < cnt; ++fast) { if(nums[fast] == a[slow]) { ++fast; } else { a[slow++]=nums[fast]; } } return a; } };
我的AC代码2
以下为正确思路，看了标准答案以后写的
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int cnt = nums.size(); for(int i = 0; i < cnt; ++i) { nums[i] = nums[i] * nums[i]; } vector<int>a(cnt,-1); int l = 0; int r = cnt-1; while(l <= r) { if(nums[l] <= nums[r]) { a[--cnt] = nums[r]; --r; } else { a[--cnt] = nums[l]; ++l; } } return a; } };
标准答案
class Solution { public: vector<int> sortedSquares(vector<int>& A) { int k = A.size() - 1; vector<int> result(A.size(), 0); for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素 if (A[i] * A[i] < A[j] * A[j]) { result[k--] = A[j] * A[j]; j--; } else { result[k--] = A[i] * A[i]; i++; } } return result; } };
209. 长度最小的子数组 - 力扣（LeetCode）
思路:因为以前做过，所以第一时间想到了滑动窗口，即一个指针负责右端，一个指针负责左端，当总和小于target的时候，右端不停向右移动，直到总和大于target，然后此时再让左端指针不停向右移动(不要忘了减数据)，力图找出最小的连续子数组长度，第一次没AC是因为忘记无解的时候返回0了，很尴尬
我的AC代码
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int sum = 0; int slow = 0; int fast = 0; int cnt = nums.size(); int ans = 1e5 + 10; for(fast = 0;fast < cnt; ++fast) { sum += nums[fast]; while(sum >= target) { ans = min(ans, fast - slow + 1); sum -= nums[slow]; slow++; } } if(ans == 1e5 + 10) { ans = 0; } return ans; } };
标准答案
// 滑动窗口法 // 时间复杂度：O(n) // 空间复杂度：O(1) class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; int sum = 0; // 滑动窗口数值之和 int i = 0; // 滑动窗口起始位置 int subLength = 0; // 滑动窗口的长度 for (int j = 0; j < nums.size(); j++) { sum += nums[j]; // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件 while (sum >= s) { subLength = (j - i + 1); // 取子序列的长度 result = result < subLength ? result : subLength; sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置） } } // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列 return result == INT32_MAX ? 0 : result; } };
59. 螺旋矩阵 II - 力扣（LeetCode）
思路:这题目第一眼很懵逼，但是思路还是简单的，只要坚持左闭右开的原则，顺时针画一遍就行了，主要是边界处比较难处理，想得挺久的
此处借用一下carl哥的图，这样更易于理解
我的AC代码
//时间复杂度O(n2),空间复杂度O(n2) 感觉也算遍历二维矩阵了吧 class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> ans(n,vector<int>(n,1)); int end = n*n; int r = 0; int c = 0; int q = 1; if(1 == n) { return ans; } for(int i = 0; i <= end; ) { while(c <= (n - q - 1)) { ++i; ans[r][c] = i; ++c; if(end == i) { return ans; } } while(r <= (n - q - 1)) { ++i; ans[r][c] = i; ++r; if(end == i) { return ans; } } while(c >= q) { ++i; ans[r][c] = i; --c; if(end == i) { return ans; } } while(r >= q) { ++i; ans[r][c] = i; --r; if(end == i) { return ans; } } ++r; ++c; ++q; if((end - 1) == i){ ans[r][c] = end; return ans; } } return ans; } };
附一个vector初始化二维数组的办法
// 初始化一个 二维的matrix, 行M,列N,且值为0 vector<vector<int>> matrix(M,vector<int>(N)); // 等价于下面的 vector<vector<int> > matrix(M); for(int i=0;i<M;i++) { matrix[i].resize(N); } // 等价于下面的 vector< vector<int> > matrix; matrix.resize(M);// M行 for(int i=0;i<matrix.size();i++){ matrix[i].resize(N);// 每一行都是N列 } // 初始化一个 二维的matrix, 行M,列N,且值自定义为data; vector<vector<int>> matrix(M,vector<int>(N,data));
我和carl哥代码的最大区别就是我的终止条件不是转几圈，而是数字全部赋完，这也导致一个问题，就是n为奇数时最后一个数字可能无法赋值，循环就永远都无法结束，得加入特判
标准答案
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组 int startx = 0, starty = 0; // 定义每循环一个圈的起始位置 int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理 int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2) int count = 1; // 用来给矩阵中每一个空格赋值 int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位 int i,j; while (loop --) { i = startx; j = starty; // 下面开始的四个for就是模拟转了一圈 // 模拟填充上行从左到右(左闭右开) for (j = starty; j < n - offset; j++) { res[startx][j] = count++; } // 模拟填充右列从上到下(左闭右开) for (i = startx; i < n - offset; i++) { res[i][j] = count++; } // 模拟填充下行从右到左(左闭右开) for (; j > starty; j--) { res[i][j] = count++; } // 模拟填充左列从下到上(左闭右开) for (; i > startx; i--) { res[i][j] = count++; } // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1) startx++; starty++; // offset 控制每一圈里每一条边遍历的长度 offset += 1; } // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值 if (n % 2) { res[mid][mid] = count; } return res; } };
Comments NOTHING