照例比赛总结。
第一题
922. Sort Array By Parity II
https://leetcode.com/contest/weekly-contest-106/problems/sort-array-by-parity-ii/
这道题就是维护好奇偶索引，然后用一个指针去遍历原数组。
O n 空间代码比较好写。
public int[] sortArrayByParityII(int[] A) {
int i = 0, j = 1;
int l = A.length;
int[] B = new int[l];
for(int k = 0; k < A.length; k++){
if(A[k]%2 == 0){
B[i] = A[k];
i+=2;
}else{
B[j] = A[k];
j+=2;
}
}
return B;
}
可以用O1 的空间。
public int[] sortArrayByParityII(int[] A) {
int i = 0, j = 1, k = 0;
int l = A.length;
while(k < A.length && (i < A.length || j < A.length)){
if(A[k]%2 == k%2){
if(k==j) j+=2;
else if(k==i) i+=2;
k++;
}else{
int tmp = A[k];
if(A[k]%2==1){
A[k] = A[j];
A[j] = tmp;
j+=2;
}else{
A[k] = A[i];
A[i] = tmp;
i+=2;
}
}
}
return A;
}
921. Minimum Add to Make Parentheses Valid
https://leetcode.com/contest/weekly-contest-106/problems/minimum-add-to-make-parentheses-valid/
这道题我们要分别记录左括号不符合的数量，加上右括号不符合的数量。
右括号不符合的数量，是当左括号没得用了，那么每多一个右括号都要删除。如右括号在最前面的时候）））
或者（）））
左括号不符合的数量，就是在最后多出来没用完的左括号。
（）（（
public int minAddToMakeValid(String S) {
char[] cs = S.toCharArray();
int cnt = 0;
int need = 0;
for(char c : cs){
if(c == '('){
cnt++;
}else if(c == ')'){
if(cnt > 0) cnt--;
else need++;
}
}
return need+cnt;
}
923. 3Sum With Multiplicity
https://leetcode.com/contest/weekly-contest-106/problems/3sum-with-multiplicity/
这道题是3SUM的变种，
首先3SUM 是 N^2 的时间复杂度。我们看一些数据规模，大概是N^2 可以过的。
但是和3SUM不同的是，这个要求出所有解的数量，而在原3SUM中，只要找到一个合法解就可以退出。
然后我依照3SUM的做法，做到后面发现，一旦出现了重复，原来N^2的算法会遇到一个问题。
比如确定了3元祖的第一个数，用TAR-第一个数，我们只要在剩余数组里，求2SUM。然而排好序的2SUM 是ON的。用HASHMAP的2SUM 也是ON，不要求排序。但是要额外空间。
所以这边可以走2个分支。
第一个分支，排序的，设定头尾指针，为了计算所有的解空间。匹配到了还不能停，但是因为有重复的，如果匹配到了，如1,1,2,2. 无论此时移动头指针，还是尾指针，都会漏解。所以要用排序来求，我们必须要求DISTINT VALUE。
所以产生了以下解法。
随后发现，结果集可能是来自3个不同的元素，也可以是来自2个相同，一个不同，也可以是3个都相同。后2种情况，只要用一点组合的计算技巧，可以在NLOGN 和 LOGN 求出。所以时间还是N^2
public int threeSumMulti(int[] A, int target) {
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int i : A) map.put(i,map.getOrDefault(i,0)+1);
int[] key = new int[map.size()];
int[] val = new int[map.size()];
int idx = 0;
int M = 1000000007;
//make key distinct
for(Map.Entry<Integer,Integer> e : map.entrySet()){
key[idx] = e.getKey();
val[idx++] = e.getValue();
}
int l = key.length;
//cnt 3 different solution
long cnt = 0;
for(int i = 0; i < l-2; i++){
int tar = target-key[i];
int s = i+1, e = l-1;
while(s < e) {
int cur = key[s]+key[e];
if(cur > tar) e--;
else if(cur < tar) s++;
else{
cnt = (cnt+val[i]*val[s]*val[e])%M;
s++;
e--;
}
}
}
//cnt 2 different solution
for(int i = 0; i < l; i++){
if(val[i]<=1) continue;
int tar = target-2*key[i];
int ii = Arrays.binarySearch(key,tar);
if(ii < 0 || ii == i) continue;
cnt += val[ii]*(val[i]*(val[i]-1)/2);
cnt %= M;
}
//cnt 1 different solution
if(target % 3 == 0){
int ii = Arrays.binarySearch(key,target/3);
if(ii < 0) return (int)cnt;
cnt += (((long)val[ii]*(val[ii]-1))%M)*(val[ii]-2)/6;
cnt %= M;
}
return (int)cnt;
}
用hashMap 的解法。
public int threeSumMulti(int[] A, int target) {
int l = A.length;
long cnt = 0;
int M = 1000000007;
for(int i = 0; i < l-2; i++){
//2sum to tar
int tar = target - A[i];
Map<Integer,Integer> m = new HashMap<>();
for(int j = i+1; j < l; j++){
cnt = (cnt + m.getOrDefault(tar-A[j],0))%M;
m.put(A[j],m.getOrDefault(A[j],0)+1);
}
}
return (int)cnt;
}
924. Minimize Malware Spread
https://leetcode.com/contest/weekly-contest-106/problems/minimize-malware-spread/
最后一道题的思考过程如下：
因为是无向图，所以只要用并查集就可以找到所有的连通集合。每个连通集合只要有一个数在污染点里，那么整个集合就会被污染。
我们有一次丢掉一个污染点的机会。如果这个点用在原集合上，该集合还有另一个污染点。其实丢这个污染点是没作用的。
所以我们需要丢，只有一个污染点的集合，并且这个集合的CNT，也就是包含的点数是最大的。如果一样大，取小的那个污染点。
那么按照这个思路基本就可以写代码了。
1.先写并查集
2.初始化相应的PARENT数组 和 CNT数组
3.根据GRAPH 做UNION
4.统计每个污染点的集合里的污染点的个数,然后遍历那些个数为1的污染点的集合
5.从那些污染点为1里面的集合，找到CNT最大的，输出那个污染点的下标
6。如果没有1的，就是丢掉任何一个点，都不会改变情况。只要输出原污染点坐标最小的即可。
int[] par;
int[] cnt;
int find(int i){
if(i == par[i]) return i;
return par[i] = find(par[i]);
}
boolean union(int i,int j){
int pi = find(i);
int pj = find(j);
if(pi == pj) return false;
par[pi] = pj;
cnt[pj] += cnt[pi];
return true;
}
public int minMalwareSpread(int[][] graph, int[] initial) {
int l = graph.length;
par = new int[l];
cnt = new int[l];
Arrays.fill(cnt,1);
for(int i = 0; i < l; i++) par[i] = i;
for(int i = l-2; i >= 0; i--){
for(int j = i+1; j < l; j++){
if(graph[i][j] == 0) continue;
union(i,j);
}
}
int[] map = new int[l];
int[] chd = new int[l];
Arrays.fill(chd,Integer.MAX_VALUE);
for(int i : initial){
int pi = find(i);
chd[pi] = Math.min(i,chd[pi]);
map[pi]++;
}
int max = 0;
Arrays.sort(initial);
int res = initial[0];
for(int pi = 0; pi < l; pi++){
if(map[pi] == 1){
if(cnt[pi]>max){
max = cnt[pi];
res = chd[pi];
}
}
}
return res;
}
