函数加工

给定一个函数 f，可以 1～5 的数字等概率返回一个。请加工出 1～7 的数字等概率返回一个的函数 g。

思路：先将函数 f 转化为能随机得到 0、1的函数 r01 ，然后将 r01 没得到一个数就放到一个二进制位上，得到想要的范围内的数，如果超出范围就重新随机

代码实现：

  1. public class Rand5ToRand7 {
  3.     /**
  4.      * 1 ~ 5
  5.      */
  6.     public static int f() {
  7.         return (int) (Math.random() * 5 + 1);
  8.     }
  10.     /**
  11.      * 0 1
  12.      */
  13.     public static int r01() {
  14.         int num = 0;
  15.         // 如果等于 3 就一直循环
  16.         do {
  17.             num = f();
  18.         } while (num == 3);
  19.         return num > 3 ? 0 : 1;
  20.     }
  22.     /**
  23.      * 1 ~ 7
  24.      */
  25.     public static int g() {
  26.         // 1 ~ 7 = (0 ~ 6) + 1
  27.         // 6 是使用 3 个二进制位就可以表示，如果大于 6 就重新随机
  28.         int num = 0;
  29.         do {
  30.             num = (r01() << 2) + (r01() << 1) + r01();
  31.         } while (num > 6);
  32.         return num + 1;
  33.     }
  35.     public static void main(String[] args) {
  36.         for (int i = 10; i > 0; i--) {
  37.             System.out.println(g());
  38.         }
  39.     }
  40. }

给定一个函数 f，可以 a～b 的数字等概率返回一个。请加工出 c～d 的数字等概率返回一个的函数 g。
同样的思路：

  1. 将 f 加工为 0、1 发生器 r01，具体步骤：
    1. 计算 f 范围的中间值，mid = (b+a)/2
    2. 如果 b+a 是偶数，f() < mid 为 1，f() > mid 为 0，f() == mid 重新执行；如果 b+a 是奇数，f() <= mid 为 1，f() > mid 为 0
  2. r01 加工为 0 ~ (d-c) 范围，用 r01 代表二进制的每一位，超出范围就重新执行
  3. 返回结果 + c 就是在 c~d 范围

给定一个函数 f，以 p 概率返回 0，以 1-p 概率返回 1。请加工出等概率返回 0 和 1 的函数 g。
思路：
让函数 f 执行两次，如果结果为 00 或者 11 就重新执行两次；如果结果是 01 返回 0；结果是 10 返回 1。
f 执行两次的结果概率为：

  • 00 : p*p
  • 11 : (1-p) * (1-p)
  • 01 : p * (1-p)
  • 10 : (1-p) * p

01 和 10 的概率相同

n 个二叉树

给定一个非负整数 n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构

思路：
对于 n 个节点来说，存在如下情况：

  • n = 0，一种情况空节点
  • n = 1，一种情况单节点
  • n = 2，两种情况，头节点+左子节点、头节点+右子节点
  • n = i，……

image.png

代码实现：

  1. public class UniqueBST {
  3.     /**
  4.      * 递归版本
  5.      */
  6.     public static int numTrees(int n) {
  7.         if (n < 0) return 0;
  8.         if (n == 0) return 1;
  9.         if (n == 1) return 1;
  10.         if (n == 2) return 2;
  12.         int res = 0;
  13.         for (int leftNum = 0; leftNum <= n - 1; leftNum++) {
  14.             int leftWays = numTrees(leftNum);
  15.             int rightWays = numTrees(n - 1 - leftNum);
  16.             res += leftWays * rightWays;
  17.         }
  18.         return res;
  19.     }
  21.     /**
  22.      * 动态规划
  23.      */
  24.     public static int numTrees1(int n) {
  25.         if (n < 2) {
  26.             return 1;
  27.         }
  28.         int[] num = new int[n + 1];
  29.         num[0] = 1;
  30.         for (int i = 1; i < n + 1; i++) {
  31.             for (int j = 0; j <= i - 1; j++) {
  32.                 num[i] += num[j] * num[i - j - 1];
  33.             }
  34.         }
  35.         return num[n];
  36.     }
  39.     public static void main(String[] args) {
  40.         for (int i = 0; i < 15; i++) {
  41.             System.out.println(numTrees(i));
  42.             System.out.println(numTrees1(i));
  43.         }
  44.     }
  46. }

