LeetCode 图解算法数据结构
替换空格
class Solution {
public:
string replaceSpace(string s) {
string res;
for(auto c:s){
if(c!=' '){
res+=c;
continue;
}
res+="%20";
}
return res;
}
};
从尾到头打印链表
方法一：递归
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector reversePrint(ListNode* head) {
vector res;
if(head==NULL){
return res;
}
res=reversePrint(head->next);
res.push_back(head->val);
return res;
}
};
方法二：栈
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector reversePrint(ListNode* head) {
vector res;
stack stack;
while(head!=NULL){
stack.push(head->val);
head=head->next;
}
while(!stack.empty()){
res.push_back(stack.top());
stack.pop();
}
return res;
}
};
用两个栈实现队列
class CQueue {
private:
stack stack1;
stack stack2;
public:
CQueue() {
}
void appendTail(int value) {
stack1.push(value);
}
int deleteHead() {
int res=-1;
if(stack1.empty() && stack2.empty()){
return res;
}
if(!stack2.empty()){
res=stack2.top();
stack2.pop();
return res;
}
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
res=stack2.top();
stack2.pop();
return res;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
表示数值的字符串
class Solution {
private:
bool scanUnsignedInteger(string &s,int &index){
int pos=index;
while(s[index]>='0' && s[index]<='9'){
index++;
}
return index>pos;
}
bool scanInteger(string &s,int &index){
if(s[index]=='+' || s[index]=='-'){
index++;
}
return scanUnsignedInteger(s,index);
}
public:
bool isNumber(string s) {
int index=0;
bool numeric=false;
while(s[index]==' '){
index++;
}
numeric=scanInteger(s,index);
if(s[index]=='.'){
index++;
numeric=(scanUnsignedInteger(s,index)||numeric);
}
if(s[index]=='e' || s[index]=='E'){
index++;
numeric=numeric&&scanInteger(s,index);
}
while(s[index]==' '){
index++;
}
return numeric&&(index==s.size());
}
};
反转链表
方法一：递归
/**
* 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) {
if(head==NULL || head->next==NULL){
return head;
}
ListNode *tail=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tail;
}
};
方法二：双指针
/**
* 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) {
if(head==NULL || head->next==NULL){
return head;
}
ListNode *cur=head;
ListNode *pre=NULL;
while(cur!=NULL){
ListNode *temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
};
包含min函数的栈
class MinStack {
private:
stack stack;
vector minNums;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
stack.push(x);
if(minNums.empty()){
minNums.push_back(x);
}
else {
minNums.push_back(std::min(minNums[minNums.size()-1],x));
}
}
void pop() {
stack.pop();
minNums.pop_back();
}
int top() {
return stack.top();
}
int min() {
return minNums[minNums.size()-1];
}
};
/**
* 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();
*/
复杂链表的复制
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL){
return head;
}
Node *cur=head;
while(cur!=NULL){
Node *temp=new Node(cur->val);
temp->next=cur->next;
cur->next=temp;
cur=temp->next;
}
cur=head;
while(cur!=NULL){
Node *temp=cur->next;
temp->random=cur->random==NULL?NULL:cur->random->next;
cur=temp->next;
}
cur=head;
Node *newHead=head->next;
while(cur!=NULL){
Node *temp=cur->next;
cur->next=temp->next;
temp->next=cur->next==NULL?NULL:cur->next->next;
cur=cur->next;
}
return newHead;
}
};
拼接 + 拆分
左旋转字符串
class Solution {
public:
string reverseLeftWords(string s, int n) {
string res;
for(int i=n;i
滑动窗口的最大值
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
vector deque,res;
if(nums.empty()){
return res;
}
int max=0;
for(int i=0;imax){
max=nums[i];
}
deque.push_back(nums[i]);
}
res.push_back(max);
for(int i=k;imax){
max=deque[j];
}
}
deque.push_back(nums[i]);
res.push_back(max);
}
return res;
}
};
队列的最大值
class MaxQueue {
private:
queue queue;
deque deque;
public:
MaxQueue() {
}
int max_value() {
if(queue.empty()){
return -1;
}
return deque.front();
}
void push_back(int value) {
queue.push(value);
if(deque.empty()){
deque.push_back(value);
}
else {
while(!deque.empty() && deque.back()max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
把字符串转换成整数
class Solution {
public:
int strToInt(string str) {
int index=0,res=0,symbol=1,bndry=INT_MAX/10;
while(str[index]==' '){
index++;
}
if(str[index]=='-'){
symbol=-1;
}
if(str[index]=='-' || str[index]=='+'){
index++;
}
for(int i=index;i'9'){
break;
}
if(res>bndry || (res>=bndry && str[i]>'7')){
return symbol==1?INT_MAX:INT_MIN;
}
res=res*10+(str[i]-'0');
}
return symbol*res;
}
};
斐波那契数列
class Solution {
public:
int fib(int n) {
int a=0,b=1;
if(n==0){
return a;
}
for(int i=2;i<=n;i++){
int temp=a;
a=b;
b=(temp+b)%1000000007;
}
return b;
}
};
青蛙跳台阶问题
class Solution {
public:
int numWays(int n) {
int a=1,b=1;
if(n==0 || n==1){
return 1;
}
for(int i=2;i<=n;i++){
int temp=a;
a=b;
b=(temp+b)%1000000007;
}
return b;
}
};
连续子数组的最大和
class Solution {
public:
int maxSubArray(vector& nums) {
int max=nums[0],temp=nums[0];
for(int i=1;i 
把数字翻译成字符串
class Solution {
public:
int translateNum(int num) {
int a=1,b=1;
while(num>9){
int end=num%100;
int c=end>=10 && end<=25?a+b:a;
b=a;
a=c;
num/=10;
}
return a;
}
};
礼物的最大价值
class Solution {
public:
int maxValue(vector>& grid) {
int rows=grid.size(),cols=grid[0].size();
//初始化第一行
for(int i=1;i 
最长不含重复字符的子字符串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map map;
int maxLength=0,preMax=0;
for(int i=0;i 解题思路
本题主要需要弄懂状态转移方程即可
丑数
class Solution {
public:
int nthUglyNumber(int n) {
vector nums(1,1);
int a=0,b=0,c=0;
while(nums.size() 
n个骰子的点数
class Solution {
public:
vector dicesProbability(int n) {
vector probability(6,1.0/6);
for(int i=1;i temp((i+1)*5+1,0);
for(int j=0;j 
股票的最大利润
class Solution {
public:
int maxProfit(vector& prices) {
if(prices.empty()){
return 0;
}
int profit=0,minPrice=prices[0];
for(auto price:prices){
if(price 
矩阵中的路径
class Solution {
public:
bool dfs(vector>& board, string word, int i, int j, int k){
if(i>=board.size() || i<0 || j>=board[0].size() || j<0 || board[i][j]!=word[k])
return false;
if(k==word.size()-1)
return true;
board[i][j]=' ';
bool res = dfs(board, word, i-1, j, k+1) || dfs(board, word, i+1, j, k+1) || dfs(board, word, i, j-1, k+1) || dfs(board, word, i, j+1, k+1);
board[i][j]=word[k];
return res;
}
bool exist(vector>& board, string word) {
int rows=board.size();
int cols=board[0].size();
for(int i=0;i DFS 解析：
递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
返回 false：
-
行或列索引越界
-
当前矩阵元素与目标字符不同
-
当前矩阵元素已访问过 （ (3) 可合并至 (2) ） 。
返回 true： k = len(word) - 1 ，即字符串 word 已全部匹配。
递推工作：
标记当前矩阵元素： 将 board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。
搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。
返回值： 返回布尔量 res ，代表是否搜索到目标字符串。
机器人的运动范围
class Solution {
public:
int dfs(vector>& isVisited,int i, int j, int m,int n,int k){
if(i<0 || i>=m || j<0 || j>=n || isVisited[i][j])
return 0;
int temp=0,row=i,col=j;
while(row!=0){
temp+=(row%10);
row/=10;
}
while(col!=0){
temp+=(col%10);
col/=10;
}
if(temp>k){
isVisited[i][j]=1;
return 0;
}
isVisited[i][j]=1;
int res=1;
res+=(dfs(isVisited, i-1, j, m, n, k) + dfs(isVisited, i+1, j, m, n, k) + dfs(isVisited, i, j-1, m, n, k) + dfs(isVisited, i, j+1, m, n, k));
return res;
}
int movingCount(int m, int n, int k) {
vector> isVisited(m,vector(n,0));
return dfs(isVisited,0,0,m,n,k);
}
};
树的子结构
/**
* 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 isEqual(TreeNode* A, TreeNode* B){
if(B==NULL)
return true;
if(A==NULL || A->val!=B->val)
return false;
return isEqual(A->left,B->left) && isEqual(A->right,B->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
return (A!=NULL && B!=NULL) && (isEqual(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,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:
TreeNode* mirrorTree(TreeNode* root) {
if(root==NULL){
return NULL;
}
TreeNode *temp=root->left;
root->left=mirrorTree(root->right);
root->right=mirrorTree(temp);
return root;
}
};
对称的二叉树
/**
* 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 symmetric(TreeNode *left,TreeNode *right){
if(left==NULL && right==NULL){
return true;
}
if(left==NULL || right==NULL){
return false;
}
if(left->val!=right->val){
return false;
}
return symmetric(left->left,right->right) && symmetric(left->right,right->left);
}
bool isSymmetric(TreeNode* root) {
if(root==NULL)
return true;
return symmetric(root->left,root->right);
}
};
从上到下打印二叉树
/**
* 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 levelOrder(TreeNode* root) {
vector res;
if(root==NULL){
return res;
}
queue queue;
queue.push(root);
while(!queue.empty()){
for(int i=0;ival);
if(node->left!=NULL){
queue.push(node->left);
}
if(node->right!=NULL){
queue.push(node->right);
}
queue.pop();
}
}
return res;
}
};
从上到下打印二叉树 ΙΙ
/**
* 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> levelOrder(TreeNode* root) {
vector> res;
if(root==NULL){
return res;
}
queue queue;
queue.push(root);
while(!queue.empty()){
vector row;
int times=queue.size();
for(int i=0;ival);
if(node->left!=NULL){
queue.push(node->left);
}
if(node->right!=NULL){
queue.push(node->right);
}
queue.pop();
}
res.push_back(row);
}
return res;
}
};
从上到下打印二叉树 ΙΙΙ
/**
* 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> levelOrder(TreeNode* root) {
deque deque;
vector> res;
if(root != NULL) deque.push_back(root);
while(!deque.empty()) {
// 打印奇数层
vector tmp;
for(int i = deque.size(); i > 0; i--) {
// 从左向右打印
TreeNode* node = deque.front();
deque.pop_front();
tmp.push_back(node->val);
// 先左后右加入下层节点
if(node->left != NULL) deque.push_back(node->left);
if(node->right != NULL) deque.push_back(node->right);
}
res.push_back(tmp);
if(deque.empty()) break; // 若为空则提前跳出
// 打印偶数层
tmp.clear();
for(int i = deque.size(); i > 0; i--) {
// 从右向左打印
TreeNode* node = deque.back();
deque.pop_back();
tmp.push_back(node->val);
// 先右后左加入下层节点
if(node->right != NULL) deque.push_front(node->right);
if(node->left != NULL) deque.push_front(node->left);
}
res.push_back(tmp);
}
return res;
}
};
二叉树中和为某一值的路径
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(vector>& res,vector& row,TreeNode *node,int sum,int target){
sum+=node->val;
row.push_back(node->val);
if(sum==target && node->left== nullptr && node->right== nullptr){
res.push_back(row);
}
if(node->left!= nullptr){
dfs(res,row,node->left,sum,target);
row.pop_back();
}
if(node->right!= nullptr){
dfs(res,row,node->right,sum,target);
row.pop_back();
}
}
vector> pathSum(TreeNode* root, int target) {
vector> res;
if(root==NULL){
return res;
}
vector row;
dfs(res,row,root,0,target);
return res;
}
};
二叉搜索树与双向链表
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
void dfs(vector& nodes,Node *root){
if(root==NULL){
return;
}
dfs(nodes,root->left);
nodes.push_back(root);
dfs(nodes,root->right);
}
Node* treeToDoublyList(Node* root) {
if(root==NULL){
return NULL;
}
vector nodes;
dfs(nodes,root);
Node *pre=nodes[0];
for(int i=1;iright=nodes[i];
nodes[i]->left=pre;
pre=nodes[i];
}
Node *start=nodes[0];
Node *end=nodes[nodes.size()-1];
start->left=end;
end->right=start;
Node *head=new Node(0);
head->right=start;
return start;
}
};
字符串的排列
class Solution {
public:
void dfs(vector& res,string s,int index){
if(index==s.length()-1){
res.push_back(s);
return;
}
unordered_set cs;
for(int i=index;i permutation(string s) {
vector res;
dfs(res,s,0);
return res;
}
};
二叉搜索树的第k大节点
方法一
/**
* 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:
void dfs(vector& nums,TreeNode *node){
if(node==NULL){
return;
}
dfs(nums,node->left);
nums.push_back(node->val);
dfs(nums,node->right);
}
int kthLargest(TreeNode* root, int k) {
vector nums;
dfs(nums,root);
return nums[nums.size()-k];
}
};
方法二
/**
* 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:
void dfs(int& res,TreeNode *node,int& k,bool isOk){
if(node==NULL || isOk){
return;
}
dfs(res,node->right,k,isOk);
k--;
if(k==0){
res=node->val;
isOk=true;
}
dfs(res,node->left,k,isOk);
}
int kthLargest(TreeNode* root, int k) {
int res;
dfs(res,root,k, false);
return res;
}
};
二叉树的深度
/**
* 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:
void dfs(int& maxDepth,TreeNode *node,int depth){
if(node==NULL)
return;
depth++;
maxDepth=max(maxDepth,depth);
dfs(maxDepth,node->left,depth);
dfs(maxDepth,node->right,depth);
}
int maxDepth(TreeNode* root) {
int maxDepth=0;
dfs(maxDepth,root,0);
return maxDepth;
}
};
平衡二叉树
/**
* 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:
int recur(TreeNode *node){
if(node==NULL){
return 0;
}
int left=recur(node->left);
if(left==-1){
return -1;
}
int right=recur(node->right);
if(right==-1){
return -1;
}
return abs(left-right)<2?max(left,right)+1:-1;
}
bool isBalanced(TreeNode* root) {
int res=recur(root);
return res!=-1;
}
};
求 1 + 2 + ... + n
class Solution {
public:
int sumNums(int n) {
if(n==1)
return 1;
return n+sumNums(n-1);
}
};
二叉搜索树的最近公共祖先
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(p->val>q->val){
swap(p,q);
}
while(root!=NULL){
if(root->valval){
root=root->right;
}
else if(root->val>q->val){
root=root->left;
}
else {
break;
}
}
return root;
}
};
二叉树的最近公共祖先
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL || root==p || root==q)
return root;
TreeNode *left=lowestCommonAncestor(root->left,p,q);
TreeNode *right=lowestCommonAncestor(root->right,p,q);
if(left==NULL && right==NULL)
return NULL;
if(left==NULL)
return right;
if(right==NULL)
return left;
return root;
}
};
重建二叉树
/**
* 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* recur(vector& preorder,unordered_map& map,int root,int left,int right){
if(left>right)
return NULL;
TreeNode *node=new TreeNode(preorder[root]);
int i=map[preorder[root]];
node->left=recur(preorder,map,root+1,left,i-1);
node->right=recur(preorder,map,root+i-left+1,i+1,right);
return node;
}
TreeNode* buildTree(vector& preorder, vector& inorder) {
unordered_map map;
for(int i=0;i 
数值的整数次方
class Solution {
public:
double myPow(double x, int n) {
if(x==0.0f){
return x;
}
double res=1.0;
long b=n;
if(b<0){
x=1.0/x;
b=-b;
}
while(b>0){
if(b&1==1)
res*=x;
x*=x;
b>>=1;
}
return res;
}
};
打印从 1 到最大的 n 位数
class Solution {
public:
vector printNumbers(int n) {
int times=1;
while(n>0){
times*=10;
n--;
}
vector res;
for(int i=1;i 
二叉搜索树的后序遍历序列
class Solution {
public:
bool verifyPostorder(vector& postorder) {
stack stack;
int root=INT_MAX;
for(int i=postorder.size()-1;i>=0;i--){
if(postorder[i]>root)
return false;
while(!stack.empty() && stack.top()>postorder[i]){
root=stack.top();
stack.pop();
}
stack.push(postorder[i]);
}
return true;
}
};
数组中的逆序对
class Solution {
public:
int mergeSort(int left,int right,vector &nums,vector& temp){
if(left>=right)
return 0;
int mid=(left+right)/2;
int res=mergeSort(left,mid,nums,temp)+mergeSort(mid+1,right,nums,temp);
int i=left,j=mid+1;
for(int k=left;k<=right;k++){
temp[k]=nums[k];
}
for(int k=left;k<=right;k++){
if(i==mid+1){
nums[k]=temp[j++];
}
else if(j==right+1 || temp[i]<=temp[j]){
nums[k]=temp[i++];
}
else {
nums[k]=temp[j++];
res+=mid-i+1;
}
}
return res;
}
int reversePairs(vector& nums) {
vector temp(nums.size());
return mergeSort(0,nums.size()-1,nums,temp);
}
};
最小的 k 个数
class Solution {
public:
void mergeSort(vector& nums,int left,int right){
if(left>=right)
return;
int mid=(left+right)/2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
int temp[right-left+1];
for(int k=left;k<=right;k++){
temp[k-left]=nums[k];
}
int i=0,j=mid-left+1;
for(int k=left;k<=right;k++){
if(i==mid-left+1){
nums[k]=temp[j++];
}
else if(j==right-left+1 || temp[i]<=temp[j]){
nums[k]=temp[i++];
}
else {
nums[k]=temp[j++];
}
}
}
vector getLeastNumbers(vector& arr, int k) {
int size=arr.size();
mergeSort(arr,0,arr.size()-1);
for(int i=size-k;i>0;i--){
arr.pop_back();
}
return arr;
}
};
数据流中的中位数
class MedianFinder {
private:
priority_queue,greater> A;//小顶堆，用于存储较大的一半
priority_queue,less> B;//大顶堆，用于存储较小的一半
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if(A.size()!=B.size()){
A.push(num);
B.push(A.top());
A.pop();
}
else {
B.push(num);
A.push(B.top());
B.pop();
}
}
double findMedian() {
return A.size()==B.size()?(A.top()+B.top())/2.0:A.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
把数组排成最小的数
class Solution {
public:
void quickSort(vector& strs,int left,int right){
if(left>=right)
return;
int i=left,j=right;
while(i=strs[left]+strs[j] && i& nums) {
vector strs;
for(auto num:nums){
strs.push_back(to_string(num));
}
string res;
quickSort(strs,0,strs.size()-1);
for(auto str:strs){
res.append(str);
}
return res;
}
};
扑克牌中的顺子
class Solution {
public:
void mergeSort(vector& nums,int left,int right){
if(left>=right)
return;
int mid=(left+right)/2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
int temp[right-left+1];
for(int k=left;k<=right;k++){
temp[k-left]=nums[k];
}
int i=0,j=mid-left+1;
for(int k=left;k<=right;k++){
if(i==mid-left+1)
nums[k]=temp[j++];
else if(j==right-left+1 || temp[i]<=temp[j])
nums[k]=temp[i++];
else
nums[k]=temp[j++];
}
}
bool isStraight(vector& nums) {
mergeSort(nums,0,nums.size()-1);
int joker=0;
for(int i=0;i 
数组中重复的数字
class Solution {
public:
int findRepeatNumber(vector& nums) {
unordered_map map;
for(auto num:nums){
if(map[num])
return num;
map[num]=true;
}
return -1;
}
};
二维数组中的查找
class Solution {
public:
bool findNumberIn2DArray(vector>& matrix, int target) {
for(int i=0;i0 && (matrix[i][0]>target || matrix[i][matrix[i].size()-1] 
旋转数组的最小数字
class Solution {
public:
int minArray(vector& numbers) {
int left=0,right=numbers.size()-1;
while(leftnumbers[right])
left=mid+1;
else if(numbers[mid] 
第一个只出现一次的字符
class Solution {
public:
char firstUniqChar(string s) {
queue queue;
unordered_map map;
for(auto c:s){
if(map.count(c)==0){
queue.push(c);
map[c]=1;
}
else {
map[c]=++map[c];
}
}
while(!queue.empty()){
char c = queue.front();
if(map[c]==1){
return c;
}
queue.pop();
}
return ' ';
}
};
在排序数组中查找数字 Ι
class Solution {
public:
int search(vector& nums, int target) {
int left=0,right=nums.size()-1;
int res=0;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]target)
right=mid-1;
else{
res+=1;
int p1=mid-1,p2=mid+1;
while(p1>=0 && nums[p1]==target){
res++;
p1--;
}
while(p2<=nums.size()-1 && nums[p2]==target){
res++;
p2++;
}
return res;
}
}
return res;
}
};
0 ~ n-1 中缺失的数字
class Solution {
public:
int missingNumber(vector& nums) {
int left=0,right=nums.size()-1;
while(left 
删除链表的节点
/**
* 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) {
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* cur=head;
while(cur!=NULL){
if(cur->val==val){
pre->next=cur->next;
cur->next=NULL;
break;
}
else {
cur=cur->next;
pre=pre->next;
}
}
return cur==head?pre->next:head;
}
};
调整数组顺序使奇数位于偶数前面
class Solution {
public:
vector exchange(vector& nums) {
int left=0,right=nums.size()-1;
while(left 
链表中倒数第 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* p1=head;
ListNode* p2=head;
for(int i=0;inext;
}
while(p2!=NULL && p2->next!=NULL){
p1=p1->next;
p2=p2->next;
}
return p2==NULL?p1:p1->next;
}
};
合并两个排序的链表
/**
* 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) {
if(l1==NULL || l2==NULL){
return l1==NULL?l2:l1;
}
if(l1->val<=l2->val){
l1->next=mergeTwoLists(l1->next,l2);
}
else{
l2->next=mergeTwoLists(l1,l2->next);
}
return l1->val<=l2->val?l1:l2;
}
};
两个链表的第一个公共节点
/**
* 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) {
ListNode* p1=headA;
ListNode* p2=headB;
while(p1!=p2){
p1=p1!=NULL?p1->next:headB;
p2=p2!=NULL?p2->next:headA;
}
return p1;
}
};/**
* 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) {
ListNode* p1=headA;
ListNode* p2=headB;
while(p1!=p2){
p1=p1!=NULL?p1->next:headB;
p2=p2!=NULL?p2->next:headA;
}
return p1;
}
};
和为 s 的两个数字
class Solution {
public:
vector twoSum(vector& nums, int target) {
int left=0,right=nums.size()-1;
vector res;
while(lefttarget){
right--;
}
else if(sum 
翻转单词顺序
class Solution {
public:
string reverseWords(string s) {
if(s.length()==0){
return s;
}
int left=0,right=0;
bool hasLetter=false;
string res="";
while(right
二进制中 1 的个数
class Solution {
public:
int hammingWeight(uint32_t n) {
int res=0;
while(n!=0){
n%2==0?res:res++;
n>>=1;
}
return res;
}
};
