回文子串

題目：給定一個(gè)字符串，你的任務(wù)是計(jì)算這個(gè)字符串中有多少個(gè)回文子串。具有不同開(kāi)始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會(huì)被視作不同的子串。

示例 1：
輸入："abc"
輸出：3
解釋?zhuān)喝齻€(gè)回文子串: "a", "b", "c"
示例 2：
輸入："aaa"
輸出：6
解釋?zhuān)?個(gè)回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
輸入的字符串長(zhǎng)度不會(huì)超過(guò) 1000 。

思路：這個(gè)題我覺(jué)得最簡(jiǎn)單的辦法就是暴力遍歷。每個(gè)元素都往后遍歷出所有的回文串。長(zhǎng)度不超過(guò)1000，也就是全遍歷也不超過(guò)1000000。我先去試試。超時(shí)了再說(shuō)算法什么的。
暴力法居然沒(méi)超時(shí)。。這個(gè)題有點(diǎn)東西啊，我先附上代碼：

class Solution {
    public int countSubstrings(String s) {
        int res = s.length();
        char[] c = s.toCharArray();
        for(int i = 0;i<c.length;i++) {
            for(int j = i+1;j<c.length;j++) {
                boolean flag = true;
                int k = 0;
                while(i+k<j-k) {
                    if (c[i+k]!=c[j-k]) {
                        flag = false;
                        break;
                    }
                    k++;
                }
                if(flag) res++;
            }
        }
        return res;
    }
}

當(dāng)然了是低空略過(guò)，所以這個(gè)實(shí)現(xiàn)絕對(duì)不應(yīng)該這么暴力遍歷，我再想想怎么用一些算法來(lái)解決這個(gè)題吧：

class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        char[] c = s.toCharArray();
        for(int i = 0;i<c.length;i++) {
            //以當(dāng)前元素為中心的回文串
            int k = 0;
            while(i-k>=0 && i+k<c.length) {
                if(c[i-k] == c[i+k]) {
                    res++;
                }else {
                    break;
                }
                k++;
            }
            k = 0;
            while(i-k>=0 && i+k+1<c.length) {
                if(c[i-k] == c[i+k+1]) {
                    res++;
                }else {
                    break;
                }
                k++;
            }
        }
        return res;
    }
}

也沒(méi)用啥算法，就是換了個(gè)思路。之前的話是從某個(gè)位置開(kāi)始作為回文串的左起始點(diǎn)。其實(shí)這個(gè)比較麻煩的就是很多時(shí)候要做無(wú)用功。換了個(gè)思路找到回文串的中間點(diǎn)（單數(shù)是中間那個(gè)。雙數(shù)是中間兩個(gè)中靠前那個(gè)）。這樣當(dāng)發(fā)現(xiàn)這個(gè)作為中點(diǎn)不符合要求可以直接跳過(guò)判斷了，可以少做很多無(wú)用功。然后這個(gè)代碼的性能超過(guò)百分之九十六的人，所以這個(gè)題就這樣過(guò)了。下一題吧。

單詞替換

題目：在英語(yǔ)中，我們有一個(gè)叫做 詞根(root)的概念，它可以跟著其他一些詞組成另一個(gè)較長(zhǎng)的單詞——我們稱這個(gè)詞為 繼承詞(successor)。例如，詞根an，跟隨著單詞 other(其他)，可以形成新的單詞 another(另一個(gè))?，F(xiàn)在，給定一個(gè)由許多詞根組成的詞典和一個(gè)句子。你需要將句子中的所有繼承詞用詞根替換掉。如果繼承詞有許多可以形成它的詞根，則用最短的詞根替換它。你需要輸出替換之后的句子。

示例 1：
輸入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
輸出："the cat was rat by the bat"
示例 2：
輸入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
輸出："a a b c"
示例 3：
輸入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
輸出："a a a a a a a a bbb baba a"
示例 4：
輸入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
輸出："the cat was rat by the bat"
示例 5：
輸入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
輸出："it is ab that this solution is ac"
提示：
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] 僅由小寫(xiě)字母組成。
1 <= sentence.length <= 10^6
sentence 僅由小寫(xiě)字母和空格組成。
sentence 中單詞的總量在范圍 [1, 1000] 內(nèi)。
sentence 中每個(gè)單詞的長(zhǎng)度在范圍 [1, 1000] 內(nèi)。
sentence 中單詞之間由一個(gè)空格隔開(kāi)。
sentence 沒(méi)有前導(dǎo)或尾隨空格。

