❤️《十大算法入门》❤️(建议收藏)_英雄哪里出来-CSDN博客

watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1doZXJlSXNIZXJvRnJvbQ==,size_16,color_FFFFFF,t_70#pic_center

🙉饭不食，水不饮，题必须刷🙉
C语言免费动漫教程，和我一起打卡！ 🌞《光天化日学C语言》🌞
LeetCode 太难？先看简单题！ 🧡《C语言入门100例》🧡
数据结构难？不存在的！ 🌳《数据结构入门》🌳
LeetCode 太简单？算法学起来！ 🌌《夜深人静写算法》🌌
究极算法奥义！深度学习！ 🟣《深度学习100例》🟣

我们平时在 「求职面试」 的时候，总会遇到被要求做一个算法题，如果你写不出来，可能你的 「 offer 」 年包就打了七折，或者直接与 「 offer 」 失之交臂，都是有可能的。
当然，它不能完全代表你的「编码能力」，因为有些 「算法」 确实是很巧妙，加上当时紧张的面试氛围，想不出来其实也是正常的，但是你能确保面试官是这么想的吗？不能！
我们要做的是十足的准备，既然决定出来，offer 当然是越高越好，毕竟大家都要「养家糊口」，房价又这么贵，如果能够在算法这一块取得先机，也不失为一个捷径。
但是，「茫茫多的算法题，我们从何刷起呢？」那么，接下来，我会介绍几个简单的入门算法，并且介绍下每个算法对应的题型，希望对你有所帮助！

💨一、排序

一般网上的文章在讲各种 「排序」 算法的时候，都会甩出一张 「思维导图」，如下：

watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1doZXJlSXNIZXJvRnJvbQ==,size_32,color_FFFFFF,t_70#pic_center

当然，我也不例外……
这些概念也不用多说，只要你能够把「快速排序」的思想理解了。基本上其它算法的思想也都能学会。这个思路就是经典的：「要学就学最难的，其它肯定能学会」。因为当你连「最难的」都已经 「 KO 」 了，其它的还不是「小菜一碟」？信心自然就来了。
我们要战胜的其实不是「算法」本身，而是我们对 「算法」 的恐惧。一旦建立起「自信心」，后面的事情，就「水到渠成」了。
然而，实际情况比这可要简单得多。实际在上机刷题的过程中，不可能让你手写一个排序，你只需要知道 C++ 中 STL 的 sort 函数就够了，它的底层就是由【快速排序】实现的。
所有的排序题都可以做。我挑一个来说。至于上面说到的那十个排序算法，如果有缘，我会在八月份的这个专栏 ❤️《数据结构入门》导航 ❤️ 中更新，尽情期待~~

I、例题描述

给你两个有序整数数组 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2，请你将 n u m s 2 nums2 nums2 合并到 n u m s 1 nums1 nums1 中，使 n u m s 1 nums1 nums1 成为一个有序数组。初始化 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2 的元素数量分别为 m m m 和 n n n 。你可以假设 n u m s 1 nums1 nums1 的空间大小等于 m + n m + n m+n，这样它就有足够的空间保存来自 n u m s 2 nums2 nums2 的元素。
样例输入： n u m s 1 = [ 1 , 2 , 3 , 0 , 0 , 0 ] , m = 3 , n u m s 2 = [ 2 , 5 , 6 ] , n = 3 nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 nums1=[1,2,3,0,0,0],m=3,nums2=[2,5,6],n=3
样例输出： [ 1 , 2 , 2 , 3 , 5 , 6 ] [1,2,2,3,5,6] [1,2,2,3,5,6]
原题出处： LeetCode 88. 合并两个有序数组

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    }
};

III、思路分析

这个题别想太多，直接把第二个数组的元素加到第一个数组元素的后面，然后直接排序就成。

IV、时间复杂度

STL 排序函数的时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)，遍历的时间复杂度为 O ( n ) O(n) O(n)，所以总的时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)。

IV、源码详解

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = m; i < n + m; ++i) {
            nums1[i] = nums2[i-m];               // (1)
        }
        sort(nums1.begin(), nums1.end());        // (2)
    }
};

( 1 ) (1) (1) 简单合并两个数组；
( 2 ) (2) (2) 对数组1进行排序；

VI、本题小知识

只要能够达到最终的结果， O ( n ) O(n) O(n) 和 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) 的差距其实并没有那么大。只要是和有序相关的，就可以调用这个函数，直接就出来了。

🥖二、线性枚举

线性枚举，一般配合的数据结构是【数组】或者【链表】，实现方式就是一个循环。正因为只有一个循环，所以线性枚举解决的问题一般比较简单，而且很容易从题目中看出来。

I、例题描述

编写一个函数，将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
样例输入： [ “ a ” , “ b ” , “ c ” , “ d ” ] [“a”, “b”, “c”, “d”] [“a”,“b”,“c”,“d”]
样例输出： [ “ d ” , “ c ” , “ b ” , “ a ” ] [ “d”, “c”, “b”, “a”] [“d”,“c”,“b”,“a”]
原题出处： LeetCode 344. 反转字符串

II、基础框架

c++ 版本给出的基础框架代码如下，要求不采用任何的辅助数组；
也就是空间复杂度要求 O ( 1 ) O(1) O(1)。

class Solution {
public:
    void reverseString(vector<char>& s) {
    }
};

III、思路分析

翻转的含义，相当于就是第一个字符和最后一个交换，第二个字符和最后第二个交换，… 以此类推，所以我们首先实现一个交换变量的函数 swap，然后再枚举第一个字符、第二个字符、第三个字符 …… 即可。
对于第 i i i 个字符，它的交换对象是第 l e n − i − 1 len-i-1 len−i−1 个字符 (其中 l e n len len 为字符串长度)。swap函数的实现，可以参考：《C语言入门100例》 - 例2 | 交换变量。

IV、时间复杂度

线性枚举的过程为 O ( n ) O(n) O(n)，交换变量为 O ( 1 ) O(1) O(1)，两个过程是相乘的关系，所以整个算法的时间复杂度为 O ( n ) O(n) O(n)。

IV、源码详解

class Solution {
public:
    void swap(char& a, char& b) {            // (1)
        char tmp = a;
        a = b;
        b = tmp;
    }
    void reverseString(vector<char>& s) {
        int len = s.size();
        for(int i = 0; i < len / 2; ++i) {   // (2)
            swap(s[i], s[len-i-1]);
        }
    }
};

( 1 ) (1) (1) 实现一个变量交换的函数，其中&是C++中的引用，在函数传参是经常用到，被称为：引用传递(pass-by-reference)，即被调函数的形式参数虽然也作为局部变量在堆栈中开辟了内存空间
，但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何操作都被处理成间接寻址，即通过堆栈中存放的地址访问主调函数中的实参变量。

简而言之，函数调用的参数，可以传引用，从而使得函数返回时，传参值的改变依旧生效。

( 2 ) (2) (2) 这一步是做的线性枚举，注意枚举范围是 [ 0 , l e n / 2 − 1 ] [0, len/2-1] [0,len/2−1]。

VI、本题小知识

函数调用的参数，可以传引用，从而使得函数返回时，传参值的改变依旧生效。

