# CyC2018/CS-Notes

Switch branches/tags
Nothing to show
2a11c8f Oct 7, 2018
7 contributors

### Users who have contributed to this file

7058 lines (5650 sloc) 191 KB

# 算法思想

## 双指针

Leetcode ：167. Two Sum II - Input array is sorted (Easy)

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

• 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变大一些。
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum == target) {
return new int[]{i + 1, j + 1};
} else if (sum < target) {
i++;
} else {
j--;
}
}
return null;
}

633. Sum of Square Numbers (Easy)

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

public boolean judgeSquareSum(int c) {
int i = 0, j = (int) Math.sqrt(c);
while (i <= j) {
int powSum = i * i + j * j;
if (powSum == c) {
return true;
} else if (powSum > c) {
j--;
} else {
i++;
}
}
return false;
}

345. Reverse Vowels of a String (Easy)

Given s = "leetcode", return "leotcede".

private final static HashSet<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

public String reverseVowels(String s) {
int i = 0, j = s.length() - 1;
char[] result = new char[s.length()];
while (i <= j) {
char ci = s.charAt(i);
char cj = s.charAt(j);
if (!vowels.contains(ci)) {
result[i++] = ci;
} else if (!vowels.contains(cj)) {
result[j--] = cj;
} else {
result[i++] = cj;
result[j--] = ci;
}
}
return new String(result);
}

680. Valid Palindrome II (Easy)

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

public boolean validPalindrome(String s) {
int i = -1, j = s.length();
while (++i < --j) {
if (s.charAt(i) != s.charAt(j)) {
return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
}
}
return true;
}

private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}

88. Merge Sorted Array (Easy)

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - 1, index2 = n - 1;
int indexMerge = m + n - 1;
while (index1 >= 0 || index2 >= 0) {
if (index1 < 0) {
nums1[indexMerge--] = nums2[index2--];
} else if (index2 < 0) {
nums1[indexMerge--] = nums1[index1--];
} else if (nums1[index1] > nums2[index2]) {
nums1[indexMerge--] = nums1[index1--];
} else {
nums1[indexMerge--] = nums2[index2--];
}
}
}

public boolean hasCycle(ListNode head) {
return false;
}
while (l1 != null && l2 != null && l2.next != null) {
if (l1 == l2) {
return true;
}
l1 = l1.next;
l2 = l2.next.next;
}
return false;
}

524. Longest Word in Dictionary through Deleting (Medium)

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output:
"apple"


public String findLongestWord(String s, List<String> d) {
String longestWord = "";
for (String target : d) {
int l1 = longestWord.length(), l2 = target.length();
if (l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)) {
continue;
}
if (isValid(s, target)) {
longestWord = target;
}
}
return longestWord;
}

private boolean isValid(String s, String target) {
int i = 0, j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}

## 排序

### 堆排序

Kth Element

215. Kth Largest Element in an Array (Medium)

public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}

public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
for (int val : nums) {
if (pq.size() > k)  // 维护堆的大小为 K
pq.poll();
}
return pq.peek();
}

public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k) {
break;
} else if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}

private int partition(int[] a, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (a[++i] < a[l] && i < h) ;
while (a[--j] > a[l] && j > l) ;
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, l, j);
return j;
}

private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}

### 桶排序

347. Top K Frequent Elements (Medium)

Given [1,1,1,2,2,3] and k = 2, return [1,2].

public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> frequencyForNum = new HashMap<>();
for (int num : nums) {
frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1);
}
List<Integer>[] buckets = new ArrayList[nums.length + 1];
for (int key : frequencyForNum.keySet()) {
int frequency = frequencyForNum.get(key);
if (buckets[frequency] == null) {
buckets[frequency] = new ArrayList<>();
}
}
List<Integer> topK = new ArrayList<>();
for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {
if (buckets[i] != null) {
}
}
}

451. Sort Characters By Frequency (Medium)

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
public String frequencySort(String s) {
Map<Character, Integer> frequencyForNum = new HashMap<>();
for (char c : s.toCharArray())
frequencyForNum.put(c, frequencyForNum.getOrDefault(c, 0) + 1);

List<Character>[] frequencyBucket = new ArrayList[s.length() + 1];
for (char c : frequencyForNum.keySet()) {
int f = frequencyForNum.get(c);
if (frequencyBucket[f] == null) {
frequencyBucket[f] = new ArrayList<>();
}
}
StringBuilder str = new StringBuilder();
for (int i = frequencyBucket.length - 1; i >= 0; i--) {
if (frequencyBucket[i] == null) {
continue;
}
for (char c : frequencyBucket[i]) {
for (int j = 0; j < i; j++) {
str.append(c);
}
}
}
return str.toString();
}

### 荷兰国旗问题

75. Sort Colors (Medium)

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

public void sortColors(int[] nums) {
int zero = -1, one = 0, two = nums.length;
while (one < two) {
if (nums[one] == 0) {
swap(nums, ++zero, one++);
} else if (nums[one] == 2) {
swap(nums, --two, one);
} else {
++one;
}
}
}

private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}

## 贪心思想

Input: [1,2], [1,2,3]
Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int gi = 0, si = 0;
while (gi < g.length && si < s.length) {
if (g[gi] <= s[si]) {
gi++;
}
si++;
}
return gi;
}

435. Non-overlapping Intervals (Medium)

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, Comparator.comparingInt(o -> o.end));
int cnt = 1;
int end = intervals[0].end;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i].start < end) {
continue;
}
end = intervals[i].end;
cnt++;
}
return intervals.length - cnt;
}

Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.end - o2.end;
}
});

452. Minimum Number of Arrows to Burst Balloons (Medium)

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2


public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
int cnt = 1, end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] <= end) {
continue;
}
cnt++;
end = points[i][1];
}
return cnt;
}

406. Queue Reconstruction by Height(Medium)

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

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

public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0) {
return new int[0][0];
}
Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
List<int[]> queue = new ArrayList<>();
for (int[] p : people) {
}
return queue.toArray(new int[queue.size()][]);
}

763. Partition Labels (Medium)

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
public List<Integer> partitionLabels(String S) {
int[] lastIndexsOfChar = new int[26];
for (int i = 0; i < S.length(); i++) {
lastIndexsOfChar[char2Index(S.charAt(i))] = i;
}
List<Integer> partitions = new ArrayList<>();
int firstIndex = 0;
while (firstIndex < S.length()) {
int lastIndex = firstIndex;
for (int i = firstIndex; i < S.length() && i <= lastIndex; i++) {
int index = lastIndexsOfChar[char2Index(S.charAt(i))];
if (index > lastIndex) {
lastIndex = index;
}
}
firstIndex = lastIndex + 1;
}
return partitions;
}

private int char2Index(char c) {
return c - 'a';
}

605. Can Place Flowers (Easy)

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

public boolean canPlaceFlowers(int[] flowerbed, int n) {
int len = flowerbed.length;
int cnt = 0;
for (int i = 0; i < len && cnt < n; i++) {
if (flowerbed[i] == 1) {
continue;
}
int pre = i == 0 ? 0 : flowerbed[i - 1];
int next = i == len - 1 ? 0 : flowerbed[i + 1];
if (pre == 0 && next == 0) {
cnt++;
flowerbed[i] = 1;
}
}
return cnt >= n;
}

392. Is Subsequence (Medium)

s = "abc", t = "ahbgdc"
Return true.
public boolean isSubsequence(String s, String t) {
int index = -1;
for (char c : s.toCharArray()) {
index = t.indexOf(c, index + 1);
if (index == -1) {
return false;
}
}
return true;
}

665. Non-decreasing Array (Easy)

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

public boolean checkPossibility(int[] nums) {
int cnt = 0;
for (int i = 1; i < nums.length && cnt < 2; i++) {
if (nums[i] >= nums[i - 1]) {
continue;
}
cnt++;
if (i - 2 >= 0 && nums[i - 2] > nums[i]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
return cnt <= 1;
}

122. Best Time to Buy and Sell Stock II (Easy)

public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += (prices[i] - prices[i - 1]);
}
}
return profit;
}

53. Maximum Subarray (Easy)

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int preSum = nums[0];
int maxSum = preSum;
for (int i = 1; i < nums.length; i++) {
preSum = preSum > 0 ? preSum + nums[i] : nums[i];
maxSum = Math.max(maxSum, preSum);
}
return maxSum;
}

121. Best Time to Buy and Sell Stock (Easy)

public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int soFarMin = prices[0];
int max = 0;
for (int i = 1; i < n; i++) {
if (soFarMin > prices[i]) soFarMin = prices[i];
else max = Math.max(max, prices[i] - soFarMin);
}
return max;
}

## 二分查找

public int binarySearch(int[] nums, int key) {
int l = 0, h = nums.length - 1;
while (l <= h) {
int m = l + (h - l) / 2;
if (nums[m] == key) {
return m;
} else if (nums[m] > key) {
h = m - 1;
} else {
l = m + 1;
}
}
return -1;
}

m 计算

• m = (l + h) / 2
• m = l + (h - l) / 2

l + h 可能出现加法溢出，最好使用第二种方式。

• -1：以一个错误码表示没有查找到 key
• l：将 key 插入到 nums 中的正确位置

public int binarySearch(int[] nums, int key) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= key) {
h = m;
} else {
l = m + 1;
}
}
return l;
}

• 循环条件为 l < h
• h 的赋值表达式为 h = m
• 最后返回 l 而不是 -1

nums = {0, 1, 2}, key = 1
l   m   h
0   1   2  nums[m] >= key
0   0   1  nums[m] < key
1   1   1  nums[m] >= key
1   1   1  nums[m] >= key
...


69. Sqrt(x) (Easy)

