LeetCode刷题笔记

！！！

注：本文不会对某一算法进行很深入，很细致的讲解，博主追求以最少的文字获得更深的理解，全文的都将按照是什么（what？）``为什么（why？）``怎么做（how？）来进行讲解，我们一直都坚持实践是检验认识真理性的唯一标准，好的算法要能真正解决实际问题，不能光是侃侃而谈。本文代码都根据C++来实现，我们一直秉承一个理念：编程语言永远只是工具，重要的是思想。若想细致了解某一算法，可进行专门的学习。

！！！

回溯算法

认识

是什么：回溯算法也叫回溯搜索法，就是一种搜索方式，本质就是穷举或枚举所有可能，如果当前选择不符合条件，就回退一步，尝试其他选择，直到找到符合条件的解或枚举完所有情况。所以有时候效率也不会很高，一般都以递归函数实现，回溯和递归相辅相成。
为什么：回溯算法的基本思想是：从问题的某一种状态开始搜索，每次搜索时都尝试所有可能的下一步状态，直到找到一个解或者所有可能的状态都被尝试过。如果找到了一个解，就返回；否则，回溯到上一个状态，继续搜索。回溯算法的时间复杂度通常很高，因为它需要穷举所有可能的情况。但是，在某些情况下，回溯算法是最优解，因为它可以找到所有解。
怎么做：回溯算法的实现通常使用递归。具体来说，可以定义一个递归函数，该函数接收当前状态作为参数，并尝试所有可能的下一步状态。如果找到了一个解，就返回；否则，回溯到上一个状态，继续搜索。在递归函数中，需要注意以下两点：
- 定义递归函数的参数和返回值。通常情况下，递归函数的参数包括当前状态和已经搜索到的解，返回值为已经搜索到的解。
- 在递归函数中，需要判断当前状态是否满足要求。如果满足要求，就将当前状态加入已经搜索到的解中，并返回；否则，继续搜索。

根据上述特点，我们很容易可以得到一个回溯算法的程序模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果
        return;
    }
    for (一种情况 : 当前层的所有情况(若比作N叉树，就是当前层的所有结点)) {
        处理该情况
        backtracking(路径, 下一个选择列表);//递归过程
        回溯，撤销处理结果
    }
}

实践

组合

题目链接

题目：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

1 2	输入：n = 1, k = 1 输出：[[1]]

1 <= n <= 20
1 <= k <= n

题解：

当看到这个题，我们的本能反应就是：哎，这不就是高中学的那个排列组合里面的组合吗？好像是 $C_n^m$ 来着，就是从n个数字里面选择由m个数字所组成的所有组合嘛。但是我们这不是数学题，不然就没意思了，那我们来好好分析一下吧，看我们能怎么解决它：

我们可以很容易想到：如果有n个数字，我们现在要获得m个数字组成的所有组合，我们可以先在n个数字里面先取一个数字，然后再在剩下的 $n-1$ 个数字里面再取一个数字……以此类推，我们最后可以取到m个数字，这就是我们要的所有组合里面的其中一个组合，我们把它放到结果集里面，然后再进行相同的操作，直到取完我们要的所有组合。如果结合回溯算法的树形结构，就是当我从n个数字里面取了一个后，剩下的 $n-1$ 个数字都可以成为这个数字的备选数字，但是考虑到组合没有顺序要求，所以像 $[1,2]和[2,1]$ 这样的组合其实是一样的，所以已经选择过的数字将不能成为后面数字的备选数字。

举个例子，假如我们要从 $[1,2,3,4]$ 里面选择个数为3的所有组合，那么我们很容易联想到下面的流程：

graph TB;
	1 --> 2
	1 --> 3
	1 -.-> 4
	2 --> a(3)
	2 --> b(4)
	3 --> c(4)
	d(2) --> e(3)
	e --> f(4)

总共就四种组合情况

现在思想我们已经知道了，让我们试着转换成代码来试试看。我们可以用一个二维结果集 $res$ 来保存我们找到的所有组合，用一个一维的集 $path$ 来进行数字的临时保存，我们这里的终止条件就是当 $path$ 集里面的数字个数达到了 $k$ 个，当满足终止条件就将 $path$ 集里面的数据存入结果集 $res$ 里面，随后就跳出这个函数，进行回溯操作，如果不满足终止条件，说明个数还没达到要求的个数，我们再取剩下的没有选择过的数字，直到满足终止条件。