💤三、线性迭代

迭代就是一件事情重复的做，干的事情一样，只是参数的不同。一般配合的数据结构是【数组】或者【链表】，实现方式也是一个循环。比枚举稍微复杂一点。

I、例题描述

给定单链表的头节点 h e a d head head ，要求反转链表，并返回反转后的链表头。
样例输入： [ 1 , 2 , 3 , 4 ] [1,2,3,4] [1,2,3,4]
样例输出： [ 4 , 3 , 2 , 1 ] [4, 3, 2, 1] [4,3,2,1]
原题出处： LeetCode 206. 反转链表

II、基础框架

c++ 版本给出的基础框架代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    }
};

这里引入了一种数据结构链表 ListNode；
成员有两个：数据域val和指针域next。
返回的是链表头结点；

III、思路分析

这个问题，我们可以采用头插法，即每次拿出第 2 个节点插到头部，拿出第 3 个节点插到头部，拿出第 4 个节点插到头部，… 拿出最后一个节点插到头部。
于是整个过程可以分为两个步骤：删除第 i i i 个节点，将它放到头部，反复迭代 i i i 即可。
如图所示：
我们发现，图中的蓝色指针永远固定在最开始的链表头结点上，那么可以以它为契机，每次删除它的next，并且插到最新的头结点前面，不断改变头结点head的指向，迭代 n − 1 n-1 n−1 次就能得到答案了。

IV、时间复杂度

每个结点只会被访问一次，执行一次头插操作，总共 n n n 个节点的情况下，时间复杂度 O ( n ) O(n) O(n)。

V、源码详解

class Solution {
    ListNode *removeNextAndReturn(ListNode* now) {                 // (1) 
        if(now == nullptr || now->next == nullptr) {
            return nullptr;                                        // (2) 
        }
        ListNode *retNode = now->next;                             // (3) 
        now->next = now->next->next;                               // (4) 
        return retNode;
    }
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *doRemoveNode = head;                             // (5) 
        while(doRemoveNode) {                                      // (6) 
            ListNode *newHead = removeNextAndReturn(doRemoveNode); // (7) 
            if(newHead) {                                          // (8) 
                newHead->next = head;                              
                head = newHead;                
            }else {
                break;                                             // (9) 
            }
        }
        return head;
    }
};

( 1 ) (1) (1) ListNode *removeNextAndReturn(ListNode* now)函数的作用是删除now的next节点，并且返回；
( 2 ) (2) (2) 本身为空或者下一个节点为空，返回空；
( 3 ) (3) (3) 将需要删除的节点缓存起来，供后续返回；
( 4 ) (4) (4) 执行删除 now->next 的操作；
( 5 ) (5) (5) doRemoveNode指向的下一个节点是将要被删除的节点，所以doRemoveNode需要被缓存起来，不然都不知道怎么进行删除；
( 6 ) (6) (6) 没有需要删除的节点了就结束迭代；
( 7 ) (7) (7) 删除 doRemoveNode 的下一个节点并返回被删除的节点；
( 8 ) (8) (8) 如果有被删除的节点，则插入头部；
( 9 ) (9) (9) 如果没有，则跳出迭代。

VI、本题小知识

复杂问题简单化的最好办法就是将问题拆细，比如这个问题中，将一个节点取出来插到头部这件事情可以分为两步：
1）删除给定节点；
2）将删除的节点插入头部；

🥂四、二分枚举

能用二分枚举的问题，一定可以用线性枚举来实现，只是时间上的差别，二分枚举的时间复杂度一般为对数级，效率上会高不少。同时，实现难度也会略微有所上升。我们通过平时开发时遇到的常见问题来举个例子。

I、例题描述

软件开发的时候，会有版本的概念。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n n n 个版本 [ 1 , 2 , . . . , n ] [1, 2, ..., n] [1,2,...,n]，你想找出导致之后所有版本出错的第一个错误的版本。可以通过调用bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。应该尽量减少对调用 API 的次数。
样例输入： 5 5 5 和 b a d = 4 bad = 4 bad=4
样例输出： 4 4 4
原题出处： LeetCode 278. 第一个错误的版本

II、基础框架

c++ 版本给出的基础框架代码如下，其中bool isBadVersion(int version)是供你调用的 API，也就是当你调用这个 API 时，如果version是错误的，则返回true；否则，返回false；

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
    }
};

III、思路分析

由题意可得，我们调用它提供的 API 时，返回值分布如下：
000...000111...111 000...000111...111 000...000111...111
其中 0 代表false，1 代表true；也就是一旦出现 1，就再也不会出现 0 了。
所以基于这思路，我们可以二分位置；

归纳总结为 2 种情况，如下：
1）当前二分到的位置 m i d mid mid，给出的版本是错误，那么从当前位置以后的版本不需要再检测了（因为一定也是错误的），并且我们可以肯定，出错的位置一定在 [ l , m i d ] [l, mid] [l,mid]；并且 m i d mid mid 是一个可行解，记录下来；
2）当前二分到的位置 m i d mid mid，给出的版本是正确，则出错位置可能在 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]；

IV、时间复杂度

由于每次都是将区间折半，所以时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n)。

V、源码详解

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        long long l = 1, r = n;             // (1)
        long long ans = (long long)n + 1;
        while(l <= r) {
            long long mid = (l + r) / 2;
            if( isBadVersion(mid) ) {       
                ans = mid;                  // (2)
                r = mid - 1;
            }else {
                l = mid + 1;                // (3)
            }
        }
        return ans;
    }
};

( 1 ) (1) (1) 需要这里，这里两个区间相加可能超过 int，所以需要采用 64 位整型long long；
( 2 ) (2) (2) 找到错误版本的嫌疑区间 [ l , m i d ] [l, mid] [l,mid]，并且 m i d mid mid 是确定的候选嫌疑位置；
( 3 ) (3) (3) 错误版本不可能落在 [ l , m i d ] [l, mid] [l,mid]，所以可能在 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]，需要继续二分迭代；

VI、本题小知识

二分时，如果区间范围过大，int难以招架时，需要动用long long；

🥢五、双指针

双指针的概念就是对于一个线性表，通过两个变量的游走，来逐步解决问题。

1、来回跳跃

I、例题描述

给定一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
样例输入： n u m s = [ − 4 , − 1 , 0 , 3 , 9 ] nums = [-4,-1,0,3,9] nums=[−4,−1,0,3,9]
样例输出： [ 0 , 1 , 9 , 16 , 81 ] [0,1,9,16,81] [0,1,9,16,81]
原题出处： LeetCode 977. 有序数组的平方

II、基础框架

c++ 版本给出的基础框架代码如下，要求返回一个 vector<int>类型的数据；

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
    }
};

III、思路分析

首先，如果所有的数都是非负整数，那么直接按照原顺序，对数字平方塞入新的数组就是答案了。
否则，需要找到负数中，下标最大的，令它为 i i i，然后定义令一个指针 j = i + 1 j = i + 1 j=i+1。不断比较 i i i 和 j j j 对应的数的平方的大小关系，然后选择小的那个塞入新的数组，并且更新指针的位置。直到两个指针都到数组边缘时，运算完毕。

