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

三角形最小路径和

题目：给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

思路：额，这个我目前的思路就是遍历整个三角。总能找出路径最小的，至于进阶条件只使用O（n）额外空间先实现再优化吧。其实我仔细看了下，这个三角形好像是可以理解成从下到上的动归、每次往上到上一层节点，都会有上一层节点数最小的可能。比如第四层到第三层，则只会有三个可能。以6为根的6+1=7（因为6+4>7，所以直接pass），以5为根的5+1=6.以7为根的7+3=10.同理再往上一层，则变成了两种选择：以3 为根的3+6=9（因为3+7大于9，所以pass），以4为根的4+6=10.最后到了第一层变成2+9=11是最小值。我不知道我叙述明白了没有，但是这个一定是要从后往前dp。我去代码实现下。
我写完了才发现我特么这个算法就是只使用O（n）的额外空间啊？！！！！有点小骄傲呢~~我直接贴代码：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size()-1;
        if(len<0) return 0;
        if(len<1) return triangle.get(0).get(0); 
        int[] p = new int[triangle.get(len).size()];
        for(int i = 0; i<p.length; i++ ){
            p[i] = triangle.get(len).get(i);
        }
        for(int i = len-1; i>0; i--){
            int size = triangle.get(i).size();
            for(int j = 0; j<size; j++){
                //到下面的数字的最小值
                int down = triangle.get(i).get(j)+p[j];
                //到斜下面的数字的最小值
                int recline = triangle.get(i).get(j)+p[j+1];
                p[j] = Math.min(down,recline);
            }
        }
        return Math.min(p[0]+triangle.get(0).get(0),p[1]+triangle.get(0).get(0));
    }
}

讲真，我觉得这个题目如果给定的不是list<list>而是二维数组性能会好很多，而且代码也会更简洁。。。反正我这个思路是没问题的，而且额外空间也是符合要求的，至于为什么性能不咋地，我觉得也就是一些小细节没处理好。我去小修一下。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size()-1;
        if(len<0) return 0;
        int[] p = new int[triangle.get(len).size()+1];
        for(int i = len; i>=0; i--){
            int size = triangle.get(i).size();
            for(int j = 0; j<size; j++){
                //到下面的数字的最小值
                int down = triangle.get(i).get(j)+p[j];
                //到斜下面的数字的最小值
                int recline = triangle.get(i).get(j)+p[j+1];
                p[j] = Math.min(down,recline);
            }
        }
        return p[0];
    }
}

修改完了 的代码性能好点了，但是依然不及格，我直接看看性能排行第一的代码吧。

class Solution {
    int rows = 0;
    int[][] dp;    
    public int solve(List<List<Integer>> triangle, int row, int col) {
        if (row==rows-1){
        return triangle.get(row).get(col);
        } else {
            if(dp[row][col] != 0) {
                return dp[row][col];
            }
            int tmp = triangle.get(row).get(col);
            int left = solve(triangle, row + 1, col);
            int right = solve(triangle, row + 1, col + 1);
            dp[row][col] = Math.min(left, right) + tmp;
            return dp[row][col];
        }
    }
    public int minimumTotal(List<List<Integer>> triangle) {
        rows = triangle.size();
        dp = new int[rows][rows];
        return solve(triangle, 0, 0);
    }
}

说真的， 这个不能算是O（n）额外空间吧？应该是n方吧？
不管了，反正思路也就这样。下一题吧。

单词接龙

题目：给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。

