《剑指Offer》学习记录

1、找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

1、数组中重复的数字

①
class Solution {
public:
//使用set判断是否遇到过重复
int findRepeatNumber(vector& nums) {
set rec;
int ans=0;
for(auto a:nums){
if(rec.count(a)){
ans=a;
break;
}
rec.insert(a);
}
return ans;
}
};
②
class Solution {
public:
//原地判断
//注意利用题目条件：因为数组长度为n，而所有数字都在0~n-1范围内
//如果没有重复的话，说明每个数字都有他们自己一一对应的位置
//在遍历的过程中，用while循环找到当前下标对应的数字
//这个while循环过程中，可以把后面部分的数字排好，之后for循环就进入while，相当于O1时间复杂度
//while循环中找到重复就返回
int findRepeatNumber(vector& nums) {
for(int i=0;i<nums.size();++i){
while(i!=nums[i]){
if(nums[i]==nums[nums[i]]) return nums[i];
swap(nums[i],nums[nums[i]]);
}
}
return -1;
}
};Q

2、请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

2、替换空格

class Solution {
public:
//原字符串上修改
string replaceSpace(string s) {
int countSpace=0;
for(auto a:s){
if(a==‘ ‘) ++countSpace;
}

    int oldSize=s.size();
    s.resize(s.size()+2*countSpace);
    
    for(int i=s.size()-1, j=oldSize-1;j>=0;--i,--j){
        if(s[j]==‘ ‘){
            s[i--]=‘0‘;
            s[i--]=‘2‘;
            s[i]=‘%‘;
        }else{
            s[i]=s[j];
        }
    }
    return s;
}

};

3、输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

3、从尾到头打印链表

①
class Solution {
public:
//递归解法
vector reversePrint(ListNode* head) {
vector ans;
t(head, ans);
return ans;
}
void t(ListNode* head, vector &ans){
if(!head) return;
t(head->next, ans);
ans.push_back(head->val);
}
};
②
class Solution {
public:
//栈或反转数组或反转链表解法
vector reversePrint(ListNode* head) {
stack save;
while(head){
save.push(head->val);
head=head->next;
}
vector ans;
while(!save.empty()){
ans.push_back(save.top());
save.pop();
}
return ans;
}
};

4、输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

4、重建二叉树

class Solution {
public:
//思路就是，前序找根节点，中序中对应根节点的左边就是左子树，右边就是右子树，递归不断寻找构造
//用map记录inorder中各个元素对应的索引，方便从前序中找到根节点后，从中序中找对应的左子树和右子树
//不用map可以在递归中循环遍历寻找、
TreeNode* buildTree(vector& preorder, vector& inorder) {
unordered_map<int,int> m;
for(int i=0;i<inorder.size();++i) m[inorder[i]]=i;
return recursion(preorder, inorder, m, 0, inorder.size(), 0);
}
TreeNode* recursion(vector&preorder, vector&inorder, unordered_map<int,int> &m, int left, int right, int currPre){
if(left>=right) return nullptr;
TreeNode* curr=new TreeNode(preorder[currPre]);
int i=m[preorder[currPre]];
curr->left=recursion(preorder, inorder, m, left, i, currPre+1);
curr->right=recursion(preorder, inorder, m, i+1, right, currPre+i-left+1);
return curr;
}
};

5、用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

5、用两个栈实现队列

class CQueue {
public:
stack s1,s2;
CQueue() {
}

void appendTail(int value) {
    s1.push(value);
}

int deleteHead() {
    if(s2.empty()){
        while(!s1.empty()){
            int save=s1.top();
            s1.pop();
            s2.push(save);
        }
    }
    int res=-1;
    if(!s2.empty()){
        res=s2.top();
        s2.pop();
    }
    return res;
}

};

6、写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

6、斐波那契数列

class Solution {
public:
//状态压缩dp
const int mod=1e9+7;
int fib(int n) {
if(n0||n1) return n;
int l=0, r=1, ans;
for(int i=2;i<=n;++i){
ans=(l+r)%mod;
l=r;
r=ans;
}
return ans;
}
};

7、一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

7、青蛙跳台阶问题

class Solution {
public:
//状态压缩dp，和斐波那契数列一样
const int mod=1e9+7;
int numWays(int n) {
if(n<2) return 1;
int dp, a=1, b=2;
for(int i=3;i<=n;++i){
dp=(a+b)%mod;
a=b;
b=dp;
}
return dp;
}
};

8、把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

8、旋转数组的最小数字

class Solution {
public:
//二分，分三种情况，只能到最后left=right时才能确定结果
//小于，说明mid是最小或者在最小的右边
//大于，说明mid在最小的左边
//等于，说明mid可能是最小或最小的右边，但是因为不是严格递增，所以mid也有可能是最小的左边，所以只能明确right不是结果，因为等于的话，只有mid有可能是结果
int minArray(vector& numbers) {
int left=0, right=numbers.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(numbers[mid]<numbers[right]) right=mid;
else if(numbers[mid]>numbers[right]) left=mid+1;
else --right;
}
return numbers[left];
}
};

9、请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

9、矩阵中的路径

