2月份最后一周的刷題筆記（ps：以后每一篇都會記錄一個日期，恐怕自己哪周沒堅持住或者忘記了）。

金字塔轉(zhuǎn)換矩陣

題目：現(xiàn)在，我們用一些方塊來堆砌一個金字塔。 每個方塊用僅包含一個字母的字符串表示。使用三元組表示金字塔的堆砌規(guī)則如下：

對于三元組(A, B, C) ，“C”為頂層方塊，方塊“A”、“B”分別作為方塊“C”下一層的的左、右子塊。當(dāng)且僅當(dāng)(A, B, C)是被允許的三元組，我們才可以將其堆砌上。初始時，給定金字塔的基層 bottom，用一個字符串表示。一個允許的三元組列表 allowed，每個三元組用一個長度為 3 的字符串表示。如果可以由基層一直堆到塔尖就返回 true ，否則返回 false 。

示例 1：
輸入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
輸出：true
解析：
可以堆砌成這樣的金字塔:
A
/
G E
/ \ /
B C D
因?yàn)榉?'B', 'C', 'G'), ('C', 'D', 'E') 和 ('G', 'E', 'A') 三種規(guī)則。
示例 2：
輸入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
輸出：false
解析：
無法一直堆到塔尖。
注意, 允許存在像 (A, B, C) 和 (A, B, D) 這樣的三元組，其中 C != D。
提示：
bottom 的長度范圍在 [2, 8]。
allowed 的長度范圍在[0, 200]。
方塊的標(biāo)記字母范圍為{'A', 'B', 'C', 'D', 'E', 'F', 'G'}。

思路：這個題怎么說呢，暫時的思路就是首先把最后一層的底湊出來。比如第一個塔型的BCD,湊出來以后倒數(shù)第二層其實(shí)可能就有多個選擇了，因?yàn)榭赡芙M成最后一層的可能性很多。然后我們把第二層的所有可能都要跑，直到某一種方式可以直達(dá)塔頂或者所有的路都不行那么就false，總而言之這是一個dfs，也就是深度優(yōu)先搜索。我去實(shí)現(xiàn)下試試了。
貼上第一版代碼：

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, ArrayList<Character>> map = new HashMap<>();
        for (String s : allowed) {
            String key = s.substring(0, 2);
            char v = s.charAt(2);
            ArrayList<Character> list = map.get(key);
            if (list == null) {
                list = new ArrayList<>();
                list.add(v);
                map.put(key, list);
            } else {
                list.add(v);
            }
        }
        return dfs(map,bottom,"");
    }

    public boolean dfs(Map<String, ArrayList<Character>> map, String bottom, String temp) {
        if (bottom.length() == 1) return true;
        //當(dāng)前這層壘好了，繼續(xù)往上
        if (bottom.length() == temp.length() + 1) return dfs(map, temp, "");
        String cur = bottom.substring(temp.length(), temp.length() + 2);
        ArrayList<Character> list = map.get(cur);
        //到這里往下走不下去了，所以直接false
        if (list == null || list.size() == 0) return false;
        for (Character c : list) {
            //任何一種可能成功，都可以
            if (dfs(map, bottom, temp + c)) return true;
        }
        return false;
    }
}

隨著做隨著發(fā)現(xiàn)這個題不簡單啊，一開始我我尋思用字符串的startWith來判斷上一層，但是這樣會不會重復(fù)，是不是要一次次遍歷之類的就很復(fù)雜， 所以最后決定用hash表的方式來做。
把左右兩基層作為key，因?yàn)榇嬖贏,B,C, 和A,B,D這種三元組，所以value用字符的list 來存儲。這樣A,B,C和A,B,D的存儲是key 是AB，value是：[C,D]。
然后在一層一層往上加的時候只要判斷當(dāng)前兩個基層能不能組成三元組，能的話頂層是什么，并分別往下走就行了。

