压哨做完4道。
总结下思路吧。
925. Long Pressed Name
https://leetcode.com/problems/long-pressed-name/description/
这道题很快就秒了。一开始字符一定要一样。随后如果出现不一样，我们就看是不是长按造成的，一直去掉重复字符。重复字符都去完了，应该一样了，如果还不一样就FALSE。
public boolean isLongPressedName(String name, String typed) {
if(name.equals(typed)) return true;
char[] ns = name.toCharArray();
char[] ts = typed.toCharArray();
int j = 0;
for(int i = 0; i < ns.length; ) {
if(j == ts.length) return false;
if(ns[i] != ts[j]) return false;
else{
j++;
i++;
if(i == ns.length){
while(j < ts.length && ts[j] == ts[j-1]) j++;
return j == ts.length;
}
while(j < ts.length && ts[j] != ns[i] && ts[j] == ts[j-1]) j++;
}
}
return true;
}
926. Flip String to Monotone Increasing
https://leetcode.com/problems/flip-string-to-monotone-increasing/description/
这道题是一维数组加状态机的动态规划。
我们假定DP J，是到J位符合递增的序列. 那么根据J位是0或1，我们会有2个状态。
如果J位是0，我们只能从J-1位是0得过来。同时如果这个是字符串的第J个和最后的状态要求不同，需要翻成对应字符而需要+1。
如果J位是1，我们可以从J-1位是0 或者J-1位是1得过来。同时如果这个是字符串的第J个和最后的状态要求不同，需要翻成对应字符而需要+1。
public int minFlipsMonoIncr(String S) {
char[] A = S.toCharArray();
int n = A.length;
int[] one = new int[n + 1];
int[] zero = new int[n + 1];
zero[0] = one[0] = 0;
int i;
for (i = 1; i <= n; i++) {
one[i] = A[i - 1] == '1' ? Math.min(one[i - 1], zero[i - 1]) :
Math.min(one[i - 1], zero[i - 1]) + 1;
zero[i] = A[i - 1] == '0' ? zero[i - 1] : zero[i - 1] + 1;
}
return Math.min(zero[n], one[n]);
}
927. Three Equal Parts
这道题思考过程是这样，看了数据规模得出 解的时间复杂度应该是ON，那么暴力解法肯定不行。
O N + 分成3段，就想到2个指针。那么2个指针就很容易想到双向指针。
那么我就把第一个指针放在头部，后一个指针放在尾部，开始找能不能指针只会往中间走而不回退的方法。
我发现，如果一开始头尾指针构成的二进制数，如果是一样的。那么只要中间的部分和他们也是一样的就找到答案了。
如果不一样，分为2个情况
如果前面的 比 后面的 小
可以通过右移左指针而起到增大前面的本事。因为3个区间要相等。我们最开始已经贪心的把前后都压缩到最小，所以要补救势必是通过增大的方式。
如果后面比前面小。我们肯定要通过左移右指针去把中间的元素拿到右面，来增大右面。道理同上
如果配平了左右2面，此时一定是前缀和后缀长度最小的配平。根据贪心的思想。
我们就看这个最小的配平下，中间是不是也能配平。配平就找到解了。
如果中间的比右面的大，我们可以通过左移右指针，来试图让中间的区间减少。当然右移左指针也是可以的。为什么要选择左移右指针呢？
通过观察，右移左指针必然会使得前半部分增大。而左移右指针，可能因为是0，加了前缀0等于没加。而依然保持左半和右半配平。
如果中间的区间的值比右面的小，肯定无解了。因为我们已经为了配平左右而用了最小的长度。一旦要去从左右拿出元素，肯定就无法配平左右了。
分析到这里，思路就有了。
落实到代码，我决定用DQ，因为方便2头进出。
同时为了在做DQ compare的时候，加速。
我决定忽略所有前缀0，这增加了编码难度，但是加快了时间。
所有忽略前缀0的DQ，在比较的时候，
如果长度不同，可以直接比出大小。
如果长度相同，就依次遍历每一个值，如果全相同就同，如果一旦不同，直接比较这2个不同的值。
为了达到上述效果，我在发现每个DQ的前缀是0的情况下，就不插进去了。只有1做前缀的时候再插进去，同时需要补之前没插的0.
public int[] threeEqualParts(int[] A) {
int i = 0, j = A.length-1;
Deque<Integer> pre = new ArrayDeque<>();
Deque<Integer> mid = new ArrayDeque<>();
Deque<Integer> last = new ArrayDeque<>();
if(A[0]!=0) pre.offerLast(1);
if(A[j]!=0) last.offerLast(1);
for(int k = 1; k < j; k++){
if(mid.isEmpty() && A[k] == 0) continue;
mid.offerLast(A[k]);
}
while(i < j){
int cp = compare(pre,last);
if(cp<0){
i++;
if(A[i] == 0){
if(!pre.isEmpty()) pre.offerLast(0);
}
else{
if(mid.isEmpty()) break;
pre.offerLast(mid.pollFirst());
while(!mid.isEmpty() && mid.peekFirst()==0) mid.pollFirst();
}
}else if(cp>0){
j--;
if(mid.isEmpty()) break;
if(A[j] == 0) mid.pollLast();
else moveMidToLast(A,mid,last,j);
}else{
int cp2 = compare(mid,last);
if(cp2 == 0) return new int[]{i,j};
if(cp2<0) break;
else{
j--;
if(mid.isEmpty()) break;
if(A[j] == 0) mid.pollLast();
else moveMidToLast(A,mid,last,j);
}
}
}
return new int[]{-1,-1};
}
private void moveMidToLast(int[] A,Deque<Integer> mid,Deque<Integer> last,int j){
int idx = j+1;
while(idx<A.length && A[idx++]==0)
last.offerFirst(0);
last.offerFirst(mid.pollLast());
}
private int compare(Deque<Integer> a, Deque<Integer> b){
if(a.size() < b.size()) return -1;
if(a.size() == b.size()){
Iterator<Integer> itr = a.iterator();
Iterator<Integer> itr2 = b.iterator();
while(itr.hasNext()){
int fa = itr.next();
int fb = itr2.next();
if(fa == fb) continue;
return fa-fb;
}
return 0;
}
return 1;
}
928. Minimize Malware Spread II
最后这道题的思考过程，需要从上周比赛Minimize Malware Spread来。
区别就在于抹掉一个点，就抹掉了所有的连边。
1连2,2连3. 病毒有1,2. 直接这个局面是没救的。但是再这道题里，通过抹掉JOINT POINT 2，就能盘活局面。
但是并查集不是很好处理断开的情况。
那我就想既然如果，我索引遍历所有的病毒，依次抹掉这个病毒的情况下，重新生成一个图，然后算INFECTS的点的数量。
随后取最小值就可以了。
那么构成图的时候，其实就是在UNION，发现有一个点是抹除的病毒点，就CONTINUE就好。
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) {
Arrays.sort(initial);
int res = initial[0];
int min = Integer.MAX_VALUE;
for(int i = 0; i < initial.length; i++){
int tmp = initial[i];
initial[i] = -1;
int infects = minMalwareSpread2(graph,initial,tmp);
if(infects < min){
min = infects;
res = tmp;
}
initial[i] = tmp;
}
return res;
}
public int minMalwareSpread2(int[][] graph, int[] initial,int tar) {
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 || i==tar || j==tar) continue;
union(i,j);
}
}
int infects = 0;
boolean[] seen = new boolean[l];
for(int i : initial){
if(i == -1) continue;
int pi = find(i);
if(seen[pi]) continue;
seen[pi] = true;
infects += cnt[pi];
}
return infects;
}
