算法训练day02Leetcode977有序数组平方209长度最小的字数组59螺旋问题

今日学习的文章链接和视频链接

https://www.bilibili.com/video/BV1QB4y1D7ep/?vd_source=8272bd48fee17396a4a1746c256ab0ae

https://www.bilibili.com/video/BV1tZ4y1q7XE/?vd_source=8272bd48fee17396a4a1746c256ab0ae

https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

自己看到题目的第一想法

直接将所有数字平方，再排一个序（快速排序）时间复杂度是O(nlogn),但是不满足要求

解题思路

暴力排序

最直观的想法，莫过于：每个数平方之后，排个序，代码如下：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for (int i = 0; i < A.size(); i++) {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); // 快速排序
        return A;
    }
};

在 C++ 中，sort(A.begin(), A.end()); 这行代码使用的是标准库中的 std::sort 函数来对数组或向量 A 进行排序。std::sort 的实现并不是纯粹的快速排序（Quick Sort），而是一种结合多种排序算法的混合排序。

C++ 标准库中的 std::sort 通常实现为introsort，这是一种结合了快速排序、堆排序（Heapsort）和插入排序（Insertion Sort）的混合排序算法。Introsort 开始时使用快速排序，当递归深度过大时切换到堆排序，对较小的数组子集使用插入排序。这种混合方法旨在提供快速排序的高效性，同时避免其在最坏情况下的性能下降。

时间复杂度方面，std::sort 的平均和最佳情况时间复杂度为 O(n log n)，其中 n 是数组或向量 A 中元素的数量。而在最坏的情况下（例如，当快速排序的划分始终很不平衡时），introsort 由于切换到堆排序，保持时间复杂度为 O(n log n)，避免了快速排序最坏情况下的 O(n2) 时间复杂度。

因此，尽管 std::sort 在某些实现中起初使用快速排序，但它通过结合其他排序算法确保了更加稳定和高效的整体性能。

快速排序（Quick Sort）是一种高效的排序算法，由托尼·霍尔（Tony Hoare）在1960年代初期发明。它采用分治法（Divide and Conquer）的策略进行排序，其基本思想是：

1. 选择基准值（Pivot）：从数组中选择一个元素作为基准值。
2. 分区操作：重新排列数组，所有比基准值小的元素都移到基准值的前面，所有比基准值大的元素都移到基准值的后面。这个操作完成后，基准值所在的位置就是其最终位置。
3. 递归排序子数组：递归地将小于基准值和大于基准值的子数组进行快速排序。

快速排序的平均和最好情况的时间复杂度为 O(n log n)，但最坏情况下的时间复杂度为 O(n2)。最坏情况通常发生在每次分区时，都得到了极不平衡的子数组。

快速排序的实现

以下是快速排序的一个基本实现示例（使用 C++）：

#include <vector>

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high); // 执行分区操作
        quickSort(arr, low, pivot - 1);  // 递归排序左子数组
        quickSort(arr, pivot + 1, high); // 递归排序右子数组
    }
}

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];    // 选择最后一个元素作为基准
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

int main() {
    std::vector<int> array = {10, 7, 8, 9, 1, 5};
    quickSort(array, 0, array.size() - 1);
    // 输出排序后的数组...
}

在这个实现中，partition 函数是核心，它负责对数组进行分区，并返回基准值的正确位置。quickSort 函数则递归地调用自身来对分区后的子数组进行排序。这个实现中使用了最后一个元素作为基准值，但在实际应用中，选择不同的基准值策略（如随机选择、取中值等）可以帮助避免最坏情况的发生，从而提高算法的平均性能。

双指针法

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，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]; 。

不难写出如下代码：

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;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。

遇到的困难

    vector<int> result(A.size(), 0);

我初始化定义的是

vector<int> result;

导致初始化报错Segmentation fault (core dumped)

Segmentation fault (core dumped)" 是在 UNIX 或类 UNIX 系统中运行程序时可能遇到的错误消息，表示程序试图访问它无权访问的内存区域。这通常是由于以下几种常见原因之一造成的：

无效或未初始化的指针：试图解引用空指针（指向 NULL 或 nullptr 的指针）或未初始化的指针。

数组越界：访问数组或向量之外的内存，如访问数组的负索引或超过其大小的索引。

堆栈溢出：通常由于递归调用过深导致。

释放已释放的内存：试图释放已经释放的内存块，通常发生在使用 delete 或 free 时。

内存损坏：破坏内存管理结构，如通过指针写入越过分配给变量的内存。

在 C++ 中，vector<int> result(A.size(), 0); 这行代码创建了一个名为 result 的整数向量（std::vector<int>），并具有特定的初始化特性。这行代码可以拆分为两部分来理解：

1. A.size(): 这是获取另一个向量 A 的大小（即它包含的元素数量）。

2. vector<int> result(..., 0): 这是创建一个整数向量 result。向量的大小被设置为与 A 相同，而每个元素的初始值被设置为 0。

综合来看，这行代码的作用是创建一个大小等于向量 A 的新向量 result，并将 result 中的每个元素初始化为 0。例如，如果向量 A 包含 5 个元素，那么 result 将是一个包含 5 个元素的向量，每个元素都是 0。这种初始化方法在需要一个与另一个向量大小相同、但所有元素都设定为特定值的新向量时非常有用。

209 长度最小的子数组

给定一个含有 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

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

自己看到题目的第一想法

两个循环，一个控制起始位置，另一个控制终止位置

判断大于等于s的最小长度

解题思路

滑动窗口，类似于双指针，最重要的思路是如何移动起始位置

首先移动终止位置，当集合里的所有元素和target,开始移动起始位置

暴力解法

这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)。