class Solution {
public:
//dfs，剪枝
//不能使用vis数组，会超时，只能在dfs过程中更改board的值判断完后再改回来
bool exist(vector<vector>& board, string word) {
for(int i=0;i<board.size();++i){
for(int j=0;j<board[0].size();++j){
if(dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
bool dfs(vector<vector>& board, string &word, int x, int y, int index){
if(x<0||x>=board.size()||y<0|y>=board[0].size()) return false;
if(word[index]!=board[x][y]) return false;
if(index==word.size()-1) return true;
char save=board[x][y];
board[x][y]=‘0‘;
if(dfs(board, word, x+1, y, index+1)
||dfs(board, word, x-1, y, index+1)
||dfs(board, word, x, y+1, index+1)
||dfs(board, word, x, y-1, index+1)) return true;
board[x][y]=save;
return false;
}
};

10、地上有一个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。请问该机器人能够到达多少个格子？

10、机器人的运动范围

①
class Solution {
public:
//使用队列
int movingCount(int m, int n, int k) {
vector<vector> vis(m, vector(n, false));
queue<pair<int,int>> q;
q.push({0,0});
vis[0][0]=true;
int ans=1;
while(!q.empty()){
auto save=q.front();
q.pop();
auto new1=save;
++new1.first;
auto new2=save;
++new2.second;
if(new1.first>=0&new1.first<m&&new1.second>=0&&new1.second<n
&&getSum(new1)<=k&&!vis[new1.first][new1.second]){
q.push(new1);
ans++;
vis[new1.first][new1.second]=true;
}
if(new2.first>=0&new2.first<m&&new2.second>=0&&new2.second<n
&&getSum(new2)<=k&&!vis[new2.first][new2.second]){
q.push(new2);
ans++;
vis[new2.first][new2.second]=true;
}
}
return ans;
}
int getSum(pair<int,int> p){
return p.first/10+p.first%10+p.second/10+p.second%10;
}
};
②
class Solution {
public:
//递归实现
int ans=0;
int movingCount(int m, int n, int k) {
vector<vector> vis(m, vector(n, false));
dfs(0,0,m,n,k,vis);
return ans;
}
void dfs(int x, int y, int m, int n, int k, vector<vector> &vis){
if(x<0||x>=m||y<0||y>=n
||getSum(x,y)>k||vis[x][y]) return;
++ans;
vis[x][y]=true;
dfs(x+1,y,m,n,k,vis);
dfs(x,y+1,m,n,k,vis);
}
int getSum(int x, int y){
return x/10+x%10+y/10+y%10;
}
};

11、给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。剪绳子1：n<=58；剪绳子2：n<=1000

11、剪绳子1

①
class Solution {
public:
//数论+贪心
//有3全取3，余1取一个22，余2取一个2
int cuttingRope(int n) {
if(n<=3) return n-1;
if(n%30) return pow(3, n/3);
else if(n%31) return pow(3,(n-4)/3)4;
else return pow(3, (n-2)/3)2;
}
};
②
class Solution {
public:
//因为在dp运算过程中，0~3都是要不剪的
//所以n<=3先提前返回结果
//j<=i/2，因为dp[1]dp[3]==dp[3]dp[1]
//dp数组存的是当前长度的最大乘积，如何利用记忆好的数组，就是靠再遍历一次
int cuttingRope(int n) {
if(n<=3) return n-1;
vector dp(n+1);
dp[0]=0;
dp[1]=1;
dp[2]=2;
dp[3]=3;
for(int i=4;i<=n;++i){
for(int j=0;j<=i/2;++j){
dp[i]=max(dp[j]dp[i-j],dp[i]);
}
}
return dp[n];
}
};

12、剪绳子2

class Solution {
public:
//跟剪绳子1差不多，但是就是会爆掉int
//怎么解决，就是用long long类型存着，过程中求余
//n>4，因为1取1，2取2，3取3，余1即4取4
const int mod=1e9+7;
int cuttingRope(int n) {
if(n<=3) return n-1;
long long ans=1;
while(n>4){
ans=(ans3)%mod;
n-=3;
}
return ansn%mod;
}
};

13、请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。（输入就是二进制）

13、二进制中1的个数

①
class Solution {
public:
//每次用1和最后一位进行与运算，然后右移去掉一位，直到为0（所有剩下的都是前置0或者什么都没有）
//用1的时候，假如n是1010101，1会自动补0，0000001
int hammingWeight(uint32_t n) {
int count=0;
while(n){
if(n&1) ++count;
n>>=1;
}
return count;
}
};
②
class Solution {
public:
//每次清除最右边的一个1（1后面可能还有0）
//将目标二进制-1再相与，就可以将最右边的1置0
//比方法一好，这里的次数就是1出现的个数
int hammingWeight(uint32_t n) {
int count=0;
while(n){
++count;
n&=(n-1);
}
return count;
}
};

14、实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。（-100.0 < x < 100.0。n 是 32 位有符号整数，其数值范围是 [?231, 231 ? 1] 。）

14、数值的整数次方

class Solution {
public:
//要用位运算快速幂，首先排除特殊情况
//要用long long类型，因为?2^31, 2^31 ? 1，n取最小转换会溢出
double myPow(double x, int n) {
if(x1 || n0) return 1;
if(x0 || n1) return x;
double ans=1.0;
long long newN=abs(n);
while(newN){
if(newN&1) ans=x;
x=x;
newN>>=1;
}
if(n<0) return 1/ans;
return ans;
}
};

15、输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

15、打印从1到最大的n位数

①
class Solution {
public:
//大数解法
vector ans;
vector printNumbers(int n) {
string s(n,‘0‘);
//循环打印直到越界
while(!overflow(s)) newPush(s);
return ans;
}
bool overflow(string& s){
bool isOverflow=false;
int carry=0;
for(int i=s.size()-1;i>=0;--i){
//当前位置的int类型
int curr=s[i]-‘0‘+carry;
//从个位开始+1
if(is.size()-1) ++curr;
//判断是否>=10
if(curr>=10){
//如果是最高位，这位是10，说明越界了
if(i0) isOverflow=true;
else{
//放回string里，进位设为1
s[i]=curr-10+‘0‘;
carry=1;
}
}else{
//如果<10，说明不需要进行，也不需要之后高位的计算
s[i]=curr+‘0‘;
break;
}
}
return isOverflow;
}
//清除前置零
void newPush(string& s){
//当前是否为前置零
int preZero=1;
//暂存清除前置零的字符串
string temp;
for(int i=0;i<s.size();++i){
//如果是前置零，这次循环什么都不做
//如果不是前置零，把标志设为false
if(preZero&&s[i]!=‘0‘) preZero=false;
//标志设为false后，字符串都会存起来
if(!preZero) temp+=s[i];
}
ans.push_back(stoi(temp));
}
};
②
class Solution {
public:
//递归全排列
vector ans;
vector printNumbers(int n) {
string s(n,‘0‘);
//确定当前位，递归下一位
permutation(s, 0);
return ans;
}
void permutation(string &s, int pos){
//当pos字符串的长度时，说明当前字符串确定完了
if(poss.length()){
newPush(s);
return;
}
for(int i=0;i<=9;++i){
s[pos]=i+‘0‘;
permutation(s, pos+1);
}
}
//清除前置零
void newPush(string& s){
//当前是否为前置零
int preZero=1;
//暂存清除前置零的字符串
string temp;
for(int i=0;i<s.size();++i){
//如果是前置零，这次循环什么都不做
//如果不是前置零，把标志设为false
if(preZero&&s[i]!=‘0‘) preZero=false;
//标志设为false后，字符串都会存起来
if(!preZero) temp+=s[i];
}
//当s为000时，temp为空，需要特判
if(temp!="") ans.push_back(stoi(temp));
}
};

16、给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

16、删除链表的结点

①迭代
class Solution {
public:
//迭代实现
ListNode* deleteNode(ListNode* head, int val) {
ListNode* dummyHead=new ListNode(-1);
dummyHead->next=head;
ListNode* pre=dummyHead, curr=head;
while(head){
if(curr->val==val){
pre->next=curr->next;
break;
}
pre=curr;
curr=curr->next;
}
return dummyHead->next;
}
};
②递归
class Solution {
public:
//递归实现
ListNode deleteNode(ListNode* head, int val) {
if(!head) return nullptr;
if(head->val==val) return head->next;
head->next=deleteNode(head->next, val);
return head;
}
};

18、请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

18、表示数值的字符串

class Solution {
public:
//二刷再精简吧，太繁琐了
bool isNumber(string s) {
bool noNum=1, noE=1, noPoint=1;
while(s.size()&&s[0]‘ ‘) s.erase(0,1);
while(s.size()&&s[s.size()-1]‘ ‘) s.erase(s.size()-1,1);
for(int i=0;i<s.size();++i){
if(s[i]‘+‘||s[i]‘-‘) {
if(i0) continue;
else if((s[i-1]!=‘e‘&&s[i-1]!=‘E‘)) return false;
else if(is.size()-1||s[i+1]<‘0‘||s[i+1]>‘9‘) return false;
}
else if(s[i]‘e‘||s[i]‘E‘){
if(!noE) return false;
else if((s[i-1]<‘0‘||s[i-1]>‘9‘)&&s[i-1]!=‘.‘) return false;
else if(is.size()-1) return false;
else if((s[i+1]<‘0‘||s[i+1]>‘9‘)
&&s[i+1]!=‘-‘&&s[i+1]!=‘+‘) return false;
noE=0;
}
else if(s[i]‘.‘){
if(!noE) return false;
else if(!noPoint) return false;
else if(i0&&i+1<s.size()
&&(s[i+1]<‘0‘||s[i+1]>‘9‘)) return false;
else if(is.size()-1&&i-1>=0
&&(s[i-1]<‘0‘||s[i-1]>‘9‘)) return false;
else if((s[i+1]<‘0‘||s[i+1]>‘9‘)
&&(s[i-1]<‘0‘||s[i-1]>‘9‘)) return false;
noPoint=0;
}
else if(s[i]>=‘0‘&&s[i]<=‘9‘){
noNum=0;
}
else return false;
}
if(noNum) return false;
return true;
}
};
19、输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

19、调整数组顺序使奇数位于偶数前面

class Solution {
public:
//双指针，从后面找奇数，从前面找偶数
vector exchange(vector& nums) {
int odd=0, even=nums.size()-1;
while(odd<even){
while(odd<even&&(nums[odd]&1)1) ++odd;
while(odd<even&&(nums[even]&1)0) --even;
if(odd<even) swap(nums[odd], nums[even]);
}
return nums;
}
};

20、输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

20、链表中倒数第k个节点

class Solution {
public:
//双指针，第一个指针先走k步
//第一个指针走完k步后，两个指针一起走，直到第一个指针走到链表尾
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *first=head, *second=head;
while(k--&&first) first=first->next;
while(first){
first=first->next;
second=second->next;
}
return second;
}
};

21、定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

21、反转链表

①
class Solution {
public:
//迭代实现，需要三个指针，前中后
//调整时，保存中指针的下一个结点到后指针，中指针的next指向前指针
//前指针指向中指针，中指针指向后指针
ListNode* reverseList(ListNode* head) {
ListNode pre=nullptr;
while(head){
ListNode curr=head->next;
head->next=pre;
pre=head;
head=curr;
}
return pre;
}
};

②
class Solution {
public:
//递归实现
//if的第一个条件是避免一开始head就是空指针，之后都是使用head->next这个条件
//当head->next为空，说明head是最后一个结点，又是反转后链表的头结点，之后return都是这个指针
//递归进行完后进行回溯，操作两个结点，第二个结点的next指向第一个结点，第一个结点的next指向nullptr
ListNode* reverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode* ret=reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return ret;
}
};

22、输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

22、合并两个排序的链表

①
class Solution {
public:
//迭代实现，伪头结点
//dummyHead上的结点都是已经由curr确定过的
//l1和l2比较，小的一个接到curr->next上，再移动curr指针和小的指针
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummyHead=new ListNode(-1);
ListNode *curr=dummyHead;
while(l1&&l2){
if(l1->val<=l2->val){
curr->next=l1;
curr=l1;
l1=l1->next;
}else{
curr->next=l2;
curr=l2;
l2=l2->next;
}
}
if(l1) curr->next=l1;
if(l2) curr->next=l2;
return dummyHead->next;
}
};

②
class Solution {
public:
//递归实现
//结束递归的标志是任意一个链表为空，即确认完一个链表，返回另一个链表
//比较当前两个结点的大小，小的结点留下来，递归下一个结点和大的结点
//递归返回的结果接在小的结点的后面，返回小结点
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
if(l1->val<=l2->val){
l1->next=mergeTwoLists(l1->next, l2);
return l1;
}else{
l2->next=mergeTwoLists(l1, l2->next);
return l2;
}
}
};

