## #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].
``````

``````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

``````Design a data structure that supports the following two operations:

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:

search("b..") -> true
``````

``````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.
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"].
``````

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) {
}
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.
``````

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.
``````

``````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]]
``````

``````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) {
}
return;
}
for (int i = current; i < 10 && i <= n; 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.
``````

``````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], ...]
``````

``````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++) {
}
Collections.sort(lines);
List<int[]> result = new ArrayList<>();
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for (Line line : lines) {
if (line.left) {
} 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) {
} else {
int[] last = result.get(result.size() - 1);
if (last[1] != item[1]) {
}
}
}
}
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.
``````

``````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++) {
}
if (set.size() != capacity) {
return true;
}
for (int i = 0, j = capacity; j < nums.length; i++, j++) {
set.remove(nums[i]);