LeetCode 题目解答—— 第 372 到 415 题

372 到 415 题，同级别的题目反正是越来越难。老规矩，跳过了那些付费题目。

Find K Pairs with Smallest Sums

Guess Number Higher or Lower

Guess Number Higher or Lower II

Kth Smallest Element in a Sorted Matrix

Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1) – Duplicates allowed

Linked List Random Node

Lexicographical Numbers

First Unique Character in a String

Longest Absolute File Path

Longest Substring with At Least K Repeating Characters

Convert a Number to Hexadecimal

Queue Reconstruction by Height

Trapping Rain Water II

Split Array Largest Sum

Super Pow

【题目】Your task is to calculate a b mod 1337 where  a is a positive integer and  b is an extremely large positive integer given in the form of an array.

Input: a = 2, b = [3]
Output: 8

Input: a = 2, b = [1,0]
Output: 1024

【解答】

一开始很奇怪，想到最后也不是很清楚为什么这里选了一个 1337 来取余，也许就是随便选一个，要不然整个计算结果太大了。

这里有两个技巧来保证结果不要过大：

• 自己定义的 pow 方法，在求 pow 的时候，拆成两部分，把 n 尽量等分，然后对 x 也取 1337 的余，再把结果乘起来，最后取 1337 的余。如果不这样拆在最后取余之前可能会得到一个大到溢出的结果。
• 对于 b，题目已经用某种方式提示了——b 的表示方式就是一个数组，而不是一个数，这就意味着不能把它当做一个简单的数来直接处理。于是一位数一位数处理，从高到低，每算得一次结果，一样通过一个取余操作来保持结果足够小。

其中拆分的技巧在很多题目里都用到：pow(x, n) = pow(x, n/2) * pow(x, n-n/2)

class Solution {
    public int superPow(int a, int[] b) {
        long result = 1;
        for (int bi : b) {
            // from high to low, pow each digit and mod to keep the result small
            result = (pow(result, 10) * pow(a, bi)) % 1337;
        }
        return (int) result;
    }
    
    private long pow(long x, int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return x % 1337;
        // just a little trick to avoid too large result
        return pow(x % 1337, n / 2) * pow(x % 1337, n - n / 2) % 1337;
    }
}

Find K Pairs with Smallest Sums

【题目】You are given two integer arrays nums1 and  nums2 sorted in ascending order and an integer  k .

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u 1 ,v 1 ),(u 2 ,v 2 ) …(u k ,v k ) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]] 
Explanation: The first 3 pairs are returned from the sequence: 
             [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

<strong>Input: </strong>nums1 = [1,1,2], nums2 = [1,2,3], k = 2
<strong>Output: </strong>[1,1],[1,1]
<strong>Explanation: </strong>The first 2 pairs are returned from the sequence: 
             [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

<strong>Input: </strong>nums1 = [1,2], nums2 = [3], k = 3
<strong>Output: </strong>[1,3],[2,3]
<strong>Explanation: </strong>All possible pairs are returned from the sequence: [1,3],[2,3]

【解答】从 nums1 中取一个数，从 nums2 中取一个数，寻找两数之和的第 k 小。

一开始我尝试把所有数的组合都找出来，放到一个 TreeMap 里面去，取前 k 小。居然过了：

class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        if (nums1==null || nums2==null || k<0)
            throw new IllegalArgumentException();
        
        List<int[]> res = new ArrayList<>(k);
        if (nums1.length==0 || nums2.length==0)
            return res;
        
        // tree map might not be the best solution - if the arrays are all large and k is small, it's a significant waste to sort and iterate all pairs
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        
        for (int l : nums1) {
            for (int r : nums2) {
                List<int[]> list = map.getOrDefault(l+r, new ArrayList<>());
                list.add(new int[]{l, r});
                map.put(l+r, list);
            }
        }
        
        Iterator<Integer> iter = map.keySet().iterator();
        while (iter.hasNext() && k>0) {
            int sum = iter.next();
            List<int[]> list = map.get(sum);
            for (int[] pair : list) {
                res.add(pair);
                k--;
                if (k==0)
                    break;
            }
        }
        
        return res;
    }
}

显然这不是最好的办法。我还想过这样的办法：准备两个指针，一个 p1 在 num1，一个 p2 在 num2，然后每次移动指针的时候都考虑是移动 p1 还是移动 p2 可以得到更小的值，确定了以后，移动并把得到的新结果放到结果集中，直到结果集大小为 k。可是实现的时候发现其实这个方法是错误的，因为指针不能只往前走，在某些 case 下还要往后走。比如 num1=[0,1]，num2=[0,2]，k=4，用这样的方法最多只能得到大小为 3 的结果集，而实际是可以得到大小为 4 的结果集的。

如果我们以从小到大的方式来构造这个结果集，在取得某一个值 num1[i] 和 num2[j] 的时候，下一个是什么？如果需要确定下一个，需要考察什么？

• 想到这里忽然又了头绪：
• 如果 k 小于 nums1 的长度，我应该建立一个大小大致为 k 的堆；如果 k 大于 nums1 的长度，则建立一个大小为 nums1.length 的堆，无论哪种，这个堆的大小为 len。
• 初始只需要考虑 len 个元素，且表示的是对于 nums1 的下标从 0 到 len-1 的情况下，nums2 的下标都为 0 的情况。
• 每次 poll 出堆顶，即当前最小值 (nums1[i] + nums2[j]) 了之后，要找下一个，就把 (nums1[i]+nums2[j+1]) 放入堆。
• 反复如上操作，直到取得了 k 个元素，或者元素取完了。

class Item implements Comparable<Item>{
    private int[] nums1;
    private int[] nums2;
    public int i;
    public int j;
    public Item(int i, int j, int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.i = i;
        this.j = j;
    }
    
    @Override
    public int compareTo(Item that) {
        return (nums1[i]+nums2[j]) - (that.nums1[that.i]+that.nums2[that.j]);
    }
}
class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        if (nums1==null || nums2==null || k<0)
            throw new IllegalArgumentException();
        
        List<int[]> res = new ArrayList<>(k);
        if (nums1.length==0 || nums2.length==0)
            return res;
        
        int len = Math.min(nums1.length, k);
        PriorityQueue<Item> queue = new PriorityQueue<>(len);
        for (int i=0; i<len; i++) {
            queue.add(new Item(i, 0, nums1, nums2));
        }
        
        while(res.size()<k && !queue.isEmpty()) {
            Item item = queue.poll();
            res.add(new int[] {nums1[item.i], nums2[item.j]});
            if (item.j+1<nums2.length)
                queue.add(new Item(item.i, item.j+1, nums1, nums2));
        }
        
        return res;
    }
}

Guess Number Higher or Lower

【题目】We are playing the Guess Game. The game is as follows:

I pick a number from 1 to  n . You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results ( -1 ,  1 , or  0 ):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example :

Input: n = 10, pick = 6
Output: 6

【解答】猜数。二分查找，当心溢出：

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        long start=1, end=n;
        while(true) {
            int mid = (int)((start+end)/2);
            int res = guess(mid);
            if (res==0)
                return mid;
            else if (res<0)
                end = mid-1;
            else
                start = mid+1;
        }
    }
}

Guess Number Higher or Lower II

【题目】We are playing the Guess Game. The game is as follows:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

【解答】题目要求“guarantee a win”，这里面涉及不同策略的问题。但是，我们可以评估所有的策略，并取可以保证胜利的情况下最小的 money 数量。考虑三种情况分别递归计算，并且把中间计算结果缓存到一个二维数组中：猜中，猜少了，以及猜多了。

class Solution {
    public int getMoneyAmount(int n) {
        // cost[i][j] means to know the range is [i, j], what will the min cost be
        Integer[][] cost = new Integer[n+1][n+1];
        return cal(1, n, cost);
    }
    
    private int cal(int from, int to, Integer[][] cost) {
        if (from>=to)
            return 0;
        
        if (cost[from][to]!=null)
            return cost[from][to];
        
        int min = Integer.MAX_VALUE;
        for (int i=from; i<=to; i++) {
            // for each number i to guess, pick the max in all possible costs
            
            // case 1: target == i
            int total = i;
            // case 2: target < i
            total = Math.max(total, cal(from, i-1, cost)+i);
            // case 3: target > i
            total = Math.max(total, cal(i+1, to, cost)+i);
            
            // for all the guess strategies, pick the one with min cost
            min = Math.min(total, min);
        }
        
        cost[from][to] = min;
        return min;
    }
}

Wiggle Subsequence

