因为那次比赛，人在外面旅游，来补发一下104的4道题。
914. X of a Kind in a Deck of Cards
https://leetcode.com/contest/weekly-contest-104/problems/x-of-a-kind-in-a-deck-of-cards/
这道题首先就是统计，每种牌的张数。下面就找到最小的那一落，看是不是大于等于2，其次别的张数是否可以整除它。
这个思路发现当牌数为4,6的时候，会出错。
所以要算出加入最小的那落的最小质因子。
或者用前小2 的2落，求最大公约数。
public boolean hasGroupsSizeX(int[] deck) {
int l = deck.length;
if(l <= 1) return false;
Map<Integer,Integer> map = new HashMap<>();
for (int i : deck) {
map.put(i,map.getOrDefault(i,0)+1);
}
TreeSet<Integer> t = new TreeSet<>();
for(int i : map.values()){
t.add(i);
}
int min = t.pollFirst();
if(min < 2) return false;
if(t.isEmpty()) return true;
int sec = t.pollFirst();
min = lcs(sec,min);
if(min < 2) return false;
for(int i : t){
if(i % min == 0) continue;
return false;
}
return true;
}
public int lcs(int a,int b){
if(a % b == 0) return b;
return lcs(b,a%b);
}
915. Partition Array into Disjoint Intervals
https://leetcode.com/contest/weekly-contest-104/problems/partition-array-into-disjoint-intervals/
分别结算出右最小，左最大数组。然后找到左最大小于右最小的最左边的一个点。
public int partitionDisjoint(int[] A) {
int l = A.length;
int[] leftMax = new int[l];
int[] rightMin = new int[l];
leftMax[0] = A[0];
for(int i = 1; i < l; i++)
leftMax[i] = Math.max(leftMax[i-1],A[i]);
rightMin[l-1] = 20000000;
for(int i = l-2; i >= 0; i--) {
rightMin[i] = Math.min(A[i+1],rightMin[i+1]);
}
for(int i = 0; i < l; i++){
if(leftMax[i]<=rightMin[i]) return i+1;
}
return -1;
}
一次PASS怎么做？
一旦后面出现了一个数，比前面的MAX要小，这个点就是肯定要归于左边的。
所以我们需要维护2个MAX，一个是已经安放好的最左边的MAX，一个是扫描到当前位置的MAX。
然后新来一个数，一旦小于最左MAX，那么最左MAX就更新成当前MAX，随后左边必须要扩容。
public int partitionDisjoint(int[] A) {
int l = A.length;
int leftMax = A[0];
int curMax = A[0];
int p = 1;
for(int i = 1; i < l; i++){
curMax = Math.max(A[i],curMax);
if(A[i] < leftMax){
leftMax = curMax;
p = i+1;
}
}
return p;
}
916. Word Subsets
https://leetcode.com/contest/weekly-contest-104/problems/word-subsets/
先把B数组每个单词，的字母频率都统计好，在每个字母上取MAX。
随后统计A的单词，看是否都能满足B的MAX频率表
public List<String> wordSubsets(String[] A, String[] B) {
List<String> res = new ArrayList<>();
int[] map = new int[26];
for (String s : B) {
int[] tmp = new int[26];
for (char c : s.toCharArray()) {
tmp[c-'a']++;
}
for(int i = 0; i < 26; i++) {
map[i] = Math.max(map[i],tmp[i]);
}
}
for (String s : A) {
int[] tmp = new int[26];
for (char c : s.toCharArray()) {
tmp[c-'a']++;
}
boolean contains = true;
for(int i = 0; i < 26; i++) {
if(tmp[i]<map[i]){
contains = false;
break;
}
}
if(contains) res.add(s);
}
return res;
}
913. Cat and Mouse
https://leetcode.com/problems/cat-and-mouse/description/
首先因为最多50个格子，猫50个里取一个，老鼠50个里取1个，还要先后手的问题。
状态空间在50502，不算大。
这道题一开始我也适用记忆化搜索做的，后来发现是不对。
因为当你来回走的时候，回到之前去过的点，你判定是平局，不是这个状态就是平局了，而是你的一个路径回到这个状态才是平局，所以一旦你把这个状态记为平局，就会出错。
如果真的要记状态，是要把之前猫和老鼠的运动轨迹都记一下的。
随后看了答案。大概解释下我对SOLUTION的解法的理解。
答案的解法就默认了所有状态，都是平局的。
然后标记处所有的最终状态，根据最终状态去反推，所有不应该是平局的状态点。如果推不下去了，就意味着那些触及不到的状态就是平局的。最后看起始状态是否是平局还是谁赢。
那么最终状态有3种情况，
分别是老鼠走一步，走到猫身上（可能被猫逼入死角，只能往猫身上走了）。算猫赢
猫走一步，走到老鼠身上，算猫赢。
以及，老鼠在0了，猫在其他所有位置，算老鼠赢。
在反推的时候，如果最终状态下一步该猫走，说明上一步是该老鼠走。反之亦然。如果最终状态是猫赢，上一步是老鼠走的状态是猫赢，并不能说明这个状态就一定是猫赢，因为一旦有一个老鼠赢的状态也能转到该状态，那么该状态就还是老鼠赢。
如下图，当2这个子状态反推到，右边的那个1. 是不能立刻把他的PARENT标记为1.
只有所有右边的那个1的走法，走的都是2，才能标记它为2. 只要有1个1，他就是1.
为了记录所有走法是不是都是2，就需要知道每个状态的度数有多少。
然后一旦状态不一致，就让度数--，度数减到0，就代表，这个老鼠位置，怎么走都是猫赢的局面了。
final int DRAW = 0;
final int MOUSE = 1;
final int CAT = 2;
public int catMouseGame(int[][] graph) {
int n = graph.length;
int[][][] degree = new int[n+1][n+1][3];
int[][][] dp = new int[n+1][n+1][3];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
degree[i][j][1] = graph[i].length;
degree[i][j][2] = graph[j].length;
for(int k : graph[j]){
if(k == 0){
degree[i][j][2]--;
break;
}
}
}
}
Queue<int[]> q = new LinkedList<>();//mouse(1),cat(2),whoGo,whoWin
for(int i = 1; i < n; i++){
q.offer(new int[]{i,i,1,2});//mouseGo, CatWin
dp[i][i][MOUSE] = CAT;
dp[i][i][CAT] = CAT;
q.offer(new int[]{i,i,2,2});
q.offer(new int[]{0,i,2,1});//catGo, MouseWin
dp[0][i][CAT] = MOUSE;
}
while(!q.isEmpty()) {
int[] cur = q.poll();
for(int[] par : getParent(cur,graph)) {
if(dp[par[0]][par[1]][par[2]] != DRAW) continue;
if(par[2] == cur[3]){
dp[par[0]][par[1]][par[2]] = cur[3];
q.offer(new int[]{par[0],par[1],par[2],cur[3]});
}else{
//degree[par[0]][par[1]][par[2]]--;
if(--degree[par[0]][par[1]][par[2]] == 0) {
dp[par[0]][par[1]][par[2]] = 3 - par[2];
q.offer(new int[]{par[0],par[1],par[2],3 - par[2]});
}
}
}
}
return dp[1][2][1];
}
private List<int[]> getParent(int[] cur,int[][] graph) {
List<int[]> res = new ArrayList<>();
if(cur[2] == MOUSE){
for(int j : graph[cur[1]]) {
if(j == 0) continue;
res.add(new int[]{cur[0],j,CAT});
}//let cat go then to mouse go
}else{
for(int j : graph[cur[0]]) {
res.add(new int[]{j,cur[1],MOUSE});
}
}
return res;
}