Input: 4
Output: 2

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int l = 1, h = x;
while (l <= h) {
int mid = l + (h - l) / 2;
int sqrt = x / mid;
if (sqrt == mid) {
return mid;
} else if (mid > sqrt) {
h = mid - 1;
} else {
l = mid + 1;
}
}
return h;
}

744. Find Smallest Letter Greater Than Target (Easy)

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

public char nextGreatestLetter(char[] letters, char target) {
int n = letters.length;
int l = 0, h = n - 1;
while (l <= h) {
int m = l + (h - l) / 2;
if (letters[m] <= target) {
l = m + 1;
} else {
h = m - 1;
}
}
return l < n ? letters[l] : letters[0];
}

540. Single Element in a Sorted Array (Medium)

Input: [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2

public int singleNonDuplicate(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (m % 2 == 1) {
m--;   // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
}
if (nums[m] == nums[m + 1]) {
l = m + 2;
} else {
h = m;
}
}
return nums[l];
}

public int firstBadVersion(int n) {
int l = 1, h = n;
while (l < h) {
int mid = l + (h - l) / 2;
h = mid;
} else {
l = mid + 1;
}
}
return l;
}

153. Find Minimum in Rotated Sorted Array (Medium)

Input: [3,4,5,1,2],
Output: 1
public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] <= nums[h]) {
h = m;
} else {
l = m + 1;
}
}
return nums[l];
}

34. Search for a Range (Medium)

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
public int[] searchRange(int[] nums, int target) {
int first = binarySearch(nums, target);
int last = binarySearch(nums, target + 1) - 1;
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
} else {
return new int[]{first, Math.max(first, last)};
}
}

private int binarySearch(int[] nums, int target) {
int l = 0, h = nums.length; // 注意 h 的初始值
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= target) {
h = m;
} else {
l = m + 1;
}
}
return l;
}

## 分治

241. Different Ways to Add Parentheses (Medium)

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output : [0, 2]
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ways = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case '+':
break;
case '-':
break;
case '*':
break;
}
}
}
}
}
if (ways.size() == 0) {
}
return ways;
}

## 搜索

### BFS

• 0 -> {6,2,1,5}

• 6 -> {4}
• 2 -> {}
• 1 -> {}
• 5 -> {3}

• 4 -> {}
• 3 -> {}

• 队列：用来存储每一轮遍历得到的节点；
• 标记：对于遍历过的节点，应该将它标记，防止重复遍历。

[[1,1,0,1],
[1,0,1,0],
[1,1,1,1],
[1,0,1,1]]

1 表示可以经过某个位置，求解从 (0, 0) 位置到 (tr, tc) 位置的最短路径长度。

public int minPathLength(int[][] grids, int tr, int tc) {
final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
final int m = grids.length, n = grids[0].length;
Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
int pathLength = 0;
while (!queue.isEmpty()) {
int size = queue.size();
pathLength++;
while (size-- > 0) {
Pair<Integer, Integer> cur = queue.poll();
int cr = cur.getKey(), cc = cur.getValue();
grids[cr][cc] = 0; // 标记
for (int[] d : direction) {
int nr = cr + d[0], nc = cc + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grids[nr][nc] == 0) {
continue;
}
if (nr == tr && nc == tc) {
return pathLength;
}
}
}
}
return -1;
}

279. Perfect Squares (Medium)

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

public int numSquares(int n) {
List<Integer> squares = generateSquares(n);
boolean[] marked = new boolean[n + 1];
marked[n] = true;
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
while (size-- > 0) {
int cur = queue.poll();
for (int s : squares) {
int next = cur - s;
if (next < 0) {
break;
}
if (next == 0) {
return level;
}
if (marked[next]) {
continue;
}
marked[next] = true;
}
}
}
return n;
}

/**
* 生成小于 n 的平方数序列
* @return 1,4,9,...
*/
private List<Integer> generateSquares(int n) {
List<Integer> squares = new ArrayList<>();
int square = 1;
int diff = 3;
while (square <= n) {
square += diff;
diff += 2;
}
return squares;
}

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int N = wordList.size();
int start = N - 1;
int end = 0;
while (end < N && !wordList.get(end).equals(endWord)) {
end++;
}
if (end == N) {
return 0;
}
List<Integer>[] graphic = buildGraphic(wordList);
return getShortestPath(graphic, start, end);
}

private List<Integer>[] buildGraphic(List<String> wordList) {
int N = wordList.size();
List<Integer>[] graphic = new List[N];
for (int i = 0; i < N; i++) {
graphic[i] = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (isConnect(wordList.get(i), wordList.get(j))) {
}
}
}
return graphic;
}

private boolean isConnect(String s1, String s2) {
int diffCnt = 0;
for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
diffCnt++;
}
}
return diffCnt == 1;
}

private int getShortestPath(List<Integer>[] graphic, int start, int end) {
boolean[] marked = new boolean[graphic.length];
marked[start] = true;
int path = 1;
while (!queue.isEmpty()) {
int size = queue.size();
path++;
while (size-- > 0) {
int cur = queue.poll();
for (int next : graphic[cur]) {
if (next == end) {
return path;
}
if (marked[next]) {
continue;
}
marked[next] = true;
}
}
}
return 0;
}

### DFS

• 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
• 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

695. Max Area of Island (Easy)

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
return maxArea;
}

private int dfs(int[][] grid, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
return 0;
}
grid[r][c] = 0;
int area = 1;
for (int[] d : direction) {
area += dfs(grid, r + d[0], c + d[1]);
}
return area;
}

200. Number of Islands (Medium)

Input:
11000
11000
00100
00011

Output: 3

private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int islandsNum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '0') {
dfs(grid, i, j);
islandsNum++;
}
}
}
return islandsNum;
}

private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
for (int[] d : direction) {
dfs(grid, i + d[0], j + d[1]);
}
}

547. Friend Circles (Medium)

Input:
[[1,1,0],
[1,1,0],
[0,0,1]]

Output: 2

Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

private int n;

public int findCircleNum(int[][] M) {
n = M.length;
int circleNum = 0;
boolean[] hasVisited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!hasVisited[i]) {
dfs(M, i, hasVisited);
circleNum++;
}
}
return circleNum;
}

private void dfs(int[][] M, int i, boolean[] hasVisited) {
hasVisited[i] = true;
for (int k = 0; k < n; k++) {
if (M[i][k] == 1 && !hasVisited[k]) {
dfs(M, k, hasVisited);
}
}
}

130. Surrounded Regions (Medium)

For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int m, n;

public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}

m = board.length;
n = board[0].length;

for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int i = 0; i < n; i++) {
dfs(board, 0, i);
dfs(board, m - 1, i);
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'T') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}

private void dfs(char[][] board, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
return;
}
board[r][c] = 'T';
for (int[] d : direction) {
dfs(board, r + d[0], c + d[1]);
}
}

417. Pacific Atlantic Water Flow (Medium)

Given the following 5x5 matrix:

Pacific ~   ~   ~   ~   ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*   *   *   *   * Atlantic

Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> ret = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return ret;
}

m = matrix.length;
n = matrix[0].length;
this.matrix = matrix;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];

for (int i = 0; i < m; i++) {
dfs(i, 0, canReachP);
dfs(i, n - 1, canReachA);
}
for (int i = 0; i < n; i++) {
dfs(0, i, canReachP);
dfs(m - 1, i, canReachA);
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (canReachP[i][j] && canReachA[i][j]) {
}
}
}

return ret;
}

private void dfs(int r, int c, boolean[][] canReach) {
if (canReach[r][c]) {
return;
}
canReach[r][c] = true;
for (int[] d : direction) {
int nextR = d[0] + r;
int nextC = d[1] + c;
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
|| matrix[r][c] > matrix[nextR][nextC]) {

continue;
}
dfs(nextR, nextC, canReach);
}
}

### Backtracking

Backtracking（回溯）属于 DFS。

• 普通 DFS 主要用在 可达性问题 ，这种问题只需要执行到特点的位置然后返回即可。
• 而 Backtracking 主要用于求解 排列组合 问题，例如有 { 'a','b','c' } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

• 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
• 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

17. Letter Combinations of a Phone Number (Medium)

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return combinations;
}
doCombination(new StringBuilder(), combinations, digits);
return combinations;
}

private void doCombination(StringBuilder prefix, List<String> combinations, final String digits) {
if (prefix.length() == digits.length()) {
return;
}
int curDigits = digits.charAt(prefix.length()) - '0';
String letters = KEYS[curDigits];
for (char c : letters.toCharArray()) {
prefix.append(c);                         // 添加
doCombination(prefix, combinations, digits);
prefix.deleteCharAt(prefix.length() - 1); // 删除
}
}

IP 地址划分

Given "25525511135",
return ["255.255.11.135", "255.255.111.35"].
public List<String> restoreIpAddresses(String s) {
}

if (k == 4 || s.length() == 0) {
if (k == 4 && s.length() == 0) {
}
return;
}
for (int i = 0; i < s.length() && i <= 2; i++) {
if (i != 0 && s.charAt(0) == '0') {
break;
}
String part = s.substring(0, i + 1);
if (Integer.valueOf(part) <= 255) {
part = "." + part;
}
}
}
}

79. Word Search (Medium)

For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
private final static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int m;
private int n;

public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) {
return true;
}
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}

m = board.length;
n = board[0].length;
boolean[][] hasVisited = new boolean[m][n];

for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (backtracking(0, r, c, hasVisited, board, word)) {
return true;
}
}
}

return false;
}