【题目】A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences  (6,-3,5,-7,3) are alternately positive and negative. In contrast,  [1,4,7,2,5] and  [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

【解答】要形成这种 wiggle 的序列，考虑两种情况，一种是先朝上（递增），第二种是县朝下（递减）的。

定义一个 wiggleMaxLength 重载方法，除了接受 nums 数组以外，还接受一个 start 表示从某一个下标开始，increased 表示上次是递增还是递减。方法返回从 start 开始的最长 wiggle 串的长度。

在一开始的时候，可以认为“上次”既可以是递增的，也可以是递减的，因此两种情况都要算。

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums==null || nums.length==0) return 0;
        
        int inc = wiggleMaxLength(nums, 0, true);
        int dec = wiggleMaxLength(nums, 0, false);
        
        return Math.max(inc, dec);
    }
    
    private int wiggleMaxLength(int[] nums, int start, boolean increased) {
        if (start==nums.length)
            return 0;
        
        if (start==0) {
            return 1 + wiggleMaxLength(nums, 1, increased);
        } else {
            boolean monotonic = increased ? nums[start-1]<=nums[start] : nums[start-1]>=nums[start];
            if (monotonic) {
                return wiggleMaxLength(nums, start+1, increased);
            } else {
                return 1 + wiggleMaxLength(nums, start+1, !increased);
            }
        }
    }
}

Combination Sum IV

【题目】Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

<i><b>nums</b></i> = [1, 2, 3]
<i><b>target</b></i> = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is <i><b>7</b></i>.

Follow up:

What if negative numbers are allowed in the given array?

How does it change the problem?

What limitation we need to add to the question to allow negative numbers?

【解答】最终是求能得到特定值的组合个数，那么就可以使用一个 map 来存放这样的结果，key 是特定值，value 是组合个数。使用递归来遍历所有可能求解，由于有了前面的 map，重复计算可以避免。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (nums==null || nums.length==0 || target<=0)
            return 0;
        
        Map<Integer, Integer> dp = new HashMap<>();
        return com(nums, target, dp);
    }
    
    private int com(int[] nums, int target, Map<Integer, Integer> dp) {
        if (target<=0)
            return 0;
        
        if (dp.containsKey(target))
            return dp.get(target);
        
        int total = 0;
        for (int num : nums) {
            if (target==num) {
                total++;
                continue;
            } else if (num>target) {
                continue;
            } else {
                total += com(nums, target-num, dp);
            }
        }
        
        dp.put(target, total);
        return total;
    }
}

Kth Smallest Element in a Sorted Matrix

【题目】Given a n x  n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note: 

You may assume k is always valid, 1 ≤ k ≤ n 2 .

【解答】从上到下和从左到右都是逐渐增大的。所有从左上角开始一层一层往右侧和下侧蔓延，通过一个 visited 数组或者一个 dedup set 来记录已经访问过的元素，同时使用一个堆来存放着最多 k 个的元素。每次蔓延实际都是检查当前边界元素的右侧和下方两个元素，这个蔓延的行为必须持续 k 次，这样理论上所有可能出现的 k 小都已经包括在内了，而每次操作因为带有一次 poll，因此 k 次循环之后 poll 到的也就是第 k 小的元素。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        Item first = new Item(0, 0, matrix[0][0]);
        
        PriorityQueue<Item> heap = new PriorityQueue<>();
        heap.add(first);
        
        Set<Item> dedup = new HashSet<>();
        dedup.add(first);
        
        Item item = null;
        for (int p=0; p<k; p++) {
            item = heap.poll();
            int i = item.i;
            int j = item.j;
            
            if (item.i<matrix.length-1) {
                Item newItem = new Item(i+1, j, matrix[i+1][j]);
                if (dedup.add(newItem))
                    heap.add(newItem);
            }
            
            if (item.j<matrix[0].length-1) {
                Item newItem = new Item(i, j+1, matrix[i][j+1]);
                if (dedup.add(newItem))
                    heap.add(newItem);
            }
        }
        
        return item.val;
    }
}

class Item implements Comparable<Item>{
    int i;
    int j;
    int val;
    
    public Item(int i, int j, int val) {
        this.i = i;
        this.j = j;
        this.val = val;
    }
    
    @Override
    public int hashCode() {
        return i ^ j;
    }
    
    @Override
    public boolean equals(Object other) {
        Item that = ((Item) other);
        return this.i==that.i && this.j==that.j;
    }
    
    @Override
    public int compareTo(Item other) {
        return this.val - other.val;
    }
}

Insert Delete GetRandom O(1)

【题目】Design a data structure that supports all following operations in average O(1) time.

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

【解答】要能在常数时间内添加和删除任意数，不难想到使用 HashMap。要能够返回随机数，不难想到常规的 random 方法，给一个上限，每次调用 nextInt 方法。联合起来，要使得取得的随机数和里面的数的集合关联起来，并且这个上限每次在常数时间内调整，考虑使用双向 map：一个 map 是从 0~x 的连续整数映射到实际的数集合；另一个则是反过来。

class RandomizedSet {
    private Map<Integer, Integer> indexToValue = new HashMap<>();
    private Map<Integer, Integer> valueToIndex = new HashMap<>();
    private Random random = new Random(System.currentTimeMillis());

    /** Initialize your data structure here. */
    public RandomizedSet() {
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        Integer index = valueToIndex.get(val);
        if (index!=null)
            return false;
        
        // it's a new number, so the new index should be valueToIndex.size()
        valueToIndex.put(val, valueToIndex.size());
        indexToValue.put(indexToValue.size(), val);

        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        Integer index = valueToIndex.get(val);
        if (index==null)
            return false;
        
        // the target is removed but there could be a hole in the middle
        valueToIndex.remove(val);
        indexToValue.remove(index);
        
        // if the end entry was removed, no adjustment needed
        if (index==indexToValue.size())
            return true;

        // else, move the end entry to fill the hole
        int valueToAdjust = indexToValue.get(indexToValue.size());
        int indexToAdjust = valueToIndex.get(valueToAdjust);

        valueToIndex.remove(valueToAdjust);
        indexToValue.remove(indexToAdjust);

        valueToIndex.put(valueToAdjust, index);
        indexToValue.put(index, valueToAdjust);
        
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int index = random.nextInt(indexToValue.size());
        return indexToValue.get(index);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Insert Delete GetRandom O(1) – Duplicates allowed

【题目】Design a data structure that supports all following operations in average O(1) time.

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

【解答】思路和前面那道还是类似，但是因为这次允许有重复，所以这次在这两个 map 中有一个需要做出一定的改动，引入 index set。

class RandomizedCollection {
    private Map<Integer, Integer> indexToValue = new HashMap<>();
    private Map<Integer, Set<Integer>> valueToIndices = new HashMap<>();
    private Random random = new Random(System.currentTimeMillis());
    
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        int newIndex = indexToValue.size();
        indexToValue.put(newIndex, val);
        
        Set<Integer> indices = valueToIndices.getOrDefault(val, new HashSet<>());
        indices.add(newIndex);
        valueToIndices.put(val, indices);
        
        if (indices.size()==1) {
            return true;
        } else {
            return false;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        Set<Integer> indices = valueToIndices.getOrDefault(val, new HashSet<>());
        if (indices.isEmpty()) {
            return false;
        }
        
        int indexRemoved = indices.iterator().next();
        indices.remove(indexRemoved);
        indexToValue.remove(indexRemoved);
        
        // if the end entry was removed, no adjustment needed
        if (indexRemoved==indexToValue.size()) {
            return true;
        }
        
        // else, move the end entry to fill the hole
        int indexToAdjust = indexToValue.size();
        int valueToAdjust = indexToValue.get(indexToAdjust);
        indexToValue.remove(indexToAdjust);
        indexToValue.put(indexRemoved, valueToAdjust);
        valueToIndices.get(valueToAdjust).remove(indexToAdjust);
        valueToIndices.get(valueToAdjust).add(indexRemoved);
        
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        int index = random.nextInt(indexToValue.size());
        return indexToValue.get(index);
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Linked List Random Node

【题目】Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

【解答】本来一个思路是引入一个 map 来很快地访问到这个 list 上面的所有节点，但要不使用额外空间，就只有牺牲每次访问的时候的效率了：记录下 list 的长度，random 的时候生成要从 head 开始往前走的步数，从而找到要返回的值所在的节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private Random random = new Random(System.currentTimeMillis());
    private int size;
    private ListNode head;
    
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        while (head!=null) {
            this.size++;
            head = head.next;
        }
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int step = random.nextInt(size);
        ListNode cur = head;
        for (int i=0; i<step; i++) {
            cur = cur.next;
        }
        return cur.val;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

Ransom Note

【题目】Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:

You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

【解答】没太多可说的，需要记录下每个字母出现的次数。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i=0; i<magazine.length(); i++) {
            char ch = magazine.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, 0);
            }
            
            map.put(ch, map.get(ch)+1);
        }
        
        for (int i=0; i<ransomNote.length(); i++) {
            char ch = ransomNote.charAt(i);
            Integer count = map.get(ch);
            
            if (count==null || count==0)
                return false;
            
            map.put(ch, map.get(ch)-1);
        }
        
        return true;
    }
}

Shuffle an Array

【题目】Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.

int[] nums = {1,2,3};

Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.

solution.shuffle();

// Resets the array back to its original configuration [1,2,3].

solution.reset();

// Returns the random shuffling of array [1,2,3].

solution.shuffle();

