【C++】《剑指 Offer》高频算法题图文/代码全解析- 惊觉

一、丑数

给你一个整数 n ，请你找出并返回第 n 个丑数。

说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。

示例 1：

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

提示：

1 <= n <= 1690

解法一：优先级队列

我们可以确定，第一个丑数是1（题干给出）
后续每一个 “丑数”，一定是由前面的某个数和 2、3、5 相乘后的结果，并且它是最小的
由此，我们得到思路：直接将前面所有数字和 2、3、5 相乘得到的结果丢到优先级队列中，当前的 “丑数” 就是堆顶元素

class Solution {
public:
    using ull = unsigned long long;
    int nthUglyNumber(int n) {
        //丑数，是2或3或5的倍数
        if(n == 1){
            return 1;
        }
        priority_queue<ull, vector<ull>, greater<ull>> pq;
        pq.push(1);
        
        unordered_set<ull> hash;
        hash.insert(1);

        int ret = 0;
        for(int i = 2; i <= n; i++){
            int top = pq.top();
            pq.pop();
            if(!hash.count(top * 2L)){
                hash.insert(top * 2L);
                pq.push(top * 2L);
            }
            if(!hash.count(top * 3L)){
                hash.insert(top * 3L);
                pq.push(top * 3L);
            }
            if(!hash.count(top * 5L)){
                hash.insert(top * 5L);
                pq.push(top * 5L);
            }
            ret = pq.top();
        }
        return ret;
    }
};

解法二：动态规划

分析前面的优先级队列的解法，不难发现，空间上，堆中维护着很多压根不需要的结果；时间上，堆的维护也是一笔开销。

我们的核心思路是，当前丑数，一定是由前面某个数字和 2、3、5 相乘后的结果，并且这个结果为了满足递增连续一定是这些数里最小的（联想到状态转移）。那么我们可以采用动态规划的做法

确定第一个丑数是 1，作为 DP 起点
维护三个指针：p2、p3、p5，表示所指向位置乘上相应质因数
推到状态转移方程：对于 2，由 dp[p2] * 2 得到，那么后续第三个丑数，一定不可能是 dp[p2] * 2，但有可能是 dp[p2 + 1] * 2、dp[p3] * 2、dp[p5] * 5。简而言之，一个指针作为当前丑数的来源后，它必须往后挪动一位，才有可能是下一个的状态来源

class Solution {
public:
    using ull = unsigned long long;
    int nthUglyNumber(int n) {
        //每个数字，都可以从前面某个数字乘2、3、5得到
        vector<ull> dp(n + 1, 0);
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for(int i = 2; i <= n; i++){
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = min(num2, min(num3, num5));
            if(num2 == dp[i]) p2++;
            if(num3 == dp[i]) p3++;
            if(num5 == dp[i]) p5++;
        }
        return dp[n];
    }
};

二、设计机械累加器

请设计一个机械累加器，计算从 1、2… 一直累加到目标数值 target 的总和。注意这是一个只能进行加法操作的程序，不具备乘除、if-else、switch-case、for 循环、while 循环，及条件判断语句等高级功能。

示例 1：

输入: target = 5
输出: 15

示例 2：

输入: target = 7
输出: 28

提示：

1 <= target <= 10000

解法一：递归

不能用循环，自然的考虑到用递归代替循环；但是一般的递归过程中，会使用一个判断语句来判断递归是否应该结束，但是我们不能使用条件判断语句

考虑我们的行为，即：满足递归条件，后面的代码就不再执行。可以联想到语言中的行为：&& 和 || 的短路行为

当 target == 1 时，我们需要返回 1，所以我们不妨把前半个语句设置为 target > 1，不满足，说明已经触达了递归返回条件，操作符选用 &&；未触发，就继续递归

class Solution {
public:
    int mechanicalAccumulator(int target) {
        //1、2...target 智能进行加法操作
        target > 1 && (target += mechanicalAccumulator(target - 1));
        return target;
    }
};

三、望远镜中最高海拔

科技馆内有一台虚拟观景望远镜，它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 heights ，其中 heights[i] 表示对应位置的海拔高度。请找出并返回望远镜视野范围 limit 内，可以观测到的最高海拔值。

示例 1：