思路：我也不知道都是些什么題目，各種奇葩需求可以類(lèi)比于我們現(xiàn)在的甲方。我目前對(duì)這個(gè)題的思路就是詞根存Set。然后只存最終詞根。比如aa,a只存a就行了。然后再遍歷每一個(gè)單詞替換。至于這個(gè)存詞根有個(gè)模糊的想法用前綴樹(shù)。我去實(shí)現(xiàn)下試試。
在我的不懈努力下，打敗了算法的大旗，硬生生用暴力法再次解決了這個(gè)題目，可喜可賀。。哈哈，貼第一版代碼：

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        dictionary.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length() == o2.length()) return 0;
                return o1.length()>o2.length()?1:-1;
            }
        });
        Set<String> set = new HashSet<String>();
        int min = dictionary.get(0).length();
        int max = dictionary.get(0).length();
        for(String s:dictionary) {
            int i = min;
            while(i++<max) {
                if(set.contains(s.substring(0,i))) break; 
            }
            if(i>max) {//說(shuō)明沒(méi)有找到前綴
                max = s.length();
                set.add(s);
            }
        }
        String[] arr = sentence.split(" ");
        StringBuffer sb = new StringBuffer();
        for(String s:arr) {
            sb.append(" ");
            int i = min;
            boolean flag = true;
            while(i<s.length() && i<=max) {
                if(set.contains(s.substring(0,i))) {
                    sb.append(s.substring(0,i));
                    flag =false;
                    break;
                }
                i++;
            }
            if(flag) sb.append(s);
        }
        return sb.toString().substring(1);
    }
}

怎么說(shuō)呢，我一直覺(jué)得這個(gè)題應(yīng)該是用前綴樹(shù)的，但是這個(gè)數(shù)據(jù)量又很小，而且我也著實(shí)用不熟前綴樹(shù)，所以這里依然試了一下暴力法，解決居然ac了，挺開(kāi)心的。不過(guò)為了能不超時(shí)我也做了很多判斷。比如最大值最小值判斷。從最小的前綴開(kāi)始遍歷，還有到了最大的前綴就沒(méi)必要遍歷了。
當(dāng)然了這個(gè)屬于我個(gè)人的執(zhí)念，我覺(jué)得這個(gè)題還是跑不了前綴樹(shù)的，所以我打算用正確的打開(kāi)方式去寫(xiě)一遍了：

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        TreeNode d = new TreeNode();
        for(String s:dictionary) {
            TreeNode cur = d;
            for(char c:s.toCharArray()) {
                if(cur.status) break;
                if(cur.next[c-'a'] == null) cur.next[c-'a'] = new TreeNode();
                cur = cur.next[c-'a'];
            }
            //判斷這個(gè)前綴是不是新的,是的話添加狀態(tài)和單詞
            if(!cur.status) {
                cur.status = true;
                cur.word = s;
            }
        }
        StringBuffer sb = new StringBuffer();
        String[] arr = sentence.split(" ");
        for(String s:arr) {
            sb.append(" ");
            TreeNode cur = d;
            for(char c: s.toCharArray()) {
                if(cur.next[c-'a'] == null || cur.status) break;
                cur = cur.next[c-'a'];
            }
            sb.append(cur.status?cur.word:s);           
        }
        return sb.substring(1).toString();
    }
}
class TreeNode {
    boolean status;//當(dāng)前這個(gè)節(jié)點(diǎn)是不是一個(gè)完整的前綴
    String word;//以這個(gè)節(jié)點(diǎn)為重點(diǎn)的前綴的單詞
    TreeNode[] next;
    TreeNode(){
        next = new TreeNode[26];
    }    
}

怎么說(shuō)呢，暴力法半小時(shí)解決的問(wèn)題用前綴樹(shù)調(diào)試來(lái)調(diào)試去一個(gè)多小時(shí)。大概的思路是有的，寫(xiě)的時(shí)候不順，還是用的少吧。反正這個(gè)代碼性能是上來(lái)了的，超過(guò)了百分之九十的人，也算是及格了。然后只能說(shuō)最終寫(xiě)完之后對(duì)前綴樹(shù)更加熟悉了？感覺(jué)也不是啊，寫(xiě)了好多遍還會(huì)不熟。。。反正這個(gè)題就這樣了，會(huì)了暴力法的話前綴樹(shù)仔細(xì)看下就能懂的。下一題。

