详解九章算法：九章算法题解记录【八】常用数据结构

主要有以下常用数据结构
线性：堆 栈 hash
非线性 Heap Trie树

Queue & Stack
1 Min-Stack http://www.lintcode.com/en/problem/min-stack/

public class MinStack { Stack<Integer> stack = new Stack<>(); Stack<Integer> minstack = new Stack<>(); public MinStack() { } /* * @param number: An integer * @return: nothing */ public void push(int number) { if (stack.isEmpty()){ stack.push(number); minstack.push(number); } else { stack.push(number); int min = minstack.peek(); minstack.push(Math.min(min, number)); } } /* * @return: An integer */ public int pop() { if (stack.isEmpty()) { return 0; } minstack.pop(); return stack.pop(); } /* * @return: An integer */ public int min() { return minstack.peek(); }}

剑指offer原题

2 Implement a queue by two stacks http://www.lintcode.com/en/problem/implement-queue-by-two-stacks/

public class MyQueue { Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); public MyQueue() { // do intialization if necessary } /* * @param element: An integer * @return: nothing */ public void push(int element) { while (!stack2.isEmpty()){ stack1.push(stack2.pop()); } stack1.push(element); // write your code here } /* * @return: An integer */ public int pop() { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.pop(); // write your code here } /* * @return: An integer */ public int top() { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.peek(); // write your code here }}

第一遍没AC，因为小看了这题，把while错写为if

3 Largest Rectangle in histogram http://www.lintcode.com/en/problem/largest-rectangle-in-histogram

public class Solution { public int largestRectangleArea(int[] height) { if (height == null || height.length == 0) { return 0; } Stack<Integer> stack = new Stack<Integer>(); //维护单调递增 int max = 0; for (int i = 0; i <= height.length; i++) { int curt = (i == height.length) ? -1 : height[i]; while (!stack.isEmpty() && curt <= height[stack.peek()]) { //如果栈顶高度大于当前高度 int h = height[stack.pop()];//保存栈顶元素信息 int w = stack.isEmpty() ? i : i - stack.peek() - 1;//如果栈已经为空，宽度为i，否则i-s.top()-1 max = Math.max(max, h * w); } stack.push(i);//压入栈中 } return max; }}

这个题是单调栈的运用，使用一个单调递增栈来维护已经出现了的矩形高度，如果后面新来的元素高度比栈里最后的元素高，那么需要入栈，因为面积最大的元素会出现在后面。如果后面新来的元素高度比栈里的最后的元素小，那么需要弹出栈里的元素，并且，每次弹出的时候都要对计算目前的宽度，相乘得到面积。
四个技巧：

我们只需要在辅助栈保存矩形的右边界坐标即可，不需要保存高度，因为可以通过右边界坐标得到（height[i] ），也不需要保存左边界坐标，因为上一个矩形的右边界坐标+1就是当前矩形的左边界。

在直方图最后添加一个高度为0的虚拟矩形条，这样保证一次遍历之后栈里面的矩形都被正确处理过了，否则需要再重复一遍。

有一个需要认识的点在于，假如height[i - 1] < height[i] 那么i之后的长条以i为左边界的面积一定大于以i之前的元素做左边界。所以遇到一个比他小的元素就可以停止。

先pop出大或者等于的元素，再寻求用peek找他的左坐标

4 Max Tree http://www.lintcode.com/en/problem/max-tree/
待做，hard

Hash

1 Rehashing http://www.lintcode.com/en/problem/rehashing/

public class Solution { /** * @param hashTable: A list of The first node of linked list * @return: A list of The first node of linked list which have twice size */ public ListNode[] rehashing(ListNode[] hashTable) { if (hashTable == null) { return null; } int length = hashTable.length * 2; ListNode[] result = new ListNode[length]; if (length == 0) { return result; } for (ListNode node : hashTable) { while (node != null) { int hash = rehash(node.val, length); ListNode nownode = new ListNode(node.val); if (result[hash] == null) { result[hash] = nownode; } else { ListNode head = result[hash]; while (head.next != null) { head = head.next; } head.next = nownode; } node = node.next; } } return result; } private int rehash(int val, int length){ return val >= 0 ? (val % length) : (val % length + length) % length; }}

解题思路：模仿HashMap的rehash函数，需要遍历ListNode数组中的每一个元素，同时对每一个元素进行遍历。Foreach内套while node!=null

2 LRU Cache http://www.lintcode.com/zh-cn/problem/lru-cache/
用HashMap + LinkedList来实现

public class LRUCache { class LRUNode { // 链表节点 LRUNode pre; LRUNode next; int key; int val; LRUNode(int key, int val){ this.key = key; this.val = val; } } private int capacity; private LRUNode head = new LRUNode(-1, -1); private LRUNode tail = new LRUNode(-1, -1); // private int nowCapacity; 用lrucached.size()来求 private HashMap<Integer, LRUNode> lruCached = new HashMap<>(); public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.pre = head; } /* * @param key: An integer * @return: An integer */ public int get(int key) { if (lruCached.containsKey(key)) { LRUNode node = lruCached.get(key); node.pre.next = node.next; node.next.pre = node.pre; lruCached.put(node.key, node); MoveToFirst(key); return lruCached.get(key).val; } else { return -1; } } /* * @param key: An integer * @param value: An integer * @return: nothing */ public void set(int key, int value) { if (lruCached.containsKey(key)) { LRUNode node = lruCached.get(key); node.val = value; lruCached.put(key, node); node.pre.next = node.next; node.next.pre = node.pre; MoveToFirst(key); } else { if (lruCached.size() + 1 > capacity) { RemoveLast(); } LRUNode node = new LRUNode(key, value); lruCached.put(key, node); MoveToFirst(key); } } private void MoveToFirst(int key) { LRUNode node = lruCached.get(key); node.next = head.next; head.next = node; node.next.pre = node; node.pre = head; } private void RemoveLast() { if (lruCached.size() == 0){ return; } else { lruCached.remove(tail.pre.key); tail.pre = tail.pre.pre; tail.pre.next = tail; } }}

调了半天，参考答案 HashMap<key, Node> node中包含pre next key value 总体cache中包含head与tail
trick：开始时置head = New Node(-1, -1) tail = new Node(-1, -1) head.next = tail tail.pre = head 可有效避免if判断。
值得再刷。

3 Longest Consecutive Sequence http://www.lintcode.com/zh-cn/problem/longest-consecutive-sequence/

public class Solution { /** * @param num: A list of integers * @return: An integer */ public int longestConsecutive(int[] num) { // 用一个set来存放元素，污染法找上下界max HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < num.length; i++) { set.add(num[i]); } int max = 0; for (int i = 0; i < num.length; i++) { int l = num[i], r = num[i]; while (set.contains(l - 1)) { l-- ; set.remove(l); } while (set.contains(r + 1)){ r++; set.remove(r); } max = Math.max(max, r - l + 1); } return max; }}

用增强for来取set内元素容易出错。

4 Subarray sum http://www.lintcode.com/en/problem/subarray-sum/

public class Solution { /** * @param nums: A list of integers * @return: A list of integers includes the index of the first number and the index of the last number */ public ArrayList<Integer> subarraySum(int[] nums) { // write your code here int len = nums.length; ArrayList<Integer> ans = new ArrayList<Integer>(); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(0, -1); int sum = 0; for (int i = 0; i < len; i++) { sum += nums[i]; if (map.containsKey(sum)) { ans.add(map.get(sum) + 1); ans.add(i); return ans; } map.put(sum, i); } return ans; }}

解题思路：将区间[i, j]的和为0 转化成 [0,i] [0,j - 1]差为0只要在map里保留[0,k]的和，遍历一次即可。

5 anagrams http://www.lintcode.com/en/problem/anagrams/

public class Solution { /** * @param strs: A list of strings * @return: A list of strings */ public List<String> anagrams(String[] strs) { List<String> result = new ArrayList<String>(); if (strs == null || strs.length == 0) { return result; } Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>(); for (int i = 0; i < strs.length; i++) { char[] arr = strs[i].toCharArray(); Arrays.sort(arr); String s = String.valueOf(arr); if (!map.containsKey(s)) { ArrayList<String> list = new ArrayList<String>(); map.put(s, list); } map.get(s).add(strs[i]); } for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) { if (entry.getValue().size() >= 2) { result.addAll(entry.getValue()); } } return result; }}

使用一个map<Stringsort后的第一个字典序，原String的list>
遍历map，当value.size >= 2时，将value加入结果集中。 学会了好多IDEA补全。不亏。

Heap增删logn
1 Median Number http://www.lintcode.com/en/problem/data-stream-median/

public class Solution { /** * @param nums: A list of integers * @return: the median of numbers */ public int[] medianII(int[] nums) { if (nums == null) { return null; } int count = nums.length; PriorityQueue<Integer> minHeap = new PriorityQueue<>(count); PriorityQueue<Integer> maxHeap = new PriorityQueue<>(count, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); int[] result = new int[count]; for (int i = 0; i < nums.length; i++) { maxHeap.add(nums[i]); if (i % 2 == 1) { minHeap.add(maxHeap.poll()); } else { if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) { int maxroot = maxHeap.poll(); int minroot = minHeap.poll(); maxHeap.add(minroot); minHeap.add(maxroot); } } result[i] = maxHeap.peek(); } return result; }}

解题思路：这里的中位数定义为A[n/2 - 1]，使用两个堆保存，放入minHeap的元素是maxHeap的最大元素（add + poll），放入maxHeap的元素假如大于minHeap堆顶，则交换。这样保证了maxHeap堆顶一直是中位数。

2 heapify http://www.lintcode.com/en/problem/heapify/

public class Solution { /* * @param A: Given an integer array * @return: nothing */ public void heapify(int[] A) { if (A == null || A.length == 0) { return; } for (int i = (A.length - 1) / 2; i >= 0; i--) { // 从一半处开始，因为最底层必无孩子，不需要交换 siftDown(A, i); } } private void siftDown(int[] A, int startIndex){ while (left(startIndex) < A.length) { // 保证有孩子，无子则退出 int smallest = startIndex; if (left(startIndex) < A.length && A[startIndex] > A[left(startIndex)]) { smallest = left(startIndex); } if (right(startIndex) < A.length && A[smallest] > A[right(startIndex)]) { smallest = right(startIndex); } if (smallest == startIndex) { return; } swap(A, startIndex, smallest); startIndex = smallest; } } private int left(int index) { return 2 * index + 1; } private int right(int index) { return 2 * index + 2; } private void swap(int[] A, int a, int b) { // 交换 int temp = A[a]; A[a] = A[b]; A[b] = temp; }}

实际上是建最小堆的过程，趁机复习一下堆排。

public class HeapSort { public void heapsort(int[] A) { if (A == null || A.length == 0) { return; } // 建最小堆 for (int i = (A.length - 1) / 2; i >= 0; i--) { siftDown(A, i, A.length); } for (int i = 0; i < A.length; i++) { System.out.print("A[i] = " + A[i] + " "); } System.out.println("已调整为大根堆"); int size = A.length; while (size > 0) { swap(A, 0, --size); siftDown(A, 0, size); } } private void siftDown(int[] A, int startIndex, int endIndex){ while (left(startIndex) < endIndex) { // 保证有孩子，无子则退出 int largest = startIndex; if (left(startIndex) < endIndex && A[startIndex] < A[left(startIndex)]) { largest = left(startIndex); } if (right(startIndex) < endIndex && A[largest] < A[right(startIndex)]) { largest = right(startIndex); } if (largest == startIndex) { return; } swap(A, startIndex, largest); startIndex = largest; } } private int left(int index) { return 2 * index + 1; } private int right(int index) { return 2 * index + 2; } private void swap(int[] A, int a, int b) { // 交换 int temp = A[a]; A[a] = A[b]; A[b] = temp; }}

建堆和调整都用了siftDown函数，堆排序要先调整为大根堆（为了复用），再交换排序。

顺手再写个快排

public class QuickSort { public void quicksort(int[] nums) { if (nums == null || nums.length < 2) { return; } quick(nums, 0, nums.length - 1); } public void quick(int[] nums, int start, int end) { if (start < end) { int[] p = partition(nums, start, end); quick(nums, start, p[0]); quick(nums, p[1], end); } } public int[] partition(int[] A, int start, int end) { int rand = start + (int)(Math.random() * (end - start)); swap(A, rand, end); int less = start - 1; int more = end; while (start < more) { if (A[start] < A[end]) { swap(A, ++less, start++); } else if(A[start] == A[end]) { start++; } else { swap(A, start, --more); } } swap(A, end, more); return new int[]{less, more + 1}; } public void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}

也debug了半天，需要再练，结合例子。注意点：
less = start-1
–more ++less
最后的swap more end
返回{less, more + 1}

3 Merge k sorted lists http://www.lintcode.com/en/problem/merge-k-sorted-lists/

private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() { public int compare(ListNode left, ListNode right) { return left.val - right.val; } }; public ListNode mergeKLists(List<ListNode> lists) { if (lists == null || lists.size() == 0) { return null; } Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator); for (int i = 0; i < lists.size(); i++) { if (lists.get(i) != null) { heap.add(lists.get(i)); } } ListNode dummy = new ListNode(0); ListNode tail = dummy; while (!heap.isEmpty()) { ListNode head = heap.poll(); tail.next = head; tail = head; if (head.next != null) { heap.add(head.next); } } return dummy.next; }

Trie树
1 Word Search II http://www.lintcode.com/en/problem/word-search-ii/

package Jiuzhang.DataStruture;import java.util.ArrayList;import java.util.HashMap;import java.util.List;public class WordSearchII { public int[] dx = {1, 0, -1, 0}; //搜索方向 public int[] dy = {0, 1, 0, -1}; public List<String> wordSearchII(char[][] board, List<String> words) { List<String> results = new ArrayList<String>(); TrieTree tree = new TrieTree(new TrieNode()); for (String word : words){ tree.insert(word); } for (int i = 0; i < board.length; i++) {//遍历字母矩阵，将每个字母作为单词首字母开始搜索 for (int j = 0; j < board[i].length; j++) { search(board, i, j, tree.root, results); } } return results; } public void search(char[][] board,//在字典树上dfs查找 int x, int y, TrieNode root, List<String> results) { if (!root.children.containsKey(board[x][y])) { return; } TrieNode child = root.children.get(board[x][y]); if (child.word != null) { //如果访问到字典树叶子，将字符串压入result即可 if (!results.contains(child.word)) { results.add(child.word); } } char tmp = board[x][y]; board[x][y] = 0; // mark board[x][y] as used for (int i = 0; i < 4; i++) { //向四个方向dfs搜索 if (!isValid(board, x + dx[i], y + dy[i])) { continue; } search(board, x + dx[i], y + dy[i], child, results); } board[x][y] = tmp; // revert the mark } private boolean isValid(char[][] board, int x, int y) { //检测搜索位置合法 if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) { return false; } return board[x][y] != 0; }}class TrieNode { String word; HashMap<Character, TrieNode> children; public TrieNode() { word = null; children = new HashMap<Character, TrieNode>(); }}class TrieTree { TrieNode root; public TrieTree(TrieNode trieNode) { root = trieNode; } public void insert(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { if (!node.children.containsKey(word.charAt(i))) { node.children.put(word.charAt(i), new TrieNode()); } node = node.children.get(word.charAt(i)); } node.word = word; }}

Trie树插入，word字段用来表示结束。
四向搜索，搜索过的点置为0，递归。