其實(shí)這個也算是一個標(biāo)準(zhǔn)的回溯題目了，只不過因?yàn)橄乱粚邮侵苯蛹拥絫emp上所以不用退回上一步。
有點(diǎn)類似與我之前說的迷宮，每個房間7個門的demo。（這篇筆記是單獨(dú)說DFS和BFS的，感興趣可以去看一下：http://www.itdecent.cn/p/fbe0d05187a5）
然后反正現(xiàn)在是實(shí)現(xiàn)了，這個題我覺得挺不容易一下子想到的，但是慢慢琢磨也不是很難，而且這個題有一個很坑的點(diǎn)是三元組可重用。這個我也不知道為什么這么設(shè)置，反正默認(rèn)就是這樣，所以在做的時候踩了不少坑，一開始把這個題想復(fù)雜了，用過的三元組還要刪除，所以費(fèi)事還報錯。
接下來我去看看性能第一的代碼：

class Solution {
    int[][] T;

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        T = new int[7][7];
        for (String a : allowed)
            T[a.charAt(0) - 'A'][a.charAt(1) - 'A'] |= 1 << (a.charAt(2) - 'A');

        int N = bottom.length();
        int[][] A = new int[N][N];
        int t = 0;
        for (char c : bottom.toCharArray())
            A[N - 1][t++] = c - 'A';
        return solve(A, N - 1, 0);
    }

    public boolean solve(int[][] A, int N, int i) {
        if (N == 1 && i == 1) {
            return true;
        } else if (i == N) {
            return solve(A, N - 1, 0);
        } else {

            int w = T[A[N][i]][A[N][i + 1]];
            for (int b = 0; b < 7; ++b)
                if (((w >> b) & 1) != 0) {
                    A[N - 1][i] = b;
                    if (solve(A, N, i + 1))
                        return true;
                }
            return false;
        }
    }
}

真的是驚為天人！首先用數(shù)組型數(shù)組表示這個hash表的key，也就是橫縱坐標(biāo)定位了具體的基層兩個值。然后用二進(jìn)制表示list。因?yàn)樽疃噙@一個上層就'A', 'B', 'C', 'D', 'E', 'F', 'G'這七個可能，所以七個二進(jìn)制就能表示這個了。比如 1001000.就是說這個橫縱坐標(biāo)的基層頂層有兩種可能：G和D。
1110111就是橫縱坐標(biāo)有6種可能：A,B,C ,E,F,G
然后一個49個值的二維數(shù)組要遠(yuǎn)比hash表的性能好的多。
同理可以湊出來的底層（除了最底層是指定剩下其實(shí)都有多種可能）可以二維數(shù)組表示，值為0就說明當(dāng)前沒這個選擇。值不是0說明當(dāng)前選擇是可以的。
反正這個代碼精巧在把hash轉(zhuǎn)為二維數(shù)組，剩下的dfs也就那樣。。其實(shí)這種數(shù)組多維表示不同意義的方法我是早早就知道的，可惜這個題沒想到這點(diǎn)。哎，還是練得不夠，下一題了。

劃分字母區(qū)間

題目：字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個片段中。返回一個表示每個字符串片段的長度的列表。

示例：
輸入：S = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結(jié)果為 "ababcbaca", "defegde", "hijhklij"。
每個字母最多出現(xiàn)在一個片段中。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因?yàn)閯澐值钠螖?shù)較少。
提示：
S的長度在[1, 500]之間。
S只包含小寫字母 'a' 到 'z' 。

思路：這個題感覺沒啥難度啊，我暫時的想法是獲取每一個字母的第一個出現(xiàn)位置和最后一個出現(xiàn)位置。每一個字母構(gòu)成一條線。先從第一個字母開始這條件中間的元素都往外擴(kuò)散，直到所有的元素都擴(kuò)散完了。這個區(qū)域就是第一個區(qū)域，如果后面還有空間那么再逐一去判斷。
!!!居然一次就過了， 這個題目的難度果然不科學(xué)，我先貼代碼：

