共计 1612 个字符,预计需要花费 5 分钟才能阅读完成。
leetcode 977 题目链接:
https://leetcode.com/problems/squares-of-a-sorted-array/
最终 ac 代码:(双指针法)
class Solution
{
public:
vector<int> sortedSquares(vector<int> &nums)
{
vector<int> v;
int left = 0;
int right = nums.size() - 1;
while (left <= right)
{if (nums[left] * nums[left] < nums[right] * nums[right])
{v.push_back(nums[right] * nums[right]);
--right;
}
else
{v.push_back(nums[left] * nums[left]);
++left;
}
}
reverse(v.begin(), v.end());
return v;
}
};
std::vector operator[] 不做越界查看,vector::at 才查看
leetcode 209 题目链接:
https://leetcode.com/problems/minimum-size-subarray-sum/
ac 代码:(滑动窗口) 毛病:圈复杂度比拟大
class Solution
{
public:
int minSubArrayLen(int target, vector<int> &nums)
{
int wl = 0;
int wr = 0;
int wsum = 0;
int minWlen = INT_MAX;
while (true)
{if (wsum < target)
{if (wr == nums.size())
break;
wsum += nums[wr];
++wr;
}
else
{
int wlen = wr - wl;
if (wlen < minWlen)
minWlen = wlen;
wsum -= nums[wl];
++wl;
}
}
if (minWlen == INT_MAX)
return 0;
return minWlen;
}
};
双循环版本 (复杂度依然是 O(n),圈复杂度升高 ):
class Solution
{
public:
int minSubArrayLen(int target, vector<int> &nums)
{
int wl = 0;
int wsum = 0;
int minWlen = INT_MAX;
for (int wr = 0; wr < nums.size(); ++wr)
{wsum += nums[wr];
while (wsum >= target)
{
int wlen = wr - wl + 1;
if (wlen < minWlen)
minWlen = wlen;
wsum -= nums[wl++];
}
}
if (minWlen == INT_MAX)
return 0;
return minWlen;
}
};
leetcode 59
https://leetcode.com/problems/spiral-matrix-ii/
ac 代码:
class Solution
{
public:
vector<vector<int>> generateMatrix(int n)
{vector<vector<int>> v(n);
for (int i = 0; i < v.size(); i++)
{v[i] = vector<int>(n);
}
int square = n * n;
int loopnum = n / 2;
if (n % 2 == 1)
{v[loopnum][loopnum] = square;
}
int num = 1;
for (int i = 0; i < loopnum; i++)
{for (int j = i; j < n - 1 - i; ++j)
{v[i][j] = num++;
}
for (int j = i; j < n - 1 - i; ++j)
{v[j][n - i - 1] = num++;
}
for (int j = n - i - 1; j > i; --j)
{v[n - i - 1][j] = num++;
}
for (int j = n - i - 1; j > i; --j)
{v[j][i] = num++;
}
}
return v;
}
};
正文完