输入：heights = [14,2,27,-5,28,13,39], limit = 3
输出：[27,27,28,28,39]
解释：
滑动窗口的位置                最大值
---------------               -----
[14 2 27] -5 28 13 39          27
14 [2 27 -5] 28 13 39          27
14 2 [27 -5 28] 13 39          28
14 2 27 [-5 28 13] 39          28
14 2 27 -5 [28 13 39]          39

提示：

你可以假设输入总是有效的，在输入数组不为空的情况下：

1 <= limit <= heights.length
-10000 <= heights[i] <= 10000

解法一：暴力解法

这道题使用滑动窗口是确定的，每次移动窗口，都需要找当前窗口中最大的（可能会出现前一个窗口的最大的被移除窗口）。

难的不是如何解决，而是如何将维护窗口最大值的时间复杂度降到 O(1)

解法二：单调队列

窗口滑动的过程中，在一个状态下，我们只需要在意最大的；当滑入新的元素时，比新的元素小的元素都是没有意义的（因为我们放入结果的是当前窗口最大的），但是这个新的元素可能有意义，因为原来的最大元素一定会比新元素先滑出窗口，这是新的元素就可能是最大元素了
数据结构我们使用双端队列，来实现 O(1) 的头尾增删操作
双端队列我们维护成降序的；方便起见我们可以让窗口一开始从 “数组之外” 的位置开始：窗口还没有填满时，只维护队列单调性，不填入结果；窗口填满时，再入当前双端队列队头元素

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        vector<int> ret;
        deque<int> dq;
        int n = heights.size();
        for(int i = 1 - limit, j = 0; j < n; j++, i++){
            if(i > 0 && heights[i - 1] == dq.front()){
                dq.pop_front();
            }
            int newval = heights[j];
            while(!dq.empty() && dq.back() < newval){
                dq.pop_back();
            }
            dq.push_back(newval);
            if(i >= 0){
                ret.push_back(dq.front());
            }
        }
        return ret;
    }
};

四、文物朝代判断

展览馆展出来自 13 个朝代的文物，每排展柜展出 5 个文物。某排文物的摆放情况记录于数组 places，其中 places[i] 表示处于第 i 位文物的所属朝代编号。其中，编号为 0 的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否能够视为连续的五个朝代（如遇未知朝代可算作连续情况）。

示例 1：

输入：places = [0, 6, 9, 0, 7]
输出：True

示例 2：

输入：places = [7, 8, 9, 10, 11]
输出：True

提示：

places.length = 5
0 <= places[i] <= 13
首先理解何为连续：如果能够拼成 1 2 3 4 5 这种连续的序列，而不是 1 3 4 5 6 或者 1 1 3 4 5 这种
因此首先可以用哈希表（或者使用数组简化），进行验重
之后来看 0 能够填满空白。简单的判断方法就是找到最大、最小元素，两者相减，就可以得到，连续的话需要多少个元素。而我们只有 “五个朝代”，因此 max - min + 1 <= 5 （多的 0 可以直接拼到最小值之前或最大值之后）

class Solution {
public:
    bool checkDynasty(vector<int>& places) {
        bool hash[20];
        int maxVal = -1, minVal = 20;
        for(auto e: places){
            if(e == 0){
                cnt0++;
                continue;
            }
            if(hash[e] == true){
                return false;
            }
            else{
                hash[e] = true;
            }
            maxVal = max(maxVal, e);
            minVal = min(minVal, e);
        }
        return maxVal - minVal + 1 <= 5;
    }
};

五、反转字符串中的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

解法一：双指针（`O(N)` 空间复杂度）

从末尾开始遍历，将每个单词拼接到额外字符串末尾，并添加空格即可

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int begin = n - 1, end = begin;
        string str = "";

        while(begin >= 0){
            while(begin >= 0 && s[begin] == ' '){
                begin--;
            }
            if(begin < 0) break;
            end = begin;

            while(begin >= 0 && s[begin] != ' '){
                begin--;
            }

            string item = "";
            item = s.substr(begin + 1, end - begin);
            str += item;
            str += ' ';
        }
        str.pop_back();
        return str;
    }
};

解法二：双指针（原地修改，`O(1)` 空间复杂度）

