LeetCode付费题目(一)

LeetCode 300题以内需要付费才能查看的所有题目解答。

156
157
158
159
161
163
170
186
243
244
245
246
247
248
249
250
251
252
253
254
255
256
259
261
265
266
267
269
270
271
272
276
277
280
281
285
286
288
291
293
294
296
298

Binary Tree Upside Down

【题目】Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example: Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1

【解答】把题目中的树拆成好多个小三角形来分别看,比如2-4-5这个三角形,调整的三部曲:

  1. 把2->4的路径反向,
  2. 2->5的路径切断,
  3. 然后建立4->5的路径。

把这个过程看清楚以后,题目就不难了,代码写法上整体看很像中序遍历。

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode head = null;
        TreeNode cur = root;

        // reach to the most left node
        while (cur!=null && cur.left!=null) {
            stack.push(cur);
            cur = cur.left;
        }

        while (cur!=null && !stack.isEmpty()) {
            TreeNode parent = stack.pop();
            TreeNode right = parent.right;

            if (head==null) {
                head = cur;
            }

            cur.left = right;
            cur.right = parent;

            if (right!=null) {
                right.left = null;
                right.right = null;
            }

            cur = parent;
        }

        if (cur!=null) {
            cur.left = null;
            cur.right = null;
        }

        if (head==null)
            head = cur;

        return head;
    }
}

Read N Characters Given Read4

【题目】The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function will only be called once for each test case.

【解答】用一个循环来往buf里面写数据,注意三种case:

  1. n先达到
  2. buf.length先达到
  3. read4单次读到的数据小于4个字符

这三种情况都表示需要结束本次读取过程。

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        char[] b = new char[4];
        int pos = 0;
        while (true) {
            int rest = n-pos;
            if (rest==0) // case 1
                return pos;

            int s = read4(b);
            if (s==0) // case 2
                return pos;

            int copySize = s;
            if (pos+s>n)
                copySize = n - pos;

            System.arraycopy(b, 0, buf, pos, copySize);
            pos = pos+copySize;

            if (copySize<4) // case 3
                break;
        }

        return pos;
    }
}

Read N Characters Given Read4 II – Call multiple times

【题目】The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function may be called multiple times.

【解答】这道题的关键在于怎么样给条件归类从而简化逻辑。看起来似乎不复杂,但是有很多需要考虑的要素:

  1. read方法的buf长度决定了该方法读取数据的量不可能超过它;
  2. read方法的参数n也决定了该方法读取数据的量不可能超过它;
  3. read4方法可能读不到足够的数据,这种情况下读取数据的量不可能超过它;
  4. 需要考虑前一次读取完毕之后,可能会有剩余,那么在这次读取的时候,需要优先消费这个剩余量。

上面这几点里面,#1和#2可以合并成一个复合条件;对于#3,在读取不到足够数据的时候,跳出读取循环;而对于#4,考虑引入一个queue,任何情况下数据都从这个queue中取,而如果这个queue为空,就考虑调用read4方法来补充数据,之后再从这个queue中取数据——这样逻辑就得到简化了。

public class Solution extends Reader4 {
    private Queue<Character> queue = new LinkedList<>();
    private char[] buffer = new char[4];

    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        int pos = 0;
        while (n>0 && pos<buf.length) {
            if (!queue.isEmpty()) {
                buf[pos++] = queue.poll();
                n--;
                continue;
            }

            int count = read4(buffer);
            if (count==0) break;
            for (int i=0; i<count; i++) {
                queue.add(buffer[i]);
            }
        }

        return pos;
    }
}

Longest Substring with At Most Two Distinct Characters

【题目】Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is “ece” which its length is 3.

【解答】最多两个distinct字符的最长子串。这道是经典的双指针问题,一快一慢,快指针来探路,用一个map来记录当前的所有字符,只要map的大小小于等于2就走快指针;慢指针用来处理当map大小大于2的情况下,不断右移动并吐出字符,直到map大小恢复到2。

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s==null || s.length()==0)
            return 0;

        Map<Character, Integer> map = new HashMap<>();
        int slow = 0, fast = 0;
        int longest = 0;
        while(fast<s.length()) {
            char cf = s.charAt(fast);
            if (!map.containsKey(cf))
                map.put(cf, 0);
            map.put(cf, map.get(cf)+1);

            while (map.size()>2) {
                char cs = s.charAt(slow);
                map.put(cs, map.get(cs)-1);
                if (map.get(cs)==0)
                    map.remove(cs);
                slow++;
            }

            longest = Math.max(longest, fast-slow+1);
            fast++;
        }

        return longest;
    }
}

 

class TwoSum {
    private List<Integer> nums = new ArrayList<>();
    
    /** Initialize your data structure here. */
    public TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (nums.isEmpty()) {
            nums.add(number);
            return;
        }
        
        int l=0, r=nums.size()-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (nums.get(mid)==number) {
                nums.add(mid, number);
                return;
            } else if (nums.get(mid)<number) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        if (l<nums.size())
            nums.add(l, number);
        else
            nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int l=0, r=nums.size()-1;
        while (l<r) {
            int sum = nums.get(l) + nums.get(r);
            if (sum==value)
                return true;
            else if (sum<value)
                l++;
            else
                r--;
        }
        
        return false;
    }
}

One Edit Distance

【题目】Given two strings S and T, determine if they are both one edit distance apart.

【解答】抓住题目的关键,有且只有一个edit distance,所以,总共就两种可能,一种是S和T相同的长度,那么与其内部只有一个字符不同;另一个是S和T长度差别只有1,为了便于简化代码逻辑,当T长度小于S的时候交换S和T的位置再计算。

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s==null || t==null)
            return false;
        
        if (t.length()>s.length())
            return isOneEditDistance(t, s);
        
        if (s.length()-t.length()>1)
            return false;
        
        int p=0, q=0;
        boolean mismatch = false;
        while(p<s.length()) {
            if (q==t.length())
                return !mismatch;
            
            char cp = s.charAt(p);
            char cq = t.charAt(q);
            
            if (cp!=cq) {
                if (mismatch)
                    return false;
                
                mismatch = true;
                
                if (s.length()>t.length()) {
                    p++;
                    continue;
                }
            }
            
            p++;
            q++;
        }
        
        return mismatch;
    }
}

Missing Ranges