23、输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即A中有出现和B相同的结构和节点值。

23、树的子结构

①
class Solution {
public:
//迭代实现，对A树进行遍历，找到和B树根相同的，在同时对A子树和B树进行遍历
//以B树为主体，遍历时，B有A没有必错，B不等于A必错
//当遍历完B树时，即有相同子树
//当遍历完A树时，即没有相同子树
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(!B) return false;
stack<TreeNode> s;
s.push(A);
while(!s.empty()){
TreeNode curr=s.top();
s.pop();
if(curr->val==B->val){
stack<TreeNode*> a,b;
a.push(curr);
b.push(B);
int flag=1;
while(!b.empty()){
TreeNode *ACurr=a.top();
TreeNode *BCurr=b.top();
a.pop();
b.pop();
if((ACurr->val!=BCurr->val)||(!ACurr->left&&BCurr->left)
||(!ACurr->right&&BCurr->right)){
flag=0;
break;
}
if(BCurr->left&&ACurr->left){
a.push(ACurr->left);
b.push(BCurr->left);
}
if(BCurr->right&&ACurr->right){
a.push(ACurr->right);
b.push(BCurr->right);
}
}
if(flag) return true;
}
if(curr->left) s.push(curr->left);
if(curr->right) s.push(curr->right);
}
return false;
}
};

②
class Solution {
public:
//递归实现
//首先B不能为空，A为空说明已经到达某个叶子节点
//return处使用或运算，judge比较当前结点是否相同，并且会递归遍历整棵B树和A子树
//对A左子树和右子树进行递归，如果任意一棵子树下有和B相同结构，就返回true，所以使用或运算
//judge函数是用来递归判断B树的
//如果B为空，说明到达某个叶子节点之前的路径和A子树的对应路径都是相同的
//如果B不为空，A为空，即A子树不完全包含整棵B树
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(!A||!B) return false;
return judge(A, B)||isSubStructure(A->left, B)||isSubStructure(A->right, B);
}
bool judge(TreeNode* A, TreeNode* B){
if(!B) return true;
if(!A) return false;
if(A->val!=B->val) return false;
else return judge(A->left, B->left)&&judge(A->right, B->right);
}
};

24、请完成一个函数，输入一个二叉树，该函数输出它的镜像。

24、二叉树镜像

①
class Solution {
public:
//递归实现，先走到最底层，再往上一层一层的交换
TreeNode* mirrorTree(TreeNode* root) {
if(!root) return root;
mirrorTree(root->left);
mirrorTree(root->right);
mySwap(root);
return root;
}
void mySwap(TreeNode* root){
TreeNode temp=root->left;
root->left=root->right;
root->right=temp;
}
};
②
class Solution {
public:
//迭代实现，从最高层开始交换
TreeNode mirrorTree(TreeNode* root) {
if(!root) return root;
queue<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode *curr=s.front();
s.pop();
swap(curr->left, curr->right);
if(curr->left) s.push(curr->left);
if(curr->right) s.push(curr->right);
}
return root;
}
};

25、请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

25、对称的二叉树

①
class Solution {
public:
//递归实现，同时对左子树和右子树遍历
//不相同就返回false
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return traverse(root->left, root->right);
}
bool traverse(TreeNode* left, TreeNode* right){
if(!left&&!right) return true;
if(!left||!right) return false;
if(left->val!=right->val) return false;
return traverse(left->left, right->right)&&traverse(left->right,right->left);
}
};

②迭代，一个队列或栈，一次存两个弹两个。不太好的地方是，其实对称是左右平分一个树，迭代会遍历整棵树（加起来合起来是两棵树了），而递归只遍历半棵树（分开左右，合起来是一棵树）

26、输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

26、顺时针打印矩阵

class Solution {
public:
vector spiralOrder(vector<vector>& matrix) {
vector ans;
if(matrix.size()0||matrix[0].size()0) return ans;
int left=0, right=matrix[0].size()-1, top=0, bottom=matrix.size()-1;
while(left<=right&&top<=bottom){
for(int i=left;i<=right;++i) ans.push_back(matrix[top][i]);
if(++top>bottom) break;
for(int i=top;i<=bottom;++i) ans.push_back(matrix[i][right]);
if(left>--right) break;
for(int i=right;i>=left;--i) ans.push_back(matrix[bottom][i]);
if(top>--bottom) break;
for(int i=bottom;i>=top;--i) ans.push_back(matrix[i][left]);
if(++left>right) break;
}
return ans;
}
};