【解答】要求洗牌。每次都产生一个最大值为当前待选牌的数量的随机数作为下标，去这堆牌里面取，直到取完。

class Solution {
    private Random r = new Random();
    private int[] nums = null;
    
    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return this.nums;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        List<Integer> list = new ArrayList<>(nums.length);
        for (int num : nums) {
            list.add(num);
        }
        
        int[] res = new int[nums.length];
        for (int i=nums.length-1; i>=0; i--) {
            int idx = r.nextInt(i+1);
            res[i] = list.remove(idx);
        }
        
        return res;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Mini Parser

【题目】Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits  0-9 ,  [ ,  -   , ,  ] .

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

【解答】这种题目可以称之为“考操作”的题目，大致思路应该说没有什么难的，从左到右遍历，使用一个 stack 来处理括号。但是有一些细节需要注意，所以总的来说就是考操作：

• 遇到数字要读取到底，负号的可能要考虑到；
• 读完数字以后要检查移动后的下标是否还有意义（在界内）；
• 最后再处理进出栈。

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        NestedInteger root = null;
        NestedInteger cur = root;
        Stack<NestedInteger> stack = new Stack<>();
        
        int i = 0;
        while (i<s.length()) {
            // number
            String num = "";
            while (i<s.length() && (s.charAt(i)>='0' && s.charAt(i)<='9' || s.charAt(i)=='-')) {
                num += s.charAt(i);
                i++;
            }
            
            if (num.length()!=0) {
                NestedInteger numNI = new NestedInteger(Integer.parseInt(num));
                if (cur!=null) {
                    cur.add(numNI);
                } else {
                    cur = numNI;
                    root = cur;
                }
            }
            
            if (s.length()==i)
                break;
            
            char ch = s.charAt(i);
            if (ch=='[') {
                NestedInteger arrNI = new NestedInteger();
                if (cur!=null) {
                    cur.add(arrNI);
                    stack.push(cur);
                } else {
                    root = arrNI;
                }
                cur = arrNI;
            } else if (ch==']') {
                if (!stack.isEmpty())
                    cur = stack.pop();
            }
            
            i++;
        }
        
        return root;
    }
}

Lexicographical Numbers

【题目】Given an integer n , return 1 –  n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

【解答】要按照字典序找前 n 个数。开始想了想，似乎没有好的解法，就想排一排序取前面 n 个吧，果然超时了：

class Solution {
    // Time Limit ExceededMore Details 
    // Last executed input: 23489
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>(n);
        for (int i=1; i<=n; i++) {
            list.add(i);
        }
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer l, Integer r) {
                String ls = l + "";
                String rs = r + "";
                return ls.compareTo(rs);
            }
        });
        return list;
    }
}

在后来我猜逐渐理解，类似这种字典序的问题，有一个常用的思路，就是构造，而非穷举。有时候需要从左往右一位一位构造，这个构造可以表现为一棵 x 叉的树，有时候需要从这棵树的根开始一层一层往下计数。而这道题事实上还没那么麻烦，只需要从小到大尝试构造符合条件的数，操作 n 次即可。

class Solution {
    public List<Integer> lexicalOrder(int n) {
        int cur = 1;
        List<Integer> res = new ArrayList<>();
        for (int i=1; i<=n; i++) {
            res.add(cur);
            if (cur*10l<=n) { // avoid overflow
                cur = cur*10;
            } else if (cur%10!=9 && cur<n) { // can't add more digits, so increase the last digit
                cur++;
            } else { // can't add more digits, and can't change the last digit, have to shorten the number
                while ((cur/10)%10==9) { // if the second last digit is 9, remove last digit
                    cur/=10;
                }
                cur = cur/10 + 1; // remove the last digit and find the next number with the same length
            }
        }
        
        return res;
    }
}

First Unique Character in a String

【题目】Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

【解答】没有太多可说的，使用一个 map，key 是字母，value 是 index，该字母第二次及以后出现就置为特殊值-1：

public class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> map =  new HashMap<>(26);
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, i);
            } else {
                map.put(ch, -1);
            }
        }
        
        Integer min = -1;
        for (Integer pos : map.values()) {
            if (pos==null || pos.intValue()==-1)
                continue;
            
            if (min==-1 || pos.intValue()<min)
                min = pos.intValue();
        }
        
        return min;
    }
}

Longest Absolute File Path

【题目】Suppose we abstract our file system by a string in the following manner:

dir
    subdir1
    subdir2
        file.ext

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

.
.

【解答】寻找最长的路径。常规题目，从思考到写不困呢，但是考虑周全和思路清晰更重要。从左往右扫描：

• 一开始就在 input 的最后增加一个换行，目的是简化逻辑，不需要在循环跳出以后做额外的处理；
• 创建一个 nodes 的 list 用来扮演 stack 的角色，记录当前的路径；
• tabs 是用来记录当前行的节点深度的。

class Solution {
    public int lengthLongestPath(String input) {
        if (input==null)
            return 0;
        
        input += '\n';
        int longest = 0;
        int tabs = 0;
        String current = "";
        List<String> nodes = new ArrayList<>();
        for (int i=0; i<input.length(); i++) {
            char ch = input.charAt(i);
            if (ch=='\n') {
                tabs = 0;
                String path = "";
                if (current.contains(".")) {
                    for (String node : nodes) {
                        path += (node + '/');
                    }
                    path += current;
                    
                    if (path.length()>longest)
                        longest = path.length();
                } else {
                    nodes.add(current);
                }
                current = "";
            } else if (ch=='\t') {
                tabs++;
            } else {
                if (nodes.size()>tabs) {
                    for (int j=tabs; j<nodes.size(); j++) {
                        nodes.remove(j);
                    }
                }
                
                current += ch;
            }
        }
        
        return longest;
    }
}

Find the Difference

【题目】Given two strings s and  t which consist of only lowercase letters.

String t is generated by random shuffling string  s and then add one more letter at a random position.

Find the letter that was added in t .

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

【解答】使用 map 或者长度为 26 的数组来记录字符出现的次数。

public class Solution {
    public char findTheDifference(String s, String t) {
        int[] chars = new int[26];
        for (int i=0; i<s.length(); i++) {
            int pos = s.charAt(i) - 'a';
            chars[pos]++;
        }
        
        for (int i=0; i<t.length(); i++) {
            int pos = t.charAt(i) - 'a';
            chars[pos]--;
        }
        
        for (int i=0; i<chars.length; i++) {
            if (chars[i] < 0)
                return (char)('a' + i);
        }
        
        return (char)0; // unreachable
    }
}

Elimination Game

【题目】There is a list of sorted integers from 1 to n . Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n .

Example:

Input:
n = 9,
<u>1</u> 2 <u>3</u> 4 <u>5</u> 6 <u>7</u> 8 <u>9</u>
2 <u>4</u> 6 <u>8</u>
<u>2</u> 6
6

Output:
6

【解答】这一类题看起来更像数学题，也许有偏向纯数学而非计算机算法的方法来解。

最显然的办法自然是按照题目提示的规则操作一遍，不要使用 ArrayList 也不要使用普通的 LinkedList，可以考虑使用双向链表，因为这里涉及到从前往后和从后往前的双向操作，但依然，在 n 比较大的时候需要创建一大堆元素，显得效率很低。

再仔细想想，为什么要创建那么长一个链表，再逐步删掉直到只剩一个元素？能不能在操作基本不变的基础上，假想一个链表？下面的做法就是这样：

• 用 step 记录当前的步长，用 leftOrRight 记录当前的方向，rest 记录剩余元素的个数，first 记录当前剩余数中第一个的位置。
• 在 rest 为偶数的时候，first 的位置不需要调整，但是如果是奇数，first 就要增加一个步长。
• 每一遍循环都将 rest 的个数减半。

上面这个规则可以通过创建两个实际例子，一个偶数个数，一个奇数个数，来逐步摸索出来。比如下面上面这个 rest 减半的操作，需要考察实际当 rest 是偶数的时候，以及是奇数的时候两种情况，于是发现二者都可以简单地除以 2，不需要分类处理。

从一个实际数组，抽象到无数组，而只有几个关键参数的形式（因为这几个关键参数就可以完全表示出每次操作后余下的序列）——这是这类题最难的部分。

class Solution {
    public int lastRemaining(int n) {
        int rest = n;
        int step = 1;
        int first = 1; // the first number in the rest number series
        boolean leftOrRight = true;
        while (rest>1) {
            if (leftOrRight) {
                first += step;
            } else {
                if (rest%2==0) // even
                    ; // no change
                else // odd
                    first += step;
            }
            
            step *= 2;
            rest /= 2; // doesn't care rest is even or odd
            leftOrRight = !leftOrRight;
        }
        
        return first;
    }
}

稍微改进一下，本质没有区别：

class Solution {
    public int lastRemaining(int n) {
        int rest = n;
        int step = 1;
        int first = 1; // the first number in the rest number series
        boolean leftOrRight = true;
        while (rest>1) {
            if (leftOrRight || rest%2==1)
                first += step;
            
            step *= 2;
            rest /= 2; // doesn't care rest is even or odd
            leftOrRight = !leftOrRight;
        }
        
        return first;
    }
}

