leetCode进阶算法题+解析（六十二）

回文子串

题目：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

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

当然了是低空略过，所以这个实现绝对不应该这么暴力遍历，我再想想怎么用一些算法来解决这个题吧：

class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        char[] c = s.toCharArray();
        for(int i = 0;i<c.length;i++) {
            //以当前元素为中心的回文串
            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;
    }
}

也没用啥算法，就是换了个思路。之前的话是从某个位置开始作为回文串的左起始点。其实这个比较麻烦的就是很多时候要做无用功。换了个思路找到回文串的中间点（单数是中间那个。双数是中间两个中靠前那个）。这样当发现这个作为中点不符合要求可以直接跳过判断了，可以少做很多无用功。然后这个代码的性能超过百分之九十六的人，所以这个题就这样过了。下一题吧。

单词替换

题目：在英语中，我们有一个叫做词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。你需要输出替换之后的句子。

示例 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] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。

思路：我也不知道都是些什么题目，各种奇葩需求可以类比于我们现在的甲方。我目前对这个题的思路就是词根存Set。然后只存最终词根。比如aa,a只存a就行了。然后再遍历每一个单词替换。至于这个存词根有个模糊的想法用前缀树。我去实现下试试。
在我的不懈努力下，打败了算法的大旗，硬生生用暴力法再次解决了这个题目，可喜可贺。。哈哈，贴第一版代码：

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

怎么说呢，我一直觉得这个题应该是用前缀树的，但是这个数据量又很小，而且我也着实用不熟前缀树，所以这里依然试了一下暴力法，解决居然ac了，挺开心的。不过为了能不超时我也做了很多判断。比如最大值最小值判断。从最小的前缀开始遍历，还有到了最大的前缀就没必要遍历了。
当然了这个属于我个人的执念，我觉得这个题还是跑不了前缀树的，所以我打算用正确的打开方式去写一遍了：

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'];
            }
            //判断这个前缀是不是新的,是的话添加状态和单词
            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;//当前这个节点是不是一个完整的前缀
    String word;//以这个节点为重点的前缀的单词
    TreeNode[] next;
    TreeNode(){
        next = new TreeNode[26];
    }    
}

怎么说呢，暴力法半小时解决的问题用前缀树调试来调试去一个多小时。大概的思路是有的，写的时候不顺，还是用的少吧。反正这个代码性能是上来了的，超过了百分之九十的人，也算是及格了。然后只能说最终写完之后对前缀树更加熟悉了？感觉也不是啊，写了好多遍还会不熟。。。反正这个题就这样了，会了暴力法的话前缀树仔细看下就能懂的。下一题。

单调递增的数字

题目：给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:
输入: N = 10
输出: 9
示例 2:
输入: N = 1234
输出: 1234
示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

思路：这个是今天的每日一题，万恶的是我在还没做的时候就看到群友讨论这个题目了，据说看数据范围就能看出来这个是数学题而不是算法题。然后还说用数组解决了。。。有种被剧透了的感觉，简直是。。。反正按照这个思路走也没啥问题。换成数组，然后从前往后遍历，如果后面的比前面的大，前面的退一位。然后后面的都可以补9了。就酱。我去试试代码。
第一版本代码直接ac，果然有了思路就是不一样，当然也可能是这个题比较简单。然后在实现的时候又有了点新思路：其实只要记录开始借位的最高位就可以了，后面一律补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;//记录最后一个被借位的下标
            }
        }
        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;
    }
}

这个性能超过百分之九十七了，我感觉应该是正解的思路，因为这个题比较简单，所以我也不多说了，去看一眼性能排行第一的代码：

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

只能说同样都是做出来，但是水平还是不一样的。我的做法换成数组，而且是先完全的把每个元素算出来，再去拼数字。但是人家的代码一次到位。首先exp记录当前位数。然后如果顺着往下就顺着加没问题，但是精巧的是如果发现第一位要被借位了，直接-1自动生成X9999。。。简直精妙的不行。叹为观止，一看就会，一写就废那种。膜拜一波然后下一题了。

只有两个键的键盘

题目：最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。

给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。

示例 1:
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 'A'。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 'AA'。
第 3 步, 我们使用 Paste 操作来获得 'AAA'。
说明:
n 的取值范围是 [1, 1000] 。

思路：这个题，先不说这个键盘是不是应该换，单纯的说题目。我感觉是有一定规律的。比如说复制粘贴肯定是质数个，不然的话完全可以拆分出来的。比如a变aaaa的话，完全可以先粘贴变成1个，再粘贴变成2个，再复制两个，再粘贴，就是4个了。这样也是四个。主要的思路就是能不能除2.能除开的话直接变成除2的值，再复制，粘贴。两步就完事了。同理能被3整除的话，复制，粘贴粘贴三步。感觉有模糊的思路，我去试试代码。
第一版本就超过百分百了，撒花~~
这个题怎么说呢，我感觉只要思路顺就很容易写。首先如果是质数的话只能一个一个复制粘贴，所以就是n次操作。
如果不是质数的话，肯定是要找上一个能凑成的数，然后复制粘贴几次才能成为当前的数字。重点是复制算一步操作，粘贴（i-1）。所以应该是多了1+i-1步骤，也就是多了i步。就这样递归下去就ok了。

class Solution {
    public int minSteps(int n) {
        if(n == 1) return 0;
        //质数是他本身，因为不能任何复制。否则化简到质数。
        int res = 0;
        for(int i = 2; i <= Math.sqrt(n); i++){ 
            if(n%i == 0) {
                //这里加i的原因是复制算一步，然后粘贴i-1个。所以一共是i步
                return minSteps(n/i)+i;
            }
        }
        return 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;
    }
}

大概的思路就是序列化来判断是不是相同结构。重点是如果是相同结构要直接保存这个树。一开始这里我居然试图保存序列化然後反序列化回来，当然后来发现这个难度就转换思路了。然後本来我用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;
    }
}

简单说一下这个做法，大体思路是差不多的，但是我这里是用序列化的字符串来判断是不是出现了，人家这是用hash来作为唯一标识的？反正能理解这个思路，看不懂这个代码，想不到这个思维，over~

最大二叉树

题目：给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。

左子树是通过数组中最大值左边部分构造出的最大二叉树。

右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。