單調(diào)遞增的數(shù)字

題目：給定一個(gè)非負(fù)整數(shù) N，找出小于或等于 N 的最大的整數(shù)，同時(shí)這個(gè)整數(shù)需要滿足其各個(gè)位數(shù)上的數(shù)字是單調(diào)遞增。（當(dāng)且僅當(dāng)每個(gè)相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時(shí)，我們稱這個(gè)整數(shù)是單調(diào)遞增的。）

示例 1:
輸入: N = 10
輸出: 9
示例 2:
輸入: N = 1234
輸出: 1234
示例 3:
輸入: N = 332
輸出: 299
說(shuō)明: N 是在 [0, 10^9] 范圍內(nèi)的一個(gè)整數(shù)。

思路：這個(gè)是今天的每日一題，萬(wàn)惡的是我在還沒(méi)做的時(shí)候就看到群友討論這個(gè)題目了，據(jù)說(shuō)看數(shù)據(jù)范圍就能看出來(lái)這個(gè)是數(shù)學(xué)題而不是算法題。然后還說(shuō)用數(shù)組解決了。。。有種被劇透了的感覺(jué)，簡(jiǎn)直是。。。反正按照這個(gè)思路走也沒(méi)啥問(wèn)題。換成數(shù)組，然后從前往后遍歷，如果后面的比前面的大，前面的退一位。然后后面的都可以補(bǔ)9了。就醬。我去試試代碼。
第一版本代碼直接ac，果然有了思路就是不一樣，當(dāng)然也可能是這個(gè)題比較簡(jiǎn)單。然后在實(shí)現(xiàn)的時(shí)候又有了點(diǎn)新思路：其實(shí)只要記錄開(kāi)始借位的最高位就可以了，后面一律補(bǔ)9。然后就是下面的代碼：

class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] c = Integer.valueOf(N).toString().toCharArray();
        int idx = c.length-1;
        for(int i = c.length-1;i>0;i--) {
            //非遞增了，所以要借位
            if(c[i]<c[i-1]) {
                c[i-1]--;
                idx = i-1;//記錄最后一個(gè)被借位的下標(biāo)
            }
        }
        int res = 0;
        for(int i = 0;i<=idx;i++) {
            res = res*10+(c[i]-'0');
        }
        for(int i = idx+1;i<c.length;i++) {
            res = res*10+9;
        }
        return res;
    }
}

這個(gè)性能超過(guò)百分之九十七了，我感覺(jué)應(yīng)該是正解的思路，因?yàn)檫@個(gè)題比較簡(jiǎn)單，所以我也不多說(shuō)了，去看一眼性能排行第一的代碼：

class Solution {
    public int monotoneIncreasingDigits(int N) {
        int rs = 0, exp = 1, p = 10;
        while (N > 0) {
            int t = N % 10;
            if (t <= p) {
                rs += t * exp;
                p = t;
            }
            else {
                rs = t * exp - 1;
                p = t - 1;
            }
            N /= 10;
            exp *= 10;
        }
        return rs;
    }
}

只能說(shuō)同樣都是做出來(lái)，但是水平還是不一樣的。我的做法換成數(shù)組，而且是先完全的把每個(gè)元素算出來(lái)，再去拼數(shù)字。但是人家的代碼一次到位。首先exp記錄當(dāng)前位數(shù)。然后如果順著往下就順著加沒(méi)問(wèn)題，但是精巧的是如果發(fā)現(xiàn)第一位要被借位了，直接-1自動(dòng)生成X9999。。。簡(jiǎn)直精妙的不行。嘆為觀止，一看就會(huì)，一寫(xiě)就廢那種。膜拜一波然后下一題了。

只有兩個(gè)鍵的鍵盤(pán)

題目：最初在一個(gè)記事本上只有一個(gè)字符 'A'。你每次可以對(duì)這個(gè)記事本進(jìn)行兩種操作：

• Copy All (復(fù)制全部) : 你可以復(fù)制這個(gè)記事本中的所有字符(部分的復(fù)制是不允許的)。

• Paste (粘貼) : 你可以粘貼你上一次復(fù)制的字符。

給定一個(gè)數(shù)字 n 。你需要使用最少的操作次數(shù)，在記事本中打印出恰好 n 個(gè) 'A'。輸出能夠打印出 n 個(gè) 'A' 的最少操作次數(shù)。

