原來(lái)是閑了的時(shí)候刷刷題，現(xiàn)在是忙的時(shí)候擠出時(shí)間刷刷題，心態(tài)的變化讓我覺(jué)得其實(shí)一天能自由支配的時(shí)間還是挺多的，哈哈。
出現(xiàn)次數(shù)最多的子樹(shù)元素和
題目：給你一個(gè)二叉樹(shù)的根結(jié)點(diǎn)，請(qǐng)你找出出現(xiàn)次數(shù)最多的子樹(shù)元素和。一個(gè)結(jié)點(diǎn)的「子樹(shù)元素和」定義為以該結(jié)點(diǎn)為根的二叉樹(shù)上所有結(jié)點(diǎn)的元素之和（包括結(jié)點(diǎn)本身）。你需要返回出現(xiàn)次數(shù)最多的子樹(shù)元素和。如果有多個(gè)元素出現(xiàn)的次數(shù)相同，返回所有出現(xiàn)次數(shù)最多的子樹(shù)元素和（不限順序）。
思路:我現(xiàn)在一臉羞愧。第一遍沒(méi)看明白題意，還欠了吧唧的給提了個(gè)反饋以為是翻譯有問(wèn)題。哎，現(xiàn)在開(kāi)始說(shuō)這個(gè)題，簡(jiǎn)單來(lái)說(shuō)我覺(jué)得單純的暴力法也還是可以的。不考慮性能問(wèn)題的話，就是每個(gè)子樹(shù)和都存上，最后選擇出現(xiàn)次數(shù)最多的那個(gè)。然后其實(shí)這里可以有遞歸實(shí)現(xiàn)吧。我去試試。反正我目前的想法就是暴力法，我去實(shí)現(xiàn)看看。
過(guò)是過(guò)了，性能反正就那樣吧。
/**
* 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];//計(jì)數(shù)數(shù)組，不會(huì)大于list的長(zhǎng)度
Collections.sort(list);
int n = 1;
int idx = 0;
for(int i = 0;i<list.size();i++) {
//當(dāng)前元素的值
num[idx][0] = list.get(i);
//和前面元素相同。因?yàn)槭荌nteger，所以要用equals
while(i<list.size() && i>0 && list.get(i).equals(list.get(i-1))) {
i++;//繼續(xù)往下判斷
n++;//相同元素+1了
}
//當(dāng)前元素的個(gè)數(shù)。這個(gè)num的下標(biāo)其實(shí)和list2的下標(biāo)是對(duì)應(yīng)的
num[idx][1] = n;
//走到這說(shuō)明當(dāng)前元素不同了,計(jì)數(shù)歸1
n = 1;
idx++;
}
//找出出現(xiàn)最多的次數(shù)
int max = 0;
for(int[] i : num) {
if(i[1] == 0) break;//正常計(jì)數(shù)不可能是0，到0說(shuō)明后面都沒(méi)用到
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;//如果這個(gè)節(jié)點(diǎn)沒(méi)有則是0
//不是葉子節(jié)點(diǎn)，要去計(jì)算左右+當(dāng)前的和
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);//這個(gè)葉子節(jié)點(diǎn)算是單獨(dú)的一個(gè)和
return root.val;
}
}
}
我其實(shí)本來(lái)想用hash的，但是以為數(shù)組型數(shù)組會(huì)更好，反正是覺(jué)得我寫(xiě)麻煩了，我再換種方式試試。
小小的修改了一下，ac了并且性能超過(guò)百分之八十八，算是合格了吧：
/**
* 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;//如果這個(gè)節(jié)點(diǎn)沒(méi)有則是0
//計(jì)算左右+當(dāng)前的和
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;
}
}
這道題其實(shí)就是處理比較麻煩，但是還是比較容易做的，不多說(shuō)了，下一題了。
找樹(shù)左下角的值
題目：給定一個(gè)二叉樹(shù)，在樹(shù)的最后一行找到最左邊的值。
思路：不是，我不知道這個(gè)題是怎么混到中等難度的。難道不是簡(jiǎn)單題目么？層次遍歷。取最后一層第一個(gè)不就行了？難道會(huì)卡在性能上？或者說(shuō)有什么最優(yōu)的解法？我先去按照我的想法實(shí)現(xiàn)下試試。
想法沒(méi)問(wèn)題，性能超過(guò)百分之七十，直接貼代碼：
/**
* 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()){
//獲取每一層的第一個(gè)元素
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;
}
}
真的，這個(gè)題我覺(jué)得也就簡(jiǎn)單難度，看看性能排行第一的有什么優(yōu)解吧：
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;
}
//第一次大于的時(shí)候就是每層最左邊的節(jié)點(diǎn)
if(num>max){
max = num;
value = node.val;
}
get(node.left,num+1);
get(node.right,num+1);
}
}
直接用深搜。因?yàn)槭谴笥趍ax才會(huì)替換，所以最下層有多個(gè)也不怕，簡(jiǎn)單明了，感覺(jué)這個(gè)題思路清晰就沒(méi)啥問(wèn)題了，下一題吧。
在每個(gè)樹(shù)行中找到最大值
題目：您需要在二叉樹(shù)的每一行中找到最大的值。
思路：又是一個(gè)送分題，其實(shí)上面那個(gè)答案稍微變化一下就是這個(gè)了，兩種方法都可以。一個(gè)是層次遍歷，每個(gè)多一層找當(dāng)前層的最大值。還有一種就是深搜。每一層都保存最大值。沒(méi)啥好解釋的，我去寫(xiě)代碼了。
稍微改了一下上一題的代碼就ac了。當(dāng)然第一次翻車了，翻車的原因是給了一個(gè)空樹(shù)。。貼代碼：
/**
* 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;
}
}
其實(shí)深搜也可以實(shí)現(xiàn)的，換種思路寫(xiě)下這道題：
!!!我簡(jiǎn)直日狗了，一個(gè)坑栽了兩次，又沒(méi)判斷root==null。第二遍過(guò)的。貼代碼：
/**
* 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) {
//說(shuō)明當(dāng)前層沒(méi)數(shù)據(jù)，直接添加
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);
}
}
這個(gè)代碼的性能是超過(guò)百分百的，所以我也不看評(píng)論題解了，直接下一題。
統(tǒng)計(jì)只差一個(gè)字符的字串?dāng)?shù)組
題目：給你兩個(gè)字符串 s 和 t ，請(qǐng)你找出 s 中的非空子串的數(shù)目，這些子串滿足替換 一個(gè)不同字符 以后，是 t 串的子串。換言之，請(qǐng)你找到 s 和 t 串中 恰好 只有一個(gè)字符不同的子字符串對(duì)的數(shù)目。比方說(shuō)， "computer" 和 "computation" 加粗部分只有一個(gè)字符不同： 'e'/'a' ，所以這一對(duì)子字符串會(huì)給答案加 1 。請(qǐng)你返回滿足上述條件的不同子字符串對(duì)數(shù)目。一個(gè) 子字符串 是一個(gè)字符串中連續(xù)的字符。
示例 1：
輸入：s = "aba", t = "baba"
輸出：6
解釋：以下為只相差 1 個(gè)字符的 s 和 t 串的子字符串對(duì)：
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分別表示 s 和 t 串選出來(lái)的子字符串。
示例 2：
輸入：s = "ab", t = "bb"
輸出：3
解釋：以下為只相差 1 個(gè)字符的 s 和 t 串的子字符串對(duì)：
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分別表示 s 和 t 串選出來(lái)的子字符串。
示例 3：
輸入：s = "a", t = "a"
輸出：0
示例 4：
輸入：s = "abe", t = "bbc"
輸出：10
提示：
1 <= s.length, t.length <= 100
s 和 t 都只包含小寫(xiě)英文字母。
思路：這個(gè)題算是插隊(duì)來(lái)的。今晚雙周賽里在規(guī)定時(shí)間內(nèi)沒(méi)做出來(lái)的題。其實(shí)賊幾把簡(jiǎn)單，但是因?yàn)楫?dāng)時(shí)時(shí)間不夠，主要是我心態(tài)不行，看不到五分鐘就慌了所以一點(diǎn)小問(wèn)題卡住沒(méi)ac，挺遺憾的，這里記錄一下。暴力破解法就可以ac，我當(dāng)時(shí)也只是在循環(huán)的時(shí)候第二層沒(méi)有想到截取字符串是不含尾的，所以沒(méi)有加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("兩個(gè)串為："+str+"<<<<<"+str1);
if(isOk(str, str1)) res++;
}
}
}
return res;
}
public boolean isOk(String s,String t) {
boolean flag = true;
//如果都是0說(shuō)明都一樣。如果超過(guò)一個(gè)1和-1說(shuō)明超過(guò)一個(gè)不同
for(int i = 0;i<s.length();i++) {
if(s.charAt(i)!=t.charAt(i)) {
if(!flag) return false;
flag = false;
}
}
return !flag;
}
}
ps:暴力破解法性能超過(guò)百分百的畫(huà)面我要記錄一下，哈哈
最長(zhǎng)回文子序列
題目：給定一個(gè)字符串 s ，找到其中最長(zhǎng)的回文子序列，并返回該序列的長(zhǎng)度?？梢约僭O(shè) s 的最大長(zhǎng)度為 1000 。
示例 1:
輸入:
"bbbab"
輸出:
4
一個(gè)可能的最長(zhǎng)回文子序列為 "bbbb"。
示例 2:
輸入:
"cbbd"
輸出:
2
一個(gè)可能的最長(zhǎng)回文子序列為 "bb"。
提示：
1 <= s.length <= 1000
s 只包含小寫(xiě)英文字母
思路：這個(gè)題怎么說(shuō)呢，似曾相識(shí)的感覺(jué)賊強(qiáng)烈。各種回文，子串的題都差不多。但是這個(gè)題，子序列本身就比子串難的多，因?yàn)樽有蛄惺强梢蕴^(guò)的。怪不得s只能1000以下呢。感覺(jué)這種子序列的問(wèn)題一定是dp了，不然的話計(jì)算量太大。哎，之前兩道題簡(jiǎn)單就突然遇到一個(gè)不擅長(zhǎng)的了。
這里說(shuō)一下大概的想法：下面是dp的思路，接下來(lái)就是填充數(shù)據(jù)。
我反正是按照這個(gè)思路生扣出來(lái)的代碼，這個(gè)實(shí)現(xiàn)起來(lái)稍微麻煩的點(diǎn)在于一定要斜對(duì)角豎著往右下填充數(shù)據(jù)。我反正這個(gè)雙層循環(huán)調(diào)了半天（這個(gè)是因?yàn)槲姨肆耍?。反正是?shí)現(xiàn)了，性能也還算不錯(cuò)。大家可以參考下。
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;//一個(gè)元素本身就是回文序列
//兩個(gè)元素直接等于判斷
if(i!=c.length-1) dp[i][i+1] = (c[i]==c[i+1]?2:1);
}
//因?yàn)閕,i和i,i+1都填充完了，所以從i.i+2開(kāi)始填充。右下豎著填充
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];
}
}
..剛剛?cè)タ戳诵阅芘判械谝坏拇a，我簡(jiǎn)直覺(jué)得大家長(zhǎng)的不是一樣的腦子。先附上代碼：
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;
}
}
簡(jiǎn)單說(shuō)一下，反正我是寫(xiě)不出來(lái)這樣的代碼。用debug調(diào)試一遍一遍走也沒(méi)看明白。大概的思路就是大佬這個(gè)是用一維數(shù)組來(lái)壓縮的。下標(biāo)代表的數(shù)值是當(dāng)這個(gè)值作為回文子序列的第一個(gè)元素，最長(zhǎng)能有多長(zhǎng)的子序列。如圖：
其實(shí)我不太覺(jué)得這個(gè)是二維dp的壓縮。而是整個(gè)思路都不一樣的一種做法。反正我瞻仰一下可以，暫時(shí)而言別說(shuō)想了，給我思路了我都不一定能寫(xiě)出來(lái)。所以我還是順序往下刷題了。
零錢兌換2
題目：給定不同面額的硬幣和一個(gè)總金額。寫(xiě)出函數(shù)來(lái)計(jì)算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無(wú)限個(gè)。
示例 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
思路：這個(gè)題我記得和零錢兌換1差不多啊，忘記有什么區(qū)別了，反正我覺(jué)得暴力法可以，不知道超時(shí)不超時(shí)。應(yīng)該可以用dp？我不確定，反正第一反應(yīng)是遍歷。我去試試吧。
果斷超時(shí)了，我居然覺(jué)得還挺正常的，附上超時(shí)代碼：
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);
}
}
}
這個(gè)代碼我自認(rèn)為沒(méi)問(wèn)題。所以打算在這基礎(chǔ)上優(yōu)化試試。要說(shuō)dp的話，著實(shí)是是沒(méi)思路。我硬生生把這個(gè)題看成一個(gè)找規(guī)律的題了，總覺(jué)得是有啥規(guī)律，但是又不知道啥規(guī)律：
做的我死去活來(lái)的一道題，大佬隨隨便便一句話就讓我茅塞頓開(kāi)了。先附上代碼再一點(diǎn)點(diǎn)解釋：
class Solution {
public int change(int amount, int[] arr) {
// 動(dòng)態(tài)規(guī)劃
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];
}
}
這個(gè)代碼簡(jiǎn)單的很。但是具體的思路我反正是debugn多次才反推出來(lái)的。
其實(shí)可以看出來(lái)，這個(gè)dp的做法是一個(gè)一個(gè)硬幣后加進(jìn)去的。0金幣湊成方法只有1，那就是什么都不放。所以dp[0]=1這個(gè)沒(méi)疑問(wèn)。然后從硬幣開(kāi)始判斷。如果只有1金幣，那么1都可以湊出來(lái)。所以是1-10都是1。
然后2金幣。其實(shí)在總金幣數(shù)小于2的時(shí)候，是不會(huì)有改變的。所以第一個(gè)開(kāi)始改變的就是總金幣數(shù)是2的（i+coin。i是0.所以可以理解成是從coin開(kāi)始的）。這個(gè)表達(dá)式本身是 :
dp[i+coin] = dp[i]+dp[i+coin]。
其實(shí)這個(gè)挺好理解的，首先原本能湊出多少不會(huì)變的。所以是dp[i+coin]的基礎(chǔ)上再加。
然后多了這個(gè)元素能湊出的個(gè)數(shù)，是指沒(méi)有這個(gè)元素的時(shí)候有多少種可能（這些可能加上當(dāng)前元素就行了）。所以是dp[i]+dp[i+coin].
就這樣一個(gè)金幣一個(gè)金幣的累計(jì)加上去就行了。
我只能說(shuō)看懂很勉強(qiáng)。自己做出來(lái)再練一段時(shí)間吧。
這篇筆記就記到這里了，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注。也祝大家工作順順利利！生活愉快！