27、定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

27、包含min函数的栈

①
class MinStack {
public:
//使用辅助栈，主栈push时，辅助栈push当前最小值
MinStack() {
}

void push(int x) {
    s.push(x);
    if(!sAssist.empty()&&x>sAssist.top()) sAssist.push(sAssist.top());
    else sAssist.push(x);
}

void pop() {
    s.pop();
    sAssist.pop();
}

int top() {
    return s.top();
}

int min() {
    return sAssist.top();
}

private:
stack s, sAssist;
};

②
class MinStack {
public:
//一个栈完成，当push的x小于等于最小值，就要先把最小值压入栈，并更新最小值为x，再将x压栈
//弹出的时候，先判断栈顶是不是最小值，不是可以直接弹出；是最小值的话，需要先弹出栈顶元素，下一个栈顶元素就是新的最小值了，更新最小值后再次弹出
//总结就是，因为push时要更新最小值时会把最小值先压栈，方便pop时可以获取新的最小值
MinStack() {
minNum=INT_MAX;
}

void push(int x) {
    if(x<=minNum) {
        s.push(minNum);
        minNum=x;
    }
    s.push(x);
}

void pop() {
    if(s.top()==minNum){
        s.pop();
        minNum=s.top();
        s.pop();
    }else{
        s.pop();
    }
}

int top() {
    return s.top();
}

int min() {
    return minNum;
}

private:
stack s;
int minNum;
};

28、输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

28、栈的压入、弹出序列

class Solution {
public:
//借助数据结构栈，循环遍历pushed数组，压栈
//压栈后判断栈顶元素是否和poped数组当前元素相等
//相等则弹出，再重复进行判断；不相等则进行下一次循环
bool validateStackSequences(vector& pushed, vector& popped) {
stack test;
for(int i=0,j=0;i<pushed.size();++i){
test.push(pushed[i]);
while(!test.empty()&&test.top()==popped[j]){
test.pop();
++j;
}
}
return test.empty();
}
};

29、从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

29、从上到下打印二叉树 Ⅰ

class Solution {
public:
vector levelOrder(TreeNode* root) {
vector ans;
if(!root) return ans;
queue<TreeNode> q;
q.push(root);
while(!q.empty()){
TreeNode curr=q.front();
q.pop();
ans.push_back(curr->val);
if(curr->left) q.push(curr->left);
if(curr->right) q.push(curr->right);
}
return ans;
}
};

30、从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

30、从上到下打印二叉树 Ⅱ

①BFS
class Solution {
public:
vector<vector> levelOrder(TreeNode* root) {
vector<vector> ans;
if(!root) return ans;
queue<TreeNode> q;
q.push(root);
while(!q.empty()){
int size=q.size();
vector ansP;
while(size--){
TreeNode curr=q.front();
ansP.push_back(curr->val);
q.pop();
if(curr->left) q.push(curr->left);
if(curr->right) q.push(curr->right);
}
ans.push_back(ansP);
}
return ans;
}
};

②DFS
class Solution {
public:
vector<vector> levelOrder(TreeNode* root) {
vector<vector> ans;
dfs(root, ans, 0);
return ans;
}
void dfs(TreeNode* root, vector<vector>&ans, int level){
if(!root) return;
if(level==ans.size()) ans.push_back(vector());
ans[level].push_back(root->val);
dfs(root->left, ans, level+1);
dfs(root->right, ans, level+1);
}
};

31、请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

31、从上到下打印二叉树 III

class Solution {
public:
//奇数层从右往左，偶数层从左往右，利用栈的特性即可实现
//主要还是注意记录层数和按什么方式入栈
vector<vector> levelOrder(TreeNode* root) {
vector<vector> ans;
if(!root) return ans;
stack<TreeNode*> odd, even;
even.push(root);
int level=0;
while(!odd.empty()||!even.empty()){
vector ansP;
//当前是奇数层
if(level&1){
int size=odd.size();
while(size--){
TreeNode curr=odd.top();
odd.pop();
ansP.push_back(curr->val);
//从右往左压入偶数栈
if(curr->right) even.push(curr->right);
if(curr->left) even.push(curr->left);
}
}
//当前是偶数层
else{
int size=even.size();
while(size--){
TreeNode curr=even.top();
even.pop();
ansP.push_back(curr->val);
//从左往右压入奇数栈
if(curr->left) odd.push(curr->left);
if(curr->right) odd.push(curr->right);
}
}
ans.push_back(ansP);
++level;
}
return ans;
}
};

32、输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

32、二叉搜索树的后序遍历序列

class Solution {
public:
//BST的特性，左<中<右，后序遍历的特点就是先小再大再中
//对于数组就考虑后序遍历、递归的方法、还有遍历的特性
//这里的特性就是，最右边的一定是根节点，数组左边是左子树，左边到最右边为右子树
//那么左子树一定比根节点小，右子树一定比根节点大
bool verifyPostorder(vector& postorder) {
if(postorder.size()==0) return true;
return dfs(postorder, 0, postorder.size()-1);
}
bool dfs(vector& postorder, int begin, int end){
if(begin>=end) return true;
int leftB, leftE, rightB, rightE;
int countL=0, countR=0;
for(int i=begin;i<end;++i){
if(postorder[i]<postorder[end]) countL++;
}
for(int i=begin+countL;i<end;++i){
if(postorder[i]>postorder[end]) countL++;
else return false;
}
leftB=begin;
leftE=leftB+countL-1;
rightB=begin+countL;
rightE=rightB+countR-1;
return dfs(postorder, leftB, leftE)&&dfs(postorder, rightB, rightE);
}
};

33、输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

33、二叉树中和为某一值的路径

class Solution {
public:
//递归实现
vector<vector> pathSum(TreeNode* root, int sum) {
vector<vector> ans;
vector ansP;
dfs(root, sum, ans, ansP);
return ans;
}
void dfs(TreeNode* root, int sum, vector<vector> &ans, vector &ansP){
if(!root) return;
ansP.push_back(root->val);
sum-=root->val;
if(sum==0&&!root->left&&!root->right) ans.push_back(ansP);
dfs(root->left, sum, ans, ansP);
dfs(root->right, sum, ans, ansP);
ansP.pop_back();
}
};

34、请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

34、复杂链表的复制

class Solution {
public:
//利用map存旧结点对应新结点的位置
//第一次遍历复制链表，第二次遍历复制random
Node* copyRandomList(Node* head) {
if(!head) return head;
Node* dummyHead=new Node(-1);
map<Node,Node> m;
Node* curr=head, *currCopy=dummyHead;
while(curr){
currCopy->next=new Node(curr->val);
m[curr]=currCopy->next;
curr=curr->next;
currCopy=currCopy->next;
}
curr=head, currCopy=dummyHead->next;
while(curr){
currCopy->random=m[curr->random];
curr=curr->next;
currCopy=currCopy->next;
}
return dummyHead->next;
}
};

35、输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

35、二叉搜索树与双向链表