示例 1:
輸入: 3
輸出: 3
解釋:
最初, 我們只有一個(gè)字符 'A'。
第 1 步, 我們使用 Copy All 操作。
第 2 步, 我們使用 Paste 操作來(lái)獲得 'AA'。
第 3 步, 我們使用 Paste 操作來(lái)獲得 'AAA'。
說(shuō)明:
n 的取值范圍是 [1, 1000] 。

思路：這個(gè)題，先不說(shuō)這個(gè)鍵盤(pán)是不是應(yīng)該換，單純的說(shuō)題目。我感覺(jué)是有一定規(guī)律的。比如說(shuō)復(fù)制粘貼肯定是質(zhì)數(shù)個(gè)，不然的話完全可以拆分出來(lái)的。比如a變aaaa的話，完全可以先粘貼變成1個(gè)，再粘貼變成2個(gè)，再?gòu)?fù)制兩個(gè)，再粘貼，就是4個(gè)了。這樣也是四個(gè)。主要的思路就是能不能除2.能除開(kāi)的話直接變成除2的值，再?gòu)?fù)制，粘貼。兩步就完事了。同理能被3整除的話，復(fù)制，粘貼粘貼三步。感覺(jué)有模糊的思路，我去試試代碼。
第一版本就超過(guò)百分百了，撒花~~
這個(gè)題怎么說(shuō)呢，我感覺(jué)只要思路順就很容易寫(xiě)。首先如果是質(zhì)數(shù)的話只能一個(gè)一個(gè)復(fù)制粘貼，所以就是n次操作。
如果不是質(zhì)數(shù)的話，肯定是要找上一個(gè)能湊成的數(shù)，然后復(fù)制粘貼幾次才能成為當(dāng)前的數(shù)字。重點(diǎn)是復(fù)制算一步操作，粘貼（i-1）。所以應(yīng)該是多了1+i-1步驟，也就是多了i步。就這樣遞歸下去就ok了。

class Solution {
    public int minSteps(int n) {
        if(n == 1) return 0;
        //質(zhì)數(shù)是他本身，因?yàn)椴荒苋魏螐?fù)制。否則化簡(jiǎn)到質(zhì)數(shù)。
        int res = 0;
        for(int i = 2; i <= Math.sqrt(n); i++){ 
            if(n%i == 0) {
                //這里加i的原因是復(fù)制算一步，然后粘貼i-1個(gè)。所以一共是i步
                return minSteps(n/i)+i;
            }
        }
        return n;
    }
}

因?yàn)檫@道題性能也最好了，并且思路也清晰，所以不看性能第一的代碼了，直接下一題。

尋找重復(fù)的子樹(shù)

題目：給定一棵二叉樹(shù)，返回所有重復(fù)的子樹(shù)。對(duì)于同一類(lèi)的重復(fù)子樹(shù)，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可。兩棵樹(shù)重復(fù)是指它們具有相同的結(jié)構(gòu)以及相同的結(jié)點(diǎn)值。

題目截圖

思路：這個(gè)題怎么說(shuō)呢，本來(lái)一看樹(shù)我以為會(huì)很簡(jiǎn)單，但是審?fù)觐}覺(jué)得還是挺復(fù)雜的。首先這個(gè)題二叉樹(shù)的全等有點(diǎn)復(fù)雜了吧？一層一層迭代？肯定不咋現(xiàn)實(shí)。我目前的想法是換成字符串來(lái)比較。這樣重點(diǎn)就是遍歷樹(shù)，我這里比較推薦中序遍歷。每個(gè)節(jié)點(diǎn)都自成一個(gè)字符串。最終比較字符串的全等就行了。思路不清楚但是有點(diǎn)想法，我去實(shí)現(xiàn)下看看。
第一版本的ac代碼，各種修修改改。尤其是測(cè)試案例會(huì)順序不同，好麻煩的說(shuō)：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<String,Integer> map = new HashMap<String,Integer>();
    List<TreeNode> list = new ArrayList<TreeNode>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return list;
    }
    public String dfs(TreeNode root) {  
        if(root == null) return "#";    
        StringBuffer tree = new StringBuffer();
        tree.append(root.val);
        tree.append("left:"+dfs(root.left));
        tree.append("right:"+ dfs(root.right));
        String res = tree.toString();
        map.put(res, map.getOrDefault(res,0)+1);    
        if(map.get(res)==2) list.add(root);
        return res;
    }
}

