引言

本书为个人在刷题过程中的心得和体会。
主要题目来源为力扣-中国站 - LeetCode-cn
主要刷题语言为 Rust / C++
欢迎加微信 axccjqh 交流，备注 leetcode-solution 和必要的个人信息。

TIPS:本站题解已经按照时间倒序排序，且包含模糊搜索功能。
感谢Travis-CI,Rust语言和mdBook，本书就是构建在其之上。
如过觉得本项目好，可以点个Star。请点击右上角的Github图标进入本项目的Github页面。

关于从蚂蚁笔记迁移而来的说明

之前是在蚂蚁笔记上进行写作。但因为诸多问题，将其迁移到GitHub Pages上来进行维护。
如需阅览之前的笔记，请[点击下载(LeetCode-Solution-pre.zip)(共有93篇)

可能会比较乱，因为没有按照时间加标签，但根据题号还是可以找到指定的题目的。

2021 秋季力扣杯 - 战队赛复盘

写在前面

今年发挥还算挺不错的。以后再接再励！
我 30 分钟写完了 2、4 两道题，队友一小时多写完了 1、3 两道题，然后就是啥都不会的几个小时。。。

争取以后不会出现这种情况。

第一题开幕式焰火

1.1 题目

「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。
给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。

示例 1：

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

输出：3

解释：焰火中有 3 个不同的颜色，值分别为 1、2、3

示例 2：

输入：root = [3,3,3]

输出：1

解释：焰火中仅出现 1 个颜色，值为 3

提示：

1 <= 节点个数 <= 1000
1 <= Node.val <= 1000

1.3 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dp[1005];
    int count = 0;
    void deal(TreeNode * root) {
        if (!root) return ;
        if (!dp[root->val]) {
            count++;
            dp[root->val] = true;
        }
        deal(root->left);
        deal(root->right);
    }
    int numColor(TreeNode* root) {
        deal(root);
        return count;
    }
};

第二题自行车炫技赛场

2.1 题目

「力扣挑战赛」中 N*M 大小的自行车炫技赛场的场地由一片连绵起伏的上下坡组成，场地的高度值记录于二维数组 terrain 中，场地的减速值记录于二维数组 obstacle 中。

若选手骑着自行车从高度为 h1 且减速值为 o1 的位置到高度为 h2 且减速值为 o2 的相邻位置（上下左右四个方向），速度变化值为 h1-h2-o2（负值减速，正值增速）。

选手初始位于坐标 position 处且初始速度为 1，请问选手可以刚好到其他哪些位置时速度依旧为 1。请以二维数组形式返回这些位置。若有多个位置则按行坐标升序排列，若有多个位置行坐标相同则按列坐标升序排列。

注意： 骑行过程中速度不能为零或负值

示例 1：

输入：position = [0,0], terrain = [[0,0],[0,0]], obstacle = [[0,0],[0,0]]

输出：[[0,1],[1,0],[1,1]]

解释：
由于当前场地属于平地，根据上面的规则，选手从[0,0]的位置出发都能刚好在其他处的位置速度为 1。

示例 2：

输入：position = [1,1], terrain = [[5,0],[0,6]], obstacle = [[0,6],[7,0]]

输出：[[0,1]]

解释：
选手从 [1,1] 处的位置出发，到 [0,1] 处的位置时恰好速度为 1。

提示：

n == terrain.length == obstacle.length
m == terrain[i].length == obstacle[i].length
1 <= n <= 100
1 <= m <= 100
0 <= terrain[i][j], obstacle[i][j] <= 100
position.length == 2
0 <= position[0] < n
0 <= position[1] < m

2.2 思路分析

这道题是一个比较基础的 dfs 思路。可能会要使用记忆化的技术去重。仔细读题后发现，自行车到达一个地方，并非一定会有相同的速度，也就是说，不同的路径到达一个地方，速度可能并不相同。在这种情况下，我们必须得记录一下，如果两次到达同一个地方，具有相同的速度，我们就可以考虑不再继续。如果不去判断这一点，就会导致循环的出现，也就是示例 1 中出现的情况，如果我们不判断重复，一定会导致死循环。

所以总结一下，思路就是 dfs 加上记忆化去重（剪枝）。只有两次到达同一个地方并且具有相同的速度，才会是剪枝条件。

我的代码中主要分成了两块，一块是主函数，一块是 dfs，dfs 函数接受三个参数，也就是当前的 x，y 坐标和 speed 速度。当passed[x][y][speed]为true时候，就说明之前以相同的速度遍历过相同的地方，而且无需再遍历一次。res[x][y]为true的时候说明该坐标是答案的一个候选坐标。接下来就是非常常规的往四个方向进行遍历。速度小于 0 就截断之类的基操。

主函数中主要是处理了一下输入输出的逻辑，存了一些全局变量，对输出的答案格式做了一个简单的操作，包括将 res 变成答案所需的形式。

2.3 C++代码

using VI = vector<int>;
using VVI = vector<VI>;
const VI direc = {0, 1, 0, -1, 0};
class Solution {
public:
    VVI t, o;
    bool res[100][100] = {};
    bool passed[100][100][105] = {};
    int n, m;
    void dfs(int x, int y, int speed) {
        if (speed == 1) res[x][y] = true;
        if (speed < 1) return;
        if (passed[x][y][speed]) {
            return;
        }
        passed[x][y][speed] = true;
        for (int i = 0; i < 4; ++i) {
            int xt = x + direc[i];
            int yt = y + direc[i + 1];
            if (xt >= 0 && yt >= 0 && xt < n && yt < m)
                dfs(xt, yt, speed + t[x][y] - t[xt][yt] - o[xt][yt]);
        }
    }
    VVI bicycleYard(VI& p, VVI& terrain, VVI& obstacle) {
        t = terrain;
        o = obstacle;
        n = t.size();
        m = t[0].size();
        int x = p[0], y = p[1];
        dfs(x, y, 1);
        VVI res_v;
        res[x][y] = false;
        for (int i = 0; i < 100; ++i)
            for (int j = 0; j < 100; ++j)
                if (res[i][j])
                    res_v.push_back({i, j});
        return res_v;
    }
};

第三题志愿者调配

3.1 题目

「力扣挑战赛」有 n 个比赛场馆（场馆编号从 0 开始），场馆之间的通道分布情况记录于二维数组 edges 中，edges[i]= [x, y] 表示第 i 条通道连接场馆 x 和场馆 y(即两个场馆相邻)。初始每个场馆中都有一定人数的志愿者（不同场馆人数可能不同），后续 m 天每天均会根据赛事热度进行志愿者人数调配。调配方案分为如下三种：

将编号为 idx 的场馆内的志愿者人数减半；
将编号为 idx 的场馆相邻的场馆的志愿者人数都加上编号为 idx 的场馆的志愿者人数；
将编号为 idx 的场馆相邻的场馆的志愿者人数都减去编号为 idx 的场馆的志愿者人数。

所有的调配信息记录于数组 plans 中，plans[i] = [num,idx] 表示第 i 天对编号 idx 的场馆执行了第 num 种调配方案。
在比赛结束后对调配方案进行复盘时，不慎将第 0 个场馆的最终志愿者人数丢失，只保留了初始所有场馆的志愿者总人数 totalNum ，以及记录了第 1 ~ n-1 个场馆的最终志愿者人数的一维数组 finalCnt。请你根据现有的信息求出初始每个场馆的志愿者人数，并按场馆编号顺序返回志愿者人数列表。

注意：

测试数据保证当某场馆进行第一种调配时，该场馆的志愿者人数一定为偶数；
测试数据保证当某场馆进行第三种调配时，该场馆的相邻场馆志愿者人数不为负数；
测试数据保证比赛开始时每个场馆的志愿者人数都不超过 10^9；
测试数据保证给定的场馆间的道路分布情况中不会出现自环、重边的情况。

示例 1：

输入：
finalCnt = [1,16], totalNum = 21, edges = [[0,1],[1,2]], plans = [[2,1],[1,0],[3,0]]

输出：[5,7,9]

解释：

示例 2 ：