以下是具体的实现代码：

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    vector<vector<int>> combine(int n, int k) {
        getGroup(n, k, 1);
        return res;
    }

    void getGroup(int n, int k, int startIndex){
        if (path.size() == k) {
            res.push_back(path);
            return;
        }

        for (int i = startIndex; i <= n; i++) {
            path.push_back(i);
            getGroup(n, k, i + 1);
            path.pop_back();
        }
    }
};

其实只要想清楚了整个流程，想好了用什么算法，代码并不需要很多，就能解决这个问题。

N皇后问题

题目链接

题目：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例1：

1
2
3

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1 2	输入：n = 1 输出：[["Q"]]

提示：

1 <= n <= 9

题解：

当看见这个题，我的第一反应就是，这不是我之前Java课程那本很大很厚的黑皮书里面的经典的八皇后问题的拓展吗，好家伙，直接N皇后了，之前我不知道回溯算法，当时只需要找到一种就行了，我硬生生熬夜才给它做出来了，让我对Java产生了短暂的厌恶。现在我学了回溯算法，看我把你撕碎！！！

用回溯算法的思路，这个题虽然显示的是困难，但是其实思路很简单。一个 $N*N$ 大小的棋盘，我们可以先在第一行放一个，然后在第二排放一个，然后在第三排放一个，直到放到最后一行，在摆放棋子的过程中，我们每一次放都需要对该位置放置的合法度进行判断，判断一下它所在的列，左上斜线，右上斜线是否已经放置了棋子，如果都没有放置，那么我就可以摆放一个，反之则不能摆放。当在最后一行摆放了棋子后，那我们就找到了一种N个皇后的摆放方式，直接加到结果集 $res$ 里面。我们每一次放置了皇后过后，不管是否找到了一种摆放方式，我们都要进行回溯，就是还原放置前的样子，然后对其下一个格子进行相同的操作。

所以：

终止条件：最后一行放置完毕

循环域：一行的每一列的集合

递归域：每一列的集合

上代码：

class Solution {
private:
    vector<vector<string>>res;
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string>path(n,string(n,'.'));
        insertBacking(n, 0, path);
        return res;
    }

    void insertBacking(int n, int row, vector<string>& path) {
        if (row == n) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < n; i ++) {
            if (isValid(n, row, i, path)) {
                path[row][i] = 'Q';
                insertBacking(n, row + 1, path);
                // 回溯
                path[row][i] = '.';
            }
        }
    }

    bool isValid(int n, int row, int col, vector<string>& path) {
        // 列
        for (int i = 0; i < row; i ++) {
            if (path[i][col] == 'Q') return false;
        }
        // 45deg
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --) {
            if (path[i][j] == 'Q') return false;
        }
        // 135deg
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++) {
            if (path[i][j] == 'Q') return false;
        }
        
        return true;
    }
};

代码解读：

代码使用回溯算法求解，主要思路如下：

定义一个二维字符串数组 res，用于存储所有符合要求的解；
定义一个 insertBacking 函数，用于递归回溯，其中参数 n 表示棋盘大小，row 表示当前处理的行数，path 表示当前棋盘的布局；
当 row == n 时，说明已经处理完了所有的行，将 path 添加到 res 中；
在当前行 row 中枚举每一个列 col，检查该位置是否可以放置皇后，如果可以，就将皇后放在该位置，然后继续处理下一行，否则跳过；
处理完当前行后，需要回溯到上一行，将上一行中放置的皇后位置改回空位，然后尝试该行的下一个位置；
isValid 函数用于检查当前位置是否可以放置皇后，检查的方式包括：检查当前列是否已经有皇后，检查 45 度和 135 度方向上是否有皇后。

最终，solveNQueens 函数调用 insertBacking 函数，完成对 N-Queens 问题的求解，返回所有的解。

注意：