大概的思路就是序列化來(lái)判斷是不是相同結(jié)構(gòu)。重點(diǎn)是如果是相同結(jié)構(gòu)要直接保存這個(gè)樹(shù)。一開(kāi)始這里我居然試圖保存序列化然後反序列化回來(lái)，當(dāng)然后來(lái)發(fā)現(xiàn)這個(gè)難度就轉(zhuǎn)換思路了。然後本來(lái)我用stringbuffer的原因是判斷是否有左右樹(shù)，沒(méi)有不append的。。但是事實(shí)證明那樣是有問(wèn)題的（什么問(wèn)題不知道，測(cè)試案例174，一大串東西我也懶得反序列化了）。所以就用#來(lái)做占位符了。反正這樣意思也是一樣的。然後這個(gè)代碼除了性能不好沒(méi)啥去缺點(diǎn)了，也挺精簡(jiǎn)的。剩下的我去看看性能排行第一的代碼吧:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> ans = new ArrayList<>();
        lookup(root, new HashMap<>(), ans);
        return ans;
    }

    private long lookup(TreeNode node, Map<Long, Integer> map, List<TreeNode> ans) {
        if (node == null) {
            return 31;
        }
        long val = node.val + 5381;
        long left = lookup(node.left, map, ans);
        long right = lookup(node.right, map, ans);
        long hash = val + val * left + val * left * right;
        if (map.merge(hash, 1, Integer::sum) == 2) {
            ans.add(node);
        }
        return hash;
    }
}

簡(jiǎn)單說(shuō)一下這個(gè)做法，大體思路是差不多的，但是我這里是用序列化的字符串來(lái)判斷是不是出現(xiàn)了，人家這是用hash來(lái)作為唯一標(biāo)識(shí)的？反正能理解這個(gè)思路，看不懂這個(gè)代碼，想不到這個(gè)思維，over~

最大二叉樹(shù)

題目：給定一個(gè)不含重復(fù)元素的整數(shù)數(shù)組。一個(gè)以此數(shù)組構(gòu)建的最大二叉樹(shù)定義如下：

二叉樹(shù)的根是數(shù)組中的最大元素。

左子樹(shù)是通過(guò)數(shù)組中最大值左邊部分構(gòu)造出的最大二叉樹(shù)。

右子樹(shù)是通過(guò)數(shù)組中最大值右邊部分構(gòu)造出的最大二叉樹(shù)。

通過(guò)給定的數(shù)組構(gòu)建最大二叉樹(shù)，并且輸出這個(gè)樹(shù)的根節(jié)點(diǎn)。

題目截圖

思路：這個(gè)審?fù)觐}就第一反應(yīng)：遞歸，樹(shù)狀神操作。絕對(duì)的遞歸沒(méi)跑了。首先找到這個(gè)數(shù)組的最大值。這個(gè)值的左邊遞歸左樹(shù)，右邊遞歸右樹(shù)。直到兩邊沒(méi)有元素。我去擼代碼。
第一版本直接ac，性能超過(guò)百分百：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length-1);        
    }
    public TreeNode dfs(int[] nums,Integer start,Integer end) {
        if(start == end) return new TreeNode(nums[start]);
        int max = start;
        for(int i = start+1;i<=end;i++) {
            if(nums[i]>nums[max]) max = i;
        }
        TreeNode res = new TreeNode(nums[max]);
        if(max != start)res.left = dfs(nums, start, max-1);
        if(max != end) res.right = dfs(nums, max+1, end);
        return res;
    }
}

這種簡(jiǎn)單的樹(shù)狀題目還是很好寫(xiě)的，幾乎遇到樹(shù)想遞歸沒(méi)啥毛病，尤其是這道題樹(shù)中樹(shù)的題目。
本片筆記就記到這里了，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注。也祝大家工作順順利利，另外最近刷題越來(lái)越多的我覺(jué)得很簡(jiǎn)單的思路或者寫(xiě)法我都懶得寫(xiě)解釋了，昨天群里還有人吐槽我寫(xiě)的筆記只能自己看懂。。emmm...如果親看了我記下的題目但是還覺(jué)得沒(méi)懂可以評(píng)論或者私信我哈，我也是算法小白，但是能保證記錄下來(lái)的題起碼自己是理解了的~就醬！