IV、时间复杂度

两个指针只会往一个方向遍历，最多遍历一次，所以时间复杂度为 O ( n ) O(n) O(n)。

V、源码详解

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector <int> ans;                             // (1)
        if (nums.size() == 0) {                       // (2)
            return ans;
        }
        else if(nums[0] >= 0) {
            for(int i = 0; i < nums.size(); ++i) {    // (3)
                ans.push_back(nums[i] * nums[i]);
            }
        }
        else {
            int i, j;
            for(int p = nums.size()-1; p >= 0; --p) {
                if(nums[p] < 0) {
                    i = p;
                    break;                            // (4)
                }
            }
            j = i + 1;                                // (5)

            while(i >= 0 || j < nums.size()) {        // (6)
                if(i < 0) {                           // (7)
                    ans.push_back(nums[j] * nums[j]);
                    ++j;
                }else if(j >= nums.size()) {          // (8)
                    ans.push_back(nums[i] * nums[i]);
                    --i;
                }else {
                    int i2 = nums[i] * nums[i];
                    int j2 = nums[j] * nums[j];

                    if(i2 < j2) {                     // (9)
                        ans.push_back(i2);
                        --i;
                    }else {
                        ans.push_back(j2);
                        ++j;
                    }
                }
            }
        }
        return ans;

    }
};

( 1 ) (1) (1) ans为结果数组，用来存储最终答案；
( 2 ) (2) (2) 如果给定数组长度为 0，则直接返回空数组；
( 3 ) (3) (3) 给定数组所有元素都为非负整数时，直接有序的生成新的数组，数组元素为原数组元素的平方；
( 4 ) (4) (4) 找到负数中，下标最大的数，记为 i i i；
( 5 ) (5) (5) 初始化指针 j = i + 1 j = i + 1 j=i+1；
( 6 ) (6) (6) 开始对两个指针进行迭代枚举，结束条件是两个指针都碰到数组的边界；
( 7 ) (7) (7) 左指针退化，左边元素耗尽了；
( 8 ) (8) (8) 右指针退化，右边元素耗尽了；
( 9 ) (9) (9) 左右元素都在，需要选择小的那个先进结果数组，然后向外扩展指针；

VI、本题小知识

输入参数为数组时，如果要判断数组第一个元素的状态，记得对数组进行判空；

2、滑动窗口

a、无重复覆盖

I、例题描述

给定一个长度为 n ( 1 ≤ n ≤ 1 0 7 ) n (1 \le n \le 10^7) n(1≤n≤107) 的字符串 s s s，求一个最长的满足所有字符不重复的子串的长度。
样例输入：" a b c a b c b b g abcabcbbg abcabcbbg"
样例输出： 3 3 3
原题出处： LeetCode 3. 无重复字符的最长子串

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    }
};

其中 string是 C++ 的 STL 中的模板类，可以用来做字符串的各种操作；

III、思路分析

我们考虑一个子串以 s i s_i si 为左端点， s j s_j sj 为右端点，且 s [ i : j − 1 ] s[i:j-1] s[i:j−1] 中不存在重复字符， s [ i : j ] s[i:j] s[i:j] 中存在重复字符（换言之， s j s_j sj 和 s [ i : j − 1 ] s[i:j-1] s[i:j−1] 中某个字符相同）。如图所示：
那么我们没必要再去检测 s [ i : j + 1 ] s[i:j+1] s[i:j+1]， s [ i : j + 2 ] s[i:j+2] s[i:j+2]， s [ i : n − 1 ] s[i:n-1] s[i:n−1] 这几个字符串的合法性，因为当前情况 s [ i : j ] s[i:j] s[i:j] 是非法的，而这些字符串是完全包含 s [ i : j ] s[i:j] s[i:j] 的，所以它们必然也是不合法的。
那么我们可以把枚举的左端点自增，即： i = i + 1 i = i +1 i=i+1，这时，按照朴素算法的实现，右端点需要重置，即 j = i j = i j=i，实际上这里的右端点可以不动。
可以这么考虑，由于 s j s_j sj 这个字符和 s [ i : j − 1 ] s[i:j-1] s[i:j−1] 中的字符产生了重复，假设这个重复的字符的下标为 k k k，那么 i i i 必须满足 i > k i \gt k i>k，换言之， i i i 可以一直自增，直到 i = k + 1 i = k+1 i=k+1，如图所示：
这个问题是双指针问题的原题，详细的算法可以参考：夜深人静写算法（二十八）- 尺取法。

IV、时间复杂度

两个指针都只会递增各一次，所以时间复杂度为 O ( n ) O(n) O(n)。

V、源码详解

class Solution {
    int hash[257];

public:
    int lengthOfLongestSubstring(string s) {
        memset(hash, 0, sizeof(hash));
        int maxLen = 0;
        int i = 0, j = -1;             // (1)
        int len = s.length();          // (2)
        while(j++ < len - 1) {
            ++hash[ s[j] ];            // (3)
            while(hash[ s[j] ] > 1) {  // (4)
                --hash[ s[i] ];        // (5)
                ++i;
            }
            if(j - i + 1 > maxLen) {   // (6)
                maxLen = j - i + 1;
            }
        }
        return maxLen;
    }
};

( 1 ) (1) (1) 代表一开始是空串；
( 2 ) (2) (2) 之所以要这么做，是因为s.length()是无符号整型，当 j == -1的情况为无符号整型的最大值，永远都无法进入下面的while(j++ < len - 1)这个循环；
( 3 ) (3) (3) 尝试向右移动右指针；
( 4 ) (4) (4) 合法性判定：所有字符个数不超过1；
( 5 ) (5) (5) 尝试向右移动左指针；
( 6 ) (6) (6) 更新最大合法长度；

VI、本题小知识

无符号整型在进行判断的时候，如果赋值为 -1，就有可能导致变成整数最大值导致逻辑错误；

b、最小覆盖

I、例题描述

给你一个字符串 s s s 、一个字符串 t t t 。返回 s s s 中涵盖 t t t 所有字符的最小子串。如果 s s s 中不存在涵盖 t t t 所有字符的子串，则返回空字符串 ""。对于 t t t 中重复字符，寻找的子字符串中该字符数量必须不少于 t t t 中该字符数量。如果 s s s 中存在这样的子串，我们保证它是唯一的答案。两个字符串的长度都不大于 1 0 5 10^5 105。
样例输入： s = “AOBECODEBAJC”, t = “ABC”
样例输出： “BAJC”
原题出处： LeetCode 76. 最小覆盖子串

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    string minWindow(string s, string t) {
    }
};

其中 string是 c++ 的 STL 中的模板类，可以用来做字符串的各种操作；

III、思路分析

这是一个经典的双指针问题，左指针 i i i 和右指针 j j j 下标范围内的字符串就是我们要求的子串，通过主指针 j j j 的右移，带动辅助指针 i i i 的右移，每个指针最多右移 n n n 次，如图所示：
详细的算法实现可以参考：夜深人静写算法（二十八）- 尺取法。

IV、时间复杂度

两个指针都只会递增各一次，所以时间复杂度为 O ( n ) O(n) O(n)。