输入：
finalCnt = [4,13,4,3,8], totalNum = 54, edges = [[0,3],[1,3],[4,3],[2,3],[2,5]], plans = [[1,1],[3,3],[2,5],[1,0]]

输出：[10,16,9,4,7,8]

提示：

2 <= n <= 5*10^4
1 <= edges.length <= min((n * (n - 1)) / 2, 5*10^4)
0 <= edges[i][0], edges[i][1] < n
1 <= plans.length <= 10
1 <= plans[i][0] <=3
0 <= plans[i][1] < n
finalCnt.length = n-1
0 <= finalCnt[i] < 10^9
0 <= totalNum < 5*10^13

3.2 思路分析

我们只有一个值不知道，就是当前（最后时刻）第 0 号位的人数。通过观察题目不难得出，三个操作都是线性操作，而且我们准确地知道每一步的操作，也就是说，只要知道知道了最后一个时刻的第 0 号位的人数，我们就可以严丝合缝地将结果递推到第一步。并且，在此时，第一步的总和应当严格等于totalNum。

既然如此，我们不妨设一个变量 x，作为最后时刻第 0 号位的人数。逆推来完成最终的推理，推理到第一步之后，每一个场馆的人数都应该是一个关于变量 x 的一次函数，我们将其求和之后仍然是一个一次函数，这个一次函数最终等于 totalNum ，代入就可以求得 x，代入每个场馆的表达式中即可获得每个场馆在第一步时的人数。

在具体代码中，设置两个数组 x_param 和 c_param ，分别代表指定场馆一次函数中的 x 系数项和常数项。最终递推回第一步，求得 x_param_sum 与 c_param_sum 。求解 x 的方程为:

$\sum_{i = 1}^{n} x_{p a r am} [i] * x + \sum_{i = 1}^{n} c_{p a r am} [i] = t o t a lN u m$
简单变换后得到:

$x = \frac{( t o t a lN u m - \sum _{i = 1}^{n} c _{p a r am} [ i ] )}{\sum _{i = 1}^{n} x _{p a r am} [ i ]}$

最后代入到表达式中即可完成计算。

3.3 C++代码

using VI = vector<int>;
using VVI = vector<VI>;
using ll = long long;
class Solution {
public:
    VI volunteerDeployment(VI& finalCnt, ll totalNum, VVI& edges, VVI& plans) {
        VI m[50005];
        int n = finalCnt.size() + 1;
        // x系数和常数
        int x_param[50005] = {}, c_param[50005] = {};
        for (auto & edge : edges) {
            m[edge[0]].push_back(edge[1]);
            m[edge[1]].push_back(edge[0]);
        }
        x_param[0] = 1;
        for (int i = 0; i < n - 1; ++i)
            c_param[i + 1] = finalCnt[i];
        while (plans.size()) {
            int kind = plans.back()[0];
            int place = plans.back()[1];
            plans.pop_back();
            if (kind == 1) {
                x_param[place] *= 2;
                c_param[place] *= 2;
            } else if (kind == 2) {
                for (auto & nxt : m[place]) {
                    x_param[nxt] -= x_param[place];
                    c_param[nxt] -= c_param[place];
                }
            } else {
                for (auto & nxt : m[place]) {
                    x_param[nxt] += x_param[place];
                    c_param[nxt] += c_param[place];
                }
            }
        }
        ll x_param_sum = 0, c_param_sum = 0;
        for (int i = 0; i < n; ++i) {
            x_param_sum += x_param[i];
            c_param_sum += c_param[i];
        }
        // 方程: x_param_sum * x + c_param_sum = totalNum
        int x = (totalNum - c_param_sum) / x_param_sum;
        vector<int> res(n);
        for (int i = 0; i < n; ++i)
            res[i] = x_param[i] * x + c_param[i];
        return res;
    }
};

第四题入场安检

4.1 题目

「力扣挑战赛」的入场仪式马上就要开始了，由于安保工作的需要，设置了可容纳人数总和为 M 的 N 个安检室，capacities[i] 记录第 i 个安检室可容纳人数。安检室拥有两种类型：

先进先出：在安检室中的所有观众中，最早进入安检室的观众最先离开
后进先出：在安检室中的所有观众中，最晚进入安检室的观众最先离开

恰好 M+1 位入场的观众（编号从 0 开始）需要排队依次入场安检，入场安检的规则如下：

观众需要先进入编号 0 的安检室
当观众将进入编号 i 的安检室时（0 <= i < N)，
- 若安检室未到达可容纳人数上限，该观众可直接进入；
- 若安检室已到达可容纳人数上限，在该观众进入安检室之前需根据当前安检室类型选择一位观众离开后才能进入；
当观众离开编号 i 的安检室时（0 <= i < N-1)，将进入编号 i+1 的安检室接受安检。

若可以任意设定每个安检室的类型，请问有多少种设定安检室类型的方案可以使得编号 k 的观众第一个通过最后一个安检室入场。

注意：

观众不可主动离开安检室，只有当安检室容纳人数达到上限，且又有新观众需要进入时，才可根据安检室的类型选择一位观众离开；
由于方案数可能过大，请将答案对 1000000007 取模后返回。

示例 1：

输入：capacities = [2,2,3], k = 2

输出：2
解释：
存在两种设定的 2 种方案：

方案 1：将编号为 0 、1 的实验室设置为 后进先出 的类型，编号为 2 的实验室设置为 先进先出 的类型；

方案 2：将编号为 0 、1 的实验室设置为 先进先出 的类型，编号为 2 的实验室设置为 后进先出 的类型。

以下是方案 1 的示意图：

示例 2：

输入：capacities = [3,3], k = 3

输出：0

示例 3：

输入：capacities = [4,3,2,2], k = 6

输出：2

提示:

1 <= capacities.length <= 200
1 <= capacities[i] <= 200
0 <= k <= sum(capacities)

4.2 思路分析

本题注意观察题目即可发现，先进先出对应的数据结构为队列，后进先出对应的数据结构为栈。而注意看第二个gif，我们发现，当一个容器（实验室，我们在此统称为容器）为队列时，第一个进入的第一个出队列，也就是说，一个队列对于改变流程中的第一个人没任何影响。对比着来看栈，我们发现，一个长度为2的栈必须先填充1个元素，这一个元素就相当于固定在此处，没法移动，也就是说，对于流程中的第一个人，一个长度为c的栈能够拦截c-1个人。

那么就很简单了。因为我们想要让第k个人达到对首，我们必须使用栈来拦截前k个人。

所以我们把这道题翻译成一个我们喜闻乐见的形式：

有`N`个硬币，每个的金额都在`cap`数组中给出（需要一个减1操作）。我们从前往后选，求最终金额为`k`的方案数。

是不是一下就简单了呢！

最终的做法就是一个非常简单的dp。因为一个硬币只能用一次，所以要控制dp的方向。

4.3 C++代码

const int md = 1000000007;
class Solution {
public:
    int securityCheck(vector<int>& cap, int k) {
        for (auto & c : cap) c--;
        int sum = accumulate(cap.begin(), cap.end(), 0);
        if (sum < k) return 0;
        int dp[40005] = {1};
        for (auto & c : cap) {
            for (int i = k - c; i >= 0; --i) {
                (dp[i + c] += dp[i]) %= md;
            }
        }
        return dp[k];
    }
};

No.434 字符串中的单词数

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。

思路分析

这题考察的有点像状态机。因为需要维护一个前一个字符是不是字母的状态。如果前一个是空格，后一个是字母，就说明开始了一个新单词。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn count_segments(s: String) -> i32 {
        let mut state = 0;
        let mut res = 0;
        for ch in s.chars() {
            if ch == ' ' {
                state = 0;
            } else {
                if state == 0 {
                    res += 1;
                }
                state = 1;
            }
        }
        res
    }
}
}

No.414 第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示：

1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？

思路分析

这种题一般就套一个有序数组就行。

