977.有序数组的平方
- 题目链接：[https://leetcode.cn/problems/squares-of-a-sorted-array/submissions/]
文章链接：[https://programmercarl.com/0977.有序数组的平方.html#双指针法]
第一遍思路
在看到要求时间复杂度为o（n）时，想到只能对整个数组进行一次遍历，不能直接使用排序算法，因此不能先排序再平方。从双指针法的角度进行考虑，这道题也就迎刃而解了。
点击查看代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
vector<int> result;
while(left<=right){
if(abs(nums[left])<=abs(nums[right])){
result.push_back(nums[right]*nums[right]);
right--;
}
else{
result.push_back(nums[left]*nums[left]);
left++;
}
}
reverse(result.begin(),result.end());
return result;
}
};
思路总结
这道题还是比较简单的。面对数组问题时，在没有思路时，我们可以试着从方法的角度来进行考虑，一看到数组题就要想到数组常用的方法，在从中选要用的方法。总之，多练习多思考才能熟练。
209.长度最小的子数组
- 题目链接:[https://leetcode.cn/problems/minimum-size-subarray-sum/]
文章链接：[https://programmercarl.com/0209.长度最小的子数组.html#暴力解法]
第一遍思路
对于数组我想到用两个指针去控制，当总和大于等于target时，左指针前移，否则，右指针前移。我的想法是终结条件为左指针小于数组长度，用while循环控制两个指针来循环。
实现问题
实现过程中发现右指针小于最大值和等于最大值时是两种情况，因此多加了一个判断。
点击查看代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result=0;//结果
int left=0;//左边界
int right=0;//右边界
int sum=nums[0];//窗口内的总和
while(left<=nums.size()-1){
if(right<nums.size()-1){//当右边界没有到达最大值时
if(sum<target){
sum=sum+nums[right+1];
right++;
}
else if(sum>=target){
if(result==0){
result=right-left+1;
}
else{
result=result<(right-left+1)?result:(right-left+1);
}
sum=sum-nums[left];
left++;
}
}
else{//当右边界到达最大值时
if(sum>=target){
if(result==0){
result=right-left+1;
}
else{
result=result<(right-left+1)?result:(right-left+1);
}
sum=sum-nums[left];
}
left++;
}
}
return result;
}
};
题后总结
- 在滑动窗口中，用for循环来控制右指针可以比while循环更加简化。
- 可以将result设置为length+1或者设为INT32_MAX比将result设为0更加简化。
59.螺旋矩阵
- 题目链接:[https://leetcode.cn/problems/spiral-matrix-ii/]
文章链接:[https://programmercarl.com/0059.螺旋矩阵II.html#思路]
第一思路
想了半小时什么也想不出来，不知道怎么下手。。。
实现问题
。。。附上看完思路后的代码
点击查看代码
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n,vector<int>(n,0));
int startx=0,starty=0;
int loop=1;
int mid=n/2;
int i,j;
int count=1;
while(loop<=n/2){
i=startx;
j=starty;
for(;j<n-loop;j++){
result[i][j]=count++;
}
for(;i<n-loop;i++){
result[i][j]=count++;
}
for(;j>starty;j--){
result[i][j]=count++;
}
for(;i>startx;i--){
result[i][j]=count++;
}
loop++;
startx++;
starty++;
}
if(n%2){
result[mid][mid]=count;
}
return result;
}
};
题后总结
这个题最大的难度在于不知道如何把问题分成步骤进行循环。对于计算机来说，最擅长的事情就是遍历，要在此基础上进行思考。
标签：977,https,int,随想录,vector,result,数组,指针 From： https://www.cnblogs.com/suodi/p/16717784.html