V、源码详解

class Solution {
    int hash[256];
public:
    string minWindow(string s, string t) {
        memset(hash, 0, sizeof(hash));          // (1)
        int cnt = 0, needCnt = 0;               // (2)
        for(int i = 0; i < t.length(); ++i) {
            if(!hash[ t[i] ]) {
                ++needCnt;
            }
            ++ hash[ t[i] ];
        }
        int i = 0, j = -1;                      // (3)
        int l = 0, r = -1, ans = 1000000;       // (4)
        int size = s.length();
        
        while(j < size - 1) {
            ++j;                                // (5)
            if(--hash[ s[j] ] == 0) {
                ++cnt;
            }
            while(cnt == needCnt) {
                if(j - i + 1 < ans) {           // (6)
                    ans = j - i + 1;
                    l = i;
                    r = j;
                }
                if( ++hash[ s[i] ] > 0 ) {      // (7)
                    --cnt;
                }
                ++i;
            }
        }
        string ret;
        for(int i = l; i <= r; ++i) {
            ret.push_back(s[i]);
        }
        return ret;
    }
};

( 1 ) (1) (1) 利用一个哈希数组hash[]来标记字符串 t t t 中每个字符出现的次数；
( 2 ) (2) (2) cnt代表要取的 子字符串 中某一类字符的出现次数；needCnt代表字符串 t t t 中不同字符的出现次数；
( 3 ) (3) (3) i和j代表在字符串 s s s 上的两个双指针，初始化为空串，所以需要保证j - i + 1 == 0；
( 4 ) (4) (4) l和r代表 子字符串 的左右下标，ans的值恒等于 j - i + 1；
( 5 ) (5) (5) 每次迭代循环移动右指针j，并且执行--hash[ s[j] ]，一旦出现hash[ s[j] ] == 0，表示当前的 子字符串 s [ i : j ] s[i:j] s[i:j] 中已经完全包含了字符串 t t t 中的 s [ j ] s[j] s[j] 字符，所以执行 cnt自增；
( 6 ) (6) (6) 当cnt == needCnt时，通过 s [ i : j ] s[i:j] s[i:j] 是一个可行解，记录下标到l和r；
( 7 ) (7) (7) 移动左指针j，并且继续判断是否满足题意；

VI、本题小知识

无符号整型在进行判断的时候，如果赋值为 -1，就有可能导致变成整数最大值导致逻辑错误；

🍴六、坐标转换

坐标转换是比较常用的数学知识，一般用在一维转二维，二维转一维上。

I、例题描述

给出一个由二维数组表示的矩阵，以及两个正整数 r r r 和 c c c ，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数重构的操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
样例输入： n u m s = [ [ 1 , 2 ] , [ 3 , 4 ] ] , r = 1 , c = 4 nums = [[1,2],[3,4]], r = 1, c = 4 nums=[[1,2],[3,4]],r=1,c=4
样例输出： [ [ 1 , 2 , 3 , 4 ] ] [[1,2,3,4]] [[1,2,3,4]]
原题出处： LeetCode 566. 重塑矩阵

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
    }
};

输入数组参数类型是vector<vector<int>>&，代表的是一个引用类型的二维数组，按照题目要求，需要返回一个二维数组；

III、思路分析

首先，原矩阵的个数统计出来，和给出的参数的乘积 r × c r \times c r×c 比较，不相等则输出原矩阵。
否则，我们来看个图：
可以将原先的二维矩阵通过行遍历转换成一维的，然后再根据 r r r 和 c c c，每 r r r 个作为新矩阵的行，进行重新填充。
对于一个 n × m n \times m n×m 的矩阵，我们可以从左往右，从上往下进行编号，令一维编号为 i d id id，
二维转一维：
i d = r × m + c id = r \times m + c id=r×m+c
一维转二维：
r = ⌊ i d m ⌋ c = i d m o d m r = \lfloor \frac {id} m \rfloor \\ c = {id} \ mod \ m r=⌊mid⌋c=id mod m

IV、时间复杂度

时间复杂度为 O ( n m ) O(nm) O(nm)。

V、源码详解

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        vector<vector<int>> ans;
        int n = mat.size();                        // (1)
        int m = mat[0].size();                     // (2)
        if(n*m != r*c) {
            return mat;
        }
        for(int i = 0; i < r; ++i) {
            vector <int> v;
            for(int j = 0; j < c; ++j) {
                int id = i * c + j;                // (3)
                v.push_back(mat[id / m][id % m]);  // (4)
            }
            ans.push_back(v);                      // (5)
        }
        return ans;
    }
};

( 1 ) (1) (1) 获取矩阵的行 n n n；
( 2 ) (2) (2) 获取矩阵的列 m m m；
( 3 ) (3) (3) id = i * c + j代表原矩阵转换成一维线性数组以后的编号；
( 4 ) (4) (4) 坐标的反向转换，从一维重新转换成二维；
( 5 ) (5) (5) 将一维向量塞到二维向量中。

VI、本题小知识

可以用除法和取模来实现两个分量的坐标转换。

🅱七、位运算

位运算可以理解成对二进制数字上的每一个位进行操作的运算。
位运算分为布尔位运算符和移位位运算符。
布尔位运算符又分为位与(&)、位或(|)、异或(^)、按位取反(~)；移位位运算符分为左移(<<) 和右移(>>)。
如图所示：
位运算的特点是语句短，但是可以干大事！

【例题7】给出一个整数，现在要求将这个整数转换成二进制以后，将末尾连续的1都变成0，输出改变后的数（以十进制输出即可）。

我们知道，这个数的二进制表示形式一定是：
. . . 0 11...11 ⏟ k ...0\underbrace{11...11}_{\rm k} ...0k 11...11
如果，我们把这个二进制数加上1，得到的就是：
. . . 1 00...00 ⏟ k ...1\underbrace{00...00}_{\rm k} ...1k 00...00
我们把这两个数进行位与运算，得到：
. . . 0 00...00 ⏟ k ...0\underbrace{00...00}_{\rm k} ...0k 00...00
所以，你学会了吗？代码如下：

x &= x - 1;

【例题8】给定一个整数 x x x，将它低位连续的 0 都变成 1。

假设这个整数低位连续有 k k k 个零，二进制表示如下：
. . . 1 00...00 ⏟ k ...1\underbrace{00...00}_{\rm k} ...1k 00...00
那么，如果我们对它进行减一操作，得到的二进制数就是：
. . . 0 11...11 ⏟ k ...0\underbrace{11...11}_{\rm k} ...0k 11...11
我们发现，只要对这两个数进行位或，就能得到：
. . . 1 11...11 ⏟ k ...1\underbrace{11...11}_{\rm k} ...1k 11...11
也正是题目所求，所以代码实现如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | (x-1) );    // (1)
    return 0;
}

( 1 ) (1) (1) x | (x-1)就是题目所求的 “低位连续零变一” 。

【例题9】给定两个数 a a a 和 b b b，用异或运算交换它们的值。

这个是比较老的面试题了，直接给出代码：