class Solution {
    List<Integer> ans = new ArrayList<Integer>();
    public List<Integer> partitionLabels(String S) {        
        char c = S.charAt(0);
        int start = 0;
        int end = 0;
        for(int i = 0;i<=end;i++) {
            end = Math.max(S.lastIndexOf(S.charAt(i)),end);
            if(end == S.length()-1) {
                ans.add(end-start+1);
                return ans;
            }
        }
        ans.add(end-start+1);
        return partitionLabels(S.substring(end+1));
    }
}

思路和我之前想的差不多，只不過我這個代碼的性能有點(diǎn)問題。我覺得出現(xiàn)的原因應(yīng)該是我來回來去重復(fù)判斷，我應(yīng)該直接遍歷每個字母獲取其起始出現(xiàn)的元素，我去優(yōu)化下。
換了中寫法， 性能上來了，雖然還不是最好：

class Solution {
    public List<Integer> partitionLabels(String S) {  
        List<Integer> ans = new ArrayList<Integer>();
        //第一個元素是第一次出現(xiàn)的，第二個元素是最后一次出現(xiàn)的
        int[][] d = new int[26][2];
        for(int i = 0;i<d.length;i++) {
            char c = (char) (i+97);
            d[i] = new int[] {S.indexOf(c),S.lastIndexOf(c)};
        }
        Arrays.sort(d, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        for(int i = 0;i<d.length;i++) {
            int start = d[i][0];
            int end = d[i][1];
            if(start == -1) continue;//這個已經(jīng)是別的圈子里的了，不用浪費(fèi)時間
            d[i][0] = -1;//這個人已經(jīng)開圈了，所以標(biāo)記下
            for(int j = i+1;j<d.length;j++) {
                if((d[j][0]>start && d[j][0]<end)
                        ||(d[j][1]>start && d[j][1]<end)
                        ||(d[j][0]<start && d[j][1]>end)) {
                    start = Math.min(d[j][0], start);
                    end = Math.max(d[j][1], end);
                    d[j][0] = -1;
                }else{
                    break;//因?yàn)槭前雌鹗嘉恢门判虻?，所以這個不行，以后的都不行了
                }
            }
            ans.add(end-start+1);
        }
        return ans;     
    }
}

我覺得還能繼續(xù)優(yōu)化，哈哈，我去試試：

class Solution {
    List<Integer> ans = new ArrayList<Integer>();   
    public List<Integer> partitionLabels(String S) {  
        if(S.length() == 0) return ans;
        Set<Character> set = new HashSet<Character>(); 
        int start = 0;
        int end = 0;
        for(int i = 0;i<=end;i++) {
            char c = S.charAt(i);
            if(set.contains(c)) continue;
            set.add(c);
            end = Math.max(end, S.lastIndexOf(c));
        }
        ans.add(end-start+1);       
        return partitionLabels(S.substring(end+1));
    }
}

終于優(yōu)化到最佳性能了，嘿嘿，這個題其實(shí)實(shí)現(xiàn)比較簡單，從小寫a到z很容易想到數(shù)組下標(biāo)代替值。從數(shù)據(jù)范圍只有500可以讓我們有機(jī)會暴力ac。重點(diǎn)應(yīng)該是在優(yōu)化上吧：首先第一版代碼我的思路沒問題，只不每一個元素都要獲取最后一次出現(xiàn)，期間有很多重復(fù)判斷，所以性能才慘不忍睹。其實(shí)只要加個記憶的set，如果判斷過了不重復(fù)判斷就好多了。
但是我當(dāng)時思路有點(diǎn)歪，所以用類似并查的模式標(biāo)記+擴(kuò)散，找出一個個圈子了。不過性能也還行，起碼是多種思路。下一題了。

猜字謎

題目：外國友人仿照中國字謎設(shè)計了一個英文版猜字謎小游戲，請你來猜猜看吧。字謎的迷面 puzzle 按字符串形式給出，如果一個單詞 word 符合下面兩個條件，那么它就可以算作謎底：

單詞 word 中包含謎面 puzzle 的第一個字母。

單詞 word 中的每一個字母都可以在謎面 puzzle 中找到。

例如，如果字謎的謎面是 "abcdefg"，那么可以作為謎底的單詞有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 沒有出現(xiàn)在謎面中）。

返回一個答案數(shù)組 answer，數(shù)組中的每個元素 answer[i] 是在給出的單詞列表 words 中可以作為字謎迷面 puzzles[i] 所對應(yīng)的謎底的單詞數(shù)目。

示例：
輸入：
words = ["aaaa","asas","able","ability","actt","actor","access"],
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
輸出：[1,1,3,2,4,0]
解釋：
1 個單詞可以作為 "aboveyz" 的謎底 : "aaaa"
1 個單詞可以作為 "abrodyz" 的謎底 : "aaaa"
3 個單詞可以作為 "abslute" 的謎底 : "aaaa", "asas", "able"
2 個單詞可以作為 "absoryz" 的謎底 : "aaaa", "asas"
4 個單詞可以作為 "actresz" 的謎底 : "aaaa", "asas", "actt", "access"
沒有單詞可以作為 "gaswxyz" 的謎底，因?yàn)榱斜碇械膯卧~都不含字母 'g'。
提示：
1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] 都是小寫英文字母。
每個 puzzles[i] 所包含的字符都不重復(fù)。

