自定義字符串排序

題目：字符串S和 T 只包含小寫字符纹份。在S中运挫，所有字符只會出現(xiàn)一次。S 已經(jīng)根據(jù)某種規(guī)則進(jìn)行了排序亲配。我們要根據(jù)S中的字符順序?qū)進(jìn)行排序尘应。更具體地說，如果S中x在y之前出現(xiàn)吼虎，那么返回的字符串中x也應(yīng)出現(xiàn)在y之前返回任意一種符合條件的字符串T菩收。

示例:
輸入:
S = "cba"
T = "abcd"
輸出: "cbad"
解釋:
S中出現(xiàn)了字符 "a", "b", "c", 所以 "a", "b", "c" 的順序應(yīng)該是 "c", "b", "a".
由于 "d" 沒有在S中出現(xiàn), 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的輸出。
注意:
S的最大長度為26鲸睛，其中沒有重復(fù)的字符。
T的最大長度為200坡贺。
S和T只包含小寫字符官辈。

思路：我覺得這個題目還是很簡單的，目前的想法是s中每一個元素作為key存map遍坟，然後值是t中這個元素出現(xiàn)的次數(shù)拳亿。等重組t的時候可以先把t中s沒出現(xiàn)的寫前面。然後繼續(xù)按照s的順序重組字符串愿伴。反正思路很清晰肺魁，就是不知道會不會出現(xiàn)性能問題。我去試試了隔节。
第一版代碼：

class Solution {
    public String customSortString(String S, String T) {
        Map<Character,Integer> map = new HashMap<>();
        char[] arr = S.toCharArray();
        for(char c : arr) map.put(c,0);
        StringBuffer sb = new StringBuffer();
        for(char c : T.toCharArray()){
           if(map.get(c) != null){
               map.put(c,map.get(c)+1);
           }else {
               sb.append(c);
           }
        }
        for(char c : arr){
            int n = map.get(c);
            while (n>0){
                sb.append(c);
                n--;
            }
        }
        return sb.toString();
    }
}

思路是對的鹅经，就是性能不太好，我這里再看看怎么優(yōu)化怎诫。
第二版本代碼瘾晃，我是覺得這里其實不用map也可以，畢竟最多就26個數(shù)組幻妓。然後上面的 代碼2ms蹦误，這個代碼1ms，雖然進(jìn)步了但是還不是特別好肉津。

class Solution {
    public String customSortString(String S, String T) {
        int[] count = new int[26];
        Arrays.fill(count,-1);
        char[] arr = S.toCharArray();
        for(char c : arr) count[c-'a']++;//這里沒出現(xiàn)的是-1.出現(xiàn)了變0
        StringBuffer sb = new StringBuffer();
        for(char c : T.toCharArray()){
           if(count[c-'a'] > -1){
               count[c-'a']++;
           }else {
               sb.append(c);
           }
        }
        for(char c : arr){
            int n = count[c-'a'];
            while (n>0){
                sb.append(c);
                n--;
            }
        }
        return sb.toString();
    }
}

我去看看性能第一的代碼:

class Solution {
    public String customSortString(String S, String T) {
        int[] count = new int[26];
        for(char c:T.toCharArray()){
            count[c-'a']++;
        }

        StringBuilder ans = new StringBuilder();
        for(char c :S.toCharArray()){
            for(int i=0;i<count[c-'a'];i++){
                ans.append(c);
            }
            count[c-'a']=0;
        }
        for(char c ='a';c<='z';c++){
            for(int i=0;i<count[c-'a'];i++){
                ans.append(c);
            }
        }
        return ans.toString();
    }
}

不明白為什么這個性能更好强胰，for循環(huán)就比while強(qiáng)？反正這個題比較簡單妹沙，就這樣了偶洋，下一題。

匹配子序列的單詞數(shù)

題目：給定字符串 S 和單詞字典 words, 求 words[i] 中是 S 的子序列的單詞個數(shù)初烘。

