在个人博客与博客园中同步更新
第 1 天 栈与队列（简单） 剑指 Offer 09. 用两个栈实现队列class CQueue {
public:
CQueue() {
}
stacks1,s2;
void appendTail(int value) {
s1.push(value);
}
int deleteHead() {
if(s2.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
if(s2.empty())
return -1;
int tmp=s2.top();
s2.pop();
return tmp;
}
};
剑指 Offer 30. 包含min函数的栈
构造一个辅助栈，使辅助栈顶元素始终为当前栈内元素的最小值
class MinStack {
public:
MinStack() {
}
stackst;
stackm;
void push(int x) {
st.push(x);
if(m.empty()||m.top()>=x)
m.push(x);
}
void pop() {
if(st.top()==m.top())
m.pop();
st.pop();
}
int top() {
return st.top();
}
int min() {
return m.top();
}
};
第 2 天 链表（简单）
剑指 Offer 06. 从尾到头打印链表
存入数组中然后反转一下
class Solution {
public:
vector reversePrint(ListNode* head) {
vectorv;
while(head)
{
v.push_back(head->val);
head=head->next;
}
reverse(v.begin(),v.end());
return v;
}
};
剑指 Offer 24. 反转链表
让当前节点的下一个节点指向上一个节点，使用一个临时的指针来实现
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *cnt=head,*ans=NULL;
while(cnt)
{
ListNode *tmp=cnt->next;
cnt->next=ans;
ans=cnt;
cnt=tmp;
}
return ans;
}
};
剑指 Offer 35. 复杂链表的复制
待补
第三天 字符串（简单） 剑指 Offer 05. 替换空格直接遍历
class Solution {
public:
string replaceSpace(string s) {
string ans;
for(auto i:s)
{
if(i==' ')
ans+="%20";
else
ans+=i;
}
return ans;
}
};
剑指 Offer 58 - II. 左旋转字符串
class Solution {
public:
string reverseLeftWords(string s, int n) {
string ans="";
ans+=s.substr(n,s.size());
ans+=s.substr(0,n);
return ans;
}
};
第 4 天 查找算法（简单）
剑指 Offer 03. 数组中重复的数字
构建元素的索引和值为一对一的关系，如果当前索引已经有值并且和当前值相同，则出现多次
class Solution {
public:
int findRepeatNumber(vector& nums) {
int l=nums.size();
int i=0;
while(i
剑指 Offer 53 - I. 在排序数组中查找数字 I
lower_bound和upper_bound的使用
class Solution {
public:
int search(vector& nums, int target) {
int l_place=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
int r_place=upper_bound(nums.begin(),nums.end(),target)-nums.begin();
return r_place-l_place;
}
};
剑指 Offer 53 - II. 0～n-1中缺失的数字
遍历
class Solution {
public:
int missingNumber(vector& nums) {
int l=nums.size();
for(int i=0;i
二分
class Solution {
public:
int missingNumber(vector& nums) {
int l=0,r=nums.size()-1;
while(l<=r)
{
int mid=(l+r)/2;
if(nums[mid]>mid)
r=mid-1;
else
l=mid+1;
}
return l;
}
};
第 5 天 查找算法（中等）
剑指 Offer 04. 二维数组中的查找
二分
对每一行进行二分，时间复读
O
(
n
log
(
m
)
)
O(n log(m))
O(nlog(m))
class Solution {
public:
bool findNumberIn2DArray(vector>& matrix, int target) {
for(auto i:matrix)
{
int place=lower_bound(i.begin(),i.end(),target)-i.begin();
if(place!=i.size()&&i[place]==target)
return true;
}
return false;
}
};
线性查找
从右上角开始，如果当前元素比target大，往左走；如果比target小，向下走。时间复杂度为
O
(
n
+
m
)
O(n+m)
O(n+m)
[font color=“red”]注意数组为空的情况[/font]
class Solution {
public:
bool findNumberIn2DArray(vector>& matrix, int target) {
int n=matrix.size();
if(!n) return false;
int m=matrix[0].size();
int i=0,j=m-1;
while(i=0)
{
if(matrix[i][j]target)
j--;
else
return true;
}
return false;
}
};
剑指 Offer 11. 旋转数组的最小数字
遍历
class Solution {
public:
int minArray(vector& numbers) {
int ans=numbers[0];
for(auto i:numbers)
ans=min(ans,i);
return ans;
}
};
二分
注意相等的情况，需要遍历
class Solution {
public:
int minArray(vector& numbers) {
int l=0,r=numbers.size()-1;
int ans=10000000;
while(lnumbers[r])
l=mid+1;
else if(numbers[mid]
剑指 Offer 50. 第一个只出现一次的字符
直接用map存就行，可以把字符去一下重优化时间
class Solution {
public:
char firstUniqChar(string s) {
unordered_mapmp;
char ans=' ';
vectorv;
for(auto i:s)
{
if(!mp[i])
v.push_back(i);
mp[i]++;
}
for(auto i:v)
{
if(mp[i]==1)
return i;
}
return ans;
}
};
第 6 天 搜索与回溯算法（简单）
剑指 Offer 32 - I. 从上到下打印二叉树
class Solution {
public:
vector levelOrder(TreeNode* root) {
queueque;
que.push(root);
vectorans;
if(!root)
return ans;
while(!que.empty())
{
TreeNode *tmp=que.front();
que.pop();
if(tmp->left)
que.push(tmp->left);
if(tmp->right)
que.push(tmp->right);
ans.push_back(tmp->val);
}
return ans;
}
};
剑指 Offer 32 - II. 从上到下打印二叉树 II
在当前节点的下一层放入队列之前，把当前节点存下来
class Solution {
public:
vector> levelOrder(TreeNode* root) {
if(!root)
return {};
queueque;
que.push(root);
vector >ans;
while(!que.empty())
{
vectortmp;
int sz=que.size();
for(int i=0;ival);
que.pop();
if(now->left)
que.push(now->left);
if(now->right)
que.push(now->right);
}
ans.push_back(tmp);
}
return ans;
}
};
剑指 Offer 32 - III. 从上到下打印二叉树 III
和上一题一样，只不过在存入到最终结果之前需要判断一下当前在第几层，翻转一下
class Solution {
public:
vector> levelOrder(TreeNode* root) {
if(!root)
return {};
queueque;
que.push(root);
vector >ans;
while(!que.empty())
{
vectortmp;
int sz=que.size();
for(int i=0;ival);
que.pop();
if(now->left)
que.push(now->left);
if(now->right)
que.push(now->right);
}
if(ans.size()%2)
reverse(tmp.begin(),tmp.end());
ans.push_back(tmp);
}
return ans;
}
};
第 7 天 搜索与回溯算法（简单）
剑指 Offer 26. 树的子结构
先从A开始往下遍历，如果出现了与B的根节点相等的节点，开始A和B同时向下递归
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(!A||!B)
return false;
if(dfs(A,B))
return true;
return isSubStructure(A->left,B)||isSubStructure(A->right,B);
}
bool dfs(TreeNode *A,TreeNode *B)
{
if(!B)
return true;
if(!A)
return false;
if(A->val!=B->val)
return false;
return dfs(A->left,B->left)&&dfs(A->right,B->right);
}
};
剑指 Offer 27. 二叉树的镜像
BFS
用栈辅助遍历来实现二叉树的镜像
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(!root)
return root;
stackst;
st.push(root);
while(!st.empty())
{
TreeNode *node=st.top();
st.pop();
if(node->left)
st.push(node->left);
if(node->right)
st.push(node->right);
TreeNode *tmp=node->left;
node->left=node->right;
node->right=tmp;
}
return root;
}
};
DFS
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(!root)
return root;
TreeNode *node=root->left;
root->left=mirrorTree(root->right);
root->right=mirrorTree(node);
return root;
}
};
剑指 Offer 28. 对称的二叉树
对左子树和右子树同时向下遍历
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
return dfs(root->left,root->right);
}
bool dfs(TreeNode *A,TreeNode *B)
{
if(!A&&!B)
return true;
if((!A||!B)||A->val!=B->val)
return false;
return dfs(A->left,B->right)&&dfs(A->right,B->left);
}
};
第 8 天 动态规划（简单）
剑指 Offer 10- I. 斐波那契数列
别用递归写就行了
class Solution {
public:
int a[3];
const int mod=1e9+7;
int fib(int n) {
if(n<2)
return n;
a[0]=0;a[1]=1;
for(int i=2;i<=n;i++)
{
a[2]=(a[1]%mod+a[0]%mod)%mod;
a[0]=a[1];a[1]=a[2];
}
return a[2];
}
};
剑指 Offer 10- II. 青蛙跳台阶问题
d
p
[
i
]
=
d
p
[
i
−
1
]
+
d
p
[
i
−
2
]
dp[i]=dp[i-1]+dp[i-2]
dp[i]=dp[i−1]+dp[i−2]
class Solution {
public:
int dp[101];
const int mod=1e9+7;
int numWays(int n) {
dp[0]=1;
dp[1]=1;
dp[2]=2;
for(int i=2;i<=n;i++)
dp[i]=(dp[i-1]+dp[i-2])%mod;
return dp[n];
}
};
剑指 Offer 63. 股票的最大利润
不断更新当前元素与当前最小值的差值就行了
class Solution {
public:
int maxProfit(vector& prices) {
int sz=prices.size();
if(!sz)
return 0;
int m=prices[0];
int ans=0;
for(int i=1;i
第 9 天 动态规划（中等）
剑指 Offer 42. 连续子数组的最大和
class Solution {
public:
int maxSubArray(vector& nums) {
int ans=nums[0];
int tmp=0;
for(auto i:nums)
{
tmp=max(tmp+i,i);
ans=max(ans,tmp);
}
return ans;
}
};
剑指 Offer 47. 礼物的最大价值
d
p
[
i
]
[
j
]
=
max
{
d
p
[
i
−
1
]
[
j
]
+
a
[
i
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
+
a
[
i
]
[
j
]
,
d
p
[
i
]
[
j
]
}
dp[i][j]=max{dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j],dp[i][j] }
dp[i][j]=max{dp[i−1][j]+a[i][j],dp[i][j−1]+a[i][j],dp[i][j]}
class Solution {
public:
int dp[202][202];
int maxValue(vector>& grid) {
int n=grid.size(),m=grid[0].size();
dp[0][0]=grid[0][0];
for(int i=0;i
第 10 天 动态规划（中等）
剑指 Offer 46. 把数字翻译成字符串
d
p
[
i
]
dp[i]
dp[i]表示在位置
i
i
i有多少种方案，如果
i
i
i和
i
−
1
i-1
i−1位置能够在一起翻译成字母，则
d
p
[
i
]
=
d
p
[
i
−
1
]
+
d
p
[
i
−
2
]
dp[i]=dp[i-1]+dp[i-2]
dp[i]=dp[i−1]+dp[i−2]，否则
d
p
[
i
]
=
d
p
[
i
−
1
]
dp[i]=dp[i-1]
dp[i]=dp[i−1]
class Solution {
public:
int dp[20];
int translateNum(int num) {
if(num<10)
return 1;
vectorv;
while(num)
{
v.push_back(num%10);
num/=10;
}
reverse(v.begin(),v.end());
int sz=v.size();
dp[0]=1;
if(v[0]*10+v[1]<26)
dp[1]=2;
else
dp[1]=1;
for(int i=2;i=10)
dp[i]=dp[i-1]+dp[i-2];
else
dp[i]=dp[i-1];
}
return dp[sz-1];
}
};
剑指 Offer 48. 最长不含重复字符的子字符串
向后遍历，保证遍历过程中子字符串包含的字符只出现了一次。当出现第二次时，让子字符串开始的位置变成该字符出现第二次的位置。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int l=s.length();
mapmp;
int ans=0;
int place=0;
for(int i=0;i 