思路：2021/2/26的每日一題，雖然是困難難度，但是讀完題就覺得思如泉涌。我感覺這個題能卡的也就是性能了。因?yàn)橹i底的個數(shù)是100000，謎面?zhèn)€數(shù)10000，如果單純的去一對一的比對絕對是要超時。而首字母是比含的單詞。上面的題目是數(shù)組下標(biāo)代表值還是挺有用的。我目前覺得字典應(yīng)該是一個挺好的選擇。每一個謎底或者謎面用二進(jìn)制數(shù)字表示。比如aaaa不管出現(xiàn)幾次a，我們只要知道出現(xiàn)a了就可以。大概就是這樣的思路。還有謎底長度只有7，所以說如果謎面超過7的直接pass。
第一版代碼：

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        //字符串轉(zhuǎn)成二進(jìn)制方便計算。而且字母最多26個。
        Map<Integer, Integer>  map = new HashMap<>();
        for(String word : words){
            int key = 0;
            for (char ch : word.toCharArray()) key |= 1 << ch - 'a';
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        List<Integer> ans = new ArrayList<>();
        for(String s : puzzles){
             int n = 0;
             char[] c = s.toCharArray();
             //key是必選的，其余的不用
             ans.add(dfs(map, c, 1, 1 << c[0] - 'a'));
        }
        return ans;
    }
    public int dfs(Map<Integer, Integer> map, char[] puzzle, int idx, int key) {
        if (idx == puzzle.length) return map.getOrDefault(key, 0);
        // 之所以的兩種情況是因?yàn)槌耸鬃帜钙溆嗟挠袥]有都可以！
        return dfs(map,puzzle, idx + 1,  key) + dfs(map, puzzle, idx + 1, key | 1 << puzzle[idx] - 'a');
    }
}