首先通过快慢指针的方式去掉所有收尾空格、单词间的多余空格：slow、fast 指针都从头开始，fast 只要遇到字母，就写到 slow；遇到空格则跳过
最后 slow 处在的位置下标，就是去掉所有多余空格后，字符串长度，调用 resize
字符串整体逆序，可以使用 reverse
接下来将字符串中每个单词逆序即可，可以使用 Lambda 表达式自行定义逆置函数

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int slow = 0;

        for(int fast = 0; fast < n; fast++){
            if(s[fast] == ' ') continue;
            if(slow != 0){
                s[slow++] = ' ';
            }
            while(fast < n && s[fast] != ' '){
                s[slow++] = s[fast++];
            }
        }
        s.resize(slow);

        reverse(s.begin(), s.end());

        auto rever = [&](int i, int j){
            while(i < j){
                swap(s[i++], s[j--]);
            }
        };

        int left = 0;
        for(int i = 0; i < s.size(); i++){
            if(i == s.size() - 1) rever(left, i);
            if(s[i] == ' '){
                rever(left, i - 1);
                left = i + 1;
            }
        }
        return s;
    }
};

六、将字符串转成整数（atoi）

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−2(31), 2(31 )− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2(31) 的整数应该被固定为 −2(31) ，大于 2(31 )− 1 的整数应该被固定为 2(31 )− 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-2(31), 2(31) - 1] 内，最终结果为 42 。

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-2(31), 2(31) - 1] 内，最终结果为 -42 。

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-2(31), 2(31) - 1] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
首先，处理可以分为四步，包括：
1. 丢弃前导空格
2. 读取一个正负号（如果读完一个，还读到第二个，直接返回 0），或者直接开始读取数字
3. 读取数字，直到读到结尾或者读到非数字字符
4. 将数组转化为 Integer，如果整型溢出，设为 INT_MAX 或者 INT_MIN
主要是对于整型溢出的处理：
- 需要处理为负数的情况，上限为 INT_MAX + 1，即 -1 * INT_MIN；
- 需要处理为整数的情况，上限为 INT_MAX
- 为了防止 unsigned long long 溢出，在每次转数字都进行判断
- 核心就是记住：在返回以前，我们处理的都是类似于 “绝对值” 的数字，正负数体现在我们前面读到的正负号

class Solution {
public:
    using ull = unsigned long long;
    int myAtoi(string str) {
        int n = str.size();
        int cur = 0;
        while(str[cur] == ' ' && cur < n){
            cur++;
        }

        int flag = 1;
        if(str[cur] == '-') {
            flag = -1;
            cur++;
        }
        else if(str[cur] == '+'){
            cur++;
        }
        if(!isdigit(str[cur])) return 0;

        int begin = cur, end = cur;
        while(end < n && isdigit(str[end])){
            end++;
        }
        
        string item = str.substr(begin, end - begin);
        ull ret = 0;

        for(int i = 0; i < item.size(); i++){
            ret *= 10;
            ret += item[i] - '0';
            if(flag == -1 && ret > (ull)INT_MAX + 1){
                return INT_MIN;
            }
            if(flag == 1 && ret > (ull)INT_MAX){
                return INT_MAX;
            }
        }
        return flag * ret;
    }
};

七、最小栈

请你设计一个 最小栈 。它提供 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-2(31) <= val <= 2(31) - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push、pop、top 和 getMin 最多被调用 3 * 10(4) 次

难点在于怎样通过 O(1) 的时间复杂度获取到最小值。这种题，一种思路就是：将 O(N) 的时间复杂度，“平摊” 到 N 次操作中，“化为” O(1) 的时间复杂度

维护两个栈，一个正常放数字（numst），另一个放最小值（minst）
入栈时，如果入栈数字比 minst.top() 大，结合栈的出入规则，只要 minst.top() 还在，他就一定不会是最小值，而他一定比 minst.top() 先被出栈，所以他没有必要进入最小栈；出栈时，当前最小栈栈顶是最小的，下面是次小的，但是怎样判断出栈元素是否是最小栈栈顶的元素呢？这里我们采取 “不判断”，让最小栈的栈顶元素的意义成为：当 numst 的大小为 n 时（minst 大小为 n），栈内元素的最小值，因此当 x > minst.top() 时，依然入最小栈栈顶元素

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int x) {
        numst.push(x);
        if(minst.empty()){
            minst.push(x);
            return;
        }
        if(x < minst.top()){
            minst.push(x);
        }
        else{
            minst.push(minst.top());
        }
    }
    
    void pop() {
        numst.pop();
        minst.pop();
    }
    
    int top() {
        return numst.top();
    }
    
    int getMin() {
        return minst.top();
    }
