第一题，模拟。思路就是数字和字母的LOG分开，字母的需要排序，我就用TREEMAP来解决了。数字就是原顺序放进ARRAYLIST里。
937. Reorder Log Files
https://leetcode.com/contest/weekly-contest-110/problems/reorder-log-files/
public String[] reorderLogFiles(String[] logs) {
List<String> num = new ArrayList<>();
TreeMap<String,Set<String>> letter = new TreeMap<>();
for (String log : logs) {
int idx = log.indexOf(' ');
String iden = log.substring(0,idx);
String val = log.substring(idx+1);
if (Character.isDigit(val.charAt(0))) {
num.add(log);
}else{
letter.putIfAbsent(val,new TreeSet<>());
letter.get(val).add(iden);
}
}
String[] res = new String[logs.length];
int idx = 0;
for (String key : letter.keySet()) {
for (String iden : letter.get(key)) {
res[idx++] = iden+" "+key;
}
}
for (String digitLog : num) {
res[idx++] = digitLog;
}
return res;
}
938. Range Sum of BST
https://leetcode.com/contest/weekly-contest-110/problems/range-sum-of-bst/
第二题，是BST搜索，中序遍历，节点符合条件就把值加进去。同时利用BST的性质做优化，来剪枝。
int sum;
public int rangeSumBST(TreeNode root, int L, int R) {
if (root == null)
return 0;
inOrder(root, L, R);
return sum;
}
private void inOrder(TreeNode cur, int L, int R) {
if (cur == null)
return;
if(cur.val >= L)
inOrder(cur.left, L, R);
if (cur.val >= L && cur.val <= R)
sum += cur.val;
if(cur.val <= R)
inOrder(cur.right, L, R);
}
939. Minimum Area Rectangle
https://leetcode.com/contest/weekly-contest-110/problems/minimum-area-rectangle/
第三题，我卡了一会，我一开始的想法是用扫描线来做。然后遇到点困难。随后看了下数据规模，发现N^2可以，转换思路，用暴力解法。
我们就是找出所有的合法矩形，定义一个矩形需要2个点就够了。一个是左下角的，一个是右上角的。随后看另外2个点在不在点集中，如果在，这就能构成一个合法矩形，枚举左下角和右上角的2个点的选择情况。然后判断矩形存在，存在的话就更新MIN AREA
public int minAreaRect(int[][] points) {
Set<Integer> s = new HashSet<>();
for (int[] p : points) {
s.add(p[0] * 40001 + p[1]);
}
int min = Integer.MAX_VALUE;
int l = points.length;
for (int i = 0; i < l; i++) {
int[] p1 = points[i];
for (int j = i + 1; j < l; j++) {
int[] p2 = points[j];
if (p1[0] == p2[0] || p1[1] == p2[1]) continue;
int need1 = p1[0] * 40001 + p2[1];
int need2 = p2[0] * 40001 + p1[1];
if (s.contains(need1) && s.contains(need2)) {
min = Math.min(Math.abs(p1[0]-p2[0]) * Math.abs(p1[1]-p2[1]), min);
}
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
940. Distinct Subsequences II
https://leetcode.com/contest/weekly-contest-110/problems/distinct-subsequences-ii/
这道题，我上来就思考到。如果新进来一个从没见过的字母。其实就是2*pre + 1
因为除了前面部分产生的答案，随后产生的答案都可以在前面的答案基础上加上那个新字母而不会有重复。
最后+1 是因为，唯一这个新字母，也是一个答案。
但是再遇到了前面出现过这个字母的时候，遇到了困难。
随后我通过举例ABB, ABA
发现可以通过增加一个空字符串来定义当遇到一个重复字母的转移方程。
DP[0] = 1
我们开一个DP数组，表示的含义是DP I = 第I个字母作为结尾，可以贡献多少个新的子序列。
如果这个字母之前从未出现过。那么DP I = SUM{DP[0] - > DP[I-1]}
举例 "", a ,b
dp 1, 1(a), 2(b,ab)
那么再来一个B 的时候，观察发现。因为之前一些字符更短的，已经被前面的B COVER过了。所以新来的B，只能在从B开始之后构造的子序列里加上自己。
如果来的是C（一个新字符），那么可以用C 去和“” 组合，去和 a (a) 组合, 去和b (b,ab) 组合。
变成 c,ac,bc,abc
当来的是B， 那么和a 和 “”组合，会和之前的B有重复。 所以只能和B 组合。
变成 bb,abb
那么在观察aba 的时候，
a遇到了前面那个a,前面那个a 占用了和空串 组合，所以新来的A，没有必要再和前面那个A的前面的任何子串做组合了，因为都会和前面那个A组合有重复。
根据以上。
public int distinctSubseqII(String S) {
if(S.length() == 0) return 0;
int[] dp = new int[S.length()+1];
dp[0] = 1;
int M = 1000000007;
for (int i = 1; i <= S.length(); i++) {
long sum = 0;
for (int j = i - 1; j >= 0; j--) {
sum += dp[j];
if(j == 0 || S.charAt(i - 1) == S.charAt(j - 1))
break;
}
dp[i] = (int) (sum % M);
}
int res = 0;
for(int i = 1; i <= S.length(); i++) {
res = (res + dp[i]) % M;
}
return res;
}
最后求和这部，可以利用前缀和的思想，来优化掉。
但是我们要找到最近的那个相同字母的出现位置，后面的都要减去。
所以要额外开一个26的数组（等价MAP）来记录最后该字母在STR中出现的位置即可。
public int distinctSubseqII(String S) {
if(S.length() == 0) return 0;
int[] dp = new int[S.length()+1];
dp[0] = 1;
int[] pos = new int[26];
Arrays.fill(pos, -1);
int M = 1000000007;
for (int i = 1; i <= S.length(); i++) {
dp[i] = 2 * dp[i - 1] % M;
int idx = S.charAt(i - 1) - 'a';
if(pos[idx] != -1) {
dp[i] = (dp[i] - dp[pos[idx] - 1] + M) % M;
}
pos[idx] = i;
}
return dp[S.length()] - 1;
}
