Flatten Nested List Iterator

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.

典型的stack，但是在什么情况下pop出元素要考虑清楚

public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack = new Stack<NestedInteger>();
    public NestedIterator(List<NestedInteger> nestedList) {
        if (nestedList != null) {
            for (int i = nestedList.size()-1; i>= 0; i--) {
                stack.push(nestedList.get(i));
            }
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (!stack.peek().isInteger()) {
                pushFronBackToFront(stack, stack.pop());
            } else {
                return true;
            }
        }
        return false;
    }
    
    private void pushFronBackToFront(Stack<NestedInteger> stack, NestedInteger val) {
        if (val.isInteger()) {
            stack.push(val);
        } else {
            for (int i = val.getList().size()-1; i>= 0; i--) {
                stack.push(val.getList().get(i));
            }
        }
    }
}

Reverse String

Write a function that takes a string as input and returns the string reversed.

Two pointers.简单题

public class Solution {
    public String reverseString(String s) {
        int start = 0, end = s.length() - 1;
        StringBuilder builder = new StringBuilder(s);
        while (start < end) {
            char a = builder.charAt(start);
            builder.setCharAt(start, builder.charAt(end));
            builder.setCharAt(end, a);
            start++;
            end--;
        }
        return builder.toString();
    }
}

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

简单题

public class Solution {
    public String reverseVowels(String s) {
        int start = 0, end = s.length() - 1;
        StringBuilder builder = new StringBuilder(s);
        while (start < end) {
            while (start < end && !"aeiouAEIOU".contains(s.substring(start, start+1))) {
                start++;
            }
            while (start < end && !"aeiouAEIOU".contains(s.substring(end, end+1))) {
                end--;
            }
            char a = builder.charAt(start);
            builder.setCharAt(start, builder.charAt(end));
            builder.setCharAt(end, a);
            start++;
            end--;
        }
        return builder.toString();
    }
}

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
这种解法用到了bucket sort，统计出各个数字出现的次数，再将其加入到对应count的bucket中，最后从后向前便利bucket。
另外可以用heap做，复杂度比这种解法高。

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> valToCount = new HashMap<Integer, Integer>();
        for (int num : nums) {
            valToCount.put(num, valToCount.getOrDefault(num, 0) + 1);
        }
        
        int bucketNumber = 0;
        for (int count : valToCount.values()) {
            bucketNumber = Math.max(bucketNumber, count);
        }
        ArrayList<Integer>[] buckets = (ArrayList<Integer>[]) new ArrayList[bucketNumber];
        for (Map.Entry<Integer, Integer> entry : valToCount.entrySet()) {
            int index = entry.getValue()-1;
            if (buckets[index] == null) {
                buckets[index] = new ArrayList<Integer>();
            }
            buckets[index].add(entry.getKey());
        }
        List<Integer> result = new ArrayList<Integer>();
        for (int i = bucketNumber - 1; i >= 0; i --) {
            if (buckets[i] != null) {
                for (int j = 0; j < buckets[i].size(); j++) {
                    if (k == 0) {
                        break;
                    }
                    k--;
                    result.add(buckets[i].get(j));
                }
            }
        }
        return result;
    }
}

Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

简单题

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        for (int num : nums1) {
            set1.add(num);
        }
        Set<Integer> resultSet = new HashSet<Integer>();
        for (int num : nums2) {
            if (set1.contains(num)) {
                resultSet.add(num);
            }
        }
        int[] result = new int[resultSet.size()];
        int i = 0;
        for (int val : resultSet) {
            result[i] = val;
            i++;
        }
        return result;
    }
}

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

简单题

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> numToCount1 = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            numToCount1.put(num, numToCount1.getOrDefault(num, 0) + 1);
        }
        Map<Integer, Integer> resultMap = new HashMap<Integer, Integer>();
        List<Integer> resultList = new ArrayList<Integer>();
        for (int num : nums2) {
            if (resultMap.getOrDefault(num, 0) < numToCount1.getOrDefault(num, 0)) {
                resultMap.put(num, resultMap.getOrDefault(num, 0) + 1);
                resultList.add(num);
            }
        }
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}

Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
将string用count不足k的字符分段，递归完成。