【题目】Given a sorted integer array where the range of elements are in the inclusive range [lowerupper], return its missing ranges.

For example, given [0, 1, 3, 50, 75]lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

【解答】处理好首尾的情况,因为首尾的点可能在给定的数组范围内,也可能在范围外。

class Solution {
    public List<String> findMissingRanges(int[] nums, int lo, int up) {
        long lower = (long) lo;
        long upper = (long) up;
        
        if (upper<lower || nums==null)
            throw new IllegalArgumentException();
        
        List<String> result = new ArrayList<>();
        if (nums.length==0) {
            String empty = gen(lower-1, upper+1);
            result.add(empty);
            return result;
        }
        
        for (int i=0; i<nums.length; i++) {
            long num = (long) nums[i];
            
            if (i==0) {
                String first = gen(lower-1, Math.min(num, upper+1));
                if (first != null)
                    result.add(first);
            } else {
                String item = gen(Math.max(lower-1, (long)nums[i-1]), Math.min(num, upper+1));
                if (item != null)
                    result.add(item);
            }
            
            if (i==nums.length-1) {
                String last = gen(Math.max(lower-1, num), upper+1);
                if (last != null)
                    result.add(last);
            }
        }
        
        return result;
    }
    
    private String gen(long l, long r) {
        if (l>=r-1)
            return null;
        
        if (l==r-2) {
            return "" + (r-1);
        } else {
            return (l+1) + "->" + (r-1);
        }
    }
}

Two Sum III – Data structure design

【题目】Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

【解答】数据结构的设计,这里有一个权衡,而具体需求题目并未说清楚。

  • 要么牺牲add方法,即让find方法获得O(1)的时间复杂度,但是add方法时间复杂度会相对较高;
  • 要么牺牲find方法,即让add方法获得O(1)的时间复杂度,但是find方法时间复杂度会相对较高。

我把这两种方法都放在下面,但是只有后一种方法能够跑通性能测试用例。

方法一,find方法时间复杂度为O(1):

class TwoSum2 {
    private Set<Integer> nums = new HashSet<>();
    private Set<Integer> results = new HashSet<>();
    
    /** Initialize your data structure here. */
    public TwoSum2() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        for (int num : nums) {
            results.add(number + num);
        }
        
        nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        return results.contains(value);
    }
}

方法二,add方法时间复杂度为O(1):

class TwoSum {
    private List<Integer> nums = new ArrayList<>();
    
    /** Initialize your data structure here. */
    public TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (nums.isEmpty()) {
            nums.add(number);
            return;
        }
        
        int l=0, r=nums.size()-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (nums.get(mid)==number) {
                nums.add(mid, number);
                return;
            } else if (nums.get(mid)<number) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        if (l<nums.size())
            nums.add(l, number);
        else
            nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int l=0, r=nums.size()-1;
        while (l<r) {
            int sum = nums.get(l) + nums.get(r);
            if (sum==value)
                return true;
            else if (sum<value)
                l++;
            else
                r--;
        }
        
        return false;
    }
}

Reverse Words in a String II

【题目】Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Could you do it in-place without allocating extra space?

【解答】这个题目很常规,先尝试字符串整体反转,然后再给每个单词单独反转:

class Solution {
    public void reverseWords(char[] str) {
        if (str==null || str.length==0)
            return;
        
        int p=0, q=str.length-1;
        reverse(str, p, q);
        
        p=0; q=0;
        while(q<=str.length) {
            if (q==str.length-1 || str[q+1]==' ') {
                reverse(str, p, q);
                q = q+2;
                p = q;
                continue;
            }
            
            q++;
        }
    }
    
    private void reverse(char[] str, int p, int q) {
        while(p<q) {
            swap(str, p, q);
            p++;
            q--;
        }
    }
    
    private void swap(char[] str, int p, int q) {
        char temp = str[p];
        str[p] = str[q];
        str[q] = temp;
    }
}

Shortest Word Distance

【题目】Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”word2 = “practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

【解答】找两个单词的最近距离,用一个map存储单词的位置,key为单词本身,value可以用TreeSet,也可以用Heap来存放位置集合,这样value的元素是有序的,比较容易找最近距离:

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        Map<String, TreeSet<Integer>> map = new HashMap<>();
        for (int i=0; i<words.length; i++) {
            TreeSet<Integer> ts = map.getOrDefault(words[i], new TreeSet<>());
            ts.add(i);
            map.put(words[i], ts);
        }
        
        TreeSet<Integer> ts1 = map.get(word1);
        TreeSet<Integer> ts2 = map.get(word2);
        
        Iterator<Integer> it1 = ts1.iterator();
        Iterator<Integer> it2 = ts2.iterator();
        int v1 = it1.next();
        int v2 = it2.next();
        int min = Math.abs(v1-v2);
        
        while(it1.hasNext() || it2.hasNext()) {
            if (min==0)
                return 0;
            
            if (v1<v2) {
                if (!it1.hasNext()) {
                    return min;
                } else {
                    v1 = it1.next();
                    min = Math.min(min, Math.abs(v1-v2));
                }
            } else {
                if (!it2.hasNext()) {
                    return min;
                } else {
                    v2 = it2.next();
                    min = Math.min(min, Math.abs(v1-v2));
                }
            }
        }
        
        return min;
    }
}

Shortest Word Distance II

【题目】This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”word2 = “practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

【解答】解法和上面那道一样,略。

Shortest Word Distance III

【题目】This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”word2 = “coding”, return 1.
Given word1 = "makes"word2 = "makes", return 3.

Note:
You may assume word1 and word2 are both in the list.

【解答】其实解法还是可以基本一样,只需要单独处理word1和word2相同的情况而已。不过上面说了,这个map的value可以是TreeSet,也可以是堆,既然上面用了TreeSet,下面用堆来做一下吧(堆的实现在Java中是优先级队列):

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        Map<String, PriorityQueue<Integer>> map = new HashMap<>();
        for (int i=0; i<words.length; i++) {
            String word = words[i];
            PriorityQueue<Integer> pq = map.getOrDefault(word, new PriorityQueue<>());
            pq.add(i);
            map.put(word, pq);
        }
        
        PriorityQueue<Integer> pq1 = map.get(word1);
        PriorityQueue<Integer> pq2 = map.get(word2);
        
        int min = Integer.MAX_VALUE;
        if (word1.equals(word2)) {
            Integer last = null;
            for (int v : pq1) {
                if (last==null) {
                    last = v;
                } else {
                    min = Math.min(min, v-last);
                    last = v;
                }
            }
            
            return min;
        }
        
        Integer l1 = pq1.poll();
        Integer l2 = pq2.poll();
        while(!pq1.isEmpty() || !pq2.isEmpty()) {
            if (l2>l1) {
                min = Math.min(l2-l1, min);
                if (!pq1.isEmpty())
                    l1 = pq1.poll();
                else
                    return min;
            } else {
                min = Math.min(l1-l2, min);
                if (!pq2.isEmpty())
                    l2 = pq2.poll();
                else
                    return min;
            }
        }
        
        return Math.min(min, Math.abs(l2-l1));
    }
}