完整的括号

一个完整的括号字符串定义规则如下:

  1. 空字符串是完整的。
  2. 如果 s 是完整的字符串，那么 (s) 也是完整的。
  3. 如果 s 和 t 是完整的字符串，将它们连接起来形成的 st 也是完整的。

例如，"(()())"、"" 和 "(())()" 是完整的括号字符串，"())("、"()(" 和 ")" 是不完整的括号字符串。
牛牛有一个括号字符串 s，现在需要在其中任意位置尽量少地添加括号，将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号？

思路一：
如果将能匹配的括号对“消除掉”后，剩下的就是不能匹配的括号，有多少这样不能匹配的括号就会需要添加多少括号。具体步骤：

  1. 新建一个栈
  2. 将字符串按顺序遍历，当前字符为 cur，判断当前的 cur 是否组成了括号对，是否需要被“消除”
    • 如果栈为空，将 cur 放入栈中
    • 如果栈不为空，且 cur 为左括号，那就取栈顶元素是否为右括号，如果是右括号说明能组成括号对，将栈顶弹出，相当于执行了“消除”
    • 如果栈不为空，且 cur 为右括号，说明不能组成括号对，直接放入栈中
  3. 此时，在栈中就是不能组成括号对的数量，即：需要添加多少括号

思路二：
思路一的优点是只需要遍历一次字符串就能得到结果，但是在需要使用容器来存放不能匹配的括号，那么能不能优化栈使用的空间呢？可以使用统计括号的思路：
首先，如果判断一个字符串是否是完整的括号字符串，就可以这样统计：

  1. 一个统计值 count
  2. 遍历字符串，如果遇到左括号就 ++，遇到右括号就 —
  3. 如果 count 出现负数的情况，就说明出现了 )( 这样的括号。也就是说出现了不能匹配的括号，遍历结束
  4. 如果遍历完成 count == 0，且中间未出现 count < 0 的情况，说明了该字符串是完整括号字符串

伪代码如下：

  1. boolean isParentheses(String str) {
  2.     int count = 0;
  3.     for (int i = 0; i < str.length(); i++) {
  4.         char c = str.charAt(i);
  5.         if (c == '(') {
  6.             count ++;
  7.         } else {
  8.             count --;
  9.             if (count < 0) {
  10.                 return false;
  11.             }
  12.         }
  13.     }
  14.     return count == 0;
  15. }

上面的逻辑就解决是否是完整的括号字符串的问题，适当改造下就可以用来解决需要添加多少个括号的问题，现在逻辑上找到不能匹配的情况：

  • count < 0 时，说明出现了不能匹配的情况
  • 最后遍历完成 count != 0 时，说明有不能匹配的情况

count 统计了左括号被“消除”后多出来的数量，needNum 统计了右括号多出来的数量，最后的结果就是 count + needNum

做如下改造：

  1. int needParentheses(String str) {
  2.     int needNum = 0;
  3.     int count = 0;
  4.     for (int i = 0; i < str.length(); i++) {
  5.         char c = str.charAt(i);
  6.         if (c == '(') {
  7.             count ++;
  8.         } else {
  9.             count --;
  10.             if (count == -1) {
  11.                 count = 0;
  12.                 needNum ++;
  13.             }
  14.         }
  15.     }
  16.     return count + needNum;
  17. }

思路二其实使用两个变量来代替了原先的“消除”步骤

最后的代码实现：

  1. import java.util.Stack;
  3. public class NeedParentheses {
  4.     // 思路一
  5.     public static int needParentheses(String str) {
  6.         Stack<Character> stack = new Stack<>();
  7.         for (int i = 0; i < str.length(); i++) {
  8.             char c = str.charAt(i);
  9.             if (!stack.isEmpty()) {
  10.                 if (c == ')' && stack.peek() == '(') {
  11.                     stack.pop();
  12.                 } else {
  13.                     stack.push(c);
  14.                 }
  15.             } else {
  16.                 stack.push(c);
  17.             }
  18.         }
  19.         return stack.size();
  20.     }
  22.     // 思路二
  23.     public static int needParentheses1(String str) {
  24.         int leftRest = 0;
  25.         int needSolveRight = 0;
  26.         for (int i = 0; i < str.length(); i++) {
  27.             if (str.charAt(i) == '(') {
  28.                 leftRest++;
  29.             } else {
  30.                 if (leftRest == 0) {
  31.                     needSolveRight++;
  32.                 } else {
  33.                     leftRest--;
  34.                 }
  35.             }
  36.         }
  37.         return leftRest + needSolveRight;
  38.     }
  40.     public static void main(String[] args) {
  41.         System.out.println(needParentheses("())("));
  42.         System.out.println(needParentheses1("())("));
  43.         System.out.println(needParentheses("()("));
  44.         System.out.println(needParentheses1("()("));
  45.         System.out.println(needParentheses("("));
  46.         System.out.println(needParentheses1("("));
  47.         System.out.println(needParentheses("(((())((("));
  48.         System.out.println(needParentheses1("(((())((("));
  49.     }
  50. }

去重数字对

给定一个数组arr，求差值为 k 的去重数字对。

例如：
数组为 [3,2,5,7,0,0]，k 为 2，那么去重的数字对就为：3,5、5,7、0,2。
因为是去重的，所以即使有两个 0 也不能出现两次 0,2；也不能出现 3,5 5,3 这样的顺序不同的重复

思路：使用哈希表记录数组的值，然后遍历数组，判断该值 +k 后的值是否在哈希表中是否存在，如果存在就说明这两个数组成了一对

代码实现：

  1. package com.leetcodetest.middle;
  3. import java.util.ArrayList;
  4. import java.util.HashMap;
  5. import java.util.List;
  6. import java.util.Map;
  8. public class SubValueEqualK {
  9.     public static List<List<Integer>> allPair(int[] arr, int k) {
  10.         Map<Integer, Integer> map = new HashMap<>();
  12.         for (int i : arr) {
  13.             map.put(i, i + 2);
  14.         }
  16.         List<List<Integer>> list = new ArrayList<>();
  17.         for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  18.             if (map.containsKey(entry.getValue())) {
  19.                 List<Integer> pair = new ArrayList<>();
  20.                 pair.add(entry.getKey());
  21.                 pair.add(entry.getValue());
  22.                 list.add(pair);
  23.             }
  24.         }
  25.         return list;
  26.     }
  28.     public static void main(String[] args) {
  29.         int[] arr = {3, 2, 5, 7, 0, 0};
  31.         System.out.println(allPair(arr, 2));
  32.     }
  33. }