private boolean backtracking(int curLen, int r, int c, boolean[][] visited, final char[][] board, final String word) {
if (curLen == word.length()) {
return true;
}
if (r < 0 || r >= m || c < 0 || c >= n
|| board[r][c] != word.charAt(curLen) || visited[r][c]) {

return false;
}

visited[r][c] = true;

for (int[] d : direction) {
if (backtracking(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
return true;
}
}

visited[r][c] = false;

return false;
}

257. Binary Tree Paths (Easy)

  1
/  \
2    3
\
5
["1->2->5", "1->3"]
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) {
return paths;
}
List<Integer> values = new ArrayList<>();
backtracking(root, values, paths);
return paths;
}

private void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
if (node == null) {
return;
}
if (isLeaf(node)) {
} else {
backtracking(node.left, values, paths);
backtracking(node.right, values, paths);
}
values.remove(values.size() - 1);
}

private boolean isLeaf(TreeNode node) {
return node.left == null && node.right == null;
}

private String buildPath(List<Integer> values) {
StringBuilder str = new StringBuilder();
for (int i = 0; i < values.size(); i++) {
str.append(values.get(i));
if (i != values.size() - 1) {
str.append("->");
}
}
return str.toString();
}

46. Permutations (Medium)

[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}

private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
if (permuteList.size() == nums.length) {
return;
}
for (int i = 0; i < visited.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
backtracking(permuteList, permutes, visited, nums);
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}

47. Permutations II (Medium)

[1,1,2] have the following unique permutations:
[[1,1,2], [1,2,1], [2,1,1]]

public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
Arrays.sort(nums);  // 排序
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}

private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
if (permuteList.size() == nums.length) {
return;
}

for (int i = 0; i < visited.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;  // 防止重复
}
if (visited[i]){
continue;
}
visited[i] = true;
backtracking(permuteList, permutes, visited, nums);
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}

77. Combinations (Medium)

If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> combineList = new ArrayList<>();
backtracking(combineList, combinations, 1, k, n);
return combinations;
}

private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
if (k == 0) {
return;
}
for (int i = start; i <= n - k + 1; i++) {  // 剪枝
backtracking(combineList, combinations, i + 1, k - 1, n);
combineList.remove(combineList.size() - 1);
}
}

39. Combination Sum (Medium)

given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[[7],[2, 2, 3]]
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
backtracking(new ArrayList<>(), combinations, 0, target, candidates);
return combinations;
}

private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
int start, int target, final int[] candidates) {

if (target == 0) {
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] <= target) {
backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
tempCombination.remove(tempCombination.size() - 1);
}
}
}

40. Combination Sum II (Medium)

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
Arrays.sort(candidates);
backtracking(new ArrayList<>(), combinations, new boolean[candidates.length], 0, target, candidates);
return combinations;
}

private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
boolean[] hasVisited, int start, int target, final int[] candidates) {

if (target == 0) {
return;
}
for (int i = start; i < candidates.length; i++) {
if (i != 0 && candidates[i] == candidates[i - 1] && !hasVisited[i - 1]) {
continue;
}
if (candidates[i] <= target) {
hasVisited[i] = true;
backtracking(tempCombination, combinations, hasVisited, i + 1, target - candidates[i], candidates);
hasVisited[i] = false;
tempCombination.remove(tempCombination.size() - 1);
}
}
}

1-9 数字的组合求和

216. Combination Sum III (Medium)

Input: k = 3, n = 9

Output:

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

public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtracking(k, n, 1, path, combinations);
return combinations;
}

private void backtracking(int k, int n, int start,
List<Integer> tempCombination, List<List<Integer>> combinations) {

if (k == 0 && n == 0) {
return;
}
if (k == 0 || n == 0) {
return;
}
for (int i = start; i <= 9; i++) {
backtracking(k - 1, n - i, i + 1, tempCombination, combinations);
tempCombination.remove(tempCombination.size() - 1);
}
}

78. Subsets (Medium)

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, size, nums); // 不同的子集大小
}
return subsets;
}

private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets,
final int size, final int[] nums) {

if (tempSubset.size() == size) {
return;
}
for (int i = start; i < nums.length; i++) {
backtracking(i + 1, tempSubset, subsets, size, nums);
tempSubset.remove(tempSubset.size() - 1);
}
}

90. Subsets II (Medium)

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
}
return subsets;
}

private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
final int size, final int[] nums) {

if (tempSubset.size() == size) {
return;
}
for (int i = start; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
continue;
}
hasVisited[i] = true;
backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
hasVisited[i] = false;
tempSubset.remove(tempSubset.size() - 1);
}
}

131. Palindrome Partitioning (Medium)

For example, given s = "aab",
Return

[
["aa","b"],
["a","a","b"]
]
public List<List<String>> partition(String s) {
List<List<String>> partitions = new ArrayList<>();
List<String> tempPartition = new ArrayList<>();
doPartition(s, partitions, tempPartition);
return partitions;
}

private void doPartition(String s, List<List<String>> partitions, List<String> tempPartition) {
if (s.length() == 0) {
return;
}
for (int i = 0; i < s.length(); i++) {
if (isPalindrome(s, 0, i)) {
doPartition(s.substring(i + 1), partitions, tempPartition);
tempPartition.remove(tempPartition.size() - 1);
}
}
}

private boolean isPalindrome(String s, int begin, int end) {
while (begin < end) {
if (s.charAt(begin++) != s.charAt(end--)) {
return false;
}
}
return true;
}

37. Sudoku Solver (Hard)

private boolean[][] rowsUsed = new boolean[9][10];
private boolean[][] colsUsed = new boolean[9][10];
private boolean[][] cubesUsed = new boolean[9][10];
private char[][] board;

public void solveSudoku(char[][] board) {
this.board = board;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
continue;
}
int num = board[i][j] - '0';
rowsUsed[i][num] = true;
colsUsed[j][num] = true;
cubesUsed[cubeNum(i, j)][num] = true;
}

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
backtracking(i, j);
}
}
}

private boolean backtracking(int row, int col) {
while (row < 9 && board[row][col] != '.') {
row = col == 8 ? row + 1 : row;
col = col == 8 ? 0 : col + 1;
}
if (row == 9) {
return true;
}
for (int num = 1; num <= 9; num++) {
if (rowsUsed[row][num] || colsUsed[col][num] || cubesUsed[cubeNum(row, col)][num]) {
continue;
}
rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = true;
board[row][col] = (char) (num + '0');
if (backtracking(row, col)) {
return true;
}
board[row][col] = '.';
rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = false;
}
return false;
}

private int cubeNum(int i, int j) {
int r = i / 3;
int c = j / 3;
return r * 3 + c;
}

N 皇后

51. N-Queens (Hard)

45 度对角线标记数组的长度为 2 * n - 1，通过下图可以明确 (r, c) 的位置所在的数组下标为 r + c。

135 度对角线标记数组的长度也是 2 * n - 1，(r, c) 的位置所在的数组下标为 n - 1 - (r - c)。

private List<List<String>> solutions;
private char[][] nQueens;
private boolean[] colUsed;
private boolean[] diagonals45Used;
private boolean[] diagonals135Used;
private int n;

public List<List<String>> solveNQueens(int n) {
solutions = new ArrayList<>();
nQueens = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(nQueens[i], '.');
}
colUsed = new boolean[n];
diagonals45Used = new boolean[2 * n - 1];
diagonals135Used = new boolean[2 * n - 1];
this.n = n;
backtracking(0);
return solutions;
}

private void backtracking(int row) {
if (row == n) {
List<String> list = new ArrayList<>();
for (char[] chars : nQueens) {
}
return;
}

for (int col = 0; col < n; col++) {
int diagonals45Idx = row + col;
int diagonals135Idx = n - 1 - (row - col);
if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]) {
continue;
}
nQueens[row][col] = 'Q';
colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = true;
backtracking(row + 1);
colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = false;
nQueens[row][col] = '.';
}
}

## 动态规划

### 斐波那契数列

70. Climbing Stairs (Easy)

public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2;
for (int i = 2; i < n; i++) {
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}

198. House Robber (Easy)

public int rob(int[] nums) {
int pre2 = 0, pre1 = 0;
for (int i = 0; i < nums.length; i++) {
int cur = Math.max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}

213. House Robber II (Medium)

public  int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}

private   int rob(int[] nums, int first, int last) {
int pre2 = 0, pre1 = 0;
for (int i = first; i <= last; i++) {
int cur = Math.max(pre1, pre2 + nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}

• i==k，交换 i 和 k 的信后，它们的信和信封在正确的位置，但是其余 i-2 封信有 dp[i-2] 种错误装信的方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-2] 种错误装信方式。
• i != k，交换 i 和 j 的信后，第 i 个信和信封在正确的位置，其余 i-1 封信有 dp[i-1] 种错误装信方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-1] 种错误装信方式。

### 矩阵路径

64. Minimum Path Sum (Medium)

[[1,3,1],
[1,5,1],
[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) {
dp[j] = dp[j - 1];
} else {
dp[j] = Math.min(dp[j - 1], dp[j]);
}
dp[j] += grid[i][j];
}
}
return dp[n - 1];
}

62. Unique Paths (Medium)

public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}

public int uniquePaths(int m, int n) {
int S = m + n - 2;  // 总共的移动次数
int D = m - 1;      // 向下的移动次数
long ret = 1;
for (int i = 1; i <= D; i++) {
ret = ret * (S - D + i) / i;
}
return (int) ret;
}

### 数组区间

303. Range Sum Query - Immutable (Easy)

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

class NumArray {

private int[] sums;

public NumArray(int[] nums) {
sums = new int[nums.length + 1];
for (int i = 1; i <= nums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
}

public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}

413. Arithmetic Slices (Medium)

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

dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。

public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int n = A.length;
int[] dp = new int[n];
for (int i = 2; i < n; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
}
}
int total = 0;
for (int cnt : dp) {
total += cnt;
}
}