①
class Solution {
public:
//先掏出中序遍历非递归的模板
//因为结点有前后指针，所以要同时操作两个结点，分别用pre和root表示
//head是确定头结点，第一个拿出来的点，即head没确定时，这个点就是head
//第一个点没有pre，所以要第二个点才开始改指向操作
Node* treeToDoublyList(Node* root) {
if(!root) return root;
Node* head=nullptr, pre=nullptr;
stack<Node> s;
while(!s.empty()||root){
while(root) {
s.push(root);
root=root->left;
}
root=s.top();
s.pop();
if(!head) head=root;
if(pre){
pre->right=root;
root->left=pre;
}
pre=root;
root=root->right;
}
//头尾相连
head->left=pre;
pre->right=head;
return head;
}
};
②
class Solution {
public:
//递归实现
Node* head=nullptr, pre=nullptr;
Node treeToDoublyList(Node* root) {
if(!root) return root;
inorder(root);

    //头尾相连
    head->left=pre;
    pre->right=head;
    return head;
}
void inorder(Node* root){
    if(!root) return;
    inorder(root->left);
    if(!head) head=root;
    if(pre) {
        pre->right=root;
        root->left=pre;
    }
    pre=root;
    inorder(root->right);
}

};

36、请实现两个函数，分别用来序列化和反序列化二叉树。

36、序列化二叉树

class Codec {
public:
//下次二刷记得用ostringstream
//没啥思路，就是模拟
string serialize(TreeNode* root) {
if(!root) return "";
string ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode *curr=q.front();
q.pop();
if(curr) ans+=to_string(curr->val);
else{
ans+="null";
ans+=",";
continue;
}
ans+=",";
q.push(curr->left);
q.push(curr->right);
}
ans.pop_back();
while(ans[ans.size()-1]==‘l‘) ans.resize(ans.size()-5);
return ans;
}

TreeNode* deserialize(string data) {
    if(data.size()==0) return nullptr;
    string dataSpace;
    for(int i=0;i<data.size();++i){
        if(data[i]==‘n‘){
            dataSpace+=" ";
            i+=3;
        }else{
            dataSpace+=data[i];
        }
    }
    vector<TreeNode*> res;
    for(int i=0;i<dataSpace.size();++i){
        if(dataSpace[i]==‘,‘) continue;
        else if(dataSpace[i]!=‘ ‘){
            int count=1;
            while(i<dataSpace.size()&&dataSpace[++i]!=‘,‘) ++count;
            string str;
            if(i==dataSpace.size()) str=dataSpace.substr(i-count+1,count-1);
            else str=dataSpace.substr(i-count,count);
            int save=stoi(str);
            res.push_back(new TreeNode(save));
        } 
        else if(dataSpace[i]==‘ ‘) res.push_back(nullptr);
    }
    
    int pos=1;
    for(int i=0;pos<res.size();++i){
        if(!res[i]) continue;
        res[i]->left = res[pos++]; 
        if(pos<res.size()){
            res[i]->right = res[pos++]; 
        }
    }

    return res[0];
}

};

37、输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

37、字符串的排列

class Solution {
public:
//递归全排列，O(n!)
//打印从1到最大的n位数也是用全排列，但是和这道题有区别
//这道题也能那道题的全排列方法，时间复杂度是O(n^n)
vector ans;
unordered_set checkAns;
vector permutation(string s) {
permutation(s, 0);
return ans;
}
void permutation(string& s, int pos){
if(pos==s.length()){
if(checkAns.count(s)) return;
checkAns.insert(s);
ans.push_back(s);
return;
}
for(int i=pos;i<s.size();++i){
swap(s[i],s[pos]);
permutation(s, pos+1);
swap(s[i],s[pos]);
}
}
};

38、数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

38、数组中出现次数超过一半的数字

class Solution {
public:
//摩尔投票法
int majorityElement(vector& nums) {
int res, count=0;
for(int i=0;i<nums.size();++i){
if(count==0) res=nums[i];
if(res!=nums[i]) --count;
else ++count;
}
return res;
}
};

39、输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

39、最小的k个数（TopK）

①
class Solution {
public:
//先排序再取前k个数，nlogn
vector getLeastNumbers(vector& arr, int k) {
vector ans;
if(k0) return ans;
sort(arr.begin(),arr.end());
for(auto a: arr){
if(k0) break;
ans.push_back(a);
k--;
}
return ans;
}
};

②
class Solution {
public:
//用最大堆，先取k个数放进堆
//继续遍历剩下的，比堆顶小就弹出堆顶，压入新的数
//堆一直都是维持k个数，最后全部压入ans数组
vector getLeastNumbers(vector& arr, int k) {
vector ans;
if(k==0) return ans;
priority_queue<int, vector, less> q;
for(int i=0;i<k;++i) q.push(arr[i]);
for(int i=k;i<arr.size();++i){
if(arr[i]<q.top()){
q.pop();
q.push(arr[i]);
}
}
for(int i=0;i<k;++i){
ans.push_back(q.top());
q.pop();
}
return ans;
}
};

③
class Solution {
public:
//利用快排partition的性质，可以确定pivotkey的同时确定pivotkey左边的都比pivotkey小
vector getLeastNumbers(vector& arr, int k) {
vector ans;
quickSort(arr, k, 0, arr.size()-1);
for(int i=0;i<k;++i) ans.push_back(arr[i]);
return ans;
}
void quickSort(vector& arr, int k, int left, int right){
if(left>=right) return;
int pivotkey=partition(arr, left, right);
if(pivotkey==k-1) return;
else if(pivotkey<k-1) quickSort(arr, k, pivotkey+1, right);
else if(pivotkey>k-1) quickSort(arr, k, left, pivotkey-1);
}
int partition(vector& arr, int left, int right){
int save=arr[left];
while(left<right){
while(left<right&&arr[right]>=save) --right;
arr[left]=arr[right];
while(left<right&&arr[left]<=save) ++left;
arr[right]=arr[left];
}
arr[left]=save;
return left;
}
};

40、如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

40、数据流中的中位数

class MedianFinder {
public:
//很妙的思路，就算记住要两个优先队列也不一定做得出来
//一个优先队列放中位数左边的数，另一个放右边的数
//主要还是维护的问题，要维持左边的数比右边的数小
MedianFinder() {}

void addNum(int num) {
    if(big.size()==small.size()){
        small.push(num);
        big.push(small.top());
        small.pop();
    }
    else{
        big.push(num);
        small.push(big.top());
        big.pop();
    }
}

double findMedian() {
    if(big.size()==small.size()) return (big.top()+small.top())/2.0;
    else return big.top();
}

private:
priority_queue<int, vector, less> big;
priority_queue<int, vector, greater> small;
};

41、输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

41、 连续子数组的最大和

class Solution {
public:
//dp，dp[i]为取i下标的元素时和的最大值
//所以过程中可能出现最优结果，可以最后再遍历一次dp取出结果，也可以过程中取最大
int maxSubArray(vector& nums) {
if(nums.size()==0) return 0;
vector dp(nums.size());
dp[0]=nums[0];
int ans=dp[0];
for(int i=1;i<nums.size();++i){
dp[i]=max(nums[i], nums[i]+dp[i-1]);
ans=max(ans, dp[i]);
}
return ans;
}
};

42、输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

42、1~n整数中1出现的次数