magic 操作

给一个包含 n 个整数元素的集合 a，一个包含 m 个整数元素的集合 b。 定义 magic 操作为，从一个集合中取出一个元素，放到另一个集合里，且操作过后每个集合的平均值都大于操作前。 注意以下两点：

  1. 不可以把一个集合的元素取空，这样就没有平均值了
  2. 值为 x 的元素从集合 b 取出放入集合 a，但集合 a 中已经有值为 x 的元素，则a的平均值不变（因为集合元素不会重复），b的平均值可能会改变（因为 x 被取出了）

问最多可以进行多少次 magic 操作？

思路：
假设：

  • a 的平均值等于 b 的平均值，平均值都为 100：
    • 如果从 a 取出大于 100 的数，a 的平均值会减少，不成立
    • 如果从 a 取出等于 100 的数，a 的平均值不变，不成立
    • 如果从 a 取出小于 100 的数，a 的平均值变大，b 的平均值变小，不成立

所以，本情况不成立

  • a 的平均值 50 小于 b 的平均值 100：
    • 如果从 a 取出大于 50 的数，a 的平均值会减少，不成立
    • 如果从 a 取出等于 50 的数，a 的平均值不变，b 的平均值变小，不成立
    • 如果从 a 取出小于 50 的数，b 的平均值会减少，不成立
  • a 的平均值 100 大于 b 的平均值 50：
    • 如果从 a 取出大于 100 的数，a 的平均值会减少，不成立
    • 如果从 a 取出等于 100的数，a 的平均值不变，b 的平均值变大，不成立
    • 如果从 a 取出小于 100 的数，a 的平均值变大
      • 若该数大于 50，b 的平均值变大，成立
      • 若该数小于 50，b 的平均值变小，不成立