我果然是個渣渣，這個代碼是看了別人的題解最終實(shí)現(xiàn)的。其實(shí)大體思路我是知道的，也想到了二進(jìn)制，就是不會具體怎么運(yùn)算，一直鉆牛角尖以為能直接用位運(yùn)算。。卻不想人家用的位移一個個比較。。。說實(shí)話就key | 1 << puzzle[idx] - 'a'這句代碼我自己是想不到的。總體而言這個題的思路總結(jié)一下：
首先一個個字符串比較肯定超時而且沒必要。
因?yàn)橹i面可能會很長，但是本質(zhì)上出現(xiàn)的字母不會超過三個，所以這里用字母的排序（a是0，z是25）來代表數(shù)值，最終實(shí)現(xiàn)把每一個謎面包含的字母都用數(shù)字的形式存起來（好像聽說過這個是狀態(tài)壓縮），然后重點(diǎn)就來：其實(shí)一個謎面最多包含7個字符，所以不管謎面什么形式，肯定有重復(fù)的，比如aaabbb,ab,aaab,abbb這些本質(zhì)上都是一樣的。所以我們用hash表根據(jù)謎面字母不同計數(shù)。比如上文中的就可以這么存：ab:4.而上文我也說了為了性能，所以這里我們也不存ab了，而是把a(bǔ)b轉(zhuǎn)化成一個數(shù)字來存儲。就這樣我們根據(jù)出現(xiàn)的字符的不同把謎面都分別存儲好。
接下來遍歷謎底：因?yàn)橹i底一定是七個字符。除了首字母是必須存在的，其余都可有可無，所以我們可以將謎面拆開：首字母是必須的，任何首字母+隨意其他六個元素的組合都滿足要求，所以這里用遞歸的方式實(shí)現(xiàn)。因?yàn)槌耸鬃帜钙溆嗟亩伎捎锌蔁o，所以我們可以理解為除了首字母其余的都分兩種情況：有/無。所以遞歸中是兩種情況的結(jié)果的和。
這個題到這里就解出來了。
其實(shí)我覺得這個題考點(diǎn)有幾個：一個是字符串轉(zhuǎn)數(shù)字存儲（不這樣會超時）。一個是hash，還有一個是就是把所有謎底對應(yīng)謎面的可能性都列出來。大概就是這樣吧，這個題我做好難，我還是滾去刷中等題目吧。下一題了。

最大加號標(biāo)志

題目：在一個大小在 (0, 0) 到 (N-1, N-1) 的2D網(wǎng)格 grid 中，除了在 mines 中給出的單元為 0，其他每個單元都是 1。網(wǎng)格中包含 1 的最大的軸對齊加號標(biāo)志是多少階？返回加號標(biāo)志的階數(shù)。如果未找到加號標(biāo)志，則返回 0。

一個 k" 階由 1 組成的“軸對稱”加號標(biāo)志具有中心網(wǎng)格 grid[x][y] = 1 ，以及4個從中心向上、向下、向左、向右延伸，長度為 k-1，由 1 組成的臂。下面給出 k" 階“軸對稱”加號標(biāo)志的示例。注意，只有加號標(biāo)志的所有網(wǎng)格要求為 1，別的網(wǎng)格可能為 0 也可能為 1。

k 階軸對稱加號標(biāo)志示例:
階 1:
000
010
000
階 2:
00000
00100
01110
00100
00000
階 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

示例 1：
輸入: N = 5, mines = [[4, 2]]
輸出: 2
解釋:
11111
11111
11111
11111
11011
在上面的網(wǎng)格中，最大加號標(biāo)志的階只能是2。一個標(biāo)志已在圖中標(biāo)出。
示例 2：
輸入: N = 2, mines = []
輸出: 1
解釋:
11

11
沒有 2 階加號標(biāo)志，有 1 階加號標(biāo)志。
示例 3：
輸入: N = 1, mines = [[0, 0]]
輸出: 0
解釋:

0
沒有加號標(biāo)志，返回 0 。
提示：
整數(shù)N 的范圍： [1, 500].
mines 的最大長度為 5000.
mines[i] 是長度為2的由2個 [0, N-1] 中的數(shù)組成.
(另外,使用 C, C++, 或者 C# 編程將以稍小的時間限制進(jìn)行判斷.)

思路：這個題的思路應(yīng)該是找中心點(diǎn)吧，有一個靈機(jī)一動的想法：用四個數(shù)組：分別從上到下，從下到上，從左到右，從右到左四個方向累加。最終選出四個維度最小的值。我這么說可能比較抽象，簡單舉個例子：
1 1 0 1 1 1
1 0 0 0 0 0
1 1 0 1 1 1
0 0 1 1 1 1
1 0 1 1 0 1
0 1 0 1 0 1
比如上面的數(shù)組：那么左到右：
1 2 0 1 2 3
1 0 0 0 0 0
1 2 0 1 2 3
0 0 1 2 3 4
1 0 1 2 0 1
0 1 0 1 0 1
從右到左：
2 1 0 3 2 1
1 0 0 0 0 0
2 1 0 3 2 1
0 0 4 3 2 1
1 0 2 1 0 1
0 1 0 1 0 1

剩下的兩個我就不寫了，但是從上面的demo看，想要左右1最長，就要兩個數(shù)組中最小的那個，是可以組成左右加號的數(shù)量。差不多就這個思路，我去代碼實(shí)現(xiàn)下試試。
雖然性能賊雞兒垃圾，但是起碼ac了，這里貼上第一版本代碼：

class Solution {
    public static  int orderOfLargestPlusSign(int N, int[][] mines) {
        int ans = 0;
        int[][] left = new int[N][N];
        int[][] right = new int[N][N];
        int[][] top = new int[N][N];
        int[][] bottom = new int[N][N];
        Set<Integer> set = new HashSet<>();
        for(int[] i:mines) set.add(i[0]*10000+i[1]);
        for(int i = 0;i<N;i++){
            left[i][0] = set.contains(i*10000)?0:1;
            for(int j = 1;j<N;j++){
                left[i][j] = set.contains(i*10000+j)?0:left[i][j-1]+1;
            }
            right[i][N-1] = set.contains(i*10000+N-1)?0:1;
            for(int j = N-2;j>=0;j--){
                right[i][j] = set.contains(i*10000+j)?0:right[i][j+1]+1;
            }
        }
        for(int i = 0;i<N;i++){
            top[0][i] = set.contains(i)?0:1;
            for (int j = 1;j<N;j++){
                top[j][i] = set.contains(j*10000+i)?0:top[j-1][i]+1;
            }
            bottom[N-1][i] = set.contains((N-1)*10000+i)?0:1;
            for(int j = N-2;j>=0;j--){
                bottom[j][i] = set.contains(j*10000+i)?0:bottom[j+1][i]+1;
            }
        }
        for(int i = 0;i<N;i++){
            for(int j = 0;j<N;j++) ans = Math.max(ans,Math.min(Math.min(top[i][j],bottom[i][j]),Math.min(left[i][j],right[i][j])));
        }
        return  ans;
    }
}

當(dāng)然了，隨著實(shí)現(xiàn)，也發(fā)現(xiàn)了一些可優(yōu)化的空間， 然后我優(yōu)化了半天也沒什么好辦法，所以直接看了性能第一的代碼：

class Solution {
    public int orderOfLargestPlusSign(int N, int[][] mines) {
        int[][] grid = new int[N][N];

        for (int i = 0; i < grid.length; i++) {
            Arrays.fill(grid[i], N);
        }
        for (int[] mine : mines) {
            grid[mine[0]][mine[1]] = 0;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0, l = 0; j < N; j++) {
                grid[i][j] = Math.min(grid[i][j], l = (grid[i][j] == 0 ? 0 : l + 1));
            }
            for (int k = N - 1, r = 0; k >= 0; k--) {
                grid[i][k] = Math.min(grid[i][k], r = (grid[i][k] == 0 ? 0 : r + 1));
            }
            for (int j = 0, u = 0; j < N; j++) {
                grid[j][i] = Math.min(grid[j][i], u = (grid[j][i] == 0 ? 0 : u + 1));
            }
            for (int k = N - 1, d = 0; k >= 0; k--) {
                grid[k][i] = Math.min(grid[k][i], d = (grid[k][i] == 0 ? 0 : d + 1));
            }
        }

        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res = Math.max(res, grid[i][j]);
            }
        }

        return res;
    }
}

講真，我總覺得思路是一樣的。我之前嘗試自己優(yōu)化也都是壓縮成一個數(shù)組型數(shù)組。但是最終沒優(yōu)化出來。

優(yōu)化代碼