#include <stdio.h>
int main() {
    int a, b;
	while (scanf("%d %d", &a, &b) != EOF) {
	    a = a ^ b;   // (1)
	    b = a ^ b;   // (2)
	    a = a ^ b;   // (3)
	    printf("%d %d\n", a, b);
	}
	return 0;
}

我们直接来看 ( 1 ) (1) (1) 和 ( 2 ) (2) (2) 这两句话，相当于b等于a ^ b ^ b，根据异或的几个性质，我们知道，这时候的b的值已经变成原先a的值了。
而再来看第 ( 3 ) (3) (3) 句话，相当于a等于a ^ b ^ a，还是根据异或的几个性质，这时候，a的值已经变成了原先b的值。
从而实现了变量a和b的交换。

对于 x x x 模上一个 2 的次幂的数 y y y，我们可以转换成位与上 2 y − 1 2^y-1 2y−1。
即在数学上的：
x m o d 2 y x \ mod \ 2^y x mod 2y
在计算机中就可以用一行代码表示：x & ((1 << y) - 1)。

♈八、递推

递推也是数学中非常常见的问题，一般递推问题在数学中有个名词叫 递推公式。我们可以通过递推公式，加上计算机的循环来实现最后的结果。最经典的当属斐波那契数列了。

1、一维递推

I、例题描述

斐波那契数，通常用 F ( n ) F(n) F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F ( 0 ) = 0 ， F ( 1 ) = 1 F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(0) = 0，F(1) = 1 \\ F(n) = F(n - 1) + F(n - 2) F(0)=0，F(1)=1F(n)=F(n−1)+F(n−2) 给定 n n n ，求 F ( n ) F(n) F(n)。
样例输入： 4
样例输出： 5
原题出处： LeetCode 509. 斐波那契数

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    int fib(int n) {
    }
};

III、思路分析

直接一层循环枚举，递推计算即可。

IV、时间复杂度

时间复杂度为一个for循环的次数，即 O ( n ) O(n) O(n)。

V、源码详解

class Solution {
    int f[1000];                      // (1)
public:
    int fib(int n) {
        f[0] = 0;                     // (2)
        f[1] = 1;
        for(int i = 2; i <= n; ++i) { // (3)
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];                  // (4)
    }
};

( 1 ) (1) (1) 用一个数组来缓存结果；
( 2 ) (2) (2) 初始化 n = 0 , 1 n=0,1 n=0,1 的情况；
( 3 ) (3) (3) 递推求解；
( 4 ) (4) (4) 返回最后的结果；

VI、本题小知识

数学上的递推问题，在程序中不需要计算出通项公式，可以直接通过一个循环来搞定！

2、二维递推

I、例题描述

给定一个非负整数 n u m R o w s numRows numRows，生成杨辉三角的前 n u m R o w s numRows numRows 行。
在杨辉三角中，每个数是它 左上方 和 右上方 的数的和。
样例输入： 5
样例输出：
原题出处： LeetCode 118. 杨辉三角

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
    }
};

可以理解成返回的是一个二维数组。

III、思路分析

根据杨辉三角的定义，我们可以简单将上面的图进行一个变形，得到：

20210717061706355.gif#pic_center

于是，我们可以得出以下结论：
1）杨辉三角的所有数可以存储在一个二维数组中，行代表第一维，列代表第二维度；
2）第 i i i 行的元素个数为 i i i 个；
3）第 i i i 行第 j j j 列的元素满足公式： c [ i ] [ j ] = { 1 i = 0 c [ i − 1 ] [ j − 1 ] + c [ i − 1 ] [ j ] o t h e r w i s e c[i][j] = c[i][j]={1c[i−1][j−1]+c[i−1][j]i=0otherwise

于是就可以两层循环枚举了。

IV、时间复杂度

两层循环嵌套，所以时间复杂度 O ( n 2 ) O(n^2) O(n2)。

V、源码详解

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for(int i = 0; i < numRows; ++i) {                        // (1)
            vector<int> v;
            for(int j = 0; j <= i; ++j) {                         // (2)
                if(j == 0 || j == i) {
                    v.push_back(1);                               // (3)
                }else { 
                    v.push_back( ans[i-1][j-1] + ans[i-1][j] );   // (4)
                }
            }
            ans.push_back(v);
        }
        return ans;
    }
};

( 1 ) (1) (1) 第一层循环枚举行；
( 2 ) (2) (2) 第二层循环枚举列，列的上限为行编号；
( 3 ) (3) (3) 杨辉三角两边恒为 1；
( 4 ) (4) (4) 杨辉三角中间的数，为 c[i-1][j-1] + c[i-1][j]；

VI、本题小知识

组合数的递推求解，又被称为杨辉三角。

💥九、递归

递归说白了就是函数自己调用自己，只是调用参数的不同。

1、分治问题

I、例题描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。需要将它们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
样例输入：

样例输出：
原题出处： LeetCode 617. 合并二叉树

II、基础框架

c++ 版本给出的基础框架代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    }
};

TreeNode代表一个二叉树节点，有数据域和指针域两部分组成，数据域为val，指针域为left和right，分别指向左右两个子树的根节点；
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2)这个接口，传参root1和root2为两个需要合并的二叉树的根节点，返回的是合并后的二叉树的根节点。

III、思路分析

遇到二叉树问题，基本第一个思路就是递归。根据经验，来谈谈递归需要注意的点：
1）递归出口一定要考虑好，这个题的递归出口就是两棵树中任意一棵是空树的情况；
2）对于非递归出口，先处理根节点，再递归处理左子树和右子树。处理的过程中一定要清楚明白，处理的事情是什么，返回值是什么。这个题中处理的事情就是将两棵树的根节点合并，返回值就是合并后的树根。合并后的树根可以使用新申请的内存。
3）需要注意，千万不要返回栈上变量的地址，函数销毁的时候，栈变量的生命周期也就结束了。

IV、时间复杂度

每个节点只会访问一次，时间复杂度为 O ( n ) O(n) O(n)。

V、源码详解

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        TreeNode *p = new TreeNode();                           // (1)
        if(root1 == nullptr) {
            return root2;                                       // (2)
        }else if(root2 == nullptr) {
            return root1;                                       // (3)
        }else {
            p->val = root1->val + root2->val;                   // (4)
            p->left = mergeTrees(root1->left, root2->left);     // (5)
            p->right = mergeTrees(root1->right, root2->right);  // (6)
        }
        return p;
    }
};

( 1 ) (1) (1) 必须在堆上申请内存，否则函数返回时就销毁了；这里的p为合并后的树的根节点指针；
( 2 ) (2) (2) 如果root1为空树，则直接返回root2；
( 3 ) (3) (3) 如果root2为空树，则直接返回root1；
( 4 ) (4) (4) 当两者都不为空树时，将两棵树的根节点的值相加，赋值给合并后的树根的数据域val；
( 5 ) (5) (5) 递归合并左子树；
( 6 ) (6) (6) 递归合并右子树；

VI、本题小知识

递归问题，千万不要返回栈上变量的地址（从堆上申请），函数销毁的时候，栈变量的生命周期也就结束了。

2、连通块问题

I、例题描述

