刷题记录

Analysis: A straight forward approach is to do with two-pass, first pass extract all the words, store in either array or stack. Second pass output. The one pass solution uses two pointers to keep track of the start of the word and end of the word by reserve scanning.   Since substring will be used, need to check s.charAt(start - 1), then we can use s.substring(start, end) to extract word. Solution: public class Solution { public String reverseWords(String s) { StringBuilder sb = new StringBuilder(); int end = s.length(); for (int start = s.length() - 1; start >= 0; start--) { if (s.charAt(start) == ' ') { end = start; } else if ( start == 0 || s.charAt(start - 1) == ' ') { if (sb.length() != 0) { sb.append(' '); } sb.append(s.substring(start, end)); } } return sb.toString(); } }

8/17/2018 update: 关于重复的问题。如果sum是其中一个数的2倍。下面这种方法存频率是因为已经把所有数都加入hashmap了。如果是边加 边判断则不需要保存频率，直接用hash set可以解决。 Analysis: The tricky part of this problem is that how to deal with duplicates. Use hashtable to store each number as key and the occurrence of the number as value. Inside find() method, iterate through the hashtable, find key target - currentValue .  If the key to find is equivalent to current value, make sure the current value exists more than twice or we get wrong answer. add() is O(1) , find is O(n), space is O(n). Solution: class TwoSum { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); /** Initialize your data structure here. */ public TwoSum() { } /** Add the number to an internal data structure.. */ public void add(int number) { int count = map.containsKey(number) ? map.get(number) : 0; map.put(number, ++count); } /** Find if there exists any pair of numbers which sum is equal to the v

3/20/2018 update: 这道题另外一种解法真是太难了。看不懂，性价比超低。 Analysis: Use array [14,14,14,9] as an example. Translate every number to binary, we can get: 1110 1110 1110 1001 ------- 4331 and sum up each position, we can get the result binary from %3 on each position. Solution: class Solution { public int singleNumber(int[] nums) { int[] A = new int[32]; int result = 0; for(int i = 0; i < 32; i++) { int count = 0; for(int j = 0; j < nums.length; j++) { // count nums[j] at position A[i] if(((nums[j] >> i) & 1) == 1) { count++; } } if(count > 0) { result |= (count%3) << i; } } return result; } }

Problem: Calculate the sum of two integers  a  and  b , but you are  not allowed  to use the operator  +  and  - . Example: Given  a  = 1 and  b  = 2, return 3. 3/22/2017 update: See example below: Use XOR, we can get the bits without carry, use & we can get carry before shift left by 1.  class Solution { public int getSum ( int a, int b) { while (b != 0 ) { int carry = a & b; a = a ^ b; b = carry << 1 ; } return a; } } Analysis : Shift a&b to left by 1 bit makes carry of a+b. a^b means a+b without considering carry. Solution: class Solution { public int getSum(int a, int b) { while (b!=0) { int _a = a ^ b; int _b = (a & b) << 1; a = _a; b = _b; } return a; } }

Problem: Given an unsorted array  nums , reorder it  in-place  such that  nums[0] <= nums[1] >= nums[2] <= nums[3]... . For example, given  nums = [3, 5, 2, 1, 6, 4] , one possible answer is  [1, 6, 2, 5, 3, 4] Analysis: 3/15/2018 update: If the index is odd, the number is peak. Otherwise, is valley. Loop through the array, if nums[i]  and nums[i - 1] violates the trend, swap them. How do we know that the above approach works. For instance If we reach index 3, we found that nums[3] < nums[2], we need to swap them. Before swapping, we know that nums[1] > nums[2] >nums[3]. We will swap a smaller number to left, still follow the wiggle trend. Solution: class Solution { public void wiggleSort ( int [] nums) { if (nums . length == 0 || nums == null) { return ; } for ( int i = 0 ; i < nums . length - 1 ; i ++ ) { if ((i % 2 == 0 && nums[i] > nums[i + 1 ]) ||

3/20/2018 update: In this problem we don't update next in hasNext(). hasNext just prepares next but not move the iterator to next. In the flatten next list iterator, hasNext() prepares for the stack, but next() is the one that actually pop the stack. 3/17/2018 update: need to consider peek() return null. Add throw exception. Analysis: Use Integer next to cache the to be peeked element. // Java Iterator interface reference: // https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html class PeekingIterator implements Iterator<Integer> { Integer next = null; Iterator<Integer> it = null; public PeekingIterator(Iterator<Integer> iterator) { // initialize any member here. it = iterator; if (it.hasNext()) { next = it.next(); } } // Returns the next element in the iteration without advancing the iterator. public Integer peek() { return next; }

Problem: Given two 1d vectors, implement an iterator to return their elements alternately. For example, given two 1d vectors: v1 = [1, 2] v2 = [3, 4, 5, 6] By calling  next  repeatedly until  hasNext  returns  false , the order of elements returned by  next  should be:  [1, 3, 2, 4, 5, 6] . Follow up : What if you are given  k  1d vectors? How well can your code be extended to such cases? Clarification for the follow up question -  Update (2015-09-18): The "Zigzag" order is not clearly defined and is ambiguous for  k > 2  cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input: [1,2,3] [4,5,6,7] [8,9] It should return  [1,4,8,2,5,9,3,6,7] . 4/11/2018 update: Remember to check the v1 or v2 is empty case. 3/19/2018 update: public class ZigzagIterator { Queue< Iterator< Integer > > queue; public ZigzagIterator ( List< Integer > v1,

Problem: Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling  next()  will return the next smallest number in the BST. Note:  next()  and  hasNext()  should run in average O(1) time and uses O( h ) memory, where  h  is the height of the tree. Analysis : 3/16/2018 update: Remember to check cur != null in hasNext(). Stack might be empty but we still have cur. public class BSTIterator { Stack< TreeNode > stack; TreeNode cur; public BSTIterator ( TreeNode root) { stack = new Stack<> (); cur = root; } /** @return whether we have a next smallest number */ public boolean hasNext () { return ! stack . isEmpty() || cur != null; } /** @return the next smallest number */ public int next () { while (cur != null) { stack . push(cur); cur = cur . left; } TreeNode temp = sta

Problem: Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Example 1: Given the list  [[1,1],2,[1,1]] , By calling  next  repeatedly until  hasNext  returns false, the order of elements returned by  next  should be:  [1,1,2,1,1] . Example 2: Given the list  [1,[4,[6]]] , By calling  next  repeatedly until  hasNext  returns false, the order of elements returned by  next  should be:  [1,4,6] . Analysis： 3/16/2018 update: Remember to call hasNext() in next() to make sure no error. public class NestedIterator implements Iterator< Integer > { Stack< NestedInteger > stack = new Stack<> (); public NestedIterator ( List< NestedInteger > nestedList) { pushToStack(nestedList); } @Override public Integer next () { return hasNext() ? stack . pop() . getInteger() : null; } @Ove

Problem: Implement an iterator to flatten a 2d vector. For example, Given 2d vector = [ [1,2], [3], [4,5,6] ] By calling  next  repeatedly until  hasNext  returns false, the order of elements returned by  next  should be:  [1,2,3,4,5,6] . 6/7/2018 update: In hasNext(), inner != null controls the corner case [] or inner.hasNext() is used, so inner should not be null. -------------------------------------------------------------------------------------------------------------------------------------------- 4/12/2018 update: We use while in hasNext() to cover the case like:[ [], [], [1,2,3] ]. We should return null if user calls next() directly without calling hasNext() first when there is nothing left.  为什么要在hasNext里面准备inner iterator？ 因为在判断hasNext()的时候，如果inner为空或者没有下一个，我们会去更新inner，这样自然而然就需要在hasNext准备下一个inner。 Analysis: Use 2 iterators, 1 is on Integer level (j) the other is on List level (i). Once j reaches the end, then update j from i.next(). Code is as fol

kth largest number 问题： heap, quicksort Flatten list问题： 用栈 Reverse 问题: 先reverse局部再整体      需要巩固括号和array, string

思路： 弱智题，体力活。lintcode居然识别不出map.KeySet().

思路： 有多种解法，最有价值的就是用heap和分治法。 解法一： heap 把所有listnode放到heap里面。然后挨个从heap里面取，这样可以保证每次取的都是最小值。连到result list上。如果heap.poll().next != null，把heap.poll().next放进heap里面。 代码如下： /** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param lists: a list of ListNode * @return: The head of one sorted list. */ public ListNode mergeKLists(List<ListNode> lists) { // write your code here if(lists.size() == 0 || lists == null ) { return null; } Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>() { public int compare(ListNode a, ListNode b) { return a.val - b.val; } }); // initialize heap for(ListNode n: lists) { if(n !

11/15/2017 更新 保持top k不需要判断新来的数和heap.peek()的大小。新add数先无脑加进heap，然后判断heap.size() > k ? poll() : return; public void add(int num) { // write your code here minHeap.add(num); if(minHeap.size() > count) { minHeap.poll(); } } ----------------------------------------------------------------------------------------- 思路： 用minheap在维持前k大的数，如果加进来的大于heap顶端那么replace。 实现： Priorityqueue的iterator要留意一下。 Iterator it = minHeap.iterator(); 这道题主要用到iterator的hasNext(), next方法。 还有就是Collections.sort(Collection, direction)。 代码如下： public class Solution { /* * @param k: An integer */ private Queue<Integer> minHeap = new PriorityQueue<>(); private int count = 0; public Solution(int k) { // do intialization if necessary count = k; } /* * @param num: Number to be added * @return: nothing */ public void add(int num) { // write your code here

思路： 这是leetcode hard的难度。利用hashset的离散属性，可以在O(n)的时间下完成。 1. 把所有数加到hashset里面。 2. 遍历数组，找到sub sequence的起始点，也就是!set.contains(n-1)。然后再看比它大1的数在不在set里面，更新current longest count。 代码如下： public class Solution { /* * @param num: A list of integers * @return: An integer */ public int longestConsecutive(int[] num) { // write your code here if(num == null || num.length == 0) return 0; int longest = 0; Set<Integer> set = new HashSet<>(); // add each number to set for(int n: num) { set.add(n); } for(int n: num) { if(!set.contains(n-1)) { int current = 1; while(set.contains(++n)) { current++; } longest = Math.max(longest, current); } } return longest; } }

思路： 方法一： 建一个hashtable, HashMap<String, List<String>>。逐个扫描strs，然后sort, 思路显而易见。 时间复杂度是O(nklogk)。k: length of longest string in strs. 方法二： 把string 转化成int[26], 记录每一个字符的个数：count[c - 'a']。然后再把count[26]转化成统一格式的string: "#0#0#0#0....."  #eachcount,一个26个。目的和sort一样的，如果是anagram转化完成后会相等，只不过时间复杂度变成了O(nk)。 代码如下： public class Solution { /* * @param strs: A list of strings * @return: A list of strings */ public List<String> anagrams(String[] strs) { // write your code here List<String> res = new ArrayList<>(); if(strs.length == 0|| strs == null) { return res; } Map<String, ArrayList<String>> map = new HashMap<>(); int[] count = new int[26]; for(String s: strs) { Arrays.fill(count, 0); for(char c: s.toCharArray()) { count[c - 'a']++; } StringBuilder sb = new StringBuilder("");

Problem: Design and implement a data structure for  Least Recently Used (LRU) cache . It should support the following operations:  get  and  put . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in  O(1)  time complexity? Example: LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4 4/11/2018 update: Use doubly linked list. Insert the most recently used node to head. So what's befor

思路： 虽然是简单题，但是也没有想出来。同向双指针，一个遍历，另一个指向非重复的数。 代码如下： public class Solution { /* * @param nums: an array of integers * @return: the number of unique integers */ public int deduplication(int[] nums) { // write your code here if(nums == null || nums.length == 0) return 0; Arrays.sort(nums); int index = 0; for(int i = 0; i < nums.length; i++) { if(nums[index] != nums[i]) { nums[++index] = nums[i]; } } return index + 1; } }

思路： 才有quicksort的思想，先求出一个midcolor =(1+k)/2。把小于等于mid放左边，大于mid放右边。然后再分解。 实现： 代码如下： public class Solution { /* * @param colors: A list of integer * @param k: An integer * @return: nothing */ public void sortColors2(int[] colors, int k) { // write your code here rainbowSort(colors, 0, colors.length - 1, 1, k); } private void rainbowSort(int[] colors, int left, int right, int fromColor, int toColor) { if(fromColor == toColor) return; if(left >= right) return; int midColor = (fromColor + toColor) / 2; int index = left; for(int i = left; i <= right; i++) { if(colors[i] <= midColor) { swap(colors, i, index++); } } rainbowSort(colors, left, index - 1, fromColor, midColor); rainbowSort(colors, index, right, midColor + 1, toColor); }

2/21/2018 update nums[i]等于2的时候不+1是因为如果换回来的是0，则需要再检查一遍。循环满足条件是i <= r，因为最后一个数也需要检查。 思路： 3个指针，left: left左边为0， right: 右边为2， i:遍历数组的指针。代码如下： public class Solution { /* * @param nums: A list of integer which is 0, 1 or 2 * @return: nothing */ public void sortColors(int[] nums) { // write your code here int left = 0, right = nums.length -1, i = 0; while(i <= right) { if(nums[i] == 0) { swap(nums, i++, left++); } else if(nums[i] == 1) { i++; } else { swap(nums, i, right--); } } } private void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } 为什么等于0时i++，等于2是不变。因为数组是从左到右遍历的，可以保证i的左边都是sorted order。

思路： 用quicksort partition的思路，直接返回storedIndex就好了。代码如下 public class Solution { /* * @param nums: The integer array you should partition * @param k: An integer * @return: The index after partition */ public int partitionArray(int[] nums, int k) { // write your code here if(nums == null || nums.length == 0) return nums.length; int res = 0; for(int i = 0; i < nums.length;i++) { if(nums[i] < k) { int temp = nums[i]; nums[i] = nums[res]; nums[res] = temp; res++; } } return res; } }

思路： find kth smallest 马甲，直接找nums.length - k + 1 小的。

2/20/2018 update 在quick selcct里面判断start > end没有必要。因为如果start > end，那么partition里面什么都不会干。 if (pivotIndex == k  - 1) so that all numbers before pivotIndex is smaller than nums[PI]. class Solution { public int findKthLargest ( int [] nums, int k) { return quickSelect(nums, 0 , nums . length, k); } private int quickSelect ( int [] nums, int start, int end, int k) { int pivotIndex = partition(nums, start, end); if (pivotIndex == k - 1 ) { return nums[pivotIndex]; } else if (pivotIndex < k - 1 ) { return quickSelect(nums, pivotIndex + 1 , nums . length, k); } else { return quickSelect(nums, start, pivotIndex, k); } } private void swap ( int [] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } private int partition ( int [] nums, int start, int end) { int pivot

思路： 在partition的时候，可以只用一个指针。详见：https://visualgo.net/en/sorting 代码如下： public class Solution { /* * @param A: an integer array * @return: */ public void sortIntegers(int[] A) { // write your code here quickSort(A, 0, A.length - 1); } private void quickSort(int[] A, int start, int end) { if(start < end) { int pivot = partition(A, start, end); // since A[pivot] is at sorted poisition, exclude pivot. quickSort(A, start, pivot - 1); quickSort(A, pivot + 1, end); } } private int partition(int[] A, int start, int end) { int pivotValue = A[start]; int storeIndex = start + 1; for(int i = start + 1; i <= end; i++) { // put value less then pivotValue to left if(A[i] < pivotValue) { swap(A, storeIndex++, i); } } // place the pivot in the middle swap(A, start, storeIndex - 1); // ret