Perfect Rectangle

【题目】Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

【解答】要看其中的矩形们能否联合起来恰好形成一个矩形，没有重叠，没有遗漏。

最直接的做法，我引入一个标记是否覆盖过的图，第一次访问的时候就标记一下，第二次就返回失败，标记完毕以后再遍历一下，如果发现还有未覆盖的就返回失败，否则返回成功。思路简单，但是无论是时间复杂度还是空间复杂度都明显超出要求：

class Solution {
    private Integer rowMin = null;
    private Integer rowMax = null;
    private Integer colMin = null;
    private Integer colMax = null;
    private Map<Integer, Set<Integer>> graph = new HashMap<>();
    
    public boolean isRectangleCover(int[][] rectangles) {
        for (int[] row : rectangles) {
            for (int i=row[0]; i<row[2]; i++) {
                for (int j=row[1]; j<row[3]; j++) {
                    if (!mark(i, j))
                        return false;
                }
            }
        }
        
        return check();
    }
    
    private boolean mark(int i, int j) {
        if (rowMin==null || rowMin>i) rowMin = i;
        if (rowMax==null || rowMax<i) rowMax = i;
        if (colMin==null || colMin>j) colMin = j;
        if (colMax==null || colMax<j) colMax = j;
        
        Set<Integer> set = graph.getOrDefault(i, new HashSet<>());
        if (!set.add(j))
            return false;
        
        graph.put(i, set);
        return true;
    }
    
    private boolean check() {
        for (int i=rowMin; i<=rowMax; i++) {
            for (int j=colMin; j<=colMax; j++) {
                Set<Integer> set = graph.get(i);
                if (set==null)
                    return false;
                if (!set.contains(j))
                    return false;
            }
        }
        
        return true;
    }
}

也许还有一个类似方向的思路，就是用 TreeMap 来做，像是线段树一样，存放起始点和终结点，好处是省掉实际实打实的这个是否覆盖过的图，但问题是这会让代码很复杂，因为这个覆盖情况的判别不是一维的，而是二维的。

以下方法来自 讨论区 ，我认为非常巧妙。

如下两个条件满足的情况下，可以推出“Perfect Rectangle”的结论：

1. 把所有子矩形的面积加起来，恰好等于四个边界点所围成的最大矩形面积
2. 除去位于这个最大矩形的边上的部分，所有子矩形的边，都为偶数条

以上两个结论，如果只满足第一个，即只具备面积相等的条件，那么“最大矩形”内部同时还可能包含重叠和空缺；如果只满足第二个，可能出现的反例是，存在子矩形重叠且重叠导致的重复边为偶数。但是当两个结论都成立的时候，它们就构成了“Perfect Rectangle”的充分条件。

上面第一点要容易想到，因而第二点是题目解决最关键的部分。上面这两个结论，严格地可以通过数学方法推导出来。换言之，复杂度通过数学方法减小了。

具体实现：

• 循环所有子矩形，累加所有面积；
• 在判断两个点形成的线段是否有重复的方法上面，考虑每一条边线，通过用空格连接每一维实际的坐标，然后得到的字符串利用 HashSet 判别去重（算是取了个巧，比自定义一个表示线段的类要稍微简便一些）；
• 寻找到所有子矩形的最左点、最右点、最上点和最下点；
• 上面的一通去重操作以后，应该只剩下恰好构成最终覆盖矩形的四个顶点了，其它的点应该都已经去重过程中湮灭掉了，于是在循环结束后判断一下这个 set 里面是否真的只剩它们。

复杂度上看，时间复杂度，避免了每一点的考察，只需要考察所给的图形，通常图形的个数和覆盖的点的个数差别巨大；空间复杂度，避免了建立整体矩形大小的标记数组，都获得了简化。

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles.length == 0 || rectangles[0].length == 0) return false;

        int x1 = Integer.MAX_VALUE;
        int x2 = Integer.MIN_VALUE;
        int y1 = Integer.MAX_VALUE;
        int y2 = Integer.MIN_VALUE;
        
        HashSet<String> set = new HashSet<String>();
        int area = 0;
        
        for (int[] rect : rectangles) {
            x1 = Math.min(rect[0], x1);
            y1 = Math.min(rect[1], y1);
            x2 = Math.max(rect[2], x2);
            y2 = Math.max(rect[3], y2);
            
            area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
            
            String s1 = rect[0] + " " + rect[1];
            String s2 = rect[0] + " " + rect[3];
            String s3 = rect[2] + " " + rect[3];
            String s4 = rect[2] + " " + rect[1];
            
            if (!set.add(s1)) set.remove(s1);
            if (!set.add(s2)) set.remove(s2);
            if (!set.add(s3)) set.remove(s3);
            if (!set.add(s4)) set.remove(s4);
        }
        
        if (!set.contains(x1 + " " + y1) || !set.contains(x1 + " " + y2) || !set.contains(x2 + " " + y1) || !set.contains(x2 + " " + y2) || set.size() != 4) return false;
        
        return area == (x2-x1) * (y2-y1);
    }
}

Is Subsequence

【题目】Given a string s and a string  t , check if  s is subsequence of  t .

You may assume that there is only lower case English letters in both s and  t .  t is potentially a very long (length ~= 500,000) string, and  s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of  "abcde" while  "aec" is not).

Example 1:

s =  "abc" ,  t =  "ahbgdc"

Return true .

Example 2:

s =  "axc" ,  t =  "ahbgdc"

Return false .

Follow up:

If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

【解答】要判断 s 是不是 t 的子序列，我的第一反应是想大概是一道动态规划的题目，判断 s 的某一个字母 s[i] 是否在以 t[j..] 这个子串内，可是后来仔细分析以后发现，这个问题其实可以用贪心的策略来解决，这就要简单一些。

为 t 建立一个 map（实现的时候通过 array 达到一样的效果），key 是字符，value 是一个 HashSet，里面存放的是该字符出现的 index。这样每出现一个字符，就可以使用 ceiling 函数寻找所有可行的位置中最小的那一个。如果贪心可行，贪心的方法往往要比动态规划简单一些。

class Solution {
    public boolean isSubsequence(String s, String t) {
        // tree set array
        // (1) array index indicates the character
        // (2) indices of s are stored in its tree set
        TreeSet<Integer>[] positions = new TreeSet[26];
        
        // step 1: build tree set array
        for (int i=0; i<t.length(); i++) {
            char ch = t.charAt(i);
            int index = ch - 'a';
            
            if (positions[index]==null)
                positions[index] = new TreeSet<>();
            
            TreeSet<Integer> ts = positions[index];
            ts.add(i);
        }
        
        // step 2: search
        int lastPos = -1;
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            int index = ch - 'a';
            
            if (positions[index]==null)
                return false;
            
            Integer newPos = positions[index].ceiling(lastPos + 1);
            // +1 is important to indicate any position can only be used no more than once
            
            if (newPos==null)
                return false;
            
            lastPos = newPos;
        }
        
        return true;
    }
}

UTF-8 Validation

【题目】A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

data = [197, 130, 1], which represents the octet sequence: <b>11000101 10000010 00000001</b>.

Return <b>true</b>.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

data = [235, 140, 4], which represented the octet sequence: <b>11101011 10001100 00000100</b>.

Return <b>false</b>.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

【解答】要先把题意看懂，规则看懂。又是一道“考操作”的题目。

• 从前往后扫描，定义一个 rest 来表示除了开头那八位，后面还有多少个八位来存放实际数据，rest 可以为 0、1、2 或 3，这取决于开头那八位的值；
• 定义一个 getType 用来区分上面的几种情况，定义 TYPE_CONT 表示该八位以 10 开头，后面可以存放数据；
• 于是，在 rest 为 0 的情况下，作为开头八位，getType 不能返回 TYPE_CONT；
• 在 rest 不为 0 的情况下，getType 方法就必须返回 TYPE_CONT，其它都是错误的。

class Solution {
    /**
       TYPE=1: 0000 0000-0000 007F | 0xxxxxxx
       TYPE=2: 0000 0080-0000 07FF | 110xxxxx 10xxxxxx
       TYPE=3: 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
       TYPE=4: 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
     */
    private static int TYPE_CONT = -1; // 10xxxxxx
    private static int TYPE_ERROR = 0;
    
    public boolean validUtf8(int[] data) {
        if (data==null || data.length==0)
            return false;
        
        Integer type = null;
        int rest = 0;
        for (int i=0; i<data.length; i++) {
            if (rest == 0) {
                type = getType(data[i]);
                
                if (type==TYPE_CONT || type==TYPE_ERROR)
                    return false;
                
                rest = type - 1;
            } else {
                rest--;
                if (getType(data[i]) != TYPE_CONT)
                    return false;
            }
        }
        
        return rest == 0;
    }
    