综上，确立了条件：只有当 a 的平均值 大于 b 的平均值，取出 x 小于 a 的平均值且大于 b 的平均值时，才能满足条件。

那么应该怎么取 x 呢？
假设，a = {60, 70, 80, 90, 100, 110, 120, 130, 140} 平均值为 100，b = {50} 平均值为 50，此时，满足 x 小于 a 的平均值且大于 b 的平均值 的值有 {60, 70, 80, 90}。

  • 从小到大取 60，取出 60 后，对 a 的平均值提升最大，变成 105；对 b 的平均值提升最小，变成 55； x 的取值范围，从 [50, 100] 变成 [55, 105]
  • 从大到小取 90，取出 90 后，对 a 的平均值提升最小，变成 101；对 b 的平均值提升最大，变成 70； x 的取值范围，从 [50, 100] 变成 [70, 101]，变小了

综上，取 x 应该从小到大取

最多可以取多少次 magic 呢？
由于 x 的取值范围会发生变化，在具体到多少次的计算中，应该每次取完数后重新去下一个数，直到取出最后一个数为止。

代码实现：

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  5. public class MagicOp {
  6.     // 请保证arr1无重复值、arr2中无重复值，且arr1和arr2肯定有数字
  7.     public static int maxOps(int[] arr1, int[] arr2) {
  8.         // 排序
  9.         Arrays.sort(arr1);
  10.         Arrays.sort(arr2);
  12.         // 和
  13.         int sum1 = Arrays.stream(arr1).sum();
  14.         int sum2 = Arrays.stream(arr2).sum();
  16.         // 平均值
  17.         double avg1 = sum1 / arr1.length;
  18.         double avg2 = sum2 / arr2.length;
  20.         if (avg2 >= avg1) return 0;
  22.         List<Integer> optList = new ArrayList<>();
  23.         Integer min = null;
  24.         while (avg1 > avg2) {
  25.             // 找到 > avg2 && < avg1 的最小的值
  26.             for (int item : arr1) {
  27.                 if (item > avg2 && item < avg1 && !optList.contains(item)) {
  28.                     min = item;
  29.                     break;
  30.                 }
  31.             }
  32.             if (min == null || arr1.length == optList.size() + 1) {
  33.                 // 获取不到满足条件的值 或 已经要把 arr1 取完了 就停止
  34.                 break;
  35.             }
  36.             optList.add(min);
  37.             // 重算平均值
  38.             sum1 -= min;
  39.             sum2 += min;
  40.             avg1 = sum1 / (arr1.length - optList.size());
  41.             avg2 = sum2 / (arr2.length + optList.size());
  42.             System.out.println("取出 " + min + " 新的范围是 [" + avg2 + ", " + avg1 + "]");
  43.         }
  45.         return optList.size();
  46.     }
  48.     public static void main(String[] args) {
  49.         System.out.println(maxOps(new int[]{60, 70, 80, 90, 100, 110, 120, 130, 140}, new int[]{50}));
  50.     }
  51. }

数字转字符串

将给定的数转换为字符串，原则如下：1 对应 a，2 对应 b，…..26 对应 z，例如 12258
可以转换为 “abbeh”、”aveh”、”abyh”、”lbeh” 和 “lyh”，个数为 5，编写一个函数，给出可以转换的不同字符串的个数。

