LeetCode刷题 day38
目录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]这里不做推导但是这种优化转移方程的求解思想值得学习

相关新闻

唐朔飞计算机组成原理核心难点解析:Cache、CPU与总线系统

唐朔飞计算机组成原理核心难点解析:Cache、CPU与总线系统

1. 项目概述:为什么我们需要一份“唐版”计组总结?如果你正在学习计算机组成原理,尤其是手头捧着唐朔飞老师那本经典的《计算机组成原理(第3版)》,那你大概率正经历着和我当年一样的“甜蜜烦恼”。这本书内…

2026/11/15 5:50:43 阅读更多 →
GetQzonehistory:QQ空间历史说说备份工具完整指南,把青春记忆轻松搬进本地

GetQzonehistory:QQ空间历史说说备份工具完整指南,把青春记忆轻松搬进本地

GetQzonehistory:QQ空间历史说说备份工具完整指南,把青春记忆轻松搬进本地 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 想把QQ空间的历史说说完整备份到本地&…

2026/11/14 23:30:48 阅读更多 →
探索银川市建设局网站如何助力城市腾飞与民生改善

探索银川市建设局网站如何助力城市腾飞与民生改善

在这座被黄沙与黄河共同雕琢的塞上明珠里,日子总是过得慢条斯理却又充满生机。作为一名在这个城市扎根多年的老银川人,我时常喜欢骑着那辆斑驳的自行车,沿着南熏大道缓缓骑行。清晨的空气中弥漫着羊杂碎汤的香气,傍晚的贺兰山轮廓在夕阳下显得格外温柔。这里的一切变化,都…

2026/11/17 5:00:30 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