private:
    stack<int> numst;
    stack<int> minst;
};

八、设计自助结算系统

请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：

get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1
add(value)：将价格为 value 的商品加入待结算商品队列的尾部
remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1

注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)

示例 1：

输入: 

["Checkout","add","add","get_max","remove","get_max"]

[[],[4],[7],[],[],[]]

输出: [null,null,null,7,4,7]

示例 2：

输入: 

["Checkout","remove","get_max"]

[[],[],[]]

输出: [null,-1,-1]

提示：

1 <= get_max, add, remove 的总操作数 <= 10000
1 <= value <= 10^5
借鉴前面的思路，只要队列中来了个最大值，那么前面的所有数值，都一定不会是 get_max 的结果；但是后面的结果有可能在当前最大值被出队列后，成为新的最大值
因此思路是：维护一个 deque，实现 O(1) 的头尾操作。每次入队列，都清除 deque 中的所有比当前值小的元素，并尾差新的数值
每次获取最大值，都获取 deque 首元素；每次出队列，如果出的是当前 deque 首元素，deque 同步出，否则不出

九、子结构判断

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，**空树 **不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例 1：

输入：tree1 = [1,7,5], tree2 = [6,1]
输出：false
解释：tree2 与 tree1 的一个子树没有相同的结构和节点值。

示例 2：

输入：tree1 = [3,6,7,1,8], tree2 = [6,1]
输出：true
解释：tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 -> 1。

提示：

0 <= 节点个数 <= 10000

不要将检查子结构和遍历 tree1 放在一起
递归分为两个任务
- 将每一个 tree1 的节点作为根节点
- 以根节点，去递归匹配 tree2
返回条件
- B 为空，根据题意无法匹配（但是在递归检查的过程中，B为空说明匹配完成）
- A 为空，无法匹配不为空的 B

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == nullptr || B == nullptr){
            return false;
        }
        return isMatch(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

    bool isMatch(TreeNode* A, TreeNode* B){
        if(B == nullptr){
            return true;
        }
        if(A == nullptr){
            return false;
        }
        if(A->val != B->val){
            return false;
        }
        return isMatch(A->left, B->left) && isMatch(A->right, B->right);
    }
};

十、验证二叉搜索树的后序遍历

请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。

示例 1：

输入: postorder = [4,9,6,5,8]
输出: false 
解释：从上图可以看出这不是一颗二叉搜索树

示例 2：

输入: postorder = [4,6,5,9,8]
输出: true 
解释：可构建的二叉搜索树如上图

提示：

数组长度 <= 1000
postorder 中无重复数字
一个平衡二叉树的后续遍历序列可以分为 【左子树】【右子树】【根】
左子树中的数字都是比根小，右子树的数字都是比根大。
自然的，我们可以通过递归的方式判断，只要找到左子树的根（rootleft），再找到右子树的根（rootright），并且 rootright 和 root 之间没有其他值，就去递归判断 rootleft 和 rootright

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        return recur(postorder, 0, postorder.size() - 1);
    }

    bool recur(vector<int>& postorder, int begin, int end){
        if(begin >= end)  return true;
        int m = begin;
        while(m < end && postorder[m] < postorder[end]){
            m++;
        }
        int n = m;
        while(n < end && postorder[n] > postorder[end]){
            n++;
        }
        return n == end && recur(postorder, begin, m - 1) && recur(postorder, m, n - 1);
    }
};

十一、将二叉搜索树转化为排序的双向链表

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

示例 1：

输入：root = [4,2,5,1,3]

输出：[1,2,3,4,5]
解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

示例 2：

输入：root = [2,1,3]
输出：[1,2,3]

示例 3：

输入：root = []
输出：[]
解释：输入是空树，所以输出也是空链表。

示例 4：

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

提示：