class Solution {
public:
//找规律
//三种情况，curr=0,1,>1
int countDigitOne(int n) {
int ans=0;
long digit=1;//当前指向的位数，位数同时也代表低位的数字的数量
while(n/digit!=0){
long lowNum=n%digit, highNum=n/(digit10);//低位数值和高位数值
long curr=n/digit%10; //当前指向位数的数值
if(curr==0) ans+=highNumdigit;
else if(curr==1) ans+=highNumdigit+lowNum+1;
else ans+=(highNum+1)digit;
digit*=10;
}
return ans;
}
};

43、数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

43、数字序列中某一位的数字

class Solution {
public:
//注意直接排除n=0的情况，因为要让其他数字符合规律
//digit是数位
//start是当前数位开始的数字
//count是当前数位所有数字的长度
//while循环后定位到第n位对应的数位
//num是对应到相对的位置，n-1是因为索引从0开始
//这里之后其实用字符串更快
//n重新确定为在num的位置
int findNthDigit(int n) {
int digit=1;
long long start=1;
long long count=9;
while(n>count){
n-=count;
++digit;
start=10;
count=digit9*start;
}

    int num=start+(n-1)/digit;
    n-=digit*(num-start);
    num/=pow(10, (digit-n));
    int res=num%10;
    return res;
}

};

44、输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

44、把数组排成最小的数

class Solution {
public:
//lambda表达式，借助string解决大数问题
string minNumber(vector& nums) {
string ans;
vector numsStr;
for(auto a:nums) numsStr.push_back(to_string(a));
sort(numsStr.begin(),numsStr.end(),[](const string &a, const string &b)->bool{
return a+b<b+a;
});
for(auto a:numsStr) ans+=a;
return ans;
}
};

45、给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

45、把数字翻译成字符串

class Solution {
public:
//dp，类似斐波那契数列
//三个判断
//一、前一个数字和当前数字合并若不能进行合法翻译，即截至当前数字的解法和上一个数字的解法是一样的
//二、能合法翻译，即能合并，既截至当前数字的解法，有上一个数字解法也有上上一个数字解法
//三、能合法翻译，但是没有上上一个数字，+1
int translateNum(int num) {
string numStr=to_string(num);
vector dp(numStr.size());
dp[0]=1;
for(int i=1;i<numStr.size();++i){
if(numStr[i-1]‘0‘||numStr[i-1]>‘2‘
||(numStr[i-1]‘2‘&&numStr[i]>‘5‘)) dp[i]=dp[i-1];
else if(i>1) dp[i]=dp[i-1]+dp[i-2];
//i==1的情况
else dp[i]=dp[i-1]+1;
}
return dp[numStr.size()-1];
}
};

46、在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

46、礼物的最大价值

class Solution {
public:
//dp，二维数组
int maxValue(vector<vector>& grid) {
vector<vector> dp;
dp=grid;
for(int i=1;i<grid[0].size();++i) dp[0][i]+=dp[0][i-1];
for(int i=1;i<grid.size();++i) dp[i][0]+=dp[i-1][0];
for(int i=1;i<grid.size();i++){
for(int j=1;j<grid[0].size();++j){
dp[i][j]+=max(dp[i][j-1], dp[i-1][j]);
}
}
return dp[grid.size()-1][grid[0].size()-1];
}
};

47、请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

47、最长不含重复字符的子字符串

class Solution {
public:
//最长子字符串，最优解是要么整个字符串都不重复，要么该子字符串向前+1后刚好开头结尾字符重复
//遍历字符串，left是此时子字符串的开头，
//每到一个字符，利用map判断当前子字符串里有没有出现这个字符
//有则改变子字符串的开头
//无则子字符串增长后继续下一个字符
//利用map记录到达当前字符a前，遍历过的所有字符在字符a前的最后出现位置
//过程中可能出现最优解，用ans存并返回
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> m;
int ans=0, left=0;
for(int i=0;i<s.length();++i){
if(m.find(s[i])!=m.end()&&m[s[i]]>=left) left=m[s[i]]+1;
m[s[i]]=i;
ans=max(ans, i-left+1);
}
return ans;
}
};

48、我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

48、丑数

class Solution {
public:
//除去1，其他丑数都是由这三个质因子合成的，所以能用dp这种记忆化的方法
//三个if去除相同情况，比如26，34，而不是用if else
int nthUglyNumber(int n) {
vector dp(n);
dp[0]=1;
int p2=0, p3=0, p5=0;
for(int i=1;i<n;++i){
dp[i]=min(min(dp[p2]2, dp[p3]3), dp[p5]5);
if(dp[i]==dp[p2]2) ++p2;
if(dp[i]dp[p3]*3) ++p3;
if(dp[i]dp[p5]*5) ++p5;
}
return dp[n-1];
}
};

49、在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

49、第一个只出现一次的字符

class Solution {
public:
//vector相当于map，存每个字符出现的次数
//下一次遍历字符串，第一个出现次数为1字符就是结果
char firstUniqChar(string s) {
vector m(26, 0);
for(auto a:s) m[a-‘a‘]++;
for(auto a:s){
if(m[a-‘a‘]==1) return a;
}
return ‘ ‘;
}
};

50、在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

50、数组的逆序对

class Solution {
public:
//想得到就能做出来，归并排序模板题
int ans=0;
int reversePairs(vector& nums) {
division(nums, 0, nums.size()-1);
return ans;
}
void division(vector& nums, int left, int right){
if(left>=right) return;
int mid=left+(right-left)/2;
division(nums, left, mid);
division(nums, mid+1, right);
merge(nums, left, mid, mid+1, right);
}
void merge(vector &nums, int left1, int right1, int left2, int right2){
int leftSave=left1;
vector temp;
while(left1<=right1&&left2<=right2){
if(nums[left1]>nums[left2]){
temp.push_back(nums[left1++]);
ans+=right2-left2+1;
}
else temp.push_back(nums[left2++]);
}
while(left1<=right1) temp.push_back(nums[left1++]);
while(left2<=right2){
temp.push_back(nums[left2++]);
ans+=((right1-left1+1)*(right2-left2+1));
}
for(int i=leftSave,tempIndex=0;i<=right2;++i,++tempIndex)
nums[i]=temp[tempIndex];
}
};

51、输入两个链表，找出它们的第一个公共节点。

51、两个链表的第一个公共结点

class Solution {
public:
//看了题解，真的泪目，最浪漫的一道算法题了
//假如我们错过了第一次相遇，来到了终点
//那么你变成了我，我变成了你
//你走我走过的路，我走你走过的路
//我们终将再次相遇
//PS：没有第一次相遇（就是没有交点的），那就是换路走以后也碰不上的QAQ
//走到nullptr时，这一步要当作一步，不能马上接回另一个链表的头
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *currA=headA, *currB=headB;
while(currA!=currB){
if(!currA) currA=headB;
else currA=currA->next;
if(!currB) currB=headA;
else currB=currB->next;
}
return currA;
}
};

52、统计一个数字在排序数组中出现的次数。

52、在排序数组中查找数字 Ⅰ

class Solution {
public:
//三次二分
//第一次找出某个target
//第二次找target左边的边界
//第三次找target右边的边界
//注意判断条件
int search(vector& nums, int target) {
int left=0, right=nums.size();
int mid=0;
while(left<right){
mid=left+((right-left)>>1);
if(nums[mid]==target) break;
else if(nums[mid]>target) right=mid;
else left=mid+1;
}

    //找左边界需要的判断条件
    int leftL=left, rightL=mid;
    //找右边界需要的判断条件
    int leftR=mid+1, rightR=right;


    while(leftL<rightL){
        int mid=leftL+((rightL-leftL)>>1);
        //注意
        if(nums[mid]>=target) rightL=mid;
        else if(nums[mid]<target)leftL=mid+1;
    }
    
    while(leftR<rightR){
        int mid=leftR+((rightR-leftR)>>1);
        //注意
        if(nums[mid]>target) rightR=mid;
        else if(nums[mid]<=target) leftR=mid+1;
    }
    return rightR-leftL;
}

};