O(n)的话就维护一下有序数组，使得数组中元素的个数不会大于三个。因为大于三个也用不到。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
use std::collections::BTreeSet;
impl Solution {
    pub fn third_max(mut nums: Vec<i32>) -> i32 {
        let mut set = BTreeSet::new();
        for item in nums {
            set.insert(item);
        }
        *set.iter().rev().nth(2).unwrap_or(set.iter().last().unwrap())
    }
}
}

No.284 窥探迭代器

请你设计一个迭代器，除了支持 hasNext 和 next 操作外，还支持 peek 操作。

实现 PeekingIterator 类：

PeekingIterator(int[] nums) 使用指定整数数组 nums 初始化迭代器。
int next() 返回数组中的下一个元素，并将指针移动到下个元素处。
bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false 。
int peek() 返回数组中的下一个元素，但不移动指针。

示例：

输入：
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
输出：
[null, 1, 2, 2, 3, false]

解释：
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // 返回 1 ，指针移动到下一个元素 [1,2,3]
peekingIterator.peek();    // 返回 2 ，指针未发生移动 [1,2,3]
peekingIterator.next();    // 返回 2 ，指针移动到下一个元素 [1,2,3]
peekingIterator.next();    // 返回 3 ，指针移动到下一个元素 [1,2,3]
peekingIterator.hasNext(); // 返回 False

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
对 next 和 peek 的调用均有效
next、hasNext 和 peek 最多调用 1000 次

进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？

思路分析

本题的难点主要在于，本来原题给我们提供的数据结构Iterator只提供了以下两个接口：

int next()
bool hasNext()

而我们要实现的数据结构要在其基础上再实现一个int peek()。

这里就会出现一个问题，也就是每次调用next()无疑都会使得迭代器向后移动一个位置，但是每次调用peek()却不会。

其实很好提出一个解决方法，就是在每次调用next()的时候拿一个数字存一下，作为下次调用peek()时候的返回值。但这样会出现问题。

观察一下示例1，可以发现，在调用peek()时，指针不发生移动，但是确确实实地，我们获取到了下一个变量的值。这题的难点就在于，我们期望能够在获取下一个元素的值的时候不移动指针。但next()一定会移动指针。

思路可以这样：先用一个变量一直存住下一个元素的值，如果遇到了peek()就返回这个预先存的值，如果遇到next()也返回这个预先存的值并且更新预先存的值为下一个。

C++ 代码

class PeekingIterator : public Iterator {
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        flag = Iterator::hasNext();
        if (flag) {
            nextElement = Iterator::next();
        }
    }
    
    int peek() {
        return nextElement;
    }
    
    int next() {
        int ret = nextElement;
        flag = Iterator::hasNext();
        if (flag) {
            nextElement = Iterator::next();
        }
        return ret;
    }
    
    bool hasNext() const {
        return flag;
    }
private:
    int nextElement;
    bool flag;
};

No.482 密钥格式化

有一个密钥字符串 S ，只包含字母，数字以及 '-'（破折号）。其中， N 个 '-' 将字符串分成了 N+1 组。

给你一个数字 K，请你重新格式化字符串，使每个分组恰好包含 K 个字符。特别地，第一个分组包含的字符个数必须小于等于 K，但至少要包含 1 个字符。两个分组之间需要用 '-'（破折号）隔开，并且将所有的小写字母转换为大写字母。

给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。

示例 1：

输入：S = "5F3Z-2e-9-w", K = 4
输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；
     注意，两个额外的破折号需要删掉。

示例 2：

输入：S = "2-5g-3-J", K = 2
输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。

提示:

S 的长度可能很长，请按需分配大小。K 为正整数。
S 只包含字母数字（a-z，A-Z，0-9）以及破折号'-'
S 非空

思路分析

根据题目的思路可知，原字符串中的下划线对本题没什么用，所以统计的时候去掉。

首先计算每个部分可以分到多少个字符，也就是parts变量。然后计算第一个区块中有多少个字符，也就是remains。如果可以整除，第一个区块中就有k个字符，如果不能整除，第一个区块中的个数会小于k个，也就是valid(合法字符) / k。

在计算完成后，就可以将原字符串中的字符填充进去。注意：在填充完成remains个之后就填入一个下划线，并且将remains重置成k，因为往后的每一个区块之内都有k个字符。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn license_key_formatting(s: String, k: i32) -> String {
        let k = k as usize;
        let n = s.len();
        let count = s.chars().fold(0, |acc, x| acc + (x == '-') as usize);
        let valid = n - count;
        let parts = valid / k + (valid % k > 0) as usize;
        let mut remains = if valid % k == 0 {k} else {valid % k};
        let mut res = "".to_string();
        for ch in s.chars() {
            if ch == '-' {
                continue;
            }
            if remains == 0 {
                res.push('-');
                remains = k;
            }
            res.push(ch.to_ascii_uppercase());
            remains -= 1;
        }
        res
    }
}
}

No.166 分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证答案字符串的长度小于 10⁴ 。

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1
输出："2"

示例 3：

输入：numerator = 2, denominator = 3
输出："0.(6)"

示例 4：

输入：numerator = 4, denominator = 333
输出："0.(012)"

示例 5：

输入：numerator = 1, denominator = 5
输出："0.2"

提示：

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

思路分析

这道题本质上就是要让我们用除法的思维去做题。
在我们做除法的时候，怎么判断重复循环的小数呢？

首先当然是进行预处理。包括以下几个步骤。

处理符号，将负号统一处理一下。因为两个正数相除显然比较符合人类的习惯。
将所有32位数字输入处理成64位，因为可能会超限。
处理整数部分，因为整数部分一般不参与到循环小数的范围内。
其他特殊情况。

在处理完上述步骤之后，我们得到了还是题目中的两个数字numerator和denominator。这两个数字仍然是被除数与除数的关系，只不过经过减去整数部分的处理之后，我们能确保numerator一定小于denominator。小学课本对于循环小数的讲解

如果没有思路可以看一下上面这张图。这张图基本上概括了本题所需的循环小数部分的数学知识。可以看出，在除法的过程中，遇到除不尽的数字，我们一般是采用余数的方式，并且继续拿余数乘10之后再除。可以确定的是，只有在余数出现相同的情况下，余数之后的情况也会一模一样，也就是说，第一次出现相同的余数就是循环节的位置。

在此处，我们使用一个哈希表来存之前出现过的所有余数，并且在第二次出现余数的时候，标注循环节的位置，结束程序。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
use std::collections::HashMap;
impl Solution {
    pub fn fraction_to_decimal(numerator: i32, denominator: i32) -> String {
        let mut ret = String::new();
        if (numerator as i64 * denominator as i64) < 0 {
            ret.push('-');
        }
        let mut denominator = (denominator as i64).abs();
        let mut numerator = (numerator as i64).abs();
        let pre = numerator / denominator;
        numerator %= denominator;
        let mut map: HashMap<i64, i32> = HashMap::new();
        ret.push_str(&pre.to_string());
        if numerator == 0 {
            return ret;
        }
        ret.push('.');
        let mut ws = ret.len() as i32;
        loop {
            if numerator == 0 {
                break;
            }
            if map.contains_key(&numerator) {
                ret.insert(*map.get(&numerator).unwrap() as usize, '(');
                ret.push(')');
                break;
            }
            map.insert(numerator, ws);
            numerator *= 10;
            ret.push((('0' as u8) + (numerator / denominator) as u8) as char);
            numerator %= denominator;
            ws += 1;
        }
        ret
    }
}
}

No.405 数字转换为十六进制数

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用补码运算方法。

注意:

十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

输入:
26

输出:
"1a"

示例 2：

输入:
-1

输出:
"ffffffff"

思路分析

本质上就是一个二进制转十六进制的操作。最好使用二进制运算来做，能够更高效地利用计算机二进制的架构。

一位十六进制对应到四位二进制。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn to_hex(num: i32) -> String {
        let turned: Vec<char> = "0123456789abcdef".chars().collect();
        let mut num = num as u32;
        if num == 0 {
            return "0".to_string();
        }
        let mut res = vec![];
        while num != 0 {
            let mut tmp = 0;
            for i in 0..4 {
                tmp += (num & 1) * (1 << i);
                num >>= 1;
            }
            res.push(turned[tmp as usize]);
        }
        res.reverse();
        res.iter().collect()
    }
}
}