思路：这个题题目很复杂啊。语言表述不少，但是做起来应该不难。首先有一点注意的：不应该出现来回来去重复选取的情况。比如hot-dot,再找dot的只差一个字母的单词时就不能选择hot了。所以这里应该是用标记的。相比于下标代替下标，数值代表状态（初始0是没用过，用过改成-1）我更倾向于直接用个boolean数组来表示状态。然后我去尝试写代码了。
好了，实现是实现了，但是性能有点问题，我先贴出代码再优化：

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //字典中没有endword直接返回0
        if(wordList.indexOf(endWord)==-1) return 0;
        Queue<String> queue = new LinkedList<String>();
        queue.offer(beginWord);
        int count = 0;
        while(!queue.isEmpty()){//当queue为空说明到不了endword了  
            count++;    
            int size = queue.size();
            for(int j = 0;j<size;j++){
                String s = queue.poll();
                for(int i = wordList.size()-1;i>=0;i--){    
                    String temp = wordList.get(i);         
                    if(canConvert(s,temp)){
                        if(endWord.equals(temp)){
                            return count+1;
                        }else{
                            queue.offer(temp);
                            wordList.remove(i);
                        }
                    }
                }
                            
            }                 
        }
        return 0;
    }
    //只有一个字母不同才算是演变单词
    public boolean canConvert(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1.charAt(i) != s2.charAt(i)) {
                ++count;
                if (count > 1) {
                    return false;
                }
            }
        }
        return count == 1;
    }
}

首先在做的过程中有些和思路不一样的修改，本来我是打算用标记来去除重复选项的。但是后来觉得挺没意义的，既然选过一次就不能再选了，还不如直接删除呢，然后就是以上代码的逻辑（因为有删除，所以从后往前遍历了。）
首先代码580ms，其实可以想象，因为这个确实是一个乘积的时间复杂度。。其次先入先出习惯用队列了，其实list也完全可以实现的。并且我怀疑换成list性能会比现在好，但是这个应该不是问题的主要吧，其实下面这个我觉得也这个charAt也可以换换，换成数组比较字符会不会好点？我改一下试试。
我的难受无以言表，兴致冲冲改了点细节，然后从几百到上千ms。。。但是我也要把改版的贴出来，毕竟也是劳动成果：

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //字典中没有endword直接返回0
        if(wordList.indexOf(endWord)==-1) return 0;
        LinkedList<String> list = new LinkedList<String>();
        list.add(beginWord);
        int count = 0;
        while(list.size()!=0){//当queue为空说明到不了endword了  
            count++;    
            int size = list.size();
            for(int j = 0;j<size;j++){
                String s = list.removeFirst();
                for(int i = wordList.size()-1;i>=0;i--){    
                    String temp = wordList.get(i);         
                    if(canConvert(s.toCharArray(),temp.toCharArray())){
                        if(endWord.equals(temp)){
                            return count+1;
                        }else{
                            list.add(temp);
                            wordList.remove(i);
                        }
                    }
                }                            
            }                 
        }
        return 0;
    }
    //只有一个字母不同才算是演变单词
    public boolean canConvert(char[] c1,char[] c2) {
        int count = 0;
        for (int i = 0; i < c1.length; i++) {
            if (c1[i]!=c2[i]) {
                ++count;
                if (count > 1) {
                    return false;
                }
            }
        }
        return true;
    }
}

然后我直接去看性能排行第一的代码了，我已经放弃优化了。
额，看完了，人家的注解很详细，并且逻辑很简单，属于一看就懂，一写就懵的那种，我直接贴出来膜拜下：

/**
 * 在提交里看到的最优解，看懂了，解读一下分享出来：
 * 需要掌握的知识递进：
 * 1.BFS。
 * 2.双端BFS。
 * 3.临近点查找方式：
 * 首先将所有的字符存到结构为HashSet的dic字典里去，然后将字符串的每一位挨个从a变到z,
 * 在变化的时候实时去字典里查，因为是hashset，所以复杂度是O(1)，非常快。
 * 如果查到了，则就是找到了临近点。
 */