53、一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

53、0~n-1中缺失的数字

①
class Solution {
public:
//二分
int missingNumber(vector& nums) {
int left=0, right=nums.size();
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]>mid) right=mid;
else left=mid+1;
}
return left;
}
};
②
class Solution {
public:
//位运算，异或
int missingNumber(vector& nums) {
int res;
for(int i=0;i<nums.size();++i){
if(i^nums[i]){
res=i;
break;
}
}
return res;
}
};

54、给定一棵二叉搜索树，请找出其中第k大的节点。

54、二叉搜索树的第k大节点

class Solution {
public:
//类中序遍历
int kthLargest(TreeNode* root, int k) {
stack<TreeNode> s;
int res;
while(!s.empty()||root){
while(root){
s.push(root);
root=root->right;
}
TreeNode curr=s.top();
s.pop();
if(--k==0){
res=curr->val;
break;
}
root=curr->left;
}
return res;
}
};

55、输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

55、二叉树的深度

①
class Solution {
public:
//递归方式
int maxDepth(TreeNode* root) {
if(!root) return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return max(left, right)+1;
}
};
②
class Solution {
public:
//非递归方式，层序遍历
int maxDepth(TreeNode* root) {
if(!root) return 0;
int depth=0;
queue<TreeNode> q;
q.push(root);
while(!q.empty()){
int sz=q.size();
while(sz--){
TreeNode curr=q.front();
q.pop();
if(curr->left) q.push(curr->left);
if(curr->right) q.push(curr->right);
}
++depth;
}
return depth;
}
};

56、输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

56、平衡二叉树

class Solution {
public:
//递归实现
bool isBalanced(TreeNode* root) {
return depth(root)!=-1;
}
int depth(TreeNode *root){
if(!root) return 0;
int left=depth(root->left);
if(left-1) return -1;
int right=depth(root->right);
if(right-1) return -1;
if(abs(left-right)>1) return -1;
return max(left, right)+1;
}
};

57、一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

57、数组中数字出现的次数

class Solution {
public:
//位运算找规律
//第一步，全部数字异或得到两个不相同的数的异或结果
//第二步，找到异或结果某一位为1的那一位
//因为异或结果为1，说明异或的两个数字的那一位是不相同的
//那么我们就可以根据这一位进行分组，一组的元素个数必定是奇数
//第三步，将两组分别进行异或得到两个数字，就是结果数组
vector singleNumbers(vector& nums) {
//第一步
int all=0;
for(auto num:nums) all^=num;
//第二步
int find=1;
while((all&find)==0){
find<<=1;
}
//第三步
int ans1=0, ans2=0;
for(auto num:nums){
if(find&num) ans1^=num;
else ans2^=num;
}
return {ans1,ans2};
}
};

58、在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

58、数组中数字出现的次数 Ⅱ

①哈希表②排序
③
class Solution {
public:
//位运算
//一个int有32位，把nums中所有数字都变成二进制，加到对应的rec
//出现三次的数字，该位余3一定等于0
//不等于0，就用那一位构造出只出现一次的数字的一部分
int singleNumber(vector& nums) {
vector rec(32, 0);
for(auto num:nums){
for(int i=0;i<32;++i){
rec[i]+=(num&1);
num>>=1;
}
}
int ans=0;
for(int i=0;i<32;++i){
if(rec[i]%3) ans+=pow(2,i);
}
return ans;
}
};

59、输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

59、和为s的两个数字

①
class Solution {
public:
//遍历数组，二分查找
vector twoSum(vector& nums, int target) {
vector ans;
for(int i=0;i<nums.size();++i){
int newTarget=target-nums[i];
if(newTarget<nums[i]) break;
int left=i+1, right=nums.size();
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]newTarget) return vector{nums[i], nums[mid]};
else if(nums[mid]>newTarget) right=mid;
else left=mid+1;
}
}
return ans;
}
};
②
class Solution {
public:
//双指针
vector twoSum(vector& nums, int target) {
vector ans;
int left=0, right=nums.size()-1;
while(left<right){
int sum=nums[left]+nums[right];
if(sumtarget) {
return vector{nums[left],nums[right]};
}
else if(sum>target) --right;
else ++left;
}
return ans;
}
};

60、输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

60、和为s的连续正整数序列

class Solution {
public:
//双指针
//要想到连续数字的和的计算公式
//那么双指针求出来的和，那就有三种情况
//第一，等于，这就是一个结果，l++，r++
//第二，大于，说明以l为起点的这一段都不对，l++
//第三，小于，说明以l为起点的还有可能找到适合的，r++
vector<vector> findContinuousSequence(int target) {
vector<vector> ans;
vector ansP;
int l=1,r=2;
while(l<r){
int sum=(l+r)*(r-l+1)/2;
if(sum==target){
for(int i=l;i<=r;++i) ansP.push_back(i);
ans.push_back(ansP);
ansP.clear();
++l;
++r;
}else if(sum>target){
++l;
}else{
++r;
}
}
return ans;
}
};

61、输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

61、翻转单词顺序

class Solution {
public:
//类双指针
//另开str
//遇到空格就跳过，这一步可以去除句子前后和中间多余的空格
//遇到不是空格，开始双指针。right记录单词结尾，left去找单词开头
string reverseWords(string s) {
string ans;
int left=s.size()-1;
while(left>=0){
if(s[left]!=‘ ‘){
int right=left;
while(left>=0&&s[left]!=‘ ‘) --left;
//找到单词边界后有两种情况
//第一、左边到尽头了，并且左边不是空格
//第二、这里又包括两种，左边到尽头并且是空格，这样就和普通情况一样
if(left==0&&s[left]!=‘ ‘) ans+=s.substr(left, right-left+1);
else ans+=s.substr(left+1, right-left);
ans+=" ";
}
--left;
}
//弹出最后的多余空格
ans.pop_back();
return ans;
}
};

62、字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

62、左旋转字符串

①
class Solution {
public:
//反转3次
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin()+n);
reverse(s.begin()+n, s.end());
reverse(s.begin(), s.end());
return s;
}
};
②
class Solution {
public:
//一步到位
string reverseLeftWords(string s, int n) {
return (s+s).substr(n, s.size());
}
};

63、给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

63、滑动窗口的最大值