### 分割整数

343. Integer Break (Medim)

public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
}
}
return dp[n];
}

279. Perfect Squares(Medium)

public int numSquares(int n) {
List<Integer> squareList = generateSquareList(n);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int square : squareList) {
if (square > i) {
break;
}
min = Math.min(min, dp[i - square] + 1);
}
dp[i] = min;
}
return dp[n];
}

private List<Integer> generateSquareList(int n) {
List<Integer> squareList = new ArrayList<>();
int diff = 3;
int square = 1;
while (square <= n) {
square += diff;
diff += 2;
}
return squareList;
}

91. Decode Ways (Medium)

public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int one = Integer.valueOf(s.substring(i - 1, i));
if (one != 0) {
dp[i] += dp[i - 1];
}
if (s.charAt(i - 2) == '0') {
continue;
}
int two = Integer.valueOf(s.substring(i - 2, i));
if (two <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}

### 最长递增子序列

300. Longest Increasing Subsequence (Medium)

public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
int max = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
max = Math.max(max, dp[j] + 1);
}
}
dp[i] = max;
}
return Arrays.stream(dp).max().orElse(0);
}

int ret = 0;
for (int i = 0; i < n; i++) {
ret = Math.max(ret, dp[i]);
}
return ret;

• 如果它大于 tails 数组所有的值，那么把它添加到 tails 后面，表示最长递增子序列长度加 1；
• 如果 tails[i-1] < x <= tails[i]，那么更新 tails[i] = x。

tails      len      num
[]         0        4
[4]        1        3
[3]        1        6
[3,6]      2        5
[3,5]      2        null

public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] tails = new int[n];
int len = 0;
for (int num : nums) {
int index = binarySearch(tails, len, num);
tails[index] = num;
if (index == len) {
len++;
}
}
return len;
}

private int binarySearch(int[] tails, int len, int key) {
int l = 0, h = len;
while (l < h) {
int mid = l + (h - l) / 2;
if (tails[mid] == key) {
return mid;
} else if (tails[mid] > key) {
h = mid;
} else {
l = mid + 1;
}
}
return l;
}

646. Maximum Length of Pair Chain (Medium)

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

public int findLongestChain(int[][] pairs) {
if (pairs == null || pairs.length == 0) {
return 0;
}
Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
int n = pairs.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Arrays.stream(dp).max().orElse(0);
}

376. Wiggle Subsequence (Medium)

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

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

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

public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}

### 最长公共子序列

• 当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。
• 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。

• 针对的是两个序列，求它们的最长公共子序列。
• 在最长递增子序列中，dp[i] 表示以 Si 为结尾的最长递增子序列长度，子序列必须包含 Si ；在最长公共子序列中，dp[i][j] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含 S1i 和 S2j
• 在求最终解时，最长公共子序列中 dp[N][M] 就是最终解，而最长递增子序列中 dp[N] 不是最终解，因为以 SN 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。
public int lengthOfLCS(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}

### 0-1 背包

• 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
• 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。

public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = 1; j <= W; j++) {
if (j >= w) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}

public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = W; j >= 1; j--) {
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
return dp[W];
}

0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.

id w v v/w
0 1 6 6
1 2 10 5
2 3 12 4

• 完全背包：物品数量为无限个

• 多重背包：物品数量有限制

• 多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制

• 其它：物品之间相互约束或者依赖

416. Partition Equal Subset Sum (Medium)

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

public boolean canPartition(int[] nums) {
int sum = computeArraySum(nums);
if (sum % 2 != 0) {
return false;
}
int W = sum / 2;
boolean[] dp = new boolean[W + 1];
dp[0] = true;
Arrays.sort(nums);
for (int num : nums) {                 // 0-1 背包一个物品只能用一次
for (int i = W; i >= num; i--) {   // 从后往前，先计算 dp[i] 再计算 dp[i-num]
dp[i] = dp[i] || dp[i - num];
}
}
return dp[W];
}

private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}

494. Target Sum (Medium)

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

                  sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)

public int findTargetSumWays(int[] nums, int S) {
int sum = computeArraySum(nums);
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int W = (sum + S) / 2;
int[] dp = new int[W + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = W; i >= num; i--) {
dp[i] = dp[i] + dp[i - num];
}
}
return dp[W];
}

private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}

DFS 解法：

public int findTargetSumWays(int[] nums, int S) {
return findTargetSumWays(nums, 0, S);
}

private int findTargetSumWays(int[] nums, int start, int S) {
if (start == nums.length) {
return S == 0 ? 1 : 0;
}
return findTargetSumWays(nums, start + 1, S + nums[start])
+ findTargetSumWays(nums, start + 1, S - nums[start]);
}

139. Word Break (Medium)

s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。

0-1 背包和完全背包在实现上的不同之处是，0-1 背包对物品的迭代是在最外层，而完全背包对物品的迭代是在最里层。

public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) {   // 完全一个物品可以使用多次
int len = word.length();
if (len <= i && word.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}

01 字符构成最多的字符串

474. Ones and Zeroes (Medium)

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0"

public int findMaxForm(String[] strs, int m, int n) {
if (strs == null || strs.length == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) {    // 每个字符串只能用一次
int ones = 0, zeros = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
zeros++;
} else {
ones++;
}
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}

322. Coin Change (Medium)

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

• 物品：硬币
• 物品大小：面额
• 物品价值：数量

public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return 0;
}
int[] minimum = new int[amount + 1];
Arrays.fill(minimum, amount + 1);
minimum[0] = 0;
Arrays.sort(coins);
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length && coins[j] <= i; j++) {
minimum[i] = Math.min(minimum[i], minimum[i - coins[j]] + 1);
}
}
return minimum[amount] > amount ? -1 : minimum[amount];
}

377. Combination Sum IV (Medium)

nums = [1, 2, 3]
target = 4

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

Note that different sequences are counted as different combinations.

Therefore the output is 7.

public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] maximum = new int[target + 1];
maximum[0] = 1;
Arrays.sort(nums);
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length && nums[j] <= i; j++) {
maximum[i] += maximum[i - nums[j]];
}
}
return maximum[target];
}

### 股票交易

309. Best Time to Buy and Sell Stock with Cooldown(Medium)

public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int N = prices.length;
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = s2[i - 1] - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}

714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Selling at prices[3] = 8
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

public int maxProfit(int[] prices, int fee) {
int N = prices.length;
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = Math.max(sell[i - 1], s2[i - 1]) - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) - fee + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}

123. Best Time to Buy and Sell Stock III (Hard)

public int maxProfit(int[] prices) {
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int curPrice : prices) {
}
if (firstSell < firstBuy + curPrice) {
}
if (secondBuy < firstSell - curPrice) {
}
if (secondSell < secondBuy + curPrice) {
}
}
return secondSell;
}

188. Best Time to Buy and Sell Stock IV (Hard)

public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) {   // 这种情况下该问题退化为普通的股票交易问题
int maxProfit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
int[][] maxProfit = new int[k + 1][n];
for (int i = 1; i <= k; i++) {
int localMax = maxProfit[i - 1][0] - prices[0];
for (int j = 1; j < n; j++) {
maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
}
}
return maxProfit[k][n - 1];
}

### 字符串编辑

583. Delete Operation for Two Strings (Medium)

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return m + n - 2 * dp[m][n];
}

72. Edit Distance (Hard)

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[m][n];
}

650. 2 Keys Keyboard (Medium)

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

public int minSteps(int n) {
if (n == 1) return 0;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return i + minSteps(n / i);
}
return n;
}
public int minSteps(int n) {
int[] dp = new int[n + 1];
int h = (int) Math.sqrt(n);
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j <= h; j++) {
if (i % j == 0) {
dp[i] = dp[j] + dp[i / j];
break;
}
}
}
return dp[n];
}

## 数学

### 素数

x 和 y 的最大公约数为：gcd(x,y) = 2min(m0,n0) * 3min(m1,n1) * 5min(m2,n2) * ...

x 和 y 的最小公倍数为：lcm(x,y) = 2max(m0,n0) * 3max(m1,n1) * 5max(m2,n2) * ...

204. Count Primes (Easy)

public int countPrimes(int n) {
boolean[] notPrimes = new boolean[n + 1];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrimes[i]) {
continue;
}
count++;
// 从 i * i 开始，因为如果 k < i，那么 k * i 在之前就已经被去除过了
for (long j = (long) (i) * i; j < n; j += i) {
notPrimes[(int) j] = true;
}
}
return count;
}

### 最大公约数

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
return a * b / gcd(a, b);
}

• 如果 a 和 b 均为偶数，f(a, b) = 2*f(a/2, b/2);
• 如果 a 是偶数 b 是奇数，f(a, b) = f(a/2, b);
• 如果 b 是偶数 a 是奇数，f(a, b) = f(a, b/2);
• 如果 a 和 b 均为奇数，f(a, b) = f(b, a-b);

public int gcd(int a, int b) {
if (a < b) {
return gcd(b, a);
}
if (b == 0) {
return a;
}
boolean isAEven = isEven(a), isBEven = isEven(b);
if (isAEven && isBEven) {
return 2 * gcd(a >> 1, b >> 1);
} else if (isAEven && !isBEven) {
return gcd(a >> 1, b);
} else if (!isAEven && isBEven) {
return gcd(a, b >> 1);
} else {
return gcd(b, a - b);
}
}

### 进制转换

7 进制

504. Base 7 (Easy)

