977.有序数组的平方
解题思路
- 暴力解法：先将每个元素进行平方，再对其平方进行快速排序。时间复杂度是 O(n + nlogn)
- 双指针解法：数组是非递减排序，存在负数，也就是说平方后的最大值将会在两边。用 i 和 j 两个指针分别指向数组的起始位置和终止位置，定义一个和原数组大小相同的新数组result，k指向result数组终止位置，将数组从左到右（k--)输出。
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]; 。遇到的问题
- 第一反应还是暴力求解，并没有想到双指针方法
- 对双指针理解容易，写起来略微困难
代码实现
暴力求解（C语言版）
引用力扣官方题解的代码来说明。
// 定义比较函数cmp，用于qsort排序时的元素比较
int cmp(const void* _a, const void* _b) {
int a = *(int*)_a, b = *(int*)_b;
return a - b; // 返回a与b的大小关系，负数表示_a排在_b之前，正数表示_a排在_b之后，零表示相等
}
// 将数组中每个元素的平方进行排序
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
(*returnSize) = numsSize; // 将返回的数组大小赋值为numsSize
int* ans = malloc(sizeof(int) * numsSize); // 分配存储排序后结果的内存空间
for (int i = 0; i < numsSize; ++i) {
ans[i] = nums[i] * nums[i]; // 计算每个元素的平方并存入ans数组
}
qsort(ans, numsSize, sizeof(int), cmp); // 使用qsort对ans数组进行排序，使用cmp作为比较函数
return ans; // 返回排序后的结果数组
}
双指针求解（C语言版）
int* sortedSquares(int* nums, int numsSize, int* returnSize){
//返回的数组大小是原数组大小
*returnSize = numsSize;
int left = 0;
int right = numsSize - 1;
//最后要返回的结果数组
int* ans = (int*)malloc(sizeof(int) * numsSize);
int index;
for(index = numsSize - 1; index >= 0; index--) {
int lSquare = nums[left] * nums[left];
int rSquare = nums[right] * nums[right];
//若左指针指向元素平方比右指针指向元素平方大，将左指针指向元素平方放入结果数组。左指针右移一位
if(lSquare > rSquare) {
ans[index] = lSquare;
left++;
}
else {
ans[index] = rSquare;
right--;
}
}
return ans;
}总结
题目不是很难，不过还需多多琢磨。
209.长度最小的子数组
解题思路
- 暴力解法：两层for循环实现，第一层for循环用来控制起始位置，第二层for循环用来控制终止位置。时间复杂度为O(n^2)。（力扣提示超时）
- 滑动窗口法：for循环的索引表示滑动窗口的终止位置，关键就变成了起始位置如何移动。当前窗口的值大于s时，起始位置向前移动。时间复杂度为O(n)。
遇到的问题
对滑动窗口的理解较为吃力，自己不能独立写出代码
代码实现
暴力求解
int minSubArrayLen(int target, int* nums, int numsSize){
//初始化最小长度为INT_MAX
int minLength = INT_MAX;
int sum;
int left, right;
for(left = 0; left < numsSize; ++left) {
//每次遍历都清零sum，计算当前位置后和>=target的子数组的长度
sum = 0;
//从left开始，sum中添加元素
for(right = left; right < numsSize; ++right) {
sum += nums[right];
//若加入当前元素后，和大于target，则更新minLength
if(sum >= target) {
int subLength = right - left + 1;
minLength = minLength < subLength ? minLength : subLength;
}
}
}
//若minLength不为INT_MAX，则返回minLnegth
return minLength == INT_MAX ? 0 : minLength;
}滑动窗口求解
int minSubArrayLen(int target, int* nums, int numsSize){
//初始化最小长度为INT_MAX
int minLength = INT_MAX;
int sum = 0;
int left = 0, right = 0;
//右边界向右扩展
for(; right < numsSize; ++right) {
sum += nums[right];
//当sum的值大于等于target时，保存长度，并且收缩左边界
while(sum >= target) {
int subLength = right - left + 1;
minLength = minLength < subLength ? minLength : subLength;
sum -= nums[left++];
}
}
//若minLength不为INT_MAX，则返回minLnegth
return minLength == INT_MAX ? 0 : minLength;
}总结
利用滑动窗口求解时的关键在于for循环索引的理解以及起始位置和终止位置如何进行移动。
59.螺旋矩阵II
解题思路
- 本题并不涉及到什么算法，就是模拟过程，但十分考察对代码的掌控能力。
- 转圈这个过程需要处理的边界条件很多
- 坚持循环不变量原则。
遇到的困难
不说了，遇到的困难就是都是困难，思路困难、理解困难、写代码困难......还得多多理解+练习。。。
代码实现
这里依旧用的是卡哥题解里的代码
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
//初始化返回的结果数组的大小
*returnSize = n;
*returnColumnSizes = (int*)malloc(sizeof(int) * n);
//初始化返回结果数组ans
int** ans = (int**)malloc(sizeof(int*) * n);
int i;
for(i = 0; i < n; i++) {
ans[i] = (int*)malloc(sizeof(int) * n);
(*returnColumnSizes)[i] = n;
}
//设置每次循环的起始位置
int startX = 0;
int startY = 0;
//设置二维数组的中间值，若n为奇数。需要最后在中间填入数字
int mid = n / 2;
//循环圈数
int loop = n / 2;
//偏移数
int offset = 1;
//当前要添加的元素
int count = 1;
while(loop) {
int i = startX;
int j = startY;
//模拟上侧从左到右
for(; j < startY + n - offset; j++) {
ans[startX][j] = count++;
}
//模拟右侧从上到下
for(; i < startX + n - offset; i++) {
ans[i][j] = count++;
}
//模拟下侧从右到左
for(; j > startY; j--) {
ans[i][j] = count++;
}
//模拟左侧从下到上
for(; i > startX; i--) {
ans[i][j] = count++;
}
//偏移值每次加2
offset+=2;
//遍历起始位置每次+1
startX++;
startY++;
loop--;
}
//若n为奇数需要单独给矩阵中间赋值
if(n%2)
ans[mid][mid] = count;
return ans;
}总结
坚持循环不变量原则。
今日总结
感觉跟历劫一样，困难重重，脑子刚长出来就要大量运动了啊啊啊。今日刷题不是很扎实，只是基本理解了每道题，但自己写不出来，得看题解，还得之后有空再回过头来看看。