C++代码

static const char * turned = "0123456789abcdef";
class Solution {
public:
    string toHex(unsigned int num) {
        string res;
        do {
            int tmp = 0;
            for (int i = 0; i < 4; ++i) {
                tmp += (num & 1) * (1 << i);
                num >>= 1;
            }
            res.push_back(turned[tmp]);
        } while (num != 0);
        reverse(res.begin(), res.end());
        return res;
    }
};

No.1436 旅行终点站

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityA_i, cityB_i] 表示该线路将会从 cityA_i 直接前往 cityB_i 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

示例 1：

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A" 。

示例 3：

输入：paths = [["A","Z"]]
输出："Z"

提示：

1 <= paths.length <= 100
paths[i].length == 2
1 <= cityA_i.length, cityB_i.length <= 10
cityA_i!= cityB_i
所有字符串均由大小写英文字母和空格字符组成。

思路分析

如题要求一个站点没有下一个到达点，也就是说该城市不会位于(A, B)中的A位置，只位于B位置，因此我们只需要将所有的A用哈希表存储起来，然后遍历所有B，查看是否存在于表中，某个城市不存在直接返回答案（该城市）。

Java代码

class Solution {
    public String destCity(List<List<String>> paths) {
        int len = paths.size();
        Set<String> set = new HashSet<>();
        paths.forEach((path) -> {
            set.add(path.get(0));
        });
        for (int i = 0; i < len; i++) {
            List<String> list = paths.get(i);
            if (!set.contains(list.get(1))) {
                return list.get(1);
            }
        }
        return null;
    }
}

No.223 矩形面积

给你二维平面上两个 由直线构成的 矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其左下顶点和右上顶点坐标表示：

第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

示例 1：

输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45

示例 2：

输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16

提示：

-10⁴ <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10⁴

思路分析

首先可以想想，两个长方形重叠有哪些情况，有如上图这样，也有这样：

msg

也有如下这样：
msg2

也有可能长这样：
msg3

但其实不管他到底长什么样，我们都可以通过两正方形面积之和减去重合部分得出答案，设两长方形分别为 A 和 B，则：

A 和 B 的面积很好求，这里就不再赘述，这里主要说说重合的面积如何求；重合部分仔细考虑，他也是一个长方形，也有长和高，所以求出长和高是关键：长为 x 轴方向某两个端点之差，高则是 y 轴方向某两个端点之差，那这两个点是哪两个呢？

是这两个点（这种情况是红色部分点减去绿色部分点，为正数）：
在这里插入图片描述

是这两个点（这种情况是绿色点减去黄色点，为负数）：
在这里插入图片描述

由此可见：两点分别为：两个长方形的最右边的 x 的最小值 & 两个长方形最左边的 x 的最大值

高度方向也类似，就不过于赘述。

若长或者高任一为负数 or0，则将其置为 0.得出的重合面积也为 0：

Java 代码

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int A = (ax1 - ax2) * (ay1 - ay2);
        int B = (bx1 - bx2) * (by1 - by2);
        int C_X = Math.max(0, Math.min(ax2 ,bx2) - Math.max(ax1, bx1));
        int C_Y = Math.max(0, Math.min(ay2 ,by2) - Math.max(ay1, by1));
        int C = C_X * C_Y;
        return A + B - C;
    }
}

Rust 代码


#![allow(unused)]
fn main() {
struct Solution;
pub fn compute(a: i32, b: i32, c: i32, d: i32) -> i32 {
    let t = c.max(a);
    (b - t).min(d - t).max(0)
}
impl Solution {
    pub fn compute_area(a: i32, b: i32, c: i32, d: i32, e: i32, f: i32, g: i32, h: i32) -> i32 {
        // 重叠面积
        let cd = compute(a, c, e, g) * compute(b, d, f, h);
        (c-a)*(d-b) + (h-f)*(g-e) - cd
    }
}
}

No.517 超级洗衣机

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

示例 1：

输入：machines = [1,0,5]
输出：3
解释：
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2

示例 2：

输入：machines = [0,3,0]
输出：2
解释：
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1

示例 3：

输入：machines = [0,2,0]
输出：-1
解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。

提示：

n == machines.length
1 <= n <= 10⁴
0 <= machines[i] <= 10⁵

思路分析

本题主要的思路就是遍历。先遍历一遍，求得是否有可行解以及每个位置上的平均衣服的件数avg是多少。这里肯定大家都想得到。那么下面怎么办呢？我们知道，如果衣服多，假设一个位置上有K件衣服，而K>avg,那么我们最终的答案一定不会小于K-avg，因为对于该堆衣服来说，不考虑其他洗衣机的操作，仅对于本洗衣机而言，一定要花费K-avg的时间将里面多出来的衣服分出去。

对于本题我们还知道，可以在遍历数组的时候维护一个cur。假设有一只无形的大手在遍历数组的同时将所有洗衣机里衣服的数量变成了avg，多余的衣服就认为是余量，缺少的就认为是缺口。这样有一个好处，就是能够各司其职。下面的例子能够加强理解。

示例：          [5, 0, 7], avg = 12 / 3 = 4
在遍历时的`cur`值：[1, -3, 0]

这样可以发现，对于本数组而言，cur的最大绝对值就是需要的总时间。因为我们如果单看一个1号位，也就是中间的那一位，我们会发现，一定要4次填充才能将其填到avg。但是这四次填充有一次是来自左边，三次是来自右边，这两段时间是可以重叠的。而cur值就很好的对于缺口和余量的体现。当遍历到这一位，缺口是k时，说明之前的所有洗衣机就算内部匀一匀也还缺k个，必须从cur的右方去移动过来，这个k就是最小移动时间。而当余量是k时，也是一样的道理，说明在cur及cur的左边怎么匀都会多出来k个，必须转移到cur的右边，而转移必须通过cur，也就是说这k个转移是没有叠加的余地的，必须在最短为k的时间内完成。

所以cur可以作为一个全局的转移次数的把控。但还存在一些局限。看下面一个例子

示例：          [0, 3, 0], avg = 3 / 3 = 1
在遍历时的`cur`值：[-1, 1, 0]

这个示例来看，cur忽略了一个非常关键的点，也就是对于3而言，必须花费2次的时间才能将其完全转移出去。但对于cur来说，它并不知道自己所遍历到的-1和1是没法叠加的，都是从3上面分出来的。那么这时候就需要同考虑cur和K-avg对于最终结果的作用了。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn find_min_moves(machines: Vec<i32>) -> i32 {
        let sum: i32 = machines.iter().sum();
        let n = machines.len() as i32;
        if sum % n != 0 {
            return -1;
        } 
        let avg = sum / n;
        let mut res = 0;
        let mut cur = 0;
        for mut m in machines {
            m -= avg;
            cur += m;
            res = res.max(cur.abs()).max(m);
        }
        res
    }
}
}

C++代码

class Solution {
public:
    int findMinMoves(vector<int>& m) {
        int n = m.size();
        int sum = 0;
        for (auto & t : m) sum += t;
        if (sum % n != 0) return -1;
        int per = sum / n;
        sum = 0;
        int res = 0;
        for (auto & t : m) {
            t -= per;
            sum += t;
            res = max(res, abs(sum));
            res = max(res, t);
        }
        return res;
    }
};

No.437 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

二叉树的节点个数的范围是 [0,1000]
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

思路分析

不难看出本题一定会遍历到每个节点。而且方式一定是dfs。因为只有dfs我们才比较方便对路径进行处理。
常规的思路一定是存一下本节点之前遍历到的路径的所有值。并且回溯删除来保证只关注遍历到的节点所处的环境。

但是这样会比较复杂，如果只存之前遍历到的所有值，我们还得判断哪些区间可以加起来等于target。这样就是 $O (n^{2})$ 。