思路：
遍历字符串，从 i 位置开始：

  • i 不等于 0，直接转为字母，
  • i 等于 0 不能单独转为字母，必须和前面的 i-1 组合
  • i 和 i + 1 组成的数字转为字母，不能大于 26

开始递归

  1. public class NumToStringWays {
  3.     // 递归
  4.     public static int convertWays1(int num) {
  5.         if (num <= 0) return 0;
  7.         return process(num + "", 0);
  8.     }
  10.     public static int process(String str, int index) {
  11.         if (index == str.length()) return 1;
  13.         if (str.charAt(index) == '0') { // 不能以 0 开头，只能和之前的数组合
  14.             return 0;
  15.         }
  17.         int res = 0;
  18.         res += process(str, index + 1);
  20.         if (str.length() >= index + 2) {
  21.             if (Integer.parseInt(str.substring(index, index + 2)) <= 26) {
  22.                 res += process(str, index + 2);
  23.             }
  24.         }
  26.         return res;
  27.     }
  29.     // 动态规划
  30.     public static int convertWays2(int num) {
  31.         if (num <= 0) return 0;
  32.         String str = num + "";
  33.         int length = str.length();
  34.         int[] dp = new int[length + 1];
  36.         dp[length] = 1;
  38.         dp[length - 1] = str.charAt(length - 1) == '0' ? 0 : 1;
  40.         for (int i = length - 2; i >= 0; i--) {
  41.             if (str.charAt(i) == '0') {
  42.                 dp[i] = 0;
  43.             } else {
  44.                 dp[i] = dp[i + 1];
  45.                 if (Integer.parseInt(str.substring(i, i + 2)) <= 26)
  46.                     dp[i] += dp[i + 2];
  48.             }
  49.         }
  51.         return dp[0];
  52.     }
  54.     public static void main(String[] args) {
  55.         System.out.println(convertWays1(12258));
  56.         System.out.println(convertWays1(12));
  57.         System.out.println(convertWays1(122));
  58.         System.out.println(convertWays1(1207));
  59.         System.out.println("=================");
  60.         System.out.println(convertWays2(12258));
  61.         System.out.println(convertWays2(12));
  62.         System.out.println(convertWays2(122));
  63.         System.out.println(convertWays2(1207));
  64.     }
  65. }

括号的深度

一个合法的括号匹配序列有以下定义：

  1. 空串 "" 是一个合法的括号匹配序列
  2. 如果 "X" 和 "Y" 都是合法的括号匹配序列，"XY" 也是一个合法的括号匹配序列
  3. 如果 "X" 是一个合法的括号匹配序列，那么 "(X)" 也是一个合法的括号匹配序列
  4. 每个合法的括号序列都可以由以上规则生成。

例如：""、"()"、"()()"、"((()))" 都是合法的括号序列

对于一个合法的括号序列我们又有以下定义它的深度：

  1. 空串 "" 的深度是 0
  2. 如果字符串 "X" 的深度是 x，字符串 "Y" 的深度是 y，那么字符串 "XY" 的深度为max(x, y)
  3. 如果 "X" 的深度是 x，那么字符串 "(X)" 的深度是 x+1

例如：
"()()()" 的深度是 1
"((()))" 的深度是3

牛牛现在给你一个合法的括号序列，需要你计算出其深度。

思路：
首先如何判断一个字符串是否是合法的括号序列呢？
一般我们首先会想到：使用栈结构。遍历字符串，遇到左括号保存到栈中；遇到右括号就将栈顶弹出。如果整个遍历过程中栈不为空，且遍历完成后栈为空，那么说明是合法的括号序列。

利用上面的逻辑稍加改造就可以完成本题，在本题中会给出一个合法的括号序列，那么在栈中的左括号数量最多时，就是给出的序列最大的深度。

