中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

蘭州網(wǎng)站建設(shè)招聘信息策劃公司

蘭州網(wǎng)站建設(shè)招聘信息,策劃公司,吉林省高等級(jí)公路建設(shè)局死人網(wǎng)站,網(wǎng)站制作費(fèi)用需要多少錢樹形DP(靈神筆記) 543 二叉樹的直徑 543. 二叉樹的直徑 - 力扣(LeetCode) 給你一棵二叉樹的根節(jié)點(diǎn),返回該樹的 直徑 。 二叉樹的 直徑 是指樹中任意兩個(gè)節(jié)點(diǎn)之間最長路徑的 長度 。這條路徑可能經(jīng)過也可能不經(jīng)過根…

樹形DP(靈神筆記)

543 二叉樹的直徑

543. 二叉樹的直徑 - 力扣(LeetCode)

給你一棵二叉樹的根節(jié)點(diǎn),返回該樹的 直徑 。

二叉樹的 直徑 是指樹中任意兩個(gè)節(jié)點(diǎn)之間最長路徑的 長度 。這條路徑可能經(jīng)過也可能不經(jīng)過根節(jié)點(diǎn) root 。

兩節(jié)點(diǎn)之間路徑的 長度 由它們之間邊數(shù)表示。

示例 1:

img

輸入:root = [1,2,3,4,5]
輸出:3
解釋:3 ,取路徑 [4,2,1,3] 或 [5,2,1,3] 的長度。

示例 2:

輸入:root = [1,2]
輸出:1

提示:

  • 樹中節(jié)點(diǎn)數(shù)目在范圍 [1, 104] 內(nèi)
  • -100 <= Node.val <= 100