public String convertToBase7(int num) {
if (num == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
boolean isNegative = num < 0;
if (isNegative) {
num = -num;
}
while (num > 0) {
sb.append(num % 7);
num /= 7;
}
String ret = sb.reverse().toString();
return isNegative ? "-" + ret : ret;
}

public String convertToBase7(int num) {
return Integer.toString(num, 7);
}

16 进制

405. Convert a Number to Hexadecimal (Easy)

Input:
26

Output:
"1a"

Input:
-1

Output:
"ffffffff"

public String toHex(int num) {
char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
if (num == 0) return "0";
StringBuilder sb = new StringBuilder();
while (num != 0) {
sb.append(map[num & 0b1111]);
num >>>= 4; // 因为考虑的是补码形式，因此符号位就不能有特殊的意义，需要使用无符号右移，左边填 0
}
return sb.reverse().toString();
}

26 进制

168. Excel Sheet Column Title (Easy)

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB

public String convertToTitle(int n) {
if (n == 0) {
return "";
}
n--;
return convertToTitle(n / 26) + (char) (n % 26 + 'A');
}

### 阶乘

172. Factorial Trailing Zeroes (Easy)

public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}

### 字符串加法减法

a = "11"
b = "1"
Return "100".
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, carry = 0;
StringBuilder str = new StringBuilder();
while (carry == 1 || i >= 0 || j >= 0) {
if (i >= 0 && a.charAt(i--) == '1') {
carry++;
}
if (j >= 0 && b.charAt(j--) == '1') {
carry++;
}
str.append(carry % 2);
carry /= 2;
}
return str.reverse().toString();
}

public String addStrings(String num1, String num2) {
StringBuilder str = new StringBuilder();
int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
while (carry == 1 || i >= 0 || j >= 0) {
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
str.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return str.reverse().toString();
}

### 相遇问题

462. Minimum Moves to Equal Array Elements II (Medium)

Input:
[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

public int minMoves2(int[] nums) {
Arrays.sort(nums);
int move = 0;
int l = 0, h = nums.length - 1;
while (l <= h) {
move += nums[h] - nums[l];
l++;
h--;
}
return move;
}

public int minMoves2(int[] nums) {
int move = 0;
int median = findKthSmallest(nums, nums.length / 2);
for (int num : nums) {
move += Math.abs(num - median);
}
return move;
}

private int findKthSmallest(int[] nums, int k) {
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k) {
break;
}
if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}

private int partition(int[] nums, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (nums[++i] < nums[l] && i < h) ;
while (nums[--j] > nums[l] && j > l) ;
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}

### 多数投票问题

169. Majority Element (Easy)

public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}

public int majorityElement(int[] nums) {
int cnt = 0, majority = nums[0];
for (int num : nums) {
majority = (cnt == 0) ? num : majority;
cnt = (majority == num) ? cnt + 1 : cnt - 1;
}
return majority;
}

### 其它

367. Valid Perfect Square (Easy)

Input: 16
Returns: True

public boolean isPerfectSquare(int num) {
int subNum = 1;
while (num > 0) {
num -= subNum;
subNum += 2;
}
return num == 0;
}

3 的 n 次方

326. Power of Three (Easy)

public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}

238. Product of Array Except Self (Medium)

For example, given [1,2,3,4], return [24,12,8,6].

public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] products = new int[n];
Arrays.fill(products, 1);
int left = 1;
for (int i = 1; i < n; i++) {
left *= nums[i - 1];
products[i] *= left;
}
int right = 1;
for (int i = n - 2; i >= 0; i--) {
right *= nums[i + 1];
products[i] *= right;
}
return products;
}

628. Maximum Product of Three Numbers (Easy)

Input: [1,2,3,4]
Output: 24
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int n : nums) {
if (n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (n > max2) {
max3 = max2;
max2 = n;
} else if (n > max3) {
max3 = n;
}

if (n < min1) {
min2 = min1;
min1 = n;
} else if (n < min2) {
min2 = n;
}
}
return Math.max(max1*max2*max3, max1*min1*min2);
}

# 数据结构相关

## 链表

160. Intersection of Two Linked Lists (Easy)

A:          a1 → a2
↘
c1 → c2 → c3
↗
B:    b1 → b2 → b3

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
while (l1 != l2) {
l1 = (l1 == null) ? headB : l1.next;
l2 = (l2 == null) ? headA : l2.next;
}
return l1;
}

• 把第一个链表的结尾连接到第二个链表的开头，看第二个链表是否存在环；
• 或者直接比较两个链表的最后一个节点是否相同。

public ListNode reverseList(ListNode head) {
}
}

public ListNode reverseList(ListNode head) {
}
}

21. Merge Two Sorted Lists (Easy)

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}

83. Remove Duplicates from Sorted List (Easy)

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
public ListNode deleteDuplicates(ListNode head) {
}

19. Remove Nth Node From End of List (Medium)

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
public ListNode removeNthFromEnd(ListNode head, int n) {
while (n-- > 0) {
fast = fast.next;
}
if (fast == null) return head.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
}

24. Swap Nodes in Pairs (Medium)

Given 1->2->3->4, you should return the list as 2->1->4->3.

public ListNode swapPairs(ListNode head) {
ListNode node = new ListNode(-1);
ListNode pre = node;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next, l2 = pre.next.next;
ListNode next = l2.next;
l1.next = next;
l2.next = l1;
pre.next = l2;

pre = l1;
}
return node.next;
}

445. Add Two Numbers II (Medium)

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> l1Stack = buildStack(l1);
Stack<Integer> l2Stack = buildStack(l2);
int carry = 0;
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
}
}

private Stack<Integer> buildStack(ListNode l) {
Stack<Integer> stack = new Stack<>();
while (l != null) {
stack.push(l.val);
l = l.next;
}
return stack;
}

public boolean isPalindrome(ListNode head) {
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) slow = slow.next;  // 偶数节点，让 slow 指向下一个节点
}

private void cut(ListNode head, ListNode cutNode) {
}
}

}
}

private boolean isEqual(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
if (l1.val != l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}

725. Split Linked List in Parts(Medium)

Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

public ListNode[] splitListToParts(ListNode root, int k) {
int N = 0;
ListNode cur = root;
while (cur != null) {
N++;
cur = cur.next;
}
int mod = N % k;
int size = N / k;
ListNode[] ret = new ListNode[k];
cur = root;
for (int i = 0; cur != null && i < k; i++) {
ret[i] = cur;
int curSize = size + (mod-- > 0 ? 1 : 0);
for (int j = 0; j < curSize - 1; j++) {
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return ret;
}

328. Odd Even Linked List (Medium)

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
public ListNode oddEvenList(ListNode head) {
}
while (even != null && even.next != null) {
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
}

## 树

### 递归

104. Maximum Depth of Binary Tree (Easy)

public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

110. Balanced Binary Tree (Easy)

    3
/ \
9  20
/  \
15   7

private boolean result = true;

public boolean isBalanced(TreeNode root) {
maxDepth(root);
return result;
}

public int maxDepth(TreeNode root) {
if (root == null) return 0;
int l = maxDepth(root.left);
int r = maxDepth(root.right);
if (Math.abs(l - r) > 1) result = false;
return 1 + Math.max(l, r);
}

543. Diameter of Binary Tree (Easy)

Input:

1
/ \
2  3
/ \
4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return max;
}

private int depth(TreeNode root) {
if (root == null) return 0;
int leftDepth = depth(root.left);
int rightDepth = depth(root.right);
max = Math.max(max, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}

226. Invert Binary Tree (Easy)

public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = root.left;  // 后面的操作会改变 left 指针，因此先保存下来
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}

617. Merge Two Binary Trees (Easy)

Input:
Tree 1                     Tree 2
1                         2
/ \                       / \
3   2                     1   3
/                           \   \
5                             4   7

Output:
3
/ \
4   5
/ \   \
5   4   7
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return null;
if (t1 == null) return t2;
if (t2 == null) return t1;
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}

Leetcdoe : 112. Path Sum (Easy)

Given the below binary tree and sum = 22,

5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == sum) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

437. Path Sum III (Easy)

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/  \
5   -3
/ \    \
3   2   11
/ \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return ret;
}

private int pathSumStartWithRoot(TreeNode root, int sum) {
if (root == null) return 0;
int ret = 0;
if (root.val == sum) ret++;
ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
return ret;
}

572. Subtree of Another Tree (Easy)

Given tree s:
3
/ \
4   5
/ \
1   2

Given tree t:
4
/ \
1   2

Return true, because t has the same structure and node values with a subtree of s.

Given tree s:

3
/ \
4   5
/ \
1   2
/
0

Given tree t:
4
/ \
1   2

Return false.
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
if (t == null && s == null) return true;
if (t == null || s == null) return false;
if (t.val != s.val) return false;
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}

101. Symmetric Tree (Easy)

    1
/ \
2   2
/ \ / \
3  4 4  3
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}

111. Minimum Depth of Binary Tree (Easy)

public int minDepth(TreeNode root) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
if (left == 0 || right == 0) return left + right + 1;
return Math.min(left, right) + 1;
}

404. Sum of Left Leaves (Easy)

    3