第六行我用了string(n, '.')语句，该语句可以生成一个长度为 n 的每一位都是'.'的字符串，加上vector的初始化语法，完成了对结果集res的初始化，对C++不了解的朋友可以根据自己的兴趣去了解一下对应的知识点，但是不强制。因为我们一直秉持一个理念：“编程语言永远只是工具，重要的是思想”。

附：

为了一些刚学习Java的同学理解，这里给出Java版本，希望不要被那个黑色厚书给击败，Java还是很有趣的，🙉🛩️

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }


    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(Array2List(chessboard));
            return;
        }

        for (int col = 0;col < n; ++col) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }


    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }


    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i=0; i<row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

贪心算法

认识

是什么：贪心算法是一种基于贪心策略的算法，它在每个阶段选择当前看起来最优的解决方案，以期望能够得到全局最优解。在贪心算法中，我们不考虑未来的决策所造成的影响，只关注当前的最优解。
为什么：贪心算法具有简单、高效的特点，并且可以应用于许多实际问题的求解中。虽然贪心算法不能保证一定得到全局最优解，但是对于某些问题，贪心算法能够得到与全局最优解非常接近的解。
怎么做：

贪心算法的实现步骤通常包括以下几个步骤：

1. 确定问题的最优子结构：将原问题分解成若干个子问题，每个子问题都可以独立求解，且原问题的最优解包含所有子问题的最优解。

2. 构造贪心选择：确定每个子问题的最优解，这里需要使用贪心策略，即每次选择当前看起来最优的解决方案。

3. 证明贪心选择的正确性：证明每个子问题的最优解组合起来可以得到原问题的最优解。

4. 实现贪心算法：根据贪心选择的策略实现算法，通常使用迭代或递归的方式求解。

需要注意的是，在使用贪心算法时，需要满足贪心选择性质和最优子结构性质。如果问题不满足这些性质，则贪心算法可能无法得到正确的结果。

实践

分发饼干

题目链接

题目：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示：

1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

题解：

说实话，我第一眼看见这个题，我有点懵，但是看见这只是一个简单题，心想：蛙趣，怎么搞的？简单题都看懵了（但是我确实没有想到很好的方法）。我沉思了一下……有了：我直接一个孩子一个孩子分配，每次都找大于孩子胃口且最接近孩子胃口的饼干，这样不就可以了。试一试

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 每次都找一个最接近孩子胃口的

        int countChild = 0;
        // 最合适的下标
        int suIndex = -1;
        // 差值
        int delta = -1;
        for (int i = 0; i < g.size(); i ++) {

            for (int j = 0; j < s.size(); j++) {
                if (s[j] == -1) continue;
                if (s[j] >= g[i] && s[j] - g[i] > delta) {
                    delta = s[j] - g[i];
                    suIndex = j;
                }
            }
            if (delta != -1) {
                s[suIndex] = -1;
                countChild ++;
                delta = -1;
            }
        }

        return countChild;
    }
};

直接运行：😄

😢😢😢😢😢😢

错了……

why？

明明没问题呀！！

怎么会呀？这可是简单题呀😱我是不是要寄了，啊，不行，我得思考一下……………………………………………………

啊，我知道了，虽然我这个思路看似没问题，但是我虽然每次都选一个最接近当前孩子胃口的饼干，看似很合理，但是，但是万一下一个孩子更适合当前这个饼干呢，当测试数据少的时候可能没问题，但是要是数据到达一定程度，就会有问题。🙀

怎么办？有了：我何不先满足胃口大的孩子，虽然我最开始的思路错了，但是也是有一定的用处，要是分配给当前孩子的饼干就是最合适他的不就行了吗，但是怎么确定就是最合适的呢。我们判断是不是最合适的，本质上不就是看二者之间的差值是不是最小的嘛，之所以我不知道是不是最合适的，是因为我不知道下一个数字和当前数字的大小关系，那我要是给这两个数组都排个序，那不就解决了吗，下一个数字和当前数字的大小关系不就确定了吗？而且我还有两种分配方式：1️⃣先给胃口大的分配；2️⃣ 先给胃口小的分配；二者的思路是一致的，在结合我最开始的想法，那问题不就解决了吗？