Strobogrammatic Number

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers “69″, “88″, and “818″ are all strobogrammatic.

【解答】这个题目的关键在于找strobogrammatic这种数可能的组合,仔细思考以后,发现就这么几种:11,88, 00, 69,96。

class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num==null || num.length()==0)
            return false;
        
        int l=0, r=num.length()-1;
        while(l<=r) {
            int lnum = num.charAt(l)-'0';
            int rnum = num.charAt(r)-'0';
            
            if (!isStrobogrammatic(lnum, rnum))
                return false;
            
            l++;
            r--;
        }
        
        return true;
    }
    
    private boolean isStrobogrammatic(int l, int r) {
        if (l==1 && r==1)
            return true;
        if (l==8 && r==8)
            return true;
        if (l==6 && r==9 || l==9 && r==6)
            return true;
        if (l==0 && r==0)
            return true;
        
        return false;
    }
}

Strobogrammatic Number II

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].

【解答】有了前面题目的积累,这个题目可以考虑构造法而不是采用搜索法。即我们已经知道n位的数怎样构造才能组成满足题目的数。通常能构造的时候,可以不要使用搜索,因为搜索的复杂度比构造高

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        if (n<=0) return result;
        
        fs("", n, result);
        
        return result;
    }
    
    private void fs(String x, int n, List<String> result) {
        if (n==0) {
            if (x.length()!=0) {
                if (x.startsWith("0") && !x.equals("0"))
                    return;
                
                result.add(x);
            }
            
            return;
        }
        
        if (n%2==1) {
            fs("1", n-1, result);
            fs("8", n-1, result);
            fs("0", n-1, result);
        } else {
            fs("1"+x+"1", n-2, result);
            fs("8"+x+"8", n-2, result);
            fs("0"+x+"0", n-2, result);
            
            fs("6"+x+"9", n-2, result);
            fs("9"+x+"6", n-2, result);
        }
        
    }
}

Strobogrammatic Number III

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = “50″, high = “100″, return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

【解答】和上题相比更进一步,现在要找一个范围内所有的strobogrammatic数。我们可以继续使用构造法,但是需要判断数是不是在要求的范围内。

class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int sl = low.length();
        int sh = high.length();
        
        int count = 0;
        for (int i=sl; i<=sh; i++) {
            count += sr(low, high, "", i);
        }
        
        return count;
    }
    
    private int sr(String low, String high, String str, int i) {
        int ll = low.length();
        int hl = high.length();
        
        if (i==0) {
            if (str.length()==ll && str.compareTo(low)<0)
                return 0;
            if (str.length()==hl && str.compareTo(high)>0)
                return 0;
            
            if (str.startsWith("0") && !str.equals("0"))
                return 0;
            
            return 1;
        }
        
        int count = 0;
        if (i%2==1) {
            count += sr(low, high, "0", i-1);
            count += sr(low, high, "1", i-1);
            count += sr(low, high, "8", i-1);
        } else {
            count += sr(low, high, "0"+str+"0", i-2);
            count += sr(low, high, "1"+str+"1", i-2);
            count += sr(low, high, "8"+str+"8", i-2);
            
            count += sr(low, high, "9"+str+"6", i-2);
            count += sr(low, high, "6"+str+"9", i-2);
        }
        
        return count;
    }
}

Group Shifted Strings

【题目】Given a string, we can “shift” each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep “shifting” which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
A solution is:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

【解答】关键是处理好ba这种后面的字符字母序小于前面字符的情况。用一个map来给他们归类,key为相邻两个字符间的距离。

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<List<Integer>, List<String>> map = new HashMap<>();
        for (String str : strings) {
            List<Integer> list = new ArrayList<>(str.length()-1);
            Character last = null;
            for (int i=0; i<str.length(); i++) {
                Character ch = str.charAt(i);
                if (last==null) {
                    last = ch;
                } else {
                    int diff = ch - last;
                    if (ch<last) {
                        diff = ('z'-last) + (ch-'a') + 1;
                    }
                    
                    list.add(diff);
                    last = ch;
                }
            }
            
            List<String> strs = map.getOrDefault(list, new ArrayList<>());
            strs.add(str);
            map.put(list, strs);
        }
        
        return new ArrayList<>(map.values());
    }
}

Count Univalue Subtrees

【题目】Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

 

return 4.

【解答】定义一个类Res,用来存放两个信息,一个是树是否是univalue的,一个是该树往下包含的univalue的树有多少个。这样就可以用递归来解了:

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        if (root==null) return 0;
        
        return count(root).count;
    }
    
    private Res count(TreeNode root) {
        int count = 0;
        boolean isUS = true;
        if (root.left!=null) {
            Res left = count(root.left);
            if (!left.isUS || root.val!=root.left.val)
                isUS = false;
            
            count += left.count;
        }
        if (root.right!=null) {
            Res right = count(root.right);
            if (!right.isUS || root.val!=root.right.val)
                isUS = false;
            
            count += right.count;
        }
        
        if (isUS)
            count++;
        
        return new Res(count, isUS);
    }
}

class Res {
    int count;
    boolean isUS;
    
    public Res(int count, boolean isUS) {
        this.count = count;
        this.isUS = isUS;
    }
}

Flatten 2D Vector

【题目】Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

【解答】只有二维,那问题就不麻烦,用两个指针,一个p,一个q,分别指向第一维的位置和第二维的位置。定一个一个check方法,用来保持指针指向的位置是有意义的。

public class Vector2D implements Iterator<Integer> {
    private List<List<Integer>> lists = null;
    private Integer p = null;
    private Integer q = null;
    