示例:
輸入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
輸出: 3
解釋: 有三個是 S 的子序列的單詞: "a", "acd", "ace"涡真。
注意:
所有在words和 S 里的單詞都只由小寫字母組成分俯。
S 的長度在 [1, 50000]。
words 的長度在 [1, 5000]哆料。
words[i]的長度在[1, 50]缸剪。

思路：這個題怎么說呢，感覺可實現(xiàn)的方式還是不少的东亦，不管是每個words去對比杏节，還是直接S的所有子串找出來。典阵。但是問題是性能絕對是個大問題奋渔。。初步估計應(yīng)該都會超時吧。總而言之我現(xiàn)在的想法還是用map善玫。S中每一個字母對應(yīng)的下標(biāo)都記錄太防。然後words直接去從字符開始判斷，每次取盡量小的。當(dāng)遇到無法取值的時候就false了。（這里的盡量小是滿足上一個的后續(xù)的最小值。比如說上一個字母的下表取了11藤树，那么當(dāng)前字母可選下標(biāo)6，12拓萌，16岁钓，19，因為6小于上一個所以直接pass微王。能取的最合適的值就是12.）我感覺思路挺清晰的屡限，我去實現(xiàn)試試。
第一版本代碼:

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Map<Character,List<Integer>> map = new HashMap<>();
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            List<Integer> list = map.get(c);
            if(list == null) list =  new ArrayList<>();
            list.add(i);
            map.put(c,list);
        }
        int ans = 0;
        for(String temp : words){
            if(isOk(map,temp)) ans++;
        }
        return ans;
    }
    public boolean isOk(Map<Character,List<Integer>> map,String temp){
        int start = -1;
        for(char c:temp.toCharArray()){
            List<Integer> list = map.get(c);
            if(list == null) return false;
            boolean flag = true;
            for(int i : list){
                if(i>start){
                    flag = false;
                    start = i;
                    break;
                }
            }
            //如果flag為true說明根本沒有合適條件的值炕倘，所以直接false
            if(flag) return false;
        }
        return true;
    }
}

勉強(qiáng)過了沒超時囚霸，我居然還挺慶幸。激才。拓型。感覺可優(yōu)化的點(diǎn)就是這個從頭開始遍歷map的list。這塊肯定是有問題的瘸恼，極端點(diǎn)的情況 aaaaaaaaaaa...aa.這樣到后面的判斷都快n方了劣挫。但是也最多就是從遍歷變成二分。东帅。覺得還是這個方式有點(diǎn)問題压固，我去看看題解吧。
題解跟我做的都好像不是一個題目靠闭，大概思路是分桶：
因為 S 很長帐我，所以尋找一種只需遍歷一次 S 的方法坎炼，避免暴力解法的多次遍歷。將所有單詞根據(jù)首字母不同放入不同的桶中拦键。例如當(dāng) words = ['dog', 'cat', 'cop']谣光，根據(jù)首字母不同可以分為 'c' : ('cat', 'cop'), 'd' : ('dog',)。換句話說芬为，每個桶中的單詞就是該單詞正在等待匹配的下一個字母萄金。在遍歷 S 的同時，將匹配到單詞根據(jù)下一個需要匹配的字母移動到不同的桶中媚朦。
例如氧敢，有字符串 S = 'dcaog'：

• 初始化 heads = 'c' : ('cat', 'cop'), 'd' : ('dog',)；
• 遍歷 S[0] = 'd' 后询张，heads = 'c' : ('cat', 'cop'), 'o' : ('og',)孙乖；
• 遍歷 S[1] = 'c' 后，heads = 'a' : ('at',), 'o' : ('og', 'op')份氧；
• 遍歷 S[2] = 'a' 后的圆，heads = 'o' : ('og', 'op'), 't': ('t',) ;
• 遍歷 S[3] = 'o' 后，heads = 'g' : ('g',), 'p': ('p',), 't': ('t',)半火；
• 遍歷 S[0] = 'g' 后，heads = 'p': ('p',), 't': ('t',)季俩。

