0%

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}

双向链表,小了则移除,压入潜在最大值的下标,滑出则移除

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
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> result;
deque<int> tower;
result.reserve(num.size() - size + 1);
for (int i = 0; i < num.size(); i++)
{
while (tower.size() > 0 && num[tower.back()] < num[i])
{
tower.pop_back();
}
while (tower.size() > 0 && i - tower.front() >= size )
{
tower.pop_front();
}
tower.push_back(i);
if (i >= size - 1)
{
result.push_back(num[tower.front()]);
}
}
return result;
}
};

如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

最小堆+最大堆

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
class Solution {
public:
vector<int> max, min;
void Insert(int num)
{
if(((min.size() + max.size()) & 1) == 0)
{
if (min.size() > 0 && num > min[0])
{
min.push_back(num);
push_heap(min.begin(), min.end(), greater<int>());
num = min[0];
pop_heap(min.begin(), min.end(), greater<int>());
min.pop_back();
}
max.push_back(num);
push_heap(max.begin(), max.end(), less<int>());
}
else
{
if (max.size() > 0 && num < max[0])
{
max.push_back(num);
push_heap(max.begin(), max.end(), less<int>());
num = max[0];
pop_heap(max.begin(), max.end(), less<int>());
max.pop_back();
}
min.push_back(num);
push_heap(min.begin(), min.end(), greater<int>());
}
}

double GetMedian()
{
const int size = min.size() + max.size();
if (size == 0)
{
return 0;
}
else if ((size & 1) == 0)
{
return static_cast<double>(max[0] + min[0]) / 2;
}
else
{
return max[0];
}
}
};

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

中序,root不压栈、设为c

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
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
TreeNode *c = pRoot;
stack<TreeNode*> s;
while (c != nullptr || s.size() > 0)
{
while (c != nullptr)
{
s.push(c);
c = c->left;
}
c = s.top();
s.pop();
k--;
if (k == 0)
{
return c;
}
c = c->right;
}
return nullptr;
}
};

请实现两个函数,分别用来序列化和反序列化二叉树

二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#),以 ! 表示一个结点值的结束(value!)。

二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。

  1. 前序,但空节点输出空字符
  2. 要求char*,考虑reinterpret_cast<char*>(int*)
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
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
int d[65535];
const int EMPTY = numeric_limits<int>::max();
char* Serialize(TreeNode *root) {
if (root == nullptr)
{
return nullptr;
}
else
{
stack<TreeNode*> s;
s.push(root);
for (int i = 0; s.size() > 0; i++)
{
TreeNode *n = s.top();
s.pop();
if (n == nullptr)
{
d[i] = EMPTY;
}
else
{
d[i] = n->val;
s.push(n->right);
s.push(n->left);
}
}
return reinterpret_cast<char*>(d);
}
}
TreeNode* Deserialize(char *str) {
int *dd = reinterpret_cast<int*>(str);
if (str == nullptr || *dd == EMPTY)
{
return nullptr;
}
else
{
TreeNode *root = new TreeNode(*dd);
stack<TreeNode*> s;
s.push(root);
for (int i = 1; s.size() > 0; i++)
{
for (int lvalue; (lvalue = dd[i]) != EMPTY; i++)
{
TreeNode *lchild = new TreeNode(lvalue);
s.top()->left = lchild;
s.push(lchild);
}
i++;
for (int rvalue; s.size() > 0 && (rvalue = dd[i]) == EMPTY; i++)
{
s.pop();
}
if (s.size() > 0)
{
TreeNode *rchild = new TreeNode(dd[i]);
s.top()->right = rchild;
s.pop();
s.push(rchild);
}
}
return root;
}
}
};

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

开始打印任意一层前记录list大小,以区分各行

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
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
if (pRoot == nullptr)
{
return {};
}
else
{
vector<vector<int>> result;
list<TreeNode*> l{pRoot};
int size;
while (size = l.size())
{
vector<int> row;
row.reserve(size);
for (; size > 0; size--)
{
TreeNode *n = l.front();
l.pop_front();
row.push_back(n->val);
if (n->left != nullptr)
{
l.push_back(n->left);
}
if (n->right != nullptr)
{
l.push_back(n->right);
}
}
result.push_back(row);
}
return result;
}
}
};

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

