有序数组的平方
题目
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
提示
- 题目建议： 本题关键在于理解双指针思想
- 题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
- 文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
- 视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep
思路
这种类型题目的数组应该是包含复数的，平方之后会改变排序的趋势。含有负数，那么平方之后的大小趋势就是两边大，中间小，最大元素一定是在两边。这里需要创建一个新的数组存储元素。比较两端的值的大小，放入新数组的那一端的指针做++或–的操作，可以用双指针去解决
代码
python双指针解法：
（直接用sorted方法可以直接做）
class Solution(object):
def sortedSquares(self, nums):
result_list = [] # 定义一个存储最终元素的新列表
i = 0
j = len(nums) - 1
while(i <= j):
# 先把两种平方命名为其他变量，更简洁
i2 = nums[i]**2
j2 = nums[j]**2
if i2 > j2:
# 符合条件直接用inster插到最前面
result_list.insert(0, i2)
i += 1
else:
result_list.insert(0, j2)
j -= 1
return result_list
java。
class Solution {
public int[] sortedSquares(int[] nums) {
int l = 0; //定义左指针
int r = nums.length - 1; //定义右指针
int [] res = new int[nums.length]; // 定义新列表
int j = nums.length - 1; //定义新列表的下标
while(l <= r){
if(nums[l]*nums[l] > nums[r]*nums[r]){
res[j--] = nums[l] * nums[l++];
}
else{
res[j--] = nums[r]*nums[r--];
}
}
return res;
}
}
C++。
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1; //新数组的长度
vector<int> result(A.size(), 0) ;//定义新数组
for(int i = 0, j = A.size() - 1; i <= j;){
if(A[i]*A[i] < A[j]*A[j]){
result[k--] = A[j] * A[j--];
}
else{
result[k--] = A[i] * A[i++];
}
}
return result;
}
};
长度最小的子数组
题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路
本题关键在于理解滑动窗口。暴力解法为两个for循环遍历，时间复杂度高。滑动窗口将两个for循环做的事情放到一个for循环中。这一个for循环中的参数代表的是终止位置，刚开始起始位置不动，终止位置的指针移动，当所形成的区间的和大于等于sum时，起始指针开始移动，寻找长度最小的连续子数组。
如何移动起始位置呢？利用sum的值的变化去代表移动起始位置。其实移动终止位置也可以理解为利用sum的值的变化去代表。移动终止位置是sum加上下一个元素，那么移动起始位置就是sum减去最前面的元素。
提示
- 题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
- 文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
- 视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
代码
C++
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX; // 将result的初始值设定的很大，用来比较存储最短子数组
int sum = 0; //滑动窗口的数值之和
int i = 0; //滑动窗口的起始位置
int subLength = 0; //滑动窗口的长度
for (int j=0;j<nums.size();j++){ //j是滑动窗口的终止位置
sum += nums[j];
//这里要使用while，要连续多次判断是否为最短子数组
while(sum >= s){
//取出当前自学列的长度
subLength = (j - i + 1);
//三目运算符，如果resul小于subLength，那么返回result，否则返回subLength
result = result < subLength ? result : subLength;
sum -= nums[i++]; //滑动窗口的精髓之处
}
}
return result == INT32_MAX ? 0 : result;
}
};
`java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 滑动窗口的起始位置
int start = 0;
// 存储最小子数组的长度
int result = Integer.MAX_VALUE;
// 存储当前子数组的长度
int subLength = 0;
// 存储子数组的和
int sum_list = 0;
for(int end=0;end < nums.length;end++){
sum_list += nums[end];
while(sum_list >= target){
result = Math.min(result, end-start+1);
sum_list -= nums[start++];
}
}
return result == Integer.MAX_VALUE ? 0:result;
}
}
螺旋矩阵
题目
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
螺旋矩阵
思路
- 涉及到很多的边界问题，这样的问题一定要设定循环不变量，而这里的循环不变量是处理每条边的区间，都应该是左闭右开[x,y)。
- 为偶数转圈的次数为n/2(举例画图)，若为奇数转圈的次数也为n/2，但最后中间的值要单独填上
提示
- 题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
- 文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
- 视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
代码
C++
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
int startx = 0, starty = 0; //定义每个循环一个圈的起始位置
int loop = n/2; //转圈循环的次数
int mid = n / 2;//矩阵最中间的位置。例如：n为3， 中间的位置就是(1，1)
int count = 1; //用来给矩阵空格赋值
int offset = 1; //需要控制每一条边遍历的长度，每次循环右边界收缩一位
int i,j;
while(loop --){
i = startx;
j = starty;
// 上：从左到右
for(j = starty; j<n-offset;j++){
res[startx][j] = count++;
}
// 右：从上往下
for(i = startx;i<n-offset;i++){
res[i][j] = count++;
}
//下：从右玩过
for (;j>starty;j--){
res[i][j] = count++;
}
//左：从下往上
for(;i>startx;i--){
res[i][j] = count++;
}
//第二圈时，各自的起始位置都要加1
startx++;
starty++;
offset += 1;
}
if(n%2){
res[mid][mid] = count;
}
return res;
}
};