2月份最后一周的刷題筆記（ps：以后每一篇都會(huì)記錄一個(gè)日期休讳，恐怕自己哪周沒(méi)堅(jiān)持住或者忘記了）。

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

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

對(duì)于三元組(A, B, C) ，“C”為頂層方塊皂甘，方塊“A”、“B”分別作為方塊“C”下一層的的左悼凑、右子塊偿枕。當(dāng)且僅當(dāng)(A, B, C)是被允許的三元組，我們才可以將其堆砌上户辫。初始時(shí)渐夸，給定金字塔的基層 bottom，用一個(gè)字符串表示渔欢。一個(gè)允許的三元組列表 allowed墓塌，每個(gè)三元組用一個(gè)長(zhǎng)度為 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
解析：
無(wú)法一直堆到塔尖垫挨。
注意, 允許存在像 (A, B, C) 和 (A, B, D) 這樣的三元組韩肝，其中 C != D。
提示：
bottom 的長(zhǎng)度范圍在 [2, 8]九榔。
allowed 的長(zhǎng)度范圍在[0, 200]哀峻。
方塊的標(biāo)記字母范圍為{'A', 'B', 'C', 'D', 'E', 'F', 'G'}涡相。

思路：這個(gè)題怎么說(shuō)呢，暫時(shí)的思路就是首先把最后一層的底湊出來(lái)剩蟀。比如第一個(gè)塔型的BCD,湊出來(lái)以后倒數(shù)第二層其實(shí)可能就有多個(gè)選擇了催蝗，因?yàn)榭赡芙M成最后一層的可能性很多。然后我們把第二層的所有可能都要跑育特，直到某一種方式可以直達(dá)塔頂或者所有的路都不行那么就false丙号，總而言之這是一個(gè)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)這個(gè)題不簡(jiǎn)單啊，一開(kāi)始我我尋思用字符串的startWith來(lái)判斷上一層涮拗，但是這樣會(huì)不會(huì)重復(fù)乾戏，是不是要一次次遍歷之類的就很復(fù)雜， 所以最后決定用hash表的方式來(lái)做三热。
把左右兩基層作為key鼓择，因?yàn)榇嬖贏,B,C, 和A,B,D這種三元組，所以value用字符的list 來(lái)存儲(chǔ)就漾。這樣A,B,C和A,B,D的存儲(chǔ)是key 是AB呐能，value是：[C,D]。
然后在一層一層往上加的時(shí)候只要判斷當(dāng)前兩個(gè)基層能不能組成三元組抑堡，能的話頂層是什么摆出，并分別往下走就行了。

其實(shí)這個(gè)也算是一個(gè)標(biāo)準(zhǔn)的回溯題目了首妖，只不過(guò)因?yàn)橄乱粚邮侵苯蛹拥絫emp上所以不用退回上一步偎漫。
有點(diǎn)類似與我之前說(shuō)的迷宮，每個(gè)房間7個(gè)門(mén)的demo有缆。（這篇筆記是單獨(dú)說(shuō)DFS和BFS的象踊，感興趣可以去看一下：http://www.reibang.com/p/fbe0d05187a5）
然后反正現(xiàn)在是實(shí)現(xiàn)了，這個(gè)題我覺(jué)得挺不容易一下子想到的棚壁，但是慢慢琢磨也不是很難杯矩，而且這個(gè)題有一個(gè)很坑的點(diǎn)是三元組可重用。這個(gè)我也不知道為什么這么設(shè)置灌曙，反正默認(rèn)就是這樣菊碟，所以在做的時(shí)候踩了不少坑，一開(kāi)始把這個(gè)題想復(fù)雜了在刺，用過(guò)的三元組還要?jiǎng)h除逆害，所以費(fèi)事還報(bào)錯(cuò)头镊。
接下來(lá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ù)組表示這個(gè)hash表的key魄幕，也就是橫縱坐標(biāo)定位了具體的基層兩個(gè)值相艇。然后用二進(jìn)制表示list。因?yàn)樽疃噙@一個(gè)上層就'A', 'B', 'C', 'D', 'E', 'F', 'G'這七個(gè)可能纯陨，所以七個(gè)二進(jìn)制就能表示這個(gè)了坛芽。比如 1001000.就是說(shuō)這個(gè)橫縱坐標(biāo)的基層頂層有兩種可能：G和D。
1110111就是橫縱坐標(biāo)有6種可能：A,B,C ,E,F,G
然后一個(gè)49個(gè)值的二維數(shù)組要遠(yuǎn)比hash表的性能好的多翼抠。
同理可以湊出來(lái)的底層（除了最底層是指定剩下其實(shí)都有多種可能）可以二維數(shù)組表示咙轩，值為0就說(shuō)明當(dāng)前沒(méi)這個(gè)選擇。值不是0說(shuō)明當(dāng)前選擇是可以的阴颖。
反正這個(gè)代碼精巧在把hash轉(zhuǎn)為二維數(shù)組活喊，剩下的dfs也就那樣。量愧。其實(shí)這種數(shù)組多維表示不同意義的方法我是早早就知道的钾菊，可惜這個(gè)題沒(méi)想到這點(diǎn)。哎偎肃，還是練得不夠煞烫，下一題了。

