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].
就这样一个金币一个金币的累计加上去就行了。
我只能说看懂很勉强。自己做出来再练一段时间吧。
这篇笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利！生活愉快！
