LeetCode Problems 501-600.
501. Find Mode in Binary Search Tree
https://leetcode.com/problems/find-mode-in-binary-search-tree/
使用一个数组存储全部的mode，然后使用中序遍历，统计当前遍历的数出现的次数，并判断是否需要更新到mode数组中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int currVal;
private int currCount = 0;
private int maxCount = 0;
private int modeCount = 0;
private int[] modes;
public int[] findMode(TreeNode root) {
inorder(root);
modes = new int[modeCount];
modeCount = 0;
currCount = 0;
inorder(root);
return modes;
}
private void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
// update current number's count
if (root.val != currVal) {
currVal = root.val;
currCount = 0;
}
currCount++;
if (currCount > maxCount) {
// if current number is new mode, update
maxCount = currCount;
modeCount = 1;
} else if (currCount == maxCount) {
// current number one of the modes
if (modes != null) {
modes[modeCount] = currVal;
}
modeCount++;
}
inorder(root.right);
}
}
502. IPO
https://leetcode.com/problems/ipo/
如果Capital中每个数都小于w，说明本金足够多，可以任选k个项目，直接选利润最高的k个即可；否则，需要从成本低的项目选起，找出既满足成本，又是当前最高利润的项目。每做完一个项目，利润 + 原始的本金就变成了新的本金，可以做更多的项目，于是再次去尝试找到成本符合要求的项目，并且利润尽量高…
因为最多可以做k个项目，我们的代码至多为k次循环，每次循环内都重复以上流程；而如果剩下的项目全部高于已有本金，循环就提前终止。
class Solution {
public int findMaximizedCapital(int k, int w, int[] Profits, int[] Capital) {
// true if all capitals <= initial capital
boolean speedUp = true;
for (int c: Capital) {
if (w < c) {
speedUp = false;
}
}
// add k largest profits
if (speedUp) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int p: Profits) {
heap.add(p);
if (heap.size() > k) {
heap.poll();
}
}
for (int h: heap) {
w += h;
}
return w;
}
int n = Profits.length;
PriorityQueue<Integer> minCapitalHeap = new PriorityQueue<>((a, b) -> Capital[a] - Capital[b]);
PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>((a, b) -> Profits[b] - Profits[a]);
// sort all projects by capital in ascending order
for (int i = 0; i < n; i++) {
minCapitalHeap.offer(i);
}
// we can finish at most k projects
for (int i = 0; i < k; i++) {
// find projects that can be selected with the available capital
while (!minCapitalHeap.isEmpty() && Capital[minCapitalHeap.peek()] <= w) {
maxProfitHeap.add(minCapitalHeap.poll());
}
// terminate if we are not able to find any available capital
if (maxProfitHeap.isEmpty()) {
break;
}
// add first project's profit
w += Profits[maxProfitHeap.poll()];
}
return w;
}
}
503. Next Greater Element II
https://leetcode.com/problems/next-greater-element-ii/
两次循环，并用一个栈存储遍历时涉及的元素下标。
第一次循环，遍历一个数时检查栈，如果栈不空并且栈顶下标对应的数比遍历数小，说明当前的遍历数就是栈顶对应数的next greater element。之后，把当前遍历数下标存入栈中。
第二次循环，再次从头开始遍历数组，然而第一次循环后的栈并未被清空，相当于新遍历的下标在与此前循环的遍历结果进行比较，以这种方式模拟循环数组。具体比较策略与第一次循环相同。
class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] result = new int[nums.length];
Stack<Integer> stack = new Stack<>();
// first loop, get the index of next greater element in normal array
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
int index = stack.pop();
result[index] = nums[i];
}
stack.push(i);
}
// second loop, get the index of next greater element in circular array
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
int index = stack.pop();
result[index] = nums[i];
}
}
// cannot find greater element
while (!stack.isEmpty()) {
result[stack.pop()] = -1;
}
return result;
}
}
504. Base 7
https://leetcode.com/problems/base-7/
不断提取每一位的模，最后再头尾颠倒生成字符串。注意对于0，直接返回。
class Solution {
public String convertToBase7(int num) {
if (num == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
int n = Math.abs(num);
while (n != 0) {
sb.append(n % 7);
n /= 7;
}
if (num < 0) {
sb.append("-");
}
return sb.reverse().toString();
}
}
505. The Maze II
https://leetcode.com/problems/the-maze-ii/
使用一个二维数组distance存储起点到每个点的最短距离（初始距离都是-1，即假设为不可达）。之后使用BFS，遍历每个方向并且在每个方向一直走直到撞上障碍，如果走到一个未访问过的方格中，或者当前的路径比之前的路径更短，就把当前方格加入到队列中，并更新当前方格最短距离。
class Solution {
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
// directions to top, bottom, left and right
int[][] dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
// store shotest distance
int[][] distance = new int[maze.length][maze[0].length];
// Set all cell as -1 initially
for (int[] d : distance) {
Arrays.fill(d, -1);
}
distance[start[0]][start[1]] = 0; // start distance
Queue<int[]> q = new ArrayDeque<>();
q.add(start);
while (!q.isEmpty()) {
int[] c = q.poll();
for (int[] dir : dirs) {
int count = distance[c[0]][c[1]];
int x = c[0];
int y = c[1];
while (x + dir[0] >= 0 && x + dir[0] < maze.length && y + dir[1] >= 0 && y + dir[1] < maze[0].length && maze[x + dir[0]][y + dir[1]] != 1) {
x += dir[0];
y += dir[1];
count++;
}
// unvisited cell, or a shorter path, add it to queue and update distance
if (distance[x][y] == -1 || distance[x][y] > count) {
q.add(new int[]{x, y});
distance[x][y] = count;
}
}
}
return distance[destination[0]][destination[1]];
}
}
506. Relative Ranks
https://leetcode.com/problems/relative-ranks/
找出数组的最大值和最小值，以此安排桶容纳所有元素并进行排序，每个元素因为是唯一的，所以排序上每个元素也不存在并列的情况。完成桶排序之后，从大桶开始向下遍历，分配排名座次。
class Solution {
public String[] findRelativeRanks(int[] score) {
if (score == null || score.length == 0) {
return null;
}
int n = score.length;
String[] result = new String[n];
// find min and max values to set buckets
int max = 0, min = Integer.MAX_VALUE;
for (int num : score) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// each value is mapped to a unique index
int[] valToIndex = new int[max - min + 1];
Arrays.fill(valToIndex, -1);
for (int i = 0; i < n; i++) {
valToIndex[score[i] - min] = i;
}
// start from highest scores to assign rank
int rank = 1;
for (int val = max - min; val >= 0; val--) {
if (valToIndex[val] == -1) {
continue;
}
if (rank == 1) {
result[valToIndex[val]] = "Gold Medal";
} else if (rank == 2) {
result[valToIndex[val]] = "Silver Medal";
} else if (rank == 3) {
result[valToIndex[val]] = "Bronze Medal";
} else {
result[valToIndex[val]] = String.valueOf(rank);
}
rank++;
}
return result;
}
}
507. Perfect Number
https://leetcode.com/problems/perfect-number/
从2到sqrt(num)，穷举累加所有质因数组合，看总和 + 1是否与num一致。需要注意排除1和所有非正数。
class Solution {
public boolean checkPerfectNumber(int num) {
if (num <= 1) {
return false;
}
int sumOfDivisors = 0;
for (int i = 2; i <= (int)Math.sqrt(num); i++) {
if (num % i == 0) {
sumOfDivisors += (i + num / i);
}
}
return sumOfDivisors + 1 == num;
}
}
508. Most Frequent Subtree Sum
https://leetcode.com/problems/most-frequent-subtree-sum/
DFS遍历，每个子树的和是左子树的和 + 右子树的和 + 根节点的值。使用一个map统计当前每个子树和的值以及对应的出现次数，每计算出一个子树和就更新一次map。同时维护一个储存最高频子树和的list，如果当前的值是出现频率最高的，就一并更新list。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> list;
private int maxFreq = 0;
// <sum, freq>
private Map<Integer, Integer> map;
public int[] findFrequentTreeSum(TreeNode root) {
if (root == null) {
return new int[]{};
}
map = new HashMap<>();
list = new ArrayList<>();
DFS(root);
int[] result = new int[list.size()];
int i = 0;
for (int ele: list) {
result[i] = ele;
i++;
}
return result;
}
private int DFS(TreeNode cur) {
// current subtree's sum
if (cur == null) {
return 0;
}
int leftSum = DFS(cur.left);
int rightSum = DFS(cur.right);
int sum = leftSum + rightSum + cur.val;
int curFreq = map.getOrDefault(sum, 0) + 1;
map.put(sum, curFreq);
// empty list and add the new largest sum
if (curFreq > maxFreq) {
maxFreq = curFreq;
list.clear();
list.add(sum);
} else if (curFreq == maxFreq) {
list.add(sum);
}
return sum;
}
}
509. Fibonacci Number
https://leetcode.com/problems/fibonacci-number/
循环累加即可。
class Solution {
public int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// current index of Fibonacci sequence
int current = 2;
// current Fibonacci number
int num = 0;
// preceding two numbers
int preceding2 = 0;
int preceding1 = 1;
while (current <= n) {
num = preceding2 + preceding1;
// update preceding numbers
preceding2 = preceding1;
preceding1 = num;
current++;
}
return num;
}
}
510. Inorder Successor in BST II
https://leetcode.com/problems/inorder-successor-in-bst-ii/
如果x没有右儿子，就向上寻找到比x大的最小祖先；反之，向下寻找到右子树中的最小节点。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/
class Solution {
public Node inorderSuccessor(Node x) {
// no right child, find the smallest ancestor which is larger than x
if (x.right == null) {
Node cur = x;
// search upwards in the right subtree
while (cur.parent != null && cur.parent.right == cur) {
cur = cur.parent;
}
return cur.parent;
}
// have right child, find the leftmost element in the right subtree
Node cur = x.right;
while (cur.left != null) {
cur = cur.left;
}
return cur;
}
}
511. Game Play Analysis I
https://leetcode.com/problems/game-play-analysis-i/
做一次group by即可。
SELECT player_id, MIN(event_date) AS first_login
FROM Activity
GROUP BY player_id;
512. Game Play Analysis II
https://leetcode.com/problems/game-play-analysis-ii/
先找到首次登陆的记录行，再从中提取出player_id与device_id。
SELECT player_id, device_id
FROM activity
WHERE (player_id, event_date) IN (
SELECT player_id, MIN(event_date)
FROM activity
GROUP BY player_id
)
513. Find Bottom Left Tree Value
https://leetcode.com/problems/find-bottom-left-tree-value/
使用中序遍历，保证先访问当前节点的左子树，每访问一个节点，节点深度就增加1，如果当前节点深度最大就更新结果。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int result = 0;
private int maxLevel = -1;
public int findBottomLeftValue(TreeNode root) {
findLevel(root, 0);
return result;
}
// in-order will always visit the leftmost value first
public void findLevel(TreeNode root, int level) {
if (root == null) {
return;
}
findLevel(root.left, level + 1);
// update current max level
if (level > maxLevel) {
maxLevel = level;
result = root.val;
}
findLevel(root.right, level + 1);
}
}
514. Freedom Trail
https://leetcode.com/problems/freedom-trail/
使用DFS + dp。先遍历ring，把每个字符和对应的下标储存起来。之后使用二维dp，dp[rIdx][kIdx]表示从ring[rIdx]下标开始转，完成key[kIdx]以及之后的字符需要多少步。每一次转动时，都要比较是顺时针转还是逆时针转所需步骤更少，完成当前步之后再用DFS累计后续步骤，得到dp值。注意最后总步骤+1，因为还要按下中央按钮。
class Solution {
public int findRotateSteps(String ring, String key) {
// <character, character's index in ring>
List<Integer>[] map = new List[26];
for (int i = 0; i < ring.length(); i++) {
char c = ring.charAt(i);
if (map[c - 'a'] == null) {
map[c - 'a'] = new ArrayList();
}
map[c - 'a'].add(i);
}
int[][] dp = new int[ring.length() + 1][key.length() + 1];
return helper(ring, key, 0, 0, map, dp);
}
private int helper(String ring, String key, int rIdx, int kIdx, List<Integer>[] map, int[][] dp) {
// already end of the key, no more characters to press
if (key.length() == kIdx) {
return 0;
}
// already calculated
if (dp[rIdx][kIdx] > 0) {
return dp[rIdx][kIdx];
}
int min = Integer.MAX_VALUE;
for (int i : map[key.charAt(kIdx) - 'a']) {
// clockwise vs anticlockwise offset
int offset = Math.min(Math.abs(rIdx - i), ring.length() - Math.abs(rIdx - i));
// current offset + all subsequent offsets
min = Math.min(min, offset + helper(ring, key, i, kIdx + 1, map, dp));
}
// +1 for pressing the button
dp[rIdx][kIdx] = min + 1;
return dp[rIdx][kIdx];
}
}
515. Find Largest Value in Each Tree Row
https://leetcode.com/problems/find-largest-value-in-each-tree-row/
前序遍历，如果访问到新的一层，就把当前的节点加到list中，临时充当本层的最大值；否则，如果是已经访问过的层数，就判断是否需要更新这一层的最大值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
largestValues(root, result, 0);
return result;
}
public void largestValues(TreeNode root, List<Integer> result, int height) {
if (root == null) {
return;
}
if (height == result.size()) {
// add value in the new height
result.add(root.val);
} else {
// set max of current height
result.set(height, Math.max(result.get(height), root.val));
}
largestValues(root.left, result, height + 1);
largestValues(root.right, result, height + 1);
}
}
516. Longest Palindromic Subsequence
https://leetcode.com/problems/longest-palindromic-subsequence/
先用二维dp，其中dp[i][j]表示s[i, j]中的最长回文串的长度。显然，如果s[i] = s[j]，长度就是dp[i+1][j-1]的基础上 + 2，否则就是dp[i+1][j]与dp[i][j-1]二者取较大值。
得到二维递推后，可以进一步压缩dp维度，把dp[m][n]压缩成dp[n]，为此可以加入一个变量pre用于辅助保存当前回文串的起始位置。
class Solution {
public int longestPalindromeSubseq(String s) {
int[] dp = new int[s.length()];
// dp[i][j]: the longest palindromic subsequence's length of substring(i, j)
// dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
// otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
// we can then reduce dp[m][n] to dp[n]
for (int i = s.length() - 1; i >= 0; i--) {
dp[i] = 1;
int pre = 0;
for (int j = i + 1; j < s.length(); j++) {
int tmp = dp[j];
if (s.charAt(i) == s.charAt(j)) {
dp[j] = pre + 2;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
pre = tmp;
}
}
return dp[s.length() - 1];
}
}
517. Super Washing Machines
https://leetcode.com/problems/super-washing-machines/
首先通过整除性排除无法均摊衣服的情况。之后通过total / n得到每个洗衣机内的目标衣服数量。因为衣服的均摊需要相邻的洗衣机不断接力传递，因此设定一个toRight变量用于存储不断接力累加后，当前洗衣机需要向右边相邻洗衣机传递的衣服数量（如果为负数，表示从右侧相邻洗衣机接受的衣服数量）。
很显然，为了平衡衣服数量，即便toRight是0，也需要至少m - target移动；而如果通过toRight累积的数量很大，则需要更多次移动。因此，对每台洗衣机，移动的次数就是这两个变量的最大值。
class Solution {
public int findMinMoves(int[] machines) {
int total = 0, n = machines.length;
for (int m : machines) {
total += m;
}
// skip impossible cases
if (total % n > 0) {
return -1;
}
int target = total / n, result = 0, toRight = 0;
for (int m : machines) {
// the clothes that we need to pass to the right number
toRight = m + toRight - target;
result = Math.max(result, Math.max(Math.abs(toRight), m - target));
}
return result;
}
}
518. Coin Change 2
https://leetcode.com/problems/coin-change-2/
01背包问题，简而言之就是讨论两种情况，要么用当前的硬币，要么不用。
class Solution {
// dp[i][j] : the number of combinations to make up amount j by using the first i types of coins
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length+1][amount+1];
dp[0][0] = 1;
for (int i = 1; i <= coins.length; i++) {
dp[i][0] = 1;
// dp[i - 1][j]: the number of combinations if we don't use the i-th coin
// dp[i][j-coins[i-1]]：the number of combinations if we must use at least one of the i-th coin
for (int j = 1; j <= amount; j++) {
dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j - coins[i-1]] : 0);
}
}
return dp[coins.length][amount];
}
// public int change(int amount, int[] coins) {
// int[] dp = new int[amount + 1];
// dp[0] = 1;
// for (int coin : coins) {
// for (int i = coin; i <= amount; i++) {
// dp[i] += dp[i-coin];
// }
// }
// return dp[amount];
// }
}
519. Random Flip Matrix
https://leetcode.com/problems/random-flip-matrix/
把二维数组看成一个长度为m * n的序列，问题转化为每一轮保持均匀地从序列中随机抽取一个数，直到抽完为止。
根据Fisher–Yates shuffle算法中的modern method，每抽一个数，都会使得剩余序列的长度变短，这时候我们需要将剩余序列中最后一个未被选择的数替换到当前被抽取的数的位置上。
class Solution {
private Map<Integer, Integer> map = new HashMap<>();
private int row, col, total;
private Random rand = new Random();
public Solution(int m, int n) {
row = m;
col = n;
total = row * col;
}
public int[] flip() {
// generate index, decrease total number of values
int r = rand.nextInt(total);
total--;
// check if we have already put something at this index
int x = map.getOrDefault(r, r);
// swap, put total at index that we generated
map.put(r, map.getOrDefault(total, total));
return new int[]{x / col, x % col};
}
public void reset() {
map.clear();
total = row * col;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(m, n);
* int[] param_1 = obj.flip();
* obj.reset();
*/
520. Detect Capital
https://leetcode.com/problems/detect-capital/
统计大写字母的个数，这个个数只能是0，1或者和word一样长。如果是1，这个大写字母必须是首字母。
class Solution {
public boolean detectCapitalUse(String word) {
int count = 0;
char[] wordArray = word.toCharArray();
for (int i = 0; i < wordArray.length; i++) {
if (wordArray[i] >= 'A' && wordArray[i] <= 'Z') {
count++;
}
}
return count == 0 ||
count == wordArray.length ||
(count == 1 && wordArray[0] >= 'A' && wordArray[0] <= 'Z');
}
}
521. Longest Uncommon Subsequence I
https://leetcode.com/problems/longest-uncommon-subsequence-i/
如果两个字符串一模一样，就不存在LUS；否则，LUS就直接返回两个字符串中较长的那个，因为很显然较长的那个不可能是较短的那个的子字符串。
class Solution {
public int findLUSlength(String a, String b) {
return a.equals(b) ? -1 : Math.max(a.length(), b.length());
}
}
522. Longest Uncommon Subsequence II
https://leetcode.com/problems/longest-uncommon-subsequence-ii/
两层循环，判断当前字符串是否是其他任意字符串的子序列，如果不存在，当前字符串就是一个可能的LUS，根据它的长度决定是否更新已有的最大值。
class Solution {
public int findLUSlength(String[] strs) {
int result = -1, n = strs.length;
for (int i = 0; i < n; i++) {
if (strs[i].length() < result) {
continue;
}
int j = -1;
while (++j < n) {
if (i != j && isSubsequence(strs[i], strs[j])) {
break;
}
}
// current string is not subsequence of any other string
if (j == n) {
result = Math.max(result, strs[i].length());
}
}
return result;
}
public boolean isSubsequence(String a, String b) {
int i = 0, j = 0;
while (i < a.length() && j < b.length()) {
if (a.charAt(i) == b.charAt(j++)) {
i++;
}
}
return i == a.length();
}
}
523. Continuous Subarray Sum
https://leetcode.com/problems/continuous-subarray-sum/
使用一个变量curSum，循环遍历数组的同时，用curSum记录截止每一位时的累加数值，然后再用curMod保存curSum与k的模，并且用HashMap把这个数值和下标对应起来。当前的curMod如果和之前的重复了，说明中间这一段子数组的和一定是k的倍数。
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if (nums.length < 2) {
return false;
}
// <mod value, index>
Map<Integer, Integer> map = new HashMap<>();
// the first subarray with first two numbers in array could form the result
map.put(0, -1);
int curSum = 0;
int curMod = 0;
for (int i = 0; i < nums.length; i++) {
curSum += nums[i];
// corner case: k CANNOT be 0 when we use a number mod k
curMod = k != 0 ? curSum % k : curSum;
// the mode repeat again, so numbers between them should be a multiple of k
if (map.containsKey(curMod)) {
// subarray of size at least 2
if (i - map.get(curMod) > 1) {
return true;
}
} else {
map.put(curMod, i);
}
}
return false;
}
}
524. Longest Word in Dictionary through Deleting
https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/
遍历d中每个单词，首先要找到某个单词能够成为s的子序列，其次这个单词要越长越好。如果有多个相同长度的这种单词，用compareTo()方法找到字典序最小的即可。
class Solution {
public String findLongestWord(String s, List<String> d) {
String result = "";
for (String word: d) {
if ((word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0) && isSubsequence(word, s)) {
result = word;
}
}
return result;
}
public boolean isSubsequence(String a, String b) {
int i = 0, j = 0;
while (i < a.length() && j < b.length()) {
if (a.charAt(i) == b.charAt(j++)) {
i++;
}
}
return i == a.length();
}
}
525. Contiguous Array
https://leetcode.com/problems/contiguous-array/
用HashMap统计数组开头到每个下标的子数组和，如果发现当前的和重复，说明数组中出现了为和0的子数组序列，计算出下标差并更新最大值。
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> sumToIndex = new HashMap<>();
sumToIndex.put(0, -1);
int sum = 0, result = 0;
for (int i = 0; i < nums.length; i++) {
sum += (nums[i] * 2 - 1); // 0 -> -1, 1 -> 1
if (sumToIndex.containsKey(sum)) {
result = Math.max(result, i - sumToIndex.get(sum));
} else {
sumToIndex.put(sum, i);
}
}
return result;
}
}
526. Beautiful Arrangement
https://leetcode.com/problems/beautiful-arrangement/
回溯算法，从数组尾开始向前，循环遍历并跟起始数交换，看是否满足，如果满足就向前进一步移动起始数，直至数组头。
class Solution {
private int count = 0;
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void helper(int[] nums, int start) {
// reach array start, add total count
if (start == 0) {
count++;
return;
}
// backtrack, try each pair then restore
for (int i = start; i > 0; i--) {
swap(nums, start, i);
// arrange one num, move start forward
if (nums[start] % start == 0 || start % nums[start] == 0) {
helper(nums, start - 1);
}
swap(nums, i, start);
}
}
public int countArrangement(int n) {
int[] nums = new int[n + 1];
for (int i = 0; i <= n; i++) {
nums[i] = i;
}
// start from n
helper(nums, n);
return count;
}
}
527. Word Abbreviation
https://leetcode.com/problems/word-abbreviation/
初始情况下，先找出每个单词的最短缩写，即首字母 + 中间缩略长度 + 末字母。用这样的缩写作为key，建立HashMap，value是缩写相同的单词集合，并同时存储了单词本身与单词的下标。
对于缩写重复的单词，尝试找到最长公共前缀，这样就能确定缩写的前缀长度至少要达到多少才能使得前缀唯一。
此题的一大技巧是同时存储单词本身与下标，这样使得后续修改前缀时直接从map中读取单词位置，始终能在O(1)时间内完成修改，加快运行效率。
class Solution {
class IndexToWord {
int index;
String word;
public IndexToWord(int index, String word) {
this.index = index;
this.word = word;
}
}
public List<String> wordsAbbreviation(List<String> dict) {
Map<String, List<IndexToWord>> map = new HashMap<>();
List<String> result = new ArrayList<>();
for (int i = 0; i < dict.size(); i++) {
// use prefix length = 1 to generate initial abbr
String abbr = getAbbr(dict.get(i), 1);
// same abbr cannot be repeatedly added as a key
map.putIfAbsent(abbr, new ArrayList<>());
// words with same abbr are stored in the same list
map.get(abbr).add(new IndexToWord(i, dict.get(i)));
result.add(abbr);
}
for (List<IndexToWord> group: map.values()) {
// unique abbr -> word mapping
if (group.size() == 1) {
continue;
}
// for words with same abbr, sort in alphabetical order
Collections.sort(group, (a, b) -> a.word.compareTo(b.word));
// find new prefix length to become unique
int[] lcp = new int[group.size()];
for (int i = 1; i < group.size(); i++) {
int p = longestCommonPrefix(group.get(i - 1).word, group.get(i).word);
lcp[i] = p;
lcp[i-1] = Math.max(lcp[i-1], p);
}
// set abbr to result
for (int i = 0; i < group.size(); i++) {
result.set(group.get(i).index, getAbbr(group.get(i).word, lcp[i]));
}
}
return result;
}
private int longestCommonPrefix(String word1, String word2) {
int i = 0;
while (i < word1.length() && i < word2.length() && word1.charAt(i) == word2.charAt(i)) {
i++;
}
return i + 1;
}
private String getAbbr(String word, int i) {
if (word.length() <= 3 || i+2 >= word.length()) {
return word;
}
StringBuilder sb = new StringBuilder();
sb.append(word.substring(0, i)); // first i characters to make prefix unique
sb.append(word.length() - i - 1); // abbr length
sb.append(word.substring(word.length() - 1)); // last char
return sb.toString();
}
}
528. Random Pick with Weight
https://leetcode.com/problems/random-pick-with-weight/
用一个长度为100的数组表示总共100%的权重和。计算每一个数的权重百分比，如果一个数权重为w，就给它在数组中分配w的长度（用它的下标给这一段区间赋值），以此类推。
由于每个数的weight都转化成了整数，因此对于非整数的weight有一定的精度损失，这导致实际上最终的weight的之和并不一定是100。为此，我们需要用一个size变量，累计所有的整数weight和，这个才是最终随机pick时的范围。
class Solution {
// total weight is always 100%
private int[] map = new int[100];
// total int weight length
private int size = 0;
public Solution(int[] w) {
// sum of all nums
int total = 0;
for (int num : w) {
total += num;
}
for (int i = 0; i < w.length; i++) {
// calculate each number's weight, then allocate the space proportional to the weight
int weight = (int)(w[i] * 100.0 / total);
while (weight-- > 0) {
map[size] = i;
size++;
}
}
}
public int pickIndex() {
return map[(int)(Math.random() * size)];
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/
529. Minesweeper
https://leetcode.com/problems/minesweeper/
dfs递归检查邻近方格，检查时可以借助bfs思想遍历8个方向，直到遇到某个方格周围有雷，终止递归。
class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
if (board.length == 0 || board[0].length == 0 || click.length != 2) {
return board;
}
int x = click[0], y = click[1], m = board.length, n = board[0].length;
if (board[x][y] == 'M') {
// reveal the mine
board[x][y] = 'X';
} else {
// dfs check the board
int[][] dirs = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
};
dfs(board, x, y, m, n, dirs);
}
return board;
}
private void dfs(char[][] board, int x, int y, int m, int n, int[][] dirs) {
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'E') {
return;
}
int mine = adjMine(board, x, y, m, n);
if (mine > 0) {
// count total mine numbers
board[x][y] = (char) ('0' + mine);
} else {
// no adjacent mines, recursively reveal adjacent unrevealed squares
board[x][y] = 'B';
// try all directions
for (int[] d : dirs) {
dfs(board, x + d[0], y + d[1], m, n, dirs);
}
}
}
private int adjMine(char[][] board, int x, int y, int m, int n) {
int count = 0;
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'M') {
count++;
}
}
}
return count;
}
}
530. Minimum Absolute Difference in BST
https://leetcode.com/problems/minimum-absolute-difference-in-bst/
中序遍历，因为是BST，把所有节点想像成一条数轴上的数。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int result = Integer.MAX_VALUE;
private TreeNode prev;
public int getMinimumDifference(TreeNode root) {
inorder(root);
return result;
}
private void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.left);
if (prev != null) {
result = Math.min(result, Math.abs(node.val - prev.val));
}
prev = node;
inorder(node.right);
}
}
531. Lonely Pixel I
https://leetcode.com/problems/lonely-pixel-i/
先遍历一遍picture，遇到一个'B'就把当前行、列中的'B'数量增加1；之后再次遍历，如果某一行或列的'B'数量不是1，就可以直接跳过，节省时间。
class Solution {
public int findLonelyPixel(char[][] picture) {
int rows = picture.length;
int cols = picture[0].length;
int rowCount[] = new int[rows];
int colCount[] = new int[cols];
int result = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (picture[i][j] == 'B') {
// current row and col have 1 more black pixel
rowCount[i]++;
colCount[j]++;
}
}
}
for (int i = 0; i < rows; i++) {
// current row doesn't have only 1 black pixel
if (rowCount[i] != 1) {
continue;
}
for (int j = 0; j < cols; j++) {
// current col doesn't have only 1 black pixel
if (colCount[j] != 1) {
continue;
}
if (picture[i][j] == 'B') {
result++;
}
}
}
return result;
}
}
532. K-diff Pairs in an Array
https://leetcode.com/problems/k-diff-pairs-in-an-array/
首先统计每个数出现的频率。之后分类讨论：
k > 0，此时如果一个数num和num + k都在map中，说明这两个数能组成k-diff-pairk == 0，此时如果一个数num出现了不止一次，也算作两个数组成了k-diff-pair
class Solution {
public int findPairs(int[] nums, int k) {
// <number, number's frequency>
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int result = 0;
for (int num : map.keySet()) {
// assume k > 0 and num is the smaller one in the k-diff pair
// or k == 0 and there is more than one num in the map
if ((k > 0 && map.containsKey(num + k)) || (k == 0 && map.get(num) > 1)) {
result++;
}
}
return result;
}
}
533. Lonely Pixel II
https://leetcode.com/problems/lonely-pixel-ii/
与lonely-pixel-i类似，先遍历picture，遇到'B'就让每一行、列的'B'数量增加1。之后检查两条rule，先排除行列不为N个'B'的情况，再判断对应的行列是否存在相同的'B'。可以使用List完成这个目标。
class Solution {
public int findBlackPixel(char[][] picture, int N) {
int rowsLength = picture.length;
int colsLength = picture[0].length;
int result = 0;
int[] row = new int[rowsLength];
int[] column = new int[colsLength];
for (int i = 0; i < rowsLength; i++) {
for (int j = 0; j < colsLength; j++) {
if (picture[i][j] == 'B') {
// current row and col have 1 more black pixel
row[i]++;
column[j]++;
}
}
}
// Figure out the rows for each column
for (int j = 0; j < colsLength; j++) {
// current row doesn't have N black pixel
if (column[j] != N) {
continue;
}
// all columns with 'B' in this row
List<Integer> rows = new ArrayList<>();
for (int i = 0; i < rowsLength; i++) {
if (row[i] == N && picture[i][j] == 'B') {
rows.add(i);
}
}
// current col doesn't have N black pixel
if (rows.size() != N) {
continue;
}
boolean isEqual = true;
// check for all rows
for (int k = 1; k < rows.size(); k++) {
char[] prevRow = picture[rows.get(k)];
char[] currRow = picture[rows.get(k-1)];
// rows that have a black pixel at column C, should be exactly the same as row R
for (int r = 0; r < prevRow.length; r++) {
if (prevRow[r] != currRow[r]) {
isEqual = false;
break;
}
}
}
if (isEqual) {
result = result + N;
}
}
return result;
}
}
534. Game Play Analysis III
https://leetcode.com/problems/game-play-analysis-iii/
activity表自连接，指定一张表的event_date在另一张之后，这样能够选出从某个时间点开始的所有数据。
SELECT a1.player_id, a1.event_date, SUM(a2.games_played) AS games_played_so_far
FROM activity AS a1 INNER JOIN activity AS a2
ON a1.event_date >= a2.event_date AND a1.player_id = a2.player_id
GROUP BY a1.player_id, a1.event_date
535. Encode and Decode TinyURL
https://leetcode.com/problems/encode-and-decode-tinyurl/
用base64算法，生成longUrl对应的shortUrl，然后用HashMap存储每一组<shortUrl, longUrl>，方便编码和解码。
public class Codec {
private Map<String, String> map = new HashMap<>();
private int counter = 1000000000;
// Encodes a URL to a shortened URL.
public String encode(String longUrl) {
--counter;
String url = base64(counter);
map.put(url, longUrl);
return url;
}
// Decodes a shortened URL to its original URL.
public String decode(String shortUrl) {
return map.get(shortUrl);
}
static String digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";
public String base64(int val) {
StringBuffer sb = new StringBuffer();
while (val > 0) {
int digit = val % 64;
val = val / 64;
sb.append(digits.charAt(digit));
}
return sb.toString();
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));
536. Construct Binary Tree from String
https://leetcode.com/problems/construct-binary-tree-from-string/
使用一个下标idx维护遍历s的进度。每遇到一个整数时，提取其符号以及全部数字，之后用这个数构造一个树节点。
构造完当前节点后，如果后面遇到了括号，说明进入了更深的递归，即需要构造子树。此时，需要依照先左后右的顺序构造两边子树，注意移动idx跳过每个子树两个括号。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int idx = 0;
public TreeNode str2tree(String s) {
if (s == null || s.length() == 0) {
return null;
}
// decide whether current num is positive or negative
int negative = 1;
int current = 0;
if (s.charAt(idx) == '-') {
negative = -1;
idx++;
}
while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
current = current * 10 + s.charAt(idx) - '0';
idx++;
}
// construct current node
TreeNode root = new TreeNode(negative * current);
// left subtree
if (idx < s.length() && s.charAt(idx) == '(') {
idx++; // open parenthesis
root.left = str2tree(s);
idx++; // close parenthesis
}
// right subtree
if (idx < s.length() && s.charAt(idx) == '(') {
idx++; // open parenthesis
root.right = str2tree(s);
idx++; // close parenthesis
}
return root;
}
}
537. Complex Number Multiplication
https://leetcode.com/problems/complex-number-multiplication/
先根据+号split，然后把虚数部分的i去掉，算出新的实虚系数。之后再把整数重新转换为字符串。
class Solution {
public String complexNumberMultiply(String num1, String num2) {
String[] part1 = num1.split("\\+");
String[] part2 = num2.split("\\+");
// remove i in both parts
int x = Integer.parseInt(part1[0]);
int y = Integer.parseInt(part1[1].replace("i", ""));
int c = Integer.parseInt(part2[0]);
int d = Integer.parseInt(part2[1].replace("i", ""));
// convert integer to string again
String ansOne = Integer.toString(x * c - y * d);
String ansTwo = Integer.toString(x * d + y * c) + "i";
return ansOne + "+" + ansTwo;
}
}
538. Convert BST to Greater Tree
https://leetcode.com/problems/convert-bst-to-greater-tree/
类似中序遍历，先递归算右子树的总和，之后加上根节点的和，最后再去算左子树。每一步的起始sum都取决于上一步的结果。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode convertBST(TreeNode root) {
helper(root, 0);
return root;
}
private int helper(TreeNode node, int sum) {
// no node or child
if (node == null) {
return sum;
}
// sum of right subtree
int right = helper(node.right, sum);
// sum of right subtree + current node
node.val += right;
// sum of left、right subtrees and root node
return helper(node.left, node.val);
}
}
539. Minimum Time Difference
https://leetcode.com/problems/minimum-time-difference/
把时间转换成分钟，（以0为基准），然后把所有timePoints进行排序，找出相邻两个时间点的最小差值。注意需要额外考虑第一个时间点和最后一个。
class Solution {
private int convertTimeToMin(String time) {
String[] timeSplit = time.split(":");
int hour = Integer.parseInt(timeSplit[0]);
int minute = Integer.parseInt(timeSplit[1]);
return hour * 60 + minute;
}
public int findMinDifference(List<String> timePoints) {
int result = Integer.MAX_VALUE;
int[] convertedTime = new int[timePoints.size()];
for (int i = 0; i < timePoints.size(); i++) {
convertedTime[i] = convertTimeToMin(timePoints.get(i));
}
Arrays.sort(convertedTime);
for (int i = 0; i < convertedTime.length - 1; i++) {
result = Math.min(result, convertedTime[i+1] - convertedTime[i]);
}
result = Math.min(result, convertedTime[0] + 1440 - convertedTime[convertedTime.length - 1]);
return result;
}
}
540. Single Element in a Sorted Array
https://leetcode.com/problems/single-element-in-a-sorted-array/
正常来说，如果两个数两两配对，所有偶数下标和下一个奇数下标的数都应该是相等的。因此使用二分查找，总是先找到中点偏左的第一个偶数下标。如果这个数和下一个数不相同，说明左半侧的数中有个数落单了，导致正常的奇偶配对产生了下标偏移；反之说明在右半侧。
class Solution {
public int singleNonDuplicate(int[] nums) {
int start = 0, end = nums.length - 1;
while (start < end) {
// find the even index if the left part is sorted
int mid = start + (end - start) / 2;
if (mid % 2 == 1) {
mid--;
}
if (nums[mid] != nums[mid + 1]) {
// single is in left part
end = mid;
} else {
// single is in right part
start = mid + 2;
}
}
return nums[start];
}
}
541. Reverse String II
https://leetcode.com/problems/reverse-string-ii/
两层循环，外层遍历每2k个字符，内层颠倒每组2k个字符中的前k个字符，注意最后一组可能提前到达结尾。
class Solution {
public String reverseStr(String s, int k) {
char[] array = s.toCharArray();
// for every 2k characters
for (int left = 0; left < array.length; left += 2 * k) {
// reverse first k characters
for (int i = left, j = Math.min(left + k - 1, array.length - 1); i < j; i++, j--) {
char tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
return new String(array);
}
}
542. 01 Matrix
https://leetcode.com/problems/01-matrix/
对任意一个方格，最近的0距离不可能超过矩阵的row + col - 1。因此，可以将这个值作为初始的最大值，然后通过动态规划遍历更新最小距离。
class Solution {
public int[][] updateMatrix(int[][] mat) {
int row = mat.length;
int col = mat[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 0) {
continue;
}
// row + col - 1 is the max distance away for top left cell and bottom right cell
mat[i][j] = row + col - 1;
if (i > 0) {
// compare with top of current cell
mat[i][j] = Math.min(mat[i][j], mat[i - 1][j] + 1);
}
if (j > 0) {
// compare with left of current cell
mat[i][j] = Math.min(mat[i][j], mat[i][j - 1] + 1);
}
}
}
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (mat[i][j] == 0) {
continue;
}
if (i < row - 1) {
// compare with bottom of current cell
mat[i][j] = Math.min(mat[i][j], mat[i + 1][j] + 1);
}
if (j < col - 1) {
// compare with right of current cell
mat[i][j] = Math.min(mat[i][j], mat[i][j + 1] + 1);
}
}
}
return mat;
}
}
543. Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree/
要求出任意两个节点间的最大距离，大致的方向就是求出根节点的左右子树的深度，然后把两个树的深度进行累加，用这个累加值来更新最大结果。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int result = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return result;
}
private int maxDepth(TreeNode node) {
if (node == null) {
return 0;
}
// left and right subtrees' depth
int left = maxDepth(node.left);
int right = maxDepth(node.right);
// use sum of two subtrees to update result
result = Math.max(result, left + right);
// max subtree's depth + root node
return Math.max(left, right) + 1;
}
}
544. Output Contest Matches
https://leetcode.com/problems/output-contest-matches/
先按顺序把1～n进行排序，然后两两配对，第i支球队和第(n - 1 - i)支球队搭配。
class Solution {
public String findContestMatch(int n) {
String[] m = new String[n];
// map each number to corresponding string
for (int i = 0; i < n; i++) {
m[i] = String.valueOf(i + 1);
}
while (n > 1) {
// i-th team is paired with (n - 1 - i)-th team
for (int i = 0; i < n / 2; i++) {
m[i] = "(" + m[i] + "," + m[n - 1 - i] + ")";
}
n /= 2;
}
return m[0];
}
}
545. Boundary of Binary Tree
https://leetcode.com/problems/boundary-of-binary-tree/
环绕整棵树，分为三个步骤：
- 从上到下，遍历左边界
- 从左到右，遍历所有叶子节点
- 从下到上，遍历右边界
因此，把上述三个步骤写成三个函数。注意到左右的遍历是近似对称的，但由于遍历方向不同，添加根节点的时机也不同。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> result = new ArrayList<>();
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
if (root == null) {
return result;
}
result.add(root.val); // root is boundary as well
// root node has no child
if (root.left == null && root.right == null) {
return result;
}
// add left, right and leaves boundary
addLeft(root.left);
addLeaves(root);
addRight(root.right);
return result;
}
public void addLeft(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return;
}
// for left boundary, visit root node first then subtree
result.add(root.val);
// left subtree is boundary if it exists, otherwise right subtree is boundary
if (root.left != null) {
addLeft(root.left);
} else {
addLeft(root.right);
}
}
public void addRight(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return;
}
// right subtree is boundary if it exists, otherwise left subtree is boundary
if (root.right != null) {
addRight(root.right);
} else {
addRight(root.left);
}
// for right boundary, visit subtree first then root node
result.add(root.val);
}
public void addLeaves(TreeNode root) {
if (root == null) {
return;
}
// only add when there is no child
if (root.left == null && root.right == null) {
result.add(root.val);
}
addLeaves(root.left);
addLeaves(root.right);
}
}
546. Remove Boxes
https://leetcode.com/problems/remove-boxes/
给定boxes[i, j]这段区间，从左边界开始向右搜索连续相同的箱子数量。假设连续相同的最右下标是m，那么之后有两种策略：
- 先把
boxes[m]消除，这样就得到k * k的奖励，剩余的奖励全部产自boxes[i, m - 1] - 把
boxes[m]留着之后再用，那么就要进行比较，看boxes[i, m-1]和boxes[m+1, j]哪一段收益更大
class Solution {
public int removeBoxes(int[] boxes) {
if (boxes == null || boxes.length == 0) {
return 0;
}
int size = boxes.length;
int[][][] dp = new int[size][size][size];
return dfs(dp, boxes, 0, size - 1, 1);
}
private int dfs(int[][][] dp, int[] boxes, int i, int j, int k) {
if (i > j) {
return 0;
} else if (i == j) {
return k * k;
} else if (dp[i][j][k] != 0) {
return dp[i][j][k];
} else {
int result = dfs(dp, boxes, i + 1, j, 1) + k * k;
for (int m = i + 1; m <= j; m++) {
if (boxes[i] == boxes[m]) {
result = Math.max(result, dfs(dp, boxes, i + 1, m - 1, 1) + dfs(dp, boxes, m, j, k + 1));
}
}
dp[i][j][k] = result;
return result;
}
}
}
547. Number of Provinces
https://leetcode.com/problems/number-of-provinces/
使用一个一维数组，记录已经访问过的人。每一个人都检查他和其他人是否有朋友关系，如果发现了一组关系就检查这个朋友是否和其他人也有关系，以此dfs下去直到找不到为止。
class Solution {
public int findCircleNum(int[][] isConnected) {
int result = 0;
boolean[] visited = new boolean[isConnected.length];
for (int i = 0; i < visited.length; i++) {
// a new friend circle
if (!visited[i]) {
dfs(isConnected, visited, i);
result++;
}
}
return result;
}
private void dfs(int[][] isConnected, boolean[] visited, int i) {
for (int j = 0; j < visited.length; j++) {
if (i == j) {
continue;
}
// check friends one by one
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = true;
// dfs search to check friend's circle
dfs(isConnected, visited, j);
}
}
}
}
548. Split Array with Equal Sum
https://leetcode.com/problems/split-array-with-equal-sum/
三重循环，暴力破解。注意只有上两段子区间的和相同时，才开启下一重循环。
class Solution {
public boolean splitArray(int[] nums) {
int[] presum = new int[nums.length];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i ++) {
presum[i] = i == 0 ? nums[i] : presum[i - 1] + nums[i];
map.putIfAbsent(presum[i], new ArrayList<>());
map.get(presum[i]).add(i);
}
int n = nums.length;
for (int i = 1; i <= nums.length - 6; i++) {
int target = presum[i - 1];
List<Integer> kIndices = map.getOrDefault(presum[nums.length - 1] - target, new ArrayList<>());
for (int k : kIndices) {
if (k < n - 1 && k >= i + 4) {
List<Integer> jIndices = map.getOrDefault(presum[k - 1] - target, new ArrayList<>());
for (int j : jIndices) {
if (j > i + 1 && j < k - 1 && presum[j - 1] - presum[i] == target) {
return true;
}
}
}
}
}
return false;
}
}
549. Binary Tree Longest Consecutive Sequence II
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/
分别统计升序列和降序列的长度。统计时先遍历左子树，从底向上算出最长的升降序列；之后遍历右子树，从底向上算出最长的升降序列并和左子树的已有最大值进行比较；最后后序访问根节点，当前节点的最长连续序列就是升降序列之和，减去重复的长度1（根节点本身）。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int result = 0;
public int longestConsecutive(TreeNode root) {
helper(root);
return result;
}
public int[] helper(TreeNode root) {
if (root == null) {
return new int[] {0, 0};
}
int increase = 1, decrease = 1;
if (root.left != null) {
int[] l = helper(root.left);
if (root.val == root.left.val - 1) {
increase = l[0] + 1;
} else if (root.val == root.left.val + 1) {
decrease = l[1] + 1;
}
}
if (root.right != null) {
int[] r = helper(root.right);
if (root.val == root.right.val - 1) {
increase = Math.max(increase, r[0] + 1);
} else if (root.val == root.right.val + 1) {
decrease = Math.max(decrease, r[1] + 1);
}
}
result = Math.max(result, increase + decrease - 1);
return new int[] {increase, decrease};
}
}
550. Game Play Analysis IV
https://leetcode.com/problems/game-play-analysis-iv/
先找出每个玩家的最早登录记录，存为t1表，之后拿t1表和Activity表左连接，看能不能在最早登录日之后的一天继续找到了新的登录数据。
SELECT ROUND(COUNT(t2.player_id) / COUNT(t1.player_id), 2) AS fraction
FROM (
SELECT player_id, MIN(event_date) AS first_login
FROM Activity
GROUP BY player_id) t1 LEFT JOIN Activity t2
ON t1.player_id = t2.player_id AND t1.first_login = t2.event_date - 1
551. Student Attendance Record I
https://leetcode.com/problems/student-attendance-record-i/
分类讨论，注意遇到A或P时，要清空连续L状态。
class Solution {
public boolean checkRecord(String s) {
int countOfA = 0;
int continuousL = 0;
for (char c: s.toCharArray()) {
if (c == 'A') {
countOfA++;
if (countOfA > 1) {
return false;
}
continuousL = 0;
} else if (c == 'P') {
if (continuousL > 0) {
continuousL = 0;
}
} else if (c == 'L') {
continuousL++;
if (continuousL > 2) {
return false;
}
}
}
return true;
}
}
552. Student Attendance Record II
https://leetcode.com/problems/student-attendance-record-ii/
用ApLq来表示某个字符串中包含p个A，并且以q个L结束。根据题意，这边的p只能是0或者1，因为Absent次数最多为1；而q可以是0、1或2，因为连续Late次数最多为2。
当n = 1时，我们可以列出所有符合rewardable条件的字符串：
A0L0: P
A0L1: L
A0L2:
A1L0: A
A1L1:
A1L2:
当n = 2时，我们进一步列举：
A0L0: LP, PP
A0L1: PL
A0L2: LL
A1L0: AP, LA, PA
A1L1: AL
A1L2:
归纳总结发现以下状态转化表：
-----+---------------
INIT | A -- L -- P --
-----+---------------
A0L0 | A1L0 A0L1 A0L0
A0L1 | A1L0 A0L2 A0L0
A0L2 | A1L0 Done A0L0
A1L0 | Done A1L1 A1L0
A1L1 | Done A1L2 A1L0
A1L2 | Done Done A1L0
可以发现：
- 对于
n，A0L0的结果来自于n-1时，A0L0 + A0L1 + A0L2的和（相当于结尾添加一个P） - 对于
n，A0L1的结果实际上就是n-1时，A0L0的值（相当于结尾添加一个L） - …
根据以上推论，我们可以用一个长度为6的dp数组表示初始情况下n = 1时，A0L0 ～ A1L2对应的字符串数量，之后循环增大n时，用新的值覆盖原来dp数组即可。
class Solution {
public int checkRecord(int n) {
// init dp array for n = 1
int[] dp = { 1, 1, 0, 1, 0, 0 };
// temp array to store values for new dp array
int[] temp = { 0, 0, 0, 0, 0, 0 };
for (int i = 2; i <= n; i++) {
temp[0] = sum(dp, 0, 2);
temp[1] = dp[0];
temp[2] = dp[1];
temp[3] = sum(dp, 0, 5);
temp[4] = dp[3];
temp[5] = dp[4];
// copy temp values to dp
for (int j = 0; j < 6; j++) {
dp[j] = temp[j];
}
}
return sum(dp, 0, 5);
}
private int sum(int[] arr, int left, int right) {
int result = 0;
for (int i = left; i <= right; i++) {
result = (result + arr[i]) % 1000000007;
}
return result;
}
}
553. Optimal Division
https://leetcode.com/problems/optimal-division/
分类讨论：
- 只有1个数，这个数就是结果
- 只有2个数，那么第一个数除以第二个数就是结果
- 超过2个数，第一个数永远是被除数，后面的数依次连续除下去，因此能得到最小的除数，进而得到最大的商
class Solution {
public String optimalDivision(int[] nums) {
// only 1 number, result should be number itself
if (nums.length == 1) {
return Integer.toString(nums[0]);
}
// more than 1 number, the first number should always be dividend
StringBuilder sb = new StringBuilder();
sb.append(nums[0]).append("/");
// if 2 numbers, the second number should be divisor
// otherwise, all numbers except the first one should keep dividing
if (nums.length == 2) {
sb.append(nums[1]);
return sb.toString();
} else {
sb.append("(");
}
for (int i = 1; i < nums.length; i++) {
sb.append(nums[i]);
sb.append(i != nums.length - 1 ? "/" : ")");
}
return sb.toString();
}
}
554. Brick Wall
https://leetcode.com/problems/brick-wall/
用一个map存储对于某个下标，有多少行砖块在这个下标长度有缝隙。遍历每一行砖，每经过一块砖就更新一次map，最后看在哪一个下标上，有最多行砖是缝隙，这个地方就是画线的地方，可以保证穿过最少的砖。
class Solution {
private int mostCommon = 0;
public int leastBricks(List<List<Integer>> wall) {
// <index that at least 1 row has edge, row count>
Map<Integer, Integer>map = new HashMap<>();
for (List<Integer>list : wall) {
updateMap(list, map);
}
return wall.size() - mostCommon;
}
public void updateMap(List<Integer>list, Map<Integer,Integer> map) {
int currRowLen = 0;
for (int i = 0; i < list.size() - 1; i++) {
// get current brick length and add to current row's length
int brickLen = list.get(i);
currRowLen = currRowLen + brickLen;
// update number of rows that have edge on this length
map.put(currRowLen, map.getOrDefault(currRowLen, 0) + 1);
mostCommon = Math.max(mostCommon, map.get(currRowLen));
}
}
}
555. Split Concatenated Strings
https://leetcode.com/problems/split-concatenated-strings/
用StringBuilder把所有字符串连起来，转换到2倍复制扩容的char array里，之后分正序和倒序两种情况进行讨论，注意倒序的时候需要同时颠倒char array中前半段本体和后半段复制体。
此题运用了不少Java Arrays相关的API，可以较快帮助实现数组复制、比较等麻烦的操作：
Arrays.copyOf(Object[] original, int newLength): 从original对象数组中拷贝所有内容到新数组，并且使得新数组的长度为newLength。看长度变化，决定是否需要截断后续元素，或者是补0System.arrayCopy(Object[] src, int srcPos, Object[] dest, int destPos, int length): 从src指定位置，拷贝length长度的元素到dest的指定位置Arrays.compare(Object[] a, int aFromIndex, int aToIndex, Object[] b, int bFromIndex, int bToIndex): 用字典序比较a[aFromIndex, aToIndex]和b[bFromIndex, bToIndex]
class Solution {
public String splitLoopedString(String[] strs) {
StringBuilder concatted = new StringBuilder();
// for each string, decide whether to add original or reversed version based on lexicographical order
for (int i = 0; i < strs.length; i++) {
StringBuilder reversed = new StringBuilder(strs[i]).reverse();
concatted.append(CharSequence.compare(strs[i], reversed) > 0 ? strs[i] : reversed);
}
int totalLength = concatted.length();
char[] result = new char[totalLength];
// duplicate dc
char[] dc = Arrays.copyOf(concatted.toString().toCharArray(), totalLength * 2);
System.arraycopy(dc, 0, dc, totalLength, totalLength);
for (int i = 0, k = 0; i < strs.length; i++) {
// normal compare, copy dc to result
for (int j = 0; j < strs[i].length(); j++) {
if (Arrays.compare(result, 0, totalLength, dc, k + j, k + j + totalLength) < 0) {
System.arraycopy(dc, k + j, result, 0, totalLength);
}
}
// reverse each k + string's length, then compare, copy dc to result
reverse(dc, k, k + strs[i].length());
reverse(dc, k + totalLength, k + totalLength + strs[i].length());
for (int j = 0; j < strs[i].length(); j++) {
if (Arrays.compare(result, 0, totalLength, dc, k + j, k + j + totalLength) < 0) {
System.arraycopy(dc, k + j, result, 0, totalLength);
}
}
// reverse back
reverse(dc, k + totalLength, k + totalLength + strs[i].length());
k += strs[i].length();
}
return String.valueOf(result);
}
private void reverse(char[] str, int beginIndex, int endIndex) {
for (int i = 0; i < (endIndex - beginIndex) / 2; i++) {
char tmp = str[beginIndex + i];
str[beginIndex + i] = str[endIndex - 1 - i];
str[endIndex - 1 - i] = tmp;
}
}
}
556. Next Greater Element III
https://leetcode.com/problems/next-greater-element-iii/
与此前的Next Permutation问题完全一致，唯一区别在于输入参数从数组变成了整数，因此只需要把输入的整数转换成数组，然后用此前的解法找出下一组Permutation，最后再重新转换回整数。注意，如果发现转换的整数不大于输入的整数，说明不存在Next Greater Element。
class Solution {
private int[] toArray(int n) {
List<Integer> list = new ArrayList<>();
while (n != 0) {
list.add(n % 10);
n /= 10;
}
int[] result = new int[list.size()];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(result.length - 1 - i);
}
return result;
}
private int toInt(int[] nums) {
int result = 0;
for (int i : nums) {
result *= 10;
result += i;
}
return result;
}
public void nextPermutation(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
// search from right to left and find the first element to upset the ascending order
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i+1]) {
i--;
}
// if there is an element that upsets the ascending order
if (i >= 0) {
int j = nums.length - 1;
// find the rightmost element which is larger than nums[i]
while (nums[i] >= nums[j]) {
j--;
}
// swap nums[i] and nums[j]
swap(nums, i, j);
}
// reverse all elements after index i
reverseArray(nums, i + 1, nums.length - 1);
}
// swap two nums
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// reverse a part of the array
private void reverseArray(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
public int nextGreaterElement(int n) {
int[] nums = toArray(n);
nextPermutation(nums);
int nextNum = toInt(nums);
return nextNum <= n ? -1 : nextNum;
}
}
557. Reverse Words in a String III
https://leetcode.com/problems/reverse-words-in-a-string-iii/
split分割所有单词，每个单词倒序添加，然后再添加空格。
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
String[] words = s.split(" ");
for (String word : words) {
for (int i = word.length() - 1; i >= 0; i--) {
sb.append(word.charAt(i));
}
sb.append(" ");
}
// remove last blank space
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
}
558. Logical OR of Two Binary Grids Represented as Quad-Trees
https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/
DFS思想，不断对quad1, quad2同位置四个子树递归求出intersection结果，然后把结果覆盖到quad1上。如果发现当前quad1上是叶子结点，注意要将其子节点设为null。
/*
// Definition for a QuadTree node.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node() {}
public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
*/
class Solution {
public Node intersect(Node quad1, Node quad2) {
// logical bitwise OR
if (quad1.isLeaf) {
return quad1.val? quad1 : quad2;
}
if (quad2.isLeaf) {
return quad2.val? quad2 : quad1;
}
quad1.topLeft = intersect(quad1.topLeft, quad2.topLeft);
quad1.topRight = intersect(quad1.topRight, quad2.topRight);
quad1.bottomLeft = intersect(quad1.bottomLeft, quad2.bottomLeft);
quad1.bottomRight = intersect(quad1.bottomRight, quad2.bottomRight);
// current node is leaf, all 4 children should be null
if (quad1.topLeft.isLeaf && quad1.topRight.isLeaf
&& quad1.bottomLeft.isLeaf && quad1.bottomRight.isLeaf
&& quad1.topLeft.val == quad1.topRight.val
&& quad1.topRight.val == quad1.bottomLeft.val
&& quad1.bottomLeft.val == quad1.bottomRight.val) {
quad1.isLeaf = true;
quad1.val = quad1.topLeft.val;
quad1.topLeft = null;
quad1.topRight = null;
quad1.bottomLeft = null;
quad1.bottomRight = null;
}
return quad1;
}
}
559. Maximum Depth of N-ary Tree
https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
遍历所有子节点，每个子节点的子树上递归找出最大深度，汇总起来找到最大值。最后root节点本身也要使得深度+1。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int result = 0;
for (Node child : root.children) {
int currentTreeDepth = maxDepth(child);
result = Math.max(result, currentTreeDepth);
}
// add 1 as the height of root
return result + 1;
}
}
560. Subarray Sum Equals K
https://leetcode.com/problems/subarray-sum-equals-k/
用一个数组sum，保存截止到任意下标i时，nums[0]到nums[i]之间所有元素的和；再用一个map存储每一个pre sum分别在nums中出现了多少次。
因为我们可以很容易的获得sum[i]出现的次数，所以如果要求出值为k的pre sum出现了几次，我们只需要在map中查找值为sum[i] - k的pre sum出现的次数，对减即可。
class Solution {
public int subarraySum(int[] nums, int k) {
int result = 0;
// <sum, freq>
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
// pre sum array
int[] sum = new int[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i-1] + nums[i];
}
for (int i = 0; i < sum.length; i++) {
// if we know SUM[0, i - 1] and SUM[0, j], we get SUM[i, j]
if (map.containsKey(sum[i] - k)) {
result += map.get(sum[i] - k);
}
// add current pre sum to map
map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
}
return result;
}
}
561. Array Partition
https://leetcode.com/problems/array-partition/
排序数组，然后相邻每两个数取较小的那个进行累加。
class Solution {
public int arrayPairSum(int[] nums) {
int result = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i += 2) {
result += nums[i];
}
return result;
}
}
562. Longest Line of Consecutive One in Matrix
https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/
用4个数组分别储存每条水平、竖直、对角线和反对角线上的所有1的数量，两重循环遍历时遇到一个1就更新一次这四个数组的值，然后更新最大值。
注意，此题的技巧在于对角线与反对角线数组的表达，可以让这两个数组的长度都是矩阵长 + 宽 - 1，这样就能够方便地直接用矩阵横纵坐标定位对角线位置。
class Solution {
public int longestLine(int[][] M) {
if (M == null || M.length == 0) {
return 0;
}
int m = M.length;
int n = M[0].length;
int[] row = new int[m];
int[] col = new int[n];
int[] diag = new int[m+n-1];
int[] anti = new int[m+n-1];
int result = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
result = max(result, ++row[i], ++col[j], ++diag[i-j+n-1], ++anti[i+j]);
} else {
row[i] = col[j] = diag[i-j+n-1] = anti[i+j] = 0;
}
}
}
return result;
}
private int max(int a, int b, int c, int d, int e) {
return Math.max(a, Math.max(b, Math.max(c, Math.max(d, e))));
}
}
563. Binary Tree Tilt
https://leetcode.com/problems/binary-tree-tilt/
使用后序遍历，算出左右子树的总和绝对值之差。在上层父节点看来，下层孩子节点变成了子节点本身 + 孩子的左右子树之和。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int result = 0;
public int findTilt(TreeNode root) {
postOrder(root);
return result;
}
private int postOrder(TreeNode root) {
if (root == null) {
return 0;
}
int left = postOrder(root.left);
int right = postOrder(root.right);
result += Math.abs(left - right);
return left + right + root.val;
}
}
564. Find the Closest Palindrome
https://leetcode.com/problems/find-the-closest-palindrome/
利用输入的input字符串构造回文串，把后面的字符和前面的字符配对，得到了一个当前的回文数。然后再分别向前、后两个方向搜索最近回文数，比较这三个哪一个最近。
class Solution {
public String nearestPalindromic(String n) {
char[] arr = n.toCharArray();
for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
arr[j] = arr[i];
}
String curP = String.valueOf(arr);
String preP = nearestPalindrom(curP, false);
String nextP = nearestPalindrom(curP, true);
long num = Long.valueOf(n);
long cur = Long.valueOf(curP);
long pre = Long.valueOf(preP);
long next = Long.valueOf(nextP);
long d1 = Math.abs(num - pre);
long d2 = Math.abs(num - cur);
long d3 = Math.abs(num - next);
if (num == cur) {
return d1 <= d3 ? preP : nextP;
} else if (num > cur) {
return d2 <= d3 ? curP : nextP;
} else {
return d1 <= d2 ? preP : curP;
}
}
private String nearestPalindrom(String curP, boolean dir) {
int k = curP.length() >> 1, p = curP.length() - k;
int l = Integer.valueOf(curP.substring(0, p));
l += (dir ? 1 : -1);
if (l == 0) {
return k == 0 ? "0" : "9";
}
StringBuilder left = new StringBuilder(String.valueOf(l));
StringBuilder right = new StringBuilder(left).reverse();
if (k > left.length()) {
right.append("9");
}
return left.append(right.substring(right.length() - k)).toString();
}
}
565. Array Nesting
https://leetcode.com/problems/array-nesting/
用一个visited数组，存储全局情况下，某个数是否已经被访问过。之后遍历数组，遇到一个数currentNum就继续找nums[currentNum]，以此类推不断循环，直到遇到了重复的数字。
class Solution {
public int arrayNesting(int[] nums) {
int result = 0;
boolean[] visited = new boolean[nums.length];
for (int currentNum : nums) {
int currentLength = 0;
while (!visited[currentNum]) {
visited[currentNum] = true;
currentLength++;
currentNum = nums[currentNum];
}
result = Math.max(result, currentLength);
}
return result;
}
}
566. Reshape the Matrix
https://leetcode.com/problems/reshape-the-matrix/
把二维数组看成是一个长度为r * c的一维数组，行和列分别用除宽和模宽获得。
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int originR = nums.length;
int originC = nums[0].length;
if ((originR == r && originC == c) || (originR * originC != r * c)) {
return nums;
}
int[][] result = new int[r][c];
for (int i = 0; i < r * c; i++) {
result[i / c][i % c] = nums[i / originC][i % originC];
}
return result;
}
}
567. Permutation in String
https://leetcode.com/problems/permutation-in-string/
用滑动窗口，先用map统计s1中每个字母使用了几次，之后遍历s2，一个字母进入窗口就从map中扣去这个字母剩余的数量，一个字母退出窗口就让map加回此前扣除的数量。再使用一个变量，统计目前map中几个字母剩余数量不为0，如果所有字母剩余数量都是0则符合题意。
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
int[] map = new int[128];
int nonZeroCount = 0;
for (char c : s1.toCharArray()) {
if (map[c] == 0) nonZeroCount++;
map[c]++;
}
int s1Len = s1.length();
char[] s2CharArray = s2.toCharArray();
for (int i = 0; i < s2CharArray.length; i++) {
// add a new character to sliding window
map[ s2CharArray[i] ]--;
if (map[ s2CharArray[i] ] == -1) {
nonZeroCount++;
}
if (map[ s2CharArray[i] ] == 0) {
nonZeroCount--;
}
// remove an old character from sliding window
if (i >= s1Len) {
map[ s2CharArray[i - s1Len] ]++;
if (map[ s2CharArray[i - s1Len] ] == 0) {
nonZeroCount--;
}
if (map[ s2CharArray[i - s1Len] ] == 1) {
nonZeroCount++;
}
}
if (nonZeroCount == 0) {
return true;
}
}
return false;
}
}
568. Maximum Vacation Days
https://leetcode.com/problems/maximum-vacation-days/
每一周我们可以选择留在这个城市，这样总的休息天数就是当前这周在当前城市的休假天数 + 之后的休假天数；或者我们可以选择这周飞去其他城市，总的休息天数就变成了其他城市休假天数 + 之后的休假天数。比较取最大值。
class Solution {
private int numCities;
private int numWeeks;
private int[][] flights;
private int[][] days;
public int maxVacationDays(int[][] flights, int[][] days) {
this.numCities = flights.length;
this.numWeeks = days[0].length;
this.flights = flights;
this.days = days;
int[][] memo = new int[numCities][numWeeks];
return dfs(0, 0, memo);
}
private int dfs(int curCity, int curWeek, int[][] memo) {
if (curWeek == numWeeks) {
return 0;
}
if (memo[curCity][curWeek] != 0) {
return memo[curCity][curWeek];
}
int result = 0;
// Stay in current city for this week
result = Math.max(result, days[curCity][curWeek] + dfs(curCity, curWeek + 1, memo));
// Fly to other city to stay for this week
for (int i = 0; i < numCities; i++) {
if (i == curCity || flights[curCity][i] == 0) {
continue;
}
result = Math.max(result, days[i][curWeek] + dfs(i, curWeek+1, memo));
}
memo[curCity][curWeek] = result;
return result;
}
}
569. Median Employee Salary
https://leetcode.com/problems/median-employee-salary/
运用PARTITION BY语句，把所有公司分割开，然后在公司内部按照工资排序得到每个公司的排名表，再计算出总的公司的人数，这样就汇总得到了一份所有公司的人数+排名信息。从这个信息里，抽出每个公司里排名可能在中位数上的人。
WITH ranking_table AS (
SELECT *,
row_number() over(PARTITION BY Company ORDER BY Salary) AS company_rank,
COUNT(Id) over(PARTITION BY Company) AS company_total
FROM Employee
)
SELECT Id, Company, Salary
FROM ranking_table
WHERE company_rank BETWEEN company_total / 2 AND company_total / 2 + 1
570. Managers with at Least 5 Direct Reports
https://leetcode.com/problems/managers-with-at-least-5-direct-reports/
直接从ManagerId列表里，找到出现5次以上的编号。注意Having语句是需要搭配Group By一起使用的。
SELECT NAME
FROM Employee
WHERE Id IN (
SELECT ManagerId
FROM Employee
GROUP BY ManagerId
HAVING COUNT(ManagerId) >= 5
)
571. Find Median Given Frequency of Numbers
https://leetcode.com/problems/find-median-given-frequency-of-numbers/
假设一个数x的出现的频率为n，并且在x左侧的数总频率为l，在x右侧的数总频率为r，之后分别对小于等于x以及大于等于x的数做筛选，那么这两段数字的长度分别是n + l和n + r，两段长度对减就是l - r。很显然，如果l = r，就说明x正好是中位数；而即便l ≠ r，只要n足够大且能够覆盖l和r的差值，那也能说明x就是中位数。
SELECT AVG(n.num) median
FROM Numbers n
WHERE n.frequency >= abs((SELECT SUM(Frequency)
FROM Numbers
WHERE num <= n.num) -
(SELECT SUM(Frequency)
FROM Numbers
WHERE num >= n.num))
572. Subtree of Another Tree
https://leetcode.com/problems/subtree-of-another-tree/
判断两个树是否相等，之后再进行树的遍历。需要注意subtree为tree的子树可能有三种情况：完全相等、存在于左子树中、存在于右子树中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private boolean isSameTree(TreeNode tree, TreeNode subtree) {
if (tree == null && subtree == null) {
return true;
}
if (tree == null || subtree == null) {
return false;
}
if (tree.val != subtree.val) {
return false;
}
return isSameTree(tree.left, subtree.left) && isSameTree(tree.right, subtree.right);
}
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) {
return false;
}
return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
}
573. Squirrel Simulation
https://leetcode.com/problems/squirrel-simulation/
假设松鼠起始位置就在树下，那么总距离就是树到每个坚果的距离之和 * 2（来回）。但由于松鼠起始的位置可能不在树下，因此我们需要把原本*2中的一段进行替换，即从“树到坚果的距离”替换成“松鼠起始位置到坚果的距离”。显然，我们需要找到一个坚果，使得树、坚果的曼哈顿距离与松鼠、坚果的曼哈顿距离之差尽可能大。
class Solution {
public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
int sum = 0, maxDiff = Integer.MIN_VALUE;
for (int[] nut : nuts) {
// if the squirrel starts at the tree, the minimum total distance is 2 * total Manhattan distance
int dist = Math.abs(tree[0] - nut[0]) + Math.abs(tree[1] - nut[1]);
sum += 2*dist;
// since the squirrel starts elsewhere, substitute distance from (tree -> nut) to (squirrel -> nut) to minimize sum - maxDiff
// we shall find the nuts position that maximizes maxDiff
maxDiff = Math.max(maxDiff, dist - Math.abs(squirrel[0] - nut[0]) - Math.abs(squirrel[1] - nut[1]));
}
return sum - maxDiff;
}
}
574. Winning Candidate
https://leetcode.com/problems/winning-candidate/
根据Vote表中的CandidateId做排序，Group By之后按照CandidateId出现的数量从高到低排序，选择第一个。
SELECT Name
FROM Candidate
WHERE id = (
SELECT CandidateId
FROM Vote
GROUP BY CandidateId
ORDER BY COUNT(id)
DESC LIMIT 1
);
575. Distribute Candies
https://leetcode.com/problems/distribute-candies/
使用一个Set，统计出现过的不同candyType数量，实际能吃的数量上限是n/2。
class Solution {
public int distributeCandies(int[] candyType) {
Set<Integer> set = new HashSet<>();
for (int type : candyType) {
set.add(type);
}
return set.size() > candyType.length / 2 ? candyType.length / 2 : set.size();
}
}
576. Out of Boundary Paths
https://leetcode.com/problems/out-of-boundary-paths/
用一个三位数组dp存储状态，dp[i][j][move]表示从起点出发，经过move步到达(i, j)共有几条路径。可以进行分类讨论：
- 如果走出界了，只有1种方法走回去，即原地掉头返回矩阵
- 如果已经用完了步数，无法继续行动，返回0
- 如果
dp中的状态已经有计算好的了，直接返回 - 其他时候，用BFS遍历四个方向，更新
dp，注意取模
class Solution {
private int M = 1000000007;
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
if (maxMove == 0 || startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) {
return 0;
}
// how many possible ways to walk into cell[i][j] in step move
int[][][] dp = new int[m][n][maxMove + 1];
for (int[][] matrix : dp) {
for (int[] arr : matrix) {
Arrays.fill(arr, -1);
}
}
return updateDP(m, n, maxMove, startRow, startColumn, 0, dp);
}
public int updateDP(int m, int n, int N, int i, int j, int move, int[][][] dp) {
// out of bound, only way is to go back
if (i < 0 || i >= m || j < 0 || j >= n) {
return 1;
}
// already travel N moves, stops here
if (move == N) {
return 0;
}
// already traveled, directly retrieve from previous calculation
if (dp[i][j][move] >= 0) 「
return dp[i][j][move];
// BFS
int left = updateDP(m, n, N, i - 1, j, move + 1, dp);
int right = updateDP(m, n, N, i + 1, j, move + 1, dp);
int up = updateDP(m, n, N, i, j - 1, move + 1, dp);
int down = updateDP(m, n, N, i, j + 1, move + 1, dp);
// update new ways
dp[i][j][move] = ( (left + right) % M + (up + down) % M) % M;
return dp[i][j][move];
}
}
577. Employee Bonus
https://leetcode.com/problems/employee-bonus/
做一次left join，用empId建立关联，然后再用Where指定条件。
SELECT name, bonus
FROM Employee LEFT JOIN Bonus
ON Employee.empId = Bonus.empId
WHERE bonus < 1000 OR bonus is NULL
578. Get Highest Answer Rate Question
https://leetcode.com/problems/get-highest-answer-rate-question/
用SUM()和IF()函数，统计出对于每个question_id，answer的次数和show的次数分别是多少，二者相除，降序排序后输出最大值。
SELECT question_id survey_log
FROM SurveyLog
GROUP BY 1
ORDER BY SUM(IF(action='answer', 1, 0)) / SUM(IF(action='show', 1, 0)) DESC, 1 ASC
LIMIT 1
579. Find Cumulative Salary of an Employee
https://leetcode.com/problems/find-cumulative-salary-of-an-employee/
先确定月份范围（近期3个月并除去最近一个月），再归类范围内的月份并累加总工资。
SELECT id, month, SUMs AS salary
FROM (
SELECT id, month, ROW_NUMBER() OVER(PARTITION BY id ORDER BY month DESC) AS rk,
SUM(Salary) OVER(PARTITION BY id ORDER BY month RANGE BETWEEN 2 PRECEDING AND CURRENT ROW) AS SUMs
FROM Employee) temp
WHERE rk > 1
ORDER BY id ASC, month DESC
580. Count Student Number in Departments
https://leetcode.com/problems/count-student-number-in-departments/
用Department表和Student表左连接，因为有的Department里可能没有学生。之后再Group By用Count()统计出每个Department里的学生数量。
SELECT d.dept_name, COUNT(s.student_id) AS student_number
FROM department d LEFT JOIN student s
ON d.dept_id = s.dept_id
GROUP BY d.dept_name
ORDER BY student_number DESC
581. Shortest Unsorted Continuous Subarray
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
维护两个变量max和min，max负责从前往后搜索数组最大值，min负责从后往前搜索数组最小值。如果发现当前nums[i]比max更小，说明破坏了从左到右的升序规则，i就是排序区间的结尾；如果发现当前nums[n - 1 - i]比min更大，说明破坏了从右到左的降序规则，n - 1 - i就是排序区间的结尾。
class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int beg = -1, end = -2, min = nums[n-1], max = nums[0];
for (int i = 1; i < n; i++) {
// search max forward and search min backward
max = Math.max(max, nums[i]);
min = Math.min(min, nums[n - 1 - i]);
// find the begin and end indices that upset sorted order
if (nums[i] < max) {
end = i;
}
if (nums[n - 1 - i] > min) {
beg = n - 1 - i;
}
}
return end - beg + 1;
}
}
582. Kill Process
https://leetcode.com/problems/kill-process/
先使用一个HashMap把每个父节点以及对应的全部子节点存储起来，之后用BFS的层次遍历思想，先把kill加入队列，之后每次循环都提取出队列的第一个进程并终止，再把这个进程所有子节点加入队列，如此不断循环遍历直到队列为空。
class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
List<Integer> result = new ArrayList<>();
Map<Integer, List<Integer>> map = new HashMap<>(); // <parent process id, all children's ids>
// for each parent, add all its children
for (int i = 0; i < pid.size(); i++) {
int currentParent = ppid.get(i);
int currentChild = pid.get(i);
map.putIfAbsent(currentParent, new ArrayList<>());
map.get(currentParent).add(currentChild);
}
// use BFS to kill
Queue<Integer> queue = new ArrayDeque<Integer>();
queue.add(kill);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int cur = queue.remove();
result.add(cur);
// add every child of current process to the queue
List<Integer> children = map.get(cur);
if (children != null) {
for (int child : children) {
queue.add(child);
}
}
}
}
return result;
}
}
583. Delete Operation for Two Strings
https://leetcode.com/problems/delete-operation-for-two-strings/
此题实际上是求word1和word2的最长公共子串长度，总的操作次数实际上是word1和word2分别变成公共子串的步骤之和。显然，要使得这个操作次数尽量小，必须要让公共子串尽可能长。
使用二维动态规划，dp[i][j]表示word1的前i个字符与word2的前j个字符之间的最长公共子串长度。
对于dp[i][j]而言，如果word1[i]和word2[j]字符相同，那么二者的距离就只取决于word1[0, i-1]和word2[0, j-1]，因此dp[i][j]也只取决于dp[i - 1][j - 1]。而如果word1[i]和word2[j]字符不相同，那么就要进行比较，看是word1[0, i-1]和word2[0, j]的字串更长，还是word1[0, i]和word2[0, j-1]的字串更长。
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length(), len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else {
dp[i][j] = (word1.charAt(i-1) == word2.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]));
}
}
}
return len1 - dp[len1][len2] + len2 - dp[len1][len2];
}
}
584. Find Customer Referee
https://leetcode.com/problems/find-customer-referee/
直接指定referee_id的条件即可。
SELECT name
FROM customer
WHERE referee_id IS NULL OR referee_id != 2
585. Investments in 2016
https://leetcode.com/problems/investments-in-2016/
自连接，用Count()分别比较TIV_2015和经纬度，因为经纬度要求独一无二因此数量只能是1，而TIV_2015则要求不止一个。
SELECT SUM(TIV_2016) TIV_2016
FROM insurance a
WHERE 1 = (
SELECT COUNT(*)
FROM insurance b
WHERE a.LAT = b.LAT AND a.LON = b.LON
) AND 1 < (
SELECT COUNT(*)
FROM insurance c
WHERE a.TIV_2015 = c.TIV_2015
)
586. Customer Placing the Largest Number of Orders
https://leetcode.com/problems/customer-placing-the-largest-number-of-orders/
Group By之后，直接按Count(*)进行降序排序。
SELECT customer_number
FROM Orders
GROUP BY customer_number
ORDER BY COUNT(*) DESC
LIMIT 1
对于follow-up，只需要根据具体的最大数量，再做一次子查询即可。
SELECT customer_number
FROM Orders
GROUP BY customer_number
HAVING COUNT(order_number) = (
SELECT COUNT(order_number) AS cnt
FROM orders
GROUP BY customer_number
ORDER BY cnt DESC
LIMIT 1
)
587. Erect the Fence
https://leetcode.com/problems/erect-the-fence/
凸包(Convex Hull)问题。把所有坐标点按找x坐标从大到小排序，x相同则按y从大到小排序，这样排序的目的是之后便于指定描边的方向。之后分别进行上、下部分的描边，因为每个点已经按照坐标进行排序，所以我们希望大致沿逆时针方向进行描边，并用一个栈记录每一个经过的点。如果最近的三个点连成的两条线不能形成一个逆时针方向的转折，就把中间的点抛弃，在一次循环中该用最近的点作为中点。最后利用set除去栈中的重复元素。
这一算法的核心在于需要对所有坐标点预先进行排序，之后便可以直接按顺序单调遍历，因此时间复杂度为O(nlogn)；因为额外使用了stack与set，所以空间复杂度为O(n)。
class Solution {
public int[][] outerTrees(int[][] trees) {
// sort the point of P by x-coor (case tie, sort by y-coor)
Arrays.sort(trees, (p, q) -> q[0] == p[0] ? q[1] - p[1] : q[0] - p[0]);
// hold the vertices of upper and lower hulls
Stack<int[]> hull = new Stack<>();
int n = trees.length;
// upper layer of hulls
for (int i = 0; i < n; i++) {
// last two trees of Lower hulls and P[i] do not make a counter clockwise turn
while (hull.size() >= 2 && orientation(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i])) {
// remove q on (p, q, r)
hull.pop();
}
hull.push(trees[i]);
}
hull.pop();
// lower layer of hulls
for (int i = n - 1; i >= 0; i--) {
while (hull.size() >= 2 && orientation(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i])) {
hull.pop();
}
hull.push(trees[i]);
}
// remove redundant elements from the stack
HashSet<int[]> set = new HashSet<>(hull);
return set.toArray(new int[set.size()][2]);
}
// compare (q[1] - p[1]) / (q[0] - p[0]) and (r[1] - q[1]) / (r[0] - q[0])
// return true if pq and qr form a clockwise turn
public boolean orientation(int[] p, int[] q, int[] r) {
return (q[1] - p[1]) * (r[0] - q[0]) > (q[0] - p[0]) * (r[1] - q[1]);
}
}
588. Design In-Memory File System
https://leetcode.com/problems/design-in-memory-file-system/
设计上有几个要点：
- 自定义一个
FileNode数据结构，可以给这个数据结构加一个属性来区分这个FileNode是一个文件夹还是一个具体文件，这在之后的路径寻址上有很大帮助。此处可以直接使用一个StringBuilder对象一举两得，这个对象又可以用于存储具体的文件内容，又可以兼任这个区分属性 - 维护一个
FileNode的所有子节点，可以直接使用Tree Map，因为输出文件时也需要按照字典序输出 - 在寻址的时候，先用
split()方法分割路径，之后进行判断，如果遇到的是文件夹直接跳过；如果是文件，还需要考虑这个文件是已有的文件还是新文件，这一点可以利用map的putIfAbsent()方法实现
class FileSystem {
private FileNode root;
public FileSystem() {
root = new FileNode("");
}
public List<String> ls(String path) {
return findNode(path).getList();
}
public void mkdir(String path) {
findNode(path);
}
public void addContentToFile(String filePath, String content) {
findNode(filePath).addContent(content);
}
public String readContentFromFile(String filePath) {
return findNode(filePath).getContent();
}
private FileNode findNode(String path) {
String[] files = path.split("/");
FileNode cur = root;
for (String file : files) {
// current directory is still a folder, continue
if (file.length() == 0) {
continue;
}
// add a new file, or modify an existed file
cur.children.putIfAbsent(file, new FileNode(file));
cur = cur.children.get(file);
if (cur.isFile()) {
break;
}
}
return cur;
}
private class FileNode {
private TreeMap<String, FileNode> children;
private StringBuilder file;
private String name;
public FileNode(String name) {
children = new TreeMap<>();
file = new StringBuilder();
this.name = name;
}
public String getContent() {
return file.toString();
}
public String getName() {
return name;
}
public void addContent(String content) {
file.append(content);
}
public boolean isFile() {
return file.length() > 0;
}
public List<String> getList() {
List<String> list = new ArrayList<>();
if (isFile()) {
list.add(getName());
} else {
list.addAll(children.keySet());
}
return list;
}
}
}
589. N-ary Tree Preorder Traversal
https://leetcode.com/problems/n-ary-tree-preorder-traversal/
第一种方法，直接使用递归：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
helper(result, root);
return result;
}
private void helper(List<Integer> result, Node node) {
if (node == null) {
return;
}
result.add(node.val);
for (Node child : node.children) {
helper(result, child);
}
}
}
第二种方法，使用栈迭代访问，注意添加子节点时，需要从最后一个子节点开始压入栈中。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.empty()) {
root = stack.pop();
list.add(root.val);
for (int i = root.children.size() - 1; i >= 0; i--) {
stack.add(root.children.get(i));
}
}
return list;
}
}
590. N-ary Tree Postorder Traversal
https://leetcode.com/problems/n-ary-tree-postorder-traversal/
第一种方法，直接使用递归：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> result = new ArrayList<>();
helper(result, root);
return result;
}
private void helper(List<Integer> result, Node node) {
if (node == null) {
return;
}
for (Node child : node.children) {
helper(result, child);
}
result.add(node.val);
}
}
第二种方法，使用栈迭代访问，添加完所有子节点后，翻转list即可。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.empty()) {
root = stack.pop();
list.add(root.val);
for (Node child : root.children) {
stack.add(child);
}
}
Collections.reverse(list);
return list;
}
}
591. Tag Validator
https://leetcode.com/problems/tag-validator/
使用正则表达式：
- 用非贪心的模式
.*?匹配CDATA - 尝试用先
([A,Z]{1,9})后\\1的组合，匹配Tag name
class Solution {
public boolean isValid(String code) {
if (code.equals("t")) {
return false;
}
code = code.replaceAll("<!\\[CDATA\\[.*?\\]\\]>", "c");
String prev = "";
while (!code.equals(prev)) {
prev = code;
code = code.replaceAll("<([A-Z]{1,9})>[^<]*</\\1>", "t");
}
return code.equals("t");
}
}
592. Fraction Addition and Subtraction
https://leetcode.com/problems/fraction-addition-and-subtraction/
使用两个StringBuilder，分别存储每个分数分子和分母，之后把这两个StringBuilder转化成整数形式，并累加分数。累加后，计算分子和分母的最大公约数，再进行约分。
class Solution {
public String fractionAddition(String expression) {
if (expression == null || expression.length() == 0) {
return "";
}
int dividend = 0;
int denominator = 1;
int i = 0;
while (i < expression.length()) {
StringBuilder dividendSB = new StringBuilder();
// get dividend
while (i < expression.length() && expression.charAt(i) != '/') {
dividendSB.append(expression.charAt(i));
i++;
}
i++;
// get denominator
StringBuilder denominatorSB = new StringBuilder();
while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
denominatorSB.append(expression.charAt(i));
i++;
}
// parse to integer
int newDividend = Integer.parseInt(dividendSB.toString());
int newDenominator = Integer.parseInt(denominatorSB.toString());
// directly add fraction
dividend = dividend * newDenominator + newDividend * denominator;
denominator = denominator * newDenominator;
// find gcd then reduce fraction
int gcd = findgcd(dividend, denominator);
dividend = dividend / gcd;
denominator = denominator / gcd;
}
return dividend + "/" + denominator;
}
public int findgcd(int a, int b) {
return (a != 0) ? findgcd(b % a, a) : Math.abs(b);
}
}
593. Valid Square
https://leetcode.com/problems/valid-square/
如果四个点能组成正方形，这四个点的距离两两连线，只会有两种情况：边长和对角线长。根据这一特性，我们可以尝试用HashSet添加所有两两连线的距离，观察最后值的个数。
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
HashSet<Integer> hs = new HashSet<>(Arrays.asList(dist(p1, p2), dist(p1, p3), dist(p1, p4),
dist(p2, p3), dist(p2, p4), dist(p3, p4))
);
// side and diagonal
return !hs.contains(0) && hs.size() == 2;
}
private int dist(int[] a, int[] b) {
return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
}
}
594. Longest Harmonious Subsequence
https://leetcode.com/problems/longest-harmonious-subsequence/
用一个HashMap统计每个数字出现的频率，之后遍历map中的所有key，如果key和key + 1都存在于map中，说明由所有key和key + 1组成的序列就是一个harmonious subsequence，其长度为二者的频率之和。
class Solution {
public int findLHS(int[] nums) {
// <num, freq>
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int result = 0;
for (int key : map.keySet()) {
if (map.containsKey(key + 1)) {
result = Math.max(result, map.get(key + 1) + map.get(key));
}
}
return result;
}
}
595. Big Countries
https://leetcode.com/problems/big-countries/
直接根据条件筛选即可。
SELECT name, population, area
FROM World
WHERE population > 25000000 OR area > 3000000;
596. Classes More Than 5 Students
https://leetcode.com/problems/classes-more-than-5-students/
按照class做Group By后，统计所有不重复的学生数量。
SELECT class
FROM courses
GROUP BY class
HAVING COUNT(DISTINCT student) >= 5
597. Friend Requests I: Overall Acceptance Rate
https://leetcode.com/problems/friend-requests-i-overall-acceptance-rate/
因为两张表都没有主键，可能存在重复，因此在统计请求和接受总量时都需要带上DISTINCT；并且需要考虑到数据长度为0的情况，即用IFNULL()进行处理；最后还需要用ROUND()保留2位小数。
SELECT ROUND(IFNULL(COUNT(DISTINCT requester_id, accepter_id) / COUNT(DISTINCT sender_id, send_to_id), 0), 2) AS accept_rate
FROM FriendRequest, RequestAccepted;
于Follow-up问题，可以额外做两组子查询，一组找出RequestAccepted中所有不同accept的月份，另一组找出FriendRequest中所有不同request的月份，如果二者月份相同，就计算出这个月中的接受率。
SELECT IF(d.req = 0, 0.00, ROUND(c.acp / d.req, 2)) AS accept_rate, c.month
FROM (
SELECT COUNT(DISTINCT requester_id, accepter_id) AS acp, Month(accept_date) AS month FROM RequestAccepted) c,
(SELECT COUNT(DISTINCT sender_id, send_to_id) AS req, Month(request_date) AS month FROM FriendRequest) d
WHERE c.month = d.month
GROUP BY c.month
598. Range Addition II
https://leetcode.com/problems/range-addition-ii/
找出ops中最小的ai和bi即可，在此范围内的数都是最大值。
class Solution {
public int maxCount(int m, int n, int[][] ops) {
for (int i = 0 ; i < ops.length; i++) {
if (ops[i][0] < m) {
m = ops[i][0];
}
if (ops[i][1] < n) {
n = ops[i][1];
}
}
return m * n;
}
}
599. Minimum Index Sum of Two Lists
https://leetcode.com/problems/minimum-index-sum-of-two-lists/
先遍历一遍list1，把每个元素以及对应的下标存储到HashMap中。之后再遍历list2，看list2中的每个元素是否在map中，如果map中能找到，就计算二者的下标之和，并且把结果添加到result中。一旦后续了发现下标和更小的结果，就把result清空，重新添加。
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
List<String> result = new LinkedList<>();
// <list1 element, list1 index>
Map<String, Integer> map = new HashMap<>();
int minSum = Integer.MAX_VALUE;
for (int i = 0; i < list1.length; i++) {
map.put(list1[i], i);
}
for (int j = 0; j < list2.length; j++) {
Integer i = map.get(list2[j]);
if (i != null && i + j <= minSum) {
if (i + j < minSum) {
// update with latest minimum sum
result.clear();
minSum = i+j;
}
result.add(list2[j]);
}
}
return result.toArray(new String[result.size()]);
}
}
600. Non-negative Integers without Consecutive Ones
https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/
使用动态规划，两个数组a[]和b[]分别用于不同存储，其中a[i]表示长度为i的二进制字符串中，没有两个连续1并且结尾是0的个数；b[i]表示长度为i的二进制字符串中，没有两个连续1并且结尾是1的个数。很显然，结尾是0的字符串我们可以任意添加0或者1，但是结尾已经是1的字符串中我们只能添加0，由此可以得出递归公式。最后，减去结果中大于num的情况。
class Solution {
public int findIntegers(int num) {
StringBuilder sb = new StringBuilder(Integer.toBinaryString(num));
int n = sb.length();
// a[i] is the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0
// b[i] is the number of such strings which end in 1
// we can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1
int a[] = new int[n];
int b[] = new int[n];
a[0] = b[0] = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i - 1] + b[i - 1];
b[i] = a[i - 1];
}
int result = a[n - 1] + b[n - 1];
// subtract the solutions which is larger than num
for (int i = 1; i < n; i++) {
if (sb.charAt(i) == '1' && sb.charAt(i-1) == '1') {
break;
}
if (sb.charAt(i) == '0' && sb.charAt(i-1) == '0') {
result -= b[n-i-1];
}
}
return result;
}
}
PREVIOUSLeetCode 401-500
NEXT排序算法