代码如下：

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(1)
后面力扣更新了数据，暴力解法已经超时了。

这段代码的目的是找出数组 nums 中长度最小的子数组，使得子数组中的元素之和至少为 target。它使用了两层嵌套循环来实现这一目的。我们来分析其时间复杂度：

1. 外层循环：外层循环遍历整个数组，因此它的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。

2. 内层循环：对于外层循环中的每个元素，内层循环从当前元素开始，一直遍历到数组的末尾。在最坏的情况下，内层循环对于每个外层的迭代也需要 O(n) 次迭代。

由于内层循环嵌套在外层循环内部，总的迭代次数大致是 n + (n-1) + (n-2) + … + 1，这是一个等差数列求和，其总和为 (\frac{n(n+1)}{2})。

因此，该算法的时间复杂度为 O(n2)，即平方阶时间复杂度。

此外，空间复杂度为 O(1)，因为除了给定的数组外，只使用了固定数量的额外空间（如 sum、result 和 subL 变量）。

滑动窗口法

滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

在本题中实现滑动窗口，主要确定如下三点：

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

解题的关键在于 窗口的起始位置如何移动，如图所示：

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)

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;
    }
};

这段代码是一个更高效的解法，用于找出数组 nums 中的最小长度子数组，其元素之和至少为 s。这个解法使用了滑动窗口的方法。让我们分析它的时间复杂度：

1. 外层循环：外层循环遍历整个数组一次。在每次迭代中，它将当前元素加到 sum 中。这个循环的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。

2. 内层循环（While循环）：这个循环减小滑动窗口的大小，直到窗口内的元素和小于 s。关键是，这个循环不是嵌套的。每个元素最多被加入和移出 sum 一次。这意味着，尽管它在外层循环的内部，但是整个数组在整个算法过程中只被遍历了两次：一次是加入窗口（外层循环），另一次是离开窗口（内层循环）。因此，这个循环的时间复杂度也是 O(n)。

由于内层循环和外层循环都是线性的，并且它们不是严格的嵌套关系（即，内层循环不会对于外层循环的每次迭代都执行n次），整个算法的时间复杂度是 O(n)。

这种滑动窗口的方法大大提高了效率，特别是对于长数组，因为它避免了不必要的重复计算，每个元素只被处理一次。

至于空间复杂度，它是 O(1)，因为算法的空间消耗不随输入数组 nums 的大小而变化，只使用了固定数量的额外空间（如 sum、result、i 和 subLength 变量）。

59 螺旋矩阵

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

我的想法

脑袋空空

题目解析

循环不变量，确定区间规则

day01 中二分法一定要坚持循环不变量原则

模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上

由外向内一圈一圈这么画下去。

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

每一个拐角处的处理规则，拐角处让给新的一条边来继续画。

因为我是先在空白cpp上编写，就涉及到遍历二维vector,下面对几种遍历方法做一个记录。

在 C++ 中遍历一个二维 vector（即 vector 的 vector）可以通过两层嵌套循环完成。这里有几种不同的方法来实现这一过程：

1. 使用传统的索引循环：

#include <vector>
#include <iostream>

int main() {
    std::vector<std::vector<int>> vec2d = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

    for (size_t i = 0; i < vec2d.size(); ++i) {
        for (size_t j = 0; j < vec2d[i].size(); ++j) {
            std::cout << vec2d[i][j] << ' ';
        }
        std::cout << std::endl;
    }

    return 0;
}

2. 使用范围基于的 for 循环（C++11 及以后）：

#include <vector>
#include <iostream>

int main() {
    std::vector<std::vector<int>> vec2d = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

    for (const auto& row : vec2d) {
        for (int elem : row) {
            std::cout << elem << ' ';
        }
        std::cout << std::endl;
    }

    return 0;
}

3. 使用迭代器：

#include <vector>
#include <iostream>

int main() {
    std::vector<std::vector<int>> vec2d = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

    for (auto it = vec2d.begin(); it != vec2d.end(); ++it) {
        for (auto jt = it->begin(); jt != it->end(); ++jt) {
            std::cout << *jt << ' ';
        }
        std::cout << std::endl;
    }

    return 0;
}

在所有这些方法中，外层循环遍历二维向量的每一行（或子向量），而内层循环遍历该行（子向量）中的每个元素。您可以根据需要选择最适合您的用例的方法。范围基于的 for 循环（自 C++11 起）因其简洁性和清晰性而特别受欢迎。

整体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; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            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， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
空间复杂度 O(1)

要分析这个 generateMatrix 函数的时间复杂度，我们需要考虑循环的次数和每次循环内发生的操作。

该函数生成一个 n x n 的螺旋矩阵。主循环（while 循环）的次数由 loop 变量控制，它是 n / 2。在每次循环中，有四个 for 循环，分别填充矩阵的上边、右边、下边和左边。每个 for 循环遍历的长度随着循环的进行逐渐减少，但总的来说，每个循环都会访问 n 个元素，因为矩阵的每一边长度都是 n（减去逐渐增加的 offset）。

在最坏的情况下，我们可以估计这个函数的时间复杂度：

• 每次主循环中，四个 for 循环总共访问接近 4n 个元素（因为每条边大约有 n 个元素）。

• 主循环执行 n / 2 次。

因此，总的时间复杂度大致是 O(4n * n/2)，即 O(2n^2)。在大 O 记号中，常数因子是不考虑的，所以最终的时间复杂度是 O(n^2)。

这意味着，该函数的时间复杂度与矩阵中元素的总数成平方关系，这对于这类问题来说是相当高效的，因为你必须至少访问一次矩阵中的每个元素。

遇到的问题

我在自己写的过程中，在for循环里面写上了int，导致i和j重新初始化，无法完成循环