劃分字母區(qū)間

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

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

思路：這個(gè)題感覺(jué)沒(méi)啥難度啊，我暫時(shí)的想法是獲取每一個(gè)字母的第一個(gè)出現(xiàn)位置和最后一個(gè)出現(xiàn)位置篇裁。每一個(gè)字母構(gòu)成一條線沛慢。先從第一個(gè)字母開(kāi)始這條件中間的元素都往外擴(kuò)散，直到所有的元素都擴(kuò)散完了达布。這個(gè)區(qū)域就是第一個(gè)區(qū)域团甲，如果后面還有空間那么再逐一去判斷。
!!!居然一次就過(guò)了黍聂， 這個(gè)題目的難度果然不科學(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));
    }
}

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

class Solution {
    public List<Integer> partitionLabels(String S) {  
        List<Integer> ans = new ArrayList<Integer>();
        //第一個(gè)元素是第一次出現(xiàn)的，第二個(gè)元素是最后一次出現(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;//這個(gè)已經(jīng)是別的圈子里的了炕柔，不用浪費(fèi)時(shí)間
            d[i][0] = -1;//這個(gè)人已經(jīng)開(kāi)圈了酌泰，所以標(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)槭前雌鹗嘉恢门判虻模赃@個(gè)不行匕累，以后的都不行了
                }
            }
            ans.add(end-start+1);
        }
        return ans;     
    }
}

我覺(jué)得還能繼續(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)化到最佳性能了哩罪，嘿嘿授霸，這個(gè)題其實(shí)實(shí)現(xiàn)比較簡(jiǎn)單，從小寫(xiě)a到z很容易想到數(shù)組下標(biāo)代替值际插。從數(shù)據(jù)范圍只有500可以讓我們有機(jī)會(huì)暴力ac碘耳。重點(diǎn)應(yīng)該是在優(yōu)化上吧：首先第一版代碼我的思路沒(méi)問(wèn)題，只不每一個(gè)元素都要獲取最后一次出現(xiàn)框弛，期間有很多重復(fù)判斷辛辨，所以性能才慘不忍睹。其實(shí)只要加個(gè)記憶的set瑟枫，如果判斷過(guò)了不重復(fù)判斷就好多了斗搞。
但是我當(dāng)時(shí)思路有點(diǎn)歪，所以用類似并查的模式標(biāo)記+擴(kuò)散慷妙，找出一個(gè)個(gè)圈子了僻焚。不過(guò)性能也還行，起碼是多種思路膝擂。下一題了虑啤。

猜字謎

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

單詞 word 中包含謎面 puzzle 的第一個(gè)字母叉寂。

單詞 word 中的每一個(gè)字母都可以在謎面 puzzle 中找到萍启。

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

返回一個(gè)答案數(shù)組 answer，數(shù)組中的每個(gè)元素 answer[i] 是在給出的單詞列表 words 中可以作為字謎迷面 puzzles[i] 所對(duì)應(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 個(gè)單詞可以作為 "aboveyz" 的謎底 : "aaaa"
1 個(gè)單詞可以作為 "abrodyz" 的謎底 : "aaaa"
3 個(gè)單詞可以作為 "abslute" 的謎底 : "aaaa", "asas", "able"
2 個(gè)單詞可以作為 "absoryz" 的謎底 : "aaaa", "asas"
4 個(gè)單詞可以作為 "actresz" 的謎底 : "aaaa", "asas", "actt", "access"
沒(méi)有單詞可以作為 "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] 都是小寫(xiě)英文字母超埋。
每個(gè) puzzles[i] 所包含的字符都不重復(fù)搏讶。

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

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        //字符串轉(zhuǎn)成二進(jìn)制方便計(jì)算谴垫。而且字母最多26個(gè)章母。
        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)槌耸鬃帜钙溆嗟挠袥](méi)有都可以翩剪！
        return dfs(map,puzzle, idx + 1,  key) + dfs(map, puzzle, idx + 1, key | 1 << puzzle[idx] - 'a');
    }
}

