讲解来自 CSDN 和 jyd - 力扣（LeetCode）
一、动态规划
1.最大连续子序列和（LCS）
PTA 1007 Maximum Subsequence Sum
#include<iostream>
using namespace std;
#include<vector>
int main() {
int n;
cin>>n;
vector<int> v(n);
int temp=0,lindex=0,rindex=n-1,tempindex=0,sum=-1;
for(int i=0;i<n;i++){
cin>>v[i];
temp+=v[i];
if(temp<0){ //注意当temp<0的时候不需要更新，因为为0时不会影响sum值，所以不需要更新tempindex
temp=0;
tempindex=i+1;//保存小于0的下标，当由小于0进入大于0时，将这个下标赋值给rindex
}else if(temp>sum){
sum=temp;
//注意范围操作
lindex=tempindex;
rindex=i;
}
}
//如果sum<0，序列和结果输出为0
if(sum<0) sum=0;
cout<<sum<<" "<<v[lindex]<<" "<<v[rindex];
return 0;
}
递推公式：
int maxSubArray(vector<int>& nums) {
int max_sum = nums[0];
for(int i = 1; i < nums.size(); i++){
nums[i] +=max(nums[i - 1], 0);
max_sum = max(nums[i], max_sum);
}
return max_sum;
}2.最长不下降子序列（LIS）
PTA 1045 Favorite Color Stripe
题解：解题思路参考
#include<bits/stdc++.h>
using namespace std;
int n, m, l, ans = INT_MIN;
vector<int>book;
vector<int>org;
int main(){
cin>>n;
cin>>m;
book.resize(n+1);
for(int i=1;i<=m;i++){
int color;
cin>>color;
//记录不同颜色的喜爱程度（顺序）
book[color]=i;
}
cin>>l;
for(int i=0;i<l;i++){
int color;
cin>>color;
//判断是否是喜欢的颜色
if(book[color]>0) org.push_back(book[color]);
}
//最长不减子序列
int size = org.size();
vector<int>dp(size);
for(int i=0;i<size;i++)
{
dp[i]=1;
for(int j=0;j<i;j++){
if(org[i]>=org[j]){
dp[i]=max(dp[i], dp[j]+1);
}
}
ans=max(ans, dp[i]);
}
cout<<ans<<endl;
return 0;
}算法举例：
(2 7 1 5 6), 分别对应 (a1, a2, a3, a4, a5)
初始状态下，dp[i]均赋值为1：
递推、更新：
a1 = 2, dp[1] = 1 -->(2)
a2 = 7，对之前元素循环，发现：a1<a2，则dp[2]=max(dp[2], dp[1]+1)=2 -->(2 7)
a3=1，对之前元素循环，发现：均大于a3，则dp[3]=dp[3]=1 -->(1)
a4=5，对之前元素循环，发现：a1<a4，则dp[4]=max(dp[4], dp[1]+1)=2 -->(2 5)
a3<a4，则dp[4]=max(dp[4], dp[3]+1)=2 -->(1 5)
a5=6，对之前元素循环，发现：a1<a5，则dp[5]=max(dp[5], dp[1]+1)=2 -->(2 6)
a3<a5，则dp[5]=max(dp[5], dp[3]+1)=2 -->(1 6)
a4<a5，则dp[5]=max(dp[5], dp[4]+1)=3 -->(2/1 5 6)
for (int i = 0; i < size; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (data[i] >= data[j]) {//不降序
dp[i] = max(dp[j] + 1, dp[i]);
}
}
ans = max(ans, dp[i]);
}3.最长回文子串
PTA 1040 Longest Symmetric String
状态转移方程：
边界条件：
1）仅求长度：
首先初始化dp[i][i] = 1, dp[i][i+1]，把长度为1和2的都初始化好，然后从L = 3开始一直到 L <= len 根据动态规划的递归方程来判断
for(int i=0;i<len;++i){
dp[i][i] = 1;
if(i<len-1){
if(str[i]==str[i+1]){
dp[i][i+1] = 1;
ans = 2;
}
}
}
for(int L=3;L<=len;++L){
for(int i=0;i+L-1<len;++i){
int j = i+L-1;
if(str[i]==str[j] && dp[i+1][j-1]==1){
dp[i][j] = 1;
ans = L;
}
}
}2）求回文子串：
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
vector<vector<int>> dp(n, vector<int>(n));
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;//对角线
}
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= n; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < n; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= n) {
break;
}
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxLen);
}
};
""作者：LeetCode-Solution
链接：https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。""4.背包问题
1）算法&代码：
int maxValue(int[] weight, int[] value, int W) {
int n = weight.length;
if (n == 0) return 0;
int[][] dp = new int[n][W + 1];
// 先初始化第 0 行，也就是尝试把 0 号物品放入容量为 k 的背包中
for (int k = 1; k <= W; k++) {
if (k >= weight[0]) dp[0][k] = value[0];
}
for (int i = 1; i < n; i++) {
for (int k = 1; k <= W; k++) {
// 存放 i 号物品（前提是放得下这件物品）
int valueWith_i = (k-weight[i] >= 0) ? (value[i] + dp[i-1][k-weight[i]]) : 0;
// 不存放 i 号物品
int valueWithout_i = dp[i-1][k];
dp[i][k] = Math.max(valueWith_i, valueWithout_i);
}
}
return dp[n-1][W];
}2）压缩空间
int maxValue(int[] weight, int[] value, int W) {
int n = weight.length;
if (n == 0) return 0;
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
//只要确保 k>=weight[i] 即可，而不是 k>=1，从而减少遍历的次数
for (int k = W; k >= weight[i]; k--) {
dp[k] = Math.max(dp[k - weight[i]] + value[i], dp[k]);
}
}
return dp[W];
}3）物品重量=价值
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int dp[10100], w[10100];//dp[i]为背包大小为i时的价值和，w为物品重量
bool choice[110][10100];//choice[j][i]，容量为j时，是否存放了i物品
int cmp(int a, int b){
return a>b;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i];
}
sort(w+1, w+1+n, cmp);//将物品从大到小排序
for(int i=1;i<=n;i++){//针对每个物品
for(int j=m;j>=w[i];j--){//只考虑物品重量小于总容量的情况
if(dp[j]<=dp[j-w[i]]+w[i]){//不放入i<=放入i
choice[j][i]=true;
dp[j]=dp[j-w[i]]+w[i];
}
}
}
if(dp[m]!=m) cout<<"No Solution"<<endl;
else{//回溯物品
vector<int> arr;
int v=m, index = n;//从小物品开始
while(v>0){
if(choice[v][index]==true){
arr.push_back(w[index]);
v-=w[index];
}
index--;
}
for(int i=0;i<arr.size();i++){
if(i) cout<<" ";
cout<<arr[i];
}
cout<<endl;
}
}5.正则表达式
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
思路：官方详细解析
f[i][j] 表示 s的前 i 个字符与 p 中前 j 个字符是否匹配：
- 若 p 的第 j 个字符是小写字母：
- 若 p 的第 j 个字符是 * ，
- 匹配0次：（浪费了一个字符+星号）
- 匹配 1,2,3,...次：
......
状态转移：
代码：
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
auto matches = [&](int i, int j) {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
}
return s[i - 1] == p[j - 1];
};
vector<vector<int>> f(m + 1, vector<int>(n + 1));
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
f[i][j] |= f[i][j - 2];
if (matches(i, j - 1)) {
f[i][j] |= f[i - 1][j];
}
}
else {
if (matches(i, j)) {
f[i][j] |= f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
};6.简单应用
1）斐波那契数列
法一：简单递归
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}法二：动态规划
int fib(int n) {
int MOD = 1000000007;
if(n < 2) return n;
int p = 0, q = 0, r = 1;
for(int i = 2; i <= n; i++)
{
p = q;
q = r;
r = (p + q) % MOD;
}
return r;
}2）青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
思路：jyd大神解析
青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。
当为 1 级台阶： 剩 n-1 个台阶，此情况共有 f(n-1) 种跳法；
当为 2 级台阶： 剩 n-2 个台阶，此情况共有 f(n-2) 种跳法。
代码：
int numWays(int n) {
if(n==0||n==1) return 1;
int p=0,q=1,r=1;
int MOD = 1000000007;
for(int i=2;i<=n;i++)
{
p=q;
q=r;
r=(p+q)%MOD;
}
return r;
}Tips：
青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 ；
斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。
3）股票的最大利润
把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
递推公式：
代码：
int maxProfit(vector<int>& prices) {
int minprice = 1e9, maxprofit = 0;
for(int price : prices){
maxprofit = max(maxprofit, price - minprice);
minprice = min(price, minprice);
}
return maxprofit;
}4)礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
递推公式：
代码：
int maxValue(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for(int j = 1; j <n; j++){
//初始化第一行
grid[0][j] +=grid[0][j - 1];
}
for(int i = 1; i < m; i++){
//初始化第一列
grid[i][0] +=grid[i - 1][0];
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
grid[i][j] += max(grid[i][j - 1], grid[i - 1][j]);
}
}
return grid[m - 1][n - 1];//右下角
}5）把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
递推公式：
初始状态：
代码：
int translateNum(int num) {
int m=1,n=1;
while(num>9){
int t = (num%100>9 && num%100<26)?(m+n):n;
m=n;
n=t;
num/=10;
}
return n;
}6)最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
递推公式：
代码：
法一：动态规划 + 哈希表
int lengthOfLongestSubstring(string s) {
int len = s.size();
if(len==0) return 0;
unordered_map<char,int> hash;
int max_len=0,sub_len=0;
for(int right=0;right<len;right++){
int left=hash.find(s[right])!=hash.end()?hash[s[right]]:-1;
hash[s[right]]=right;
sub_len = (sub_len<(right-left))?(sub_len+1):(right-left);
max_len = max(max_len,sub_len);
}
return max_len;
}法二：双指针 + 哈希表
int lengthOfLongestSubstring(string s) {
int len = s.size();
if(len==0) return 0;
vector<int> hash(128,-1);
int left = 0;
int max_len = 0;
for(int right=0;right<len;right++){
if(hash[s[right]] != -1){
left= max(left, hash[s[right]] + 1);
}
hash[s[right]]=right;
max_len = max(max_len,right-left + 1);
}
return max_len;
}7）丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
递推：
代码：
class Solution {
public:
int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int dp[n];
dp[0] = 1;
for(int i = 1; i < n; i++) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = min(min(n2, n3), n5);
if(dp[i] == n2) a++;
if(dp[i] == n3) b++;
if(dp[i] == n5) c++;
}
return dp[n - 1];
}
};
8)n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
递推：
代码：
class Solution {
public:
vector<double> dicesProbability(int n) {
//原本dp[i][j]表示的是前i个骰子的点数之和为j的概率
//现在只需要最后的状态的数组，所以就只用一个一维数组dp[j]表示n个骰子下每个结果的概率
//初始是1个骰子情况下的点数之和情况，就只有6个结果，所以用dp的初始化的size是6个
vector<double> dp(6, 1.0 / 6.0);
//从第2个骰子开始，这里n表示n个骰子，
//先从第二个的情况算起，然后再逐步求3个、4个···n个的情况
for(int i = 2; i <= n; i++){
//点数之和的值最大是i*6，最小是i*1
//点数之和的值的个数是6*i-(i-1)，化简：5*i+1
vector<double> tmp(5 * i + 1, 0);
//从i-1个骰子的点数之和的值数组入手，计算i个骰子的点数之和数组的值
//先拿i-1个骰子的点数之和数组的第j个值，它所影响的是i个骰子时的tmp[j+k]的值
for(int j = 0; j < dp.size(); j++){
//比如只有1个骰子时，dp[1]是代表当骰子点数之和为2时的概率
//它会对当有2个骰子时的点数之和为3、4、5、6、7、8产生影响，因为当有一个骰子的值为2时，另一个骰子的值可以为1~6，产生的点数之和相应的就是3~8
for(int k = 0; k < 6; k++){
//这里记得是加上dp数组值与1/6的乘积，1/6是第i个骰子投出某个值的概率
tmp[j + k] += dp[j] / 6.0;
}
}
dp = tmp;
}
return dp;
}
};二、分治算法
1.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
代码：
class Solution {
public:
unordered_map<int, int> map;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0; i < inorder.size(); i++){
//构建中序序列 值-位置 的索引
map[inorder[i]] = i;
}
//递归参数包括：前序序列、中序序列、前序根节点位置、中序左边界、中序右边界
return build(preorder, inorder, 0, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preroot, int inleft, int inright){
//终止条件
if(inleft > inright) return nullptr;
//新建根节点
TreeNode* root = new TreeNode(preorder[preroot]);
//中序根节点位置
int inroot = map[preorder[preroot]];
//开启左子树递归
//左子树在前序中的根节点位于preroot+1
root->left = build(preorder, inorder, preroot + 1, inleft, inroot - 1);
//开启右子树递归
//右子树在前序中的根节点位于：根+左子树长度
root->right = build(preorder, inorder, preroot + (inroot - inleft + 1), inroot + 1, inright);
return root;
}
};2.数值的整数次方
计算 x 的 n 次幂函数。不得使用库函数，同时不需要考虑大数问题。
举例：
| 循环 | |
| 第0轮 | |
| 第1轮 | |
| 第2轮 | |
| 第3轮 | |
| 返回 |
代码：
double myPow(double x, int n) {
long long b = n; // int范围是[-2^31，2^31-1]，很明显不对称。当 n = -2^31 时，-n就得不到2^31，因此要用longlong来保存n
double res = 1.0; // 结果为double类型，初始值为1.0（因为要用res去乘）
while (b) { // 指数b为0时退出循环
if (b < 0) { // b<0，转换一下
x = 1 / x; // 底数为原来的倒数
b = -b; // 指数为原来的相反数
}
if (b & 1 == 1) {
res = res * x; // 当指数b为奇数时，会提出底数x，最终结果res就是 将所有提出的底数x相乘
}
x = x * x; // 每一轮的底数x = x^2
b >>= 1; // 每一轮指数b = b/2
}
return res;
}3.二叉搜索树的后序遍历
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
法一：递归分治
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
return recur(postorder, 0, postorder.size() - 1);
}
bool recur(vector<int>& postorder, int i, int j){
//终止条件
if(i >= j) return true;
int p = i;
//找到第一个大于根节点的位置
//在这之前均属于左子树
while(postorder[p] < postorder[j]) p++;
//记录左子树的结束位置
int m = p;
//开始判断右子树
//是否均大于根节点
while(postorder[p] > postorder[j]) p++;
//分别递归左右子树
return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
}
};
法二：辅助单调栈（目前没太弄明白）
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
stack<int> stk;
int root = 2147483647;
for(int i = postorder.size() - 1 ; i >= 0 ; i--)
{
if(postorder[i] > root) return false;
while(!stk.empty() && stk.top() > postorder[i])
{
root = stk.top();
stk.pop();
}
stk.push(postorder[i]);
}
return true;
}
};4.打印从1到最大的n位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
代码：
class Solution {
private:
vector<int> nums;
string s;
public:
vector<int> printNumbers(int n) {
s.resize(n, '0');
dfs(n, 0);
return nums;
}
//枚举所有情况
void dfs(int end, int index){
if(index == end){
save();
return;
}
for(int i = 0; i <= 9; i++){
s[index] = i + '0';
dfs(end, index + 1);
}
}
//去除首部0
void save(){
int ptr = 0;
while(ptr < s.size() && s[ptr] == '0') ptr++;
if (ptr != s.size())
// emplace_back() ，和 push_back() 一样的是都是在容器末尾添加一个新的元素进去
// 不同的是 emplace_back() 在效率上相比较于 push_back() 有了一定的提升
nums.emplace_back(stoi(s.substr(ptr)));
}
};5.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
思路：（归并排序）K神解析
- 终止条件：当 l ≥ r 时，代表子数组长度为1
- 递归划分：左、右子数组
- 合并与逆序对统计：i, j 分别指向左右子数组的首元素
当 tmp[i]≤tmp[j] 时： 添加左子数组当前元素 tmp[i] ，并执行 i = i + 1；
否则（即 tmp[i] > tmp[j]）时： 添加右子数组当前元素 tmp[j] ，并执行 j = j + 1 ；此时构成 m - i + 1 个「逆序对」，统计添加至 res
代码：
class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<int> tmp(nums.size());
return mergeSort(0, nums.size() - 1, nums, tmp);
}
private:
int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp){
//终止条件
if(l >= r) return 0;
//递归划分
int m = (l + r) / 2;
int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);
//合并阶段
//分别指向左右子数组的首元素
int i = l, j = m + 1;
//暂存元素至辅助数组
for(int k = l; k <= r; k++) tmp[k] = nums[k];
for(int k = l; k <= r; k++) {
if(i == m + 1){
//代表左子数组已经合并完
//添加右子数组
nums[k] = tmp[j++];
}
else if (j == r + 1 || tmp[i] <= tmp[j]){
//右子数组已经合并完 或者左<右
//添加左子数组
nums[k] = tmp[i++];
}
else{
nums[k] = tmp[j++];
//统计逆序对
res += m - i + 1;
}
}
return res;
}
};三、双指针
1.链表
1）链表中倒数第k个结点
思路：
- 构建双指针距离k：前指针先走k步
- 双指针共同移动：直至前指针到达尾结点
代码：
ListNode* getKthFromEnd(ListNode* head, int k) {
if(head == NULL) return nullptr;
ListNode* former = head;
ListNode* latter = head;
for(int i = 0; i < k; i++){
former = former -> next;
}
while(former != NULL){
former = former -> next;
latter = latter -> next;
}
return latter;
}2）合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* ans = new ListNode(0);
ListNode* p = ans;
while(l1 && l2){
(l1->val < l2->val) ? (p->next = l1, l1 = l1->next) : (p->next = l2, l2 = l2->next);
p = p->next;
}
p->next = l1 ? l1 : l2;
return ans->next;
}3）两个链表的第一个公共结点
思路：jyd大神讲解
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到公共结点时，共走步数为：
a + (b - c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到公共结点时，共走步数为：
b + (a - c)
如下式所示，此时指针 A , B 重合，并有两种情况：
a + (b - c) = b + (a - c)
- 若两链表 有 公共尾部 (即 c > 0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
- 若两链表 无 公共尾部 (即 c = 0 ) ：指针 A , B 同时指向 null。
代码：
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *A = headA;
ListNode *B = headB;
while(A != B){
A = (A == nullptr) ? (headB) : (A->next);
B = (B == nullptr) ? (headA) : (B->next);
}
return A;
}2.数组
1）使奇数位于偶数前面
vector<int> exchange(vector<int>& nums) {
int i = 0,j = nums.size()-1;
while(i < j){
while(i < j && ((nums[i] & 1) == 1)) i++;
while(i < j && ((nums[j] & 1) == 0)) j--;
swap(nums[i], nums[j]);
}
return nums;
}2）和为s的两个数字
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l < r){
if(nums[l] + nums[r] < target) l++;
if(nums[l] + nums[r] > target) r--;
if(nums[l] + nums[r] == target) break;
}
vector<int> ans;
ans.push_back(nums[l]);
ans.push_back(nums[r]);
return ans;
}3.字符串
- 倒序遍历字符串，记录单词左右索引边界 i , j ；
- 每确定一个单词的边界，则将其添加至单词列表 ；
- 最终，将单词列表拼接为字符串，并返回即可。
string reverseWords(string s){
string ans = "";
int n = s.size();
for(int l = n - 1; l >= 0; l--){
//从尾部开始循环
if(s[l] != ' '){//找到一个非空字符
int r = l;//记录这个单词的右边起始位置
while(s[l] != ' ' && l >=0){//单词的左边界
l--;
if(l == -1) break;//找到头了
}
//添加单词
ans += s.substr(l + 1, r - l) + " ";
}
}
//去掉最后一个空字符
return ans.substr(0, ans.size() - 1);
}四、图算法
1.图的遍历
1）DFS -- 计算连通块数
结论：连通分量的个数就是DFS使用的次数
题意：题目讲解
输入n,m,k三个数，n表示城市的个数（默认编号1~N）,m表示边数（无向边），k表示要查询的城市数。然后m行输入边的两个顶点，最后一行输入K个检查的城市结点。
对于每个输入的城市，表示该城市被敌军占领，切断所有该城市与其它城市的路径，要求需要新建多少条路径，才能使得除了该城市以外的城市之间能够畅通无阻地联系。
思路：
路径数 = 剩下的总连通块数 - 1
代码：
#include<iostream>
using namespace std;
const int maxn = 1010;
const int INF = 1e9;
int G[maxn][maxn] = {0};
bool flag[maxn];
int n, m, k;
void dfs(int u){
flag[u] = true;//访问u结点
for(int v = 1; v <=n; v++){
if(!flag[v] && G[u][v] > 0){
//没访问过，且uv之间有边连接
dfs(v);
}
}
}
int main(){
cin >> n >> m >> k;
int a, b, check;
for(int i = 1; i <=m; i++){
cin >> a >>b;
G[a][b] = G[b][a] = 1;
}
for(int i = 1; i<=k; i++){
fill(flag, flag + maxn, 0);
cin >> check;
flag[check] = true;
int cnt = 0;//连通分量数
for(int j = 1;j <=n; j++){
if(!flag[j]){
dfs(j);
cnt++;
}
}
cout << cnt - 1 << endl;
}
return 0;
}2）DFS -- 记录深度
题意：
给出n个结点（1~n）之间的n条边，问是否能构成一棵树，如果不能构成则输出它有的连通分量个数，如果能构成一棵树，输出能构成最深的树的高度时，树的根结点。如果有多个，按照从小到大输出。
代码：
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
const int maxn = 10010;
vector<int> G[maxn];
bool visited[maxn];
int n;
int deep[maxn];
int maxdep = 0;
void dfs(int u, int depth){
maxdep = max(depth, maxdep);
visited[u] = 1;
for(int i = 0; i < G[u].size(); i++)
if(visited[G[u][i]] == 0)
dfs(G[u][i], depth+1);
}
int DFSTrave(){
int Count = 0;
for(int u = 1; u <= n; u++){
if(visited[u] == 0){
dfs(u, 1);
Count++;
}
}
return Count;
}
int main()
{
cin >> n;
for(int i =0; i < n; i++){
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
int Count = DFSTrave();
if(Count == 1){
int maxdepth = 0;
for(int u = 1; u <= n; u++){
fill(visited, visited + maxn, 0);
maxdep = 0;
dfs(u, 1);
deep[u] = maxdep;
if(deep[u] > maxdepth)
maxdepth = deep[u];
}
for(int i = 1; i < maxn; ++i)
if(deep[i] == maxdepth) cout << i << endl;
}
else printf("Error: %d components\n", Count);
}
3）DFS -- 权值最大结点
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int n, k;
int w[maxn] = {0};//边的权值
map<string,int> str2int;
map<int,string> int2str;
int num = 0;//记录结点种类
int f_str2int(string s)
{
if(str2int.find(s)!=str2int.end())//找到
return str2int[s];
else{//找不到，新建索引关系
str2int[s] = num;
int2str[num] = s;
return num++;
}
}
int G[maxn][maxn] = {0};
bool visited[maxn] = {false};
//犯罪团伙成员，团伙数，头目的权重
int Gangnum = 1, Count = 0, sum_weight = 0;
int root, maxw = 0;//头目和最大权重
//寻找犯罪头目函数
string DFS(int u, int depth)
{
visited[u] = true;
for(int v = 0; v < n; v++){
if(G[u][v] != 0){
if(w[v] > maxw) {
root = v;
maxw = w[v];
}
if(visited[v] == false){
Gangnum ++;
visited[v] = true;
}
sum_weight += G[u][v];
G[u][v] = 0;
G[v][u] = 0;
DFS(v, depth + 1);
}
}
return int2str[root];
}
//计算犯罪团伙数及其对应头目
struct node{
string name;//头目
int num;//成员个数
}ans[maxn];
void DFSTrave()
{
for(int u = 0; u < n; u++)
{
if(!visited[u]){
maxw = w[u];
root = u;
string name = DFS(u, 1);
if(sum_weight > k && Gangnum > 2){
ans[Count].name = name;
ans[Count++].num = Gangnum;
}
}
Gangnum = 1, sum_weight = 0;
}
}
bool cmp(node a, node b) {return a.name < b.name;}
int main()
{
cin >> n >>k;
string a, b;
int weight;
for(int i = 0; i < n; i++)
{
cin >> a >> b >> weight;
int x = f_str2int(a);
int y = f_str2int(b);
G[x][y] += weight;
G[y][x] +=weight;
w[x] += weight;
w[y] +=weight;
}
DFSTrave();
cout << Count << endl;
sort(ans, ans + Count, cmp);
for(int i = 0; i < Count; i++)
cout << ans[i].name << " " << ans[i].num << endl;
}4）BFS -- 微博
题目大意：微博有人发消息，也有人转发消息，也可以在微博关注其他人转发其他人的消息，规定只能转发关注的人的消息，一个人不能重复转发该消息，转发层数有上限。
输入第一行是有N个用户，转发层数上限L
接下来N行是每个用户（用户编号从1到N）关注了谁。
每行第一个数字是关注了几个用户，接着就是几个数字就是该用户关注的人。
然后接下来一行是要查询k个人，看看这K个人发消息最多多少人转发消息。
输出就是K个人每个人最多有多少人转发消息。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 1005;
int N, L, K, M, tmp;
bool visited[maxn] = {0};
struct Node{
int value;
int layer;
};
vector<Node> Adj[maxn];
int BFS(int s){
int res = 0;
queue<Node> q;
Node start;
start.value = s;
start.layer = 0;
q.push(start);
visited[start.value] = 1;
while(!q.empty()){
Node topNode = q.front();
q.pop();
int u = topNode.value;
for(int i = 0; i < Adj[u].size(); i++){
Node next = Adj[u][i];
next.layer = topNode.layer + 1;
if(next.layer > L) return res;
if(!visited[next.value]){
res++;
q.push(next);
visited[next.value] = 1;
}
}
}
}
int main()
{
cin >> N >> L;
for(int i = 1; i <= N; i++)
{
cin >> M;
for(int j = 0; j < M; j++){
cin >> tmp;
Node tmp2;
tmp2.value = i;
Adj[tmp].push_back(tmp2);
}
}
cin >> K;
for(int i = 0; i < K; i++){
cin >> tmp;
int ans = BFS(tmp);
cout << ans << endl;
fill(visited, visited + maxn, 0);
}
return 0;
}2.最短路径
1）Dijkstra求单源最短路径：
题目1：
题目翻译
作为一个城市的紧急救助队的队长的你有一份特殊的你所在国家的地图。地图展示了一些通过道路连接的分散的城市。每一个城市都有急救队并且地图上标出了一些城市之间道路的长度。当你接到一个从其他城市打来的电话时，你的任务是带领你的队员尽快到达那里同时叫上尽可能多的帮手。
输入格式
每一个输入文件包含一个测试样例。对于每一个测试样例，第一行有4个正整数：N(≤500)-城市的数量（城市编号从0到N-1)，M-道路的数量，C1和C2-分别为你现在所在的城市和你必须要去救援的城市。下一行包含N个整数--分别是第i个城市所拥有的救援队的数量。接下来的M行分别用三个整数C1和C2和L表示一对城市和他们之间道路的长度。C1 和C2之间保证至少有一条通路。
输出格式
对于每一个测试样例，输出两个数字在一行：C1和C2之间的最短路径的条数以及你最多可以集合的救援队的数量。一行中的所有数字都必须用一个空格隔开并且行尾没有多余的空格。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXV = 510;
const int INF = 0x3fffffff;
int N, M, C1, C2;
int team_num[MAXV];
int G[MAXV][MAXV];
int road_num[MAXV], max_team_num[MAXV], dis[MAXV];
bool visited[MAXV] = {0};
void Dijkstra(int s){
//初始化
fill(dis, dis + MAXV, INF);
memset(road_num, 0, sizeof(road_num));
memset(max_team_num, 0, sizeof(max_team_num));
//起点
dis[s] = 0;
max_team_num[s] = team_num[s];
road_num[s] = 1;
for(int i = 0; i < N; i++){
int u = -1, min = INF;
for(int j = 0; j < N; j++){
if(visited[j] == false && dis[j] < min){
u = j;
min = dis[j];
}
}
if(u == -1) return;
visited[u] = true;
for(int v = 0; v < N; v++){
if(visited[v] == false && G[u][v] != INF){
if(dis[u] + G[u][v] < dis[v]){
dis[v] = dis[u] + G[u][v];
max_team_num[v] = max_team_num[u] + team_num[v];
road_num[v] = road_num[u];
}
else if(dis[u] + G[u][v] == dis[v]){
if(max_team_num[u] + team_num[v] > max_team_num[v])
max_team_num[v] = max_team_num[u] + team_num[v];
road_num[v] += road_num[u];
}
}
}
}
}
int main()
{
cin >> N >> M >> C1 >> C2;
for(int i = 0; i < N; i++){
cin >> team_num[i];
}
fill(G[0], G[0] + MAXV * MAXV, INF);
for(int i = 0; i < M; i++){
int x, y, L;
cin >> x >> y >> L;
G[x][y] = G[y][x] = L;
}
Dijkstra(C1);
cout << road_num[C2] << " " << max_team_num[C2] <<endl;
return 0;
}题目2：
给定一个城市地图，地图中有很多建造汽油站的候选点，要选出一个候选点位置使得它到所有城市的最小距离最大，如果多个候选点有相同的最小距离，则选择到所有城市的平均距离最小的那个。如果仍然相同，则输出城市编号最小的那个。当然，最重要的，所有城市必须在候选点的服务范围内。
解析：
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
const int MAXV = 1050;
const int INF = 0x3fffffff;
int GasMap[MAXV][MAXV];
bool GVisited[MAXV] = { false };
int Gd[MAXV];
int N, M, K, DS;
//参数
struct soluStation {
int ID;
double Dis, aveDis;
};
vector<soluStation> reses;
bool cmp(soluStation a, soluStation b) {
if (a.Dis != b.Dis) { return a.Dis > b.Dis; }
else {
if (a.aveDis != b.aveDis) { return a.aveDis < b.aveDis; }
else {
return a.ID < b.ID;
}
}
}
double tempMMin = INF;
//加油站最短路处理
void GDijkstraGas(int s) {
fill(Gd, Gd + MAXV, INF); //切记一定要初始化
Gd[s] = 0;
for (int i = 1; i <= M + N; ++i) {
int u = -1, MMIN = INF;
for (int j = 1; j <= M + N; ++j) {
if (!GVisited[j] && Gd[j] < MMIN) {
MMIN = Gd[j];
u = j;
}
}
if (u == -1) return;
GVisited[u] = true;
for (int v = 1; v <= M + N; ++v) {
if (!GVisited[v] && GasMap[u][v] != INF && GasMap[u][v] + Gd[u] < Gd[v]) {
Gd[v] = GasMap[u][v] + Gd[u];
if (v <= N && Gd[v] < tempMMin) {
tempMMin = Gd[v];
}
}
}
}
}
int getIndex(char s[]) {
int num = 0;
int itr = 1;
for (int i = strlen(s) - 1; i >= 0; --i) {
num += itr * (s[i] - '0');
itr *= 10;
}
return num;
}
int main() {
fill(GasMap[0], GasMap[0] + MAXV * MAXV, INF);
scanf("%d %d %d %d", &N, &M, &K, &DS);
char city1[1010], city2[1010];
int Glength;
int node1, node2;
for (int i = 0; i < K; ++i) {
scanf("%s %s %d", city1, city2, &Glength);
if (city1[0] == 'G') {
if (strlen(city1) == 3) { node1 = 10 + N; }
else node1 = city1[1] - '0' + N;
}
else {
node1 = getIndex(city1);
}
if (city2[0] == 'G') {
if (strlen(city2) == 3) { node2 = 10 + N; }
else node2 = city2[1] - '0' + N;
}
else {
node2 = getIndex(city2);
}
GasMap[node1][node2] = Glength;
GasMap[node2][node1] = Glength;
}
//处理加油站
for (int i = 1; i <= M; ++i) {
bool outrange = false;
double avedistemp = 0.0;
tempMMin = INF;
fill(GVisited, GVisited + MAXV, false);
GDijkstraGas(N + i); //求最短路
for (int j = 1; j <= N; ++j) {
if (Gd[j] > DS) {
outrange = true;
break;
}
avedistemp += Gd[j];
}
if (!outrange) {
soluStation tempsolu;
tempsolu.ID = i;
tempsolu.Dis = tempMMin;
tempsolu.aveDis = avedistemp / N;
reses.push_back(tempsolu);
}
}
if (reses.empty()) {
printf("No Solution\n");
}
else {
sort(reses.begin(), reses.end(), cmp);
printf("G%d\n%.1lf %.1lf", reses[0].ID, reses[0].Dis, reses[0].aveDis);
}
system("PAUSE");
return 0;
}2）Dikstra + DFS
题目1：PTA 1018 Public Bike Management
每个站点的容纳量、站点总数和需要调节的站点编号，并给出各站点间的路径信息。在前往目的站点时总选择最短路径，并调节途中所有结点到完美状态，如果有多条最短路径则选择需要从中心携带最少自行车的路径。并将该路径输出。
思路：转载大神清晰思路
- 首先，遇到最短路径，肯定是Dijstra，但题目说了，可能会有多条最短路径，我们要找到全部路径怎么办？把每一个路径都保存下来吗？可以，但没必要。我们只需要记录最短路径上每个节点的直接前驱就可以了，而这个，在Dijstra算法中，只需要在更新过程中（d[v] = d[u] + e[u][v]）加上一条语句就可以了（prev[v].push_back(u)），非常简单。如果它有多个最短路径，那么它就有多个直接前驱，因此，每个节点都应该有一个vector来保存它的全部最短路径的直接前驱，最终，就是需要一个vector数组。
- 找到最短路径显然是不够的，我们还要进行选择，选择PCBC按哪一条路走，需要带过去的自行车最少。所以，我们要遍历全部最短路径，于是dfs就出场了，因为我们保存的是它的直接前驱，所以需要从sp往PCBC去遍历。对于每一个最短路径，模拟一次PCBC需要进行的调整过程（逐个访问节点，并根据它的当前容量计算它达到完美需要的自行车参数），记录需要带过来或带回去的自行车数目，如果更少，则选择这条路径。
- 有一个好的技巧是，我们的完美状态是cmax/2，刚开始给出了所有站点的当前容量，但我们不直接保存它的当前容量，我们用diff数组保存每个站点当前容量与完美状态的差值，这样，我们很容易根据这个值的正负知道它是缺少自行车，缺少几个？或者是需要自行车，需要几个？当然，这不是我这个菜鸡能想出来的，还是参考了柳婼大神的代码之后改出来的，大神是真的强！！！
- 所以，总的来说就是，Dijstra找到全部最短路径，dfs遍历每个最短路径并找到最好的那个，选择路径的原则就是，距离最短>距离相同但发送的自行车最少>距离相同发送的自行车也相同但带回的自行车最少。
代码：
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn = 510;
const int INF = 1e9;
int G[maxn][maxn];
int d[maxn];
bool vis[maxn];
int needs[maxn];
int C, N, S, M;
int temp[maxn] = {0}, path[maxn] = {0};
int mindis, mintake = INF, minremain = INF;
int pre[maxn][maxn];
int prenum[maxn];
void Dijkstra(int end){
d[0] = 0;
for(int i = 0; i <= N; i++){
int u = -1, min = INF;
for(int j = 0; j <= N; j++){
if(!vis[j] && d[j] < min){
u = j;
min = d[j];
}
}
if(u == -1) return;
vis[u] = 1;
for(int v = 0; v <= N; v++){
if(!vis[v] && G[u][v] != INF){
if(d[u] + G[u][v] < d[v]){
d[v] = d[u] + G[u][v];
prenum[v] = 0;
pre[v][prenum[v]++] = u;
}
else if(d[u] + G[u][v] == d[v]){
pre[v][prenum[v]++] = u;
}
}
}
if(u == end){
mindis = d[end];
return;
}
}
}
void DFS(int u, int depth){
int take, remain, v;
temp[depth] = u;
if(u == 0){
take = 0, remain = 0;
for(int i = depth - 1; i >= 0; i--){
v = temp[i];
if(remain >= needs[v]){
remain -= needs[v];
}
else{
take += needs[v] - remain;
remain = 0;
}
}
if(take < mintake){
mintake = take;
minremain = remain;
for(int i = depth, j = 0; i >= 0; i--){
path[j++] = temp[i];
}
}else if(take == mintake && remain < minremain){
mintake = take;
minremain = remain;
for(int i = depth, j = 0; i >= 0; i--){
path[j++] = temp[i];
}
}
return;
}
for(int i = 0; i < prenum[u]; i++){
v = pre[u][i];
DFS(v, depth + 1);
}
}
int main()
{
cin >> C >> N >> S >> M;
C = C / 2;
for(int i = 1; i <= N; i++){
cin >> needs[i];
needs[i] = C - needs[i];
}
fill(d, d + maxn, INF);
fill(G[0], G[0] + maxn * maxn, INF);
for(int i = 0; i < M; i++){
int a, b, v;
cin >> a >> b >> v;
G[a][b] = G[b][a] = v;
}
Dijkstra(S);
DFS(S, 0);
printf("%d 0", mintake);
for(int i = 1;;i++){
printf("->%d", path[i]);
if(path[i] == S) break;
}
printf(" %d\n", minremain);
return 0;
}一张图中有多个城市，城市之间有若干条公路，两个城市之间的公路有距离、花费两个权值。
现在求从出发城市S，到目的城市D路径满足以下条件：
1、距离最短
2、如果存在多条路径距离相同，则找出花费最少的那条
代码：
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
const int MAXV = 505;
const int INF = 0x3fffffff;
int n, m, S, D, cost[MAXV][MAXV], G[MAXV][MAXV];
int d[MAXV], minCost = INF;
bool vis[MAXV] = {0};
vector<int> pre[MAXV];
vector<int> tmpPath, path;
void Dijkstra(int s){
fill(d, d+MAXV, INF);
d[s] = 0;
for(int i=0;i<n;++i){
int u = -1, MIN = INF;
for(int j=0;j<n;++j){
if(vis[j]==0 && d[j]<MIN){
u = j;
MIN = d[j];
}
}
if(u==-1) return ;
vis[u] = 1;
for(int v=0;v<n;++v){
if(vis[v]==0 && G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v] = d[u]+G[u][v];
pre[v].clear();
pre[v].push_back(u);
}
else if(d[u]+G[u][v]==d[v]) pre[v].push_back(u);
}
}
}
}
void DFS(int v){
if(v==S){
tmpPath.push_back(v);
int tmpCost = 0;
for(int i=tmpPath.size()-1;i>0;--i){
int id = tmpPath[i], idNext = tmpPath[i-1];
tmpCost += cost[id][idNext];
}
if(tmpCost<minCost){
minCost = tmpCost;
path = tmpPath;
}
tmpPath.pop_back();
return ;
}
tmpPath.push_back(v);
for(int i=0;i<pre[v].size();++i) DFS(pre[v][i]);
tmpPath.pop_back();
}
int main()
{
cin >> n >> m >> S >> D;
fill(G[0], G[0]+MAXV*MAXV, INF);
fill(cost[0], cost[0]+MAXV*MAXV, INF);
for(int i=0;i<m;++i){
int c1, c2, tmp1, tmp2;
cin >> c1 >> c2 >> tmp1 >> tmp2;
G[c2][c1] = G[c1][c2] = tmp1;
cost[c1][c2] = cost[c2][c1] = tmp2;
}
Dijkstra(S);
DFS(D);
for(int i=path.size()-1;i>=0;--i) cout << path[i] << " ";
cout << d[D] << " " << minCost << endl;
}
题目3：PTA 1087 All Roads Lead to Rome
给出起点城市和终点城市ROM，以及各个城市之间的花费（即边权），以及每个城市的幸福指数（即点权），要求输出一条边权最小且点权最大的路径，并统计边权最小的路径个数 。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
const int maxn = 201;
const int INF = 1e9;
int G[maxn][maxn], d[maxn];
int happiness[maxn] = {0}, cnt = 0;
bool vis[maxn] = {false};
int n, m, h, c, minnode = INF, maxhappiness = -1;
vector<vector<int>> pre;
vector<int> path, temp;
unordered_map<string, int> name2num;
unordered_map<int, string> num2name;
void Dijkstra(int s){
fill(d, d + maxn, INF);
d[s] = 0;
for(int i = 0; i < n; i++){
int u = -1, MIN = INF;
for(int j = 0; j < n; j++){
if(!vis[j] && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return;
vis[u] = true;
for(int v = 0; v < n; v++){
if(!vis[v] && G[u][v] !=INF){
if(d[u] + G[u][v] < d[v]){
d[v] = d[u] + G[u][v];
pre[v].clear();
pre[v].push_back(u);
}else if(d[u] + G[u][v] == d[v])
pre[v].push_back(u);
}
}
}
}
void DFS(int index, int depth){
if(index == 0){//到达起点
temp.push_back(index);
cnt++;
int happytemp = 0;
//计算每条路径的幸福值
for(int i = temp.size() - 1; i >= 0; i--)
happytemp += happiness[temp[i]];
if(happytemp > maxhappiness){
maxhappiness = happytemp;
minnode = depth;
path = temp;
}else if(happytemp == maxhappiness && depth < minnode){
minnode = depth;
path = temp;
}
temp.pop_back();
return;
}
temp.push_back(index);
for(int i = 0; i < pre[index].size(); i++)
DFS(pre[index][i], depth + 1);
temp.pop_back();
}
int main(){
fill(G[0], G[0] + maxn * maxn, INF);
string st, st1, st2;
cin >> n >> m >> st;
pre.resize(n);
name2num[st] = 0;
num2name[0] = st;
for(int i = 1; i < n; i++){
cin >> st >> h;
happiness[i] = h;
name2num[st] = i;
num2name[i] = st;
}
for(int i = 0; i < m; i++){
cin >> st1 >> st2 >> c;
int x = name2num[st1], y = name2num[st2];
G[x][y] = G[y][x] = c;
}
Dijkstra(0);
int ed = name2num["ROM"];
DFS(ed, 0);
printf("%d %d %d %d\n", cnt, d[ed], maxhappiness, maxhappiness / minnode);
for(int i = path.size() - 1; i >= 0; i--){
if(i != path.size() - 1) printf("->");
cout << num2name[path[i]];
}
return 0;
}五、链表、栈、队列
1.从尾到头打印链表
法一：辅助栈
vector<int> reversePrint(ListNode* head) {
stack<int> s;
ListNode* p;
for(p=head;p!=NULL;p=p->next)
{
s.push(p->val);
}
vector<int> res;
while(!s.empty()){
res.push_back(s.top());
s.pop();
}
return res;
}法二：反转链表
vector<int> reversePrint(ListNode* head) {
vector<int> result;
// 空链表
if (head == nullptr) return result;
// 反转链表
ListNode *curr = head->next;
ListNode *temp;
head->next = nullptr;
while(curr) {
temp = curr->next;
curr->next = head;
head = curr;
curr = temp;
}
// 取出链表中的值
while(head) {
result.push_back(head->val);
head = head->next;
}
return result;
}法三：就地逆序
vector<int> reversePrint(ListNode* head) {
vector<int> result;
while (head) {
result.push_back(head->val);
head = head->next;
}
int len = result.size();
for (int i = 0; i < len / 2; i++) {
swap(result[i], result[len-i-1]);
}
return result;
}2.链表的深拷贝
法一：哈希表
Node* copyRandomList(Node* head) {
if(head==NULL) return nullptr;
Node* cur = head;
//建立原节点->拷贝节点的映射
unordered_map<Node*, Node*> map;
while(cur){
map[cur] = new Node(cur->val);
cur = cur->next;
}
//建立新节点之间关系
cur = head;
while(cur){
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
return map[head];
}法二：拼接+拆分
Node* copyRandomList(Node* head) {
if(head == NULL) return nullptr;
Node* cur = head;
//复制各节点并拼接
while(cur){
Node* tmp = new Node(cur->val);
tmp->next = cur->next;
cur->next = tmp;
cur = tmp->next;
}
//构建random连接关系
cur = head;
while(cur){
if(cur->random){
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
//拆分
cur = head->next;
Node* pre = head, *res = head->next;
while(cur->next){
pre->next = pre->next->next;
cur->next = cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr;//单独处理原链表尾节点
return res;
}
3.单调栈、队列
题目1（单调栈实现O(1)获取最值）：剑指 Offer 30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
代码：
class MinStack {
stack<int>x_stack;
stack<int>min_stack;
public:
/** initialize your data structure here. */
MinStack() {
min_stack.push(INT_MAX);
}
void push(int x) {
x_stack.push(x);
min_stack.push(::min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int min() {
return min_stack.top();
}
};题目2（单调双端队列）：剑指 Offer 59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
解析：jyd大神解析
为了实现此递减列表，需要使用 双向队列 ，假设队列已经有若干元素：
1.当执行入队 push_back() 时： 若入队一个比队列某些元素更大的数字 x ，则为了保持此列表递减，需要将双向队列 尾部所有小于 x 的元素 弹出。
2.当执行出队 pop_front() 时： 若出队的元素是最大元素，则 双向队列 需要同时 将首元素出队 ，以保持队列和双向队列的元素一致性。
使用双向队列原因：维护递减列表需要元素队首弹出、队尾插入、队尾弹出操作皆为 O(1) 时间复杂度。
代码：
class MaxQueue {
queue<int> q;
deque<int> d; //双端辅助队列
public:
MaxQueue() {
}
int max_value() {
if(d.empty()) return -1;
return d.front();
}
void push_back(int value) {
//把所有小于新加入元素的数字删除
while(!d.empty() && d.back() < value) d.pop_back();
d.push_back(value);
q.push(value);
}
int pop_front() {
if(q.empty()) return -1;
int ans = q.front();
if(ans == d.front()){
d.pop_front();
}
q.pop();
return ans;
}
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/题目3（单调双端队列）：剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
思路：
窗口对应的数据结构为 双端队列 ，本题使用 单调队列 即可解决以上问题。
代码：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//判断特殊情况
int n = nums.size();
if(n < k || k <= 0) return{};
//滑动窗口的前后指针
int low = 1 - k, high = 0;
deque<int> dq;//双端队列
vector<int> res;
while(high < n){
//判断滑窗的low端是否是最大的元素
//当出滑窗的元素恰好是单调队列的队头元素，则一起出栈
if(low >= 1 && nums[low - 1] == dq[0]) dq.pop_front();
//让所有小于新加入元素的单调队列元素出队
while(!dq.empty() && dq[dq.size() - 1] < nums[high]) dq.pop_back();
//新元素入队
dq.push_back(nums[high]);
//形成滑窗后，取队首元素加入结果res
if(low >= 0) res.push_back(dq[0]);
low++;
high++;
}
return res;
}
};六、字符串
1.替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
法一：原地替换
string replaceSpace(string s) {
int cnt = 0, len = s.size();
//统计空格数量
for(int i = 0; i < len; i++){
if(s[i] == ' ') cnt++;
}
//修改字符串长度
s.resize(len + 2 * cnt);
//倒序遍历修改
for(int i = len - 1, j = s.size() - 1; i < j; i--, j--){
if(s[i] != ' ')
s[j] = s[i];
else{
s[j - 2] = '%';
s[j - 1] = '2';
s[j] = '0';
j -= 2;
}
}
return s;
}法二：调库
string replaceSpace(string s) {
return s.replace(" ", "%20d");
}2.左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
法一：三次翻转（自定义）
class Solution {
public:
int reverse_string(string& s, int start, int end) {
for (int i = start; i <= (start + end) / 2; i++) {
char temp = s[i];
s[i] = s[start+end-i];
s[start+end-i] = temp;
}
return 0;
}
string reverseLeftWords(string s, int n) {
int length = s.length();
reverse_string(s, 0, length-1);
reverse_string(s, 0, length-n-1);
reverse_string(s, length-n, length-1);
return s;
}
};法二：三次翻转（调库）
string reverseLeftWords(string s, int n) {
reverse(s.begin(),s.end());
reverse(s.begin(),s.begin()+s.size()-n);
reverse(s.begin()+s.size()-n,s.end());
return s;
}七、查找算法
1.二分法
1）基本算法代码
int binary_search(int left, int right, vector<int> nums, int target)
{
int mid;
while (left < right)
{
mid = (left + right) / 2;
if (target < nums[mid])
{
right = mid - 1;
}
else if (target > nums[mid])
{
left = mid + 1;
}
}
return mid;
}2）变形1（返回左 / 右边界)
class Solution {
public:
int binary_search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] <= target) left = mid + 1;
else right = mid - 1;
}
return left;
}
int search(vector<int>& nums, int target) {
return binary_search(nums, target) - binary_search(nums, target - 1);
}
};3）变形2（缺失值)
- 左子数组： nums[i] = i；
- 右子数组： nums[i] ≠ i；
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] == mid) left = mid + 1;
else right = mid - 1;
}
return left;
}4）变形3（旋转数组）
题目：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
思路：
寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 nums[x]，称 x 为 旋转点 。
1. 当 nums[m] > nums[j] 时： m 一定在 左排序数组 中，即旋转点 x 一定在 [m + 1, j] 闭区间内，因此执行 i = m + 1；
2. 当 nums[m] < nums[j] 时： m 一定在 右排序数组 中，即旋转点 x 一定在[i, m] 闭区间内，因此执行 j = m；
3. 当 nums[m] = nums[j] 时： 无法判断 m 在哪个排序数组中，即无法判断旋转点 x 在 [i, m] 还是 [m + 1, j] 区间中。
解决方案： 执行 j = j - 1 缩小判断范围，分析见大神解析
代码：
int minArray(vector<int>& numbers) {
int left = 0, right = numbers.size() - 1;
while(left < right){
int mid = (left + right) / 2;
if(numbers[mid] > numbers[right]) left = mid + 1;
else if(numbers[mid] < numbers[right]) right = mid;
else {
// right --;
// 剩下部分可直接进行线性查找，返回最小值
int x = left;
for(int k = left + 1; k < right; k++) {
if(numbers[k] < numbers[x]) x = k;
}
return numbers[x];
}
}
return numbers[left];
}
2.有序二维数组的查找
1）问题
2）算法思路
当 matrix[i][j] > target 时，执行 i-- ，即消去第 i 行元素；
当 matrix[i][j] < target 时，执行 j++ ，即消去第 j 列元素；
当 matrix[i][j] = target 时，返回 truetrue ，代表找到目标值。
3）代码实现
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
int i = matrix.size() - 1, j = 0;
while(i >= 0 && j < matrix[0].size())
{
if(matrix[i][j] > target) i--;
else if(matrix[i][j] < target) j++;
else return true;
}
return false;
}
};
""作者：jyd
链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。""3.哈希表
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
1）普通
char firstUniqChar(string s) {
unordered_map<char, bool> dic;
for(char c : s)
dic[c] = (dic.find(c) == dic.end());
for(char c : s)
if(dic[c]) return c;
return ' ';
}2）有序
在哈希表的基础上，有序哈希表中的键值对是 按照插入顺序排序 的。
char firstUniqChar(string s) {
vector<char> keys;//用其实现有序性
unordered_map<char, bool> dic;
for(char c : s) {
if(dic.find(c) == dic.end())
keys.push_back(c);
dic[c] = (dic.find(c) == dic.end());
}
for(char c : keys) {
if(dic[c]) return c;
}
return ' ';
}八、二叉树
1.遍历
1）BFS / 广度 / 层序遍历
vector<int> levelOrder(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
while(q.size()){
TreeNode* tmp = q.front();
q.pop();
ans.push_back(tmp->val);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
return ans;
}变形1：每行打印一层
题目：剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
代码：
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
while(q.size()){
vector<int> tmp;//存储每层结点
for(int i = q.size() - 1; i >=0; i--){//只进行一次初始化
TreeNode* t = q.front();
tmp.push_back(t -> val);
q.pop();
if(t -> left) q.push(t -> left);
if(t -> right) q.push(t -> right);
}
ans.push_back(tmp);
}
return ans;
}小Tips：
为什么不能用如下代码，对层内进行循环呢？
for(int i = 0; i < q.size(); i++)
例如q.size()长度为3，那么 （假设不考虑左右孩子入队列情况）：
- 第一次：i = 0,长度3,i++
- 第二次：i = 1,长度2,i++
- 第三次：i = 2,长度1,此次本应该进循环但是没有进去。
但是用上述方法，for循环里的i只能初始化一次，也就是i = 3,2,1，刚好三次。
变形2：“之”字顺序 + 每行打印一层
题目：
第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
代码：
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
bool rev=false;
while(!q.empty()){
int node_num=q.size();
vector<int> tmp(node_num);
for(int i=0;i<node_num;i++){
TreeNode* node=q.front();
q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
tmp[rev?node_num-i-1:i]=node->val;
}
rev=!rev;
ans.push_back(tmp);
}
return ans;
}2）先序遍历
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
代码：
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A==nullptr || B==nullptr) return false;
return recur(A,B) || isSubStructure(A->left,B) ||isSubStructure(A->right,B);
}
bool recur(TreeNode* A, TreeNode* B){
if(B==nullptr) return true;
if(A==nullptr || A->val!=B->val) return false;
return recur(A->left,B->left) && recur(A->right,B->right);
}
};3）DFS
输入一个二叉树，该函数输出它的镜像。
法一：递归
TreeNode* mirrorTree(TreeNode* root) {
if(root == nullptr) return nullptr;
TreeNode* tmp = root -> left;
root -> left = mirrorTree(root -> right);
root -> right = mirrorTree(tmp);
return root;
}法二：辅助栈 / 队列
TreeNode* mirrorTree(TreeNode* root) {
if(root == nullptr) return nullptr;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* cur = s.top();
s.pop();
if(cur -> left) s.push(cur -> left);
if(cur -> right) s.push(cur -> right);
TreeNode* tmp = cur -> left;
cur -> left = cur -> right;
cur -> right = tmp;
}
return root;
}//法一：递归
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
bool check(TreeNode* x, TreeNode* y){
if(!x && !y) return true;//均为空
if(!x || !y) return false;//一者为空
return x -> val == y -> val && check(x -> left, y -> right) && check(x -> right, y -> left);
}
};
//法二：辅助队列
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
bool check(TreeNode* x, TreeNode* y){
queue<TreeNode*> q;
q.push(x);
q.push(y);
while(!q.empty()){
x = q.front();
q.pop();
y = q.front();
q.pop();
if(!x && !y) continue;
if((!x || !y) || (x -> val != y -> val))return false;
q.push(x -> left);
q.push(y -> right);
q.push(x -> right);
q.push(y -> left);
}
return true;
}
};九、搜索与回溯
1. DFS + 剪枝
题目：矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
代码：
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[0].size();
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
private:
int rows, cols;
bool dfs(vector<vector<char>>& board, string word, int i, int j, int depth){
//剪枝：超出范围或者存在不相等字符
if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[depth]) return false;
//找到整个单词
if(depth == word.size() - 1) return true;
//标记当前元素，代表已经访问过，防止重复访问
board[i][j] = '\0';
bool res = dfs(board, word, i + 1, j, depth + 1) || dfs(board, word, i - 1, j, depth + 1) || dfs(board, word, i, j + 1, depth + 1) || dfs(board, word, i, j - 1, depth + 1);
//还原当前元素
board[i][j] = word[depth];
return res;
}
};
2.DFS / BFS
题目：机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
- 数位之和
int sums(int x)
int s = 0;
while(x != 0) {
s += x % 10;
x = x / 10;
}
return s;- 增量公式
- 当 ( x + 1 ) % 10 = 0 时：
如：19， 20 数位和分别为10， 2；
- 当 ( x + 1 ) % 10 != 0 时：
如：18， 19 数位和分别为 9， 10；
(x + 1) % 10 != 0 ? s_x + 1 : s_x - 8;- 可达解
矩阵中满足数位和的解构成的几何形状形如多个等腰直角三角形 ；
三角形间不一定是连通的，因此机器人不一定能到达，称之为 不可达解 ；同理，可到达的解称为 可达解 （本题求此解） 。
仅通过向右和向下移动，访问所有可达解 。
代码：
1）DFS
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> vis(m, vector<bool>(n, 0));
return dfs(0, 0, 0, 0, vis, m, n, k);
}
private:
int dfs(int i, int j, int si, int sj, vector<vector<bool>> &vis, int m, int n, int k){
//终止条件
if(i >= m || j >= n || si + sj > k || vis[i][j]) return 0;
vis[i][j] = true;
//向下、向右递推
return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj, vis, m, n, k) +
dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8, vis, m, n, k);
}
};2）BFS
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> vis(m, vector<bool>(n, 0));
int res = 0;
queue<vector<int>> que;
que.push({0, 0, 0, 0});
while(que.size()){
vector<int> x = que.front();
que.pop();
int i = x[0], j = x[1], si = x[2], sj = x[3];
if(i >= m || j >= n || si + sj > k || vis[i][j]) continue;
vis[i][j] = true;
res++;
que.push({i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj});
que.push({i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8});
}
return res;
}
};3. 位运算
要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
天秀做法：此处膜拜大神
class Solution {
public:
int sumNums(int n) {
return sizeof(bool[n][n+1])>>1;
}
};
作者：moao
链接：https://leetcode.cn/problems/qiu-12n-lcof/solution/c-tian-xiu-by-moao-u1am/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。K神题解：此处进入
分析：
计算方法主要有三种：平均计算（使用乘除法）、迭代（使用for或while）、递归（使用if）
通过逻辑运算符的短路效应实现：
if(A && B) # 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false
if(A || B) # 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true
代码：（Python实现）
class Solution:
def __init__(self):
self.res = 0
def sumNums(self, n: int) -> int:
n > 1 and self.sumNums(n - 1)
self.res += n
return self.res位运算相关：
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数
法一：逐位运算
int hammingWeight(uint32_t n) {
int res = 0;
while(n){
//判断末位是否为1
res += n & 1;
//右移
n >>= 1;
}
return res;
}法二：巧用 n&(n-1)
n - 1 ：二进制数字n最右边的1变成0，此1右边的0都变成1
n & (n - 1) ：最右边的1变成0，其余不变
int hammingWeight(uint32_t n) {
int res = 0;
while(n){
res +=1;
//每一次消去一个右边的1
n &= n - 1;
}
return res;
}写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
代码：（特别鸣谢评论区大佬@Lone）
class Solution {
public:
int add(int a, int b) {
//因为不允许用+号，所以求出异或部分和进位部分依然不能用+ 号，所以只能循环到没有进位为止
while(b!=0)
{
//保存进位值，下次循环用
int c=(unsigned int)(a&b)<<1;//C++中负数不支持左移位，因为结果是不定的
//保存不进位值，下次循环用，
a^=b;
//如果还有进位，再循环，如果没有，则直接输出没有进位部分即可。
b=c;
}
return a;
}
};题目3：剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
代码：
vector<int> singleNumbers(vector<int>& nums) {
//假设所求数字为x,y
//1.进行第一轮遍历异或，得到结果n = x^y
int n = 0;
for(int num : nums) n ^= num;
//n中至少有一位是1，否则x == y
//2.通过辅助变量m保存最低位的1
int m = 1;
//每次将m左移一位，然后跟n做&运算，直到结果不为0
while((n & m) == 0) m <<= 1;
//3.第二轮遍历&操作，分为结果为0和不为0两组
//此时，问题退化为，每一组中只有一个数字出现一次
//4.在分别对两组遍历异或操作
int x = 0, y = 0;
for(int num : nums){
if(num & m) x ^= num;
else y ^= num;
}
return vector<int> {x, y};
}5.二叉树相关
1）先序遍历 + 路径记录
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int target) {
helper(root, target);
return res;
}
private:
void helper(TreeNode* Node, int sum) {
if(Node == nullptr) return;
path.push_back(Node -> val);
sum -= Node -> val;
if(sum == 0 && Node -> left == nullptr && Node -> right == nullptr){
res.push_back(path);
}
//先序遍历：根、左、右
helper(Node -> left, sum);
helper(Node -> right, sum);
path.pop_back();//回溯
}
};2）中序遍历
性质：二叉搜索树的中序遍历为 递增序列 。
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(root == nullptr) return nullptr;
dfs(root);
head -> left = pre;
pre -> right = head;
return head;
}
private:
Node *pre, *head;
void dfs(Node* cur){
if(cur == nullptr) return;
dfs(cur -> left);
//后继指针
if(pre != nullptr) pre -> right = cur;
//头结点
else head = cur;
//前驱指针
cur -> left = pre;
pre = cur;
dfs(cur -> right);
}
};给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
思路：二叉搜索树的 中序遍历倒序 为 递减序列 。
class Solution {
public:
int kthLargest(TreeNode* root, int k) {
DFS(root, k);
return ans;
}
private:
int ans;
void DFS(TreeNode* cur, int &k){
if(cur == nullptr) return;
if(cur -> right) DFS(cur -> right, k);
if(--k == 0) {
ans = cur -> val;
return;
}
if(cur -> left) DFS(cur -> left, k);
}
};3）层序遍历BFS
请实现两个函数，分别用来序列化和反序列化二叉树。
代码：
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
//特殊情况：为空
if(!root) return res;
queue<TreeNode*> q;
//根节点初始化
q.push(root);
while(!q.empty()){
TreeNode* front = q.front();
q.pop();
if(front){
res += to_string(front->val) + ",";
q.push(front->left);
q.push(front->right);
}
else res += "null,";
}
//将末尾逗号去掉
return res.substr(0, res.size() - 1);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.empty()) return nullptr;
vector<string> s = split(data);
queue<TreeNode*> q;
//stoi函数将字符串转化为数字，默认十进制
//初始化根节点
TreeNode* root = new TreeNode(stoi(s[0]));
q.push(root);
int i = 1;
while(!q.empty()){
TreeNode* front = q.front();
q.pop();
if(s[i] != "null"){
front -> left = new TreeNode(stoi(s[i]));
q.push(front->left);
}
i++;
if(s[i] != "null"){
front -> right = new TreeNode(stoi(s[i]));
q.push(front->right);
}
i++;
}
return root;
}
vector<string> split(string& s){
//按照逗号划分
vector<string> res;
int n = s.size();
int i = 0;
while(i < n){
int j = i + 1;
//直到找到,
while(j < n && s[j] != ',') j++;
res.push_back(s.substr(i, j - i));
i = j + 1;
}
return res;
}
};
4）二叉树的深度
题目1：求二叉树的深度
法一：后序遍历DFS
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
}法二：层序遍历BFS
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
int res = 0;
queue<TreeNode*> q;
q.push(root);
while(q.size()){
for(int i = q.size(); i; i--){
TreeNode* node = q.front();
q.pop();
if(node -> left) q.push(node -> left);
if(node -> right) q.push(node -> right);
}
res++;
}
return res;
}题目2：平衡二叉树的判断
法一：自顶向下
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root == nullptr) return true;
return abs(depth(root->left) - depth(root->right)) <=1 && isBalanced(root->left) && isBalanced(root->right);
}
int depth(TreeNode* root){
if(root == nullptr) return 0;
return max(depth(root->left), depth(root->right)) + 1;
}
};法二：自底向上 + 剪枝
思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
class Solution{
public:
bool isBalanced(TreeNode* root){
return recur(root) == -1 ? false : true;
}
//后序遍历，返回子树深度
int recur(TreeNode* root){
//终止条件1：当前结点为空，返回高度0
if(root == nullptr) return 0;
int l = recur(root -> left);
//左子树剪枝
if(l == -1) return -1;
int r = recur(root -> right);
//右子树剪枝
if(r == -1) return -1;
//当左右子树深度差<=1，则返回当前子树深度
//当深度差>2，则返回-1
return abs(r - l) <= 1 ? max(l, r) + 1 : -1;
}
};5）最近公共祖先
题目1：剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
法一：迭代
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr) return nullptr;
while(root){
//都在左子树
if((p->val < root->val)&&(q->val < root->val)) root = root->left;
//都在右子树
else if((p->val > root->val)&&(q->val > root->val)) root = root->right;
else break;
}
return root;
}法二：递归
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr) return nullptr;
if((p->val < root->val)&&(q->val < root->val))
return lowestCommonAncestor(root->left, p, q);
else if((p->val > root->val)&&(q->val > root->val))
return lowestCommonAncestor(root->right, p, q);
return root;
}题目2：剑指 Offer 68 - II. 二叉树的最近公共祖先
注意！！！！！！！！本题不是搜索树！！！！
解析：K神解析
1. 当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q ，返回 null ；
2. 当 left 和 right 同时不为空 ：说明 p, q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
3. 当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
1）p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ）；
2）p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
4. 当 left 不为空 ， right 为空 ：与情况 3. 同理
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || root == p || root == q) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left == nullptr && right == nullptr) return nullptr; // 1.
if(left == nullptr) return right; // 3.
if(right == nullptr) return left; // 4.
return root; // 2. if(left != null and right != null)
}
};
//情况 1. 可合并至 3. 和 4. 内。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || root == p || root == q) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left == nullptr) return right;
if(right == nullptr) return left;
return root;
}
};
6.字符串相关
1）DFS + 剪枝
输入一个字符串，打印出该字符串中字符的所有排列。
代码：
class Solution {
public:
vector<string> permutation(string s) {
dfs(s, 0);
return res;
}
private:
vector<string> res;
void dfs(string s, int x) {
//x为固定位
//所有位已固定（最后一位只有 1 种情况）
if(x == s.size() - 1) {
res.push_back(s); // 添加排列方案
return;
}
set<int> st;
for(int i = x; i < s.size(); i++) {
// 实际上第一种情况相当于不交换
// 之后交换第x位与第 x+1 - s.size() 位
if(st.find(s[i]) != st.end()) continue; // 重复，因此剪枝
st.insert(s[i]); // 方便后续剪枝
swap(s[i], s[x]); // 交换，将 s[i] 固定在第 x 位
dfs(s, x + 1); // 开启固定第 x + 1 位字符
swap(s[i], s[x]); // 恢复交换
}
}
};十、排序
1）字符串
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
思路：大神解析
若拼接字符串 x + y > y + x ，则 x “大于” y ；
反之，若 x + y < y + x ，则 x “小于” y ；
代码：
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
for(int i = 0; i < nums.size(); i++){
strs.push_back(to_string(nums[i]));
}
quickSort(strs, 0, strs.size() - 1);
string res;
for(string s : strs){
res.append(s);
}
return res;
}
private:
void quickSort(vector<string>& strs, int l, int r){
if(l >= r) return;
//双指针
int i = l, j = r;
while(i < j){
//以l为基准，小于在左边，大于在右边
while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j --;
while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i ++;
swap(strs[i], strs[j]);
}
//还原基准的中心位置
swap(strs[i], strs[l]);
//左右部分分别递归
quickSort(strs, l, i - 1);
quickSort(strs, i + 1, r);
}
};2）数组
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
充要条件：
- 无重复的牌（大小王除外）
- 最大牌 - 最小牌 < 5 （大小王除外）
代码：
法一：集合 + 遍历
class Solution {
public:
bool isStraight(vector<int>& nums) {
set<int> s;
for(int i : nums){
//判断是否存在重复
if(s.find(i) != s.end()) return 0;
//将除了大小王的数插入
if(i) s.insert(i);
}
return *s.rbegin() - *s.begin() < 5;
}
};法二：排序 + 遍历
class Solution {
public:
bool isStraight(vector<int>& nums) {
int joker = 0;
sort(nums.begin(), nums.end());
for(int i = 0; i < 5; i++){
//统计大小王数量
if(nums[i] == 0) joker++;
//判断是否重复
else if(i < 4){
if(nums[i] == nums[i + 1]) return false;
}
}
return nums[4] - nums[joker] < 5;
}
};3）快速排序
最小的k个数
代码：
法一：排序
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
quickSort(arr, 0, arr.size() - 1);
vector<int> res;
res.assign(arr.begin(), arr.begin() + k);
return res;
}
private:
void quickSort(vector<int>& arr, int l, int r) {
// 子数组长度为 1 时终止递归
if (l >= r) return;
// 哨兵划分操作（以 arr[l] 作为基准数）
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= arr[l]) j--;
while (i < j && arr[i] <= arr[l]) i++;
swap(arr[i], arr[j]);
}
swap(arr[i], arr[l]);
// 递归左（右）子数组执行哨兵划分
quickSort(arr, l, i - 1);
quickSort(arr, i + 1, r);
}
};法二：基于快速排序的数组划分
如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。
递归条件：K神解析
若 k < i ，代表第 k + 1 小的数字在 左子数组 中，则递归左子数组；
若 k > i ，代表第 k + 1 小的数字在 右子数组 中，则递归右子数组；
若 k = i ，代表此时 arr[k] 即为第 k + 1 小的数字，则直接返回数组前 k 个数字即可；
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if(k >= arr.size()) return arr;
return quickSort(arr, k, 0, arr.size() - 1);
}
private:
vector<int> quickSort(vector<int>& arr, int k, int l, int r){
int i = l, j = r;
while(i < j){
while(i < j && arr[j] >= arr[l]) j--;
while(i < j && arr[i] <= arr[l]) i++;
swap(arr[i], arr[j]);
}
swap(arr[i], arr[l]);
//递归左半边
if(i > k) return quickSort(arr, k, l, i - 1);
//递归右半边
if(i < k) return quickSort(arr, k, i + 1, r);
vector<int> res;
res.assign(arr.begin(), arr.begin() + k);
return res;
}
};4）优先队列 / 堆
代码：评论区大神解法
class MedianFinder {
public:
// 最大堆，存储左边一半的数据，堆顶为最大值
priority_queue<int, vector<int>, less<int>> maxHeap;
// 最小堆， 存储右边一半的数据，堆顶为最小值
priority_queue<int, vector<int>, greater<int>> minHeap;
/** initialize your data structure here. */
MedianFinder() {
}
// 维持堆数据平衡，并保证左边堆的最大值小于或等于右边堆的最小值
void addNum(int num) {
/*
* 当两堆的数据个数相等时候，左边堆添加元素。
* 采用的方法不是直接将数据插入左边堆，而是将数据先插入右边堆，算法调整后
* 将堆顶的数据插入到左边堆，这样保证左边堆插入的元素始终是右边堆的最小值。
* 同理左边数据多，往右边堆添加数据的时候，先将数据放入左边堆，选出最大值放到右边堆中。
*/
if (maxHeap.size() == minHeap.size()) {
minHeap.push(num);
int top = minHeap.top();
minHeap.pop();
maxHeap.push(top);
} else {
maxHeap.push(num);
int top = maxHeap.top();
maxHeap.pop();
minHeap.push(top);
}
}
double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.top()+minHeap.top())*1.0/2;
} else {
return maxHeap.top()*1.0;
}
}
};十一、数学
题目1：剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
法一：哈希表
int majorityElement(vector<int>& nums) {
unordered_map<int, int> cnt;
int majority = 0, max_cnt = 0;
for(int num: nums){
cnt[num]++;
//打擂台方式维护最大值
if(cnt[num] > max_cnt){
majority = num;
max_cnt = cnt[num];
}
}
return majority;
}法二：排序
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n/2 的元素（下标从 0 开始）一定是众数。
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};法三：摩尔投票法
评论区大神coder_dai解析：
假设有一个擂台，有一组人，每个人有编号，相同编号为一组，依次上场，没人时上去的便是擂主（x），若有人，编号相同则继续站着（人数+1），若不同，假设每个人战斗力相同，都同归于尽，则人数-1；那么到最后站着的肯定是人数占绝对优势的那一组啦~
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0, votes = 0;
for(int num : nums){
//当发生 票数和 = 0 时，剩余数组的众数一定不变
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
};
//扩展：考虑不存在众数情况
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0, votes = 0, count = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
// 验证 x 是否为众数
for(int num : nums)
if(num == x) count++;
return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0
}
};
作者：jyd
链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
法一：表格分区
根据表格的主对角线（全为 1 ），可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果。
vector<int> constructArr(vector<int>& a) {
int len = a.size();
if(len == 0) return {};
vector<int> b(len, 1);
b[0] = 1;
int tmp = 1;
for(int i = 1; i < len; i++){
b[i] = b[i - 1] * a[i - 1];//下三角
}
for(int i = len - 2; i >= 0; i--){
tmp *= a[i + 1];//上三角
b[i] *= tmp;
}
return b;
}题目3.1：剑指 Offer 14- I. 剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
法一：数学推导
① 当所有绳段长度相等时，乘积最大。
② 最优的绳段长度为 3
int cuttingRope(int n) {
//如果绳子总长凑不足3，只能拆分成1, n-1两段
if(n <= 3) return n - 1;
int a = n / 3;
int b = n % 3;
//尽量拆分成长度为3
if(b == 0) return int(pow(3, a));
//如果剩下1，则拆分成4=2+2 > 4=3+1
if(b == 1) return int(pow(3, a - 1) * 4);
return int(pow(3, a) * 2);
}法二：动态规划
class Solution {
public:
/**
* 1. 确定dp数组下标含义 分拆数字i，可以得到的最大乘积为dp[i];
* 2. 递推公式 dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j);
* 3. 初始化 dp[2] = 1;
* 4. 遍历顺序 从前向后遍历就可以;
* 5. 推导结果;
*/
int integerBreak(int n) {
/* 定义dp数组 */
vector<int> dp(n + 1);
/* dp数组初始化 */
dp[2] = 1;
/* 从前向后遍历 */
for (int i = 3; i <= n ; i++) {
/* j遍历到小于i的值 */
for (int j = 1; j < i - 1; j++) {//是否继续拆分i-j
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
return dp[n];
}
};
作者：Nehzil
链接：https://leetcode.cn/problems/jian-sheng-zi-lcof/solution/by-nehzil-w61p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题目3.2：剑指 Offer 14- II. 剪绳子 II
同3.1，此外，答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
大数取余问题：
- 循环求余法
∵ 本题中 x<p，∴ x ⊙ p = x
public long remainder(int x,int a,int p){ //x为底数，a为幂，p为要取的模
long rem = 1 ;
for (int i = 0; i < a; i++) {
rem = (rem * x) % p ;
}
return rem;
}- 快速幂求余法
public long quickPow(int x, long a, int p) {
long res = 1;
long tt = x;
while (a != 0) {
if ((a & 1) == 1) {
res *= tt;
res %= p;
}
tt *= tt;
tt %= p;
a /= 2;
}
return res;
}数学+循环求余：
class Solution {
public:
int cuttingRope(int n) {
if(n <= 3) return n - 1;
int b = n % 3, p = 1000000007;
long rem = 1, x = 3, a = n / 3;
//直接套循环求余公式
for(int i = 0; i < ((b == 1) ? a - 1 : a); i++){
// 余数为1时，需要单独取出一个3来凑成 1+3 = 2+2
rem = (rem * x) % p;
}
if(b == 0) return (int) (rem % p);
if(b == 1) return (int) (rem * 4 % p);
return (int)(rem * 2 % p);
}
};贪心+快速幂求余：
public class Solution {
public int cuttingRope(int n) {
if (n <= 3) {
return n - 1;
}
int a = n / 3;
int b = n % 3;
if (b == 2) {
return (int) (quickPow(3, a) * b % 1000000007);
} else {
return (int) ((quickPow(3, a - 1) * (b + 3)) % 1000000007);
}
}
private long quickPow(int x, long n) {
long res = 1;
long tt = x;
while (n != 0) {
if ((n & 1) == 1) {
res *= tt;
res %= 1000000007;
}
tt *= tt;
tt %= 1000000007;
n /= 2;
}
return res;
}
}题目4：剑指 Offer 57 - II. 和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
法一：求和公式、解方程
右边界：
舍去必为负数解后，从小到大遍历左边界。
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
int i = 1;
double j = 2.0;
vector<vector<int>> res;
while(i < j) {
j = (-1 + sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
if(i < j && j == (int)j) {
vector<int> ans;
for(int k = i; k <= (int)j; k++)
ans.push_back(k);
res.push_back(ans);
}
i++;
}
return res;
}
};法二：滑动窗口（双指针）
若大于 target 则移动左边界 i （以减小窗口内的元素和），若小于 target 则移动右边界 j （以增大窗口内的元素和）。
vector<vector<int>> findContinuousSequence(int target) {
//初始化:1+2=3
int i = 1, j = 2, s = 3;
vector<vector<int>> res;
while(i < j){
if(s == target){
//如果相等，记录结果
vector<int> ans;
for(int k = i; k <= j; k++)
ans.push_back(k);
res.push_back(ans);
}
if(s >= target){
//等于的情况可能存在多种
//大于，左边界右移，减少元素个数
s -= i;
i++;
} else{
//小于，右边界右移，增加元素个数
j++;
s += j;
}
}
return res;
}0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
- （n, m）问题 --> 解为f(n)
删除数字为(m-1)%n，下一个数字t = m%n <-->0
- （n-1, m）问题 --> f(n-1)
得到对应关系：x --> (x+t)%n
f(n) = (f(n-1)+t)%n=(f(n-1)+m%n)%n=(f(n-1)+m)%n
class Solution {
public:
int lastRemaining(int n, int m) {
//f(1)=0
int x = 0;
for(int i = 2; i <= n; i++){
x = (x + m) % i;
}
return x;
}
};题目6：剑指 Offer 43. 1～n 整数中 1 出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
思路：K神解析
设数字 n 是个 x 位数，记 n 的第 i 位为 ni：
当前位：，cur
低位：，low
高位：，high
位因子：，digit
- cur = 0： high × digit
- cur = 1：high × digit + low + 1
- cur = 2, ..., 9：(high + 1) × digit
//评论区大神dingxufa
case 1: cur=0
2 3 0 4
千位和百位可以选00 01 02....22 十位可以取到1( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9 共有 23 * 10 中排列
当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23，十位只能能取0，个位取0-4即 2300 2301 2302 2303 2304
但是2301不应该算进来，这个1是 单独 出现在个位的（而11，121,111这种可以被算多次）
即 23*10
case 2: cur=1
2 3 1 4
千位和百位可以选00 01 02....22 十位可以取到1 个位可以选0-9 共有 23 * 10 中排列
当千位和百位取23,十位取1，个位可以去0-4 即 2310-2314共5个
即 23 *10 + 4 +1
case 3: cur>1 即2-9
2 3 2 4
千位和百位可以选00 01 02....22 十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9 共有 23 * 10 中排列
当千位和百位取23,十位取1，个位可以去0-9 即 2310-2319共10个 （其中2311，被计算了两次，分别是从个位和十位分析得到的1次）
即 23 *10 + 10代码：
class Solution {
public:
int countDigitOne(int n) {
// 返回结果初始化为0
int res = 0;
// 先对最低位进行初始化
int cur = n % 10, high = n / 10, low = 0;
long digital = 1;
while(high != 0 || cur != 0){
if(cur == 0){
res += int(high * digital);
}else if(cur == 1){
res += int(high * digital + low + 1);
}else{
res += int((high+1) * digital);
}
low = int(low + digital*cur);
cur = high % 10;
high = high / 10;
digital *= 10;
}
return res;
}
};数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
思路：K神题解
- 递推：
| 数字范围 | 位数 | 数字数量 | 数位数量 |
| 1~9 | 1 | 9 | 9 |
| 10~99 | 2 | 90 | 180 |
| 100~999 | 3 | 900 | 2700 |
| ... | ... | ... | ... |
| start~end | digit | 9×start | 9×start×digit |
位数：digit = digit + 1
起始数字：start = start × 10
数位数量计算：count = 9 × start × digit
确定所求数位的所在数字的位数
digit, start, count = 1, 1, 9
while n > count:
n -= count
start *= 10 # 1, 10, 100, ...
digit += 1 # 1, 2, 3, ...
count = 9 * start * digit # 9, 180, 2700, ...确定所求数位所在的数字
num = start + (n - 1) // digit确定所求数位在 num 的哪一数位
s = str(num) # 转化为 string
res = int(s[(n - 1) % digit]) # 获得 num 的 第 (n - 1) % digit 个数位，并转化为 int代码：
class Solution {
public:
int findNthDigit(int n) {
//初始化
long start=1;
long count=9;
int digit=1;
while(n>count){
//确定所求数位的所在数字的位数
n-=count;
//递推
digit++;
start*=10;
count=9*start*digit;
}
//确定所求数位所在的数字
int num=start+(n-1)/digit;
//确定所求数位在 num 的哪一数位
count=(n-1)%digit;
string s=to_string(num);
int ans=s[count]-'0';
return ans;
}
};十二、C++标准模版库（STL）
1.Vector
题目1：PTA 1039 Course List for Student
浙江大学现有在校生4万人，开设课程2500门。现在，给定所有课程的学生姓名列表，应该为每个来查询的学生输出已注册的课程列表。
思路：
1）学生姓名和课程匹配：不能用map<string, int>，会超时。只能用字符串哈希进行数组映射。
2）考生数与课程数乘积过大（40000*2500），开个二维数组内存不够。只能使用vector可变数组存放课程。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int getID(char name[]){
//字符串哈希映射
int id = 0;
for(int i = 0; i < 3; i++)
//前三位是大写字母
id = id * 26 + (name[i] - 'A');
//最后一位是数字
id = id * 10 + (name[3] - '0');
return id;
}
vector<int> vi[26*26*26*10+1];
int main()
{
int N, K;
char name[5];
int course, Ni;
cin >> N >> K;
for(int i = 0; i < K; i++){
cin >> course >> Ni;
for(int j = 0; j < Ni; j++){
cin >> name;
vi[getID(name)].push_back(course);
}
}
for(int i = 0; i < N; i++){
cin >> name;
cout << name << " " << vi[getID(name)].size();
sort(vi[getID(name)].begin(), vi[getID(name)].end());
for(int j = 0; j < vi[getID(name)].size(); j++)
cout << " " << vi[getID(name)][j];
cout << endl;
}
return 0;
}题目2：PTA 1047 Student List for Course
浙江大学现有在校生4万人，开设课程2500门。现在，给定每个学生的注册课程列表，应该输出所有课程的学生姓名列表。
代码：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
int n, k;
// n - the total number of students
// k - the total number of courses
scanf("%d %d", &n, &k);
vector<vector<string>> courses(k + 1);
for(int i = 0; i < n; ++i){
string name;
int numOfCourses;
cin >> name >> numOfCourses;
for(int j = 0; j < numOfCourses; ++j){
int course;
scanf("%d", &course);
courses[course].push_back(name);
}
}
for(int i = 0; i < k; ++i){
sort(courses[i + 1].begin(), courses[i + 1].end());
printf("%d %d\n", i + 1, (int)courses[i + 1].size());
for(int j = 0; j < courses[i + 1].size(); ++j) printf("%s\n", courses[i + 1][j].c_str());
}
return 0;
}
2.Set
给定两组整数，定义两组整数的相似度为Nc/Ntx 100%，其中Nc为两组整数共有的不同公共数的个数，Ntis为两组整数共有的不同公共数的总数。你的工作是计算任何给定的集合对的相似性。
代码：
#include<iostream>
#include<set>
using namespace std;
set<int> st[55];
int main(){
int N, tmp, score;
cin >> N;
for(int i = 1; i <= N; i++){
cin >> tmp;
while(tmp--){
cin >> score;
st[i].insert(score);
}
}
int M, X, Y;
cin >> M;
while(M--){
cin >> X >> Y;
int num_intersection = 0, num_union = 0;
for(set<int>::iterator it = st[X].begin(); it != st[X].end(); it++){
if(st[Y].find(*it) != st[Y].end()) num_intersection++;
}
num_union = st[X].size() + st[Y].size() - num_intersection;
printf("%.1f%\n", 100.0 * num_intersection / num_union);
}
return 0;
}
3.String类
如果一台机器只能保存3位有效数字，则浮点数12300和12358.9被认为是相等的，因为它们都被简单地截断为0.123x10^ 5。现在，给定一台机器上的有效数字和两个浮点数的数量，你应该知道它们在该机器中是否被平等对待。
代码：
#include<iostream>
#include<string>
using namespace std;
int n;//有效数字位数
string deal(string str, int &e)
{
//首先删除字符串的前导零
while(str.length() > 0 && str[0] == '0')
str.erase(str.begin());
//若此时首位为小数点，则去掉
if(str[0] == '.'){
str.erase(str.begin());
//并继续删除零
while(str.length() > 0 && str[0] == '0'){
str.erase(str.begin());
//指数为负数
e--;
}
}else if(str.find('.') != string::npos){
//首位不是小数点，则寻找位置，此时指数=小数点位置
e += str.find('.');
//删除小数点
str.erase(str.begin() + e);
}//找不到小数点，则指数=字符串长度
else e += str.length();
if(str.length() == 0) e = 0;
int num = 0, k = 0;
string res;
//将字符串控制在有效数字长度
while(num < n){
if(k < str.length()) res += str[k++];
//原数字位数不够，补零
else res += '0';
num ++;
}
return res;
}
int main()
{
int e1 = 0, e2 = 0;
string str1, str2, str3, str4;
cin >> n >> str1 >> str2;
str3 = deal(str1, e1);
str4 = deal(str2, e2);
if(str3 == str4 && e1 == e2){
cout << "YES 0." << str3 << "*10^" << e1 << endl;
}
else
cout << "NO 0." << str3 << "*10^" << e1 << " 0." << str4 << "*10^" << e2 <<endl;
return 0;
}十三、模拟
1.矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
思路：K神解析
| 打印方向 | 1.根据边界打印 | 2.边界向内收缩 | 3.是否打印完毕 |
| 从左向右 | 左边界 l ，右边界 r | 上边界 t++ | 是否 t > b |
| 从上向下 | 上边界 t ，下边界 b | 右边界 r-- | 是否 r < l |
| 从右向左 | 右边界 r ，左边界 l | 下边界 b-- | 是否 b < t |
| 从下向上 | 下边界 b， 上边界 t | 左边界 l++ | 是否 l > r |
代码：
vector<int> spiralOrder(vector<vector<int>>& matrix) {
//特殊情况
if(matrix.empty()) return {};
vector<int> res;
//初始化边界
int l = 0;//左边界
int r = matrix[0].size() - 1;//右边界
int t = 0;//上边界
int b = matrix.size() - 1;//下边界
while(true){
//左 -> 右
for(int i = l; i <= r; i++) res.push_back(matrix[t][i]);
if(++t > b) break;
//上 -> 下
for(int i = t; i <= b; i++) res.push_back(matrix[i][r]);
if(--r < l) break;
//右 -> 左
for(int i = r; i >= l; i--) res.push_back(matrix[b][i]);
if(--b < t) break;
//下 -> 上
for(int i = b; i >= t; i--) res.push_back(matrix[i][l]);
if(++l > r) break;
}
return res;
}2.栈
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
思路：K神解析
借用辅助栈进行模拟：
- 入栈操作：按照压栈序列的顺序执行。
- 出栈操作：每次入栈后，循环判断 “栈顶元素 == 弹出序列的当前元素” 是否成立，将符合弹出序列顺序的栈顶元素全部弹出。
代码：
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
if(pushed.size() == 0) return true;
stack<int> s;//辅助栈
int j = 0;//出栈序列的指针
for(int i = 0; i < pushed.size(); i++){
s.push(pushed[i]);
//判断是否出栈
while(!s.empty() && popped[j] == s.top()){
s.pop();
j++;
}
}
if(s.empty()) return true;
return false;
}3.字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
代码：
class Solution {
private:
//整数可以用[+|-]unsigned int表示
bool scanInt(const string s, int& index){
if(s[index] == '+' || s[index] == '-') index++;
return scanUnsingnedInt(s, index);
}
bool scanUnsingnedInt(const string s, int& index){
int befor = index;
while(index != s.size() && s[index] >= '0' && s[index] <= '9') index++;
return index > befor;
}
public:
//数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，
//其中A和C都是整数，而B是无符号整数
bool isNumber(string s) {
if(s.size() == 0) return false;
int index = 0;
//字符串开始有空格，可以返回true
while(s[index] == ' ') index++;
bool numeric = scanInt(s, index);
//如果出现'.'，则接下来是小数部分
if(s[index] == '.'){
index++;
//1.小数可以没有整数部分，如.123
//2.小数点后面可以没有数字，如233.
//3.小数点前面和后面可以均有数字
numeric = scanUnsingnedInt(s, index) || numeric;
}
//如果出现'e'或'E'，接下来是指数部分
if(s[index] == 'e' || s[index] == 'E'){
index++;
//1.当e或E前面没有数字时，不合法，如。e1
//2.当e或E后面没有整数时，不合法，如12e
numeric = numeric && scanInt(s, index);
}
//字符串结尾有空格，可以返回true
while(s[index] == ' ') index++;
return numeric && index == s.size();
}
};写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
代码：
class Solution {
public:
int strToInt(string str) {
bool sign = true; //默认为正数
//先舍弃开头可能存在的空格
int i = 0;
while(i < str.size() && str[i] == ' ') i++;
//接着判断首个字符是否为正负号
if(str[i] == '-') {
sign = false; //该字符串片段为负数
i++; //移至下一个字符接着判断
}
else if(str[i] == '+') i++; //如果首个字符为‘+’则sign已经默认为true而无须更改，直接移动到下一位即可
//下面开始对非正负符号位进行判断
if(str[i] < '0' || str[i] > '9') return 0; //如果第一个正负号字符后的首个字符就不是数字字符(也可能第一个字符就不是正负号)，那么直接返回0
int res = 0; //这里res用的int型，需要更加仔细考虑边界情况，但如果用long的话可以省去一些麻烦
//用来单独存储单个字符转换而成的数字
int num;
// 用来验证计算结果是否溢出int范围的数据
// 2147483647/10=214748364
int border = INT_MAX / 10;
while(i < str.size()){
if(str[i] < '0' || str[i] > '9') break; //遇到非数字字符则返回已经计算的res结果
if(res > border || res == border && str[i] > '7') //注意这句话要放在字符转换前，因为需要验证的位数比实际值的位数要少一位
//这里比较巧妙的地方在于 1. 用低于int型数据长度一位的数据border判断了超过int型数据长度的值 2. 将超过最大值和低于最小值的情况都包括了
//看似没有考虑 MIN, 但其实无论是 = '8' ,还是 >'8',返回的都是MIN。
return sign == true ? INT_MAX : INT_MIN;
//开始对数字字符进行转换
num = str[i] - '0';
res = res * 10 + num;
i++;
}
//最后结果根据符号添加正负号
return sign == true ? res : -res;
}
};版权声明：本文为weixin_52137590原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。