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