使用長度為 26 的數(shù)組 heads 做桶钮糖，每個字母對應(yīng)一個桶。訪問 S 中的每個字母時酌住，將該字母對應(yīng)桶中的所有單詞店归，根據(jù)下一個等待匹配字母放入到不同的桶中。如果已經(jīng)匹配到單詞的最后一個字母酪我，那么子序列單詞數(shù)加 1消痛。完整代碼如下：

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int ans = 0;
        ArrayList<Node>[] heads = new ArrayList[26];
        for (int i = 0; i < 26; ++i)
            heads[i] = new ArrayList<Node>();

        for (String word: words)
            heads[word.charAt(0) - 'a'].add(new Node(word, 0));

        for (char c: S.toCharArray()) {
            ArrayList<Node> old_bucket = heads[c - 'a'];
            heads[c - 'a'] = new ArrayList<Node>();

            for (Node node: old_bucket) {
                node.index++;
                if (node.index == node.word.length()) {
                    ans++;
                } else {
                    heads[node.word.charAt(node.index) - 'a'].add(node);
                }
            }
            old_bucket.clear();
        }
        return ans;
    }

}

class Node {
    String word;
    int index;
    public Node(String w, int i) {
        word = w;
        index = i;
    }
}

我反正是debug走了兩遍才看懂這個寫法。都哭。只能說確實挺巧妙的秩伞。。而且我還覺得這種做法似曾相識欺矫，好像之前做過類似的題目纱新。而且之前也是看題解才想到的。穆趴。算了脸爱，下一題了。

有效的“井”字游戲

題目：用字符串?dāng)?shù)組作為井字游戲的游戲板 board未妹。當(dāng)且僅當(dāng)在井字游戲過程中簿废，玩家有可能將字符放置成游戲板所顯示的狀態(tài)時空入，才返回 true。該游戲板是一個 3 x 3 數(shù)組族檬，由字符 " "歪赢，"X" 和 "O" 組成。字符 " " 代表一個空位导梆。以下是井字游戲的規(guī)則：

玩家輪流將字符放入空位（" "）中轨淌。

第一個玩家總是放字符 “X”，且第二個玩家總是放字符 “O”看尼。

“X” 和 “O” 只允許放置在空位中递鹉，不允許對已放有字符的位置進(jìn)行填充。

當(dāng)有 3 個相同（且非空）的字符填充任何行藏斩、列或?qū)蔷€時躏结，游戲結(jié)束。

當(dāng)所有位置非空時狰域，也算為游戲結(jié)束媳拴。

如果游戲結(jié)束，玩家不允許再放置字符兆览。

示例 1:
輸入: board = ["O ", " ", " "]
輸出: false
解釋: 第一個玩家總是放置“X”屈溉。
示例 2:
輸入: board = ["XOX", " X ", " "]
輸出: false
解釋: 玩家應(yīng)該是輪流放置的。
示例 3:
輸入: board = ["XXX", " ", "OOO"]
輸出: false
示例 4:
輸入: board = ["XOX", "O O", "XOX"]
輸出: true
說明:
游戲板 board 是長度為 3 的字符串?dāng)?shù)組抬探，其中每個字符串 board[i] 的長度為 3子巾。
board[i][j] 是集合 {" ", "X", "O"} 中的一個字符。

思路：這個題怎么說呢小压，我覺得有兩點(diǎn)：1.場上的符號一定是XO一樣多或者X比O多一個线梗。2.當(dāng)X僅有的出現(xiàn)了三個連一起（如示例3），那么一定O少一個怠益。剩下沒別的了吧仪搔，我去代碼試試。
第一版本代碼:

