977.有序数组的平方
1. 题目
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
2. 分析
写法1：暴力排序
直接平方后排序。注意这里不可以用冒泡排序，冒泡排序双循环，复杂度n^2。这里要用qosrt
重点：调用qsort函数
调用qsort函数，要先写出cmp函数的定义。固定格式。
int cmp(const void * _a,const void *_b)
{
return (*(int*)_a - *(int*)_b);
}
int* sortedSquares(int* nums, int numsSize, int* returnSize){
int i,j;
(*returnSize)=numsSize;
int temp;
int* ans = (int*)malloc(sizeof(int) * numsSize);
for(i=0;i<numsSize;i++)
{
ans[i]=nums[i]*nums[i];
}
qsort(ans,numsSize,sizeof(int),cmp);
return ans;
}
for循环的复杂度是n,qsort的复杂度是nlogn,可以把整体的复杂度看出nlogn。
写法2：双指针法
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。
如动画所示：
int* sortedSquares(int* nums, int numsSize, int* returnSize){
(*returnSize)=numsSize;
int left,right;
left=0;right=numsSize-1;
int index;
//首先要设立三个指针：左指针，右指针，和新数组ans的指针
int *ans=(int*)malloc(sizeof(int)*numsSize);
//新建数组ans，并开辟一份空间
for(index=numsSize-1;index>=0;index--)
{
if(nums[left]*nums[left]<nums[right]*nums[right])//左指针平方比右指针的平方小
{
ans[index]=nums[right]*nums[right];//把右指针的平方赋给新数组
right--;//右指针左移
}
else//否则
{
ans[index]=nums[left]*nums[left];//把左指针的平方赋给新数组
left++;//左指针右移
}
}
return ans;//返回新的数组
}
209.长度最小的子数组
1. 题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
2. 分析
写法1：暴力排序(O(n^2),不会通过)
int minSubArrayLen(int target, int* nums, int numsSize){
int sum;
int i,j;
int len=65535;
for(i=0;i<numsSize;i++)
{
sum=0;
for(j=i;j<numsSize;j++)
{
sum=sum+nums[j];
if(sum>=target&&(j-i+1)<=len)//连续子数组的和如果大于target且长度小于上一个len
{//j-i+1 是子序列的长度
len=j-i+1;//那么更新len
break;//并且跳出
}
}
}
if(len==65535) len=0;//如果len没有被更新过，说明没有满足条件的连续数组
return len;
}
写法2：滑动窗口
滑动窗口和双指针的思想类似。
滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
滑动窗口如何用一个for循环来完成这个操作呢。
首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。
只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。
那么问题来了， 滑动窗口的起始位置如何移动呢？
这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程
最后找到 4，3 是最短距离。
在本题中实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
int minSubArrayLen(int target, int* nums, int numsSize){
int start,end;
//滑动窗口的起始位置和终止位置
start=0;end=0;
int sum=0;
int len=INT_MAX;//易错点
for(;end<numsSize;end++)//只需要一层对end指针的循环，即滑动窗口的终止位置的索引
{
sum+=nums[end];//sum：对窗口内的值累加
while(sum>=target)//当窗口满足大于等于target的值就要缩小窗口了。
{//注意用的是while。
if(len>=end-start+1)//end-start+1 是子序列的长度，即窗口的长度
{
len=end-start+1;//更新长度，直到最小长度
}
sum=sum-nums[start];//缩小窗口的同时要把sum也缩小了
start++;//起始位置右移
}
}
if(len==INT_MAX) len=0;//如果len没有被更新过，说明没有满足条件的连续数组
return len;
}
程序中加了while的复杂度不一定会是O(n^2)。需要关注每个元素被操作的次数。
此程序中，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。
易错点：len=INT_MAX是稳定的写法，自己写的65535会报错
C中常量INT_MAX和INT_MIN分别表示最大、最小整数，定义在头文件limits.h中。
-
INT_MAX,INT_MIN数值大小：
因为int占4字节32位，根据二进制编码的规则，INT_MAX = 2^31-1，INT_MIN= -2^31 -
关于INT_MAX INT_MIN的运算
由于二进制编码按原码、补码和反码的规则进行运算，所有程序中对INT_MAX和INT_MIN的运算应当格外注意，在出现溢出的时候，不遵循数学规则。
INT_MAX + 1 = INT_MIN
INT_MIN - 1 = INT_MAX
abs(INT_MIN) = INT_MIN
比较有趣的是，INT_MAX + 1 < INT_MAX， INT_MIN - 1 > INT_MIN, abs(INT_MIN) < 0.
版权声明：本文为CSDN博主「zhusf16」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u012604810/article/details/80290706
59. 螺旋矩阵 II
1. 题目
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
2. 分析
可以总结出一圈下来，需要画四条边。这四条边都要用固定的规则来遍历！
-
经过观察，比如n=3时，每条边可以划分为边长为2的边。所以需要考虑边界的判定条件。边界条件需要依据循环不变量的原则，统一实行左闭右开。
-
其次，当n=4时，我们可以观察到需要画两圈。所以n不同，循环圈数也不同。设置变量循环圈数loop。loop=n/2。
-
在第二圈的时候，初始位置从（0，0）变成了（1，1）。所以需要设置变量startX,startY确定初始位置。在进入下一圈前，startX+1,startY+1。
-
当n=4时，在第二圈的时候，边长比第一圈-1了。所以需要设置偏移量offset。在进入下一圈前，offset+1。
-
每一圈的操作都是模拟顺时针画矩阵的过程:
-
填充上行从左到右
-
填充右列从上到下
-
填充下行从右到左
-
填充左列从下到上
所以while循环的判定条件是按圈来的。while(loop--)。
循环结束的最后，把最后一个值写入矩阵的最中间的值。这个部分需要最后另外写入。
3.知识补充：二维数组开辟存储空间
先看一下用malloc申请一维数组:
int *p=(int *)malloc(n*sizeof(int));//开辟n个内存空间
首先申请n个指针数组（不是数组指针）int *，既然是指针数组，存放的都是指针，那么我们就可以在此基础上继续开辟n个内存空间。由此构成了n * n的二维数组空间。
int **ans=(int*)malloc(sizeof(int*)*n);//申请指针数组
for(i=0;i<n;i++)
{
ans[i]=(int*)malloc(sizeof(int)*n);//再申请n个内存空间
}
参考博客：
(14条消息) 用malloc开辟二维数组的三种办法_张淑芬~的博客-CSDN博客_malloc二维数组
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
(*returnSize)=n;
(*returnColumnSizes)=(int*)malloc(sizeof(int)*n);
int **ans=(int*)malloc(sizeof(int*)*n);//开辟新空间
int i,j;
for(i=0;i<n;i++)
{
ans[i]=(int*)malloc(sizeof(int)*n);
(*returnColumnSizes)[i]=n;
}
int startX = 0;
int startY = 0;
int loop=n/2;//循环圈数
int offset=1;//每一圈的边长都需要调整，所以需要offset偏移数
int mid=n/2;//中间值的坐标。中间值需要最后另外写入
int count=1;//待写入的数值
while(loop--)
{
i=startX;
j=startY;
//上行：从左到右
for(j=startY;j<n-offset;j++)
ans[i][j]=count++;
//右列：从上到下
for(i=startX;i<n-offset;i++)
ans[i][j]=count++;
//下行：从右到左
for(;j>startY;j--)
ans[i][j]=count++;
//左列：从上到下
for(;i>startX;i--)
ans[i][j]=count++;
//从第二圈开始，起始位置都要+1
//例如，第一圈起始位置（0,0)第二圈起始位置(1,1)
startX++;
startY++;
//第二圈开始，边长-1，所以要修正
offset +=1;
}
if(n%2)
ans[mid][mid]=count;
return ans;
}