    public Vector2D(List<List<Integer>> vec2d) {
        this.lists = vec2d;
    }

    @Override
    public Integer next() {
        int toReturn = lists.get(p).get(q);
        q++;
        check();
        
        return toReturn;
    }

    @Override
    public boolean hasNext() {
        if (p==null) {
            if (lists==null || lists.isEmpty())
                return false;
            p = 0;
        }
        
        if (q==null) {
            q = 0;
            check();
        }
        
        return p!=lists.size();
    }
    
    private void check() {
        while (p!=lists.size()) {
            List list = lists.get(p);
            if (list==null || q>=list.size()) {
                p++;
                q=0;
            } else {
                return;
            }
        }
        
        return;
    }
}

Meeting Rooms

【题目】Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

【解答】先根据start时间排序,然后从小到大遍历,如果发现重叠的情况,就返回false。

class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval l, Interval r) {
                return l.start - r.start;
            }
        });
        
        Integer lastEnd = null;
        for (Interval it : intervals) {
            if (lastEnd==null) {
                lastEnd = it.end;
            } else {
                if (it.start<lastEnd)
                    return false;
                
                lastEnd = it.end;
            }
        }
        
        return true;
    }
}

Meeting Rooms II

【题目】Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

【解答】把每个时间段拆成两个点,分别为开始点和结束点。然后把所有的点排序,要求时间点早的放在前,如果时间点一样,把表示结束的点放在前。接着就可以遍历并计数了:

class Iter {
    int val;
    boolean start;
    public Iter(int val, boolean start) {
        this.val = val;
        this.start = start;
    }
}
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        List<Iter> list = new ArrayList<>(intervals.length * 2);
        for (Interval inter : intervals) {
            Iter start = new Iter(inter.start, true);
            Iter end = new Iter(inter.end, false);
            list.add(start);
            list.add(end);
        }
        
        Collections.sort(list, new Comparator<Iter>() {
            @Override
            public int compare(Iter l, Iter r) {
                if (l.val==r.val) {
                    if ((l.start && r.start) || (!l.start && !r.start))
                        return 0;
                    else if (l.start)
                        return 1;
                    else
                        return -1;
                } else {
                    return l.val - r.val;
                }
            }
        });
        
        int count = 0;
        int max = 0;
        for (Iter it : list) {
            if (it.start) {
                count++;
                max = Math.max(max, count);
            } else {
                count--;
            }
        }
        
        return max;
    }
}

Factor Combinations

【题目】Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

  1. You may assume that n is always positive.
  2. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

【解答】这类找所有组合的题目,通常可以优先考虑(1)排列组合方法能不能解,(2)其它构造法能不能解,不能的话可以用回溯法,那样的话就是一个常规问题了。回溯法的时候这里用一个list来记录走到某状态的时候,之前生成的路径,可以不断维护这个状态list,这样就避免了一大堆“new ArrayList”的代码。有些题目用回溯法解的时候,我们使用一个“visited”数组,原理是类似的。

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        cal(n, new ArrayList<>(), result);
        return result;
    }
    
    private void cal(int n, List<Integer> list, List<List<Integer>> result) {
        if (n==1) {
            if (list.size()>1) {
                List<Integer> copy = new ArrayList<>(list);
                result.add(copy);
            }
            
            return;
        }
        
        int last = 2;
        if (!list.isEmpty())
            last = list.get(list.size()-1);
        for (int i=last; i<=n; i++) {
            if (n%i==0) {
                list.add(i);
                cal(n/i, list, result);
                list.remove(list.get(list.size()-1));
            }
        }
    }
}

Verify Preorder Sequence in Binary Search Tree

【题目】Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?

【解答】首先我考虑用递归来解,要求常数空间复杂度,就定义一个start和end的组合来表示区间,在区间内满足如下条件的数列为合法的二叉搜索树:

  • 第一个数是根,接着往后遍历,前半段的数必须小于它(左子树),一旦发现某个数大于它了,表示后半段开始了(右子树),但是在后半段里面发现又有数小于根,就是非法了,否则为合法。
  • 对左子树和右子树继续如上检查。

代码不复杂:

class Solution2 {
    public boolean verifyPreorder(int[] preorder) {
        return verify(preorder, 0, preorder.length-1);
    }
    
    private boolean verify(int[] preorder, int start, int end) {
        if (start>=end) return true;
        
        int root = preorder[start];
        Integer firstRight = null;
        for (int i=start+1; i<=end; i++) {
            if (firstRight==null) {
                if (preorder[i]>root)
                    firstRight = i;
            } else {
                if (preorder[i]<root)
                    return false;
            }
        }
        
        if (firstRight==null)
            return verify(preorder, start+1, end);
        else
            return verify(preorder, start+1, firstRight-1) && verify(preorder, firstRight, end);
    }
}

运行出现了StackOverflowError,递归的工作栈太深,因此需要变个思路,不能这样递归了。那就写成循环吧。可以BFS,也可以DFS。我这里用BFS,判断逻辑和上面的递归比并无二致,使用一个queue来存放当前需要检查的所有子树。

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Queue<Range> queue = new LinkedList<>();
        Range r = new Range(0, preorder.length-1);
        queue.add(r);
        
        while (!queue.isEmpty()) {
            Queue<Range> nq = new LinkedList<>();
            for (Range range : queue) {
                int start = range.start;
                int end = range.end;
                
                if (start>=end) continue;
                
                int root = preorder[start];
                Integer firstRight = null;
                for (int i=start+1; i<=end; i++) {
                    if (firstRight==null) {
                        if (preorder[i]>root)
                            firstRight = i;
                    } else {
                        if (preorder[i]<root)
                            return false;
                    }
                }

                if (firstRight==null) {
                    nq.add(new Range(start+1, end));
                } else {
                    nq.add(new Range(start+1, firstRight-1));
                    nq.add(new Range(firstRight, end));
                }
            }
            
            queue = nq;
        }
        
        return true;
    }
}

class Range {
    int start;
    int end;
    