所以我们尝试用前缀和来简化一下，也就是在数组中存之前遍历到的所有从根节点开始的路径总和。
若一条路径上的节点为[1,2,3,4] 我们用前缀和存储变成[1,3,6,10] 当我们遍历到值为4的节点的时候，此时从根节点到本节点的路径总和是10，假设target是7，我们只需要找出来在前缀和数组中值等于10-7也就是3的节点即可算作有效方案，此时复杂度为 $O (n)$ ，因为需要对前缀和数组进行一次遍历。

本方案还可以进一步优化，因为我们要在数组里查找，而且是指定值去查找，就可以用哈希表来优化一下，最终查找的操作复杂度被我们从 $O (n^{2})$ 降低到了 $O (1)$ 。

C++代码

class Solution {
public:
    int res = 0, tar;
    unordered_map<int, int> v;
    void dfs(TreeNode * root, int cur) {
        if (!root) return;
        int tmp = cur + root->val;
        res += v[tmp - tar];
        v[tmp]++; 
        dfs(root->left, tmp);
        dfs(root->right, tmp);
        v[tmp]--; // 回溯删除
    }
    int pathSum(TreeNode* root, int targetSum) {
        tar = targetSum;
        v[0] = 1;
        dfs(root, 0);
        return res;
    }
};

No.639 解码方法 II

一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

要解码一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：

"AAJF" 对应分组 (1 1 10 6)
"KJF" 对应分组 (11 10 6)

注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。

除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回解码该字符串的方法数目。

由于答案数目可能非常大，返回对 10⁹ + 7 取余的结果。

示例 1：

输入：s = "*"
输出：9
解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。
可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。
因此，"*" 总共有 9 种解码方法。

示例 2：

输入：s = "1*"
输出：18
解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。
每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。
因此，"1*" 共有 9 * 2 = 18 种解码方法。

示例 3：

输入：s = "2*"
输出：15
解释：这一条编码消息可以表示 "21"、"22"、"23"、"24"、"25"、"26"、"27"、"28" 或 "29" 中的任意一条。
"21"、"22"、"23"、"24"、"25" 和 "26" 由 2 种解码方法，但 "27"、"28" 和 "29" 仅有 1 种解码方法。
因此，"2*" 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。

提示：

1 <= s.length <= 10⁵
s[i] 是 0 - 9 中的一位数字或字符 '*'

思路分析

这一题考察的主要就是思路严密。
通过题目所给信息不难判断这是一个一维的动态规划。
思路也是非常动态规划，dp[i]为使用了s的前i个字符所有的方案数。

如果s[i] 不是 '0'，那么就说明可以单独作为一个方案。也就是 dp[i + 1] += dp[i]
如果s[i - 1]和s[i]可以组成大于等于10（此处应为大坑，因为不能出现"01"）且小于等于26的数字，那么我们就认为可以将这两位数作为一个方案。dp[i + 1] += dp[i - 1]

思路非常简单，但是实现比较复杂，是因为我们总是会忽略各种各样的情况，比如"*"只能代表1到9，"01"不能作为合法的数之类的。

主要的思路就是分开来写，对于s[i]和s[i-1]是不是"*"分四种情况讨论，这样就不会漏了。

C++代码

using ll = int64_t;
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        ll dp[n + 1];
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '*') dp[i + 1] += dp[i] * 9;
            else if (s[i] != '0') dp[i + 1] += dp[i];
            if (i > 0) {
// cout << "Good";
                if (s[i - 1] == '*' && s[i] != '*'){
                    if (s[i] <= '6') dp[i + 1] += 2 * dp[i - 1];
                    else dp[i + 1] += dp[i - 1];
                } else if (s[i - 1] == '*' && s[i] == '*') {
                    // cout << "Good";
                    dp[i + 1] += dp[i - 1] * 15;
                } else if (s[i - 1] != '*' && s[i] == '*') {
                    if (s[i - 1] == '1') dp[i + 1] += dp[i - 1] * 9;
                    else if (s[i - 1] == '2') dp[i + 1] += dp[i - 1] * 6;
                } else {
                    if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))
                        dp[i + 1] += dp[i - 1];
                }
            }
            dp[i + 1] %= ll(1e9 + 7);
        }
        return dp[n];
    }
};

No.371 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

提示：

-1000 <= a, b <= 1000

思路分析

先给大家讲一下什么是加法器。加法器，顾名思义，就是做加法运算的工具。一个二输入的二进制加法器，应该有两个输出，一个是原原，一个是进位。下面给大家打个表看看。

数1	数2	答案	原位	进位
0	0	0	0	0
1	0	1	1	0
0	1	1	1	0
1	1	10	0	1

观察上表，我们不难看出，由原位和进位组成了最终的答案。而原位操作对于二进制来说就是一个很明显的异或(XOR)操作，而进位操作也就是与(AND)操作。那么我们可以得到一个等式：

a + b = a ^ b + (a & b) * 2
也就是
a + b = a ^ b + (a & b) << 1

从一个加号变成了另一个加号！好像没啥用。但遇到这种情况，我们可以考虑，是否可以递归。观察可得，a & b一定是一个越来越小的数字，它最后一定会趋向于0。一旦b趋向于0，那么答案就是a，我们就有了递归的基础。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn get_sum(a: i32, b: i32) -> i32 {
        if b == 0 {
            a
        } else {
            Solution::get_sum(a ^ b, (a & b) << 1)
        }
    }
}
}

C++代码

class Solution {
public:
    unsigned getSum(unsigned a, unsigned b) {
        if (b == 0) return a;
        return getSum(a ^ b, (a & b) << 1);
    }
};

No.583 两个字符串的删除操作

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

提示：

给定单词的长度不超过500。
给定单词中的字符只含有小写字母。

思路分析

两个字符串求这种类似编辑距离的题基本上用二维动态规划都比较简单。这道题有两种思路（均为动态规划），一种正着想，一种倒着想。

正向思维

dp[i][j]表示答案，也就是word1中前i个字符和word2中前j个字符所组成的字符串的删除操作的最短步数。
那么边界条件首先是dp[i][0]=i(i <= word1.length)与dp[0][i]=i(i <= word2.length)。因为一个空字符串与一个长度为i的字符串，总是要把长度为i的字符串删空才能相等，所以边界条件就此确定。动态规划的转移方程为两个

dp[i + 1][j + 1] = dp[i][j] (a[i] == b[j])
dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1]) + 1 (a[i] != b[i])

第一行，相等的时候，因为当出现两个相等字符的时候，删除的距离一定不增加。第二行也很好理解，如果没法做到相同的字符，那么就只能在删掉一位的基础上再进行比较，那么会在取最小值之后再加上1。

逆向思维

既然是删除字符串中的某些字符，那么留下来的公共部分我们怎么称呼呢？仔细思考，便发现，这不就是最长公共子序列吗！
那么我们就可以先求出两个字符串最长公共子序列的长度，然后再用两个字符串的长度减去最长公共子序列两倍的长度，即可获得每边字符串需要减少的字符数量之和。边界条件dp[i][0]=0与dp[0][i]=0
动态规划的转移方程

dp[i + 1][j + 1] = dp[i][j] + 1 (a[i] == b[j])
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]) (a[i] != b[i])

也比较好理解。

C++代码（正向）

#define REP(i, j) for (int i = 0; i < j; ++i)
class Solution {
public:
    int minDistance(string a, string b) {
        int m = a.size(), n = b.size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof dp);
        REP(i, m) REP(j, n)
            if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        return m + n - 2 * dp[m][n];
    }
};

C++代码（逆向）

#define REP(i, j) for (int i = 0; i < j; ++i)
class Solution {
public:
    int minDistance(string a, string b) {
        /*这破烂玩意不用dp做我把力扣炸了*/
        int m = a.size(), n = b.size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof dp);
        REP(i, m) REP(j, n)
            if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        return m + n - 2 * dp[m][n];
    }
};

No.430 扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：



扁平化后的链表如下图：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL

示例 3：

输入：head = []
输出：[]

如何表示测试用例中的多级链表？

以 示例 1 为例：

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

节点数目不超过 1000
1 <= Node.val <= 10^5

思路及代码分析

