在个人博客中同步更新
第 1 天 栈与队列（简单）
剑指 Offer 09. 用两个栈实现队列
点击查看代码
class CQueue {
public:
CQueue() {
}
stack<int>s1,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;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
剑指 Offer 30. 包含min函数的栈
点击查看代码
构造一个辅助栈，使辅助栈顶元素始终为当前栈内元素的最小值
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
stack<int>st;
stack<int>m;
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();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/
第 2 天 链表（简单）
剑指 Offer 06. 从尾到头打印链表
存入数组中然后反转一下
点击查看代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int>v;
while(head)
{
v.push_back(head->val);
head=head->next;
}
reverse(v.begin(),v.end());
return v;
}
};
剑指 Offer 24. 反转链表
让当前节点的下一个节点指向上一个节点，使用一个临时的指针来实现
点击查看代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
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<int>& nums) {
int l=nums.size();
int i=0;
while(i<l)
{
if(nums[i]==i)
{
i++;
continue;
}
if(nums[nums[i]]==nums[i])
return nums[i];
swap(nums[i],nums[nums[i]]);
}
return -1;
}
};
剑指 Offer 53 - I. 在排序数组中查找数字 I
lower_bound和upper_bound的使用
点击查看代码
class Solution {
public:
int search(vector<int>& 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<int>& nums) {
int l=nums.size();
for(int i=0;i<l;i++)
{
if(nums[i]!=i)
return i;
}
return l;
}
};
二分
点击查看代码
class Solution {
public:
int missingNumber(vector<int>& 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))\)
点击查看代码
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& 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)\)
[font color="red"]注意数组为空的情况[/font]
点击查看代码
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
int n=matrix.size();
if(!n) return false;
int m=matrix[0].size();
int i=0,j=m-1;
while(i<n&&j>=0)
{
if(matrix[i][j]<target)
i++;
else if(matrix[i][j]>target)
j--;
else
return true;
}
return false;
}
};
剑指 Offer 11. 旋转数组的最小数字
遍历
点击查看代码
class Solution {
public:
int minArray(vector<int>& numbers) {
int ans=numbers[0];
for(auto i:numbers)
ans=min(ans,i);
return ans;
}
};
二分
注意相等的情况，需要遍历
点击查看代码
class Solution {
public:
int minArray(vector<int>& numbers) {
int l=0,r=numbers.size()-1;
int ans=10000000;
while(l<r)
{
int mid=(l+r)/2;
if(numbers[mid]>numbers[r])
l=mid+1;
else if(numbers[mid]<numbers[r])
r=mid;
else
{
for(int i=l;i<=r;i++)
ans=min(ans,numbers[i]);
return ans;
}
}
return numbers[l];
}
};
剑指 Offer 50. 第一个只出现一次的字符
直接用map存就行，可以把字符去一下重优化时间
点击查看代码
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char,int>mp;
char ans=' ';
vector<char>v;
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. 从上到下打印二叉树
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
queue<TreeNode*>que;
que.push(root);
vector<int>ans;
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
在当前节点的下一层放入队列之前，把当前节点存下来
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root)
return {};
queue<TreeNode*>que;
que.push(root);
vector<vector<int> >ans;
while(!que.empty())
{
vector<int>tmp;
int sz=que.size();
for(int i=0;i<sz;i++)
{
TreeNode *now=que.front();
tmp.push_back(now->val);
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
和上一题一样，只不过在存入到最终结果之前需要判断一下当前在第几层，翻转一下
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root)
return {};
queue<TreeNode*>que;
que.push(root);
vector<vector<int> >ans;
while(!que.empty())
{
vector<int>tmp;
int sz=que.size();
for(int i=0;i<sz;i++)
{
TreeNode *now=que.front();
tmp.push_back(now->val);
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同时向下递归
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool 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
用栈辅助遍历来实现二叉树的镜像
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(!root)
return root;
stack<TreeNode*>st;
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
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
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. 对称的二叉树
对左子树和右子树同时向下遍历
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool 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. 青蛙跳台阶问题
\(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<int>& prices) {
int sz=prices.size();
if(!sz)
return 0;
int m=prices[0];
int ans=0;
for(int i=1;i<sz;i++)
{
m=min(prices[i],m);
ans=max(ans,prices[i]-m);
}
return ans;
}
};
第 9 天 动态规划（中等）
剑指 Offer 42. 连续子数组的最大和
点击查看代码
class Solution {
public:
int maxSubArray(vector<int>& 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. 礼物的最大价值
\(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<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
dp[0][0]=grid[0][0];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!i&&!j)
continue;
if(!i)
dp[i][j]=max(dp[i][j-1]+grid[i][j],dp[i][j]);
else if(!j)
dp[i][j]=max(dp[i-1][j]+grid[i][j],dp[i][j]);
else
dp[i][j]=max({dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j],dp[i][j]});
}
}
return dp[n-1][m-1];
}
};
第 10 天 动态规划（中等）
剑指 Offer 46. 把数字翻译成字符串
\(dp[i]\)表示在位置\(i\)有多少种方案，如果\(i\)和\(i-1\)位置能够在一起翻译成字母，则\(dp[i]=dp[i-1]+dp[i-2]\)，否则\(dp[i]=dp[i-1]\)
点击查看代码
class Solution {
public:
int dp[20];
int translateNum(int num) {
if(num<10)
return 1;
vector<int>v;
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<sz;i++)
{
if(v[i-1]*10+v[i]<26&&v[i-1]*10+v[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();
map<char,int>mp;
int ans=0;
int place=0;
for(int i=0;i<l;i++)
{
if(mp[s[i]])
place=max(place,mp[s[i]]);
ans=max(i-place+1,ans);
mp[s[i]]=i+1;
}
return ans;
}
};
第 11 天 双指针（简单）
剑指 Offer 18. 删除链表的节点
设置一个当前节点的前驱结点，如果当前节点为删除节点，停止查找，让前驱结点的下一个节点变成当前节点的下一个节点，即可实现删除
点击查看代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head->val==val)
return head->next;
ListNode *pre=head,*now=head->next;
while(now->val!=val&&now)
pre=now,now=now->next;
if(now)
pre->next=now->next;
return head;
}
};
剑指 Offer 22. 链表中倒数第k个节点
设置两个所指位置不同的指针，保证在前面的指针和在后面的指针相差\(k\)个节点，当在前面的指针指向链表末尾时，在后面的指针恰好指向倒数第\(k\)个节点
点击查看代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *slow=head,*fast=head;
for(int i=0;i<k;i++)
{
if(!fast)
return NULL;
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
};
第 12 天 双指针（简单）
剑指 Offer 25. 合并两个排序的链表
同时遍历两个链表，每次添加两个链表中较小的那个节点，知道有一个链表遍历结束
点击查看代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *head=new ListNode(0,NULL);
ListNode *tmp=head;
while(l1&&l2)
{
if(l1->val>l2->val)
{
tmp->next=l2;
l2=l2->next;
}
else
{
tmp->next=l1;
l1=l1->next;
}
tmp=tmp->next;
}
if(l2)
tmp->next=l2;
if(l1)
tmp->next=l1;
return head->next;
}
};
剑指 Offer 52. 两个链表的第一个公共节点
双指针，官方题解有证明
点击查看代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA||!headB)
return NULL;
ListNode *nodeA=headA,*nodeB=headB;
while(nodeA!=nodeB)
{
nodeA=nodeA?nodeA->next:headB;
nodeB=nodeB?nodeB->next:headA;
}
return nodeA;
}
};
第 13 天 双指针（简单）
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
两个指针分别指向数组的开头和结尾，如果左边的数为偶数，右边的数为奇数，交换两数的位置；如果左边为奇数，左指针右移；如果右边为偶数，右指针左移
点击查看代码
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int l=0,r=nums.size()-1;
while(l<r)
{
if(!(nums[l]%2)&&nums[r]%2)
swap(nums[l++],nums[r--]);
else if(nums[l]%2)
l++;
else if(!(nums[r]%2))
r--;
}
return nums;
}
};
剑指 Offer 57. 和为s的两个数字
哈希
点击查看代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int>mp;
for(auto i:nums)
{
if(mp[target-i])
return {i,target-i};
mp[i]++;
}
return {};
}
};
双指针
点击查看代码
class Solution {
public:
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++;
else if(nums[l]+nums[r]>target)
r--;
else return {nums[l],nums[r]};
}
return {};
}
};
剑指 Offer 58 - I. 翻转单词顺序
直接py
cpp的话用栈来做吧，挺麻烦的
点击查看代码
class Solution:
def reverseWords(self, s: str) -> str:
s=s.strip().split()
s.reverse()
return ' '.join(s)