    public Range(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Paint House

【题目】There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

【解答】思路基本上是DP,任意一个柱子 i 涂上颜色 x 的最小花费都和它前一个柱子涂上的其他两种颜色的最小花费相关。我可以建立三个滚动变量来存放当前柱子分别涂上这三种颜色的花费,也可以直接利用costs变量来存放,就连滚动变量都省了。

class Solution {
    public int minCost(int[][] costs) {
        // red blue green
        if (costs==null || (costs.length>0 && costs[0].length!=3))
            throw new IllegalArgumentException();
        
        if (costs.length==0)
            return 0;
        
        for (int i=0; i<costs.length; i++) {
            if (i==0) continue;
            
            costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]);
        }
        
        int last = costs.length-1;
        return Math.min(Math.min(costs[last][0], costs[last][1]), costs[last][2]);
    }
}

3Sum Smaller

【题目】Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

【解答】先排序是不会错的。之后锁定nums[i]的情况下考虑采用经典的双指针方法来寻找可行解,需要注意的是,每当双指针中的left固定,right直接找到可行解的范围,可以减小单纯遍历造成的时间复杂度。

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        
        int count = 0;
        for (int i=0; i<nums.length-2; i++) {
            int l=i+1, r=nums.length-1;
            while (l<r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum>=target) {
                    r--;
                } else {
                    count += r-l; // fix the l, move r, get all possibilities
                    l++;
                }
            }
        }
        
        return count;
    }
}

Graph Valid Tree

【题目】Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0]and thus will not appear together in edges.

【解答】无向图。要成为一棵树,意味着不能形成环。因此这道题是属于图里面的常规题。两种思路:

  1. 可以用基于搜索的BFS或者DFS来解,需要引入一个visited数组,一旦在遍历的过程中发现命中了之前遍历过的节点,说明形成环了;而如果一次遍历完毕后,发现还有节点没有覆盖到,说明存在不止一棵“树”。
  2. 当然,也可以使用并查集来求解,思路是,在构造并查集的过程中,需要union X和Y,如果发现X和Y已经是union的,说明这里存在环了;而如果在遍历完毕之后,发现并查集中存在不止一个null(null在一棵树中意味着root节点),说明这图中不止一棵树。这道题题目不难,但是非常有代表性。
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges==null || n<0)
            return false;
        
        Integer[] map = new Integer[n];
        for (int[] edge : edges) {
            int x = find(edge[0], map);
            int y = find(edge[1], map);
            
            if (x==y) {
                // the two points are already in the map so a new edge will make a cycle
                return false;
            }
            
            // union
            map[x] = y;
        }
        
        boolean flag = false;
        for (Integer point : map) {
            if (point==null) {
                if (!flag)
                    flag = true;
                else
                    return false;
            }
        }
        
        return true;
    }
    
    private int find(int num, Integer[] map) {
        if (map[num] == null)
            return num;
        else
            return find(map[num], map);
    }
}

Paint House II

【题目】There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

【解答】这道题直接拿出来的话需要好好想想,但是已经有了前面Paint House的经验,这道题的解法可以说换汤不换药。之前只有三种颜色,现在有k种颜色而已。

class Solution {
    public int minCostII(int[][] costs) {
        if (costs.length==0)
            return 0;
        
        for (int i=0; i<costs.length; i++) {
            if (i==0) continue;
            
            for (int j=0; j<costs[0].length; j++) {
                costs[i][j] += min(costs, i-1, j);
            }
        }
        
        return min(costs, costs.length-1, null);
    }
    
    private int min(int[][] costs, int i, Integer excludeJ) {
        Integer min = Integer.MAX_VALUE;
        for (int j=0; j<costs[0].length; j++) {
            if (excludeJ!=null && excludeJ.intValue()==j)
                continue;
            
            min = Math.min(min, costs[i][j]);
        }
        
        return min;
    }
}

Palindrome Permutation

【题目】Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

【解答】一个字符串的排列要能成为回文,这个字符串可以全部为成对的字符,或者只有一个字符不成对。因此引入一个HashSet,为每个字符调用add方法,根据结果来判断,如果set中已经存在,说明成对了,直接从这个set中删掉。遍历完毕后,看这个set的大小,超过1就返回false。

class Solution {
    public boolean canPermutePalindrome(String s) {
        Set<Character> set = new HashSet<>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (!set.add(ch))
                set.remove(ch);
        }
        
        return set.size()<=1;
    }
}

Palindrome Permutation II

【题目】Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

【解答】要找出所有的回文排列。首先找到每个字符可能出现的次数,存在一个数组中。然后检查这个数组,只能出现最多一次的单数,否则返回空集合,即无法形成回文。接着深度优先搜索,遍历所有可能性,这个数组正好用于遍历过程中记录状态。

class Solution {
    public List<String> generatePalindromes(String s) {
        int[] arr = new int[128];
        for (int i=0; i<s.length(); i++) {
            int idx = (int)s.charAt(i);
            arr[idx]++;
        }
        
        Integer odd = null;
        for (int i=0; i<arr.length; i++) {
            if (arr[i]%2==1) {
                if (odd!=null)
                    return new ArrayList<>();
                else
                    odd = i;
            }
        }
        
        List<String> result = new ArrayList<>();
        if (odd!=null) {
            arr[odd]--;
            travel((char)(odd.intValue()) + "", arr, result);
        } else {
            travel("", arr, result);
        }
        
        return result;
    }
    
    private void travel(String str, int[] arr, List<String> result) {
        boolean hasData = false;
        for (int i=0; i<arr.length; i++) {
            if (arr[i]==0) continue;
            
            hasData = true;
            arr[i] -= 2;
            
            travel((char)i + str + (char)i, arr, result);
            
            arr[i] += 2;
        }
        
        if (!hasData) result.add(str);
    }
}

Alien Dictionary

【题目】There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

Note:

  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.

【解答】本质上是一道图的问题。图问题的解法通常需要的并不多,下面这种基于入度(in degree)的解法很常见。

  • Step 1,建立两个数据结构,一个是表示先后顺序关系map<Character, Set<Character>>,表示key的字符必须先与任何value set的字符;另一个是indegrees<Character, Integer>,表示字符的入度,即入度为0的话表示当前没有任何字符必须先于它。
  • Step 2,每次从入度indegrees中找一个入度为0的节点作为输出的元素,然后去顺序关系map中找到它的直接后继,并将这些直接后继的入度全部减一,相当于删掉了当前节点和它的所有后继之间的路径,接着循环继续找入度为0的节点。