    private int getType(int num) {
        // only least significant 8 bits of each integer is used
        int mask = 1 << 7;
        
        if ((num&mask) == 0)
            return 1;
        
        mask = mask >>> 1;
        if ((num&mask) == 0)
            return TYPE_CONT;
        
        for (int i=2; i<=4; i++) {
            mask = mask >>> 1;
            if ((num&mask) == 0)
                return i;
        }

        return TYPE_ERROR;
    }
}

Decode String

【题目】Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string] , where the  encoded_string inside the square brackets is being repeated exactly  k times. Note that  k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k . For example, there won’t be input like  3a or  2[4] .

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

【解答】没有太多可说的，扫描+堆栈，这里面涉及到子字符串和重复次数。可以定义一个类包含这两项，然后使用一个堆栈，也可以偷个懒，使用两个堆栈，一个存放子字符串，一个存放重复次数。

class Solution {
    public String decodeString(String s) {
        Stack<Integer> times = new Stack<>();
        Stack<String> strs = new Stack<>();
        
        String cur = "";
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            
            if (ch>='0' && ch<='9') {
                int count = 0;
                while (ch>='0' && ch<='9') {
                    count = count*10 + (ch-'0');
                    i++;
                    ch = s.charAt(i);
                }
                
                times.push(count);
            }
            
            if (ch=='[') {
                strs.push(cur);
                cur = "";
            } else if (ch==']') {
                int count = times.pop();
                String newCur = "";
                for (int j=0; j<count; j++) {
                    newCur += cur;
                }
                cur = strs.pop() + newCur;
            } else {
                cur += ch;
            }
        }
        
        return cur;
    }
}

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.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

【解答】要找出最长的子串，其中的所有字符都至少重复了 k 次。

拿到题目以后我有这样几个思路：

• 第一个思路是能不能建立一个动态规划模型，假设 p[i] 表示是从 s[i] 开始的最长的满足要求的子串的长度，但是这种思路很难找到问题和子问题之间联系的关系式，这条路似乎不好走。
• 第二个思路是滑动窗口，控制一个 start 下标和一个 end 下标，各自都分别往右移动，窗口所框定的字符串满足题意。但是滑动窗口方法要求进窗口和出窗口的条件清晰，这里却并不：如果当前滑动窗口满足条件，end 下标右移，于是此时不满足了，我有两个选择，一个可以 start 前进，一个可以 end 前进，这两条路都可能是对的。
• 第三个思路是，先考虑整个字符串，如果符合条件，皆大欢喜；如果不合条件，那么就从中寻找不合要求的字符，那么显然这个字符是不可能出现在符合条件的子串中的，于是字符的两边的串分别递归求解。

显然第三条思路想起来觉得靠谱：

class Solution {
    public int longestSubstring(String s, int k) {
        return longest(s, k, 0, s.length()-1);
    }
    
    private int longest(String s, int k, int start, int end) {
        if (end-start+1 < k)
            return 0;
        
        int[] letters = new int[26];
        for (int i=start; i<=end; i++) {
            char ch = s.charAt(i);
            letters[ch-'a']++;
        }
        
        for (int l=0; l<26; l++) {
            int count = letters[l];
            if (count==0 || count>=k)
                continue;
            
            // found incompliant letter
            for (int i=start; i<=end; i++) {
                if (s.charAt(i) ==(char)('a'+l)) {
                    int leftPart = longest(s, k, start, i-1);
                    int rightPart = longest(s, k, i+1, end);
                    return Math.max(leftPart, rightPart);
                }
            }
        }
        
        // compliant
        return end-start+1;
    }
}

虽然通过了，但复杂度还是偏高，最坏的时间复杂度在 n 的平方。讨论区有复杂度为 n 的 方法 供参考。

Rotate Function

【题目】Given an array of integers A and let  n to be its length.

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

【解答】看起来就很像高中里面函数的递推关系式，事实上，也确实可以用那个时候解函数递推关系问题的办法来简化题目：

F(0) = 0*A[0] + 1*A[1] + 2*A[2] + … + (n-1)*A[n-1]  F(1) = 1*A[0] + 2*A[1] + 3*A[2] + … + 0*A[n-1]  = F(0) + sum – n*A[n-1]  …  F(k+1) = F(k) + sum – n*A[n-1-k]

于是就得到了 F(k+1) 和 F(k) 之间单纯的关系式，其中的 sum 我们可以在预先一次循环求得，利用它就可以把问题变得很简单：

class Solution {
    public int maxRotateFunction(int[] A) {
        if (A==null)
            throw new IllegalArgumentException();
        if (A.length==0)
            return 0;
        
        int sum = 0;
        int f0 = 0;
        for (int i=0; i<A.length; i++) {
            sum += A[i];
            f0 += i*A[i];
        }
        
        int last = f0;
        int max = last;
        for (int k=0; k<A.length-1; k++) {
            last = last + sum - A.length*A[A.length-1-k];
            max = Math.max(max, last);
        }
        
        return max;
    }
}

Integer Replacement

【题目】Given a positive integer n and you can do operations as follow:

<b>Input:</b>
8

<b>Output:</b>
3

<b>Explanation:</b>
8 -> 4 -> 2 -> 1

<b>Input:</b>
7

<b>Output:</b>
4

<b>Explanation:</b>
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

【解答】本质上是搜索类的问题，考虑 BSF 或者 DSF，对于这样预期步骤数量不明确的，以及回溯特征不明显的，通常都是 BSF。准备两个集合，一个用来存储当前 BSF 的边界，边界上的节点会参与到下一步的计算中；另一个用来存放已经访问过的节点，以避免重复运算。

class Solution {
    public int integerReplacement(int n) {
        // BFS
        Set<Long> visited = new HashSet<>();
        Set<Long> current = new HashSet<>();
        current.add(n+0l);
        return search(current, visited, 0);
    }
    
    private int search(Set<Long> current, Set<Long> visited, int depth) {
        if (current.contains(1l))
            return depth;
        
        visited.addAll(current);
        Set<Long> newCurrent = new HashSet<>();
        for (long cur : current) {
            if (cur%2 == 0) {
                if (visited.contains(cur/2))
                    continue;
                else
                    newCurrent.add(cur/2);
            } else {
                if (visited.contains(cur+1))
                    continue;
                else
                    newCurrent.add(cur+1);
                
                if (visited.contains(cur-1))
                    continue;
                else
                    newCurrent.add(cur-1);
            }
        }
        
        return search(newCurrent, visited, depth+1);
    }
}

Random Pick Index

【题目】Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:

The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

【解答】看起来就是要建立一个从具体数到 index 集合的映射，然后再在这个 index 集合里面使用 random 方法挑一个返回。不过题目说的不要使用“too much extra space”实在是不合适，怎样才算是“too much extra space”呢？

class Solution {
    private Map<Integer, List<Integer>> map = new HashMap<>();
    Random random = new Random();
    public Solution(int[] nums) {
        for (int i=0; i<nums.length; i++) {
            int num = nums[i];
            if (!map.containsKey(num))
                map.put(num, new ArrayList<>());
            
            map.get(num).add(i);
        }
    }
    
    public int pick(int target) {
        List<Integer> list = map.get(target);
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

Evaluate Division

【题目】Equations are given in the format A / B = k , where  A and  B are variables represented as strings, and  k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return  -1.0 .

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries  , where  equations.size() == values.size() , and the values are positive. This represents the equations. Return  vector<double> .

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

【解答】看起来让我想到了 Prolog 语言——给一堆规则，问一个问题，得到一个答案。

一开始还觉得题目似乎很新颖，没有什么思路，但是仔细研究这些规则发现，规则都是很简单的，都是除法，a/b=2.0 也就意味着 a/2.0=b，a 给一个参数 2.0 并执行除法操作，得到了 b。看起来似乎有了头绪——a 和 b 之间存在着联系，看起来可以抽象出一个双向图：a 通过权值为 2.0 的路径可以到达 b，而 b 通过权值为 1/2.0 的路径可以到达 a。

这样，当题目问起别的执行公式的时候，其实问的就是给定两个点有向的连通问题。

想到这一步，这道题可以说解出了一半，基本上就只剩操作的部分了。

具体实现上，

• 定一个 Map<String, Set<Node>> graph，key 就是起始节点，Node 包含了终止节点和路径的权值，每一个已知公式都可以表示出两条关系，即双向路径；
• 再定义一个标记是否访问过的 Map<String, Boolean> visited；
• 执行的时候首先根据已知条件把 graph 构建起来，然后从给定问题的起点开始递归搜索，DFS 方式尝试寻找从起点到终点的路径，并把其中的每一段相乘。

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Set<Node>> graph = new HashMap<>();
        Map<String, Boolean> visited = new HashMap<>();
        
        for (int i=0; i<equations.length; i++) {
            String start = equations[i][0];
            String end = equations[i][1];
            double val = values[i];
            
            visited.put(start, false);
            visited.put(end, false);
            
            if (!graph.containsKey(start))
                graph.put(start, new HashSet<>());
            graph.get(start).add(new Node(end, val));
            if (!graph.containsKey(end))
                graph.put(end, new HashSet<>());
            graph.get(end).add(new Node(start, 1/val));
        }
        
        double[] result = new double[queries.length];
        for (int i=0; i<queries.length; i++) {
            String start = queries[i][0];
            String end = queries[i][1];
            
            Double res;
            if (!visited.containsKey(start) || !visited.containsKey(end)) {
                res = null;
            } else {
                res = search(graph, visited, start, end);
            }
            
            if (res==null)
                res = -1.0;
            result[i] = res;
        }
        return result;
    }
    
