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 33 |
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 37 |
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 30 |
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 23 |
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 88 89 90 91 |
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(); */ ``` |