Leetcode977.有序数组的平方
题目链接
关键词:双指针
问题思路:给一个非递减数组,返回平方后的非递减数组,忽略非递减的条件我们可以直接对原数组进行平方然后排序,显然这样对原数组的性质运用不完全,如何体现非递减的性质?发现新数组的最大值一定是原数组的首尾项中较大的一项,故而想到采用双指针指向首尾
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int numsLength = nums.size();
vector<int> result(numsLength, 0);
int left = 0, right = numsLength - 1;
for (int i = numsLength - 1; i >= 0; --i) {
if (nums[left] * nums[left] >= nums[right] * nums[right]) {
result[i] = nums[left] * nums[left];
++left;
}
else{
result[i] = nums[right] * nums[right];
--right;
}
}
return result;
}
};
反思:将双指针的思路融入思考而不是机械化的套
Leetcode209.长度最小的子数组
题目链接
关键词:滑动窗口
问题思路:滑动窗口本质也是双指针,在使用滑动窗口时想清楚几个问题,1.左边界与右边界谁是主要边界,谁是因变量?2.次要边界维护的原则是什么?
借此再次强调双指针的关键在于无回溯,两个指针都朝着某个方向单调移动,因此时间复杂度大大降低
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0;
int result = INT32_MAX;
int i = 0;
for (int j = 0; j < nums.size(); ++j) {
sum += nums[j];
while (sum >= target) {
int length = j - i + 1;
if (result > length) result = length;
sum -= nums[i];
++i;
}
}
if (result == INT32_MAX) return 0;
return result;
}
}
反思:双指针多用于数组,链表,其作用在于利用线性表自身的性质减小时间复杂度
Leetcode59.螺旋矩阵II
关键词:拆解问题
问题思路:乍一看是很简单的问题,实际操作时会发现无从下手,在遇到这种问题时我们考虑两个问题,1.能否通过减小问题规模突出问题的关键?2.能否把该问题转化为其他几个同类的子问题?
而后发现我们把构造螺旋矩阵转化为构造单层螺线圈,把构造单层螺线圈转化为构造构造四个等长度小长方形,故而两层for循环解决问题
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> generateMatrixNew(n, vector<int>(n, 0));
int num = 1;
int loop = n / 2;
for (int i = 0; i < loop; ++i) {
for (int j = i; j < n - i - 1; ++j) {
generateMatrixNew[i][j] = num;
num++;
}
for (int j = i; j < n - i - 1; ++j) {
generateMatrixNew[j][n - i - 1] = num;
num++;
}
for (int j = n - i - 1; j > i; --j) {
generateMatrixNew[n - i - 1][j] = num;
num++;
}
for (int j = n - i - 1; j > i; --j) {
generateMatrixNew[j][i] = num;
num++;
}
}
if (n % 2 == 1) generateMatrixNew[n / 2][n / 2] = num;
return generateMatrixNew;
}
};
反思:考察一种泛化的问题建模思维
今日学习:2.5h