LeetCode 付费题目（一）
LeetCode 300 题以内需要付费才能查看的所有题目解答。
156 | Binary Tree Upside Down |
|---|---|
157 | Read N Characters Given Read4 |
158 | Read N Characters Given Read4 II – Call multiple times |
159 | Longest Substring with At Most Two Distinct Characters |
161 | One Edit Distance |
163 | Missing Ranges |
170 | Two Sum III – Data structure design |
186 | Reverse Words in a String II |
243 | Shortest Word Distance |
244 | Shortest Word Distance II |
245 | Shortest Word Distance III |
246 | Strobogrammatic Number |
247 | Strobogrammatic Number II |
248 | Strobogrammatic Number III |
249 | Group Shifted Strings |
250 | Count Univalue Subtrees |
251 | Flatten 2D Vector |
252 | Meeting Rooms |
253 | Meeting Rooms II |
254 | Factor Combinations |
255 | Verify Preorder Sequence in Binary Search Tree |
256 | Paint House |
259 | 3Sum Smaller |
261 | Graph Valid Tree |
265 | Paint House II |
266 | Palindrome Permutation |
267 | Palindrome Permutation II |
269 | Alien Dictionary |
270 | Closest Binary Search Tree Value |
271 | Encode and Decode Strings |
272 | Closest Binary Search Tree Value II |
276 | Paint Fence |
277 | Find the Celebrity |
280 | Wiggle Sort |
281 | Zigzag Iterator |
285 | Inorder Successor in BST |
286 | Walls and Gates |
288 | Unique Word Abbreviation |
291 | Word Pattern II |
293 | Flip Game |
294 | Flip Game II |
296 | Best Meeting Point |
298 | Binary Tree Longest Consecutive Sequence |
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 5return the root of the binary tree [4,5,2,#,#,3,1].
4
/ \
5 2
/ \
3 1【解答】把题目中的树拆成好多个小三角形来分别看，比如 2-4-5 这个三角形，调整的三部曲：
- 把 2->4 的路径反向，
- 2->5 的路径切断，
- 然后建立 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：
- n 先达到
- buf.length 先达到
- 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.
【解答】这道题的关键在于怎么样给条件归类从而简化逻辑。看起来似乎不复杂，但是有很多需要考虑的要素：
- read 方法的 buf 长度决定了该方法读取数据的量不可能超过它；
- read 方法的参数 n 也决定了该方法读取数据的量不可能超过它；
- read4 方法可能读不到足够的数据，这种情况下读取数据的量不可能超过它；
- 需要考虑前一次读取完毕之后，可能会有剩余，那么在这次读取的时候，需要优先消费这个剩余量。
上面这几点里面，#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 [lower, upper], 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 5return 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:
- You may assume that n is always positive.
- 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(_n_2) runtime?
【解答】先排序是不会错的。之后锁定 numsi 的情况下考虑采用经典的双指针方法来寻找可行解，需要注意的是，每当双指针中的 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.
【解答】无向图。要成为一棵树，意味着不能形成环。因此这道题是属于图里面的常规题。两种思路：
- 可以用基于搜索的 BFS 或者 DFS 来解，需要引入一个 visited 数组，一旦在遍历的过程中发现命中了之前遍历过的节点，说明形成环了；而如果一次遍历完毕后，发现还有节点没有覆盖到，说明存在不止一棵 “树”。
- 当然，也可以使用并查集来求解，思路是，在构造并查集的过程中，需要 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:
- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- 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
evalor 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– A wall or an obstacle.0– A gate.INF– Infinity means an empty room. We use the value231 - 1 = 2147483647to representINFas you may assume that the distance to a gate is less than2147483647.
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 INFAfter 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 --> l10nAssume 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:
- pattern =
"abab", str ="redblueredblue"should return true. - pattern =
"aaaa", str ="asdasdasdasd"should return true. - 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 - 0The 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
\
5Longest consecutive sequence path is 3-4-5, so return 3.
2
\
3
/
2
/
1Longest 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;
}文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
腾讯云开发者