-1000 <= Node.val <= 1000
Node.left.val < Node.val < Node.right.val
Node.val 的所有值都是独一无二的
0 <= Number of Nodes <= 2000
递归处理，左面的递归后，拿到一个有序链表的 head、tail；右面递归后，拿到一个有序链表的 head、tail，中间节点直接追加到左面递归的结果
但其实上面的 head、tail 我们只需要维护一份，head 用来返回结果，tail 用来最后做成双向链表。
所以我们可以直接通过变量的方式维护一个 head、tail，然后在递归的过程中不断更新 head、tail，最后连成双向链表后返回

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return root;
        recur(root);
        head->left = tail;
        tail->right = head;
        return head;
    }

    void recur(Node* cur){
        if(cur == nullptr){
            return;
        }
        recur(cur->left);
        cur->left = tail;
        if(tail != nullptr){
            tail->right = cur;
        }
        else{
            head = cur;
        }
        tail = cur;
        recur(cur->right);
    }
private:
    Node* head;
    Node* tail;
};

十二、Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x(n)）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2(-2) = 1/2(2) = 1/4 = 0.25

关于 n 溢出的问题，只要把计算逻辑放到另一个接收 long long 表示次数的函数里，就可以解决了

十三、破冰游戏（约瑟夫环）

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

示例 1：

输入：num = 7, target = 4
输出：1

示例 2：

输入：num = 12, target = 5
输出：0

首先明确一个共识：当只有一个人时，无论 target 是几，最后剩下的一定是他，即结果为 0
当人数为 n 时，进行的步骤为
- 离开一个人，离开的是 (target - 1) % num，还剩 n - 1 个人
- 从离开的人的下一位重新开始计数，进行下一轮处理
这就发现了递归的过程：先求这一轮，有那个人要离开；然后看 n - 1 个人时，按照他的下标计算方式（n - 1 轮的 0 下标，对应 n 轮离开的人的下一个）拿到最后剩下的人，从而我们可以求出在 n - 1 轮剩下的人在 n 轮的位置，公式为 （iceBreakingGame(num - 1, target) + target - 1 + 1）% num = (iceBreakingGame(num - 1, target) + target) % num。
而我们递归函数返回值的意义是：在人数为 n 时，最后活下来的人，因此无论是 1、2、…、100、…、n 个人时，留下的都是这个人，只不过编号不同

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        if(num == 1){
            return 0;
        }
        return (iceBreakingGame(num - 1, target) + target) % num;
    }
};

十四、统计结果概率

你选择掷出 num 个色子，请返回所有点数总和的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 num 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1：

输入：num = 3
输出：[0.00463,0.01389,0.02778,0.04630,0.06944,0.09722,0.11574,0.12500,0.12500,0.11574,0.09722,0.06944,0.04630,0.02778,0.01389,0.00463]

示例 2：

输入：num = 5
输出:[0.00013,0.00064,0.00193,0.00450,0.00900,0.01620,0.02636,0.03922,0.05401,0.06944,0.08372,0.09452,0.10031,0.10031,0.09452,0.08372,0.06944,0.05401,0.03922,0.02636,0.01620,0.00900,0.00450,0.00193,0.00064,0.00013]

每一轮得到的新的结果都依赖于上一轮的结果
第一次投色子可以确定最小的点数是 1 ~ 6，放到题目要求的数组里对应的下标是 0 ~ 5。
再往后投色子，每一个点数情况都是由上一个情况至少 +1，最多 +6 得到的，并且我们的 dp 数组中，维护的是只出现于这一轮的结果
因此，在每个点数都至少由上一轮的位置 +1 得到的情况下，需要将所有位置“左移”一位，否则将在 dp[0] 出现上一轮残留的结果，例如第二轮投色子就可能出现点数为1点的情况（从结果上看，并不在乎具体点数，而是最小的若干点数）
因此，当投第 i 轮，由上一轮的 j 位置转化来，此轮点数为 k 时，结果应该加到 j + k - 1 位置

class Solution {
public:
    vector<double> statisticsProbability(int num) {
        int n = 6;
        vector<double> dp(6, 1.0 / 6);

        for(int i = 2; i <= num; i++){
            vector<double> tmp(5 * i + 1);
            for(int j = 0; j < dp.size(); j++){
                for(int k = 1; k <= 6; k++){
                    tmp[j + k - 1] += dp[j] * (1.0 / 6);
                }
            }
            dp = tmp;
        }
        return dp;
    }
};