也可以稍微优化下，不使用栈，而是使用一个变量来记录遍历的最大深度。

  1. import java.util.Stack;
  3. public class ParenthesesDeep {
  5.     public static int deep1(String str) {
  6.         if (str == null && str == "") return 0;
  8.         int deep = 0;
  9.         Stack<Character> stack = new Stack<>();
  10.         for (int i = 0; i < str.length(); i++) {
  11.             if (str.charAt(i) == '(') {
  12.                 stack.push('(');
  13.             } else {
  14.                 stack.pop();
  15.             }
  16.             deep = Math.max(deep, stack.size());
  17.         }
  18.         return deep;
  19.     }
  21.     public static int deep2(String str) {
  22.         if (str == null && str == "") return 0;
  24.         int curDeep = 0;
  25.         int deep = 0;
  26.         for (int i = 0; i < str.length(); i++) {
  27.             if (str.charAt(i) == '(') {
  28.                 curDeep++;
  29.             } else {
  30.                 curDeep--;
  31.             }
  32.             deep = Math.max(curDeep, deep);
  33.         }
  34.         return deep;
  35.     }
  37.     public static void main(String[] args) {
  38.         System.out.println(deep1("()()()"));
  39.         System.out.println(deep1("((()))"));
  40.         System.out.println(deep1("((())((())()))"));
  42.         System.out.println(deep2("()()()"));
  43.         System.out.println(deep2("((()))"));
  44.         System.out.println(deep2("((())((())()))"));
  45.     }
  46. }

上面的简直 so easy，那么如果改为这样的问题呢：
给出一堆有左右括号组成的字符串，求出最长合法的括号序列的长度？

思路一：
题意也就是要找到最大的合法子串，那就要知道什么不时候不合法：右括号比左括号多的时候不合法。
在不合法时，记录已找到合法的子串长度，找到最大的长度即可

思路二：
遍历字符串，求出每个右括号结尾的合法字符串的长度，然后找到最大值

代码实现：

  1. // 思路一
  2. public static int maxLength(String str) {
  3.     if (str == null && str == "") return 0;
  5.     int maxLength = 0;
  6.     int curLength = 0;
  7.     int leftNum = 0;
  8.     for (int i = 0; i < str.length(); i++) {
  9.         if (str.charAt(i) == '(') {
  10.             leftNum++;
  11.         } else {
  12.             if (leftNum > 0) {
  13.                 leftNum--;
  14.                 curLength += 2;
  15.             } else {
  16.                 curLength = 0;
  17.             }
  18.             maxLength = Math.max(maxLength, curLength);
  19.         }
  20.     }
  21.     return maxLength;
  22. }
  24. // 思路二
  25. public static int maxLength1(String str) {
  26.     if (str == null || str.equals("")) {
  27.         return 0;
  28.     }
  29.     char[] chas = str.toCharArray();
  30.     int[] dp = new int[chas.length];
  31.     int pre = 0;
  32.     int res = 0;
  33.     for (int i = 1; i < chas.length; i++) {
  34.         if (chas[i] == ')') { // 只有右括号才能结尾
  35.             // 假设合法，和 i 匹配的左括号的下标
  36.             pre = i - dp[i - 1] - 1;
  37.             if (pre >= 0 && chas[pre] == '(') {
  38.                 // 如果上一个右括号能组成解法序列，那么 i 下标就是 i-i 的结果 + 2 + 上一个子串的长度
  39.                 dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
  40.             }
  41.         }
  42.         res = Math.max(res, dp[i]);
  43.     }
  44.     return res;
  45. }

有序栈

请编写一个程序，对一个栈里的整型数据，按升序进行排序（即排序前，栈里的数据是无序的，排序后最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

思路：
一个辅助栈 help，保证该栈中数据有序且小元素在栈顶。
遍历栈 cur = stack.pop();：

  • 如果 help 为空，就直接将 cur 压入 help 中
  • 如果 help 不为空，取 help 栈顶元素和 cur 做比较：
    • 栈顶元素 比 cur 大，将 cur 压入help
    • 栈顶元素 比 cur 小，将栈顶弹出并压入 stack 中，直到新的栈顶比 cur 大，将 cur 压入；或者 help 元素为空
  • 将上述操作执行完成后，stack 为空，help 中所有元素都是有序且栈顶为最小元素，依次将 help 所有元素弹出压入 stack

