选得幽居惬野情，终年无送亦无迎。
有时直上孤峰顶，月下披云啸一声。
剑指 Offer 31. 栈的压入与弹出序列*
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int len=pushed.size();
stack<int> s;
int j=0;
for(int i=0;i<len;i++){
if(s.empty()) {s.push(pushed[j]); j++;}
if(popped[i]==s.top()) {s.pop();}
else {
while(popped[i]!=s.top()) {
if(j==len) return false;
s.push(pushed[j]);
j++;
}
s.pop();
}
}
return true;
}
};
|
剑指 Offer 32. 从上到下打印二叉树*
队列实现层次遍历即可
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
节点总数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
queue<TreeNode *> que;
que.push(root);
while(!que.empty()) {
TreeNode * t=que.front();
que.pop();
ans.push_back(t->val);
if(t->left) que.push(t->left);
if(t->right) que.push(t->right);
}
return ans;
}
};
|
每一层打印到一行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode *> que;
que.push(root);
que.push(nullptr);
vector<int> temp;
while(!que.empty()) {
TreeNode * t=que.front();
if(!t) {
ans.push_back(temp);
temp.clear();
que.pop();
continue;
}
temp.push_back(t->val);
if(t->left) que.push(t->left);
if(t->right) que.push(t->right);
que.pop();
if(!que.front()) que.push(nullptr);
}
ans.pop_back();
return ans;
}
};
|
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
提示：
节点总数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
deque<TreeNode *> que;
que.push_back(root);
que.push_back(nullptr);
vector<int> temp;
bool flag=0;
while(!que.empty()) {
if(!flag) {
TreeNode * t=que.front();
if(!t) {
ans.push_back(temp);
temp.clear();
que.pop_front();
flag=1-flag;
continue;
}
temp.push_back(t->val);
if(t->left) que.push_back(t->left);
if(t->right) que.push_back(t->right);
que.pop_front();
if(!que.front()) que.push_front(nullptr);
} else {
TreeNode * t=que.back();
if(!t) {
ans.push_back(temp);
temp.clear();
que.pop_back();
flag=1-flag;
continue;
}
temp.push_back(t->val);
if(t->right) que.push_front(t->right);
if(t->left) que.push_front(t->left);
que.pop_back();
if(!que.back()) que.push_back(nullptr);
}
}
ans.pop_back();
return ans;
}
};
|
剑指 Offer 33. 二叉搜索树的后序遍历序列*
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
示例 1：输入: [1,6,3,2,5]
输出: false
示例 2：输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
int len=postorder.size();
if(len<=1) return true;
return fun(postorder, 0, len-1);
}
bool fun(vector<int>& postorder, int l, int r){
if(l>=r) return true;
int i;
for(i=l;i<r;i++) {if(postorder[i]>postorder[r]) break;}
for(int j=i+1;j<r;j++) {if(postorder[j]<postorder[r]) return false;}
return fun(postorder,l,i-1) && fun(postorder,i,r-1);
}
};
|
剑指 Offer 34. 二叉树中和为某一值的路径*
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
提示：
节点总数 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
dfs(root, sum);
return ans;
}
void dfs(TreeNode* &root, int sum){
if(!root) return;
path.push_back(root->val);
if(!root->left && !root->right && root->val==sum) {
ans.push_back(path);
path.pop_back();
return;
}
dfs(root->left, sum-(root->val));
dfs(root->right, sum-(root->val));
path.pop_back();
}
};
|
剑指 Offer 35. 复杂链表的复制*
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return nullptr;
Node *p=head, *q, *ans, *a;
while(p) {
q=p->next;
Node *t=new Node(p->val);
p->next=t;
t->next=q;
p=q;
}
p=head;
while(p) {
if(p->random) {
p->next->random=p->random->next;
}
p=p->next->next;
}
p=head;
ans=head->next;
a=head->next;
while(p) {
q=p->next->next;
if(q) {
p->next=q;
a->next=q->next;
} else {
p->next=nullptr;
a->next=nullptr;
}
a=a->next;
p=q;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL) return head;
unordered_map<Node*,Node*>mp;
Node *t=head;
while(t!=NULL){
mp[t]=new Node(t->val);
t=t->next;
}
t=head;
while(t!=NULL){
if(t->next){
mp[t]->next=mp[t->next];
}
if(t->random){
mp[t]->random=mp[t->random];
}
t=t->next;
}
return mp[head];
}
};
|
剑指 Offer 36. 二叉搜索树与双向链表*
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
class Solution {
public:
Node* treeToDoublyList(Node* node) {
if(!node) return nullptr;
if(!node->left && !node->right) {
node->left=node;
node->right=node;
return node;
} else if(!node->left) {
Node *t=treeToDoublyList(node->right);
node->right=t;
node->left=t->left;
t->left->right=node;
t->left=node;
return node;
} else if(!node->right) {
Node *t=treeToDoublyList(node->left);
node->right=t;
node->left=t->left;
t->left->right=node;
t->left=node;
return t;
}
node->right=treeToDoublyList(node->right);
Node* t1=node->right->left;
Node* t2=treeToDoublyList(node->left);
node->left=t2->left;
node->right->left=node;
node->left->right=node;
t1->right=t2;
t2->left=t1;
cout << "4:" << t2->val << endl;
return t2;
}
};
|
剑指 Offer 37. 序列化二叉树*
请实现两个函数，分别用来序列化和反序列化二叉树。
你可以将以下二叉树：
1 - (2) | (3-(4)|(5))
序列化为 “[1,2,3,null,null,4,5]”
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
class Codec {
public:
string serialize(TreeNode* root) {
string ans="";
if(!root) return ans;
int count_null=0;
queue<TreeNode *> que;
TreeNode * t=nullptr;
que.push(root);
while(!que.empty()){
t=que.front();
que.pop();
if(!t) {
ans+= "null ";
count_null++;
} else {
que.push(t->left);
que.push(t->right);
ans+= to_string(t->val) + " ";
count_null=0;
}
}
ans = ans.substr(0, ans.size()-5*count_null);
return ans;
}
TreeNode* deserialize(string data) {
int len=data.size();
if(!len) return nullptr;
int i=0, j=0, k;
while(j+1<len && data[j+1]!=' ') { j++; }
string s=data.substr(i, j-i+1);
k=atoi(s.c_str());
TreeNode *p=new TreeNode(k);
i=j+2;
queue<TreeNode *> que;
que.push(p);
bool isLeft=1;
while(i<len) {
TreeNode *q=que.front(), *t;
if(data[i]=='n') {
i+=5;
t=nullptr;
} else {
j=i;
while(j+1<len && data[j+1]!=' ') { j++; }
string s=data.substr(i, j-i+1);
k=atoi(s.c_str());
i=j+2;
t=new TreeNode(k);
que.push(t);
}
if(isLeft) {
q->left=t;
} else{
q->right=t;
que.pop();
}
isLeft = 1-isLeft;
}
return p;
}
};
|
剑指 Offer 38. 字符串的排列*
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
限制：
1 <= s 的长度 <= 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
vector<string> permutation(string s) {
vector<string> ans;
fun(ans,s,0);
return ans;
}
void fun(vector<string> &ans, string &s, int left) {
if(left==s.size()) {
ans.push_back(s);
return;
}
for(int i=left; i<s.size(); i++) {
bool flag=1;
for(int j=left; j<i; j++){
if(s[j]==s[i]) { flag=0; }
}
if(flag) {
swap(s[left],s[i]);
fun(ans, s, left+1);
swap(s[left],s[i]);
} else{
continue;
}
}
}
};
|
剑指 Offer 39. 数组中出现次数过半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public:
int majorityElement(vector<int>& nums) {
int count=0;
int len = nums.size(), num;
for(int i=0; i<len; i++) {
if(!count) {
num=nums[i];
count++;
} else if(num==nums[i]) {
count++;
} else {
count--;
}
}
return num;
}
};
|
剑指 Offer 40. 最小的k个数*
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> ans;
quick_sort(arr,0,arr.size()-1,k);
for(int i=0;i<k;i++) ans.push_back(arr[i]);
return ans;
}
void quick_sort(vector<int>& arr, int l, int r, int k) {
if(l>=r) return;
int i=l-1, j=r+1, num=arr[(l+r)/2];
while(i<j) {
i++;j--;
while(arr[i]<num) {i++;}
while(arr[j]>num) {j--;}
if(i<j) swap(arr[i], arr[j]);
cout << i << j << endl;
}
if(j-l+1==k) return;
else if(j-l+1>k) quick_sort(arr, l, j, k);
else quick_sort(arr, j+1, r, k-(j-l+1));
return;
}
};
|