十五、正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

返回一个布尔值，表示匹配是否覆盖整个输入字符串（而非部分）。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

主要是要弄清楚状态转移的过程

一维 dp 没法满足我们的需求，采取二维 dp
对于 p[j] 有三种情况
- 和 s[i] 相同，直接看前面能够匹配即可，即 dp[i][j] = dp[i - 1][j - 1]
- 为 .，能够匹配任意单个字符（零个不可以），看前面能否匹配即可，dp[i][j] = dp[i - 1][j - 1]
- 为 *，匹配零个或多个前面的字符，根据前面的字符，又分为两种情况
  - p[j - 1] 是 .，那么 .* 可以匹配零个字符，由 dp[i][j - 2] 转移来；或者匹配若干个字符，从 dp[i - 1][j] 来
  - p[j - 1] 是字母，那么匹配零个字符，由 dp[i][j - 2] 转移来；或者匹配若干个字符，需要 p[j - 1] == s[i] 才能够继续匹配，由 dp[i - 1][j] 转移来
初始化：
- 当 s、p 均为空时，true
- s 不为空，p 为空，false
- s 为空，p 不为空，需要初始化判断，因为 * 是有匹配零个字符的能力的

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p[0] == '*'){
            return false;
        }
        s = ' ' + s, p = ' ' + p;
        int m = s.size();
        int n = p.size();

        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

        dp[0][0] = true;
        for(int i = 2; i <= n; i += 2){
            if(p[i] == '*'){
                dp[0][i] = true;
            }
            else{
                break;
            }
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s[i] == p[j] || p[j] == '.'){
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if(p[j] == '*'){
                    dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
                }
            }
        }

        return dp[m][n];
    }
};

十六、数字一的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

暴力统计是一种方法，但是时间复杂度为 O(N)
我们其实可以通过直接在 n 的基础上推导的方式：我们并不关心哪些数字含有多少个1，我们关心的是一共有多少个1。
那么其实可以直接看每一位如果为 1 的话，不大于 n 的有多少个数，维护好范围我们就可以通过排列组合的方式完成
维护 high、cur、low ，分别表示当前位置前面的数字、当前位置数字、当前位置后面的数字，并维护一个 digit 表示当前正在遍历的数位
- cur == 0 ，那么如果当前数位取 1，需要高位（high）取到 0 ~ high - 1，低位（low）可以随便取，即 ret += high * digit
- cur == 1，那么一方面可以继承上面的情况；另一方面，如果高位取 high 的话，低位就要取 0 ~ low - 1，即 ret += high * digit + low + 1
- 如果 cur 为其他情况，那么高位可以取 0 ~ high，低位可以任意取，即 ret += (high + 1) * digit