思路如上,不过代码写得有点啰嗦:
class Solution {
    public String alienOrder(String[] words) {
        if (words.length == 0) return "";
        if (words.length == 1) return words[0];
        
        Map<Character, Set<Character>> map = new HashMap<>();
        Map<Character, Integer> indegrees = new HashMap<>();
        
        // Step 1
        String last = null;
        for (String word : words) {
            if (last==null) {
                last = word;
                continue;
            }
            
            boolean found = false;
            for (int i=0; i<word.length() || i<last.length(); i++) {
                char cw = 0;
                if (i<word.length()) {
                    cw = word.charAt(i);
                    if (!indegrees.containsKey(cw)) {
                        indegrees.put(cw, 0);
                        map.put(cw, new HashSet<>());
                    }
                }
                
                char cl = 0;
                if (i<last.length()) {
                    cl = last.charAt(i);
                    if (!indegrees.containsKey(cl)) {
                        indegrees.put(cl, 0);
                        map.put(cl, new HashSet<>());
                    }
                }
                
                if (i>=last.length() || i>=word.length() || cw==cl)
                    continue;

                if (!found) {
                    found = true;
                    Set<Character> set = map.get(cl);
                    if (set.add(cw))
                        indegrees.put(cw, indegrees.get(cw)+1);
                }
            }
            
            last = word;
        }
        
        // Step 2
        Character c = null;
        for (Map.Entry<Character, Integer> entry : indegrees.entrySet()) {
            if (entry.getValue()==0) {
                c = entry.getKey();
                break;
            }
        }
        if (c!=null)
            indegrees.remove(c);
        
        String result = "";
        while (c!=null) {
            result = result + c;
            
            Set<Character> set = map.get(c);
            if (set!=null) {
                for (Character ch : set) {
                    indegrees.put(ch, indegrees.get(ch)-1);
                }
            }
            
            c = null;
            for (Map.Entry<Character, Integer> entry : indegrees.entrySet()) {
                if (entry.getValue()==0) {
                    c = entry.getKey();
                    break;
                }
            }
            if (c!=null)
                indegrees.remove(c);
        }
        
        if (!indegrees.isEmpty())
            return "";
        
        return result;
    }
}

Closest Binary Search Tree Value

【题目】Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.

【解答】二叉搜索树找最接近的点。如果target大于root.val,检查root.val,与右子树递归找到的最接近的点,这二者哪个更接近;如果target小于root.val,则检查root.val,与左子树递归找到的最接近的点,这二者哪个更接近。

class Solution {
    public int closestValue(TreeNode root, double target) {
        if (target==root.val) return root.val;
        
        if (target>root.val) {
            if (root.right==null) {
                return root.val;
            } else {
                int r = closestValue(root.right, target);
                if (target-root.val > Math.abs(r-target))
                    return r;
                else
                    return root.val;
            }
        } else {
            if (root.left==null) {
                return root.val;
            } else {
                int l = closestValue(root.left, target);
                if (root.val-target > Math.abs(l-target))
                    return l;
                else
                    return root.val;
            }
        }
    }
}

Encode and Decode Strings

【题目】Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

  • The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
  • Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
  • Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

【解答】要加密和解密一个字符串数组,如果要尝试去引入一个特殊的符号来分隔这几个string,就走上一条不归路了。因为无论选用什么分隔符,这个分隔符都可能在这个string list里面出现过。我采用的办法是类似于某些协议的设计,使用第一个换行符”\n”来分隔加密后报文的头部和实体。头部存放所有string的长度列表,实体则是所有string的简单拼接。

注意两个edge cases:空list,这种情况下头部为空;list中包含空字符串”",这种情况下该字符串的长度为0,因此头部不可能为空。

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        String lengths = "";
        for (String str : strs) {
            lengths += str.length() + ",";
            sb.append(str);
        }
        
        if (lengths.length()>0)
            lengths = lengths.substring(0, lengths.length()-1);
        
        return lengths + '\n' + sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        int idx = s.indexOf('\n');
        String lens = s.substring(0, idx);
        if (idx==0) return new ArrayList<>();

        String[] ls = lens.split("\\,");

        List<String> list = new ArrayList<>(ls.length);
        int p=idx+1;
        for (String l : ls) {
            int strl = Integer.parseInt(l);
            if (strl==0) {
                list.add("");
                continue;
            }
            list.add(s.substring(p, p+strl));
            p = p + strl;
        }
        
        return list;
    }
}

Closest Binary Search Tree Value II

【题目】Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

【解答】在BST中,需要返回k个和target最接近的节点。我的做法是:

  • Step 1: 先先序遍历BST得到一个有序的double linked list,同时也记录下了最接近的节点;
  • Step 2: 然后双指针一个往前,一个往后,寻找下一个最接近的点,直到找到k个为止。
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Item c = null;
        Item min = null;
        
        // Step 1
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur!=null || !stack.isEmpty()) {
            if (cur!=null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode tn = stack.pop();
                
                if (c==null) {
                    c = new Item(tn.val);
                    min = c;
                } else {
                    c.next = new Item(tn.val);
                    c.next.prev = c;
                    
                    c = c.next;
                    if (Math.abs(c.val-target) < Math.abs(min.val-target))
                        min = c;
                }
                
                cur = tn.right;
            }
        }
        
        // Step 2
        Item l=min.prev, r=min.next;
        List<Integer> result = new ArrayList<>();
        result.add(min.val);
        while (result.size()<k) {
            double leftDiff = Double.MAX_VALUE;
            if (l!=null) {
                leftDiff = Math.abs(l.val-target);
            }
            
            double rightDiff = Double.MAX_VALUE;
            if (r!=null) {
                rightDiff = Math.abs(r.val-target);
            }
            
            if (leftDiff<rightDiff) {
                result.add(l.val);
                l = l.prev;
            } else {
                result.add(r.val);
                r = r.next;
            }
        }
        
        return result;
    }
}

class Item {
    int val;
    Item prev;
    Item next;
    
    public Item(int val) {
        this.val = val;
    }
}

虽然AC了,不过我觉得应该有更优的解法,因为我遍历了BST所有的节点,事实上,如果只要找K个,以某种方法我应该只需要遍历K个,或者接近K个节点即可。

Paint Fence

【题目】There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