class Solution {
    public boolean validTicTacToe(String[] board) {
        char[][] d = new char[3][3];
        int x = 0;
        int o = 0;
        for(int i = 0;i<3;i++) {
            for(int j = 0;j<3;j++) {
                d[i][j] = board[i].charAt(j);
                if(d[i][j] == 'X') {
                    x++;
                }else if(d[i][j] == 'O'){
                    o++;
                }
            }
        }
        //一對一個的下蜻牢。要么x多一個烤咧，要么一樣多，不會出現(xiàn)第三種結(jié)果
        if(o>x || x>o+1) return false;
        //不足三個根本不會成型抢呆，所以一定可以髓削。
        if(x<=3 && o<3) return true;
        //現(xiàn)在看來數(shù)目是對的，繼續(xù)判斷有沒有贏了還繼續(xù)下的
        boolean x1 = isOk(d, 'X');
        boolean o1 = isOk(d, 'O');
        if(x1 && o1) return false;//不可能兩個人都贏
        if(x1) return x == o+1;//如果x要贏了镀娶，那么最后一步下的立膛，所以x多一步
        if(o1) return x == o;//o要贏最后一步是o下的，所以數(shù)目要一樣
        return true;
        
    }
    public boolean isOk(char[][] d,char c) {
        if(d[0][0] == c && d[0][1] ==c && d[0][2] == c) return true;
        if(d[1][0] == c && d[1][1] ==c && d[1][2] == c) return true;
        if(d[2][0] == c && d[2][1] ==c && d[2][2] == c) return true;
        if(d[0][0] == c && d[1][0] ==c && d[2][0] == c) return true;
        if(d[0][1] == c && d[1][1] ==c && d[2][1] == c) return true;
        if(d[0][2] == c && d[1][2] ==c && d[2][2] == c) return true;
        if(d[0][0] == c && d[1][1] ==c && d[2][2] == c) return true;
        if(d[0][2] == c && d[1][1] ==c && d[2][0] == c) return true;
        return false;
    }
}

還好只是3 * 3.這要是30 * 30還得累死我。宝泵。好啰。這個isok我覺得直接寫比for循環(huán)判斷更直接。所以這個代碼的性能超過百分百了儿奶，撒花~~
這個題目沒啥難度框往，就是邏輯判斷。把所有會報錯的挑出來闯捎，剩下的就是正確的了椰弊。也沒啥好說的，我去瞅一眼性能第一的代碼：

class Solution {
    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row: board)
            for (char c: row.toCharArray()) {
                if (c == 'X') xCount++;
                if (c == 'O') oCount++;
            }

        if (oCount != xCount && oCount != xCount - 1) return false;
        if (win(board, 'X') && oCount != xCount - 1) return false;
        if (win(board, 'O') && oCount != xCount) return false;
        return true;
    }

    public boolean win(String[] B, char P) {
        // B: board, P: player
        for (int i = 0; i < 3; ++i) {
            if (P == B[0].charAt(i) && P == B[1].charAt(i) && P == B[2].charAt(i))
                return true;
            if (P == B[i].charAt(0) && P == B[i].charAt(1) && P == B[i].charAt(2))
                return true;
        }
        if (P == B[0].charAt(0) && P == B[1].charAt(1) && P == B[2].charAt(2))
            return true;
        if (P == B[0].charAt(2) && P == B[1].charAt(1) && P == B[2].charAt(0))
            return true;
        return false;
    }
}

思路大同小異瓤鼻，就是寫法上不太一樣秉版。這個題過了。

所有可能的路徑

題目：給一個有 n 個結(jié)點(diǎn)的有向無環(huán)圖茬祷，找到所有從 0 到 n-1 的路徑并輸出（不要求按順序）二維數(shù)組的第 i 個數(shù)組中的單元都表示有向圖中 i 號結(jié)點(diǎn)所能到達(dá)的下一些結(jié)點(diǎn)（譯者注：有向圖是有方向的清焕，即規(guī)定了 a→b 你就不能從 b→a ）空就是沒有下一個結(jié)點(diǎn)了。

示例 1：
輸入：graph = [[1,2],[3],[3],[]]
輸出：[[0,1,3],[0,2,3]]
解釋：有兩條路徑 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：
輸入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
輸出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
示例 3：
輸入：graph = [[1],[]]
輸出：[[0,1]]
示例 4：
輸入：graph = [[1,2,3],[2],[3],[]]
輸出：[[0,1,2,3],[0,2,3],[0,3]]
示例 5：
輸入：graph = [[1,3],[2],[3],[]]
輸出：[[0,1,2,3],[0,3]]
提示：
結(jié)點(diǎn)的數(shù)量會在范圍 [2, 15] 內(nèi)祭犯。
你可以把路徑以任意順序輸出秸妥，但在路徑內(nèi)的結(jié)點(diǎn)的順序必須保證。

