2月份最后一周的刷题笔记（ps：以后每一篇都会记录一个日期，恐怕自己哪周没坚持住或者忘记了）。

金字塔转换矩阵

题目：现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。使用三元组表示金字塔的堆砌规则如下：

对于三元组(A, B, C) ，“C”为顶层方块，方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当且仅当(A, B, C)是被允许的三元组，我们才可以将其堆砌上。初始时，给定金字塔的基层 bottom，用一个字符串表示。一个允许的三元组列表 allowed，每个三元组用一个长度为 3 的字符串表示。如果可以由基层一直堆到塔尖就返回 true ，否则返回 false 。

示例 1：
输入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出：true
解析：
可以堆砌成这样的金字塔:
A
/
G E
/ \ /
B C D
因为符合('B', 'C', 'G'), ('C', 'D', 'E') 和 ('G', 'E', 'A') 三种规则。
示例 2：
输入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出：false
解析：
无法一直堆到塔尖。
注意, 允许存在像 (A, B, C) 和 (A, B, D) 这样的三元组，其中 C != D。
提示：
bottom 的长度范围在 [2, 8]。
allowed 的长度范围在[0, 200]。
方块的标记字母范围为{'A', 'B', 'C', 'D', 'E', 'F', 'G'}。

思路：这个题怎么说呢，暂时的思路就是首先把最后一层的底凑出来。比如第一个塔型的BCD,凑出来以后倒数第二层其实可能就有多个选择了，因为可能组成最后一层的可能性很多。然后我们把第二层的所有可能都要跑，直到某一种方式可以直达塔顶或者所有的路都不行那么就false，总而言之这是一个dfs，也就是深度优先搜索。我去实现下试试了。
贴上第一版代码：

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;
        //当前这层垒好了，继续往上
        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;
    }
}

随着做随着发现这个题不简单啊，一开始我我寻思用字符串的startWith来判断上一层，但是这样会不会重复，是不是要一次次遍历之类的就很复杂， 所以最后决定用hash表的方式来做。
把左右两基层作为key，因为存在A,B,C, 和A,B,D这种三元组，所以value用字符的list 来存储。这样A,B,C和A,B,D的存储是key 是AB，value是：[C,D]。
然后在一层一层往上加的时候只要判断当前两个基层能不能组成三元组，能的话顶层是什么，并分别往下走就行了。

其实这个也算是一个标准的回溯题目了，只不过因为下一层是直接加到temp上所以不用退回上一步。
有点类似与我之前说的迷宫，每个房间7个门的demo。（这篇笔记是单独说DFS和BFS的，感兴趣可以去看一下：https://www.jianshu.com/p/fbe0d05187a5）
然后反正现在是实现了，这个题我觉得挺不容易一下子想到的，但是慢慢琢磨也不是很难，而且这个题有一个很坑的点是三元组可重用。这个我也不知道为什么这么设置，反正默认就是这样，所以在做的时候踩了不少坑，一开始把这个题想复杂了，用过的三元组还要删除，所以费事还报错。
接下来我去看看性能第一的代码：

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

真的是惊为天人！首先用数组型数组表示这个hash表的key，也就是横纵坐标定位了具体的基层两个值。然后用二进制表示list。因为最多这一个上层就'A', 'B', 'C', 'D', 'E', 'F', 'G'这七个可能，所以七个二进制就能表示这个了。比如 1001000.就是说这个横纵坐标的基层顶层有两种可能：G和D。
1110111就是横纵坐标有6种可能：A,B,C ,E,F,G
然后一个49个值的二维数组要远比hash表的性能好的多。
同理可以凑出来的底层（除了最底层是指定剩下其实都有多种可能）可以二维数组表示，值为0就说明当前没这个选择。值不是0说明当前选择是可以的。
反正这个代码精巧在把hash转为二维数组，剩下的dfs也就那样。。其实这种数组多维表示不同意义的方法我是早早就知道的，可惜这个题没想到这点。哎，还是练得不够，下一题了。

划分字母区间

题目：字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

思路：这个题感觉没啥难度啊，我暂时的想法是获取每一个字母的第一个出现位置和最后一个出现位置。每一个字母构成一条线。先从第一个字母开始这条件中间的元素都往外扩散，直到所有的元素都扩散完了。这个区域就是第一个区域，如果后面还有空间那么再逐一去判断。
!!!居然一次就过了， 这个题目的难度果然不科学，我先贴代码：

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

思路和我之前想的差不多，只不过我这个代码的性能有点问题。我觉得出现的原因应该是我来回来去重复判断，我应该直接遍历每个字母获取其起始出现的元素，我去优化下。
换了中写法， 性能上来了，虽然还不是最好：

class Solution {
    public List<Integer> partitionLabels(String S) {  
        List<Integer> ans = new ArrayList<Integer>();
        //第一个元素是第一次出现的，第二个元素是最后一次出现的
        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;//这个已经是别的圈子里的了，不用浪费时间
            d[i][0] = -1;//这个人已经开圈了，所以标记下
            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;//因为是按起始位置排序的，所以这个不行，以后的都不行了
                }
            }
            ans.add(end-start+1);
        }
        return ans;     
    }
}

我觉得还能继续优化，哈哈，我去试试：

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

