目录1.打家劫舍 III2.扁平化嵌套列表迭代器3.整数拆分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^40Node.val104思路动态规划用数组dp[2]来计算到当前节点为止能盗取的最高金额dp[0]表示包含当前节点dp[1]表示不包含当前节点则转移方程为// 包含当前节点时必然不能包含子节点dp[0]node.valleft.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[]dprobMoney(root);returnMath.max(dp[0],dp[1]);}//int[2] int[0]表示包含自己的最大金额int[1]表示不包含自己的最大金额publicint[]robMoney(TreeNoderoot){if(rootnull){returnnewint[]{0,0};}int[]leftrobMoney(root.left);int[]rightrobMoney(root.right);int[]allnewint[2];//all[0]表示包含自己all[0]root.valleft[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。每个元素要么是一个整数要么是一个列表该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化使之能够遍历这个列表中的所有整数。实现扁平迭代器类NestedIteratorNestedIterator(ListNestedInteger 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 返回 falsenext 返回的元素的顺序应该是: [1,1,2,1,1]。示例 2输入nestedList [1,[4,[6]]]输出[1,4,6]解释通过重复调用 next 直到 hasNext 返回 falsenext 返回的元素的顺序应该是: [1,4,6]。提示1 n e s t e d L i s t . l e n g t h 500 1 nestedList.length 5001nestedList.length500嵌套列表中的整数值在范围[ − 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 ListNestedInteger getList(); * } */publicclassNestedIteratorimplementsIteratorInteger{QueueIntegerqueue;publicNestedIterator(ListNestedIntegernestedList){queuenewLinkedList();flattern(nestedList);}privatevoidflattern(ListNestedIntegernestedList){IteratoritnestedList.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时的最大乘积则转移方程为//1ji;dp[i]Math.max(dp[j]*(i-j),(i-j)*j);classSolution{publicintintegerBreak(intn){int[]dpnewint[n1];//这里规定dp[1]1dp[1]1;for(inti2;in;i){for(intji-1;j1;j--){intai-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]这里不做推导但是这种优化转移方程的求解思想值得学习