題目截圖

思路：這個題我覺得思路還好吧沃粗，應(yīng)該就是廣搜或者深搜粥惧。而且注意這個題目上說到了是有向無環(huán)圖。既然無環(huán)的話也不怕死循環(huán)了最盅，直接就順序往下遍歷突雪？大概思路有的，我去實現(xiàn)下試試檩禾。
第一版本代碼：

class Solution {
    int n;
    List<List<Integer>> ans;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        ans = new ArrayList<List<Integer>>();
        n = graph.length-1;
        dfs(graph, 0,new ArrayList<Integer>());
        return ans;
    }
    public void dfs(int[][] graph,int temp,List<Integer> list){
        list.add(temp);
        if(temp == n) {
            ans.add(list);
            return;
        }
        for(int i : graph[temp]) {
            dfs(graph, i, new ArrayList<Integer>(list));
        }
    }
}

果然這個題目比我想的還要簡單。一開始看了題目我就想著要不要記憶化啥的疤祭。盼产。但是后來仔細(xì)審了題目發(fā)現(xiàn)無環(huán)，所以就直接暴力遍歷勺馆。代碼性能還行戏售，至于優(yōu)化點(diǎn)不太清楚，我現(xiàn)在能想到的就是dfs變成顯示棧調(diào)用草穆？但是感覺不會性能差別很大啊灌灾，直接去看看性能第一的代碼：

class Solution {
  public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<Integer> tem = new ArrayList<>();
        tem.add(0);
        dfs(graph,0,graph.length,tem);
        return ans;
    }

    public List<List<Integer>> ans = new ArrayList<>();
    public void dfs(int [][] graph,int next ,int end ,List<Integer> tem){

        //封裝結(jié)果
        if(next == end-1){
            ans.add(new ArrayList<>(tem));
            return;
        }

        //next 時候可以選擇得路線
        int graph_next[] = graph[next];

        for(int i=0;i<graph_next.length;i++){
            //加入路徑
            tem.add(graph_next[i]);
            dfs(graph,graph_next[i],end,tem);
            tem.remove(tem.size()-1);
        }

    }
}

性能第一的代碼用的是回溯，雖然我覺得本質(zhì)上應(yīng)該差不多悲柱，但是因為就只差了1ms的時間锋喜，所以可能這么寫就是性能更好吧，反正這個題比較簡單，直接過了嘿般，下一題段标。

不同的子序列

題目：給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現(xiàn)的個數(shù)炉奴。字符串的一個 子序列 是指逼庞，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對位置所組成的新字符串。（例如瞻赶，"ACE" 是 "ABCDE" 的一個子序列赛糟，而 "AEC" 不是）題目數(shù)據(jù)保證答案符合 32 位帶符號整數(shù)范圍。

