企业官网建设流程全解析

1.打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。
除了root之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的root。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

示例 1：
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2：
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：
树的节点数在[ 1 , 10 4 ] [1, 10^4][1,104]范围内
0 < = N o d e . v a l < = 10 4 0 <= Node.val <= 10^40<=Node.val<=104

思路
动态规划，用数组dp[2]来计算到当前节点为止，能盗取的最高金额，dp[0]表示包含当前节点，dp[1]表示不包含当前节点，则转移方程为：

// 包含当前节点时，必然不能包含子节点dp[0]=node.val+left.dp[1]+right.dp[1];//不包含当前节点时，可以包含子节点，也可以不包含子节点//这里必须要把不包含子节点考虑进去，这两个值没法判断谁大谁小，若不包含子节点大的话，那下一步计算父节点时，就有用dp[1]=Math.max(left.dp[0],left.dp[1])+Math.max(right.dp[0],right.dp[1]);

整个代码如下

classSolution{publicintrob(TreeNoderoot){int[]dp=robMoney(root);returnMath.max(dp[0],dp[1]);}//int[2] int[0]表示包含自己的最大金额，int[1]表示不包含自己的最大金额publicint[]robMoney(TreeNoderoot){if(root==null){returnnewint[]{0,0};}int[]left=robMoney(root.left);int[]right=robMoney(root.right);int[]all=newint[2];//all[0]表示包含自己all[0]=root.val+left[1]+right[1];//all[1]表示不包含自己all[1]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);returnall;}}

时间复杂度：O ( n ) O(n)O(n)
空间复杂度：O ( 1 ) O(1)O(1)

2.扁平化嵌套列表迭代器

给你一个嵌套的整数列表nestedList。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。
实现扁平迭代器类NestedIterator：
NestedIterator(List<NestedInteger> nestedList)用嵌套列表nestedList初始化迭代器。
int next()返回嵌套列表的下一个整数。
boolean hasNext()如果仍然存在待迭代的整数，返回true；否则，返回`false。
你的代码将会用下述伪代码检测：

initialize iteratorwithnestedListres=[]whileiterator.hasNext()append iterator.next()totheend of resreturnres

如果res与预期的扁平化列表匹配，那么你的代码将会被判为正确。

示例 1：=
输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：
输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

提示：
1 < = n e s t e d L i s t . l e n g t h < = 500 1 <= nestedList.length <= 5001<=nestedList.length<=500
嵌套列表中的整数值在范围[ − 10 6 , 10 6 ] [-10^6, 10^6][−106,106]内

思路
递归，使用队列，将NestedList中的所有整数放入队列中，然后从队列中取

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */publicclassNestedIteratorimplementsIterator<Integer>{Queue<Integer>queue;publicNestedIterator(List<NestedInteger>nestedList){queue=newLinkedList<>();flattern(nestedList);}privatevoidflattern(List<NestedInteger>nestedList){Iteratorit=nestedList.iterator();while(it.hasNext()){NestedIntegerobj=(NestedInteger)it.next();if(obj.isInteger()){queue.offer(obj.getInteger());}else{flattern(obj.getList());}}}@OverridepublicIntegernext(){returnqueue.poll();}@OverridepublicbooleanhasNext(){return!queue.isEmpty();}}

时间复杂度：flattern时间复杂度O ( n ) O(n)O(n)，next和hasNext时间复杂度为O(1)
空间复杂度：O ( n ) O(n)O(n)队列里保存了所有的数据

3.整数拆分

给定一个正整数n，将其拆分为k个正整数的和（k >= 2），并使这些整数的乘积最大化。
返回你可以获得的最大乘积 。

示例 1：
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2：
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示：
2 <= n <= 58

思路
动态规划，dp[i]保存到和为i时的最大乘积，则转移方程为

//1<=j<i;dp[i]=Math.max(dp[j]*(i-j),(i-j)*j);

classSolution{publicintintegerBreak(intn){int[]dp=newint[n+1];//这里规定dp[1]=1dp[1]=1;for(inti=2;i<=n;i++){for(intj=i-1;j>=1;j--){inta=i-j;dp[i]=Math.max(dp[i],a*j);dp[i]=Math.max(dp[i],a*dp[j]);}}returndp[n];}}

时间复杂度：O ( n 2 ) O(n^2)O(n2)
空间复杂度：O ( n ) O(n)O(n)
注：官方给出了O ( n ) O(n)O(n)的解法，在动态规划的基础上，利用数学思想对转移方程做了优化，保证在O ( 1 ) O(1)O(1)的时间内得到d p [ i ] dp[i]dp[i]，这里不做推导，但是这种优化转移方程的求解思想值得学习