我果然是個(gè)渣渣乳怎，這個(gè)代碼是看了別人的題解最終實(shí)現(xiàn)的。其實(shí)大體思路我是知道的前弯，也想到了二進(jìn)制舞肆，就是不會(huì)具體怎么運(yùn)算，一直鉆牛角尖以為能直接用位運(yùn)算博杖。。卻不想人家用的位移一個(gè)個(gè)比較筷登。剃根。。說(shuō)實(shí)話就key | 1 << puzzle[idx] - 'a'這句代碼我自己是想不到的前方”纷恚總體而言這個(gè)題的思路總結(jié)一下：
首先一個(gè)個(gè)字符串比較肯定超時(shí)而且沒(méi)必要廉油。
因?yàn)橹i面可能會(huì)很長(zhǎng)，但是本質(zhì)上出現(xiàn)的字母不會(huì)超過(guò)三個(gè)苗傅，所以這里用字母的排序（a是0抒线，z是25）來(lái)代表數(shù)值，最終實(shí)現(xiàn)把每一個(gè)謎面包含的字母都用數(shù)字的形式存起來(lái)（好像聽(tīng)說(shuō)過(guò)這個(gè)是狀態(tài)壓縮）渣慕，然后重點(diǎn)就來(lái)：其實(shí)一個(gè)謎面最多包含7個(gè)字符嘶炭，所以不管謎面什么形式，肯定有重復(fù)的逊桦，比如aaabbb,ab,aaab,abbb這些本質(zhì)上都是一樣的眨猎。所以我們用hash表根據(jù)謎面字母不同計(jì)數(shù)。比如上文中的就可以這么存：ab:4.而上文我也說(shuō)了為了性能强经，所以這里我們也不存ab了睡陪，而是把a(bǔ)b轉(zhuǎn)化成一個(gè)數(shù)字來(lái)存儲(chǔ)。就這樣我們根據(jù)出現(xiàn)的字符的不同把謎面都分別存儲(chǔ)好匿情。
接下來(lái)遍歷謎底：因?yàn)橹i底一定是七個(gè)字符兰迫。除了首字母是必須存在的，其余都可有可無(wú)炬称，所以我們可以將謎面拆開(kāi)：首字母是必須的汁果，任何首字母+隨意其他六個(gè)元素的組合都滿足要求，所以這里用遞歸的方式實(shí)現(xiàn)转砖。因?yàn)槌耸鬃帜钙溆嗟亩伎捎锌蔁o(wú)须鼎，所以我們可以理解為除了首字母其余的都分兩種情況：有/無(wú)。所以遞歸中是兩種情況的結(jié)果的和府蔗。
這個(gè)題到這里就解出來(lái)了晋控。
其實(shí)我覺(jué)得這個(gè)題考點(diǎn)有幾個(gè)：一個(gè)是字符串轉(zhuǎn)數(shù)字存儲(chǔ)（不這樣會(huì)超時(shí)）。一個(gè)是hash姓赤，還有一個(gè)是就是把所有謎底對(duì)應(yīng)謎面的可能性都列出來(lái)赡译。大概就是這樣吧，這個(gè)題我做好難不铆，我還是滾去刷中等題目吧蝌焚。下一題了。

最大加號(hào)標(biāo)志

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

一個(gè) k" 階由 1 組成的“軸對(duì)稱”加號(hào)標(biāo)志具有中心網(wǎng)格 grid[x][y] = 1 涝开，以及4個(gè)從中心向上循帐、向下、向左舀武、向右延伸拄养，長(zhǎng)度為 k-1，由 1 組成的臂银舱。下面給出 k" 階“軸對(duì)稱”加號(hào)標(biāo)志的示例瘪匿。注意，只有加號(hào)標(biāo)志的所有網(wǎng)格要求為 1纵朋，別的網(wǎng)格可能為 0 也可能為 1柿顶。

k 階軸對(duì)稱加號(hào)標(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)格中，最大加號(hào)標(biāo)志的階只能是2操软。一個(gè)標(biāo)志已在圖中標(biāo)出嘁锯。
示例 2：
輸入: N = 2, mines = []
輸出: 1
解釋:
11

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

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

思路：這個(gè)題的思路應(yīng)該是找中心點(diǎn)吧藏澳，有一個(gè)靈機(jī)一動(dòng)的想法：用四個(gè)數(shù)組：分別從上到下仁锯，從下到上，從左到右翔悠，從右到左四個(gè)方向累加业崖。最終選出四個(gè)維度最小的值。我這么說(shuō)可能比較抽象蓄愁，簡(jiǎn)單舉個(gè)例子：
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

剩下的兩個(gè)我就不寫(xiě)了双炕，但是從上面的demo看，想要左右1最長(zhǎng)撮抓，就要兩個(gè)數(shù)組中最小的那個(gè)妇斤，是可以組成左右加號(hào)的數(shù)量。差不多就這個(gè)思路丹拯，我去代碼實(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)化了半天也沒(méi)什么好辦法媳纬，所以直接看了性能第一的代碼：

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;
    }
}

講真双肤，我總覺(jué)得思路是一樣的。我之前嘗試自己優(yōu)化也都是壓縮成一個(gè)數(shù)組型數(shù)組钮惠。但是最終沒(méi)優(yōu)化出來(lái)。

優(yōu)化代碼