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

概述

帕斯卡三角绘制。

分析

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

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

解法

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的代码，生成后返回。

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

解法

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

概述

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

分析

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

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

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

解法

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存储当前的节点指针值，如果再次遇到这一指针，说明有环。

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

解法

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)。

解法

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