这种题目一看就可以拿递归做。而且递归是一个比较直观的办法。我们拿第一个示例来看，假设我们遍历到了3这个节点，而它有child，我们需要获取的其实是child的最后一个节点。有了最后一个节点，我们才能将其与3的后一个节点4进行连接，部分插入。

按照这个思想，我们必须新建一个函数去完成这项工作，因为原函数给入的是头结点，返回的也是头结点，而我们自定义的函数给入的头结点，返回的是尾节点。

首先先用简单的方法来思考，假设链表里没有child。那么我们的函数差不多长这样：

class Solution {
public:
    Node * deal(Node * node) {
        // 该函数返回处理之后的尾节点
        if (!node) return node;
        Node * nxt = node->next;
        if (!nxt) return node;
        else return deal(nxt);
    }
    Node* flatten(Node* head) {
        deal(head);
        return head;
    }
}

该函数deal能够确保返回一个链表（不考虑child节点）的最后一个元素。

那么考虑完了没有child节点的情况，再来想一下初衷，为什么要获取一个链表的尾节点呢？很明显就是因为，child对于我们来说是一个插入的操作，不懂的可以看第一个示例和答案，也就是说，如果一个节点有child节点，那么就相当于要将child节点插入到本节点和本节点的next节点之间。因为这是双向链表，所以我们必须拿到四个关键节点（也就是本节点、本节点的next节点，child的头结点、child的尾节点）才能进行后续工作。其中前三个都很好获取，直接取就行，但是child的尾节点对我们来说不是很容易获得，所以我们就用deal来递归获取。

在deal(child->next)获取到child的尾指针之后，就进行拼接的工作，当然我们可以进行一个边界的判断，如果该指针本身就是一个尾指针，也就是说，如果该指针next为空，child非空，我们就可以将child直接接到该指针后面，而无需进行child尾部连接的工作。

C++代码

class Solution {
public:
    Node * deal(Node * node) {
        if (!node) return node;
        Node * nxt = node->next;
        if (node->child) {
            Node * cd = node->child;
            node->child = nullptr;
            node->next = cd;
            cd->prev = node;
            if (!nxt) {
                return deal(node->next);
            } else {
                Node * tail = deal(cd);
                tail->next = nxt;
                tail->next->prev = tail;
            }
            
        }
        if (!nxt) return node;
        else return deal(nxt);
    }
    Node* flatten(Node* head) {
        deal(head);
        return head;
    }
}

No.326 3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

-2³¹ <= n <= 2³¹ - 1

进阶：

你能不使用循环或者递归来完成本题吗？

思路分析

这题其实很简单，不管递归与否

递归就是常规想法，一直除3，如果除得只剩下1，那么就是3的幂次，如果还剩点别的就不是。

非递归也是常规想法，幂次有一个特性，就是它的因子包含比它更小（或者相等）的3的所有幂次。所以我们只需要选出来一个可能出现的最大的3的幂次N（在32位整数条件下为1162261467），判断给入的数字是否是N的因子，如果是，那么一定是3的幂次。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn is_power_of_three(n: i32) -> bool {
        if n % 3 == 0 && n != 0 {
            Self::is_power_of_three(n / 3)
        } else {
            n == 1
        }
    }
}
}

C++代码

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

No.725 分隔链表

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

示例 1：

输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
解释：
第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

示例 2：

输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]
解释：
输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。

提示：

链表中节点的数目在范围 [0, 1000]
0 <= Node.val <= 1000
1 <= k <= 50

思路分析

首先是肯定要获取链表的长度。毕竟这是一个划分链表的题目，要均分成k份，如果不知道链表的长度，肯定没法划分，所以必须得先遍历一遍获得链表的长度len。

在获取了len之后，必须在获取长度之后， $p a r tl e n = l e n / k$ ，这一句话的意思就是均分长度，但不考虑多余的部分，比如长度为10的分成3份，每一份的基础长度是3，余1，多出来的这个1加到了其中的一个3上，就变成了[4,3,3]这样的形式。余数在代码中就是remains这个变量。

然后思路就很明确了，为了方便实现了一个划分函数，干两件事，划分链表，返回划分后的链表和划分出来的部分链表。一个示例：原链表head是[1,2,3,4,5]， cut(head,3)之后返回[1,2,3]并且head变成了[4,5]。这么处理会在最终形成答案的时候比较方便。最后还要特判一下为空指针的情况，否则可能会出现错误。

C++代码

class Solution {
public:
    ListNode * cut(ListNode *& node, int cutlen) {
        ListNode * res = node;
        for (int i = 0; i < cutlen - 1; ++i) node = node->next;
        ListNode * hold = node;
        node = node->next;
        hold->next = nullptr;
        return res;
    }
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        if (!head) return vector<ListNode *>(k, nullptr);
        ListNode * cur = head;
        int len = 0;
        while (cur) {
            cur = cur->next;
            len++;
        }
        int partlen = len / k, remains = len - k * partlen, i = 0;
        vector<ListNode *> res(k);
        for (; i < remains; ++i) res[i] = cut(head, partlen + 1);
        for (; i < k; ++i) if (partlen) res[i] = cut(head, partlen);
        return res;
    }
};

No.1583 统计不开心的朋友

给你一份 n 位朋友的亲近程度列表，其中 n 总是偶数。

对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 0 到 n-1 之间的整数表示。

所有的朋友被分成几对，配对情况以列表 pairs 给出，其中 pairs[i] = [x_i, y_i] 表示 x_i 与 y_i 配对，且 y_i 与 x_i 配对。

但是，这样的配对情况可能会是其中部分朋友感到不开心。在 x 与 y 配对且 u 与 v 配对的情况下，如果同时满足下述两个条件，x 就会不开心：

x 与 u 的亲近程度胜过 x 与 y，且
u 与 x 的亲近程度胜过 u 与 v

返回 不开心的朋友的数目 。

示例 1：

输入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
输出：2
解释：
朋友 1 不开心，因为：
- 1 与 0 配对，但 1 与 3 的亲近程度比 1 与 0 高，且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心，因为：
- 3 与 2 配对，但 3 与 1 的亲近程度比 3 与 2 高，且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。

示例 2：

输入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
输出：0
解释：朋友 0 和 1 都开心。

示例 3：

输入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
输出：4

提示：

2 <= n <= 500
n 是偶数
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] 不包含 i
preferences[i] 中的所有值都是独一无二的
pairs.length == n/2
pairs[i].length == 2
x_i != y_i
0 <= x_i, y_i <= n - 1
每位朋友都恰好被包含在一对中

思路分析

首先我们要对给入的数据做一个预处理，因为我们在查询亲近程度的时候一定是希望给进两个人，给出一个亲近程度的指数。而题目给我们的数据非常不直观。所以我们可以拿一个二维数组来重新装一下。

let n = 10;
let preferences = vec![vec![3]];
let n = n as usize;
let mut pre = vec![vec![0; n]; n];
for i in 0..n {
    for j in 0..(n - 1) {
        pre[i][preferences[i][j] as usize] = n - j - 1;
    }
}

以上代码将preferences重新整合至pre。这样我们就能很方便的通过pre[i][j]的方式来查询了。

接下来我们仔细观察不开心的示例并且将其改写为代码
pre[x][u] > pre[x][y] && pre[u][x] > pre[u][v]
这个式子非常有意思，不难看出，在满足这个式子的时候，不仅x不满意，u也不满意。
再进一步观察又能发现，这个式子通过x和u是可以完全确定的。所以对于x,y,u,v四个变量来说，这样的两两组合一共有四对。

let (a, b, c, d) = (0, 0, 0, 0);
let pre = vec![vec![3]];
let mut set = std::collections::HashSet::new();
if pre[a][c] > pre[a][b] && pre[c][a] > pre[c][d] {
    set.insert(a);
    set.insert(c);
}
if pre[b][c] > pre[b][a] && pre[c][b] > pre[c][d] {
    set.insert(b);
    set.insert(c);
}
if pre[b][d] > pre[b][a] && pre[d][b] > pre[d][c] {
    set.insert(b);
    set.insert(d);
}
if pre[d][a] > pre[d][c] && pre[a][d] > pre[a][b] {
    set.insert(d);
    set.insert(a);
}