给定一个包含了一些 0 和 1 的非空二维数组 g r i d grid grid 。一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 g r i d grid grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。
样例输入1： [ [ 1 , 0 , 1 ] , [ 1 , 1 , 1 ] , [ 0 , 0 , 1 ] ] [[1,0,1],[1,1,1],[0,0,1]] [[1,0,1],[1,1,1],[0,0,1]]
样例输出1： 6 6 6

样例输入2： [ [ 1 , 0 , 1 ] , [ 0 , 1 , 0 ] , [ 0 , 0 , 1 ] ] [[1,0,1],[0,1,0],[0,0,1]] [[1,0,1],[0,1,0],[0,0,1]]
样例输出2： 1 1 1

原题出处： LeetCode 695. 岛屿的最大面积

II、基础框架

c++ 版本给出的基础框架代码如下，定义一个函数maxAreaOfIsland，函数的参数是一个vector的嵌套，代表的是一个二维数组；
vector<vector<int>>可以理解成vector<T>，其中T代表vector的元素，并且这个元素是另一个vector<int>。当然，可以嵌套的实现三维数组，甚至更高维的数组。

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    }
};

III、思路分析

对 g r i d grid grid 中的每个 1 抽象成一个节点，且都有一个唯一编号。两个水平或者垂直方向相邻且都为 1，则在这两个节点之间连接一条无向边。举个例子：
[ 1 0 0 1 1 1 0 1 0 1 1 1 ] \left[ \right] ⎣⎡110011001111⎦⎤
先将每个 1 的位置都分配一个编号，假设行号为 i i i，列号为 j j j，则它的编号就是 i × 4 + j i \times 4 + j i×4+j，其中 4 4 4 代表总共有多少列。如下：
[ 0 E E 3 4 5 E 7 E 9 10 11 ] \left[ \right] ⎣⎡04EE59EE103711⎦⎤
E E E 的含义是 Empty 的意思，可以用一个额外的编号（不和其它现有编号冲突）表示，比如 -1。
所以，它其实应该是这样一个图：
这样，我们就可以转换成用深度优先搜索来求连通块问题了。
关于深度优先搜索的更深入内容，可以参考这篇文章：夜深人静写算法（一）- 搜索入门。

IV、时间复杂度

由于有哈希数组在，所以 g r i d grid grid 的每个元素最多被访问一次，如果长 n n n 宽为 m m m 的 g r i d grid grid，时间复杂度为 O ( n m ) O(nm) O(nm)。

V、源码详解

const int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };           // (1)
int bHash[100][100];                                                  // (2)
int n, m;                                                             // (3)

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int &count, int x, int y) {   // (4)
        if(x < 0 || y < 0 || x >= n || y >= m) {
            return ;                                                  // (5)
        }
        if(!grid[x][y]) {
            return ;                                                  // (6)
        }

        if(bHash[x][y]) {
            return;                                                   // (7)
        }
        bHash[x][y] = 1;
        ++count;

        for(int i = 0; i < 4; ++i) {
            dfs(grid, count, x + dir[i][0], y + dir[i][1]);           // (8)
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        memset(bHash, 0, sizeof(bHash));

        int count = 0, maxv = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(grid[i][j] && !bHash[i][j]) {                      // (9)
                        count = 0;
                        dfs(grid, count, i, j);
                        maxv = max(maxv, count);                      // (10)
                    }
                }
            }
        }
        return maxv;
    }
};

( 1 ) (1) (1) 代表四个方向的全局向量；
( 2 ) (2) (2) 二维的哈希数组，用来标记一个位置有没有被访问过；
( 3 ) (3) (3) 全局缓存 g r i d grid grid 的宽和高；
( 4 ) (4) (4) 用于对全局进行搜素的递归函数，grid作为引用传参提高效率，count作为引用传参是当全局变量来用的，x，y代表的是当前枚举到的行和列。
( 5 ) (5) (5) 如果遇到搜索到边界的情况，终止搜索；
( 6 ) (6) (6) 如果遇到不是岛屿的情况，终止搜索；
( 7 ) (7) (7) 如果遇到已经搜索过的岛屿，终止搜索；否则，标记(x,y)被搜索过，且计数器count自增。
( 8 ) (8) (8) 继续枚举四方向的下一个位置；
( 9 ) (9) (9) grid的每个位置未被访问过（!bHash[i][j]）的岛屿（grid[i][j]）都必须枚举到；
( 10 ) (10) (10) 取最大的连通块，max为系统库函数；

VI、本题小知识

利用深度优先搜索，可以用来求图的连通块问题。

3、全排列枚举

I、例题描述

给定一个 不含重复数字 的长度小于 7 的数组 n u m s nums nums ，返回其所有可能的全排列。
样例输入： n u m s = [ 1 , 2 , 3 ] nums = [1,2,3] nums=[1,2,3]
样例输出： [ [ 1 , 2 , 3 ] , [ 1 , 3 , 2 ] , [ 2 , 1 , 3 ] , [ 2 , 3 , 1 ] , [ 3 , 1 , 2 ] , [ 3 , 2 , 1 ] ] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
原题出处： LeetCode 46. 全排列

II、基础框架

c++ 版本给出的基础框架代码如下:

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
    }
};

定义一个函数permute，函数的参数是一个vector，代表的是一个数组；
返回值是vector<vector<int>>可以理解成vector<T>，其中T代表vector的元素，并且这个元素是另一个vector<int>。当然，可以嵌套的实现三维数组，甚至更高维的数组。

III、思路分析

全排列的种数是 n ! n! n!，这是最典型的深搜问题。我们可以把 n n n 个数两两建立无向边（即任意两个结点之间都有边，也就是一个 n n n 个结点的完全图），然后对每个点作为起点，分别做一次深度优先搜索，当所有点都已经标记时，输出当前的搜索路径，就是其中一个排列；
这里需要注意的是，回溯的时候需要将原先标记的点的标记取消，否则只能输出一个排列。
如下图，代表的是3个数的图表示：
3个数的全排列的深度优先搜索空间树如下图所示：
关于深度优先搜索的更深入内容，可以参考这篇文章：夜深人静写算法（一）- 搜索入门。

IV、时间复杂度

由于每次访问后会将标记过的节点标记回来，所以时间复杂度就是排列数，即 O ( n ! ) O(n!) O(n!)。

V、源码详解

class Solution {
    int hash[6];