class Solution {
public:
    using ull = unsigned long long;
    int countDigitOne(int n) {
        ull ret = 0, high = n / 10, cur = n % 10, low = 0, digit = 1;
        while(high != 0 || cur != 0){
            if(cur == 0){
                ret += high * digit;
            }
            else if(cur == 1){
                ret += high * digit + low + 1;
            }
            else{
                ret += (high + 1) * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return ret;
    }
};

十七、有效数字

有效数字（按顺序）可以分成以下几个部分：

若干空格
一个小数或者整数
（可选）一个 'e' 或 'E' ，后面跟着一个整数
若干空格

小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
至少一位数字，后面跟着一个点 '.'
至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
至少一位数字

部分有效数字列举如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

示例 1：

输入：s = "0"
输出：true

示例 2：

输入：s = "e"
输出：false

示例 3：

输入：s = "."
输出：false

提示：

1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。
如果使用简单的 if-else 结构判断，那这道题会非常的麻烦折磨人
对于 if-else 太过复杂的情况，可以考虑使用状态机来推导所有的状态转移过程，从而推导出是否符合状况
首先，判断出所有可能的状态
- 初始（尚未开始读）
- 初始空格
- 整数（或小数）符号位
- 整数部分
- 前面无整数小数点
- 前面有整数小数点
- 小数部分
- e/E
- 指数部分符号位
- 指数部分整数
- 末尾空格
我们总共可能读到以下字符
- 空格
- +、-
- 0 ~ 9
- .
- e / E
- 其他
接下来我们制作出来状态机的规则，在不同状态下，读到不同字符是否合法，以及读到后进入那种状态，如下所示

0. 初始             {1, 2, 3, 5, -1, -1}
1. 空格             {1, 2, 3, 5, -1, -1}
2. 符号位           {-1, -1, 3, 5, -1, -1}
3. 整数部分         {10, -1, 3, 4, 7, -1}
4. 左侧有整数小数点  {10, -1, 6, -1, 7, -1}
5. 左侧无整数小数点  {-1, -1, 6, -1, -1, -1}
6. 小数部分         {10, -1, 6, -1, 7, -1}
7. 字符 e/E         {-1, 8, 9, -1, -1, -1}
8. 指数部分符号位    {10, -1, 9, -1, -1, -1}
9. 指数部分整数部分 {10, -1, 9, -1, -1, -1}
10. 末尾空格        {10, -1, -1, -1, -1, -1}

class Solution {
public:
    bool validNumber(string s) {
        int trans[11][6] = {
            {1, 2, 3, 5, -1, -1},
            {1, 2, 3, 5, -1, -1},
            {-1, -1, 3, 5, -1, -1},
            {10, -1, 3, 4, 7, -1},
            {10, -1, 6, -1, 7, -1},
            {-1, -1, 6, -1, -1, -1},
            {10, -1, 6, -1, 7, -1},
            {-1, 8, 9, -1, -1, -1},
            {-1, -1, 9, -1, -1, -1},
            {10, -1, 9, -1, -1, -1},
            {10, -1, -1, -1, -1, -1}
        };

        int cur = 0;
        for(auto ch: s){
            int t = 0;
            if(ch == ' '){
                t = 0;
            }
            else if(ch == '+' || ch == '-'){
                t = 1;
            }
            else if(ch >= '0' && ch <= '9'){
                t = 2;
            }
            else if(ch == '.'){
                t = 3;
            }
            else if(ch == 'E' || ch == 'e'){
                t = 4;
            }
            else{
                t = 5;
            }

            cur = trans[cur][t];
            if(cur == -1){
                return false;
            }
        }

        return cur == 3 || cur == 4 || cur == 6 || cur ==9 || cur == 10;
    }
};

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/wangjialelele/article/details/169070677

【C++】《剑指 Offer》高频算法题图文/代码全解析

一、丑数

解法一：优先级队列

解法二：动态规划

二、设计机械累加器

解法一：递归

三、望远镜中最高海拔

解法一：暴力解法

解法二：单调队列

四、文物朝代判断

五、反转字符串中的单词

解法一：双指针（`O(N)` 空间复杂度）

解法二：双指针（原地修改，`O(1)` 空间复杂度）

六、将字符串转成整数（atoi）

七、最小栈

八、设计自助结算系统

九、子结构判断

十、验证二叉搜索树的后序遍历

十一、将二叉搜索树转化为排序的双向链表

十二、Pow(x, n)

十三、破冰游戏（约瑟夫环）

十四、统计结果概率

十五、正则表达式匹配

十六、数字一的个数

十七、有效数字

评论

评论列表

微信小程序

QQ小程序

关于作者

【C++】《剑指 Offer》高频算法题图文/代码全解析

一、丑数

解法一：优先级队列

解法二：动态规划

二、设计机械累加器

解法一：递归

三、望远镜中最高海拔

解法一：暴力解法

解法二：单调队列

四、文物朝代判断

五、反转字符串中的单词

解法一：双指针（O(N) 空间复杂度）

解法二：双指针（原地修改，O(1) 空间复杂度）

六、将字符串转成整数（atoi）

七、最小栈

八、设计自助结算系统

九、子结构判断

十、验证二叉搜索树的后序遍历

十一、将二叉搜索树转化为排序的双向链表

十二、Pow(x, n)

十三、破冰游戏（约瑟夫环）

十四、统计结果概率

十五、正则表达式匹配

十六、数字一的个数

十七、有效数字

评论

评论列表

微信小程序

QQ小程序

关于作者

解法一：双指针（`O(N)` 空间复杂度）

解法二：双指针（原地修改，`O(1)` 空间复杂度）