终于优化到最佳性能了，嘿嘿，这个题其实实现比较简单，从小写a到z很容易想到数组下标代替值。从数据范围只有500可以让我们有机会暴力ac。重点应该是在优化上吧：首先第一版代码我的思路没问题，只不每一个元素都要获取最后一次出现，期间有很多重复判断，所以性能才惨不忍睹。其实只要加个记忆的set，如果判断过了不重复判断就好多了。
但是我当时思路有点歪，所以用类似并查的模式标记+扩散，找出一个个圈子了。不过性能也还行，起码是多种思路。下一题了。

猜字谜

题目：外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

单词 word 中包含谜面 puzzle 的第一个字母。

单词 word 中的每一个字母都可以在谜面 puzzle 中找到。

例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

示例：
输入：
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" 的谜底，因为列表中的单词都不含字母 '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] 所包含的字符都不重复。

思路：2021/2/26的每日一题，虽然是困难难度，但是读完题就觉得思如泉涌。我感觉这个题能卡的也就是性能了。因为谜底的个数是100000，谜面个数10000，如果单纯的去一对一的比对绝对是要超时。而首字母是比含的单词。上面的题目是数组下标代表值还是挺有用的。我目前觉得字典应该是一个挺好的选择。每一个谜底或者谜面用二进制数字表示。比如aaaa不管出现几次a，我们只要知道出现a了就可以。大概就是这样的思路。还有谜底长度只有7，所以说如果谜面超过7的直接pass。
第一版代码：

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        //字符串转成二进制方便计算。而且字母最多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);
        // 之所以的两种情况是因为除了首字母其余的有没有都可以！
        return dfs(map,puzzle, idx + 1,  key) + dfs(map, puzzle, idx + 1, key | 1 << puzzle[idx] - 'a');
    }
}

我果然是个渣渣，这个代码是看了别人的题解最终实现的。其实大体思路我是知道的，也想到了二进制，就是不会具体怎么运算，一直钻牛角尖以为能直接用位运算。。却不想人家用的位移一个个比较。。。说实话就key | 1 << puzzle[idx] - 'a'这句代码我自己是想不到的。总体而言这个题的思路总结一下：
首先一个个字符串比较肯定超时而且没必要。
因为谜面可能会很长，但是本质上出现的字母不会超过三个，所以这里用字母的排序（a是0，z是25）来代表数值，最终实现把每一个谜面包含的字母都用数字的形式存起来（好像听说过这个是状态压缩），然后重点就来：其实一个谜面最多包含7个字符，所以不管谜面什么形式，肯定有重复的，比如aaabbb,ab,aaab,abbb这些本质上都是一样的。所以我们用hash表根据谜面字母不同计数。比如上文中的就可以这么存：ab:4.而上文我也说了为了性能，所以这里我们也不存ab了，而是把ab转化成一个数字来存储。就这样我们根据出现的字符的不同把谜面都分别存储好。
接下来遍历谜底：因为谜底一定是七个字符。除了首字母是必须存在的，其余都可有可无，所以我们可以将谜面拆开：首字母是必须的，任何首字母+随意其他六个元素的组合都满足要求，所以这里用递归的方式实现。因为除了首字母其余的都可有可无，所以我们可以理解为除了首字母其余的都分两种情况：有/无。所以递归中是两种情况的结果的和。
这个题到这里就解出来了。
其实我觉得这个题考点有几个：一个是字符串转数字存储（不这样会超时）。一个是hash，还有一个是就是把所有谜底对应谜面的可能性都列出来。大概就是这样吧，这个题我做好难，我还是滚去刷中等题目吧。下一题了。

最大加号标志

题目：在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

一个 k" 阶由 1 组成的“轴对称”加号标志具有中心网格 grid[x][y] = 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。下面给出 k" 阶“轴对称”加号标志的示例。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。

k 阶轴对称加号标志示例:
阶 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
在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。
示例 2：
输入: N = 2, mines = []
输出: 1
解释:
11

11
没有 2 阶加号标志，有 1 阶加号标志。
示例 3：
输入: N = 1, mines = [[0, 0]]
输出: 0
解释:

0
没有加号标志，返回 0 。
提示：
整数N 的范围： [1, 500].
mines 的最大长度为 5000.
mines[i] 是长度为2的由2个 [0, N-1] 中的数组成.
(另外,使用 C, C++, 或者 C# 编程将以稍小的时间限制进行判断.)

思路：这个题的思路应该是找中心点吧，有一个灵机一动的想法：用四个数组：分别从上到下，从下到上，从左到右，从右到左四个方向累加。最终选出四个维度最小的值。我这么说可能比较抽象，简单举个例子：
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
比如上面的数组：那么左到右：
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最长，就要两个数组中最小的那个，是可以组成左右加号的数量。差不多就这个思路，我去代码实现下试试。
虽然性能贼鸡儿垃圾，但是起码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;
    }
}

当然了，随着实现，也发现了一些可优化的空间， 然后我优化了半天也没什么好办法，所以直接看了性能第一的代码：

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

讲真，我总觉得思路是一样的。我之前尝试自己优化也都是压缩成一个数组型数组。但是最终没优化出来。

优化代码