先给胃口大的分配

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        // 优先满足胃口大的Child

        int countChild = 0;
        int index_g = g.size() - 1, index_s = s.size() - 1;
        while(index_g >= 0 && index_s >= 0) {
            if (s[index_s] >= g[index_g]) {
                countChild++;
                index_s--;   
            }
            index_g--;
        }
        return countChild;
    }
};

过了：

先给胃口小的分配

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        // 优先满足胃口小的Child

        int countChild = 0;
        int index_g = 0, index_s = 0;
        while(index_g < g.size() && index_s < s.size()) {
            if (s[index_s] >= g[index_g]) {
                countChild++;
                index_g++;   
            }
            index_s++;
        }
        return countChild;
    }
};

也过了！！！

nice！！！😸

刷题记录

_2023/3/26

和相等的子数组

题目描述：

给你一个下标从 0 开始的整数数组 nums ，判断是否存在两个长度为 2 的子数组且它们的和相等。注意，这两个子数组起始位置的下标必须 不相同 。

如果这样的子数组存在，请返回 true，否则返回 false 。

子数组 是一个数组中一段连续非空的元素组成的序列。

示例 1：

1
2
3

输入：nums = [4,2,4]
输出：true
解释：元素为 [4,2] 和 [2,4] 的子数组有相同的和 6 。

示例 2：

1
2
3

输入：nums = [1,2,3,4,5]
输出：false
解释：没有长度为 2 的两个子数组和相等。

示例 3：

输入：nums = [0,0,0]
输出：true
解释：子数组 [nums[0],nums[1]] 和 [nums[1],nums[2]] 的和相等，都为 0 。
注意即使子数组的元素相同，这两个子数组也视为不相同的子数组，因为它们在原数组中的起始位置不同。

提示：

2 <= nums.length <= 1000
$-10^9$ <= nums[i] <= $10^9$

这个题及时一个简单题，我们看完题目其实就会有一个很简单粗暴的想法：直接两层for循环不就解决了吗？

马上试试：

class Solution {
public:
    bool findSubarrays(vector<int>& nums) {
        // 先用最简单粗暴的方式
        int temp_sum = 0;
        for (int i = 0; i < nums.size() - 2; i ++) {
            temp_sum = nums[i] + nums[i + 1];
            for (int j = i + 1; j < nums.size() - 1; j ++) {
                if (temp_sum == nums[j] + nums[j + 1]) return true;
            }
        }
        return false;
    }
};

感觉没问题，直接自信点击提交按钮。

直接就过了，但是我们肯定不能就这样妥协，这样根本达不到练题的目的，虽然这是一个简单题。这个时间花的也太多了吧，能不能压缩一下。

这个题的本质不就是找到两个和相等的长度为2 的子数组吗？能不能值遍历一次，这样时间复杂度会大大降低。怎么办呢？突然，我灵光一现，仿佛有人点了我一下。

人生苦短，我用set

我直接遍历一次，从第一个开始，用一个set集合将当前数字和他的下一个数字的和保存起来。set集合的特性就是不允许有重复的项出现，那我一个一个保存，如果有重复的，那么就算我加进去一个新的和，如果有一样的，该set集合的长度并不会增加，那我只需要每次加完了都判断一下不就好了。（如果有对set集合的特性不清楚的朋友可以点击这里去了解一下）

想清楚了，直接写：

class Solution {
public:
    bool findSubarrays(vector<int>& nums) {
        // 用set
        set<int> set;
        int len = 0;
        for (int i = 0; i < nums.size() - 1; i ++){
            len = set.size();
            set.insert(nums[i] + nums[i + 1]);
            if (set.size() == len) return true;
        }
        return false;
    }
};

运行一下：

呼，看见0ms我就开心，但是内存占用变多了。

博主目前没有想到更好的方法可以同时兼顾时间和空间，如果你有好的点子，欢迎pr

Leetcode刷题笔记

一个很闲的vegetable

LeetCode刷题笔记

回溯算法

认识

实践

组合

N皇后问题

贪心算法

认识

实践

分发饼干

刷题记录

和相等的子数组

其他文章

Java数据结构与算法

MySQL数据库基本操作