LeetCode—剑指 Offer学习计划
2024-09-07 22:20:51
第 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;
}
};
最新文章
- video/audio在ios/android上播放兼容
- 关于SQL SERVER数据库学习总结
- Windows Server 2012 配置多用户远程桌面
- cereal:C++实现的开源序列化库
- 安装 Apache 出现 <OS 10013> 以一种访问权限不允许的方式做了一个访问套接字的尝试
- Ubuntu + CentOS7 搭建tftp Server
- linux设备驱动归纳总结（十三）：1.触摸屏与ADC时钟【转】
- HDU 2255 奔小康赚大钱
- hdu 1698 Just a Hook_线段树
- unity中的委托
- 在js中，window != top 的作用
- Java | 原来 try 还可以这样用啊？！
- MyEclipse提示
- Python/ selectors模块及队列
- adapter.notifydatasetchanged()没有效果
- Matlab:高阶常微分三种边界条件的特殊解法（中心差分法，高精度导数边界处理）
- :app:compileDebugJavaWithJavac
- Genymotion 模拟器上网出现 net::ERR_NAME_NOT_RESOLVED
- PHP 使用 MongoDB
- xhost + 的作用