【解答】首先要理解题意。题目说得不太清楚,有人在评论区里面说,一种更清晰的描述方式应该是“no 3 adjacent posts have the same color”,就是说不能连续三个post都涂上同一种颜色。现在考虑任意的连续两根柱子A和B,存在两种可能,一种是A和B同色,这种情况下的种类数设为same;另一种是A和B不同色,种类数设为diff。现在要给下一根柱子C涂色:

  • 如果C和相邻的B同色,那么很显然共有diff种涂法,因为如果A和B同色时,是不能允许C和B继续同色的;
  • 如果C和B不同色,那么有两种情况,一种是A和B同色,这种情况下要避免B和C同色,共有same*(k-1)种涂法;另一种是A和B不同色,而又要求B和C不同色,共有diff*(k-1)种涂法。
class Solution {
    public int numWays(int n, int k) {
        if (n==0 || k==0)
            return 0;
        
        if (n==1)
            return k;
        else if (n==2)
            return k*k;
        
        int same = k;
        int diff = k*(k-1);
        
        for (int i=3; i<=n; i++) {
            int newSame = diff;
            int newDiff = (same+diff) * (k-1);
            
            same = newSame;
            diff = newDiff;
        }
        
        return same + diff;
    }
}

Find the Celebrity

【题目】Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

【解答】找名人问题。n个人里面,存在至多一位名人。名人不认识其余任何一个人,而其余任何一人都认识名人。

  • 用一个变量last记录疑似名人的那个人,对于其他人i,调用knows(last, i),如果返回true,说明last不可能是名人,于是更新last为i;
  • 接着再反过来第二遍循环中调用kowns(i, last),如果返回false,说明这个last有人不认识,那么这个last就不是名人,如果所有的i都认识last,last就是名人。
public class Solution extends Relation {
    public int findCelebrity(int n) {
        if (n<=1)
            return -1;
        
        Integer last = null;
        for (int i=0; i<n; i++) {
            if (last==null) {
                last = i;
                continue;
            }
            
            boolean know = knows(last, i);
            if (know) {
                last = i;
            }
        }

        for (int i=0; i<n; i++) {
            if (last!=i) {
                boolean know = knows(i, last);
                if (!know)
                    return -1;

                know = knows(last, i);
                if (know)
                    return -1;
            }
        }
        
        return last;
    }
}
 

Wiggle Sort

【题目】Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

【解答】先排序,然后从头、尾依次取数。

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums==null || nums.length==0)
            return;
        
        int[] numsCopy = new int[nums.length];
        System.arraycopy(nums, 0, numsCopy, 0, nums.length);
        Arrays.sort(numsCopy);
        
        int left=0, right=numsCopy.length-1;
        int i=0;
        boolean flag = true;
        while(i<nums.length) {
            if (flag) {
                nums[i++] = numsCopy[left];
                left++;
                flag = !flag;
            } else {
                nums[i++] = numsCopy[right];
                right--;
                flag = !flag;
            }
        }
    }
}

Zigzag Iterator

【题目】Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:

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

It should return [1,4,8,2,5,9,3,6,7].

【解答】用一个boolean变量记录下一个访问的节点是在v1还是v2;用一个int变量col用来记录节点下标。建立一个adjust方法用来针对一些不合法的情况调整节点的位置,比如v1或者v2已经穷尽时。保证每次方法调用以后内部总是能够准备好下一个需要返回的节点。

public class ZigzagIterator {
    private List<Integer> v1 = null;
    private List<Integer> v2 = null;
    
    private boolean row = true;
    private int col = 0;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.v1 = v1;
        this.v2 = v2;
        adjust();
    }

    private void adjust() {
        if (row) {
            if (v1.size()<=col) {
                row = false;
            }
        } else {
            if (v2.size()<=col) {
                row = true;
                col++;
            }
        }
    }
    
    public int next() {
        List<Integer> v = row ? v1 : v2;
        if (col>=v.size()) throw new RuntimeException();
        
        int res = v.get(col);
        if (row) {
            row = false;
        } else {
            row = true;
            col++;
        }
        adjust();
        
        return res;
    }

    public boolean hasNext() {
        List<Integer> v = row ? v1 : v2;
        return col<v.size();
    }
}

Inorder Successor in BST

【题目】Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

【解答】用一个boolean变量记录是否已经找到p了。剩下的和普通的二叉树的中序遍历没有区别。

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        boolean matched = false;
        while (cur!=null || !stack.isEmpty()) {
            if (cur!=null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode tn = stack.pop();
                if (matched) {
                    return tn;
                } else {
                    if (p==tn) matched = true;
                    cur = tn.right;
                }
            }
        }
        
        return null;
    }
}

Walls and Gates

【题目】You are given a m x n 2D grid initialized with these three possible values.

  1. -1 - A wall or an obstacle.
  2. 0 - A gate.
  3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

【解答】我一开始的思路是DFS,从任何一点出发,为了防止循环探索,先标记自己为障碍(-1),然后探索上下左右四个方向,以找到里gate最近的步数。可是这样的方法有一个问题,在标记自己(比如为A)为障碍的时候,如果探索的位置正好需要通过A才可达呢?这样得出的结果是有问题的。另外一个麻烦的地方是,有些地方是不可达的,因此需要标记为INF,可是怎样区分是原始的INF还是我希望标记的INF呢?这个问题又需要额外的逻辑来处理。

于是,换个思路。一个相对简单的办法是,找所有gate(0)的位置,然后从gate开始往周围蔓延,寻找所有通过这个门可达的点,并且记录和更新最小步数。其中,在寻找的过程中,如果发现在该位置上已经出现了更小的值,这个值可能是障碍(-1),也可能是更小的步数,就直接返回,以减小计算量。代码简单很多。我觉得这道题在迷宫类问题中是有一定代表性的。

class Solution {
    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0)
                    mark(rooms, i, j, 0);
            }
        }
    }

    private void mark(int[][] rooms, int i, int j, int step) {
        if (i < 0 || j < 0 || j >= rooms[0].length || i >= rooms.length || rooms[i][j] < step)
            return;
        
        rooms[i][j] = step;
        
        mark(rooms, i - 1, j, step + 1);
        mark(rooms, i + 1, j, step + 1);
        mark(rooms, i, j - 1, step + 1);
        mark(rooms, i, j + 1, step + 1);
    }
}

Unique Word Abbreviation

【题目】An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example: 

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

【解答】写一个方法来得到一个词语的缩略形式,然后把缩略形式作为key,放到map里面去。这样查询的时候就可以看给定的缩略形式是不是可以找到唯一的对应词语。

