LeetCode-118-119-121-141-155

发表于   |   分类于

118 Pascal’s Triangle，119 Pascal’s Triangle II，121 Best Time to Buy and Sell Stock，141 Linked List Cycle，155 Min Stack 均较为简单，合并完成解题报告。

118 Pascal’s Triangle

概述

帕斯卡三角绘制。

分析

所谓帕斯卡三角，也叫做杨辉三角（也是贾宪三角……），解释可以在维基百科上得知。

那么只需按照定义，逐层生成即可。

解法

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
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (numRows <= 0) {
            return result;
        }

        List<Integer> prev = null;

        for (int i = 1; i <= numRows; ++i) {
            List<Integer> now = new ArrayList<Integer>();
            now.add(1);

            if (prev == null) {
                result.add(now);
                prev = now;
                continue;
            }

            for (int j = 0 ; j < prev.size() - 1; ++j) {
                now.add(prev.get(j) + prev.get(j + 1));
            }

            now.add(1);
            result.add(now);
            prev = now;
        }

        return result;
    }
}

119 Pascal’s Triangle II

概述

只绘制杨辉三角的某行。

分析

属于118 Pascal’s Triangle的扩展题目，可以考虑直接复用118的代码，生成后返回。

问题在于时间复杂度过高。后续可以优化。

解法

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
public class Solution {
    public List<Integer> getRow(int rowIndex) {
        return this.generate(rowIndex + 1).get(rowIndex);
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (numRows <= 0) {
            return result;
        }

        List<Integer> prev = null;

        for (int i = 1; i <= numRows; ++i) {
            List<Integer> now = new ArrayList<Integer>();
            now.add(1);

            if (prev == null) {
                result.add(now);
                prev = now;
                continue;
            }

            for (int j = 0 ; j < prev.size() - 1; ++j) {
                now.add(prev.get(j) + prev.get(j + 1));
            }

            now.add(1);
            result.add(now);
            prev = now;
        }

        return result;
    }
}

121 Best Time to Buy and Sell Stock

概述

给出股价列表，找出最大的获利。

分析

可以想到，获利最大，即买入价最低，卖出价最高。

每个时间段都会有最高的卖出价，在数组中，一个区间的最大值是一定的。从后向前遍历，如果当前值不大于当前位置之后的最大值，那么当前值开始的最大值，仍然是当前值之后的最大值。反之则是当前值。

只需要针对价格，再次遍历数组，获得每个位置的数字的差值，即可知道在哪一位置时获利最大，即差值最大。

解法

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
public class Solution {
    public int maxProfit(int[] prices) {
        int[] maxNumbers = new int[prices.length];

        for (int i = prices.length - 1; i >= 0; --i) {
            if (i == prices.length - 1) {
                maxNumbers[i] = prices[i];
                continue;
            }

            if (prices[i] > maxNumbers[i + 1]) {
                maxNumbers[i] = prices[i];
                continue;
            }

            maxNumbers[i] = maxNumbers[i + 1];
        }

        int maxProfit = 0;

        for (int i = prices.length - 1; i >= 0; --i) {
            if (maxProfit < (maxNumbers[i] - prices[i])) {
                maxProfit = maxNumbers[i] - prices[i];
            }
        }

        return maxProfit;
    }
}

141 Linked List Cycle

概述

判断单向链表中是否存在环。

分析

简单的做法，用hash存储当前的节点指针值，如果再次遇到这一指针，说明有环。

但是目前还没有做出不需要额外空间的做法。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (null == head) {
            return false;
        }

        HashMap<Object, Integer> m = new HashMap<Object, Integer>();

        ListNode h = head;

        while (h != null) {
            if (m.containsKey(h)) {
                return true;
            }

            m.put(h, 1);
            h = h.next;
        }

        return false;
    }
}

155 Min Stack

概述

用单向链表实现一个可以直接获得最小值的栈。

分析

栈的特点是先进后出。

push 操作，可以看做是更换首节点的操作。同时，由于要直接获得最小值，可以入栈时判断是否比当前的最小值更小，由此可以完成更新操作。

pop 操作，可以看做是删除首节点的操作。同样的，如果pop的数值比小于等于最小值，需要遍历链表找到最小值。

如是，随时获得栈最小值的时间复杂度是O(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
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
public class MinStack {

    /** initialize your data structure here. */
    public class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }

    private boolean gotMin = false;
    private int minVal = Integer.MAX_VALUE;
    private ListNode stack = null;

    public MinStack() {

    }

    public void push(int x) {
        minVal = getMin();

        if (x <= minVal) {
            minVal = x;
        }

        ListNode n = new ListNode(x);
        n.next = stack;
        stack = n;
    }

    public void pop() {
        if (stack == null) {
            gotMin = false;
            minVal = Integer.MAX_VALUE;
            return;
        }

        if (gotMin && stack.val == minVal) {
            gotMin = false;
            minVal = Integer.MAX_VALUE;
        }

        if (stack.next == null) {
            stack = null;
            gotMin = false;
            minVal = Integer.MAX_VALUE;
            return;
        }

        stack = stack.next;
    }

    public int top() {
        if (stack == null) {
            return 0;
        }

        return stack.val;
    }

    public int getMin() {
        if (gotMin) {
            return minVal;
        }

        ListNode h = stack;

        while (h != null) {
            if (h.val <= minVal) {
                gotMin = true;
                minVal = h.val;
            }

            h = h.next;
        }

        return minVal;
    }
}

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