leetCode进阶算法题+解析(五十五)

原来是闲了的时候刷刷题,现在是忙的时候挤出时间刷刷题,心态的变化让我觉得其实一天能自由支配的时间还是挺多的,哈哈。

出现次数最多的子树元素和

题目:给你一个二叉树的根结点,请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。
题目描述

思路:我现在一脸羞愧。第一遍没看明白题意,还欠了吧唧的给提了个反馈以为是翻译有问题。哎,现在开始说这个题,简单来说我觉得单纯的暴力法也还是可以的。不考虑性能问题的话,就是每个子树和都存上,最后选择出现次数最多的那个。然后其实这里可以有递归实现吧。我去试试。反正我目前的想法就是暴力法,我去实现看看。
过是过了,性能反正就那样吧。

/**
* 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[] findFrequentTreeSum(TreeNode root) {
       list = new ArrayList<Integer>();
       dfs(root);
       int[][] num = new int[list.size()][2];//计数数组,不会大于list的长度
       Collections.sort(list);
       int n = 1;
       int idx = 0; 
       for(int i = 0;i<list.size();i++) {
           //当前元素的值
           num[idx][0] = list.get(i);
           //和前面元素相同。因为是Integer,所以要用equals
           while(i<list.size() && i>0 && list.get(i).equals(list.get(i-1))) {
               i++;//继续往下判断
               n++;//相同元素+1了
           }
           //当前元素的个数。这个num的下标其实和list2的下标是对应的
           num[idx][1] = n;
           //走到这说明当前元素不同了,计数归1
           n = 1;
           idx++;
       }
       //找出出现最多的次数
       int max = 0;
       for(int[] i : num) {
           if(i[1] == 0) break;//正常计数不可能是0,到0说明后面都没用到
           max =Math.max(max, i[1]);
       }
       List<Integer> list2 = new ArrayList<Integer>();
       for(int[] i :num) {
           if(i[1] == 0) break;
           if(i[1] == max) list2.add(i[0]);
       }
       int[] res = new int[list2.size()];
       for(int i = 0;i<list2.size();i++) {
           res[i] = list2.get(i);
       }
       return res;
   }

   public int dfs(TreeNode root){
       if(root==null) return 0;//如果这个节点没有则是0
       //不是叶子节点,要去计算左右+当前的和
       if(root.left!=null || root.right!=null){
           int l = dfs(root.left);
           int r = dfs(root.right);
           list.add(l+r+root.val);
           return l+r+root.val;
       }else{
           list.add(root.val);//这个叶子节点算是单独的一个和
           return root.val;
       }
   }
}

我其实本来想用hash的,但是以为数组型数组会更好,反正是觉得我写麻烦了,我再换种方式试试。
小小的修改了一下,ac了并且性能超过百分之八十八,算是合格了吧:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer,Integer> map;
    public int[] findFrequentTreeSum(TreeNode root) {
        map = new HashMap<Integer,Integer>();
        dfs(root);
        int max = 0;
        for(Integer i:map.values()) {
            max = Math.max(max, i);
        }
        List<Integer> list = new ArrayList<Integer>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if(entry.getValue() == max) list.add(entry.getKey());
        }
        int[] res = new int[list.size()];
        for(int i = 0;i<list.size();i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public int dfs(TreeNode root){
        if(root==null) return 0;//如果这个节点没有则是0
        //计算左右+当前的和
        int val = dfs(root.left)+dfs(root.right)+root.val;
        if(map.get(val)!=null){
            map.put(val,map.get(val)+1);
        }else{
            map.put(val,1);
        }
        return val;
    }
}

这道题其实就是处理比较麻烦,但是还是比较容易做的,不多说了,下一题了。

找树左下角的值

题目:给定一个二叉树,在树的最后一行找到最左边的值。
题目

思路:不是,我不知道这个题是怎么混到中等难度的。难道不是简单题目么?层次遍历。取最后一层第一个不就行了?难道会卡在性能上?或者说有什么最优的解法?我先去按照我的想法实现下试试。
想法没问题,性能超过百分之七十,直接贴代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int res = root.val;
        while(!queue.isEmpty()){
            //获取每一层的第一个元素
            res = queue.peek().val;
            int size = queue.size();
            for(int i = 0;i<size;i++) {
                TreeNode temp = queue.poll();
                if(temp.left!=null) queue.add(temp.left);
                if(temp.right!=null) queue.add(temp.right);
            }
        }
        return res;
    }
}

真的,这个题我觉得也就简单难度,看看性能排行第一的有什么优解吧:

class Solution {
    //找最深的一层
    int max = -1;
    int value = 0;

    public int findBottomLeftValue(TreeNode root) {
        get(root,0);
        return value;
    }

    public void get(TreeNode node,int num){
        if(node==null){
            return;
        }
        //第一次大于的时候就是每层最左边的节点
        if(num>max){
            max = num;
            value = node.val;
        }
        get(node.left,num+1);
        get(node.right,num+1);

    }
}

直接用深搜。因为是大于max才会替换,所以最下层有多个也不怕,简单明了,感觉这个题思路清晰就没啥问题了,下一题吧。

在每个树行中找到最大值

题目:您需要在二叉树的每一行中找到最大的值。
题目截图

思路:又是一个送分题,其实上面那个答案稍微变化一下就是这个了,两种方法都可以。一个是层次遍历,每个多一层找当前层的最大值。还有一种就是深搜。每一层都保存最大值。没啥好解释的,我去写代码了。
稍微改了一下上一题的代码就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 {
    public List<Integer> largestValues(TreeNode root) {       
        List<Integer> res = new ArrayList<Integer>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for(int i = 0;i<size;i++) {             
                TreeNode temp = queue.poll();
                max = Math.max(max, temp.val);
                if(temp.left!=null) queue.add(temp.left);
                if(temp.right!=null) queue.add(temp.right);
            }
            res.add(max);
        }
        return res;
    }
}

其实深搜也可以实现的,换种思路写下这道题:
!!!我简直日狗了,一个坑栽了两次,又没判断root==null。第二遍过的。贴代码:

/**
 * 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 {
    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> largestValues(TreeNode root) {     
        if(root==null) return list;
        dfs(root,0);
        return list;
    }
    public void dfs(TreeNode root,int h) {
        //说明当前层没数据,直接添加
        if(list.size()==h) {
            list.add(root.val);
        }else {
            int max = Math.max(list.get(h), root.val);
            list.set(h, max);
        }
        if(root.left != null) dfs(root.left, h+1);
        if(root.right != null) dfs(root.right, h+1);
    }
}

这个代码的性能是超过百分百的,所以我也不看评论题解了,直接下一题。

统计只差一个字符的字串数组

题目:给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换 一个不同字符 以后,是 t 串的子串。换言之,请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation" 加粗部分只有一个字符不同: 'e'/'a' ,所以这一对子字符串会给答案加 1 。请你返回满足上述条件的不同子字符串对数目。一个 子字符串 是一个字符串中连续的字符。

示例 1:
输入:s = "aba", t = "baba"
输出:6
解释:以下为只相差 1 个字符的 s 和 t 串的子字符串对:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 2:
输入:s = "ab", t = "bb"
输出:3
解释:以下为只相差 1 个字符的 s 和 t 串的子字符串对:
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 3:
输入:s = "a", t = "a"
输出:0
示例 4:
输入:s = "abe", t = "bbc"
输出:10
提示:
1 <= s.length, t.length <= 100
s 和 t 都只包含小写英文字母。
思路:这个题算是插队来的。今晚双周赛里在规定时间内没做出来的题。其实贼几把简单,但是因为当时时间不够,主要是我心态不行,看不到五分钟就慌了所以一点小问题卡住没ac,挺遗憾的,这里记录一下。暴力破解法就可以ac,我当时也只是在循环的时候第二层没有想到截取字符串是不含尾的,所以没有加1.直接贴代码了

class Solution {
    public int countSubstrings(String s, String t) {
    int res = 0;
    for(int i = 0;i<s.length();i++){
        for(int j = i+1;j<s.length()+1;j++){
            String str = s.substring(i,j);           
            for(int k = 0;k<t.length()-str.length()+1;k++){                 
                String str1 = t.substring(k,k+str.length());
                // System.out.println("两个串为:"+str+"<<<<<"+str1);
                if(isOk(str, str1)) res++;
            }
        }
            
    }
    return res;

    }
    public boolean isOk(String s,String t) {
        boolean flag = true; 
        //如果都是0说明都一样。如果超过一个1和-1说明超过一个不同
        for(int i = 0;i<s.length();i++) {
            if(s.charAt(i)!=t.charAt(i)) {
                if(!flag) return false;
                flag = false;               
            }
        }
        return !flag;       
    }
}

ps:暴力破解法性能超过百分百的画面我要记录一下,哈哈


最长回文子序列

题目:给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:
输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:
"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。
提示:
1 <= s.length <= 1000
s 只包含小写英文字母

思路:这个题怎么说呢,似曾相识的感觉贼强烈。各种回文,子串的题都差不多。但是这个题,子序列本身就比子串难的多,因为子序列是可以跳过的。怪不得s只能1000以下呢。感觉这种子序列的问题一定是dp了,不然的话计算量太大。哎,之前两道题简单就突然遇到一个不擅长的了。
这里说一下大概的想法:下面是dp的思路,接下来就是填充数据。

dp思路

我反正是按照这个思路生扣出来的代码,这个实现起来稍微麻烦的点在于一定要斜对角竖着往右下填充数据。我反正这个双层循环调了半天(这个是因为我太菜了)。反正是实现了,性能也还算不错。大家可以参考下。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        char[] c = s.toCharArray();
        for(int i = 0;i<c.length;i++) {
            dp[i][i] = 1;//一个元素本身就是回文序列
            //两个元素直接等于判断
            if(i!=c.length-1) dp[i][i+1] = (c[i]==c[i+1]?2:1);
        }
        //因为i,i和i,i+1都填充完了,所以从i.i+2开始填充。右下竖着填充
        for(int j = 2;j<c.length;j++) {
            for(int i = 0;i<c.length;i++) {
                if(i+j>=c.length) break;
                if(c[i]==c[i+j]) {
                    dp[i][i+j] = dp[i+1][i+j-1]+2;
                }else {
                    dp[i][i+j] = Math.max(dp[i][i+j-1], dp[i+1][i+j]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
}

..刚刚去看了性能排行第一的代码,我简直觉得大家长的不是一样的脑子。先附上代码:

class Solution {
 public int longestPalindromeSubseq(String s) {
        return solve41(s);
    }
    private  int solve41(String s) {
        char[] c = s.toCharArray();
        int[] dp = new int[c.length];
        for (int i = 0; i < c.length; i++) {
            dp[i]=1;
            int max = 0;
            for (int j = i-1; j >= 0; j--) {
                int tmp = dp[j];
                if (c[i]==c[j]){
                    dp[j] = max+2;
                }
                max = Math.max(max,tmp);
            }
        }
        int max = 0;
        for (int i : dp) {
            max = Math.max(max, i);
        }
        return max;
    }
}

简单说一下,反正我是写不出来这样的代码。用debug调试一遍一遍走也没看明白。大概的思路就是大佬这个是用一维数组来压缩的。下标代表的数值是当这个值作为回文子序列的第一个元素,最长能有多长的子序列。如图:


一维dp实现

其实我不太觉得这个是二维dp的压缩。而是整个思路都不一样的一种做法。反正我瞻仰一下可以,暂时而言别说想了,给我思路了我都不一定能写出来。所以我还是顺序往下刷题了。

零钱兑换2

题目:给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1

思路:这个题我记得和零钱兑换1差不多啊,忘记有什么区别了,反正我觉得暴力法可以,不知道超时不超时。应该可以用dp?我不确定,反正第一反应是遍历。我去试试吧。
果断超时了,我居然觉得还挺正常的,附上超时代码:

class Solution {
    int res = 0;
    public int change(int amount, int[] coins) {
        dfs(amount,0,coins);
        return res;
    }
    public void dfs(int amount,int start,int[] coins) {
        if(amount == 0) res++;
        for(int i =start;i<coins.length;i++) {
            if(i<=amount) dfs(amount-coins[i],i, coins);
        }
    }
}

这个代码我自认为没问题。所以打算在这基础上优化试试。要说dp的话,着实是是没思路。我硬生生把这个题看成一个找规律的题了,总觉得是有啥规律,但是又不知道啥规律:


硬生生的找规律

做的我死去活来的一道题,大佬随随便便一句话就让我茅塞顿开了。先附上代码再一点点解释:

class Solution {
    public int change(int amount, int[] arr) {
        // 动态规划
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : arr) {
            for (int i = 0; i+coin <= amount; i++) {
                dp[i+coin] += dp[i];
            }
        }
        return dp[amount];
    }
}

这个代码简单的很。但是具体的思路我反正是debugn多次才反推出来的。


结果集

其实可以看出来,这个dp的做法是一个一个硬币后加进去的。0金币凑成方法只有1,那就是什么都不放。所以dp[0]=1这个没疑问。然后从硬币开始判断。如果只有1金币,那么1都可以凑出来。所以是1-10都是1。
然后2金币。其实在总金币数小于2的时候,是不会有改变的。所以第一个开始改变的就是总金币数是2的(i+coin。i是0.所以可以理解成是从coin开始的)。这个表达式本身是 :

dp[i+coin] = dp[i]+dp[i+coin]。

其实这个挺好理解的,首先原本能凑出多少不会变的。所以是dp[i+coin]的基础上再加。
然后多了这个元素能凑出的个数,是指没有这个元素的时候有多少种可能(这些可能加上当前元素就行了)。所以是dp[i]+dp[i+coin].
就这样一个金币一个金币的累计加上去就行了。
我只能说看懂很勉强。自己做出来再练一段时间吧。
这篇笔记就记到这里了,如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利!生活愉快!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,639评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,277评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,221评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,474评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,570评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,816评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,957评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,718评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,176评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,511评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,646评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,322评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,934评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,755评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,987评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,358评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,514评论 2 348