/*** 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 {private int ans; public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return -1;//返回-1 下面+1變成了0}int l_len = dfs(root.left) + 1;//左子樹最大鏈長+1int r_len = dfs(root.right) + 1;//右子樹最大鏈長+1ans = Math.max(ans, l_len + r_len);return Math.max(l_len, r_len);}
}

124 二叉樹的最大路徑和

124. 二叉樹中的最大路徑和 - 力扣(LeetCode)

二叉樹中的 路徑 被定義為一條節(jié)點(diǎn)序列,序列中每對(duì)相鄰節(jié)點(diǎn)之間都存在一條邊。同一個(gè)節(jié)點(diǎn)在一條路徑序列中 至多出現(xiàn)一次 。該路徑 至少包含一個(gè) 節(jié)點(diǎn),且不一定經(jīng)過根節(jié)點(diǎn)。

路徑和 是路徑中各節(jié)點(diǎn)值的總和。

給你一個(gè)二叉樹的根節(jié)點(diǎn) root ,返回其 最大路徑和

示例 1:

img

輸入:root = [1,2,3]
輸出:6
解釋:最優(yōu)路徑是 2 -> 1 -> 3 ,路徑和為 2 + 1 + 3 = 6

示例 2:

img

輸入:root = [-10,9,20,null,null,15,7]
輸出:42
解釋:最優(yōu)路徑是 15 -> 20 -> 7 ,路徑和為 15 + 20 + 7 = 42

提示:

  • 樹中節(jié)點(diǎn)數(shù)目范圍是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000
/*** 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 {private int ans = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return 0;//沒有結(jié)點(diǎn) 和為0}int l_val = dfs(root.left);int r_val = dfs(root.right);ans = Math.max(ans, l_val + r_val + root.val);return Math.max(Math.max(l_val, r_val) + root.val, 0);//負(fù)數(shù)不選}
}

2246 相鄰字符不同的最長路徑

2246. 相鄰字符不同的最長路徑 - 力扣(LeetCode)

給你一棵 (即一個(gè)連通、無向、無環(huán)圖),根節(jié)點(diǎn)是節(jié)點(diǎn) 0 ,這棵樹由編號(hào)從 0n - 1n 個(gè)節(jié)點(diǎn)組成。用下標(biāo)從 0 開始、長度為 n 的數(shù)組 parent 來表示這棵樹,其中 parent[i] 是節(jié)點(diǎn) i 的父節(jié)點(diǎn),由于節(jié)點(diǎn) 0 是根節(jié)點(diǎn),所以 parent[0] == -1 。

另給你一個(gè)字符串 s ,長度也是 n ,其中 s[i] 表示分配給節(jié)點(diǎn) i 的字符。

請(qǐng)你找出路徑上任意一對(duì)相鄰節(jié)點(diǎn)都沒有分配到相同字符的 最長路徑 ,并返回該路徑的長度。

示例 1:

img

輸入:parent = [-1,0,0,1,1,2], s = "abacbe"
輸出:3
解釋:任意一對(duì)相鄰節(jié)點(diǎn)字符都不同的最長路徑是:0 -> 1 -> 3 。該路徑的長度是 3 ,所以返回 3 。
可以證明不存在滿足上述條件且比 3 更長的路徑。 

示例 2:

img

輸入:parent = [-1,0,0,0], s = "aabc"
輸出:3
解釋:任意一對(duì)相鄰節(jié)點(diǎn)字符都不同的最長路徑是:2 -> 0 -> 3 。該路徑的長度為 3 ,所以返回 3 。

提示:

  • n == parent.length == s.length
  • 1 <= n <= 105
  • 對(duì)所有 i >= 10 <= parent[i] <= n - 1 均成立
  • parent[0] == -1
  • parent 表示一棵有效的樹
  • s 僅由小寫英文字母組成
class Solution {private List<Integer>[] g;//存儲(chǔ)父節(jié)點(diǎn)i的子節(jié)點(diǎn)private String s;private int ans;public int longestPath(int[] parent, String s) {this.s = s;int n = parent.length;g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (int i = 1; i < n; i++) {//記錄父節(jié)點(diǎn)的子節(jié)點(diǎn)的索引g[parent[i]].add(i);}dfs(0);return ans + 1;//求點(diǎn)的個(gè)數(shù),路徑長度+1}//計(jì)算最大長度private int dfs(int x) {int maxLen = 0;for (int y : g[x]) {int len = dfs(y) + 1;if (s.charAt(x) != s.charAt(y)) {ans = Math.max(ans, maxLen + len);//最長路徑maxLen = Math.max(maxLen, len);//左右子樹最大長度}}return maxLen;}
}

687 最長同值路徑

687. 最長同值路徑 - 力扣(LeetCode)

給定一個(gè)二叉樹的 root ,返回 最長的路徑的長度 ,這個(gè)路徑中的 每個(gè)節(jié)點(diǎn)具有相同值 。 這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點(diǎn)。

兩個(gè)節(jié)點(diǎn)之間的路徑長度 由它們之間的邊數(shù)表示。

示例 1:

img

輸入:root = [5,4,5,1,1,5]
輸出:2

示例 2:

img

輸入:root = [1,4,5,4,4,5]
輸出:2

提示:

  • 樹的節(jié)點(diǎn)數(shù)的范圍是 [0, 104]
  • -1000 <= Node.val <= 1000
  • 樹的深度將不超過 1000
/*** 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 {private int ans;public int longestUnivaluePath(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return -1;}int l_len = dfs(root.left) + 1;int r_len = dfs(root.right) + 1;if (root.left != null && root.left.val != root.val) {l_len = 0;}if (root.right != null && root.right.val != root.val) {r_len = 0;}ans = Math.max(ans, l_len + r_len);return Math.max(l_len, r_len);}
}

1617 統(tǒng)計(jì)子樹中城市之間最大距離

參考題解:1617. 統(tǒng)計(jì)子樹中城市之間最大距離 - 力扣(LeetCode)

給你 n 個(gè)城市,編號(hào)為從 1n 。同時(shí)給你一個(gè)大小為 n-1 的數(shù)組 edges ,其中 edges[i] = [ui, vi] 表示城市 uivi 之間有一條雙向邊。題目保證任意城市之間只有唯一的一條路徑。換句話說,所有城市形成了一棵 。

一棵 子樹 是城市的一個(gè)子集,且子集中任意城市之間可以通過子集中的其他城市和邊到達(dá)。兩個(gè)子樹被認(rèn)為不一樣的條件是至少有一個(gè)城市在其中一棵子樹中存在,但在另一棵子樹中不存在。

對(duì)于 d1n-1 ,請(qǐng)你找到城市間 最大距離 恰好為 d 的所有子樹數(shù)目。

請(qǐng)你返回一個(gè)大小為 n-1 的數(shù)組,其中第 d 個(gè)元素(下標(biāo)從 1 開始)是城市間 最大距離 恰好等于 d 的子樹數(shù)目。

請(qǐng)注意,兩個(gè)城市間距離定義為它們之間需要經(jīng)過的邊的數(shù)目。

示例 1:

img

輸入:n = 4, edges = [[1,2],[2,3],[2,4]]
輸出:[3,4,0]
解釋:
子樹 {1,2}, {2,3} 和 {2,4} 最大距離都是 1 。
子樹 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距離都為 2 。
不存在城市間最大距離為 3 的子樹。

示例 2:

輸入:n = 2, edges = [[1,2]]
輸出:[1]

示例 3:

輸入:n = 3, edges = [[1,2],[2,3]]
輸出:[2,1]

提示:

  • 2 <= n <= 15
  • edges.length == n-1
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • 題目保證 (ui, vi) 所表示的邊互不相同。
class Solution {private List<Integer>[] g;private boolean[] inSet, vis;//inSet是選出來的樹(城市) vis記錄的是這個(gè)城市(樹)的直徑private int[] ans;private int n, diameter;//定義n和直徑public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {this.n = n;g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (var e : edges) {int x = e[0] - 1;int y = e[1] - 1;g[x].add(y);g[y].add(x);//建樹}ans = new int[n - 1];inSet = new boolean[n];f(0);return ans;}private void f(int i) {if (i == n) {for (int v = 0; v < n; v++) {if (inSet[v]) {vis = new boolean[n];diameter = 0;dfs(v);break;}}if (diameter > 0 && Arrays.equals(vis, inSet)) {ans[diameter - 1]++;}return;}//不選城市if(i + 1);//選城市iinSet[i] = true;f(i + 1);inSet[i] = false;}//樹的直徑private int dfs(int x) {vis[x] = true;int maxLen = 0;for (int y : g[x]) {if (!vis[y] && inSet[y]) {int len = dfs(y) + 1;diameter = Math.max(diameter, maxLen + len);maxLen = Math.max(maxLen, len);}}return maxLen;}
}

2538 最大價(jià)值和與最小價(jià)值和的差值

參考題解:2538. 最大價(jià)值和與最小價(jià)值和的差值 - 力扣(LeetCode)

給你一個(gè) n 個(gè)節(jié)點(diǎn)的無向無根圖,節(jié)點(diǎn)編號(hào)為 0n - 1 。給你一個(gè)整數(shù) n 和一個(gè)長度為 n - 1 的二維整數(shù)數(shù)組 edges ,其中 edges[i] = [ai, bi] 表示樹中節(jié)點(diǎn) aibi 之間有一條邊。

每個(gè)節(jié)點(diǎn)都有一個(gè)價(jià)值。給你一個(gè)整數(shù)數(shù)組 price ,其中 price[i] 是第 i 個(gè)節(jié)點(diǎn)的價(jià)值。

一條路徑的 價(jià)值和 是這條路徑上所有節(jié)點(diǎn)的價(jià)值之和。

你可以選擇樹中任意一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn) root 。選擇 root 為根的 開銷 是以 root 為起點(diǎn)的所有路徑中,價(jià)值和 最大的一條路徑與最小的一條路徑的差值。

請(qǐng)你返回所有節(jié)點(diǎn)作為根節(jié)點(diǎn)的選擇中,最大開銷 為多少。

示例 1:

img

輸入:n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
輸出:24
解釋:上圖展示了以節(jié)點(diǎn) 2 為根的樹。左圖(紅色的節(jié)點(diǎn))是最大價(jià)值和路徑,右圖(藍(lán)色的節(jié)點(diǎn))是最小價(jià)值和路徑。
- 第一條路徑節(jié)點(diǎn)為 [2,1,3,4]:價(jià)值為 [7,8,6,10] ,價(jià)值和為 31 。
- 第二條路徑節(jié)點(diǎn)為 [2] ,價(jià)值為 [7] 。
最大路徑和與最小路徑和的差值為 24 。24 是所有方案中的最大開銷。

示例 2:

img

輸入:n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
輸出:2
解釋:上圖展示了以節(jié)點(diǎn) 0 為根的樹。左圖(紅色的節(jié)點(diǎn))是最大價(jià)值和路徑,右圖(藍(lán)色的節(jié)點(diǎn))是最小價(jià)值和路徑。
- 第一條路徑包含節(jié)點(diǎn) [0,1,2]:價(jià)值為 [1,1,1] ,價(jià)值和為 3 。
- 第二條路徑節(jié)點(diǎn)為 [0] ,價(jià)值為 [1] 。
最大路徑和與最小路徑和的差值為 2 。2 是所有方案中的最大開銷。

提示:

  • 1 <= n <= 105
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges 表示一棵符合題面要求的樹。
  • price.length == n
  • 1 <= price[i] <= 105
class Solution {private List<Integer>[] g;private int[] price;private long ans;public long maxOutput(int n, int[][] edges, int[] price) {this.price = price;g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (var e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}dfs(0, -1);return ans;}private long[] dfs(int x, int father) {// maxS1前面最大帶葉子的路徑和 maxS2前面最大不帶葉子的路徑和long p = price[x], maxS1 = p, maxS2 = 0;for (var y : g[x]) {if (y != father) {var res = dfs(y, x);// s1當(dāng)前不帶葉子的路徑和 s2當(dāng)前帶葉子的路徑和long s1 = res[0], s2 = res[1];ans = Math.max(ans, Math.max(maxS1 + s2, maxS2 + s1));maxS1 = Math.max(maxS1, s1 + p);maxS2 = Math.max(maxS2, s2 + p);// x必然不是葉子}}return new long[]{maxS1, maxS2};}
}

337 打家劫舍三

337. 打家劫舍 III - 力扣(LeetCode)

小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口,我們稱之為 root

除了 root 之外,每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后,聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果 兩個(gè)直接相連的房子在同一天晚上被打劫 ,房屋將自動(dòng)報(bào)警。

給定二叉樹的 root 。返回 在不觸動(dòng)警報(bào)的情況下 ,小偷能夠盜取的最高金額 。

示例 1:

img

輸入: root = [3,2,3,null,3,null,1]
輸出: 7 
解釋: 小偷一晚能夠盜取的最高金額 3 + 3 + 1 = 7

示例 2:

img

輸入: root = [3,4,5,1,3,null,1]
輸出: 9
解釋: 小偷一晚能夠盜取的最高金額 4 + 5 = 9

提示:

  • 樹的節(jié)點(diǎn)數(shù)在 [1, 104] 范圍內(nèi)
  • 0 <= Node.val <= 104
/*** 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 int rob(TreeNode root) {int[] ans = dfs(root);return Math.max(ans[0], ans[1]);}private int[] dfs(TreeNode root) {if (root == null) {return new int[]{0,0};}int[] left = dfs(root.left);int[] right = dfs(root.right);int rob = left[1] + right[1] + root.val;//選根節(jié)點(diǎn)//不選根節(jié)點(diǎn)int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);return new int[]{rob, notRob};}
}

1377 T秒后青蛙的位置

1377. T 秒后青蛙的位置 - 力扣(LeetCode)

參考題解:1377. T 秒后青蛙的位置 - 力扣(LeetCode)

建圖(樹)模版(以1377為例)

public static void main(String[] args) {int n = 7;int[][] edges = new int[][]{{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};List<Integer>[] g = new ArrayList[n + 1];Arrays.setAll(g, e -> new ArrayList<>());for (var e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x); // 建樹}}

給你一棵由 n 個(gè)頂點(diǎn)組成的無向樹,頂點(diǎn)編號(hào)從 1n。青蛙從 頂點(diǎn) 1 開始起跳。規(guī)則如下:

  • 在一秒內(nèi),青蛙從它所在的當(dāng)前頂點(diǎn)跳到另一個(gè) 未訪問 過的頂點(diǎn)(如果它們直接相連)。
  • 青蛙無法跳回已經(jīng)訪問過的頂點(diǎn)。
  • 如果青蛙可以跳到多個(gè)不同頂點(diǎn),那么它跳到其中任意一個(gè)頂點(diǎn)上的機(jī)率都相同。
  • 如果青蛙不能跳到任何未訪問過的頂點(diǎn)上,那么它每次跳躍都會(huì)停留在原地。

無向樹的邊用數(shù)組 edges 描述,其中 edges[i] = [ai, bi] 意味著存在一條直接連通 aibi 兩個(gè)頂點(diǎn)的邊。

返回青蛙在 t 秒后位于目標(biāo)頂點(diǎn) target 上的概率。與實(shí)際答案相差不超過 10-5 的結(jié)果將被視為正確答案。

示例 1:

img

輸入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
輸出:0.16666666666666666 
解釋:上圖顯示了青蛙的跳躍路徑。青蛙從頂點(diǎn) 1 起跳,第 1 秒 有 1/3 的概率跳到頂點(diǎn) 2 ,然后第 2 秒 有 1/2 的概率跳到頂點(diǎn) 4,因此青蛙在 2 秒后位于頂點(diǎn) 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。 

示例 2:

img

輸入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
輸出:0.3333333333333333
解釋:上圖顯示了青蛙的跳躍路徑。青蛙從頂點(diǎn) 1 起跳,有 1/3 = 0.3333333333333333 的概率能夠 1 秒 后跳到頂點(diǎn) 7 。 

提示:

  • 1 <= n <= 100
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • 1 <= t <= 50
  • 1 <= target <= n
class Solution {//自底向上查找public double frogPosition(int n, int[][] edges, int t, int target) {List<Integer>[] g = new ArrayList[n + 1];Arrays.setAll(g, e -> new ArrayList<>());g[1].add(0);// 減少額外判斷for (var e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x); // 建樹}long prod = dfs(g, target, 1, 0, t);return prod != 0 ? 1.0 / prod : 0;}private long dfs(List<Integer>[] g, int target, int x, int father, int leftT) {//t秒后在targetif (leftT == 0) {return x == target ? 1 : 0;}//target是葉子停在原地if (x == target) {return g[x].size() == 1 ? 1 : 0;}for (int y : g[x]) {if (y != father) {long prod = dfs(g, target, y, x, leftT - 1);if (prod != 0) {return prod * (g[x].size() - 1);// 乘上兒子的個(gè)數(shù)}}}return 0;// 未找到 target}
}

2646 最小化旅行的價(jià)格總和

參考題解:2646. 最小化旅行的價(jià)格總和 - 力扣(LeetCode)

現(xiàn)有一棵無向、無根的樹,樹中有 n 個(gè)節(jié)點(diǎn),按從 0n - 1 編號(hào)。給你一個(gè)整數(shù) n 和一個(gè)長度為 n - 1 的二維整數(shù)數(shù)組 edges ,其中 edges[i] = [ai, bi] 表示樹中節(jié)點(diǎn) aibi 之間存在一條邊。

每個(gè)節(jié)點(diǎn)都關(guān)聯(lián)一個(gè)價(jià)格。給你一個(gè)整數(shù)數(shù)組 price ,其中 price[i] 是第 i 個(gè)節(jié)點(diǎn)的價(jià)格。

給定路徑的 價(jià)格總和 是該路徑上所有節(jié)點(diǎn)的價(jià)格之和。

另給你一個(gè)二維整數(shù)數(shù)組 trips ,其中 trips[i] = [starti, endi] 表示您從節(jié)點(diǎn) starti 開始第 i 次旅行,并通過任何你喜歡的路徑前往節(jié)點(diǎn) endi

在執(zhí)行第一次旅行之前,你可以選擇一些 非相鄰節(jié)點(diǎn) 并將價(jià)格減半。

返回執(zhí)行所有旅行的最小價(jià)格總和。

示例 1:

img

輸入:n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
輸出:23
解釋:
上圖表示將節(jié)點(diǎn) 2 視為根之后的樹結(jié)構(gòu)。第一個(gè)圖表示初始樹,第二個(gè)圖表示選擇節(jié)點(diǎn) 0 、2 和 3 并使其價(jià)格減半后的樹。
第 1 次旅行,選擇路徑 [0,1,3] 。路徑的價(jià)格總和為 1 + 2 + 3 = 6 。
第 2 次旅行,選擇路徑 [2,1] 。路徑的價(jià)格總和為 2 + 5 = 7 。
第 3 次旅行,選擇路徑 [2,1,3] 。路徑的價(jià)格總和為 5 + 2 + 3 = 10 。
所有旅行的價(jià)格總和為 6 + 7 + 10 = 23 ??梢宰C明,23 是可以實(shí)現(xiàn)的最小答案。

示例 2:

img

輸入:n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
輸出:1
解釋:
上圖表示將節(jié)點(diǎn) 0 視為根之后的樹結(jié)構(gòu)。第一個(gè)圖表示初始樹,第二個(gè)圖表示選擇節(jié)點(diǎn) 0 并使其價(jià)格減半后的樹。 
第 1 次旅行,選擇路徑 [0] 。路徑的價(jià)格總和為 1 。 
所有旅行的價(jià)格總和為 1 ??梢宰C明,1 是可以實(shí)現(xiàn)的最小答案。

提示:

  • 1 <= n <= 50
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges 表示一棵有效的樹
  • price.length == n
  • price[i] 是一個(gè)偶數(shù)
  • 1 <= price[i] <= 1000
  • 1 <= trips.length <= 100
  • 0 <= starti, endi <= n - 1
class Solution {private List<Integer>[] g;private int[] price, cnt;private int end;public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (var e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}this.price = price;cnt = new int[n];for (var t : trips) {end = t[1];path(t[0], -1);}int[] p = dfs(0, -1);return Math.min(p[0], p[1]);}private boolean path(int x, int father) {if (x == end) {cnt[x]++;//統(tǒng)計(jì)從start到end的路徑上的點(diǎn)經(jīng)過了多少次return true;//找到終點(diǎn)}for (var y : g[x]) {if (y != father && path(y, x)) {cnt[x]++;return true;}}return false;//沒找到終點(diǎn)}private int[] dfs(int x, int father) {int notSelect = price[x] * cnt[x];//x不變int select = notSelect / 2;//x減半for (var y : g[x]) {if (y != father) {int[] p = dfs(y, x);//計(jì)算兒子y 不變/減半的最小價(jià)值總和notSelect += Math.min(p[0], p[1]);select += p[0];}}return new int[]{notSelect, select};}
}

2467 樹上最大得分和路徑

參考題解:2467. 樹上最大得分和路徑 - 力扣(LeetCode)

一個(gè) n 個(gè)節(jié)點(diǎn)的無向樹,節(jié)點(diǎn)編號(hào)為 0n - 1 ,樹的根結(jié)點(diǎn)是 0 號(hào)節(jié)點(diǎn)。給你一個(gè)長度為 n - 1 的二維整數(shù)數(shù)組 edges ,其中 edges[i] = [ai, bi] ,表示節(jié)點(diǎn) aibi 在樹中有一條邊。

在每一個(gè)節(jié)點(diǎn) i 處有一扇門。同時(shí)給你一個(gè)都是偶數(shù)的數(shù)組 amount ,其中 amount[i] 表示:

  • 如果 amount[i] 的值是負(fù)數(shù),那么它表示打開節(jié)點(diǎn) i 處門扣除的分?jǐn)?shù)。
  • 如果 amount[i] 的值是正數(shù),那么它表示打開節(jié)點(diǎn) i 處門加上的分?jǐn)?shù)。

游戲按照如下規(guī)則進(jìn)行:

  • 一開始,Alice 在節(jié)點(diǎn) 0 處,Bob 在節(jié)點(diǎn) bob 處。
  • 每一秒鐘,Alice 和 Bob 分別 移動(dòng)到相鄰的節(jié)點(diǎn)。Alice 朝著某個(gè) 葉子結(jié)點(diǎn) 移動(dòng),Bob 朝著節(jié)點(diǎn) 0 移動(dòng)。
  • 對(duì)于他們之間路徑上的每一個(gè)節(jié)點(diǎn),Alice 和 Bob 要么打開門并扣分,要么打開門并加分。注意:
    • 如果門 已經(jīng)打開 (被另一個(gè)人打開),不會(huì)有額外加分也不會(huì)扣分。
    • 如果 Alice 和 Bob 同時(shí) 到達(dá)一個(gè)節(jié)點(diǎn),他們會(huì)共享這個(gè)節(jié)點(diǎn)的加分或者扣分。換言之,如果打開這扇門扣 c 分,那么 Alice 和 Bob 分別扣 c / 2 分。如果這扇門的加分為 c ,那么他們分別加 c / 2 分。
  • 如果 Alice 到達(dá)了一個(gè)葉子結(jié)點(diǎn),她會(huì)停止移動(dòng)。類似的,如果 Bob 到達(dá)了節(jié)點(diǎn) 0 ,他也會(huì)停止移動(dòng)。注意這些事件互相 獨(dú)立 ,不會(huì)影響另一方移動(dòng)。

請(qǐng)你返回 Alice 朝最優(yōu)葉子結(jié)點(diǎn)移動(dòng)的 最大 凈得分。

示例 1:

img

輸入:edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
輸出:6
解釋:
上圖展示了輸入給出的一棵樹。游戲進(jìn)行如下:
- Alice 一開始在節(jié)點(diǎn) 0 處,Bob 在節(jié)點(diǎn) 3 處。他們分別打開所在節(jié)點(diǎn)的門。Alice 得分為 -2 。
- Alice 和 Bob 都移動(dòng)到節(jié)點(diǎn) 1 。因?yàn)樗麄兺瑫r(shí)到達(dá)這個(gè)節(jié)點(diǎn),他們一起打開門并平分得分。Alice 的得分變?yōu)?-2 + (4 / 2) = 0 。
- Alice 移動(dòng)到節(jié)點(diǎn) 3 。因?yàn)?Bob 已經(jīng)打開了這扇門,Alice 得分不變。Bob 移動(dòng)到節(jié)點(diǎn) 0 ,并停止移動(dòng)。
- Alice 移動(dòng)到節(jié)點(diǎn) 4 并打開這個(gè)節(jié)點(diǎn)的門,她得分變?yōu)?0 + 6 = 6 。
現(xiàn)在,Alice 和 Bob 都不能進(jìn)行任何移動(dòng)了,所以游戲結(jié)束。
Alice 無法得到更高分?jǐn)?shù)。

示例 2:

img

輸入:edges = [[0,1]], bob = 1, amount = [-7280,2350]
輸出:-7280
解釋:
Alice 按照路徑 0->1 移動(dòng),同時(shí) Bob 按照路徑 1->0 移動(dòng)。
所以 Alice 只打開節(jié)點(diǎn) 0 處的門,她的得分為 -7280 。

提示:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges 表示一棵有效的樹。
  • 1 <= bob < n
  • amount.length == n
  • amount[i] 是范圍 [-104, 104] 之間的一個(gè) 偶數(shù) 。
class Solution {private int[] bobTime;private int[] amount;private int ans = Integer.MIN_VALUE;public int mostProfitablePath(int[][] edges, int bob, int[] amount) {int n = amount.length;bobTime = new int[n];Arrays.fill(bobTime, n);this.amount = amount;List<Integer>[] g = new ArrayList[n + 1];Arrays.setAll(g, e -> new ArrayList<>());for (var e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x); // 建樹}dfsBob(g, bob, -1, 0);g[0].add(-1);//防止把根節(jié)點(diǎn)當(dāng)成葉子dfsAlice(g, 0, -1, 0, 0);return ans;}public boolean dfsBob(List<Integer>[] g, int p, int father, int time) {if (p == 0) {//到達(dá)0點(diǎn)bobTime[p] = time;return true;} else {boolean found0 = false;for (int e : g[p]) {if (e != father && dfsBob(g, e, p, time + 1)) {found0 = true;break;}}if (found0) {//到達(dá)0點(diǎn)bobTime[p] = time;}return found0;}}//total表示路徑得分public void dfsAlice(List<Integer>[] g, int p, int father, int time, int total) {if (bobTime[p] == time) {//兩人相遇total += amount[p] / 2;}if (bobTime[p] > time) {total += amount[p];}//找到葉子結(jié)點(diǎn) 更新答案if (g[p].size() == 1) {ans = Math.max(ans, total);return;}for (int e : g[p]) {if (e != father) {dfsAlice(g, e, p, time + 1, total);}}}
}

968 監(jiān)控二叉樹

參考:樹形 DP:監(jiān)控二叉樹【基礎(chǔ)算法精講 25】_嗶哩嗶哩_bilibili

給定一個(gè)二叉樹,我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭。

節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象、自身及其直接子對(duì)象。

計(jì)算監(jiān)控樹的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量。

示例 1:

img

輸入:[0,0,null,0,0]
輸出:1
解釋:如圖所示,一臺(tái)攝像頭足以監(jiān)控所有節(jié)點(diǎn)。

示例 2:

img

輸入:[0,0,null,0,null,0,null,null,0]
輸出:2
解釋:需要至少兩個(gè)攝像頭來監(jiān)視樹的所有節(jié)點(diǎn)。 上圖顯示了攝像頭放置的有效位置之一。

提示:

  1. 給定樹的節(jié)點(diǎn)數(shù)的范圍是 [1, 1000]。
  2. 每個(gè)節(jié)點(diǎn)的值都是 0。

思路:

  • 藍(lán)色:安裝攝像頭
  • 黃色:不安裝攝像頭,父節(jié)點(diǎn)安裝攝像頭
  • 紅色:不安裝攝像頭,至少一個(gè)兒子安裝攝像頭

藍(lán)色=min(左藍(lán) 左黃 左紅)+min(右藍(lán) 右黃 右紅)+1

黃色=min(左藍(lán) 左紅)+min(右藍(lán) 右紅)

紅色=min(左藍(lán)+右紅 左紅+右藍(lán) 左藍(lán)+右藍(lán))

/*** 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 int minCameraCover(TreeNode root) {int[] res = dfs(root);return Math.min(res[0], res[2]);}private int[] dfs(TreeNode root) {if (root == null) {return new int[]{Integer.MAX_VALUE / 2, 0, 0};}int[] left = dfs(root.left);int[] right = dfs(root.right);int choose = Math.min(Math.min(left[0], left[1]), left[2]) + Math.min(Math.min(right[0], right[1]), right[2]) + 1;int byFather = Math.min(left[0], left[2]) + Math.min(right[0], right[2]);int byChildren = Math.min(Math.min(left[0] + right[2], left[2] + right[0]), left[0] + right[0]);return new int[]{choose, byFather, byChildren};}
}

此外,我們發(fā)現(xiàn)紅色的計(jì)算結(jié)果太多了(這一層有n個(gè)結(jié)點(diǎn),總共有2^n-1種情況),那么我們?cè)撊绾蝺?yōu)化呢?

假設(shè)我們?nèi)サ舯仨氝x一個(gè)藍(lán)色的條件,式子變?yōu)?code>min(藍(lán)1,紅1)+min(藍(lán)2,紅2)+min(藍(lán)3,紅3)

例如,min(5,2)+min(7,6)+min(5,1),要想選擇一個(gè)藍(lán)色,必須將一個(gè)紅色改為藍(lán)色,因此將6改為7最為合適

由此,我們知道需要找到min(藍(lán)-紅),所以得到如下的式子:

黃色=min(藍(lán)1,紅1)+min(藍(lán)2,紅2)+min(藍(lán)3,紅3)

紅色=黃色+max(0,min(藍(lán)1-紅2 藍(lán)2-紅2 藍(lán)3-紅3))

藍(lán)色=min(藍(lán)1 黃1)+min(藍(lán)2 黃2)+min(藍(lán)3 黃3)+cost[x]

cost[x]為花費(fèi)的成本

藍(lán)色一定大于紅色,所以第三個(gè)藍(lán)色的式子不用比較紅色,這就是如下的題目

保安站崗(洛谷)

SDOI2006\ 保安站崗 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {static int[] cost;static List<Integer>[] g;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();cost = new int[n + 1];g = new ArrayList[n + 1];//建樹Arrays.setAll(g, e -> new ArrayList<>());for (; n > 0; n--) {int v = sc.nextInt();v--;cost[v] = sc.nextInt();int m = sc.nextInt();for (; m > 0; m--) {int w = sc.nextInt();w--;g[v].add(w);g[w].add(v);}}int[] ans = dfs(0, -1);int choose = ans[0];int bySon = ans[2];System.out.println(Math.min(choose, bySon));}static int[] dfs(int x, int father) {int choose = cost[x];int byFather = 0;int minExtra = Integer.MAX_VALUE / 2;for (var y : g[x]) {if (y == father) {continue;}int[] arr = dfs(y, x);int c = arr[0];//藍(lán)色int byFa = arr[1];//黃色int bySon = arr[2];//紅色choose += Math.min(c, byFa);byFather += Math.min(c, bySon);minExtra = Math.min(minExtra, c - bySon);}return new int[]{choose, byFather, byFather + Math.max(0, minExtra)};}
}

LCP 34 二叉樹染色

LCP 34. 二叉樹染色 - 力扣(LeetCode)

小扣有一個(gè)根結(jié)點(diǎn)為 root 的二叉樹模型,初始所有結(jié)點(diǎn)均為白色,可以用藍(lán)色染料給模型結(jié)點(diǎn)染色,模型的每個(gè)結(jié)點(diǎn)有一個(gè) val 價(jià)值。小扣出于美觀考慮,希望最后二叉樹上每個(gè)藍(lán)色相連部分的結(jié)點(diǎn)個(gè)數(shù)不能超過 k 個(gè),求所有染成藍(lán)色的結(jié)點(diǎn)價(jià)值總和最大是多少?

示例 1:

輸入:root = [5,2,3,4], k = 2

輸出:12

解釋:結(jié)點(diǎn) 5、3、4 染成藍(lán)色,獲得最大的價(jià)值 5+3+4=12image.png

示例 2:

輸入:root = [4,1,3,9,null,null,2], k = 2

輸出:16

解釋:結(jié)點(diǎn) 4、3、9 染成藍(lán)色,獲得最大的價(jià)值 4+3+9=16image.png

提示:

  • 1 <= k <= 10
  • 1 <= val <= 10000
  • 1 <= 結(jié)點(diǎn)數(shù)量 <= 10000

思路

如果根節(jié)點(diǎn)是白色,那么返回左邊的最大和和右邊的最大和 即f[0]=maxleft+maxright

如果根節(jié)點(diǎn)是藍(lán)色

當(dāng)i=1時(shí),兩個(gè)兒子都為白色 此時(shí)f[i]=root.val+f[0](左)+f[0](右)

當(dāng)i=2時(shí),一個(gè)兒子為藍(lán)色

  • 如果k=2,可以分為 左 0 右 1、左 1 右 0 此時(shí) f[i]=max(root.val+f[0](左)+f[1](右),root.val+f[1](左)+f[0](右))
  • 如果k=3,可分為 左 0 右 2、左 1 右 1、左 2 右 0 三種情況;

最后得到 f[i]=max(val+f[j](左)+f[i-j-1](右))

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public int maxValue(TreeNode root, int k) {int[] ans = dfs(root, k);int max = Integer.MIN_VALUE;for (int a : ans) {max = Math.max(max, a);}return max;}private int[] dfs(TreeNode root, int k) {int[] f = new int[k + 1];if (root == null) {return f;}int[] left = dfs(root.left, k);int[] right = dfs(root.right, k);int maxLeft = Integer.MIN_VALUE;int maxRight = Integer.MIN_VALUE;for (int i = 0; i < k + 1; i++) {maxLeft = Math.max(maxLeft, left[i]);maxRight = Math.max(maxRight, right[i]);}f[0] = maxLeft + maxRight;for (int i = 0; i < k + 1; i++) {for (int j = 0; j < i; j++) {f[i] = Math.max(f[i], root.val + left[j] + right[i - j - 1]);}}return f;}
}

LCP 64 二叉樹燈飾

參考視頻:動(dòng)態(tài)規(guī)劃 樹形 DP【力扣杯2022秋·個(gè)人賽】_嗶哩嗶哩_bilibili

「力扣嘉年華」的中心廣場放置了一個(gè)巨型的二叉樹形狀的裝飾樹。每個(gè)節(jié)點(diǎn)上均有一盞燈和三個(gè)開關(guān)。節(jié)點(diǎn)值為 0 表示燈處于「關(guān)閉」?fàn)顟B(tài),節(jié)點(diǎn)值為 1 表示燈處于「開啟」?fàn)顟B(tài)。每個(gè)節(jié)點(diǎn)上的三個(gè)開關(guān)各自功能如下:

  • 開關(guān) 1:切換當(dāng)前節(jié)點(diǎn)的燈的狀態(tài);
  • 開關(guān) 2:切換 以當(dāng)前節(jié)點(diǎn)為根 的子樹中,所有節(jié)點(diǎn)上的燈的狀態(tài);
  • 開關(guān) 3:切換 當(dāng)前節(jié)點(diǎn)及其左右子節(jié)點(diǎn)(若存在的話) 上的燈的狀態(tài);

給定該裝飾的初始狀態(tài) root,請(qǐng)返回最少需要操作多少次開關(guān),可以關(guān)閉所有節(jié)點(diǎn)的燈。

示例 1:

輸入:root = [1,1,0,null,null,null,1]
輸出:2
解釋:以下是最佳的方案之一,如圖所示

示例1

示例 2:

輸入:root = [1,1,1,1,null,null,1]
輸出:1
解釋:以下是最佳的方案,如圖所示

示例2

示例 3:

輸入:root = [0,null,0]
輸出:0
解釋:無需操作開關(guān),當(dāng)前所有節(jié)點(diǎn)上的燈均已關(guān)閉

提示:

  • 1 <= 節(jié)點(diǎn)個(gè)數(shù) <= 10^5
  • 0 <= Node.val <= 1

思路:

任意一個(gè)結(jié)點(diǎn),會(huì)受到哪些影響:

  1. 祖先結(jié)點(diǎn)的開關(guān)2的切換次數(shù) 偶數(shù)=不切換 奇數(shù)=切換
  2. 父節(jié)點(diǎn)是否切換了開關(guān)3

狀態(tài):(當(dāng)前結(jié)點(diǎn) 開關(guān)2的切換次數(shù)的奇偶性 父節(jié)點(diǎn)是否開關(guān)3)

返回:當(dāng)前狀態(tài),最少需要操作的次數(shù)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private HashMap<TreeNode, int[][]> map;public int closeLampInTree(TreeNode root) {map = new HashMap<>();return dfs(root, false, false);}private int dfs(TreeNode root, boolean switch2_odd, boolean switch3) {if (root == null) return 0;//記憶化搜索int x = switch2_odd ? 1 : 0;int y = switch3 ? 1 : 0;int[][] temp = new int[2][2];if (map.containsKey(root)) {temp = map.get(root);if (temp[x][y] > 0) {return temp[x][y];}} else {map.put(root, temp);}int res = Integer.MAX_VALUE / 2;//燈打開 開關(guān)2和開關(guān)3抵消 燈開//燈關(guān)閉 開關(guān)2和開關(guān)3沒有抵消 燈開if ((root.val == 1) == (switch2_odd == switch3)) {int res1 = dfs(root.left, switch2_odd, false) + dfs(root.right, switch2_odd, false) + 1; int res2 = dfs(root.left, !switch2_odd, false) + dfs(root.right, !switch2_odd, false) + 1; int res3 = dfs(root.left, switch2_odd, true) + dfs(root.right, switch2_odd, true) + 1; int res123 = dfs(root.left, !switch2_odd, true) + dfs(root.right, !switch2_odd, true) + 3;res = Math.min(Math.min(res1, res2), Math.min(res3, res123)); } else {//燈關(guān)閉 不開開關(guān) 或者 開兩個(gè)開關(guān)int res0 = dfs(root.left, switch2_odd, false) + dfs(root.right, switch2_odd, false);int res12 = dfs(root.left, !switch2_odd, false) + dfs(root.right, !switch2_odd, false) + 2;int res13 = dfs(root.left, switch2_odd, true) + dfs(root.right, switch2_odd, true) + 2;int res23 = dfs(root.left, !switch2_odd, true) + dfs(root.right, !switch2_odd, true) + 2;res = Math.min(Math.min(res0, res12), Math.min(res13, res23));}temp[x][y] = res;return res;}
}
http://www.risenshineclean.com/news/50116.html

相關(guān)文章:

  • 網(wǎng)頁制作背景圖代碼杭州seo網(wǎng)站建設(shè)
  • 在家做網(wǎng)站查網(wǎng)址
  • 查詢商品價(jià)格走勢(shì)的網(wǎng)站自己建網(wǎng)站怎么弄
  • 網(wǎng)站微信認(rèn)證費(fèi)用多少錢八上數(shù)學(xué)優(yōu)化設(shè)計(jì)答案
  • seo做的不好的網(wǎng)站免費(fèi)網(wǎng)絡(luò)推廣平臺(tái)
  • r6300v2做網(wǎng)站搜索排名廣告營銷
  • 做出口網(wǎng)站鄭州新聞發(fā)布
  • 建設(shè)工程材料網(wǎng)站百度seo怎么優(yōu)化
  • 做廚柜有招聘網(wǎng)站嗎seo網(wǎng)站關(guān)鍵字優(yōu)化
  • 紙牌網(wǎng)站建設(shè)德陽seo
  • 網(wǎng)頁設(shè)計(jì)的注意事項(xiàng)網(wǎng)絡(luò)網(wǎng)站推廣優(yōu)化
  • 怎么在programmableweb 網(wǎng)站做api分析圖表深圳百度國際大廈
  • 所有做網(wǎng)站公司營銷廣告文案
  • 外貿(mào)網(wǎng)站該怎么做營銷存在的問題及改進(jìn)
  • 爾雅網(wǎng)站開發(fā)實(shí)戰(zhàn)百度站長工具網(wǎng)站提交
  • 廣告公司做的網(wǎng)站字體侵權(quán)武漢seo首頁
  • 美國做deals的網(wǎng)站中山百度推廣公司
  • 吉林省水土保持生態(tài)建設(shè)網(wǎng)站網(wǎng)站seo優(yōu)化方案設(shè)計(jì)
  • 關(guān)于做網(wǎng)站的調(diào)查問卷外包公司
  • 鎮(zhèn)江疫情最新數(shù)據(jù)seo免費(fèi)外鏈工具
  • 相親網(wǎng)與做網(wǎng)站廣州關(guān)鍵詞搜索排名
  • 網(wǎng)站建設(shè)初期工作方案網(wǎng)絡(luò)推廣項(xiàng)目代理
  • 廣州做企業(yè)網(wǎng)站找哪家公司好網(wǎng)絡(luò)營銷推廣方法和手段
  • 移動(dòng)網(wǎng)站的開發(fā)流程圖搜索引擎培訓(xùn)班
  • 淘寶客云建站官網(wǎng)百度q3財(cái)報(bào)2022
  • 做地產(chǎn)的設(shè)計(jì)網(wǎng)站seo顧問
  • 政府網(wǎng)站用什么cmsseo新人怎么發(fā)外鏈
  • 長沙外貿(mào)建站vue seo 優(yōu)化方案
  • 北京中高端網(wǎng)站建設(shè)友情鏈接買賣平臺(tái)
  • 網(wǎng)站免費(fèi)正能量不用下載歐洲站fba