class Solution {
public:
//和下一题有一点异曲同工之妙，deque实现一个单调队列，维持一段区间的最大值
//当时看题解看到用deque和定义自己的方法，就秒懂写出来了
deque q;
vector maxSlidingWindow(vector& nums, int k) {
if(nums.size()0) return {};
vector ans;
init(nums, k);
ans.push_back(getMax());
for(int i=k;i<nums.size();++i){
pop(nums[i-k]);
push(nums[i]);
ans.push_back(getMax());
}
return ans;
}
void init(vector& nums, int k){
for(int i=0;i<k;++i){
push(nums[i]);
}
}
void push(int num){
while(!q.empty()&&num>q.back()) q.pop_back();
q.push_back(num);
}
void pop(int num){
if(numq.front()) q.pop_front();
}
int getMax(){
return q.front();
}
};
class Solution {
public:
//和下一题有一点异曲同工之妙，deque实现一个单调队列，维持一段区间的最大值
//当时看题解看到用deque和定义自己的方法，就秒懂写出来了
vector maxSlidingWindow(vector& nums, int k) {
if(nums.size()0) return {};
deque q;
vector ans;
for(int i=0;i<nums.size();++i){
if(i>=k&&nums[i-k]q.front()) q.pop_front();
while(!q.empty()&&nums[i]>q.back()) q.pop_back();
q.push_back(nums[i]);
if(i>=k-1) ans.push_back(q.front());
}
return ans;
}
};

64、请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1

64、队列的最大值

class MaxQueue {
//主要要找到这道题的特性，当一个新元素入队时，前面比它小的元素不再有影响
public:
MaxQueue() {}

int max_value() {
    if(q.empty()) return -1;
    return dq.front();
}

void push_back(int value) {
    q.push(value);
    while(!dq.empty()&&dq.back()<value) dq.pop_back();
    dq.push_back(value);
}

int pop_front() {
    if(q.empty()) return -1;
    if(dq.front()==q.front()) dq.pop_front();
    int res=q.front();
    q.pop();
    return res;
}

private:
queue q;
deque dq;
};

65、从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

65、扑克牌中的顺子

class Solution {
public:
//不能有重复元素，0不算，用set判断
//顺子，最大减最小不超过4
bool isStraight(vector& nums) {
int minNum=INT_MAX,maxNum=INT_MIN;
set rec;
for(auto num:nums){
if(num==0) continue;
if(rec.count(num)) return false;
rec.insert(num);
minNum=min(minNum, num);
maxNum=max(maxNum, num);
}
return maxNum-minNum<5;
}
};

66、0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

66、圆圈中最后剩下的数字

①
class Solution {
public:
//数学解法
//i的含义是剩余个数
//pos的含义是在i下的下标
int lastRemaining(int n, int m) {
int pos=0;
for(int i=2;i<=n;++i) pos=(pos+m)%i;
return pos;
}
};

②
class Solution {
public:
//链表模拟，会超时
class ListNode{
public:
int val;
ListNode *next;
ListNode(int x):val(x),next(nullptr){}
};
int lastRemaining(int n, int m) {
ListNode *head=new ListNode(0);
ListNode *curr=head;
for(int i=1;i<n;++i){
curr->next=new ListNode(i);
curr=curr->next;
}
curr->next=head;

    while(curr->next!=curr){
        for(int i=0;i<m-1;++i){
            curr=curr->next;
        } 
        ListNode *del=curr->next;
        curr->next=del->next;
        delete(del);
    }
    return curr->val;
}

};

67、假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

67、股票的最大利润

class Solution {
public:
//当天的最大利润是当天的股票价格-之前的最低股票价格
//所以不断更新最低股票价格，再用来获取截至当天的最大利润
int maxProfit(vector& prices) {
int profit=0, minM=INT_MAX;
for(int i=0;i<prices.size();++i){
minM=min(minM, prices[i]);
profit=max(profit, prices[i]-minM);
}
return profit;
}
};

68、求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

68、求1+2+…+n
class Solution {
public:
//递归解法
int sumNums(int n) {
if(n==0) return 0;
return sumNums(n-1)+n;
}
};

69、写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

69、不用加减乘除做加法
class Solution {
public:
//计组中加法器学过
//考虑无进位加法怎么实现：异或
//考虑什么情况下需要进位，同位都为1：与运算，再左移
int add(int a, int b) {
while(b){
int carry=(unsigned)(a&b)<<1;
a^=b;
b=carry;
}
return a;
}
};

70、给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

70、构造乘积数组
class Solution {
public:
//用left和righ分别存当缺i时i左边的乘积和i右边的乘积
vector constructArr(vector& a) {
vector left(a.size(),1), right(a.size(), 1);
for(int i=1;i<a.size();++i) left[i]=left[i-1]a[i-1];
for(int i=a.size()-2;i>=0;--i) right[i]=right[i+1]a[i+1];
vector ans;
for(int i=0;i<a.size();++i) ans.push_back(left[i]right[i]);
return ans;
}
};

71、写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。

71、把字符串转换成整数
class Solution {
public:
//模拟+边界条件
int strToInt(string str) {
int i=0, negative=1;
while(i<str.size()&&str[i]‘ ‘) ++i;
if(istr.size()) return 0;
long long res=0;
if(str[i]‘-‘) negative=-1;
if(str[i]‘-‘||str[i]==‘+‘) ++i;
for(;i<str.size();++i){
if(str[i]<‘0‘||str[i]>‘9‘) break;
res=res10+negative(str[i]-‘0‘);
if(res<INT_MIN) return INT_MIN;
if(res>INT_MAX) return INT_MAX;
}
return res;
}
};

72、给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

72、二叉搜索树的最近公共祖先
①
class Solution {
public:
//迭代
//注意利用二叉搜索树的特性，左小右大
//最近的公共结点必定满足root<pORq，root>qORp
//而再上一点的公共结点一定不满足
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root){
if(root->valval&&root->valval) root=root->right;
else if(root->val>p->val&&root->val>q->val) root=root->left;
else break;
}
return root;
}
};

②
class Solution {
public:
//递归
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root->valval&&root->valval)
return lowestCommonAncestor(root->right,p,q);
else if(root->val>p->val&&root->val>q->val)
return lowestCommonAncestor(root->left,p,q);
else return root;
}
};

73、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

73、二叉树的最近公共祖先
class Solution {
public:
//递归
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return nullptr;
if(root==p||root=q) return root;
TreeNode *left=lowestCommonAncestor(root->left, p, q);
TreeNode *right=lowestCommonAncestor(root->right, p, q);
if(left&&right) return root;
return left?left:right;
}
};

74、在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

74、二维数组中的查找
class Solution {
public:
bool findNumberIn2DArray(vector<vector>& matrix, int target) {
if(matrix.size()0||matrix[0].size()0) return false;
int top=0, right=matrix[0].size()-1;
while(top<matrix.size()&&right>=0){
if(matrix[top][right]==target) return true;
else if(matrix[top][right]>target) --right;
else if(matrix[top][right]<target) ++top;
}
return false;
}
};

75、把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

75、n个骰子的点数

class Solution {
public:
    //dp，一生之敌
    //dp[i][j]，i是骰子个数，j是点数和，dp[i][j]是i个骰子能得到某个点数和的出现次数
    //一个骰子只有1，2，3，4，5，6
    //所以在i个骰子的情况下，统计某个点数和的出现次数取决于i-1个骰子时的部分点数和
    vector<double> dicesProbability(int n) {
        int dp[12][70]{0};
        for(int i=1;i<=6;++i) dp[1][i]=1;


        for(int i=2;i<=n;++i){
            for(int j=i;j<=6*i;++j){
                for(int k=1;k<=6;++k){
                    if(j<=k) break;
                    dp[i][j]+=dp[i-1][j-k];
                }
            }
        }


        vector<double> ans;
        double all=pow(6,n);
        for(int i=n;i<=6*n;++i) ans.push_back(dp[n][i]/all);
        return ans;
    }
};

《剑指Offer》学习记录

原文：https://www.cnblogs.com/wasi-991017/p/14065763.html