    private Double search(Map<String, Set<Node>> graph, Map<String, Boolean> visited, String start, String end) {
        if (start.equals(end))
            return 1.0;
        
        if (visited.get(start))
            return null;

        for (Node node : graph.get(start)) {
            visited.put(start, true);
            Double next = search(graph, visited, node.end, end);
            visited.put(start, false);
            if (next!=null)
                return node.distance * next;
        }

        return null;
    }
}

class Node {
    public String end;
    public Double distance;
    public Node(String end, double distance) {
        this.end = end;
        this.distance = distance;
    }
}

Nth Digit

【题目】Find the n th digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

<b>Input:</b>
3

<b>Output:</b>
3

<b>Input:</b>
11

<b>Output:</b>
0

<b>Explanation:</b>
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

【解答】要找到第 n 位数字是什么，这怎么可能只是 easy 难度？拿到题目的时候，心里有一个大致的思路，就是把这些数字挨个写出来，然后找第 n 位。但是实际上，并不需要真的把这些数写出来，而是根据数字排列的规律，把这些数字分成这样的多个部分：

1 ~ 9  10 ~ 99  100 ~ 999  …

这样分的原因是，一组一组可以逐渐线性增大，而且每一组内部的构成都是一致的（都具备相同的数字位数，这点便于计算）：

• 如果定义一个 totalNumber 表示当前组数字的数量，第一组是 1~9，一共 9 个；第二组 10~99 就是 totalNumber*10，因为第一组的每一个数字后面都可以跟一个数字，这个数字来自 0~9 中的任意一个。这个具备递进关系的分组是本题的关键。
• 不断用增大的组数去累计并挑战 n，直到发现累计到最新的组所包含的数字超过 n，这是退出循环。因为所求的数字应当在当前组内。
• 在已知当前组的起始元素和每个元素的长度（数字个数）的情况下，可以找到所求数字所在的元素（除法）和元素中的数字序号（取余）。

class Solution {
    public int findNthDigit(int n) {
        int startNumber = 1;
        int length = 1;
        long totalDigits = 9; // 1 ~ 9

        while (true) {
            if (n <= length * totalDigits)
                break;
            
            n -= length * totalDigits; // 1~9
            
            totalDigits *= 10; // 1~9 => adding 10 and 11~99
            startNumber *= 10; // 1 => 10
            length++;
        }
        
        // startNumber is 10^m, so "rest" starts from 0
        int rest = (n-1) / length;
        int digitNo = (n-1) % length;
        int locatedNumber = startNumber + rest;
        // e.g. startNumber=1000, n=5, length=4, so locatedNumber = 1000 + (5-1)/4 = 1001
        
        return ("" + locatedNumber).charAt(digitNo) - '0';
    }
}

Binary Watch

【题目】A binary watch has 4 LEDs on the top which represent the hours ( 0-11 ), and the 6 LEDs on the bottom represent the  minutes ( 0-59 ).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

• The order of output does not matter.
• The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
• The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

【解答】要寻找所有可能的时间。思路并不难找，但是要一次做对很有难度。

• 首先定义一个 Time 类，包含小时和分钟，把时间抽象地表示出来，而且实现 Comparable 接口，便于排序以统一顺序。
• 定义 hours 和 minutes 这两个标记访问情况的数组，接着回溯法去递归寻找所有表示的可能，每一个灯都有“亮”和“不亮”两种情况的考量。
• 特别注意这次的回溯法有点特殊，是需要考虑两个核心目标模型，一个是 hour，一个是 minute。因此需要去重——先算了 hour 再算 minute，或者先算 minute 再算 hour，二者只能取其中之一。这是这道题的重点之一。
• 有一些特殊情况需要考虑，比如 12:00，不应考虑，它应该用 0:00 来表示。

class Solution {
    public List<String> readBinaryWatch(int num) {
        // hour: 2^0 ~ 2^3
        // min: 2^0 ~ 2^5
        boolean[] hours = new boolean[4];
        boolean[] minutes = new boolean[6];

        List<Time> list = iterate(num, new Time(0, 0), 0, 0, hours, minutes);
        List<String> results = new ArrayList<>();
        for (Time time : list) {
            String min = "" + time.minute;
            if (time.minute < 10)
                min = '0' + min;

            results.add(time.hour + ":" + min);
        }
        Collections.sort(results);
        return results;
    }

    private List<Time> iterate(int num, Time time, int fromHourIndex, int fromMinIndex, boolean[] hours, boolean[] minutes) {
        List<Time> list = new ArrayList<>();
        if (num == 0) {
            list.add(time);
            return list;
        }

        for (int i = fromHourIndex; i < hours.length; i++) {
            if (hours[i])
                continue;

            int newHour = time.hour + (int) Math.pow(2, i);
            // 12:00 is not counted
            if (newHour >= 12)
                continue;
            hours[i] = true;
            list.addAll(iterate(num - 1, new Time(newHour, time.minute), i+1, fromMinIndex, hours, minutes));
            hours[i] = false;
        }

        for (int i = fromMinIndex; i < minutes.length; i++) {
            if (minutes[i])
                continue;

            int newMin = time.minute + (int) Math.pow(2, i);
            if (newMin>=60)
                continue;
            
            minutes[i] = true;
            // fromHourIndex = hours.length to avoid duplicates
            list.addAll(iterate(num - 1, new Time(time.hour, newMin), hours.length, i+1, hours, minutes));
            minutes[i] = false;
        }

        return list;
    }
}

class Time implements Comparable<Time> {
    public int hour;
    public int minute;

    public Time(int hour, int minute) {
        this.hour = hour;
        this.minute = minute;
    }

    @Override
    public int compareTo(Time that) {
        int hourDiff = this.hour - that.hour;
        if (hourDiff != 0)
            return hourDiff;

        int minDiff = this.minute - that.minute;
        return minDiff;
    }
}

Remove K Digits

【题目】Given a non-negative integer num represented as a string, remove  k digits from the number so that the new number is the smallest possible.

Note:

• The length of  num  is less than 10002 and will be ≥  k .
• The given  num  does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

【解答】把问题思考清楚，写几个例子寻找思路：

• 从左向右扫描，如果 num 中存在相邻的的两个数字且是递减的，即 num[i-1]>num[i]，那么移除 num[i-1]；
• 如果不存在，删掉最后一个数字。

注意 leading zero 的处理。

class Solution {
    public String removeKdigits(String num, int k) {
        if (num==null || k<0 || k>num.length())
            throw new IllegalArgumentException();
        
        if (k == num.length())
            return "0";
        if (k == 0) {
            if (num.charAt(0) == '0')
                return removeKdigits(num.substring(1), 0);
            else
                return num;
        }
        
        for (int i=0; i<num.length(); i++) {
            if (i>0 && num.charAt(i-1)>num.charAt(i)) { // decreasing found
                return removeKdigits(num.substring(0, i-1) + num.substring(i), k-1);
            }
        }
        
        // no dcreasement found, remove the last digit
        return removeKdigits(num.substring(0, num.length()-1), k-1);
    }
}

Frog Jump

【题目】A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

<b>[0,1,3,5,6,8,12,17]</b>

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

<b>Return true</b>. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

<b>[0,1,2,3,4,8,9,11]</b>

<b>Return false</b>. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

【解答】判断从起点到终点是否可达的问题，而且是一维的，特殊的地方在于，每次可执行的步骤数是 k、k-1 或者 k+1。

看起来似乎不难，就是一个普通的回溯法问题。为了尽量避免重复计算，对于某个状态，无论是有解还是无解，都要把这个结果存起来。但是在逐步抽象模型建立起这个数据结构的时候发现似乎这条路是一条复杂的路，这个数据结构 map 类似于：

<stoneValue, <index, <jump, canCross>>>

• 第一层是一个 HashMap，根据不同的 stoneValue 要找到石头以及相关数据；
• 第二层是一个 TreeMap，key 是 index，因为找到的石头里面需要过滤掉当前和左侧的石头，因此需要用到 higherKey() 方法，即只考虑右侧的石头；
• 第三层是一个 HashMap，jump 为 key；
• 第四层是一个 Boolean，表示给定的 index 和 jump 的情况下，能否 cross。

即便可以做，这就显得很复杂了，map 很少有嵌套那么多层的。

在讨论区有一个简洁清晰的 解法 ，思路是：