class ValidWordAbbr {
    private Map<String, Set<String>> map = new HashMap<>();
    public ValidWordAbbr(String[] dictionary) {
        for (String s : dictionary) {
            String key = getKey(s);
            Set<String> set = map.get(key);
            if (set == null)
                set = new HashSet<>();
            
            set.add(s);
            
            map.put(key, set);
        }
    }
    
    private String getKey(String s) {
        String key = null;
        if (s.length()<3)
            key = s;
        else
            key = "" + s.charAt(0) + (s.length()-2) + s.charAt(s.length()-1);
        
        return key;
    }
    
    public boolean isUnique(String word) {
        String key = getKey(word);
        if (!this.map.containsKey(key))
            return true;
        else {
            Set<String> set = this.map.get(key);
            if (set.size() == 1 && set.contains(word))
                return true;
        }
        
        return false;
    }
}

Word Pattern II

【题目】Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

  1. pattern = "abab", str = "redblueredblue" should return true.
  2. pattern = "aaaa", str = "asdasdasdasd" should return true.
  3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:

You may assume both pattern and str contains only lowercase letters.

【解答】判断字符串是否匹配这个pattern。我的思路是回溯法,使用两个map,一个是pattern的字符对应到str中的substring的map;另一个是反过来,substring对应到字符。

  • 如果发现某个字符在map中出现过,必须要同时检查另一个map,看这个substring是否也出现过且对应到相同的字符去,然后才递归调用余下的部分。
  • 如果发现字符没有出现过,也要类似的操作,确保选取的substring也是没有出现过的。再递归调用余下的部分,只要有一种substring选取的解返回true,这个方法就返回true。
class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        return match(pattern, 0, str, 0, new HashMap<>(), new HashMap<>());
    }
    
    private boolean match(String pattern, int p, String str, int s, Map<Character, String> map, Map<String, Character> map2) {
        if (p==pattern.length() && s==str.length()) return true;
        if (p==pattern.length() || s==str.length()) return false;
        
        char cp = pattern.charAt(p);
        if (map.containsKey(cp)) {
            String token = map.get(cp);
            if (token.length()>=str.length()-s+1)
                return false;
            
            String sub = str.substring(s, s+token.length());
            if (!sub.equals(token))
                return false;
            
            Character ch = map2.get(sub);
            if (ch.charValue()!=cp)
                return false;
            
            return match(pattern, p+1, str, s+token.length(), map, map2);
        } else {
            for (int i=1; i<=str.length()-s; i++) {
                String sub = str.substring(s, s+i);
                if (map2.containsKey(sub))
                    continue;
                
                map.put(cp, sub);
                map2.put(sub, cp);
                
                boolean res = match(pattern, p+1, str, s+i, map, map2);
                if (res) return true;
                
                map.remove(cp);
                map2.remove(sub);
            }
            
            return false;
        }
    }
}

Flip Game

【题目】You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = "++++", after one move, it may become one of the following states:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

【解答】转成char array然后替换相应的字符。

class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> result = new ArrayList<>();
        for (int i=1; i<s.length(); i++) {
            if (s.charAt(i)=='+' && s.charAt(i-1)=='+') {
                char[] chs = s.toCharArray();
                chs[i] = '-';
                chs[i-1] = '-';
                result.add(new String(chs));
            }
        }
        return result;
    }
}

Flip Game II

【题目】You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm’s runtime complexity.

【解答】本质上还是回溯法。自己当前可以选择一步走,如果走了哪一步,接下去如果对手无法赢,那么自己就赢了。

class Solution {
    public boolean canWin(String s) {
        return canWin(s.toCharArray());
    }
    
    private boolean canWin(char[] chs) {
        for (int i=1; i<chs.length; i++) {
            if (chs[i]=='+' && chs[i-1]=='+') {
                
                chs[i]='-';
                chs[i-1]='-';
                
                boolean res = canWin(chs);
                
                chs[i]='+';
                chs[i-1]='+';
                
                if (!res)
                    return true;
            }
        }
        
        return false;
    }
}

Best Meeting Point

【题目】A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0)(0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

【解答】显然,把图上的每个点取出来去计算和所有人所在的点距离之和是一个办法,但是复杂度太高了。考虑优化的办法。这里的距离用的是曼哈顿距离,因此可以看到,行和列的距离计算是完全独立的。也就是说,从行这个维度上去取点的逻辑,和从列这个维度上去取点的逻辑,是互不影响的。这一点非常重要,因为有了这一个理论基础,就可以把这个二维的问题降为一维来解决。

如果这个图只有一维,那么这些人的位置的中位数是最佳的位置(不是平均数)。有了这个发现以后,问题就变成了求中位数的过程,也就迎刃而解了。

class Solution {
    public int minTotalDistance(int[][] grid) {
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[0].length; j++) {
                if (grid[i][j]==1) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        
        Collections.sort(rows);
        Collections.sort(cols);
        
        int i = rows.get(rows.size() / 2);
        int j = cols.get(cols.size() / 2);
        
        int total = 0;
        for (int p : rows) {
            total += Math.abs(p-i);
        }
        for (int q : cols) {
            total += Math.abs(q-j);
        }
        
        return total;
    }
}

Binary Tree Longest Consecutive Sequence

【题目】Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    /
   2
  /
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

【解答】建立一个Result对象,用来在递归遍历这棵树的时候传递子树的结果,包含两个值,一个是发现的最长递增串,一个是以该子树root为起点的最长递增串。

class Solution {
    public int longestConsecutive(TreeNode root) {
        return travel(root).longest;
    }
    
    private Result travel(TreeNode root) {
        if (root==null)
            return new Result();
        
        int longest = 1;
        int increasing = 1;
        
        Result left = travel(root.left);
        longest = Math.max(left.longest, longest);
        if (root.left!=null && root.val+1==root.left.val) {
            increasing = Math.max(left.increasing+1, increasing);
        }
        
        Result right = travel(root.right);
        longest = Math.max(right.longest, longest);
        if (root.right!=null && root.val+1==root.right.val) {
            increasing = Math.max(right.increasing+1, increasing);
        }
        
        longest = Math.max(longest, increasing);
        
        Result res = new Result();
        res.longest = longest;
        res.increasing = increasing;
        
        return res;
    }
}

class Result {
    int longest;
    int increasing;
}

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: