回文子串

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

示例 1：
輸入："abc"
輸出：3
解釋：三個回文子串: "a", "b", "c"
示例 2：
輸入："aaa"
輸出：6
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
輸入的字符串長度不會超過 1000 。

思路：這個題我覺得最簡單的辦法就是暴力遍歷。每個元素都往后遍歷出所有的回文串。長度不超過1000，也就是全遍歷也不超過1000000。我先去試試。超時了再說算法什么的。
暴力法居然沒超時。。這個題有點東西啊，我先附上代碼：

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)然了是低空略過，所以這個實現(xiàn)絕對不應(yīng)該這么暴力遍歷，我再想想怎么用一些算法來解決這個題吧：

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

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

單詞替換

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

示例 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] 僅由小寫字母組成。
1 <= sentence.length <= 10^6
sentence 僅由小寫字母和空格組成。
sentence 中單詞的總量在范圍 [1, 1000] 內(nèi)。
sentence 中每個單詞的長度在范圍 [1, 1000] 內(nèi)。
sentence 中單詞之間由一個空格隔開。
sentence 沒有前導(dǎo)或尾隨空格。

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

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) {//說明沒有找到前綴
                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);
    }
}

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

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'];
            }
            //判斷這個前綴是不是新的,是的話添加狀態(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)前這個節(jié)點是不是一個完整的前綴
    String word;//以這個節(jié)點為重點的前綴的單詞
    TreeNode[] next;
    TreeNode(){
        next = new TreeNode[26];
    }    
}

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

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

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

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

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

這個性能超過百分之九十七了，我感覺應(yīng)該是正解的思路，因為這個題比較簡單，所以我也不多說了，去看一眼性能排行第一的代碼：

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

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

只有兩個鍵的鍵盤

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

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

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

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

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

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

class Solution {
    public int minSteps(int n) {
        if(n == 1) return 0;
        //質(zhì)數(shù)是他本身，因為不能任何復(fù)制。否則化簡到質(zhì)數(shù)。
        int res = 0;
        for(int i = 2; i <= Math.sqrt(n); i++){ 
            if(n%i == 0) {
                //這里加i的原因是復(fù)制算一步，然后粘貼i-1個。所以一共是i步
                return minSteps(n/i)+i;
            }
        }
        return n;
    }
}

因為這道題性能也最好了，并且思路也清晰，所以不看性能第一的代碼了，直接下一題。

尋找重復(fù)的子樹

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

題目截圖

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

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

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

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

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

最大二叉樹

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

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

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

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

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

題目截圖

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

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

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