右进左出即反向,两端进出即双向链表

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
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
if (pRoot == nullptr)
{
return {};
}
else
{
vector<vector<int>> result;
bool isLeftFirst = true;
list<TreeNode*> l{pRoot};
int line_width;
while (line_width = l.size())
{
vector<int> row;
row.reserve(line_width);
if (isLeftFirst)
{
for (; line_width > 0; line_width--)
{
TreeNode *n = l.front();
l.pop_front();
row.push_back(n->val);
if (n->left != nullptr)
{
l.push_back(n->left);
}
if (n->right != nullptr)
{
l.push_back(n->right);
}
}
isLeftFirst = false;
}
else
{
for (; line_width > 0; line_width--)
{
TreeNode *n = l.back();
l.pop_back();
row.push_back(n->val);
if (n->right != nullptr)
{
l.push_front(n->right);
}
if (n->left != nullptr)
{
l.push_front(n->left);
}
}
isLeftFirst = true;
}
result.push_back(row);
}
return result;
}
}
};

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

  1. 子树对称、递归
  2. 左中右、右中左、DFS
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
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if (pRoot == nullptr)
{
return true;
}
else
{
stack<TreeNode*> s;
s.push(pRoot->left);
s.push(pRoot->right);
while (s.size() > 1)
{
TreeNode *r, *l;
r = s.top();
s.pop();
l = s.top();
s.pop();
if (r != nullptr && l != nullptr)
{
if (r->val != l->val)
{
return false;
}
s.push(l->left);
s.push(r->right);
s.push(l->right);
s.push(r->left);
}
else if (!(l == nullptr && r == nullptr))
{
return false;
}
}
return true;
}
}
};

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

左中右,有右则右,没有则上。右上后左上,无左上则空。

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
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if (pNode->right == nullptr)
{
while (pNode->next && pNode->next->right == pNode)
{
pNode = pNode->next;
}
if (pNode->next == nullptr)
{
return nullptr;
}
else
{
return pNode->next;
}
}
else
{
pNode = pNode->right;
while (pNode->left)
{
pNode = pNode->left;
}
return pNode;
}
}
};

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

判重、全删

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
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if (pHead == nullptr || pHead->next == nullptr)
{
return pHead;
}
else
{
ListNode head(pHead->val - 1);
head.next = pHead;
ListNode *last = &head, *current = head.next;
while (current != nullptr)
{
if (current->next != nullptr &&current->val == current->next->val)
{
while (current->next != nullptr && current->val == current->next->val)
{
ListNode *tail = current->next->next;
// delete current->next;
current->next = tail;
}
current = current->next;
// delete current
last->next = current;
}
else
{
last = current;
current = current->next;
}
}
return head.next;
}
}
};

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

快慢指针,有环必相遇。设环长c,环外长d,自环外起点,从0开始编号,环内自入口从0开始编号。

二者第一次相遇,快指针走了2n12n_1步,慢指针走了n1n_1步,相遇即(2n1d)%c=(n1d)%c(2n_1 - d) \% c = (n_1 - d) \% c,即n1%c=0n_1 \% c = 0

此时将慢指针置回起点,二者同速各走n2=dn_2 = d步,慢指针在入口,快指针在(2n1+n2d)%c=2n1%c=0(2n_1 + n_2 - d) \% c = 2n_1 \% c = 0处,即二者在入口处相遇。

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
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (pHead == nullptr)
{
return nullptr;
}
else if (pHead->next == pHead)
{
return pHead;
}
else
{
ListNode *f = pHead, *s = pHead;
while (f == pHead || f != s)
{
s = s->next;
f = f->next;
if (f == nullptr)
{
return nullptr;
}
else
{
f = f->next;
}
if (f == nullptr || s == nullptr)
{
return nullptr;
}
}
s = pHead;
while (f != s)
{
f = f->next;
s = s->next;
}
return f;
}
}
};