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步，相遇即(2n1−d)%c=(n1−d)%c(2n_1 - d) \% c = (n_1 - d) \% c，即n1%c=0n_1 \% c = 0。

此时将慢指针置回起点，二者同速各走n2=dn_2 = d步，慢指针在入口，快指针在(2n1+n2−d)%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;
        }
    }
};