前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、寻找重复数（题号：287）
描述：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2: 输入: [3,1,3,4,2] 输出: 3
说明：
1）不能更改原数组（假设数组是只读的）。
2）只能使用额外的O(1)空间。
3）时间复杂度小于O(n^2)。
4）数组中只有一个重复的数字，但它可能不止一次的出现。
解题思路：如果不限定额外空间复杂度，我们可以使用的手段就很多了，比如使用TreeMap。如果采取双层循环比较，那么时间复杂度就是O(N^2)。
我们曾经做过一个题目，就是验证一个单项链表是否有环，使用快慢指针来解题。数组也是个线性存储结构，重复节点元素也可以看成环的交点。
public class TestMain {
public static void main(String[] args) {
int[] source = {3,1,3,4,2};
System.out.println(execute(source));
}
/**
* 此题本身并不复杂，但是其思路很巧妙，跟判断链表是否有环很像。
* 设计两个指针，快、慢指针。将数组看成循环数组。
* 两个指针并行移动，知道找到两个数字相同、且index不同。
*
* 此题的前提：只有一个重复的元素。
* @param source
* @return
*/
private static int execute(int[] source) {
int si = 0;//慢指针，每次移动1个。到达尾部结束
int fi = 0;//快指针，每次移动2个元素。到达尾部则继续循环
int length = source.length;
while (si < length) {
int sv = source[si];
fi = (fi + 1) % length;
int fv = source[fi];
if (sv == fv && fi != si) {
return sv;
}
fi = (fi + 1) % length;
if (sv == fv && fi != si) {
return sv;
}
si++;
}
return -1;
}
}
二、二叉树的序列化和反序列化（题号：297）
描述：序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
解题思路：二叉树序列化的方式很多，如果非搜索树或者满二叉树，能够复原的序列化方式、易于实现的就是广度遍历；对于任何节点，其左右节点如果为null，则用一个特殊的占位符表示，则在反序列化时，总是成对的解析结果，遇到占位符则用null表示。
public class TestMain {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode n1 = new TreeNode(2);
TreeNode n2 = new TreeNode(3);
TreeNode n3 = new TreeNode(4);
TreeNode n4 = new TreeNode(5);
root.left = n1;
root.right = n2;
n2.left = n3;
n2.right = n4;
String sr = Codec.serialize(root);
System.out.println(sr);
TreeNode dr = Codec.deserialize(sr);
System.out.println(dr);
}
public static class Codec {
/**
* 对于非满二叉树，只有广度遍历的结果，才能适用于序列化和反序列化。
* 其他遍历方式，在序列化和反序列时更加复杂。
* @param root
* @return
*/
public static String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node == null) {
sb.append("-");//null
continue;
}
sb.append(node.value);
queue.offer(node.left);//可能是null
queue.offer(node.right);//可能是null;
}
}
return sb.toString();
}
/**
* 反序列化
* @param data
* @return
*/
public static TreeNode deserialize(String data) {
TreeNode root = new TreeNode(Character.digit(data.charAt(0),10));
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
int i = 1;
while (i < data.length()) {
TreeNode node = queue.poll();
char cv = data.charAt(i);
if (cv != '-') {
node.left = new TreeNode(Character.digit(cv,10));
queue.offer(node.left);
}
//只要父节点不为null，子节点总是成对的被解析。
char nv = data.charAt(++i);
if (nv != '-') {
node.right = new TreeNode(Character.digit(nv,10));
queue.offer(node.right);
}
++i;
}
return root;
}
}
public static class TreeNode {
private int value;
private TreeNode left;
private TreeNode right;
public TreeNode(int value) {
this.value = value;
}
}
}
三、最小高度树（题号：310）
描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
格式：
该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
示例 1:
输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
输出: [1]
示例 2:
输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
输出: [3, 4]
说明:
1）根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
2）树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
解题思路：最小高度树，即从跟节点到叶子节点的高度的最大值是最小；对于这种无向树图，选定任意一个节点作为跟节点，都会产生一个树高（跟节点到最远叶子的距离）；树高最小，那么我在无法直接找到最长路径的前提下，完成此题；只能通过不断删除叶子节点（0入度）的方式达成。
public class TestMain {
public static void main(String[] args) {
int[][] s1 = {{1, 0}, {1, 2}, {1, 3}};
System.out.println(execute(4,s1));
int[][] s2 = {{0, 3}, {1, 3}, {2, 3}, {4, 3}, {5, 4}};
System.out.println(execute(6,s2));
}
/**
*
* @param n 节点个数，节点的值域 [0,n),这个前提很重要。
* @param source 无向边
* @return
*/
private static Collection<Integer> execute(int n, int[][] source) {
if (n == 0) {
return Collections.singletonList(0);
}
//初始化，如果节点的值不是数字，此处需要换成Map
List<Set<Integer>> container = new ArrayList<>(n);
for (int i = 0; i < n;i++) {
container.add(new HashSet<>());//先占位
}
for (int[] item : source) {
//每个节点的关联的节点列表
container.get(item[0]).add(item[1]);
container.get(item[1]).add(item[0]);
}
//找到叶子节点，即只有一个元素与其关联，暂且不考虑树深问题。
Queue<Integer> leaves = new LinkedList<>();
for (int i = 0; i < n; ++i) {
if (container.get(i).size() == 1) {
leaves.add(i);
}
}
/**
* 首先，我们不需要找到树图的最长路径，只需要按照如下方式：
* 1）删除所有的叶子节点 （即入度为0的节点，没有前驱）
* 2）剩余的树结构，继续找到叶子节点，重复1）
* 3）知道树中剩余1、2个节点，那么剩余的节点即为最小高度数的跟。
*
* 既然无向图，节点个数超过2，一定存在0入度
*/
while (leaves.size() > 2) {
int size = leaves.size();
//逐批删除
for (int i=0; i < size; i++) {
int v = leaves.poll();
//新的叶子节点
//获此其叶子节点的关联节点
int j = container.get(v).iterator().next();
//将其从关联节点中移除
container.get(j).remove(v);
//如果此关联节点，只被叶子节点引用
//移除所有叶子节点之后，此关联节点也是叶子节点
if (container.get(j).size() == 1) {
leaves.add(j);
}
}
}
return leaves;
}
}
四、计算右侧小于当前元素的个数（题号：315）
描述：给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例: 输入: [5,2,6,1] 输出: [2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1). 2 的右侧仅有 1 个更小的元素 (1). 6 的右侧有 1 个更小的元素 (1). 1 的右侧有 0 个更小的元素.
说明：元素可能重复。元素值均为数字。
解题思路：暴力遍历法，实现起来很简单，但是时间复杂度O(N^2)，这不是此题考查的主要目的。我们输出每个元素右边比起小的元素个数，同时我们不能在原数组上进行排序来解答，我们都知道BST（二叉搜索树）可以很便捷的获取比其小的节点个数，因为左子树的节点个数就是答案。此题查看此元素右边比起小的元素个数，我们可以从右到左遍历数组，并构建BST，插入新节点时通过统计“跳过的所有左子树元素”个数即可得到结果。此题构建BST的过程，也可以作为单独的考察点。
示例:
输入: [7,5,2,6,1]
BST：
1
\
6
/ \
2 7
\
5
public class TestMain {
public static void main(String[] args) {
int[] source = {7,5,2,6,1};
int[] result = execute(source);
System.out.println(result);
}
private static int[] execute(int[] source) {
int length = source.length;
int[] result = new int[length];
Node root = null;
//每个节点，都从root开始寻路，插入到合适的位置，最终构建一个BST。
for (int i = length - 1; i >= 0; i--) {
root = insertNode(source[i], root, i, 0, result);
}
return result;
}
public static class Node {
int value;//当前值
int sum = 0;//小于value的子节点个数（不包含=，即左子树节点个数）
int dup = 1;//重复次数，重复值只做计数标记
Node left;//比value值小的，在左边
Node right;//比value值大的，在有变
public Node(int value) {
this.value = value;
}
}
/**
*
* @param value 需要插入的节点值
* @param node 遍历时，当前需要比较的节点值
* @param i 当前节点值在原始数组的位置
* @param prevSum 在插入之前，遍历BST时，遇到的小于value的节点的个数。
* 如果一个节点值小于value，那么此节点的所有左子树的节点都小于它，所以它的值为（当前节点左子树节点个数 + 等于当前节点值的重复元素个数（包括自己） + 父节点小于value的节点个数）
* @param result 插入一个节点时，就是遍历的过程，result记录小于value的节点个数
* @return
*/
private static Node insertNode(int value, Node node, int i, int prevSum, int[] result) {
//如果node尚未构建，则插入
if (node == null) {
node = new Node(value);
result[i] = prevSum;
} else if (value == node.value) {
node.dup += 1;
result[i] = prevSum + node.sum;
} else if (value > node.value) {
//构建right节点，
node.right = insertNode(value, node.right, i, prevSum + node.sum + node.dup, result);
} else {
node.sum += 1;
node.left = insertNode(value, node.left, i, prevSum, result);
}
return node;
}
}
五、零钱兑换（题号：322）
描述：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1
说明：你可以认为每种硬币的数量是无限的。
解题思路：社区有很多种解题办法，不过有些思路本人理解起来比较困难。本文用动态规划的方式来解题，比如面值为[1,2,5]，总额为11，易于理解的作法就是找最大数，我们可以用5面值2个硬币，余数1，再用其他面值补充；此后我们还可以用2面值的5个硬币，余数1，再用其他面值补充。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute(new int[]{1,2,5},11));
System.out.println(execute(new int[]{2},3));
}
/**
* 动态规划方式，比如n=11,硬币面值为1，2，5
* 依次将其中一个面值的硬币，作为最多数，将余数使用其他面值去继续验证。
* 比如：
* 1）将5作为最多数，11 / 5 = 2，即可以有2个5，余数为1，将1作为输入，继续验证所有面值的硬币，此时只有1面值支持，即[1,5,5]
* 2）将2作为最多数，11 / 2 = 5,即可以有5个2，余数为1，将1作为输入验证所有面值的硬币，此值只有1面值支持，即[2,2,2,2,2,1]
*
* @param source
* @param n
* @return
*/
private static List<Integer> execute(int[] source,int n) {
List<Integer> result = new ArrayList<>();//计算结果
//根据输入值n，依次验证所有面值，n可以原始输入值，也可以是其他面值的余数
for (int i : source) {
if (n < i) {
continue;
}
//当前面值的硬币个数
int x = n / i;
//如果result已经保存了其他面值的成功的结果，则查看其硬币个数是否最少
//如果当前面值的个数，多，则放弃此次结果。因为我们题目要求返回硬币个数最少的组合。
if (!result.isEmpty() && x > result.size()) {
continue;
}
//余数
int y = n % i;
//余数不为0，则递归，尝试使用其他面值补充
if (y != 0) {
List<Integer> _current = execute(source,y);
//如果为空，表示其他面值的，无法满足结果
if (_current.isEmpty()) {
continue;
}
//如果其他面值可以满足余数，且当前计算的所有硬币数 大于历史计算的组合，则放弃
if (_current.size() + x > result.size()) {
continue;
}
//否则，清空历史结果，将当前组合保存
result.clear();
result.addAll(_current);
}
//余数为0，或者余数能够被其他面值满足时，将当前硬币数量添加到结果中
for (int t = 0; t < x; t++) {
result.add(i);
}
}
return result;
}
}
六、验证二叉树的前序序列化（题号：331）
描述：序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。
编写一个在不重构树的条件下的可行算法。每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例 1: 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true 示例 2: 输入: "1,#" 输出: false 示例 3: 输入: "9,#,#,1" 输出: false
解题思路：遍历字符串时，构建逻辑二叉树，并对空的叶子节点删除。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute("9,3,4,#,#,1,#,#,2,#,6,#,#"));
System.out.println(execute("1,#"));
}
/**
* 前序遍历结果的特点：
* 1）第一个元素为根节点。
* 2）跟节点左子树节点，都在右子树的前面。
* 3）最底层的节点，保持可读的"中左右"
*
* 本题的前提是，一个节点为null，则用"#"代替。
* 根据本题，一个节点如果为#，那么其不再有左右节点。
*
* 本题的解题思路，就是"删子节点"：
* 1）如果一个节点值不是#，说明其存在左右节点（也可能为#）
* 2) 遍历时，如果要值为#,需要看其上一个元素值是否为#（左节点或者父节点）
* A）如果上一个元素为#，当前元素必定为子树的右节点，表明此节点已经为叶子节点，则删除其所在的左、父节点，并将#值补充到父节点位置（标记为此父节点已没有子节点）
* B）如果上一个元素不为#，则表示此节点正常，而且它还可能有子节点，所以需要暂存。
* C）根据A，删除空的叶子节点时，需要继续向上遍历并删除，直到遇到非空子树为止。
* 3）如果最终树为空，则表示遍历数组，对应的逻辑树，是合法的二叉树。如果最终逻辑树还有未被删除的节点，则表示通过数组构建逻辑树时存在缺失节点的情况。
* @param source
* @return
*/
private static boolean execute(String source) {
//基本校验
if (source == null || source.length() == 0) {
return false;
}
String[] container = source.split(",");
//使用栈保存
Stack<String> stack = new Stack<>();
for (int i = 0; i < container.length; i++) {
String value = container[i];
//如果当前元素为#,对应逻辑树，就是一个空节点
if (value.equals("#")) {
while (!stack.isEmpty()) {
//如果上一个节点不是空，表明，当前节点可能是左节点或者父节点
if (!stack.peek().equals("#")) {
break;
}
//如果上一个节点也为#,表示当前节点，为叶子节点，且父节点的两个子节点都是空
//则删除父节点
stack.pop();
//如果不对称，则非法
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
//将当前值加入队列
// 对于#也需要加入，表明是个空节点，或者一路删除之后占位的空节点
stack.push(value);
}
String last = stack.pop();
//逻辑树为空
return stack.isEmpty() && last.equals("#");
}
}
七、重新安排行程（题号：332）
描述：给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。
说明:
1）如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
2）所有的机场都用三个大写字母表示（机场代码）。
3）假定所有机票至少存在一种合理的行程。
特别说明：这是一个有效行程，即它总是一个有效的单向路径，不存在中间分叉的情况。这与树不一样，这是个有向图。
示例 1: 输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] 输出: ["JFK", "MUC", "LHR", "SFO", "SJC"] 示例 2: 输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] 输出: ["JFK","ATL","JFK","SFO","ATL","SFO"] 解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
解题思路：刚开始，本人尝试使用拓扑排序的方式解决，但是其实是无法得到答案的（拓扑排序，存在0入度节点）。后来明确了题目前提之后，转换为有向图的深度遍历（DFS）方式，从给定的起始节点开始，按照方向深度遍历，直到最后一个“0出度”节点即可。
public class TestMain {
public static void main(String[] args) {
String[][] s1 = {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
System.out.println(execute(s1));
String[][] s2 = {{"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"}};
System.out.println(execute(s2));
}
/**
* 深度遍历的典型使用，指定起点，然后输出一条最长路径。
* 跟拓扑排序（图排序）有些不同，因为深度遍历，通常指定起点，拓扑排序需要首先知道0入度节点。
* 刚开始，我本人也是借鉴拓扑排序，发现很难实现此题的要求。
*
* 深度遍历，就是根据起点开始，依次跟进每个有向边的节点知道结束。路径可能有多个。
* 本题，是航班，也是有向路径的一种表达。
* 千万不要忽略本题的几个条件：
* 1）一定至少存在一种合理的路径。
* 2）如果一个出发站点，航班有多个，字典顺序。
* 3) 本题是个行程表，这以为不存在一个出发站、对应两个到达站、且两个到达站之间还不存在航班的情况。即此航班安排是合理，我们只需要重新安排即可。
* 比如：
* A -> B -> C
* |
* | -> D
*
* 这个跟一个树的深度遍历（通常为前序）有区别
* @param tickets
* @return
*/
private static List<String> execute(String[][] tickets) {
//key为出发站点，value为按照字典排序的到达站点
//保存一个出发点，可以到达的所有航班，航班信息按照站点的字典顺序排序。
Map<String, PriorityQueue<String>> flights = new HashMap<>();
for (String[] ticket : tickets) {
flights.putIfAbsent(ticket[0], new PriorityQueue<>());
flights.get(ticket[0]).add(ticket[1]);
}
//栈
LinkedList<String> path = new LinkedList<>();
//起点为JFK
dfs("JFK", flights, path);
return path;
}
/**
*
* @param departure 出发站点
* @param flights 航班，航线
* @param path 已经整理的路径
*/
private static void dfs(String departure, Map<String, PriorityQueue<String>> flights, LinkedList<String> path) {
//获取当前出发站点的可行的航班列表
PriorityQueue<String> arrivals = flights.get(departure);
while (arrivals != null && !arrivals.isEmpty()) {
//遍历之后删除，剩余路径为尚未遍历的，避免再次被安排。
String next = arrivals.poll();
dfs(next, flights, path);
}
//
path.addFirst(departure);
}
}
八、递增的三元子序列（题号：334）
描述：给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
1）如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
2）使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明:
1）要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。
2）注意，i,j,k三个元素可以不是连续的、相邻的。
解题思路：此题本人第一次写的时候，搞错了一个概念，就是认为i,j,k是相邻的，所以设计的复杂度很低，每个元素只需要与其左、右相邻元素比较即可，不过这不符合本题的要求。既然递增的三元子序列，[min,medium,max]，我们只需要把遍历是遇到的min、medium记录下来，只要遇到一个比medium大的元素，即可认为条件成立。
public class TestMain {
public static void main(String[] args) {
int[] s1 = {1,2,3,4,5};
System.out.println(execute(s1));
int[] s2 = {5,4,3,2,1};
System.out.println(execute(s2));
int[] s3 = {5,6,1,3,2,7,4};
System.out.println(execute(s3));
}
/**
* 解答此题，需要明确两个个前提：
* 1）数组是无序的
* 2）所谓的"三元子序列"，这三个元素并非完全相邻，array[n - 1] < array[n] < array[n + 1]
* 如果没有第二个条件或者前提，很容易误解。
*
* 理解之后，就很简单了，我们设置两个临时数，最小值、中值，最小值 < 中值，在遍历时如果遇到值比中值大，就可以判定存在子序列。
* @param source
* @return
*/
private static boolean execute(int[] source) {
int min = Integer.MAX_VALUE;//三元子序列的最小值
int medium = Integer.MAX_VALUE;//三元子序列的中值
for (int i : source) {
//如果当前值比最小值小，则交换
if (i <= min) {
min = i;
} else if (i <= medium) {
//比中值小，则交换
medium = i;
} else {
//比中值大，可以认为存在三元子序列存在
return true;
}
}
return false;
}
}
九、打家劫舍II（题号：337）
描述：在上次*****，小*又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小*意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被**，房屋将自动报警。计算在不触动警报的情况下，小*一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
解题思路：我们很容易发现规律，小偷窃取时，不能窃取相邻两层（树深）的房子。我们采用广度遍历时，只需要分别计算奇数层、偶数层的数字之和，取最大值即可。此题之所以能这么解答，因为小偷必须从树的根节点开始。
public class TestMain {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode n1 = new TreeNode(4);
TreeNode n2 = new TreeNode(5);
TreeNode n3 = new TreeNode(1);
TreeNode n4 = new TreeNode(3);
TreeNode n5 = new TreeNode(1);
root.left = n1;
root.right = n2;
n1.left = n3;
n1.right = n4;
n2.right = n5;
long start = System.currentTimeMillis();
System.out.println(execute(root));
System.out.println(System.currentTimeMillis() - start);
}
/**
* 广度遍历，一次遍历即可，分别记录奇偶数层的累加和
* @param root
* @return
*/
private static int execute(TreeNode root) {
Queue<TreeNode> stack = new LinkedList<>();
stack.add(root);
//层数为偶数的和
int v1 = 0;
//层数为奇数的和
int v2 = 0;
int level = 0;
while (!stack.isEmpty()) {
int size = stack.size();
for (int i = 0;i < size;i++) {
TreeNode current = stack.poll();
if (current.left != null) {
stack.add(current.left);
}
if (current.right != null) {
stack.add(current.right);
}
if (level % 2 == 0) {
v1 += current.value;
} else {
v2 += current.value;
}
}
level++;
}
return Math.max(v1,v2);
}
public static class TreeNode {
private TreeNode left;
private TreeNode right;
private int value;
public TreeNode(int value) {
this.value = value;
}
}
}
十、整数拆分（题号：343）
描述：给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明：你可以假设n不小于2，且不大于58。（int不会溢出）
public class TestMain {
public static void main(String[] args) {
System.out.println(1 + "," + execute(1));
System.out.println(2 + "," + execute(2));
System.out.println(3 + "," + execute(3));
System.out.println(4 + "," + execute(4));
System.out.println(5 + "," + execute(5));
System.out.println(10 + "," + execute(10));
}
/**
* 这个题，找规律，一个整数，无论拆多少个乘法因子，只有增量因子才会扩大乘积有帮助。
* 1：1 * 0
* 2：1 * 1
* 3：1 * 2
* 4：2 * 2
* 5：2 * 3
* 6：3 * 3
* 7：2 * 2 * 3 （可能会拆出1，1 * 3 * 3,出1的话，就减少一个3，换成两个2）
* 8：2 * 3 * 3
* 9：3 * 3 * 3
* 10：2 * 2 * 3 * 3
*
* 规律可见：
* 1）如果整数为3个倍数，则乘法因子全是3，结果最大
* 2）其他的数字，保持两个原则：拆出尽量多的3、且不能拆出1；不能拆出1的原因是浪费一个数字且对结果没任何帮助。
* 为了避免拆出1，那么就是减少一个3，拆出两个2.（因为 1 * 3，小于2 * 2）
* 拆出2的数字，不需要过度关注，因为2也是增量因子
*
* 为什么不将其他因子作为增量
* 1）4：任何数乘4，等于 2 * 2
* 2）5：任何数乘5，小于 2 * 3，即乘以5，还不如把5拆成 (2,3)
* 3）6：任何数乘6，小于 3 * 3，即乘以6，还不如把6拆成（3,3）
* 4）7：乘以7，不如把7拆成（2,2,3）
* ...
* 最终，无论怎么拆，都是2、3这两个增量因子的事情。
* @param n
* @return
*/
private static int execute(int n) {
//最小因子，不用拆，直接计算，我们只看能拆出2、3的因子
if (n < 4) {
return n -1;
}
//如果是三的倍数
if (n % 3 == 0) {
return (int) Math.pow(3, n / 3);
} else if (n % 3 == 1) {
//3 * n + 1
// n - 4的原因是，4被拆成 2 * 2，余数为3的倍数
return 2 * 2 * (int) Math.pow(3, (n - 4) / 3);
} else {
//3 * n + 2,把2拆出来，余数为3的倍数
return 2 * (int) Math.pow(3, n / 3);
}
}
}
相关推荐
如何正确刷题？LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】
Backtracking回溯解题套路【LeetCode刷题套路教程18】
Heap堆解题套路【LeetCode刷题套路教程6】
一些java基础算法、leetcode刷题 Java学习资料
主要介绍了如何在Intellij中安装LeetCode刷题插件方便Java刷题,本文通过图文并茂的形式给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下
哈希表HashMap解题套路【LeetCode刷题套路教程7】
Stack堆栈解题套路【LeetCode刷题套路教程5】
这个是自己收藏的一个leetcode刷题记录，分享给需要的亲。非原创，自己也正在学习中。
DynamicProgramming2D解题套路【LeetCode刷题套路教程15】
Array题型_双指针Two_Pointers套路【LeetCode刷题套路教程2】
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
DynamicProgramming1D解题套路【LeetCode刷题套路教程14】
DynamicProgramming2D高级解题套路【LeetCode刷题套路教程17】
DynamicProgramming2D进阶解题套路【LeetCode刷题套路教程16】
Search,_Dynamic_Programming1【LeetCode刷题套路教程13】
Graph图BFS广度优先搜索套路【LeetCode刷题套路教程10】
Graph图DFS深度优先搜索题型套路【LeetCode刷题套路教程12】
树Tree深度优先搜索DFS解题套路【LeetCode刷题套路教程9】
树Tree题型广度优先搜索BFS套路【LeetCode刷题套路教程8】
Graph图Best-First_Search题型套路【LeetCode刷题套路教程11】