刷题记录

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 t...

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 &...

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...