Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In Valine:

链表反转-题目描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。
样例
输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

Read more »

Posted on Edited on In Valine:

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

样例
输入：[2, 3, 5]
返回：[5, 3, 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> r;
        while (head) {
            r.push_back(head->val);
            head = head->next;
        }
        return vector<int>(r.rbegin(), r.rend()); 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;

    void reverse(ListNode* head) {
        if (!head) return;
        reverse(head->next);
        res.push_back(head->val);
    }

    vector<int> reversePrint(ListNode* head) {
        reverse(head);
        return res;
    }
};

Posted on Edited on In , Valine:

链表环入口-题目描述

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

样例
QQ截图20181202023846.png

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

Read more »

Posted on Edited on In , Valine:

二叉树子结构-题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。

我们规定空树不是任何树的子结构。

样例
树A：

 8
/ \

8 7
/ \
9 2
/ \
4 7
树B：

8
/ \
9 2
返回 true ,因为B是A的子结构。

Read more »

Posted on Edited on In , Valine:

判断二叉树是否对称-题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。

如果一棵二叉树和它的镜像一样，那么它是对称的。

样例
如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树：
1
/ \
2 2
/ \ / \
3 4 4 3

如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树：
1
/ \
2 2
\ / \
4 4 3

Read more »

Posted on Edited on In , Valine:

二叉树镜像-题目描述

输入一个二叉树，将它变换为它的镜像。

样例
输入树：
8
/ \
6 10
/ \ / \
5 7 9 11

[8,6,10,5,7,9,11,null,null,null,null,null,null,null,null]
输出树：
8
/ \
10 6
/ \ / \
11 9 7 5

[8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]

Read more »

Posted on Edited on In Valine:

支持min操作的栈-题目描述

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
样例
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin(); —> Returns -4.
minStack.pop();
minStack.top(); —> Returns 3.
minStack.getMin(); —> Returns -1.

支持min操作的栈-总体思路

空间换时间，用另外一个stack去储存最小值。

另外，如果要求额外存储空间控制在$O(1)$呢？

思路：

  1. 用一个数字来存储当前最小值
  2. 栈中存差值，确保可以根据栈中存的值 与 最小值，能够还原出 原始值。

如果新来的元素NewCome，比之前的最小值oldMin更小；oldMin存的就是当前元素了； 现在的问题变成“当当前元素被pop出之后，如何计算出新的最小值）？” 新存入的diff = newMin - oldMin; oldMin = newMin - diff ; 因为diff小于0，所以oldMin更大；

  1. 当发生pop时，能够计算得出新的最小值

支持min操作的栈-代码实现

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class MinStack {
public:
    stack<int> ms;
    stack<int> hs;
    
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        ms.push(x);
        if (hs.empty()) hs.push(x);
        else hs.push(min(x, hs.top()));
    }
    
    void pop() {
        ms.pop();
        hs.pop();
    }
    
    int top() {
        return ms.top();
    }
    
    int getMin() {
        return hs.top();
    }

    //O(1)额外空间的解法【注意：下面的代码有错误！调试未通过！】
  stack<int> diff;
    int minE;

    void push(int value) {
        if (diff.empty()) {
            minE = value;
            diff.push(0);
            return;
        }

        if (minE <= value) {
            diff.push(value - minE);
            return;
        }
        else { //进入了一个更小的元素
            diff.push(value - minE); 
            minE = value;
        }
    }

    void pop() {
        int t = diff.top();
        diff.pop();
        if (t < 0) { //更新最小值
            minE = minE - t;
        }
    }

    int top() {
        int t = diff.top();
         if (t >= 0) {
             return t + minE;
         } else {
             return minE;
         }
    }

    int min() {
        return minE;
    }

     //O(1)额外空间的解法【注意：下面的代码可能有错误！调试未通过！】

    stack<int> diffs;
    int m = MAX_INT;

    void push(int x) {

        if (diffs.empty()) {
            m = x;
            diffs.push(0);
            return;
        }

        diffs.push(m - x);
        if (x > m) {
            m = x;
        }
    }
    
    void pop() { 
        int s = diffs.top();
        if  (s < 0) {
           m = m + s; //更新max
        } 
        diffs.pop();
    }
    
    int top() {
        int s = diffs.top();
        return m - s;
    }
    
    int getMax() {
        return m;
    }

};

/**
 * 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.getMin();
 */