其中set是为了不重复而设置的哈希集合。（x,y,u,v为了方便写成了a,b,c,d）然后再对哈希表进行遍历并输出即可。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn unhappy_friends(n: i32, preferences: Vec<Vec<i32>>, pairs: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut pre = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..(n - 1) {
                pre[i][preferences[i][j] as usize] = n - j - 1;
            }
        }
        // println!("{:?}", pre);
        use std::collections::*;
        let mut set = HashSet::new();
        for i in 0..pairs.len() {
            for j in 0..pairs.len() {
                let a = pairs[i][0] as usize;
                let b = pairs[i][1] as usize;
                let c = pairs[j][0] as usize;
                let d = pairs[j][1] as usize;
                if pre[a][c] > pre[a][b] && pre[c][a] > pre[c][d] {
                    set.insert(a);
                    set.insert(c);
                }
                if pre[b][c] > pre[b][a] && pre[c][b] > pre[c][d] {
                    set.insert(b);
                    set.insert(c);
                }
                if pre[b][d] > pre[b][a] && pre[d][b] > pre[d][c] {
                    set.insert(b);
                    set.insert(d);
                }
                if pre[d][a] > pre[d][c] && pre[a][d] > pre[a][b] {
                    set.insert(d);
                    set.insert(a);
                }
            }
        }
        set.len() as i32
    }
}
}

No.233 数字1的个数

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

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

0 <= n <= 2 * 10⁹

思路分析



令a=n/i,b=n%i;
举例分析，假设n=12345，i=100; 此时a=123,b=45：
1）当a的个位大于1时（也就是n的百位），百位为1的数总共出现了(a/10+1)*100次
2）当a为1的时候，百位为1的数总共出现了(a/10)*100+(b+1);
3）当a为0的时候，百位为1的数出现了(a/10)*100次；
因此可以根据a的个位是否为1分成2中情况计算，可以使用一个表达式合并以上三个式子。
a.   9=>(a个位)>=2和0=<(a个位<=1)时的(a/10+1),(a/10)表达式与(a+8)/10等价；
b.  （a>=2时（a+8）/10的结果与a/10+1相同，a==1或a==0时（a+8）/10的结果等价a/10。
c.   当a个位为1时需要加上（b+1）与(a%10==1)*(b+1)等价。因此合并后百位为1的数的个数为
(a+8)/10*i+(a%10==1)*(b+1);
然后令i从个位到最高位遍历即可计算每一位含1的个数；

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn count_digit_one(n: i32) -> i32 {
        let mut cnt = 0;
        let mut i = 1;
        while i <= n {
            let a = n / i;
            let b = n % i;
            cnt += (a + 8) / 10 * i + if a % 10 == 1 {b + 1} else {0};
            i *= 10;
        }
        cnt
    }
}
}

No.516 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

思路分析

其实有一个非常关键的思路。就是
字符串s的最长回文子序列等价于字符串s和s的倒序s'的最长公共子序列

简单的证明，s与s倒序的最长公共子序列一定是回文的。正着有，反着有，且相同，这就是回文的定义。
也不会有比s与s倒序的最长公共子序列更长的回文子序列了。如果有，那么s与s倒序的最长公共子序列也会变得更长。

所以我们成功的将题目转化为求s与s倒序的最长公共子序列的长度。

既然是这样，就非常方便了。直接使用二维动态规划即可轻松求解。首先设置动态规划变量dp[n+1][n+1](预留一个空位方便计算)。

再说dp[i][j]的含义，就是s中前i位与s'中前j位的最长公共子序列。

动态规划的递推式也非常好思考。只要遇到了两个相同的字符，dp[i][j] = dp[i - 1][j - 1] + 1
否则，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn longest_palindrome_subseq(s: String) -> i32 {
        let s = s.into_bytes();
        let n = s.len();
        let mut res = 0;
        let mut dp = vec![vec![0; n + 1]; n + 1];
        for i in 1..=n {
            for j in 1..=n {
                if s[n - i] == s[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
                }
            }
        }

        dp[n][n]
    }
}
}

No.446 等差数列划分 II - 子序列

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

示例 1：

输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：

输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

提示：

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1

思路分析

本题与昨天的题目几乎完全一致。唯一有区别的地方就是将子数组改成了子序列。
但这个改动可不是小小的改动，我们之前的思考在这里几乎不会有什么用处。

子序列是没有连续性的，也就是说，对于任意一些有先后顺序但是没有邻接顺序的数字，只要他们满足差值是一个恒定的数，他们就是合法的等差子序列。

首先要理解题目，才有可能做出来。

那么对于子序列，我们能想到的除了暴力还有别的办法吗？
其实答案很简单，我们只需要去提炼一下规律，一个可以总结的规律。
比如在这一题中，如果我们知道[.....,2,4,6]是一个等差数列，那么4前面的东西有多少位与我们并无关系，也就是说，对于后面的数字来说，我们并不关心2前面有几位，因为都是差为2的等差数列。

那么整个数据结构的雏形就出来了，首先外层是一个从前向后的遍历，每一步都会对自己及之前的东西做一个记录，方便后续使用。
记录的这个东西，肯定是基于等差数列的差来记录的，我们就使用一个HashMap<i32,?>来记录，那么记录的内容是什么呢？
为了后续使用，我们肯定要想记录数量，也就是合法的等差子序列的数量，但是这里又出现了一个问题，长度问题。

长度是一个很关键的点，如果我们记录的是长度为2的，就有可能多算；我们也没有办法只记录长度大于等于3的，因为这必定是基于长度为2的才能推得
在这种情况下，我们使用了HashMap<i32, (i32, i32)>的数据结构。这样可以用前面的i32来记录长度大于等于3的，后面的来记录长度等于2的。

但这里还有一个坑点需要注意，我相信大家也都没发现：

-2³¹ <= nums[i] <= 2³¹ - 1

这个条件直接导致我们在计算两位之差的时候需要使用比i32更大的数据，否则会溢出。所以我们改用了i64。

然后我们写出了第一版本的代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        use std::collections::*;
        let mut dp: Vec<HashMap<i64, (i32, i32)>> = vec![];
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            let mut nxt = HashMap::new();
            for j in 0..i {
                let diff = nums[i] as i64 - nums[j] as i64;
                if let Some(value) = dp[j].get(&diff) {
                    nxt.entry(diff).or_insert((0, 0)).0 += value.0 + value.1;
                    res += value.0 + value.1;
                }
                nxt.entry(diff).or_insert((0, 0)).1 += 1;
            }
            dp.push(nxt);
        }
        res
    }
}
}

dp是一个包含每一个位所有信息的一个总和。在对nums进行遍历的同时，记录所有数据。

nxt.entry(diff).or_insert((0, 0)).1 += 1;
这句话的意思就是对于所有在i前面的nums[j]都可以与nums[i]组成一个长度为2的组合。所以加到了后面的位。 nxt.entry(diff).or_insert((0, 0)).0 += value.0 + value.1;
这句话的意思是如果j位置之前出现过长度大于3或者长度等于2的，再与nums[i]进行搭配，一定会得到一个长度大于等于3的子序列，那么我们就将其加到前面的位上，并且加到答案上。

这段代码是可以通过的，但是我们发现一个要点。在我们使用(i32, i32)时，总是使用它们的和。代码中出现的只有value[0] + value[1]。那么我们是否可以考虑将其合并？

其实也是可以的。合并之后的含义就变化了，HashMap<i64, i32>表示的就是一个特定的diff下长度大于等于2的所有子序列数量。而最令人震惊的是这好像不影响计算。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        use std::collections::*;
        let mut dp: Vec<HashMap<i64, i32>> = vec![];
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            let mut nxt = HashMap::new();
            for j in 0..i {
                let diff = nums[i] as i64 - nums[j] as i64;
                if let Some(value) = dp[j].get(&diff) {
                    *nxt.entry(diff).or_insert(0) += value;
                    res += value;
                }
                *nxt.entry(diff).or_insert(0) += 1;
            }
            dp.push(nxt);
        }
        res
    }
}
}