public class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> charToCount = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            charToCount.put(c, charToCount.containsKey(c) ? charToCount.get(c) + 1 : 1);
        }
        boolean complete = true;
        for (Map.Entry<Character, Integer> entry :charToCount.entrySet()) {
            if (entry.getValue() < k) {
                complete = false;
                break;
            }
        }
        if (complete) {
            return s.length();
        }
        int prev = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (charToCount.get(c) < k) {
                max = Math.max(max, longestSubstring(s.substring(prev, i), k));
                prev = i + 1;
            }
        }
        return Math.max(max, longestSubstring(s.substring(prev, s.length()), k));
    }
}

Rotate Function

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).
观察一下规律不难发现f(n) = f(n-1) + arraySum – arrayLength*A[i-1]

public class Solution {
    public int maxRotateFunction(int[] A) {
        int oneRoundSum = 0;
        int max = 0;
        for (int i = 0; i <A> 0; i--) {
            int cur = prev + oneRoundSum - A.length * A[i];
            max = Math.max(max, cur);
            prev = cur;
        }
        return max;
    }
}

Integer Replacement

Given a positive integer n and you can do operations as follow:

If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n – 1.
What is the minimum number of replacements needed for n to become 1?
关键点在于当n是基数时，如果倒数第二位是0， 那么减1， 否则加1
另外一定使用>>>而不是>>, >>>会在前面补0，当n为max时，补完零是负数，因此while条件是n!=1， 而不是n > 1.

public class Solution {
    public int integerReplacement(int n) {
        int result = 0;
        while (n != 1) {// n > 1 won't work for max value, as n >>>= 1 will be negative
            if (n == 3) {
                return result + 2;
            }
            if ((n & 1) != 0) {
                if (((n >>> 1) & 1) == 0) {
                    n--;
                } else {
                    n++;
                }
            } else {
                n >>>= 1;
            }
            result++;
        }
        return result;
    }
}

Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
解法：
对于每一个word， 拆分成前后两部分， 如果其中任意一部分本身是palindrome， 查看另一部分的reverse是否存在。 存在即可连接成为palindrome。
需要注意的是如果有word为空，因为会跳过最内层for循环，因此要单独处理。

public class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Map<String, Integer> wordToIndex = new HashMap<String, Integer>();;
    for (int i = 0; i < words.length; i++) {
      wordToIndex.put(words[i], i);
    }
    for (int i = 0; i < words.length; i++) {
      String word = words[i];
      if (word.length() == 0) {
        for (int j = 0; j < words.length; j++) {
          if (isPalindrome(words[j]) && j != i) {
            List<Integer> pair = new ArrayList<Integer>();
            pair.add(i);
            pair.add(j);
            result.add(pair);      
          }
        }
      }
      for (int index = 0; index < word.length(); index++) {
        String firstHalf = word.substring(0, index);
        String secondHalf = word.substring(index, word.length());
        String reversedSecond = new StringBuilder(secondHalf).reverse().toString();
        String reversedFirst = new StringBuilder(firstHalf).reverse().toString();
        if (isPalindrome(firstHalf) && wordToIndex.containsKey(reversedSecond) && wordToIndex.get(reversedSecond) != i) {
          List<Integer> pair = new ArrayList<Integer>();
          pair.add(wordToIndex.get(reversedSecond));
          pair.add(i);
          result.add(pair);
        }
        if (isPalindrome(secondHalf) && wordToIndex.containsKey(reversedFirst) && wordToIndex.get(reversedFirst) != i) {
          List<Integer> pair = new ArrayList<Integer>();
          pair.add(i);
          pair.add(wordToIndex.get(reversedFirst));
          result.add(pair);
        }
      }
    }
    return result;
  }
    
  private boolean isPalindrome(String a) {
    for (int i = 0, j = a.length() - 1; i <= j; i++, j--) {
      if (a.charAt(i) != a.charAt(j)) {
        return false;
      }
    }
    return true;
  }
}