Leetcode 日记:剑指offer篇

Leetcode 日记:剑指offer篇

三月 01, 2022

我真的不想刷题!! T_T

剑指 Offer 33. 二叉搜索树的后序遍历序列

题目描述:

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

    5
   / \
  2   6
 / \
1   3

示例 1:

输入: [1,6,3,2,5]
输出: false

示例 2:

输入: [1,3,2,6,5]
输出: true

code

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) {
stack<int> s;
int root = INT_MAX;
for(int i = postorder.size() - 1; i >= 0; i--){
if(postorder[i] > root){
return false;
}
while(!s.empty() && postorder[i] < s.top()){
root = s.top();
s.pop();
}
s.push(postorder[i]);
}
return true;
}
};

剑指 Offer 36. 二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
Node *pre = nullptr, *head = nullptr;
void dfs(Node* root){
if(!root) return;
dfs(root -> left);
if (pre) pre->right = root;
else head = root; // 保存链表头结点
root->left = pre;
pre = root;
dfs(root->right); //右子树
}
Node* treeToDoublyList(Node* root) {
if (!root) return root;
dfs(root);
head->left = pre;
pre->right = head;
return head;
}
};

剑指 Offer II 078. 合并排序链表

题目描述

给定一个链表数组,每个链表都已经按升序排列。
请将所有链表合并到一个升序链表中,返回合并后的链表。

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:
struct cmp{
bool operator() (ListNode* a, ListNode* b){
return a -> val > b -> val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode *, vector<ListNode *>, cmp> pq;
ListNode* dummy = new ListNode(0);
for(auto p : lists){
if(p) pq.push(p);
}
ListNode* t = dummy;

while(!pq.empty()){
t -> next = pq.top();
t = pq.top();
pq.pop();
if(t->next){
pq.push(t->next);
}
}
return dummy->next;

}
};

剑指 Offer II 106. 二分图

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
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
if(n == 0){
return true;
}
vector<int> color(n, 0);
queue<int> q;
for(int i = 0; i < n; i++){
if(!color[i]){
q.push(i);
color[i] = 1;
}
while(!q.empty()){
int node = q.front();
q.pop();
for(const int & j : graph[node]){
if(color[j] == 0){
color[j] = color[node] == 2 ? 1 : 2;
q.push(j);
}
else if(color[node] == color[j])
return false;
}
}
}
return true;
}
};

Gitalking ...