image.png

代码实现：

  1. import java.util.Stack;
  3. public class SortStack {
  5.     public static void sortStack(Stack<Integer> stack) {
  6.         if (stack == null || stack.isEmpty()) return;
  8.         // 小元素在上的栈
  9.         Stack<Integer> minStack = new Stack<>();
  11.         while (!stack.isEmpty()) {
  12.             Integer top = stack.pop();
  13.             while (!minStack.isEmpty() && minStack.peek() < top) {
  14.                 stack.push(minStack.pop());
  15.             }
  16.             minStack.push(top);
  17.         }
  19.         while (!minStack.isEmpty()) stack.push(minStack.pop());
  20.     }
  22.     public static void main(String[] args) {
  23.         Stack<Integer> stack = new Stack<Integer>();
  24.         stack.push(3);
  25.         stack.push(1);
  26.         stack.push(6);
  27.         stack.push(2);
  28.         stack.push(5);
  29.         stack.push(4);
  30.         sortStack(stack);
  31.         System.out.println(stack.pop());
  32.         System.out.println(stack.pop());
  33.         System.out.println(stack.pop());
  34.         System.out.println(stack.pop());
  35.         System.out.println(stack.pop());
  36.         System.out.println(stack.pop());
  37.     }
  38. }

最大权值

二叉树每个结点都有一个 int 型权值，给定一棵二叉树，要求计算出从根结点到叶结点的所有路径中，权值和最大的值为多少。

思路一：
对于树中任意的节点来说，该节点的最大的路径为 该节点的权值 + 子树中最大的权值

思路二：
使用 map 来保存每条路径的最大值

代码实现：

  1. import java.util.HashMap;
  2. import java.util.Map;
  3. import java.util.Stack;
  5. public class MaxSumInTree {
  6.     public static class Node {
  7.         public int value;
  8.         public Node left;
  9.         public Node right;
  11.         public Node(int val) {
  12.             value = val;
  13.         }
  14.     }
  16.     // 递归
  17.     public static int maxSumRecursive(Node head) {
  18.         if (head == null) return 0;
  19.         return process(head);
  20.     }
  22.     public static int process(Node node) {
  23.         if (node == null) return 0;
  25.         int leftData = node.value + process(node.left);
  26.         int rightData = node.value + process(node.right);
  27.         return Math.max(leftData, rightData);
  28.     }
  30.     // 非递归
  31.     private static int maxSumUnrecursive(Node head) {
  32.         if (head == null) return 0;
  34.         Stack<Node> stack = new Stack<>();
  35.         stack.push(head);
  37.         Map<Node, Integer> sumMap = new HashMap<>();
  38.         sumMap.put(head, head.value);
  40.         int max = 0;
  42.         while (!stack.isEmpty()) {
  43.             Node cur = stack.pop();
  44.             if (cur.left == null && cur.right == null) max = Math.max(max, sumMap.get(cur));
  46.             if (cur.right != null) {
  47.                 sumMap.put(cur.right, sumMap.get(cur) + cur.right.value);
  48.                 stack.push(cur.right);
  49.             }
  51.             if (cur.left != null) {
  52.                 sumMap.put(cur.left, sumMap.get(cur) + cur.left.value);
  53.                 stack.push(cur.left);
  54.             }
  55.         }
  57.         return max;
  58.     }
  60.     public static void main(String[] args) {
  61.         Node head = new Node(4);
  62.         head.left = new Node(1);
  63.         head.left.left = new Node(24);
  64.         head.left.left.right = new Node(2);
  65.         head.left.right = new Node(25);
  66.         head.right = new Node(-7);
  67.         head.right.left = new Node(3);
  68.         head.right.right = new Node(30);
  69.         System.out.println(maxSumRecursive(head));
  70.         System.out.println(maxSumUnrecursive(head));
  71.     }
  72. }