示例 1：
輸入：s = "rabbbit", t = "rabbit"
輸出：3
解釋：
如下圖所示, 有 3 種可以從 s 中得到 "rabbit" 的方案砸逊。
(上箭頭符號 ^ 表示選取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
示例 2：
輸入：s = "babgbag", t = "bag"
輸出：5
解釋：
如下圖所示, 有 5 種可以從 s 中得到 "bag" 的方案璧南。
(上箭頭符號 ^ 表示選取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
提示：
0 <= s.length, t.length <= 1000
s 和 t 由英文字母組成

思路：這個是21/3/17的每日一題，困難難度的痹兜，其實我現(xiàn)在對于困難難度的題目都抱著敬而遠(yuǎn)之的態(tài)度穆咐，畢竟自認(rèn)為太菜。不過既然是現(xiàn)在每日一題做到了也要盡量啃啃字旭。從頭說這個題目对湃，這個題目的標(biāo)簽有個動態(tài)規(guī)劃，只要是dp肯定是有個dp公式的遗淳。暫時我的想法肯定是從左往右一次遍歷拍柒，至于遞推公式，我的想法是二維數(shù)組屈暗，長寬是s和t的長度拆讯。所以盲猜動態(tài)方程肯定是從角角逼近的方式填充的。
上面的思路連蒙帶猜的對了养叛，但是動態(tài)方程遲遲沒有寫出來种呐，所以我決定還是直接看題解了。當(dāng)然只看了下思路弃甥，然后自己去寫的代碼爽室。
附上代碼：

class Solution {
    public int numDistinct(String s, String t) {
        int lens = s.length();
        int lent = t.length();
        if(lens<lent) return 0;//t如果比s長，不可能有子序列
        int[][] dp = new int[lens+1][lent+1];
        //最后一個字符是空淆攻，空是任何字符串的子序列阔墩。所以補(bǔ)1
        for(int i = 0;i<=lens;i++) dp[i][lent] = 1;
        for(int i = lens-1;i>=0;i--) {
            char cs = s.charAt(i);
            for(int j = lent-1;j>=0;j--) {
                char ct = t.charAt(j);
                //不管當(dāng)前元素能不能用上，之前已經(jīng)能組成的可能都不變瓶珊，所以都加下面那個數(shù)字
                if(cs == ct) {
                    //右下是當(dāng)前元素的下一個啸箫。都可以被當(dāng)前元素續(xù)上，所以加上右下
                    dp[i][j] = dp[i+1][j+1]+dp[i+1][j];
                }else {
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }
}

其實上面的猜測很大一部分都對了的伞芹，比如說二維dp數(shù)組角落逼近忘苛。我差的就是這么個思路清晰的遞推公式。。
附上當(dāng)時我看的遞推公式推到的表述：

• 假設(shè)字符串 s和 t的長度分別為 m 和 n柑土。如果 t 是 s 的子序列蜀肘，則 s 的長度一定大于或等于 t 的長度，即只有當(dāng) m≥n 時稽屏，t 才可能是 s 的子序列扮宠。如果 m<n，則 t 一定不是 s 的子序列狐榔，因此直接返回 0坛增。
• 當(dāng) m≥n 時，可以通過動態(tài)規(guī)劃的方法計算在 s 的子序列中 t 出現(xiàn)的個數(shù)薄腻。
• 創(chuàng)建二維數(shù)組dp收捣，其中 dp[i][j] 表示在 s[i:]的子序列中 t[j:] 出現(xiàn)的個數(shù)。
• 上述表示中庵楷，s[i:] 表示 s從下標(biāo) i 到末尾的子字符串罢艾，t[j:] 表示 t從下標(biāo) j 到末尾的子字符串。
• 考慮動態(tài)規(guī)劃的邊界情況：
  • 當(dāng) j=n時尽纽，t[j:] 為空字符串咐蚯，由于空字符串是任何字符串的子序列，因此對任意dp[i][n]=1弄贿；
  • 當(dāng) i=m 且 j<n 時春锋，s[i:]為空字符串，t[j:] 為非空字符串差凹，由于非空字符串不是空字符串的子序列期奔，因此對任意 j<n，dp[m][j]=0危尿。
  • 當(dāng) s[i]=t[j]時呐萌，dp[i][j] 由兩部分組成：
    如果 s[i] 和 t[j] 匹配，則考慮 t[j+1:]作為 s[i+1:] 的子序列谊娇，子序列數(shù)為dp[i+1][j+1]肺孤；
    如果 s[i] 不和 t[j] 匹配，則考慮 t[j:]作為 s[i+1:] 的子序列邮绿，子序列數(shù)為 dp[i+1][j]渠旁。
    因此當(dāng) s[i] = t[j]時攀例，有dp[i][j] = dp[i+1][j+1] + dp[i+1][j]船逮。

以上就是全部dp 的思路。也是上面代碼的語言表述粤铭。由此得出這個題的答案挖胃。

本篇筆記就記到這里，如果稍微幫到你了記得點(diǎn)個喜歡點(diǎn)個關(guān)注，也祝大家工作順順利利吧~