数组02
LeetCode 997-有序数组的平方
思考
第一眼的思路：先平方后排序，时间复杂度根据排序算法的选择决定，最快为O(nlgn)，或者现根据绝对值排序后平方，本质上是一个思路。
考虑双指针后的思路：存在负数的有序数组，平方后的最大值一定在两端，不考虑空间的消耗，从两端往中间遍历，比较两端点，大者存入新的数组，即可实现一轮循环完成排序，时间复杂度O(n)，空间复杂度O(n)。
算法实现
第一眼思路算法实现：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++){
nums[i] *= nums[i];
}
sort(nums.begin(), nums.end());
return nums;
}
};
使用双指针之后的算法实现：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result(nums.size(), 0);//存放结果的数组
int i = nums.size() - 1;
int j = 0;
int k = i;
while(j <= i){
int a = nums[i] * nums[i];
int b = nums[j] * nums[j];
if(a >= b){
result[k--] = a;
i--;
}
else{
result[k--] = b;
j++;
}
}
return result;
}
};
总结
-
新的双指针使用方式，首尾指针法，用于需要对数组进行收尾同时操作的过程中
-
顺序数组的良好性质，可方便的随机读取，实现头尾同时向中间遍历
LeetCode 209-长度最小的子数组
长度最小的子数组
思考
暴力解，使用两个for循环，依次寻找满足大于等于target的子串，并保留最小值，然后很自然的超时了
滑动窗口方法：
- 设立两个指针，i、j
- 当窗口内部元素，不满足条件时，i++，j不变
- 当窗口内元素满足条件时，更新最短子串长度，并且j++，i不变
- 重复上两过程
这样，时间复杂度就降低到O(n)啦
暴力解代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//双循环
int minSub = INT32_MAX;
int i, j;
int sum = 0;
int sumLen = 0;
for ( i = 0; i < nums.size(); i ++ ) {
sum = 0;
for ( j = i; j < nums.size(); j++ ) {
sum += nums[j];
if ( sum >= target ) {
sumLen = j - i + 1;
minSub = sumLen < minSub ? sumLen : minSub;
break;
}
}
}
return minSub == INT32_MAX ? 0 : minSub;
}
};
滑动窗口代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int minSub = INT32_MAX;//最短子串长度
int i, j;//双指针
int sum = 0;//求和
int sumLen = 0;//窗口长度
for (i = 0, j = 0; j < nums.size(); j ++) {
sum += nums[ j ];
while ( sum >= target ) {
sumLen = j - i + 1;
minSub = minSub <= sumLen ? minSub : sumLen;
sum -= nums[ i++ ];
}
}
return minSub == INT32_MAX ? 0 : minSub;
}
};
总结
- 双指针方法的另一应用，前后指针都可移动，实现窗口的向后滑动
- 这里使用wihle更好一些，需要循环加判断，或者使用if+for代替
- 虽然有两层循环，但是我们对于整个数组的遍历只进行了i，j两遍，也就是O(2n)
LeetCode 59-螺旋矩阵II
思考
第一眼：没有思路。
看题解后：这是一道模拟过程的题目，那么最重要的就是分析好这个矩阵的填写过程，填写过程如下：
- 从左往右
- 从上到下
- 从右往左
- 从下到上
上述过程就是填写一圈的流程，为了让这个流程可控，最好的方式是每条边填写的数字个数相同，考虑到循环不变量的原则，以左闭右开为区间定义，完成对四条边填写的控制；
那么填写一圈的逻辑确定后，还需确定的是一共需要填写多少圈，每圈的起始位置在哪，每圈的边长为多少，对此我们需要初始化如下信息：
- 每一圈的起始位置（0，0），（1，1）。。。
- 需要循环的圈数，n/2，需要注意的是，n为奇数需要特殊处理最中间的数字，也就是最后一位数字的填写
- 记录需要填写的数字count
- 记录每圈的边长
那么实现代码如下：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> matrix(n, vector<int>(n, 0));//初始化内容全部为0的二维数组
int startx = 0, starty = 0;//每一圈的起点
int loop = n / 2;//循环的圈数
int length = n - 1;//定义每一圈的变边长，根据左闭右开，初始长度为n-1
int count = 1;//每个位置应填的数值
int i,j;//循环变量
while ( loop-- ) {
i = startx;
j = starty;
//开始模拟四个边的填写过程
//写上边
for ( ; j < length; j ++ ) {
matrix[i][j] = count ++;
}
//写右边
for ( ; i < length; i ++ ) {
matrix[i][j] = count ++;
}
//写下边
for ( ; j > starty; j -- ) {
matrix[i][j] = count ++;
}
//写左边
for ( ; i > startx; i --) {
matrix[i][j] = count ++;
}
//下一圈，起点x++，y++，边长--
startx ++;
starty ++;
length --;
}
//处理一下，n为奇数的情况
if ( n % 2 ) {
matrix[ n / 2 ][ n / 2 ] = count ++;
}
return matrix;
}
};
总结
- 过程模拟，重在考虑好各种情况，一个是分析四条边，一个是分析n的奇偶情况
- 循环过程中，保持循环不变量原则，就不会出错