    void dfs(int dep, int maxdep, vector<int>& nums, vector<vector<int>>& ans, vector<int>& st) {                                                            // (1)
        if(dep == maxdep) {
            ans.push_back( st );                             // (2)
            return ;
        }

        for(int i = 0; i < maxdep; ++i) {                    
            if(!hash[i]) {                                   // (3)
                hash[i] = 1;                                
                st.push_back(  nums[i] );                   
                dfs(dep + 1, maxdep, nums, ans, st);         // (4)
                st.pop_back();                               // (5)
                hash[i] = 0;                                 // (6)
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;            
        memset(hash, 0, sizeof(hash));        
        vector<int> st; 
        dfs(0, nums.size(), nums, ans, st);     
        return ans;
    }
};

( 1 ) (1) (1) dep代表本地递归访问第几个节点，maxdep代表递归的层数，vector<int>& nums则代表原始输入数组，vector<vector<int>>& ans代表结果数组，vector<int>& st代表存储当前搜索结果的栈；
( 2 ) (2) (2) dep == maxdep代表一次全排列访问，这时候得到一个可行解，放入结果数组中；
( 3 ) (3) (3) 如果节点 i i i 未访问，则将第 i i i 个节点的值塞入搜索结果栈，并且用hash数组标记已访问；
( 4 ) (4) (4) 继续递归调用下一层；
( 5 ) (5) (5) 将栈顶元素弹出，代表本次访问的回溯；
( 6 ) (6) (6) 取消数组标记；

VI、本题小知识

利用深度优先搜索，可以用来求全排列问题。

🚕十、简单动态规划

1、线性DP

1）递推型

I、例题描述

数组的每个下标作为一个阶梯，第 i i i 个阶梯对应着一个非负数的体力花费值 c o s t [ i ] cost[i] cost[i]（下标从 0 开始）。每当爬上一个阶梯，都要花费对应的体力值，一旦支付了相应的体力值，就可以选择 向上爬一个阶梯 或者 爬两个阶梯。求找出达到楼层顶部的最低花费。在开始时，可以选择从下标为 0 或 1 的元素作为初始阶梯。
样例输入： c o s t = [ 1 , 99 , 1 , 1 , 1 , 99 , 1 , 1 , 99 , 1 ] cost = [1, 99, 1, 1, 1, 99, 1, 1, 99, 1] cost=[1,99,1,1,1,99,1,1,99,1]
样例输出： 6 6 6
如图所以，蓝色的代表消耗为 1 的楼梯，红色的代表消耗 99 的楼梯。

原题出处： LeetCode 746. 使用最小花费爬楼梯

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
    }
};

III、思路分析

令走到第 i i i 层的最小消耗为 f [ i ] f[i] f[i]
假设当前的位置在 i i i 层楼梯，那么只可能从 i − 1 i-1 i−1 层过来，或者 i − 2 i-2 i−2 层过来；
如果从 i − 1 i-1 i−1 层过来，则需要消耗体力值： f [ i − 1 ] + c o s t [ i − 1 ] f[i-1] + cost[i-1] f[i−1]+cost[i−1]；
如果从 i − 2 i-2 i−2 层过来，则需要消耗体力值： f [ i − 2 ] + c o s t [ i − 2 ] f[i-2] + cost[i-2] f[i−2]+cost[i−2]；
起点可以在第 0 或者第 1 层，于是有状态转移方程：
f [ i ] = { 0 i = 0 , 1 min ⁡ ( f [ i − 1 ] + c o s t [ i − 1 ] , f [ i − 2 ] + c o s t [ i − 2 ] ) i > 1 f[i] = f[i]={0min(f[i−1]+cost[i−1],f[i−2]+cost[i−2])i=0,1i>1

IV、时间复杂度

状态数： O ( n ) O(n) O(n)
状态转移： O ( 1 ) O(1) O(1)
时间复杂度： O ( n ) O(n) O(n)

V、源码详解

class Solution {
    int f[1100];                                                   // (1)
public:
    int minCostClimbingStairs(vector<int>& cost) {
        f[0] = 0, f[1] = 0;                                        // (2)
        for(int i = 2; i <= cost.size(); ++i) {
            f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);    // (3)
        }
        return f[cost.size()];
    }
};

( 1 ) (1) (1) 用f[i]代表到达第 i i i 层的消耗的最小体力值。
( 2 ) (2) (2) 初始化；
( 3 ) (3) (3) 状态转移；

VI、本题小知识

有没有发现，这个问题和斐波那契数列很像，只不过斐波那契数列是求和，这里是求最小值。

2）最大子段和

I、例题描述

给定一个整数数组 n u m s nums nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
样例输入： n u m s = [ − 2 , 1 , − 3 , 4 , − 1 , 2 , 1 , − 5 , − 7 ] nums = [-2,1,-3,4,-1,2,1,-5,-7] nums=[−2,1,−3,4,−1,2,1,−5,−7]
样例输出： 6 6 6，即 [ 4 , − 1 , 2 , 1 ] [4,-1,2,1] [4,−1,2,1]。
原题出处： LeetCode 53. 最大子序和

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    }
};

III、思路分析

由于要求的是连续的子数组，所以对于第 i i i 个元素，状态转移一定是从 i − 1 i-1 i−1 个元素转移过来的。