/ \
9  20
/  \
15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
if (isLeaf(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}

private boolean isLeaf(TreeNode node){
if (node == null) return false;
return node.left == null && node.right == null;
}

687. Longest Univalue Path (Easy)

             1
/ \
4   5
/ \   \
4   4   5

Output : 2
private int path = 0;

public int longestUnivaluePath(TreeNode root) {
dfs(root);
return path;
}

private int dfs(TreeNode root){
if (root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
path = Math.max(path, leftPath + rightPath);
return Math.max(leftPath, rightPath);
}

337. House Robber III (Medium)

     3
/ \
2   3
\   \
3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
public int rob(TreeNode root) {
if (root == null) return 0;
int val1 = root.val;
if (root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
if (root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
int val2 = rob(root.left) + rob(root.right);
return Math.max(val1, val2);
}

671. Second Minimum Node In a Binary Tree (Easy)

Input:
2
/ \
2   5
/ \
5  7

Output: 5

public int findSecondMinimumValue(TreeNode root) {
if (root == null) return -1;
if (root.left == null && root.right == null) return -1;
int leftVal = root.left.val;
int rightVal = root.right.val;
if (leftVal == root.val) leftVal = findSecondMinimumValue(root.left);
if (rightVal == root.val) rightVal = findSecondMinimumValue(root.right);
if (leftVal != -1 && rightVal != -1) return Math.min(leftVal, rightVal);
if (leftVal != -1) return leftVal;
return rightVal;
}

### 层次遍历

637. Average of Levels in Binary Tree (Easy)

public List<Double> averageOfLevels(TreeNode root) {
List<Double> ret = new ArrayList<>();
if (root == null) return ret;
while (!queue.isEmpty()) {
int cnt = queue.size();
double sum = 0;
for (int i = 0; i < cnt; i++) {
TreeNode node = queue.poll();
sum += node.val;
}
}
return ret;
}

513. Find Bottom Left Tree Value (Easy)

Input:

1
/ \
2   3
/   / \
4   5   6
/
7

Output:
7
public int findBottomLeftValue(TreeNode root) {
while (!queue.isEmpty()) {
root = queue.poll();
}
return root.val;
}

### 前中后序遍历

    1
/ \
2   3
/ \   \
4   5   6
• 层次遍历顺序：[1 2 3 4 5 6]
• 前序遍历顺序：[1 2 4 5 3 6]
• 中序遍历顺序：[4 2 5 1 3 6]
• 后序遍历顺序：[4 5 2 6 3 1]

① 前序

void dfs(TreeNode root) {
visit(root);
dfs(root.left);
dfs(root.right);
}

② 中序

void dfs(TreeNode root) {
dfs(root.left);
visit(root);
dfs(root.right);
}

③ 后序

void dfs(TreeNode root) {
dfs(root.left);
dfs(root.right);
visit(root);
}

144. Binary Tree Preorder Traversal (Medium)

public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
stack.push(node.right);  // 先右后左，保证左子树先遍历
stack.push(node.left);
}
return ret;
}

145. Binary Tree Postorder Traversal (Medium)

public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
stack.push(node.left);
stack.push(node.right);
}
Collections.reverse(ret);
return ret;
}

94. Binary Tree Inorder Traversal (Medium)

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
cur = node.right;
}
return ret;
}

### BST

669. Trim a Binary Search Tree (Easy)

Input:

3
/ \
0   4
\
2
/
1

L = 1
R = 3

Output:

3
/
2
/
1

public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val > R) return trimBST(root.left, L, R);
if (root.val < L) return trimBST(root.right, L, R);
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}

230. Kth Smallest Element in a BST (Medium)

private int cnt = 0;
private int val;

public int kthSmallest(TreeNode root, int k) {
inOrder(root, k);
return val;
}

private void inOrder(TreeNode node, int k) {
if (node == null) return;
inOrder(node.left, k);
cnt++;
if (cnt == k) {
val = node.val;
return;
}
inOrder(node.right, k);
}

public int kthSmallest(TreeNode root, int k) {
int leftCnt = count(root.left);
if (leftCnt == k - 1) return root.val;
if (leftCnt > k - 1) return kthSmallest(root.left, k);
return kthSmallest(root.right, k - leftCnt - 1);
}

private int count(TreeNode node) {
if (node == null) return 0;
return 1 + count(node.left) + count(node.right);
}

Convert BST to Greater Tree (Easy)

Input: The root of a Binary Search Tree like this:

5
/   \
2     13

Output: The root of a Greater Tree like this:

18
/   \
20     13

private int sum = 0;

public TreeNode convertBST(TreeNode root) {
traver(root);
return root;
}

private void traver(TreeNode node) {
if (node == null) return;
traver(node.right);
sum += node.val;
node.val = sum;
traver(node.left);
}

235. Lowest Common Ancestor of a Binary Search Tree (Easy)

        _______6______
/                \
___2__             ___8__
/      \           /      \
0        4         7        9
/  \
3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}

236. Lowest Common Ancestor of a Binary Tree (Medium)

       _______3______
/              \
___5__           ___1__
/      \         /      \
6        2       0        8
/  \
7    4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left == null ? right : right == null ? left : root;
}

108. Convert Sorted Array to Binary Search Tree (Easy)

public TreeNode sortedArrayToBST(int[] nums) {
}

private TreeNode toBST(int[] nums, int sIdx, int eIdx){
if (sIdx > eIdx) return null;
int mIdx = (sIdx + eIdx) / 2;
TreeNode root = new TreeNode(nums[mIdx]);
root.left =  toBST(nums, sIdx, mIdx - 1);
root.right = toBST(nums, mIdx + 1, eIdx);
return root;
}

109. Convert Sorted List to Binary Search Tree (Medium)

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
ListNode mid = preMid.next;
preMid.next = null;  // 断开链表
TreeNode t = new TreeNode(mid.val);
t.right = sortedListToBST(mid.next);
return t;
}

while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
return pre;
}

653. Two Sum IV - Input is a BST (Easy)

Input:

5
/ \
3   6
/ \   \
2   4   7

Target = 9

Output: True

public boolean findTarget(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inOrder(root, nums);
int i = 0, j = nums.size() - 1;
while (i < j) {
int sum = nums.get(i) + nums.get(j);
if (sum == k) return true;
if (sum < k) i++;
else j--;
}
return false;
}

private void inOrder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inOrder(root.left, nums);
inOrder(root.right, nums);
}

530. Minimum Absolute Difference in BST (Easy)

Input:

1
\
3
/
2

Output:

1

private int minDiff = Integer.MAX_VALUE;
private TreeNode preNode = null;

public int getMinimumDifference(TreeNode root) {
inOrder(root);
return minDiff;
}

private void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);
preNode = node;
inOrder(node.right);
}

501. Find Mode in Binary Search Tree (Easy)

   1
\
2
/
2

return [2].

private int curCnt = 1;
private int maxCnt = 1;
private TreeNode preNode = null;

public int[] findMode(TreeNode root) {
List<Integer> maxCntNums = new ArrayList<>();
inOrder(root, maxCntNums);
int[] ret = new int[maxCntNums.size()];
int idx = 0;
for (int num : maxCntNums) {
ret[idx++] = num;
}
return ret;
}

private void inOrder(TreeNode node, List<Integer> nums) {
if (node == null) return;
inOrder(node.left, nums);
if (preNode != null) {
if (preNode.val == node.val) curCnt++;
else curCnt = 1;
}
if (curCnt > maxCnt) {
maxCnt = curCnt;
nums.clear();
} else if (curCnt == maxCnt) {
}
preNode = node;
inOrder(node.right, nums);
}

### Trie

Trie，又称前缀树或字典树，用于判断字符串是否存在或者是否具有某种字符串前缀。

208. Implement Trie (Prefix Tree) (Medium)

class Trie {

private class Node {
Node[] childs = new Node[26];
boolean isLeaf;
}

private Node root = new Node();

public Trie() {
}

public void insert(String word) {
insert(word, root);
}

private void insert(String word, Node node) {
if (node == null) return;
if (word.length() == 0) {
node.isLeaf = true;
return;
}
int index = indexForChar(word.charAt(0));
if (node.childs[index] == null) {
node.childs[index] = new Node();
}
insert(word.substring(1), node.childs[index]);
}

public boolean search(String word) {
return search(word, root);
}

private boolean search(String word, Node node) {
if (node == null) return false;
if (word.length() == 0) return node.isLeaf;
int index = indexForChar(word.charAt(0));
return search(word.substring(1), node.childs[index]);
}

public boolean startsWith(String prefix) {
return startWith(prefix, root);
}

private boolean startWith(String prefix, Node node) {
if (node == null) return false;
if (prefix.length() == 0) return true;
int index = indexForChar(prefix.charAt(0));
return startWith(prefix.substring(1), node.childs[index]);
}

private int indexForChar(char c) {
return c - 'a';
}
}

677. Map Sum Pairs (Medium)

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
class MapSum {

private class Node {
Node[] child = new Node[26];
int value;
}

private Node root = new Node();

public MapSum() {

}

public void insert(String key, int val) {
insert(key, root, val);
}

private void insert(String key, Node node, int val) {
if (node == null) return;
if (key.length() == 0) {
node.value = val;
return;
}
int index = indexForChar(key.charAt(0));
if (node.child[index] == null) {
node.child[index] = new Node();
}
insert(key.substring(1), node.child[index], val);
}

public int sum(String prefix) {
return sum(prefix, root);
}

private int sum(String prefix, Node node) {
if (node == null) return 0;
if (prefix.length() != 0) {
int index = indexForChar(prefix.charAt(0));
return sum(prefix.substring(1), node.child[index]);
}
int sum = node.value;
for (Node child : node.child) {
sum += sum(prefix, child);
}
return sum;
}

private int indexForChar(char c) {
return c - 'a';
}
}

## 栈和队列

232. Implement Queue using Stacks (Easy)

class MyQueue {

private Stack<Integer> in = new Stack<>();
private Stack<Integer> out = new Stack<>();

public void push(int x) {
in.push(x);
}

public int pop() {
in2out();
return out.pop();
}

public int peek() {
in2out();
return out.peek();
}

private void in2out() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}

public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}

225. Implement Stack using Queues (Easy)

class MyStack {

private Queue<Integer> queue;

public MyStack() {
}

public void push(int x) {
int cnt = queue.size();
while (cnt-- > 1) {
}
}

public int pop() {
return queue.remove();
}

public int top() {
return queue.peek();
}

public boolean empty() {
return queue.isEmpty();
}
}