建立一个 map：Map<Integer, Set<Integer>>，key 是 stoneValue，value 是从它开始所有可以进行的 jump，也就是说，这里不考虑 index。这个 map 在初始构造的时候，map[0] == [1]，因为从最开始跳一步可以达到它右边的那个石头。除了它以外，其它的 set 都是空的，也就是说只是记录一下 stoneValue。

然后从左到右开始迭代，每一块石头取出来看，都要查看他的 set，即当前所有可以 jump 的可能性，只要没到最后一块石头，就把 jump 放到 set 里面去。

class Solution {
    public boolean canCross(int[] stones) {
        if (stones == null || stones.length == 0) {
            throw new IllegalArgumentException();
        }

        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>(stones.length);
        map.put(0, new HashSet<Integer>());
        map.get(0).add(1);
        for (int i = 1; i < stones.length; i++) {
            map.put(stones[i], new HashSet<Integer>());
        }

        for (int stone : stones) {
            for (int step : map.get(stone)) {
                int reach = step + stone;
                if (reach == stones[stones.length - 1]) {
                    return true;
                }
                
                Set<Integer> set = map.get(reach);
                if (set != null) {
                    if (step - 1 > 0)
                        set.add(step - 1);
                    set.add(step);
                    set.add(step + 1);
                }
            }
        }

        return false;
    }
}

Sum of Left Leaves

【题目】Find the sum of all left leaves in a given binary tree.

Example:

3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values <b>9</b> and <b>15</b> respectively. Return <b>24</b>.

【解答】要求所有左叶子之和。这种二叉树的遍历问题，解法有一定套路，经常出现指针+栈的组合。像这道题，一个指向节点的指针，永远往左下方走；而栈则永远只存放右孩子。如果发现指针指向的节点没有左右孩子了，那就是找到左叶子了；如果左孩子为空，那就出栈一次。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null)
            return 0;
        
        int sum = 0;
        // always keep cur pointing to left child,
        // because right child would never be a left leave
        TreeNode cur = root.left;
        
        // always put right child to the queue
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if (root.right != null)
            queue.add(root.right);
        
        while (cur != null || queue.peek() != null) {
            if (cur != null) {
                if (cur.left == null && cur.right == null) { // leaf
                    sum += cur.val;
                    cur = null;
                } else {
                    if (cur.right != null)
                        queue.add(cur.right);
                    cur = cur.left;
                }
            } else {
                TreeNode node = queue.poll();
                cur = node.left;
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        
        return sum;
    }
}

Convert a Number to Hexadecimal

【题目】Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

1. All letters in hexadecimal ( a-f ) must be in lowercase.
2. The hexadecimal string must not contain extra leading  0 s. If the number is zero, it is represented by a single zero character  '0' ; otherwise, the first character in the hexadecimal string will not be the zero character.
3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
4. You  must not use  any  method provided by the library  which converts/formats the number to hex directly.

Example 1:

Input:
26

Output:
"1a"

Example 2:

Input:
-1

Output:
"ffffffff"

【解答】转十六进制数。对于正数来说，没有什么难的。关键是负数，要使用补码的方法。如果是二进制，那就在非符号位上面取反加一，现在十六进制呢？其实可以一样操作，本身十六进制也是由 4 个二进制数联合构成的。如果要对十六进制数直接取反加一也可以，和二进制类似：二进制数 x 取反是 1-x，十六进制数 x 就是 15-x。加一的操作发生在个位。

class Solution {
    public String toHex(int num) {
        if (num==0)
            return "0";
        
        String result = "";
        long number = num + 0l;
        if (num<0)
            number = -number;
        
        while (number>0) {
            long quotient = number / 16;
            int mod = (int)(number % 16);
            result = toHexSingleDigit(mod) + result;
            number = quotient;
        }
        
        if (num<0)
            result = toComplement(result);
        return result;
    }
    
    private char toHexSingleDigit(int num) {
        if (num < 10)
            return (char)('0' + num);
        else
            return (char)('a' + (num-10));
    }
    
    private String toComplement(String s) {
        int len = s.length();
        for (int i=0; i<8-len; i++) {
            s = '0' + s;
        }
        
        String result = "";
        boolean carry = false;
        for (int i=7; i>=0; i--) {
            char ch = s.charAt(i);
            int num;
            if (ch >='0' && ch <= '9')
                num = ch - '0';
            else
                num = ch - 'a' + 10;
            
            num = 15 - num;
            if (i==7 || carry)
                num++;
            if (num == 16) {
                carry = true;
                num = num - 16;
            } else {
                carry = false;
            }
            
            result = toHexSingleDigit(num) + result;
        }
        return result;
    }
}

Queue Reconstruction by Height

【题目】Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k) , where  h is the height of the person and  k is the number of people in front of this person who have a height greater than or equal to  h . Write an algorithm to reconstruct the queue.

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

【解答】排序题。这道题目如果拿到以后去考虑怎样实现 Comparable 接口或者实现一个 Comparator 比较类，然后调用 Collections.sort()，那就踏上不归路了。因为单纯地拿出任意两个数来，比如 [7,1] 和 [4,4]，是无法判断谁在前面的，就因为这一点，一般的排序方式不再好用。

换一个思路，尽量先按照某个规则把整体顺序预置妥当，再利用插入排序的思想，逐渐构造出满足要求的序列来，这种方式在任意时间，构造的序列都是符合题意规则的。而且最重要的一点是，整个插入的过程，由于所取的元素是相等或者逐渐减小的，因此可以保证无论插入在结果集中的哪个位置，都对已有结果元素的合法性不产生任何影响。这个思路这个题目最关键的一点，剩下的都是“常规操作”。

首先按照身高从高到矮排序，如果高矮相等，按照第二个参数的大小，从小到大排序。排完序的链表作为源数据。

定义结果集 result，在循环中把确定的结果插入到 result 中去。由于源数据是按照高度有序的，因此每次从中取出的元素都是相比结果集中的的元素相等身高或者更矮一些，正是因为如此，根据它对元素的第二维上的要求，从左往右找到位置插进去，根本不用担心插入位置对于结果集中已有元素的影响。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if (people==null || people.length==0)
            return people;
        
        List<int[]> list = new LinkedList<>();
        for (int[] person : people) {
            list.add(person);
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] left, int[] right) {
                int diff = left[0] - right[0];
                if (diff!=0)
                    return -diff;
                else
                    return left[1] - right[1];
            }
        });
        
        List<int[]> result = new ArrayList<>();
        int start = 0;
        int end = 0;
        Integer height = null;
        while(start<list.size() && end<list.size()) {
            if (height==null) {
                height = list.get(end)[0];
                end++;
            } else {
                if (list.get(end)[0]==height) {
                    end++;
                } else {
                    insert(list, start, end, result);
                    start = end;
                    height = null;
                }
            }
        }
        
        insert(list, start, end, result);
        int[][] arr = new int[people.length][];
        for (int i=0; i<result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }
    
    // [start, end)
    private void insert(List<int[]> list, int start, int end, List<int[]> result) {
        while (start<end) {
            int[] item = list.get(start);
            result.add(item[1], item);
            start++;
        }
    }
}

Trapping Rain Water II

【题目】Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:

Both m and  n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

【解答】之前用双指针的方法解过一维的积雨水问题，现在是二维的。某种程度上二者有类似的思路。整个二维图形的最外圈是无法积水的，并且注意到，四个角上的元素，无论高度是多少，都对积水能力没有任何影响。当这个外圈固定下来，就可以从外圈上最矮的那一点 P 开始，考察它四周的位置，凡是没有考察过的新位置，都是考虑可以储水的，但是必须要比这个 P 点更矮；如果更高，那虽然这个点没法储水，但是从下一轮开始的循环中，它的高度潜在拔高了最矮的点 P。具体说：

• 初始操作：
  • 建立一个 visitedMap（或者重用 heightMap）来标记该位置是否已经访问过；
  • 建立一个最小堆 heap 用来标记考察区域的外边界，把 heightMap 最靠外的这一圈放到 heap 里面去，同时更新 visitedMap（注意：heightMap 的四个角预先标记为“访问过”，且不放入 heap，因为它们不对存水产生任何影响）。
•  循环操作：
  • 每次都从 heap 中取最小值（最小堆）p，并拿它的高度和当前的存水阈值比较，取较大的一个作为新的阈值；
  • 考察 p 的上下左右四个元素，如果没有访问过，就记录下它的存水量，标记访问过，并存入 heap；
  • 反复操作，直到 heap 为空。

