目录
剑指 Offer 32 - III. 从上到下打印二叉树 III
剑指 Offer 30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
class MinStack {
public:
/** initialize your data structure here. */
stack<int> sk1,sk2;
MinStack() {
sk2.push(INT_MAX);
}
void push(int x) {
sk1.push(x);
if(x<=sk2.top()) sk2.push(x);
}
void pop() {
int t=sk1.top();
sk1.pop();
if(t==sk2.top()) sk2.pop();
}
int top() {
return sk1.top();
}
int min() {
return sk2.top();
}
};
剑指 Offer 31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int i=0,j=0;
stack<int> sk;
for(auto i:pushed)
{
sk.push(i);
while(!sk.empty()&&sk.top()==popped[j])
{
sk.pop();
j++;
}
}
return j==popped.size();
}
};面试题32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<int> vec;
if(root==nullptr) return {};
q.push(root);
while(!q.empty())
{
vec.push_back(q.front()->val);
root=q.front();
q.pop();
if(root->left!=nullptr) q.push(root->left);
if(root->right!=nullptr) q.push(root->right);
}
return vec;
}
};-
二叉树的层序遍历
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<int> v;
vector<vector<int>> vec;
queue<TreeNode*> q;
stack<int> sk;
int level=1;
if(root==nullptr) return {};
q.push(root);
while(!q.empty())
{
int size=q.size();
while(size--)
{
root=q.front();
if(level&1)
v.push_back(root->val);
else
sk.push(root->val);
q.pop();
if(root->left!=nullptr) q.push(root->left);
if(root->right!=nullptr) q.push(root->right);
}
if(!(level&1))
{
while(!sk.empty())
{
v.push_back(sk.top());
sk.pop();
}
}
vec.push_back(v);
v.clear();
level++;
}
return vec;
}
};-
用栈模拟倒序插入
剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
return recur(0, postorder.size()-1,postorder);
}
bool recur(int left,int right,vector<int>& postorder)
{
if(left>=right) return true;
int index=0; //第一次大于根节点的下标
while(postorder[index]<postorder[right])
{
index++;
}
int t=index;
while(t<right)
{
if(postorder[t]<postorder[right]) return false;
t++;
}
return recur(left,index-1,postorder)&&recur(index, right-1, postorder);
}
};剑指 Offer 34. 二叉树中和为某一值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
class Solution {
public:
vector<int> v;
vector<vector<int>>vec;
vector<vector<int>> pathSum(TreeNode* root, int target) {
dfs(root, target);
return vec;
}
void dfs(TreeNode* root, int target)
{
if(root==nullptr) return;
v.push_back(root->val);
target-=root->val;
if(root->left==nullptr&&root->right==nullptr&&target==0)
{
vec.push_back(v);
v.pop_back();
return;
}
if(root->left!=nullptr) dfs(root->left, target);
if(root->right!=nullptr) dfs(root->right, target);
v.pop_back();
}
};剑指 Offer 35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
class Solution {
public:
Node* copyRandomList(Node* head) {
Node* t=head;
unordered_map<Node*,Node*> um;
while(t!=nullptr)
{
Node *p=new Node(t->val);
um[t]=p;
t=t->next;
}
t=head;
while(t!=nullptr)
{
um[t]->random=um[t->random];
um[t]->next=um[t->next];
t=t->next;
}
return um[head];
}
};-
存放旧节点到新节点的映射
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
class Solution {
public:
Node* treeToDoublyList(Node* root) {
vector<Node*> vec;
if(root==nullptr) return nullptr;
inOrder(root,vec);
vec[0]->left=vec[vec.size()-1];
vec[vec.size()-1]->right=vec[0];
for(int i=1;i<vec.size();i++)
{
vec[i-1]->right=vec[i];
vec[i]->left=vec[i-1];
}
return vec[0];
}
void inOrder(Node* root,vector<Node*>& vec)
{
if(root==nullptr) return;
inOrder(root->left, vec);
vec.push_back(root);
inOrder(root->right, vec);
}
};-
中序遍历+存节点
剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if ( root == nullptr ) return "";
ostringstream output;
queue<TreeNode*> que;
que.push(root);
while ( !que.empty() ) {
TreeNode* node = que.front();
que.pop();
if ( node == nullptr ) output << "# ";
else {
output << node->val << ' ';
que.push(node->left);
que.push(node->right);
}
}
return output.str();
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if ( data.empty() ) return nullptr;
vector<TreeNode*> nodes;
string val;
istringstream input(data);
while ( input >> val ) {
if ( val == "#" ) nodes.push_back(nullptr);
else nodes.push_back(new TreeNode(stoi(val)));
};
int pos = 1;
for ( int i = 0; i < nodes.size(); ++i ) {
if ( nodes[i] == nullptr ) continue;
nodes[i]->left = nodes[pos++];
nodes[i]->right = nodes[pos++];
}
return nodes[0];
}
};剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
class Solution {
public:
vector<bool> visited;
vector<string> vec;
string t;
vector<string> permutation(string s) {
sort(s.begin(),s.end());
visited=vector<bool>(s.size());
backtracking(s, 0);
return vec;
}
void backtracking(string s,int n)
{
if(n==s.size())
{
vec.push_back(t);
return;
}
for(int i=0;i<s.size();i++)
{
if(visited[i]==false)
{
if(i>0&&s[i]==s[i-1]&&visited[i-1]==true) continue; //去重
t.push_back(s[i]);
visited[i]=true;
backtracking(s, n+1);
t.pop_back();
visited[i]=false;
}
}
}
};-
回溯+去重
剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n=0;
int target=nums[0];
for(int i=1;i<nums.size();i++)
{
if(nums[i]==target) n++;
else n--;
if(n<0)
{
target=nums[i];
n=0;
}
}
return target;
}
};-
摩尔投票法
剑指 Offer 40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
vector<int> vec;
for(auto &i:arr)
{
pq.push(i);
}
while(k--)
{
vec.push_back(pq.top());
pq.pop();
}
return vec;
}
};-
小根堆
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
priority_queue<int, vector<int>, less<int>> pq;
vector<int> vec;
if(k==0) return{};
for(int i=0;i<k;i++)
{
pq.push(arr[i]);
}
for(int j=k;j<arr.size();j++)
{
if(arr[j]<pq.top())
{
pq.pop();
pq.push(arr[j]);
}
}
while(k--)
{
vec.push_back(pq.top());
pq.pop();
}
return vec;
}
};-
大根堆
-
先把k个数放入大根堆中，从k+1个数开始遍历，如果当前数比堆顶数小，堆顶弹出，当前数入堆
-
遍历完成后，堆中的元素即为答案
剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
class MedianFinder {
public:
/** initialize your data structure here. */
int count=0;
priority_queue<int, vector<int>, less<int>> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
MedianFinder() {
}
void addNum(int num) {
count++;
if(count==1) //如果该数字为第一个元素
{
maxHeap.push(num);
}
else
{
if(num>maxHeap.top()) minHeap.push(num);
else maxHeap.push(num);
}
int m=maxHeap.size(),n=minHeap.size();
if(m-n>1) //使堆平衡
{
minHeap.push(maxHeap.top());
maxHeap.pop();
}
if(n-m>1)
{
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if(count&1) return maxHeap.size()>minHeap.size()?maxHeap.top()*1.0:minHeap.top()*1.0;
return (maxHeap.top()+minHeap.top())/2.0;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size());
int sum=0;
int ans=INT_MIN;
for(int i=0;i<nums.size();i++)
{
if(sum>=0) sum+=nums[i];
else sum=nums[i];
ans=max(ans,sum);
}
return ans;
}
};剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> vec;
for(auto &i:nums)
{
vec.push_back(to_string(i));
}
sort(vec.begin(),vec.end(),[](string&a,string&b){return a+b<b+a;});
string s;
for(int i=0;i<vec.size();i++)
{
s+=vec[i];
}
return s;
}
};剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
class Solution {
public:
int translateNum(int num) {
return f(num);
}
int f(int num)
{
if(num<10) return 1;
if(num%100>=10&&num%100<=25) return f(num/100)+f(num/10); //余100是判断后两位数是否在范围内
return f(num/10);
}
};剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
vector<vector<int>> dp(grid.size(),vector<int>(grid[0].size()));
dp[0][0]=grid[0][0];
for(int i=1;i<grid.size();i++)
dp[i][0]=grid[i][0]+dp[i-1][0];
for(int i=1;i<grid[0].size();i++)
dp[0][i]=grid[0][i]+dp[0][i-1];
for(int i=1;i<grid.size();i++)
{
for(int j=1;j<grid[0].size();j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[grid.size()-1][grid[0].size()-1];
}
};class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
for(int i=1;i<grid.size();i++)
grid[i][0]+=grid[i-1][0];
for(int i=1;i<grid[0].size();i++)
grid[0][i]+=grid[0][i-1];
for(int i=1;i<grid.size();i++)
{
for(int j=1;j<grid[0].size();j++)
{
grid[i][j]=max(grid[i-1][j],grid[i][j-1])+grid[i][j];
}
}
return grid[grid.size()-1][grid[0].size()-1];
}
};-
用原数组代替dp，降低空间复杂度
剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char,int> mp;
for(auto &i:s)
{
mp[i]++;
}
for(auto &i:s)
{
if(mp[i]==1) return i;
}
return ' ';
}
};-
哈希表，两次遍历
剑指 Offer 52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pa=headA,*pb=headB;
while(headA!=headB)
{
if(headA==nullptr) headA=pb;
else headA=headA->next;
if(headB==nullptr) headB=pa;
else headB=headB->next;
}
return headA;
}
};-
双指针
剑指 Offer 53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
if(nums.size()==0) return 0;
while(l<r)
{
int mid=l+((r-l)>>1);
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
int start=l;
l=0,r=nums.size()-1;
while(l<r)
{
int mid=1+l+((r-l)>>1);
if(nums[mid]<=target) l=mid;
else r=mid-1;
}
int end=r;
if(nums[start]!=target) return 0;
return end-start+1;
}
};-
二分查找
剑指 Offer 53 - II. 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int l=0,r=nums.size()-1;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(nums[mid]==mid) l=mid+1;
else r=mid-1;
}
return l;
}
};-
二分查找
剑指 Offer 54. 二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
class Solution {
public:
vector<int> vec;
int kthLargest(TreeNode* root, int k) {
dfs(root);
return vec[vec.size()-k];
}
void dfs(TreeNode* root)
{
if(root==nullptr) return;
if(root->left!=nullptr) dfs(root->left);
vec.push_back(root->val);
if(root->right!=nullptr) dfs(root->right);
}
};-
中序遍历
剑指 Offer 55 - I. 二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr) return 0;
return dfs(root);
}
int dfs(TreeNode* root)
{
if(root==nullptr) return 0;
return max(dfs(root->left),dfs(root->right))+1;
}
};剑指 Offer 55 - II. 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root==nullptr) return true;
if(abs(dfs(root->left)-dfs(root->right))>1) return false;
return isBalanced(root->left)&&isBalanced(root->right);
}
int dfs(TreeNode* root)
{
if(root==nullptr) return 0;
return max(dfs(root->left),dfs(root->right))+1;
}
};-
自顶向下，时间复杂度 O(N^2)
class Solution {
public:
bool isBalanced(TreeNode* root) {
return dfs(root)!=-1;
}
int dfs(TreeNode* root)
{
if(root==nullptr) return 0;
int left=dfs(root->left);
if(left==-1) return -1;
int right=dfs(root->right);
if(right==-1) return -1;
if(abs(left-right)>1) return -1;
return max(left,right)+1;
}
};-
后序遍历
-
自底向上 ，时间复杂度O（N）