壓哨做完4道首懈。
總結(jié)下思路吧暇唾。
925. Long Pressed Name
https://leetcode.com/problems/long-pressed-name/description/
這道題很快就秒了进统。一開(kāi)始字符一定要一樣乖寒。隨后如果出現(xiàn)不一樣，我們就看是不是長(zhǎng)按造成的蓬网，一直去掉重復(fù)字符窒所。重復(fù)字符都去完了，應(yīng)該一樣了帆锋，如果還不一樣就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/
這道題是一維數(shù)組加狀態(tài)機(jī)的動(dòng)態(tài)規(guī)劃。
我們假定DP J窟坐，是到J位符合遞增的序列. 那么根據(jù)J位是0或1海渊，我們會(huì)有2個(gè)狀態(tài)。
如果J位是0哲鸳，我們只能從J-1位是0得過(guò)來(lái)臣疑。同時(shí)如果這個(gè)是字符串的第J個(gè)和最后的狀態(tài)要求不同，需要翻成對(duì)應(yīng)字符而需要+1徙菠。
如果J位是1讯沈，我們可以從J-1位是0 或者J-1位是1得過(guò)來(lái)。同時(shí)如果這個(gè)是字符串的第J個(gè)和最后的狀態(tài)要求不同婿奔，需要翻成對(duì)應(yīng)字符而需要+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
這道題思考過(guò)程是這樣问慎，看了數(shù)據(jù)規(guī)模得出 解的時(shí)間復(fù)雜度應(yīng)該是ON，那么暴力解法肯定不行挤茄。
O N + 分成3段如叼，就想到2個(gè)指針。那么2個(gè)指針就很容易想到雙向指針穷劈。
那么我就把第一個(gè)指針?lè)旁陬^部笼恰，后一個(gè)指針?lè)旁谖膊浚_(kāi)始找能不能指針只會(huì)往中間走而不回退的方法歇终。
我發(fā)現(xiàn)社证，如果一開(kāi)始頭尾指針構(gòu)成的二進(jìn)制數(shù)，如果是一樣的评凝。那么只要中間的部分和他們也是一樣的就找到答案了追葡。
如果不一樣，分為2個(gè)情況
如果前面的 比 后面的 小
可以通過(guò)右移左指針而起到增大前面的本事奕短。因?yàn)?個(gè)區(qū)間要相等宜肉。我們最開(kāi)始已經(jīng)貪心的把前后都?jí)嚎s到最小，所以要補(bǔ)救勢(shì)必是通過(guò)增大的方式篡诽。
如果后面比前面小崖飘。我們肯定要通過(guò)左移右指針去把中間的元素拿到右面榴捡，來(lái)增大右面杈女。道理同上
如果配平了左右2面，此時(shí)一定是前綴和后綴長(zhǎng)度最小的配平吊圾。根據(jù)貪心的思想达椰。
我們就看這個(gè)最小的配平下，中間是不是也能配平项乒。配平就找到解了啰劲。
如果中間的比右面的大，我們可以通過(guò)左移右指針檀何，來(lái)試圖讓中間的區(qū)間減少蝇裤。當(dāng)然右移左指針也是可以的。為什么要選擇左移右指針呢频鉴？
通過(guò)觀察栓辜，右移左指針必然會(huì)使得前半部分增大。而左移右指針垛孔，可能因?yàn)槭?藕甩，加了前綴0等于沒(méi)加。而依然保持左半和右半配平周荐。
如果中間的區(qū)間的值比右面的小狭莱，肯定無(wú)解了僵娃。因?yàn)槲覀円呀?jīng)為了配平左右而用了最小的長(zhǎng)度。一旦要去從左右拿出元素腋妙，肯定就無(wú)法配平左右了默怨。
分析到這里，思路就有了辉阶。
落實(shí)到代碼先壕，我決定用DQ，因?yàn)榉奖?頭進(jìn)出谆甜。
同時(shí)為了在做DQ compare的時(shí)候垃僚，加速。
我決定忽略所有前綴0规辱，這增加了編碼難度谆棺，但是加快了時(shí)間。
所有忽略前綴0的DQ罕袋，在比較的時(shí)候改淑，
如果長(zhǎng)度不同，可以直接比出大小浴讯。
如果長(zhǎng)度相同朵夏，就依次遍歷每一個(gè)值，如果全相同就同榆纽，如果一旦不同仰猖，直接比較這2個(gè)不同的值。
為了達(dá)到上述效果奈籽，我在發(fā)現(xiàn)每個(gè)DQ的前綴是0的情況下饥侵，就不插進(jìn)去了。只有1做前綴的時(shí)候再插進(jìn)去衣屏，同時(shí)需要補(bǔ)之前沒(méi)插的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
最后這道題的思考過(guò)程躏升，需要從上周比賽Minimize Malware Spread來(lái)。
區(qū)別就在于抹掉一個(gè)點(diǎn)狼忱，就抹掉了所有的連邊膨疏。
1連2,2連3. 病毒有1,2. 直接這個(gè)局面是沒(méi)救的。但是再這道題里钻弄，通過(guò)抹掉JOINT POINT 2佃却，就能盤(pán)活局面。
但是并查集不是很好處理斷開(kāi)的情況斧蜕。
那我就想既然如果双霍，我索引遍歷所有的病毒，依次抹掉這個(gè)病毒的情況下，重新生成一個(gè)圖洒闸，然后算INFECTS的點(diǎn)的數(shù)量染坯。
隨后取最小值就可以了。
那么構(gòu)成圖的時(shí)候丘逸，其實(shí)就是在UNION单鹿，發(fā)現(xiàn)有一個(gè)點(diǎn)是抹除的病毒點(diǎn)，就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;
}