155. Min Stack (Easy)

class MinStack {

private Stack<Integer> dataStack;
private Stack<Integer> minStack;
private int min;

public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
min = Integer.MAX_VALUE;
}

public void push(int x) {
min = Math.min(min, x);
}

public void pop() {
dataStack.pop();
minStack.pop();
min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
}

public int top() {
return dataStack.peek();
}

public int getMin() {
return minStack.peek();
}
}

20. Valid Parentheses (Easy)

"()[]{}"

Output : true
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char cStack = stack.pop();
boolean b1 = c == ')' && cStack != '(';
boolean b2 = c == ']' && cStack != '[';
boolean b3 = c == '}' && cStack != '{';
if (b1 || b2 || b3) {
return false;
}
}
}
return stack.isEmpty();
}

739. Daily Temperatures (Medium)

Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] dist = new int[n];
Stack<Integer> indexs = new Stack<>();
for (int curIndex = 0; curIndex < n; curIndex++) {
while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {
int preIndex = indexs.pop();
dist[preIndex] = curIndex - preIndex;
}
}
return dist;
}

503. Next Greater Element II (Medium)

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.


public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] next = new int[n];
Arrays.fill(next, -1);
Stack<Integer> pre = new Stack<>();
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!pre.isEmpty() && nums[pre.peek()] < num) {
next[pre.pop()] = num;
}
if (i < n){
pre.push(i);
}
}
return next;
}

## 哈希表

• Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。

• Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。在对一个内容进行压缩或者其它转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。例如在一个简化 url 的系统中 Leetcdoe : 535. Encode and Decode TinyURL (Medium)，利用 HashMap 就可以存储精简后的 url 到原始 url 的映射，使得不仅可以显示简化的 url，也可以根据简化的 url 得到原始 url 从而定位到正确的资源。

1. Two Sum (Easy)

public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> indexForNum = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (indexForNum.containsKey(target - nums[i])) {
return new int[]{indexForNum.get(target - nums[i]), i};
} else {
indexForNum.put(nums[i], i);
}
}
return null;
}

217. Contains Duplicate (Easy)

public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
}
return set.size() < nums.length;
}

594. Longest Harmonious Subsequence (Easy)

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

public int findLHS(int[] nums) {
Map<Integer, Integer> countForNum = new HashMap<>();
for (int num : nums) {
countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
}
int longest = 0;
for (int num : countForNum.keySet()) {
if (countForNum.containsKey(num + 1)) {
longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
}
}
return longest;
}

128. Longest Consecutive Sequence (Hard)

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

public int longestConsecutive(int[] nums) {
Map<Integer, Integer> countForNum = new HashMap<>();
for (int num : nums) {
countForNum.put(num, 1);
}
for (int num : nums) {
forward(countForNum, num);
}
return maxCount(countForNum);
}

private int forward(Map<Integer, Integer> countForNum, int num) {
if (!countForNum.containsKey(num)) {
return 0;
}
int cnt = countForNum.get(num);
if (cnt > 1) {
return cnt;
}
cnt = forward(countForNum, num + 1) + 1;
countForNum.put(num, cnt);
return cnt;
}

private int maxCount(Map<Integer, Integer> countForNum) {
int max = 0;
for (int num : countForNum.keySet()) {
max = Math.max(max, countForNum.get(num));
}
return max;
}

## 字符串

s1 = AABCD, s2 = CDAA
Return : true

s1 进行循环移位的结果是 s1s1 的子字符串，因此只要判断 s2 是否是 s1s1 的子字符串即可。

s = "abcd123" k = 3
Return "123abcd"

s = "I am a student"
Return "student a am I"

242. Valid Anagram (Easy)

s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

public boolean isAnagram(String s, String t) {
int[] cnts = new int[26];
for (char c : s.toCharArray()) {
cnts[c - 'a']++;
}
for (char c : t.toCharArray()) {
cnts[c - 'a']--;
}
for (int cnt : cnts) {
if (cnt != 0) {
return false;
}
}
return true;
}

409. Longest Palindrome (Easy)

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

public int longestPalindrome(String s) {
int[] cnts = new int[256];
for (char c : s.toCharArray()) {
cnts[c]++;
}
int palindrome = 0;
for (int cnt : cnts) {
palindrome += (cnt / 2) * 2;
}
if (palindrome < s.length()) {
palindrome++;   // 这个条件下 s 中一定有单个未使用的字符存在，可以把这个字符放到回文的最中间
}
return palindrome;
}

205. Isomorphic Strings (Easy)

Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

public boolean isIsomorphic(String s, String t) {
int[] preIndexOfS = new int[256];
int[] preIndexOfT = new int[256];
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i), tc = t.charAt(i);
if (preIndexOfS[sc] != preIndexOfT[tc]) {
return false;
}
preIndexOfS[sc] = i + 1;
preIndexOfT[tc] = i + 1;
}
return true;
}

647. Palindromic Substrings (Medium)

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

private int cnt = 0;

public int countSubstrings(String s) {
for (int i = 0; i < s.length(); i++) {
extendSubstrings(s, i, i);     // 奇数长度
extendSubstrings(s, i, i + 1); // 偶数长度
}
return cnt;
}

private void extendSubstrings(String s, int start, int end) {
while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
start--;
end++;
cnt++;
}
}

9. Palindrome Number (Easy)

public boolean isPalindrome(int x) {
if (x == 0) {
return true;
}
if (x < 0 || x % 10 == 0) {
return false;
}
int right = 0;
while (x > right) {
right = right * 10 + x % 10;
x /= 10;
}
return x == right || x == right / 10;
}

696. Count Binary Substrings (Easy)

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
public int countBinarySubstrings(String s) {
int preLen = 0, curLen = 1, count = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
curLen++;
} else {
preLen = curLen;
curLen = 1;
}

if (preLen >= curLen) {
count++;
}
}
return count;
}

## 数组与矩阵

283. Move Zeroes (Easy)

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
public void moveZeroes(int[] nums) {
int idx = 0;
for (int num : nums) {
if (num != 0) {
nums[idx++] = num;
}
}
while (idx < nums.length) {
nums[idx++] = 0;
}
}

566. Reshape the Matrix (Easy)

Input:
nums =
[[1,2],
[3,4]]
r = 1, c = 4

Output:
[[1,2,3,4]]

Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
public int[][] matrixReshape(int[][] nums, int r, int c) {
int m = nums.length, n = nums[0].length;
if (m * n != r * c) {
return nums;
}
int[][] reshapedNums = new int[r][c];
int index = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
reshapedNums[i][j] = nums[index / n][index % n];
index++;
}
}
return reshapedNums;
}

485. Max Consecutive Ones (Easy)

public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, cur = 0;
for (int x : nums) {
cur = x == 0 ? 0 : cur + 1;
max = Math.max(max, cur);
}
return max;
}

240. Search a 2D Matrix II (Medium)

[
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
]
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (target == matrix[row][col]) return true;
else if (target < matrix[row][col]) col--;
else row++;
}
return false;
}

378. Kth Smallest Element in a Sorted Matrix ((Medium))

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

return 13.

public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int lo = matrix[0][0], hi = matrix[m - 1][n - 1];
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
cnt++;
}
}
if (cnt < k) lo = mid + 1;
else hi = mid - 1;
}
return lo;
}

public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
for(int j = 0; j < n; j++) pq.offer(new Tuple(0, j, matrix[0][j]));
for(int i = 0; i < k - 1; i++) { // 小根堆，去掉 k - 1 个堆顶元素，此时堆顶元素就是第 k 的数
Tuple t = pq.poll();
if(t.x == m - 1) continue;
pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
}
return pq.poll().val;
}

class Tuple implements Comparable<Tuple> {
int x, y, val;
public Tuple(int x, int y, int val) {
this.x = x; this.y = y; this.val = val;
}

@Override
public int compareTo(Tuple that) {
return this.val - that.val;
}
}

645. Set Mismatch (Easy)

Input: nums = [1,2,2,4]
Output: [2,3]
Input: nums = [1,2,2,4]
Output: [2,3]

public int[] findErrorNums(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return new int[]{nums[i], i + 1};
}
}
return null;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}

287. Find the Duplicate Number (Medium)

public int findDuplicate(int[] nums) {
int l = 1, h = nums.length - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) cnt++;
}
if (cnt > mid) h = mid - 1;
else l = mid + 1;
}
return l;
}

public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}

667. Beautiful Arrangement II (Medium)

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

public int[] constructArray(int n, int k) {
int[] ret = new int[n];
ret[0] = 1;
for (int i = 1, interval = k; i <= k; i++, interval--) {
ret[i] = i % 2 == 1 ? ret[i - 1] + interval : ret[i - 1] - interval;
}
for (int i = k + 1; i < n; i++) {
ret[i] = i + 1;
}
return ret;
}

697. Degree of an Array (Easy)

Input: [1,2,2,3,1,4,2]
Output: 6

public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> numsCnt = new HashMap<>();
Map<Integer, Integer> numsLastIndex = new HashMap<>();
Map<Integer, Integer> numsFirstIndex = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);
numsLastIndex.put(num, i);
if (!numsFirstIndex.containsKey(num)) {
numsFirstIndex.put(num, i);
}
}
int maxCnt = 0;
for (int num : nums) {
maxCnt = Math.max(maxCnt, numsCnt.get(num));
}
int ret = nums.length;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int cnt = numsCnt.get(num);
if (cnt != maxCnt) continue;
ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
}
return ret;
}

766. Toeplitz Matrix (Easy)

1234
5123
9512

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
public boolean isToeplitzMatrix(int[][] matrix) {
for (int i = 0; i < matrix[0].length; i++) {
if (!check(matrix, matrix[0][i], 0, i)) {
return false;
}
}
for (int i = 0; i < matrix.length; i++) {
if (!check(matrix, matrix[i][0], i, 0)) {
return false;
}
}
return true;
}