看到了吗？其实答案就是我们在读取前一位的长度为2的子序列的时候，加上这一位一定大于等于3了，所以我们多虑了！
但你要是不试你永远也不知道自己多虑了。 😂

No.413 等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1]
输出：0

提示：

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000

思路分析

子数组一定是在原数组中连续的，所以我们关心的只有原数组中的两两之差。所以可以预处理一下，开一个新的数组存相邻数字的差。
先来思考一个问题，什么样的才能构成等差数列。
答案：字面意思，差相等。那么如果出现连读多个差相等的情况该怎么办呢

根据示例可见，如果出现多个连续的差相等的情况，其实是比较类似排列组合的一个选择，比如[1,2,3,4]和[1,2,3]、[2,3,4]都是合法答案。如果连续四个数（也就是连续三个缝隙）差相等，就存在三种情况。如果连续n个数字呢？

1.先假设存在n个可以构成等差数列的数字
例如：1,2,3,4,5,6,7,.....,n（刚好n个）
2.因为最短需要长度为3的子数组，所以长度为3的有n - 2个
3.长度为t的子数组（t<n）有n - t + 1个
4.总共有(n-2)+(n-3)+....+(1)个
还是4.所以总共有(n-2)*(n-1)/2个

但对于我们来说，计算哪几个数在同一个等差数列很困难，而且存在交叉公用的情况，比如[1,2,3,2,1]中的3，就可能是两个子数组公用的数。
所以我们用缝隙来处理，先计算出两两之差（即缝隙），再比较。
将[1,2,3,2,1]处理成[1,1,-1,-1]这样，只要出现两个连续的缝隙，我们就认为可以组成子数组。
这样也很巧妙地处理了公用数字的情况。

那么思路就非常清晰了，我们只需要遍历一遍数组，只关心缝隙，在缝隙连续出现的时候统计，最多连续出现n个缝隙，然后再将答案加上n*(n-1)即可

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = 0;
        let mut pre = i32::MAX;
        let mut count = 0;
        for i in 1..n {
            let item = nums[i] - nums[i - 1];
            if pre != item {
                if count > 1 {
                    res += count * (count - 1) / 2;
                }
                pre = item;
                count = 1;
            } else {
                count += 1;
            }
        }
        if count > 1 {
            res += count * (count - 1) / 2;
        }
        res
    }
}
}

No.313 超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32 
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

提示：

1 <= n <= 10⁶
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列

思路分析

题目的意思还是比较好理解的，我们需要列出来一个列表（的前n项），这个列表里包括了所有的超级丑数，而我们关心的就是只有第n个超级丑数。列这个表有许多种思路。比较常见的是优先队列的思路。

优先对列是一个特殊的数据结构，它能保证在其中的所有数字都是有序的。既然如此，我们可以维护一个优先队列，原始值为[1]，并对它进行n次如下操作:

    1.在第n次的时候，从优先队列中取出一个最小的数字t
    2.t即为第n个超级丑数
    3.将t * primes[0], t * primes[1], .....等数字放入优先队列中。
    4.这样就能保证所有超级丑数都曾经被加入过该优先队列，而且因为我们是按照从小到大的顺序取的，所以第二条成立

按照这个思路，我们可以在 $O (n * p r im es . l e n g t h * l o g_{2} (n * p r im es . l e n g t h))$ 的复杂度内计算出第n个超级丑数。

Rust代码


#![allow(unused)]
fn main() {
use std::collections::*;
struct Solution;
impl Solution {
    pub fn nth_super_ugly_number(mut n: i32, primes: Vec<i32>) -> i32 {
        let mut set = BTreeSet::new();
        set.insert(1);
        while set.len() > 0 {
            let first = *set.iter().next().unwrap();
            set.remove(&first);
            for &prime in &primes {
                if (first as i64) * (prime as i64) < (i32::MAX as i64) {
                    set.insert(first * prime);
                }
            }
            n -= 1;
            if n == 0 {
                return first;
            }
        }
        0
    }
}
}

进阶方法

思路

不难看出，超级丑数数列中的所有项都可以表示为 primes中的一个数和另一个在其之前出现的超级丑数的乘积。
看懂了上面的那个方法之后，也可以看出，我们再每一步将一个超级丑数取出来，乘了一个primes中的数字，再放回到超级丑数的序列中作为候选。
但这样会出现许多冗余和不必要的计算。
比如超级丑数的数列过长，而我们需要的可能只是前几项。
这促使我们找到一个新的方法来计算
因此，我们设立一个新的数组pointer，其中的每一项和primes中的每一项都对应，且初值均为0。在这种情况下，我们也需要将丑数记录在一个名为dp的数列里
在每一次循环中做如下的工作

1.计算出当前最小候选超级丑数的值
2.具体的流程为求 dp[pointer[i]] * primes[i] 的最小值(i的取值范围就是primes的长度m)
3.该数即为下一个超级丑数 dp_nxt
4.对于所有项 dp[pointer[i]] * primes[i] == dp_nxt 的i，均使 pointer[i] 增加1

再理一遍思路，所有超级丑数都是由之前出现过的一个超级丑数乘上primes中的一个数可以获得的。而现在pointer指示的就是之前出现过的超级丑数的位置。
可能出现重复的情况，比如2*9和6*3都会获得18，也就是说为什么对于所有符合最小值的项均需在pointer加1。
按照这种遍历方式，可以从小到大完全遍历所有可能出现的超级丑数，并且省去了很多无效计算。
按照这个思路，我们可以在O(n * primes.length)的时间内完成所有的计算。


#![allow(unused)]
fn main() {
use std::collections::*;
struct Solution;
impl Solution {
    pub fn nth_super_ugly_number(n: i32, primes: Vec<i32>) -> i32 {
        let mut dp = vec![1];
        let n = n as usize;
        let m = primes.len();
        let mut pointer = vec![0; m];
        while dp.len() < n {
            let mut min_pos = 0;
            for i in 1..m {
                if dp[pointer[i]] * primes[i] < dp[pointer[min_pos]] * primes[min_pos] {
                    min_pos = i;
                }
            }
            let tmp = dp[pointer[min_pos]] * primes[min_pos];
            dp.push(tmp);
            for i in 0..m {
                if dp[pointer[i]] * primes[i] == tmp {
                    pointer[i] += 1;
                }
            }
        }
        println!("{:?}", dp);
        dp[n - 1]
    }
}
}

No.1137 第N个泰波那契数

泰波那契序列 T_n 定义如下：

T₀ = 0, T₁ = 1, T₂ = 1, 且在 n >= 0 的条件下 T_n+3 = T_n + T_n+1 + T_n+2

给你整数 n，请返回第 n 个泰波那契数 T_n的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

0 <= n <= 37
答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

思路分析

通过观察，发现题目要求的是一个数列的和。而且这个数列可以通过前面的3项来计算得到后面的一项。因此我们可以用最简单的暴力算法来做。也就是我们新建一个数组，里面有固定的三项[0,1,1]。这是题目中给我们的条件，然后我们根据给入的n去计算到我们需要的地方，就可以获得第 N 个泰波那契数了

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn tribonacci(n: i32) -> i32 {
        let n = n as usize;
        let mut v = vec![0, 1, 1];
        let mut cur_len = 3;
        while cur_len <= n {
            v.push(v[cur_len - 1] + v[cur_len - 2] + v[cur_len - 3]);
            cur_len += 1;
        }
        v[n]
    }
}
}

运行效果

fn main() {
pub fn tribonacci(n: i32) -> i32 {
   let n = n as usize;
   let mut v = vec![0, 1, 1];
   let mut cur_len = 3;
   while cur_len <= n {
       v.push(v[cur_len - 1] + v[cur_len - 2] + v[cur_len - 3]);
       cur_len += 1;
   }
   v[n]
}
println!("{:?}", tribonacci(2));
}

LeetCode Solution - 力扣题解