目录
- 0 引言
- 1 有序数组列表
- 1.1 我的题解（双指针）
- 1.2 根据官方解题修改后
- 2 长度最小的子数组
- 2.1 我的题解
- 2.2 官方滑动窗口（双指针）题解
- 3 螺旋矩阵
- 3.1 我的题解
- 🙋♂️ 作者：海码007
- 📜 专栏：算法专栏
- 💥 标题：
- ❣️ 寄语：书到用时方恨少，事非经过不知难！
0 引言
1 有序数组列表
- 🎈 文档讲解：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
- 🎈 做题状态：没有抓住顺序排序的精髓，导致解题思路不明确。现在知道双指针不仅可以从一头遍历，也可以同时从两头遍历
1.1 我的题解（双指针）
这道题主要利用了数组顺序排序的特性，基于此可以得知数组平方后的最大数一定在数组的两端。所以只需要从两端开始比较找出最大的数，然后插入到新数组的最后一位即可得到排序好的新数组。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// 平方后的数肯定大于等于0
vector<int> result;
int leftIndex, rightIndex;
leftIndex = 0; rightIndex = nums.size() - 1;
// 双指针法基于数组非递减顺序的特点，可知平方后的最大数在数组的两端
// 所以从两头往中间遍历依次把最大数插入到新的数组中，即可得到答案。
while (leftIndex <= rightIndex)
{
// 当左侧数的绝对值更大时插入左侧的数据，leftIndex加一
if (abs(nums[leftIndex]) >= abs(nums[rightIndex]))
{
result.insert(result.begin(), abs(nums[leftIndex] * abs(nums[leftIndex])));
leftIndex++;
}
// 当右侧数的绝对值更大时插入右侧的数据，rightIndex减一
else
{
int temp = abs(nums[rightIndex] * abs(nums[rightIndex]));
result.insert(result.begin(), temp);
rightIndex--;
}
}
return result;
}
};
1.2 根据官方解题修改后
但是我这个题解还有很多不足的地方，例如新数组的插入操作，使用的是Insert，这个函数的时间复杂度是 n，因为是从头插入新的元素，所以每次都会导致其他元素全部向后移动一位。
通过官方题解，可以得知。直接将新数组元素个数确定，然后采用索引的方式从后往前给新数组赋值，这样可以节省很多的时间。
class Solution {
public:
vector<int> sortedSquares2(vector<int>& nums) {
// 平方后的数肯定大于等于0
int leftIndex, rightIndex, insertIndex;
leftIndex = 0; insertIndex = rightIndex = nums.size() - 1;
vector<int> result(nums.size());
while (leftIndex <= rightIndex)
{
if (abs(nums[leftIndex]) >= abs(nums[rightIndex]))
{
result[insertIndex] = abs(nums[leftIndex] * abs(nums[leftIndex]));
leftIndex++;
}
else
{
result[insertIndex] = abs(nums[rightIndex] * abs(nums[rightIndex]));
rightIndex--;
}
insertIndex--;
}
return result;
}
};
2 长度最小的子数组
- 🎈 文档讲解：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
- 🎈 做题状态：不看视频和文档直接写出来了（因该还是学习了之前的双指针思想有所启发），但是代码还是有很多地方需要优化
2.1 我的题解
主要就是通过左右两个索引来对该范围内的数组进行相加统计。但是我的代码存在很多特殊条件的判断，不够精简。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = nums.size() + 1, leftIndex = 0, rightIndex = 0;
int sum = nums[0];
// 当rightIndex大于数组长度时才结束遍历
while (rightIndex < nums.size() && leftIndex < nums.size())
{
// 当sum的合小于目标值，rightIndex加一
if (sum < target)
{
rightIndex++;
if (rightIndex >= nums.size())
{
// 处理特殊情况
if (result == nums.size() + 1)
{
return 0;
}
return result;
}
sum = sum + nums[rightIndex];
}
// 当sum大于等于target时，将result和 (rightIndex-leftIndex)+1 作比较，取最小的值
// 此时leftIndex要减一
else
{
result = min(result, rightIndex - leftIndex + 1);
// 如果result等于1时，直接返回
if (result == 1) return result;
// 先减去左边索引的值，然后在将坐标索引向右移动一位
sum = sum - nums[leftIndex];
leftIndex++;
}
}
// 处理特殊情况
if (result == nums.size() + 1)
{
return 0;
}
return result;
}
};
2.2 官方滑动窗口（双指针）题解
官方的滑动窗口和我写的有细微区别，但是对于 sum 的操作都是一样，当rightIndex向右移动是需要 sum加，让leftIndex向右移动时，需要sum减去值。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口数值之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
};
3 螺旋矩阵
- 🎈 文档讲解：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/BV1SL4y1N7mV/?vd_source=d499e7f3a8e68e2b173b1c6f068b2147
- 🎈 做题状态：主要是循环条件的确定需要慢慢调试
3.1 我的题解
- 思路：根据n来计算需要遍历的圈数，n为1时0圈，n为2时一圈，n为3时一圈。圈数为 n/2 然后取整。然后再根据四个赋值的方向制作四个循环。最后当n为奇数时，需要手动给中间的数赋值。
- 难点：每次循环时，条件的确定。时刻记住数组的最大的下标和数组元素个数相差1。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n, vector<int>(n));
int number = 1;
int i = 0;
// 遍历的圈数确定，圈数 = n/2然后取整 （n为1时0圈，n为2时一圈，n为3时一圈）
for ( ; i < n/2; i++)
{
// 每遍历完一圈后，行的区间要从首尾各减去一，列的区间也要从首尾各减去一
int j = i;
for (j = i; j < (n - i); j++)
{
// 第一行
result[i][j] = number;
number++;
}
for (j = i+1; j < (n - i); j++)
{
// 最后一列，n-1 对应最后一列
result[j][n - 1 - i] = number;
number++;
}
for (j = i+1; j < (n - i); j++)
{
// 最后一行，从最后一列开始遍历，n-1是最后一列
result[n - 1 - i][n - 1 - j] = number;
number++;
}
// 第一列遍历，少一个元素，需要注意
for (j = i+1; j < (n - i) - 1; j++)
{
// 第一列，从最后一行向上
result[n - 1 - j][i] = number;
number++;
}
}
// 当n为奇数时，需要手动给中心点赋值
if (n%2 != 0)
{
result[i][i] = number;
}
// 遍历完后返回结果
return result;
}
};
