#210 Course Schedule II
Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
思路，
这题是#207 Course Schedule的加强版，在解207题的时候没有注意，用了拓扑排序，实际上207只需要DFS判断有无环就好了，这道题目才是需要给出一个拓扑序。
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] result = new int[numCourses];
int[][] matrix = new int[numCourses][numCourses];
int[] degrees = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
int x = prerequisites[i][0];
int y = prerequisites[i][1];
if (matrix[y][x] == 0) {
matrix[y][x] = 1;
degrees[x] += 1;
}
}
int count = 0;
int visited = 0;
while (visited < numCourses) {
int idx = -1;
for (int i = 0; i < degrees.length; i++) {
if (degrees[i] == 0) {
result[count++] = i;
idx = i;
degrees[i] = -1;
break;
}
}
if (idx == -1) {
break;
}
visited += 1;
for (int i = idx, j = 0; j < numCourses; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] = 0;
degrees[j] -= 1;
}
}
}
if (visited != numCourses) {
return new int[] {};
}
return result;
}
}
#211 Add and Search Word
Add and Search Word
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
思路，
题目需要实现一个能够支持添加、简单搜索以及带通配符搜索的数据结构。通配符只有'.'用以表示任意字符。Trie是可以满足需求的数据结构，搜索时如果遇到'.'，则可以查询当前所有子节点判断单词是否存在。Trie借用了#208 Implement Trie的实现。
public class WordDictionary {
public class TrieNode {
private TrieNode[] nodes;
private boolean end;
public TrieNode() {
int size = 26;
nodes = new TrieNode[size];
end = false;
}
public void insert(char[] chars, int start) {
if (start == chars.length) {
end = true;
return;
}
int idx = getIndex(chars[start]);
if (idx == -1) {
for (int i = 0; i < nodes.length; i++) {
insert(i, chars, start);
}
} else {
insert(idx, chars, start);
}
}
private void insert(int idx, char[] chars, int start) {
TrieNode node = nodes[idx];
if (node != null) {
node.insert(chars, start + 1);
} else {
node = new TrieNode();
nodes[idx] = node;
node.insert(chars, start + 1);
}
}
public boolean search(char[] chars, int start) {
if (start == chars.length) {
return end;
}
char c = chars[start];
int idx = getIndex(c);
if (idx == -1) {
boolean flag;
for (int i = 0; i < nodes.length; i++) {
flag = search(i, chars, start);
if (flag) {
return true;
}
}
return false;
} else {
return search(idx, chars, start);
}
}
private boolean search(int idx, char[] chars, int start) {
TrieNode node = nodes[idx];
if (node == null) {
return false;
}
return node.search(chars, start + 1);
}
private int getIndex(char c) {
if (c == '.') {
return -1;
}
return c - 'a';
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
root.insert(word.toCharArray(), 0);
}
// Returns if the word is in the trie.
public boolean search(String word) {
return root.search(word.toCharArray(), 0);
}
}
public Trie trie = new Trie();
// Adds a word into the data structure.
public void addWord(String word) {
trie.insert(word);
}
// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
public boolean search(String word) {
return trie.search(word);
}
}
#212 Word Search II
Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Return ["eat","oath"].
思路，
这题是#79 Word Search的增强版。
首先还是来看看通用的BFS搜索，遍历每一个单词，用BFS的方式判定是否存在。这个方法在大数据集下会超时。如何才能降低搜索的次数？考虑有大量重复或是有共同前缀的单词组成的数据集，对于重复元素以及共同前缀的搜索应该是可以删减的。什么样的数据结构可以用于处理共同前缀？Trie。
Trie依然借用了#208 Implement Trie的实现。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
Set<String> result = new HashSet<>();
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
search(board, i, j, trie.getNode(), result, new StringBuilder());
}
}
return new ArrayList<>(result);
}
private void search(char[][] board, int i, int j, TrieNode node, Set<String> set, StringBuilder builder) {
if (node.end == true) {
set.add(builder.toString());
}
if (i < 0 || i >= board.length) {
return;
}
if (j < 0 || j >= board[0].length) {
return;
}
if (board[i][j] == ' ') {
return;
}
int idx = board[i][j] - 'a';
if (node.nodes[idx] == null) {
return;
}
char c = board[i][j];
board[i][j] = ' ';
search(board, i, j + 1, node.nodes[idx], set, builder.append(c));
builder.deleteCharAt(builder.length() - 1);
board[i][j] = c;
board[i][j] = ' ';
search(board, i, j - 1, node.nodes[idx], set, builder.append(c));
builder.deleteCharAt(builder.length() - 1);
board[i][j] = c;
board[i][j] = ' ';
search(board, i + 1, j, node.nodes[idx], set, builder.append(c));
builder.deleteCharAt(builder.length() - 1);
board[i][j] = c;
board[i][j] = ' ';
search(board, i - 1, j, node.nodes[idx], set, builder.append(c));
builder.deleteCharAt(builder.length() - 1);
board[i][j] = c;
}
public static class TrieNode {
private TrieNode[] nodes;
private boolean end;
public TrieNode() {
int size = 26;
nodes = new TrieNode[size];
end = false;
}
public void insert(char[] chars, int start) {
if (start == chars.length) {
end = true;
return;
}
int idx = chars[start] - 'a';
TrieNode node = nodes[idx];
if (node != null) {
node.insert(chars, start + 1);
} else {
node = new TrieNode();
nodes[chars[start] - 'a'] = node;
node.insert(chars, start + 1);
}
}
public boolean search(char[] chars, int start) {
if (start == chars.length) {
return end;
}
char c = chars[start];
TrieNode node = nodes[c - 'a'];
if (node == null) {
return false;
}
return node.search(chars, start + 1);
}
public boolean startWith(char[] chars, int start) {
if (start == chars.length) {
return true;
}
char c = chars[start];
TrieNode node = nodes[c - 'a'];
if (node == null) {
return false;
}
return node.startWith(chars, start + 1);
}
}
public static class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public TrieNode getNode() {
return root;
}
// Inserts a word into the trie.
public void insert(String word) {
root.insert(word.toCharArray(), 0);
}
// Returns if the word is in the trie.
public boolean search(String word) {
return root.search(word.toCharArray(), 0);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
return root.startWith(prefix.toCharArray(), 0);
}
}
}
#213 House Robber II
House Robber II
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
思路，
这题是#198 House Robber的改进版。与198的不同之处是，题目里的屋子是一个环。环与非环的影响在于第一间与最后一间屋子是否能被偷窃。于是可以分情况讨论，rob表示偷窃start到end之间的屋子所能获得的最大收益，
rob(nums, start, end) = max(rob(nums, 1, end), nums[0] + rob(nums, 2, end - 1));
public class Solution {
public int rob(int[] nums) {
if (nums.length <= 3) {
return Arrays.stream(nums).max().orElse(0);
}
int[] rotate = new int[nums.length - 3];
System.arraycopy(nums, 2, rotate, 0, nums.length - 3);
int includeFirst = nums[0] + internalRob(rotate);
rotate = new int[nums.length - 1];
System.arraycopy(nums, 1, rotate, 0, nums.length - 1);
int notIncludeFirst = internalRob(rotate);
return Math.max(includeFirst, notIncludeFirst);
}
public int internalRob(int[] nums) {
int[] dp = Arrays.copyOf(nums, nums.length);
int result = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i - 2; j >= 0 && j >= j - 3; j--) {
dp[i] = Math.max(dp[i], nums[i] + dp[j]);
}
result = Math.max(dp[i], result);
}
return result;
}
}
#214 Shortest Palindrome
Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
思路，
题目需要在原有字符串上构建最短的会文串，只能在字符串首部增加元素。分析后可以看出，如果希望最终构建的回文串长度最小，那么需要找到原字符串中包含首个字符的最长回文串的长度。
从原字符串中间位置开始，分别判断是否存在奇数长度、偶数长度的回文串。一旦获得的回文串包含了第一个字符，这个回文串就是最长的一个。
public class Solution {
public String shortestPalindrome(String s) {
int length = longestPalindromeIncludeFirstChar(s);
StringBuilder builder = new StringBuilder();
for (int i = s.length() - 1; i > length; i--) {
builder.append(s.charAt(i));
}
builder.append(s);
return builder.toString();
}
public int longestPalindromeIncludeFirstChar(String input) {
for (int k = input.length() / 2; k >= 0; k--) {
int length = getPalindromeLength(input, k);
if (length > 0) {
return length;
}
}
return 0;
}
private int getPalindromeLength(String input, int center) {
// 奇数长度回文
int right = 0;
int i = center - 1;
int j = center + 1;
while (i >= 0 && j < input.length()) {
if (input.charAt(i) != input.charAt(j)) {
break;
}
i -= 1;
j += 1;
}
if (i + 1 == 0) {
right = Math.max(right, j - 1);
}
// 偶数长度回文
i = center;
j = center + 1;
while (i >= 0 && j < input.length()) {
if (input.charAt(i) != input.charAt(j)) {
break;
}
i -= 1;
j += 1;
}
if (i + 1 == 0) {
right = Math.max(right, j - 1);
}
return right;
}
}
#215 Kth Largest Element in an Array
Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
思路，
题目要求寻找数组中的第K大数。最简单的做法就是排序后再获取，不过这样时间复杂度就不符合要求了。想在O(n)时间内获得第K大数则可以考虑类似快速排序的实现。通过分治的方式不断排除元素，这样最终平均复杂度就能够达到要求。
public class Solution {
public int findKthLargest(int[] nums, int k) {
sort(nums, 0, nums.length, k);
return nums[k-1];
}
private void sort(int[] nums, int start, int end, int k) {
if (start >= end - 1) {
return;
}
if (start == end - 2) {
if (nums[start] < nums[end - 1]) {
swap(nums, start, end - 1);
}
return;
}
int middle = (start + end) / 2;
int pivot = nums[middle];
swap(nums, start, middle);
int i = start + 1;
int j = end - 1;
while (i < j) {
for (; i < j && nums[i] >= pivot; i += 1) {}
for (; j > i && nums[j] <= pivot; j -= 1) {}
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, start, i - 1);
if (k < i) {
sort(nums, start, i, k);
} else {
sort(nums, i, end, k);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
#216 Combination Sum III
Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
思路，
没有什么特别的思路，DFS搜索即可。
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
recursive(1, k, n, new ArrayList<>(), result);
return result;
}
private void recursive(int current, int remain, int n, List<Integer> matches, List<List<Integer>> result) {
if (remain == 0) {
if (n == 0) {
result.add(new ArrayList<>(matches));
}
return;
}
for (int i = current; i < 10 && i <= n; i++) {
matches.add(i);
recursive(i + 1, remain - 1, n - i, matches, result);
matches.remove(matches.size() - 1);
}
}
}
#217 Contains Duplicate
Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
思路，
直接用HashSet进行判断。
public class Solution {
public boolean containsDuplicate(int[] nums) {
return nums.length != Arrays.stream(nums).boxed().collect(Collectors.toSet()).size();
}
}
#218 The Skyline Problem
The Skyline Problem
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
Buildings Skyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
The number of buildings in any input list is guaranteed to be in the range [0, 10000].
The input list is already sorted in ascending order by the left x position Li.
The output list must be sorted by the x position.
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
思路，
这道题目自己没有想出很好的思路，从这里借鉴了思路。
题目的关键在于对skyline边缘的排序，具体的排序规则见代码中的compareTo函数。在有了有序的边之后，通过PriorityQueue来维护当前最高的高度。
public class Solution {
public static class Line implements Comparable<Line> {
public int x;
public boolean left;
public int height;
public Line(int x, int height, boolean left) {
this.x = x;
this.height = height;
this.left = left;
}
@Override
public int compareTo(Line line) {
if (x != line.x) {
return x - line.x;
}
if (left != line.left) {
if (left) {
return -1;
} else {
return 1;
}
} else {
if (left) {
return line.height - height;
} else {
return height - line.height;
}
}
}
@Override
public String toString() {
return "Line{" +
"x=" + x +
", left=" + left +
", height=" + height +
'}';
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<Line> lines = new ArrayList<>();
for (int i = 0; i < buildings.length; i++) {
lines.add(new Line(buildings[i][0], buildings[i][2], true));
lines.add(new Line(buildings[i][1], buildings[i][2], false));
}
Collections.sort(lines);
List<int[]> result = new ArrayList<>();
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for (Line line : lines) {
if (line.left) {
heap.add(line.height);
} else {
heap.remove(line.height);
}
int height = heap.size() == 0 ? 0 : heap.peek();
if (line.height >= height) {
int[] item = new int[] {line.x, height};
if (result.size() == 0) {
result.add(item);
} else {
int[] last = result.get(result.size() - 1);
if (last[1] != item[1]) {
result.add(item);
}
}
}
}
return result;
}
}
#219 Contains Duplicate II
Contains Duplicate II
Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
思路，
题目需要判定数组中是否存在重复元素，重复元素之间的距离不超过k。判定是否重复可以用HashSet，类似这种连续元素的判定可以使用滑动窗口的方式来实现。
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
int capacity = Math.min(k + 1, nums.length);
for (int i = 0; i <= k && i < nums.length; i++) {
set.add(nums[i]);
}
if (set.size() != capacity) {
return true;
}
for (int i = 0, j = capacity; j < nums.length; i++, j++) {
set.remove(nums[i]);
set.add(nums[j]);
if (set.size() != capacity) {
return true;
}
}
return false;
}
}