class Solution {
    private Item load(int[][] heightMap, int x, int y) {
        if (x<0 || y<0 || x>=heightMap.length || y>=heightMap[0].length || heightMap[x][y]<0)
            return null;
        Item item = new Item(x, y, heightMap[x][y]);
        heightMap[x][y] = -1;
        return item;
    }
    
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null)
            throw new IllegalArgumentException();
        if (heightMap.length<=2 || heightMap[0].length<=2)
            return 0;
        
        int total = 0;
        Queue<Item> heap = new PriorityQueue<>();
        // top and bottom row
        for (int i=1; i<heightMap[0].length-1; i++) {
            heap.add(this.load(heightMap, 0, i));
            heap.add(this.load(heightMap, heightMap.length-1, i));
        }
        // left and right column
        for (int i=1; i<heightMap.length-1; i++) {
            heap.add(this.load(heightMap, i, 0));
            heap.add(this.load(heightMap, i, heightMap[0].length-1));
        }
        // mark the four corners visited
        heightMap[0][0] = -1;
        heightMap[0][heightMap[0].length-1] = -1;
        heightMap[heightMap.length-1][0] = -1;
        heightMap[heightMap.length-1][heightMap[0].length-1] = -1;
        
        int threshold = heap.peek().h;
        while (!heap.isEmpty()) {
            Item item = heap.poll();
            // the threshold would never get smaller
            threshold = Math.max(threshold, item.h);
            
            Item up = this.load(heightMap, item.x-1, item.y);
            Item down = this.load(heightMap, item.x+1, item.y);
            Item left = this.load(heightMap, item.x, item.y-1);
            Item right = this.load(heightMap, item.x, item.y+1);
            
            if (up != null) {
                if (up.h < threshold)
                    total += threshold - up.h;
                heap.offer(up);
            }
            if (down != null) {
                if (down.h < threshold)
                    total += threshold - down.h;
                heap.offer(down);
            }
            if (left != null) {
                if (left.h < threshold)
                    total += threshold - left.h;
                heap.offer(left);
            }
            if (right != null) {
                if (right.h < threshold)
                    total += threshold - right.h;
                heap.offer(right);
            }
        }
        
        return total;
    }
}

class Item implements Comparable<Item> {
    public int x;
    public int y;
    public int h;
    
    public Item(int x, int y, int h) {
        this.x = x;
        this.y = y;
        this.h = h;
    }
    
    @Override
    public String toString() {
        return "[" + this.x + ", " + this.y + "]: " + this.h;
    }
    
    @Override
    public int compareTo(Item other) {
        return this.h - other.h;
    }
}

Longest Palindrome

【题目】Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:

Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

【解答】问能构建最长的回文串。对于偶数回文串，所有字符都是成对出现的；但是对于奇数回文串，允许有一个特殊字符出现奇数次。

class Solution {
    public int longestPalindrome(String s) {
        boolean[] chars = new boolean[52];
        int count = 0;
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            int index;
            if (ch >= 'A' && ch <= 'Z') {
                index = ch - 'A' + 26;
            } else {
                index = ch - 'a';
            }
            if (chars[index]) {
                chars[index] = false;
                count += 2;
            } else {
                chars[index] = true;
            }
        }
        
        for (int i=0; i<52; i++) {
            if (chars[i])
                return count + 1;
        }
        return count;
    }
}

Split Array Largest Sum

【题目】Given an array which consists of non-negative integers and an integer m , you can split the array into  m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these  m subarrays.

Note:

If  n is the length of array, assume the following constraints are satisfied:

• 1 ≤  n  ≤ 1000
• 1 ≤  m  ≤ min(50,  n )

Examples:

Input:
<b>nums</b> = [7,2,5,10,8]
<b>m</b> = 2

Output:
18

Explanation:
There are four ways to split <b>nums</b> into two subarrays.
The best way is to split it into <b>[7,2,5]</b> and <b>[10,8]</b>,
where the largest sum among the two subarrays is only 18.

【解答】要把数组分成 m 份，并且让各份的和的最大值尽量小。

一开始我的反应是先尝试贪心这条路，但是发现不好走。因为很难找到一个特定的规则下结论说，符合条件了，这就是最优解的一部分。接着就想那退一步，能不能用动态规划，这条路依然不好走，因为原始问题和子问题的关系并不是清晰。

这样的情况下，似乎执着于分析问题本身的性质来寻找最优解的大致方向不正确。于是开始考虑能否反过来，从结论出发，去“猜”一个解，再反过来去验证它是不是真正的最优解。但是要猜，不能胡猜，这个最优解的下界是所有数中最大的一个，上界是所有数之和。接下去，借用二分查找的方式，找到这个最优解。

求和的时候为防止溢出，使用 long 代替 int。

class Solution {
    public int splitArray(int[] nums, int m) {
        long left = 0;
        long right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        
        int largestSum = (int) right;
        while (left <= right) {
            long mid = (left+right) / 2;
            int subArrNum = m;
            long sum = 0;
            for (int num : nums) {
                // no need to continue the loop
                if (subArrNum == 0) {
                    break;
                }
                
                if (sum + num <= mid) {
                    sum += num;
                } else {
                    sum = num;
                    // a new sub array is required
                    subArrNum--;
                }
            }
            
            // make sure every time left or right moves
            if (subArrNum > 0) {
                right = mid - 1;
                largestSum = (int) mid;
            } else {
                left = mid + 1;
            }
        }
        
        return largestSum;
    }
}

Fizz Buzz

【题目】Write a program that outputs the string representation of numbers from 1 to n .

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

【解答】没有太多可说的，注意数字是从 1 开始，而不是 0.

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        for (int i=0; i<n; i++) {
            int num = i+1;
            String s = null;
            if (num%3==0 && num%5==0)
                s = "FizzBuzz";
            else if (num%3==0)
                s = "Fizz";
            else if (num%5==0)
                s = "Buzz";
            else
                s = "" + num;
            
            list.add(s);
        }
        
        return list;
    }
}

Arithmetic Slices

【题目】A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:

A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

【解答】统计所有满足题目要求的子串的数量。理解题意后，发现只需要看连续两个数的差值，并且只关心同一个差值连续出现的次数，而根本不需要关心每个元素的值本身。发现这一点可以大大简化题目。

比如这样的差值数列，和连续出现的次数，以及结果的关系：

3, 3 => 2 times => result is 1
3, 3, 3 => 3 times => result is 2 + 1
3, 3, 3, 3 => 4 times => result is 3 + 2 + 1
… => x times => result is ((x-1) + 1) * (x-1) / 2

也就是说，如果给定一个长度为 x 的 arithmetic slice，它本身包含了 result is ((x-1) + 1) * (x-1) / 2 这么多个隐含的 arithmetic slice。所以，只需要寻找这样的连续子串，其中相邻两两元素的差值相等，它尽可能长，然后对于每个子串套用上面的公式即可。

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if (A==null)
            throw new IllegalArgumentException();
        if (A.length<3)
            return 0;
        
        List<Integer> diffs = new ArrayList<>();
        int diff = A[1] - A[0];
        int count = 1; // diff count
        int total = 0; // result
        for (int i=2; i<A.length; i++) {
            if (A[i] - A[i-1] == diff) {
                count++;
            } else {
                if (count > 1) {
                    total += ((count-1) + 1) * (count-1) / 2;
                }
                diff = A[i] - A[i-1];
                count = 1;
            }
        }
        
        if (count > 1) {
            total += ((count-1) + 1) * (count-1) / 2;
        }
        
        return total;
    }
}

Third Maximum Number

【题目】Given a non-empty array of integers, return the  third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

<b>Input:</b> [3, 2, 1]

<b>Output:</b> 1

<b>Explanation:</b> The third maximum is 1.

Example 2:

<b>Input:</b> [1, 2]

<b>Output:</b> 2

<b>Explanation:</b> The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

<b>Input:</b> [2, 2, 3, 1]

<b>Output:</b> 1

<b>Explanation:</b> Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

【解答】返回第三大的数。注意去重。

class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0)
            throw new IllegalArgumentException();
        
        Queue<Integer> heap = new PriorityQueue<>(nums.length, new Comparator<Integer>(){
            @Override
            public int compare(Integer left, Integer right) {
                // no dup so no need to cover right == left
                return right > left ? 1 : -1;
            }
        });
        
        for (int num : nums) {
            if (!heap.contains(num))
                heap.add(num);
        }
        
        if (heap.size() < 3)
            return heap.poll();
        
        int countDown = 3;
        int number = 0;
        while (countDown > 0) {
            number = heap.poll();
            countDown --;
        }
        
        return number;
    }
}

Add Strings

【题目】Given two non-negative integers num1 and  num2 represented as string, return the sum of  num1 and  num2 .

Note:

1. The length of both  num1  and  num2  is < 5100.
2. Both  num1  and  num2  contains only digits  0-9 .
3. Both  num1  and  num2  does not contain any leading zero.
4. You  must not use any built-in BigInteger library  or  convert the inputs to integer  directly.

【解答】相加两个用 string 表示的数。

class Solution {
    public String addStrings(String num1, String num2) {
        int carry = 0;
        int idx = 0;
        String result = "";
        while (idx < num1.length() || idx < num2.length()) {
            int num = carry;
            if (idx < num1.length())
                num += num1.charAt(num1.length()-1-idx) - '0';
            if (idx < num2.length())
                num += num2.charAt(num2.length()-1-idx) - '0';
            
            if (num >= 10) {
                num -= 10;
                carry = 1;
            } else {
                carry = 0;
            }
            
            result = num + result;
            idx ++;
        }
        
        if (carry>0)
            result = carry + result;
        
        return result;
    }
}