class Solution {
    //递归
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0) return 0;
        //hashset的好处：去重也完成了
        //开始端
        HashSet<String> start = new HashSet<>();
        //结束端
        HashSet<String> end = new HashSet<>();
        //所有字符串的字典
        HashSet<String> dic = new HashSet<>(wordList);
        start.add(beginWord);
        end.add(endWord);
        if (!dic.contains(endWord)) return 0;
        //经历过上面的一系列判定，到这里的时候，若是有路径，则最小是2，所以以2开始
        return bfs(start, end, dic, 2);

    }

    public int bfs(HashSet<String> st, HashSet<String> ed, HashSet<String> dic, int l) {
        //双端查找的时候，若是有任意一段出现了“断裂”，也就是说明不存在能够连上的路径，则直接返回0
        if (st.size() == 0) return 0;
        if (st.size() > ed.size()) {//双端查找，为了优化时间，永远用少的去找多的，比如开始的时候塞进了1000个，而结尾只有3个，则肯定是从少的那一端开始走比较好
            return bfs(ed, st, dic, l);
        }
        //BFS的标记行为，即使用过的不重复使用
        dic.removeAll(st);
        //收集下一层临近点
        HashSet<String> next = new HashSet<>();
        for (String s : st) {
            char[] arr = s.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                char tmp = arr[i];
                //变化
                for (char c = 'a'; c <= 'z'; c++) {
                    if (tmp == c) continue;
                    arr[i] = c;
                    String nstr = new String(arr);
                    if (dic.contains(nstr)) {
                        if (ed.contains(nstr)) return l;
                        else next.add(nstr);
                    }
                }
                //复原
                arr[i] = tmp;
            }
        }
        return bfs(next, ed, dic, l + 1);
    }

}

讲真，他这个性能，我不懂为啥这么比较会比两个单词的比较性能高。。。我总怀疑是测试案例的问题。有大佬明白的也请指点下。。然后下一题了。

求根到叶子节点数字之和

题目：给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。说明: 叶子节点是指没有子节点的节点。

示例 1:
输入: [1,2,3]
1
/
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:
输入: [4,9,0,5,1]
4
/
9 0
/
5 1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

思路：额，我觉得这道题好像挺简单啊，我个人是打算用list存路径，然后遍历树，最后得出list<list>,再以数字的形式相加。。我不知道有没有坑，我先去实现看看。
哎，我这一言难尽的小性能啊，写完我就觉得有改善的空间，不过先提交了下测试思路对不对，所以第一版本代码毕竟是劳动成果，先贴出来了：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> list;
    public int sumNumbers(TreeNode root) {
        list = new ArrayList<List<Integer>>();
        dfs(new ArrayList(),root);
        int sum = 0;
        for(List<Integer> l : list){
            int count = 0;
            for(int i : l){
                count = count*10+i;
            }
            sum += count;
        }
        return sum;
    }
    public void dfs(List<Integer> path, TreeNode root){
        if(root==null) return;
        path.add(root.val);
        //遍历到叶子节点了
        if(root.left==null && root.right==null){
            list.add(path);
            return;
        }
        dfs(new ArrayList(path),root.left);
        dfs(new ArrayList(path),root.right);
    }
}

然后我去优化了。好了，优化版本来了：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> list;
    public int sumNumbers(TreeNode root) {
        list = new ArrayList<Integer>();
        dfs(0,root);
        int sum = 0;
        for(int i : list){
            sum += i;
        }
        return sum;
    }
    public void dfs(int sum, TreeNode root){
        if(root==null) return;
        sum = sum*10 + root.val;
        //遍历到叶子节点了
        if(root.left==null && root.right==null){
            list.add(sum);
            return;
        }
        dfs(sum,root.left);
        dfs(sum,root.right);
    }
}

从 3ms 到1ms，进步挺大的，就是排名上不去。。我直接去看性能排行第一的代码吧：
哎，这个我应该可以会的，怪我没静下心来，其实第一的代码比我多处理了一下，上面我的优化版还是用的list记录每一条路径的和，最后相加，其实这里可以直接存总路径。我直接贴代码了：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res;
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;
        dfs(0,root);
        return res;
    }
    public void dfs(int sum, TreeNode root){
        if(root==null) return;
        sum = sum*10 + root.val;
        //遍历到叶子节点了
        if(root.left==null && root.right==null){
            res += sum;
            return;
        }
        dfs(sum,root.left);
        dfs(sum,root.right);
    }
}

这道题是真的怪我，有点着急了，算是个教训吧。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！！