基于这一点，可以令 f [ i ] f[i] f[i] 表示以 i i i 号元素结尾的最大值。
那么很自然，这个最大值必然包含 n u m s [ i ] nums[i] nums[i] 这个元素，那么要不要包含 n u m s [ i − 1 ] , n u m s [ i − 2 ] , n u m s [ i − 3 ] , . . . , n u m s [ k ] nums[i-1],nums[i-2],nums[i-3],...,nums[k] nums[i−1],nums[i−2],nums[i−3],...,nums[k] 呢？其实就是看第 i − 1 i-1 i−1 号元素结尾的最大值是否大于零，也就是：当 f [ i − 1 ] ≤ 0 f[i-1] \le 0 f[i−1]≤0 时，则前 i − 1 i-1 i−1 个元素是没必要包含进来的。所以就有状态转移方程：
f [ i ] = { n u m s [ 0 ] i = 0 n u m s [ i ] f [ i − 1 ] ≤ 0 n u m s [ i ] + f [ i − 1 ] f [ i − 1 ] > 0 f[i] = f[i]=⎩⎪⎨⎪⎧nums[0]nums[i]nums[i]+f[i−1]i=0f[i−1]≤0f[i−1]>0
一层循环枚举后，取 m a x ( f [ i ] ) max(f[i]) max(f[i]) 就是答案了。

IV、时间复杂度

状态数： O ( n ) O(n) O(n)
状态转移： O ( 1 ) O(1) O(1)
时间复杂度： O ( n ) O(n) O(n)

V、源码详解

class Solution {
    int f[30010];
public:
    int maxSubArray(vector<int>& nums) {
        int maxValue = nums[0];
        f[0] = nums[0];                          // (1)
        for(int i = 1; i < nums.size(); ++i) {
            f[i] = nums[i];
            if(f[i-1] > 0) {
                f[i] += f[i-1];                  // (2)
            }
            maxValue = max(maxValue, f[i]);      // (3)
        }
        return maxValue;
    }
};

( 1 ) (1) (1) 初始值；
( 2 ) (2) (2) 状态转移；
( 3 ) (3) (3) 过程中取最大值；

VI、本题小知识

连续子数组问题，可以考虑前一个元素已经计算出来的状态进行下一个元素的求解。

3）最长递增子序列

更多有关最长递增子序列的内容，限于字数的关系的关系，不便再做展开，有兴趣的读者可以参考以下这篇文章：夜深人静写算法（二十）- 最长单调子序列。

2、序列匹配问题

1）正则表达式匹配

I、例题描述

给定一个 匹配字符串 s (只包含小写字母) 和一个 模式字符串 p (包含小写字母和两种额外字符：'.'和 '*')，要求实现一个支持 '.'和 '*'的正则表达式匹配（'*'前面保证有字符）。
'.'匹配任意单个字符
'*'匹配零个或多个前面的那一个元素

样例输入： s = "mississippi"、p = "mis*is*p*."
样例输出： false。
原题出处： LeetCode 10. 正则表达式匹配

II、基础框架

c++ 版本给出的基础框架代码如下：

class Solution {
public:
    bool isMatch(string str, string pattern) {
    }
};

str是匹配串；
pattern是模式串；

III、思路分析

这是个经典的 串匹配 问题，可以按照 最长公共子序列 的思路去解决。
令 f ( i , j ) f(i, j) f(i,j) 代表的是 匹配串前缀 s[0:i] 和 模式串前缀 p[0:j] 是否有匹配，只有两个值： 0 代表 不匹配， 1 代表匹配。

于是，对模式串进行分情况讨论：
1）当 p[j] 为.时，代表 s[i] 为任意字符时，它都能够匹配（没毛病吧？没毛病），所以问题就转化成了求 匹配串前缀 s[0:i-1] 和 模式串前缀 p[0:j-1] 是否有匹配的问题，也就是这种情况下 f ( i , j ) = f ( i − 1 , j − 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i−1,j−1)，如图1所示：

图1
2）当 p[j] 为 *时，由于 *前面保证有字符，所以拿到字符 p[j-1]，分情况讨论：
2.a）如果 p[j-1] 为 .时，可以匹配所有 s[0:i] 的后缀，这种情况下，只要 f ( k , j − 2 ) f(k, j-2) f(k,j−2) 为 1， f ( i , j ) f(i, j) f(i,j) 就为 1；其中 k ∈ [ 0 , i ] k \in [0, i] k∈[0,i]。如图2所示：

图2
2.b）如果 p[j-1] 非 .时，只有当 s[0:i] 的后缀字符全为 p[j-1] 时，才能去匹配 s[0:i] 的前缀，同样转化成 f ( k , j − 2 ) f(k, j-2) f(k,j−2) 的子问题。如图3所示：

图3
3）当 p[j] 为其他任意字符时，一旦 p[j] 和 s[i] 不匹配，就认为 f ( i , j ) = 0 f(i, j) = 0 f(i,j)=0，否则 f ( i , j ) = f ( i − 1 , j − 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i−1,j−1)，如图4所示：

图4

最后，这个问题可以采用记忆化搜索求解，并且需要考虑一些边界条件，边界条件可以参考代码实现中的讲解。
有关记忆化搜索的内容，可以参考以下这篇文章：夜深人静写算法（二十六）- 记忆化搜索。
有关最长公共子序列的内容，可以参考以下这篇文章：夜深人静写算法（二十一）- 最长公共子序列。

IV、时间复杂度

匹配串的长度为 n n n，模式串的长度为 m m m。
状态数： O ( n m ) O(nm) O(nm)
状态转移： O ( n ) O(n) O(n)
时间复杂度： O ( n 2 m ) O(n^2m) O(n2m)

V、源码详解

const int maxn = 110;
 
class Solution {
public:
    int dfs(int dp[maxn][maxn], string& str, string& pattern, int sidx, int pidx) {
        if(sidx == -1 && pidx == -1)                       // (1) 
            return 1;
        if(pidx == -1)                                     // (2) 
            return 0;
        if(sidx == -2) {                                   // (3)        
            return 0;
        }
        int &x = dp[sidx+1][pidx+1];                       // (4) 
        if(x != -1)
            return x;                                      // (5) 
        x = 0;                                             // (6) 
        if(pattern[pidx] == '.') {
            x |= dfs(dp, str, pattern, sidx-1, pidx-1);    // (7)  
        }else if(pattern[pidx] == '*') {
            if(pidx == 0) {
                x |= dfs(dp, str, pattern, sidx, pidx-1);
            }else {
                char c = pattern[pidx-1];
                x |= dfs(dp, str, pattern, sidx, pidx-2);  // (8) 
                for(int i = sidx; i >= 0; --i) {
                    if(c == '.' || c == str[i])  {         // (9) 
                        x |= dfs(dp, str, pattern, i - 1, pidx - 2);
                    }else {
                        break;
                    }
                }
            }
        }else {
            if(sidx >= 0 && pattern[pidx] == str[sidx])    // (10) 
                x |= dfs(dp, str, pattern, sidx-1, pidx-1);
            else                                           // (11)
                x  = 0;
        }
        return x;
    }
     
    bool isMatch(string str, string pattern) {
        int dp[maxn][maxn];
        int len = str.size();
        int plen = pattern.size();
        memset(dp, -1, sizeof(dp));
        int ans = dfs(dp, str, pattern, len-1, plen-1);
        return ans;
    }
};

( 1 ) (1) (1) 边界情况1：空匹配串 和 空模式串 的匹配，直接返回1；
( 2 ) (2) (2) 边界情况2：非空匹配串 和 空模式串 是无法匹配的，直接返回0；
( 3 ) (3) (3) 边界情况3：空匹配串 和 非空模式串 也是无法匹配的，直接返回0；
( 4 ) (4) (4) 记忆化的部分，避免 -1 数组下标越界，采用 +1 偏移；
( 5 ) (5) (5) 利用记忆化，已经计算出结果的，则直接返回；
( 6 ) (6) (6) 初始时，认为都不匹配；
( 7 ) (7) (7) .表示匹配任意单个字符，对应上文 1）的情况；
( 8 ) (8) (8) 让 c*去匹配空串，剩下的进行匹配；
( 9 ) (9) (9) 只要模式字符是.或者 匹配字符 和 模式字符 相等，都能够进行下一步匹配；对应上文 2）的情况；
( 10 ) (10) (10) 和 ( 11 ) (11) (11) 对应上文 3）的情况。

VI、本题小知识

两个串的模式匹配问题，可以采用动态规划求解，实现方式可以采用记忆化搜索，更加好理解。这题对于求职来说较难，如果在面试的遇到，那表明你运气不好哈（当然，不排除你是 ACM 大神！Good Luck！）。

2）最长公共子序列

限于篇幅，有关最长公共子序列的问题，可以参考：夜深人静写算法（二十一）- 最长公共子序列。

3）最短编辑距离

限于篇幅，有关最短编辑距离的问题，可以参考：夜深人静写算法（二十二）- 最小编辑距离。

3、背包问题

背包相关的所有问题，可以参考：夜深人静写算法（十九）- 背包总览。

4、记忆化搜索

记忆化相关问题，可以参考：夜深人静写算法（二十六）- 记忆化搜索。

❤️《十大算法入门》❤️(建议收藏)

💨一、排序

🥖二、线性枚举

💤三、线性迭代

🥂四、二分枚举

🥢五、双指针

1、来回跳跃

2、滑动窗口

a、无重复覆盖

b、最小覆盖

🍴六、坐标转换

🅱七、位运算

♈八、递推

1、一维递推

2、二维递推

💥九、递归

1、分治问题

2、连通块问题

3、全排列枚举

🚕十、简单动态规划

1、线性DP

1）递推型

2）最大子段和

3）最长递增子序列

2、序列匹配问题

1）正则表达式匹配

2）最长公共子序列

3）最短编辑距离

3、背包问题

4、记忆化搜索

Recommend

About Joyk