private boolean check(int[][] matrix, int expectValue, int row, int col) {
if (row >= matrix.length || col >= matrix[0].length) {
return true;
}
if (matrix[row][col] != expectValue) {
return false;
}
return check(matrix, expectValue, row + 1, col + 1);
}

565. Array Nesting (Medium)

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

public int arrayNesting(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
int cnt = 0;
for (int j = i; nums[j] != -1; ) {
cnt++;
int t = nums[j];
nums[j] = -1; // 标记该位置已经被访问
j = t;

}
max = Math.max(max, cnt);
}
return max;
}

769. Max Chunks To Make Sorted (Medium)

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

public int maxChunksToSorted(int[] arr) {
if (arr == null) return 0;
int ret = 0;
int right = arr[0];
for (int i = 0; i < arr.length; i++) {
right = Math.max(right, arr[i]);
if (right == i) ret++;
}
return ret;
}

## 图

### 二分图

785. Is Graph Bipartite? (Medium)

Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
public boolean isBipartite(int[][] graph) {
int[] colors = new int[graph.length];
Arrays.fill(colors, -1);
for (int i = 0; i < graph.length; i++) {  // 处理图不是连通的情况
if (colors[i] == -1 && !isBipartite(i, 0, colors, graph)) {
return false;
}
}
return true;
}

private boolean isBipartite(int curNode, int curColor, int[] colors, int[][] graph) {
if (colors[curNode] != -1) {
return colors[curNode] == curColor;
}
colors[curNode] = curColor;
for (int nextNode : graph[curNode]) {
if (!isBipartite(nextNode, 1 - curColor, colors, graph)) {
return false;
}
}
return true;
}

### 拓扑排序

207. Course Schedule (Medium)

2, [[1,0]]
return true
2, [[1,0],[0,1]]
return false

public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graphic = new List[numCourses];
for (int i = 0; i < numCourses; i++) {
graphic[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
}
boolean[] globalMarked = new boolean[numCourses];
boolean[] localMarked = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (hasCycle(globalMarked, localMarked, graphic, i)) {
return false;
}
}
return true;
}

private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked,
List<Integer>[] graphic, int curNode) {

if (localMarked[curNode]) {
return true;
}
if (globalMarked[curNode]) {
return false;
}
globalMarked[curNode] = true;
localMarked[curNode] = true;
for (int nextNode : graphic[curNode]) {
if (hasCycle(globalMarked, localMarked, graphic, nextNode)) {
return true;
}
}
localMarked[curNode] = false;
return false;
}

210. Course Schedule II (Medium)

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 int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] graphic = new List[numCourses];
for (int i = 0; i < numCourses; i++) {
graphic[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
}
Stack<Integer> postOrder = new Stack<>();
boolean[] globalMarked = new boolean[numCourses];
boolean[] localMarked = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (hasCycle(globalMarked, localMarked, graphic, i, postOrder)) {
return new int[0];
}
}
int[] orders = new int[numCourses];
for (int i = numCourses - 1; i >= 0; i--) {
orders[i] = postOrder.pop();
}
return orders;
}

private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked, List<Integer>[] graphic,
int curNode, Stack<Integer> postOrder) {

if (localMarked[curNode]) {
return true;
}
if (globalMarked[curNode]) {
return false;
}
globalMarked[curNode] = true;
localMarked[curNode] = true;
for (int nextNode : graphic[curNode]) {
if (hasCycle(globalMarked, localMarked, graphic, nextNode, postOrder)) {
return true;
}
}
localMarked[curNode] = false;
postOrder.push(curNode);
return false;
}

### 并查集

684. Redundant Connection (Medium)

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/ \
2 - 3

public int[] findRedundantConnection(int[][] edges) {
int N = edges.length;
UF uf = new UF(N);
for (int[] e : edges) {
int u = e[0], v = e[1];
if (uf.connect(u, v)) {
return e;
}
uf.union(u, v);
}
return new int[]{-1, -1};
}

private class UF {

private int[] id;

UF(int N) {
id = new int[N + 1];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}

void union(int u, int v) {
int uID = find(u);
int vID = find(v);
if (uID == vID) {
return;
}
for (int i = 0; i < id.length; i++) {
if (id[i] == uID) {
id[i] = vID;
}
}
}

int find(int p) {
return id[p];
}

boolean connect(int u, int v) {
return find(u) == find(v);
}
}

## 位运算

1. 基本原理

0s 表示一串 0，1s 表示一串 1。

x ^ 0s = x      x & 0s = 0      x | 0s = x
x ^ 1s = ~x     x & 1s = x      x | 1s = 1s
x ^ x = 0       x & x = x       x | x = x

• 利用 x ^ 1s = ~x 的特点，可以将位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
• 利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
• 利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。

• n&(n-1) 去除 n 的位级表示中最低的那一位。例如对于二进制表示 10110 100 ，减去 1 得到 10110011，这两个数相与得到 10110000
• n&(-n) 得到 n 的位级表示中最低的那一位。-n 得到 n 的反码加 1，对于二进制表示 10110 100 ，-n 得到 01001100，相与得到 00000100
• n-n&(~n+1) 去除 n 的位级表示中最高的那一位。

• >> n 为算术右移，相当于除以 2n
• >>> n 为无符号右移，左边会补上 0。
• << n 为算术左移，相当于乘以 2n

3. Java 中的位操作

static int Integer.bitCount();           // 统计 1 的数量
static int Integer.highestOneBit();      // 获得最高位
static String toBinaryString(int i);     // 转换为二进制表示的字符串

461. Hamming Distance (Easy)

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
↑   ↑

The above arrows point to positions where the corresponding bits are different.

public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while(z != 0) {
if ((z & 1) == 1) cnt++;
z = z >> 1;
}
return cnt;
}

public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while (z != 0) {
z &= (z - 1);
cnt++;
}
return cnt;
}

public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}

136. Single Number (Easy)

Input: [4,1,2,1,2]
Output: 4

public int singleNumber(int[] nums) {
int ret = 0;
for (int n : nums) ret = ret ^ n;
return ret;
}

268. Missing Number (Easy)

Input: [3,0,1]
Output: 2

public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret = ret ^ i ^ nums[i];
}
return ret ^ nums.length;
}

260. Single Number III (Medium)

diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。

public int[] singleNumber(int[] nums) {
int diff = 0;
for (int num : nums) diff ^= num;
diff &= -diff;  // 得到最右一位
int[] ret = new int[2];
for (int num : nums) {
if ((num & diff) == 0) ret[0] ^= num;
else ret[1] ^= num;
}
return ret;
}

190. Reverse Bits (Easy)

public int reverseBits(int n) {
int ret = 0;
for (int i = 0; i < 32; i++) {
ret <<= 1;
ret |= (n & 1);
n >>>= 1;
}
return ret;
}

private static Map<Byte, Integer> cache = new HashMap<>();

public int reverseBits(int n) {
int ret = 0;
for (int i = 0; i < 4; i++) {
ret <<= 8;
ret |= reverseByte((byte) (n & 0b11111111));
n >>= 8;
}
return ret;
}

private int reverseByte(byte b) {
if (cache.containsKey(b)) return cache.get(b);
int ret = 0;
byte t = b;
for (int i = 0; i < 8; i++) {
ret <<= 1;
ret |= t & 1;
t >>= 1;
}
cache.put(b, ret);
return ret;
}

a = a ^ b;
b = a ^ b;
a = a ^ b;

231. Power of Two (Easy)

public boolean isPowerOfTwo(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}

public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}

342. Power of Four (Easy)

public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) == 0 && (num & 0b01010101010101010101010101010101) != 0;
}

public boolean isPowerOfFour(int num) {
return Integer.toString(num, 4).matches("10*");
}

693. Binary Number with Alternating Bits (Easy)

Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.

Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.

public boolean hasAlternatingBits(int n) {
int a = (n ^ (n >> 1));
return (a & (a + 1)) == 0;
}

476. Number Complement (Easy)

Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

public int findComplement(int num) {
if (num == 0) return 1;
int mask = 1 << 30;
}

public int findComplement(int num) {
if (num == 0) return 1;
}

mask |= mask >> 1    11000000
mask |= mask >> 4    11111111
public int findComplement(int num) {
}

371. Sum of Two Integers (Easy)

a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。

public int getSum(int a, int b) {
return b == 0 ? a : getSum((a ^ b), (a & b) << 1);
}

318. Maximum Product of Word Lengths (Medium)

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

public int maxProduct(String[] words) {
int n = words.length;
int[] val = new int[n];
for (int i = 0; i < n; i++) {
for (char c : words[i].toCharArray()) {
val[i] |= 1 << (c - 'a');
}
}
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((val[i] & val[j]) == 0) {
ret = Math.max(ret, words[i].length() * words[j].length());
}
}
}
return ret;
}

338. Counting Bits (Medium)

public int[] countBits(int num) {
int[] ret = new int[num + 1];
for(int i = 1; i <= num; i++){
ret[i] = ret[i&(i-1)] + 1;
}
return ret;
}

# 参考资料

• Leetcode
• Weiss M A, 冯舜玺. 数据结构与算法分析——C 语言描述[J]. 2004.
• Sedgewick R. Algorithms[M]. Pearson Education India, 1988.
• 何海涛, 软件工程师. 剑指 Offer: 名企面试官精讲典型编程题[M]. 电子工业出版社, 2014.
• 《编程之美》小组. 编程之美[M]. 电子工业出版社, 2008.
• 左程云. 程序员代码面试指南[M]. 电子工业出版社, 2015.