有序数组的平方
leetcode：977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
暴力法
思路
- 遍历数组，元素原地替换为自身平方值。
- 将数组进行排序。
复杂度分析
时间复杂度：O(N+logN)
空间复杂度：O(1)
注意点
- sort(parm1,parm2,options)，接收首地址/迭代器、末地址/迭代器、比较函数。
- begin()、end()方法返回首、末迭代器。c++里很多容器都有这两个方法。
代码实现
class Solution {
public:
// 暴力法，先平方再排序
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0;i < nums.size();i++){
nums[i] = nums[i] * nums[i];
}
sort(nums.begin(),nums.end());
return nums;
}
};
相向双指针法
思路
基于1. 原数组有序；2. 元素有正有负两条特性，元素平方后的值，最大值一定出现在两端，利用相向双指针从两端向中间靠拢，寻找每一轮的最大值，倒序赋值给新数组，从而达到排序效果。
-
初始化左、右指针、新数组、新数组指针（末位） .
-
左右指针对比，找到本轮自身平方最大的元素，填入新数组中。
若左元素大，则填入左元素，left++，cur--；
否则，填入右元素，right--，cur--；
-
重复2直至left>right，循环结束。
复杂度分析
时间复杂度：O(N)
空间复杂度：O(N)，额外开辟了一个等大数组.
注意点
- 必须在新开辟数组填入元素,否则修改原数组会污染数据.
代码实现
class Solution {
public:
// 相向双指针，利用最大值出现在数组两端的特性（有正有负）
// 两指针向中间靠拢，每次都找到剩余元素中最大的，
// 将找到的元素倒序插入新数组中，即可完成排序
vector<int> sortedSquares(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
int cur = nums.size() - 1;
vector<int> arr(nums.size());
// 右闭原则
while(left <= right){
// 每轮取最大的元素，倒序填入
if(nums[left]*nums[left] > nums[right]*nums[right]){ // left大
arr[cur--] = nums[left]*nums[left];
left++;
}else{ // right大或相等
arr[cur--] = nums[right]*nums[right];
right--;
}
}
return arr;
}
};
长度最小的子数组
leetcode：209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
暴力法
思路
外层代表终止指针，遍历数组；内层代表起始指针，从0遍历到终止指针。内层遍历过程中起始指针不断后移，同时不断检测是否还满足条件。
- 外层循环，移动终止指针i，遍历数组
- 内层循环，移动起始指针j，遍历0~i（含i），如果局部和
curSum >= target那么就尝试更新（与历史最短比较，如果更短就更新数值）最短值。 - 重复2直至遍历完成，返回时检测result是否更新过，若未更新则不存在满足条件的子序列，返回0。
复杂度分析
时间复杂度：O(N)
空间复杂度：O(1)
注意点
- 内层循环要使用局部累和
curSum，否则用原累和sum会污染数据。 - 内层j可以取到i,此时长度为1。
代码实现
class Solution {
public:
// 暴力法
// 外层终止指针遍历数组
// 内层起始指针遍历到终止指针，找到最小值
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0;
for(int i = 0;i < nums.size();i++){
sum += nums[i];
if(sum >= target){
int curSum = sum;
for(int j = 0;j <= i; ){
if(curSum >= target){
// 尝试更新
int subLength = i-j+1;
result = subLength < result ? subLength : result;
curSum -= nums[j++];
}else{
break;
}
}
}
}
return result == INT32_MAX ? 0 : result;
}
};
滑动窗口法(同向双指针)
思路
设置同向双指针，利用nums元素是正数的特点，终止指针后移一定使累和增大，起始指针后移一定使累和减小，不存在起始指针回头还是最优解的情况。
- 外层循环移动终止指针
i，遍历数组，同时计算累和sum。 - 当
sum >= target时，内层循环移动起始指针j，尝试更新最短长度。 - 重复1、2，直至循环完毕。返回时检测result是否更新过，若未更新则不存在满足条件的子序列，返回0。
复杂度分析
时间复杂度：O(N)。虽然两层循环，但i、j整体只会移动N次
空间复杂度：O(1)。无额外空间。
注意点
- 内层j可以取到i,此时长度为1。
代码实现
class Solution {
public:
// 滑动窗口（同向双指针）
// 因为nums元素都是正数，终止指针后移累和一定增大
// 起始指针后移累和一定减小，不存在起始指针回头还满足条件的情况
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0;
// 外层移动终止指针
for(int i = 0,j = 0;i < nums.size();i++){
sum += nums[i];
while(sum >= target && j <= i){
int subLength = i-j+1;
result = subLength < result ? subLength : result;
sum -= nums[j++];
}
}
return result == INT32_MAX ? 0 : result;
}
};
螺旋矩阵
思路
表现是螺旋形，但是处理时是一环一环地处理。
- 声明一个大小为n×n的二维矩阵matrix，并将每个元素初始化为n×n（避免了处理N为奇数的情况）。
- 进入循环，循环条件为需要进行的螺旋层数loop大于等于0。
- 在每一层中，按照螺旋顺序遍历矩阵的边界，将计数器count的值逐个赋给矩阵对应位置的元素，并将count加1。
- 每完成一次螺旋遍历，需要进行的螺旋层数loop减1，同时记录当前层的偏移量offset加1。
- 循环结束后，返回生成的螺旋矩阵matrix。
复杂度分析
时间复杂度：O(N^2)。
空间复杂度：O(N^2)。额外声明了二维数组。
注意点
- 左闭右开原则，每次只处理到末元素前一个。
- 元素初始化为N*N，避免了N是奇数时的处理。
代码实现
class Solution {
public:
// 左闭右开原则
vector<vector<int>> generateMatrix(int n) {
int count = 1;
int loop = n/2;
int offset = 0;
int i=0,j=0;
// 声明n*n矩阵，元素初始化为n*n
vector<vector<int>> matrix(n,vector<int>(n,n*n));
while(loop--){
for(j = offset;j < n - 1 - offset;j++){
matrix[offset][j] = count++;
}
for(i = offset;i < n - 1 - offset;i++){
matrix[i][j] = count++;
}
for(;j > offset;j--){
matrix[i][j] = count++;
}
for(;i > offset;i--){
matrix[i][j] = count++;
}
offset++;
}
return matrix;
}
};