在 Chrome 上有个很好用的插件 FeHelper,应该是每个开发人员都在使用的,功能很全面。想着能不能搞个桌面版的,这样多屏环境下可以不用在众多 tab 页中找功能了。

桌面版实现,界面比较丑陋,不过用起来方便就行。这样可以在多屏环境下一个屏用来开啊,另一个屏可以观察辅助信息和使用小工具。

了解到 electron 是一个开源跨平台框架,可以使用 nodejs 做后端和 chromium 做前端开发。像 atom 和 vs code 使用这个框架开发的。觉得还是和方便的,主要是跨平台。而这个插件也是基于 nodejs 开发的,应该可以迁移过来。然后按照官方文档开发,通过 iframe load 不同页面。

项目地址:https://github.com/noogel/xyzToolbox

Mac 安装包下载地址:https://pan.baidu.com/s/1SYjVX2Dhz6TTbaif1Bk8RA 密码:64oo

拉取项目和子模块

1
2
3
git clone https://xxx.git
git submodule init
git submodule update

打包命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
环境安装
npm install

# Linux打包成AppImage文件
# 在Linux环境上执行
node_modules/.bin/electron-builder -l AppImage

# Windows打包成exe安装文件
# 在Windows环境下执行
node_modules/.bin/electron-builder -w nsis
node_modules/.bin/electron-builder -w --ia32 nsis

# 如果在非Windows上打包win程序,也可以借助docker 如下
# docker run --rm -it -v ${PWD}:/project electronuserland/builder:wine sh -c "node_modules/.bin/electron-builder -w nsis"

# Mac打包成dmg文件
# 在Mac环境下执行
node_modules/.bin/electron-builder -m dmg

打包参考链接

https://qii404.me/2019/07/10/electron.html

设计原则

如果把设计模式理解为优秀软件系统模块设计的最小抽象,那么设计原则就是这些抽象的指导思想。目的是设计一个易于扩展和维护的系统。设计模式的六大原则有:

  • Single Responsibility Principle:单一职责原则
  • Open Closed Principle:开闭原则
  • Liskov Substitution Principle:里氏替换原则
  • Law of Demeter:迪米特法则
  • Interface Segregation Principle:接口隔离原则
  • Dependence Inversion Principle:依赖倒置原则

单一职责原则

应该有且只有一个原因引起类的变化,一个类只负责一个职责。一个功能应该要划分成多少个职责类去实现,并没有明显的限定。举例说明对于用户管理,用户信息管理和用户行为管理可以做初步拆分,用户信息管理又可以拆分成普通信息维护和敏感信息的维护。又比如用户发生一笔支付行为可以初步拆分为交易信息管理和支付信息管理。职责划分的粗细的影响因素有对于业务理解程度、项目开发阶段等,过粗会造成一个处理类包含太多职责,过细又会增加开发维护成本。单一职责是“高内聚低耦合”设计的一种实现形式,单一职责即为同一职责内部的内聚性,降低不同职责之间的耦合性。

里氏替换原则

描述继承关系,子类全部实现或继承父类方法,子类可以扩展父类方法实现,将子类替换父类不会产生异常。在重构角度来说如果多个子类拥有相同的行为,可以将相同行为提取到父类实现,子类调用扩展父类实现。在开发上基于“组合大于继承”的原则,通过定义实现接口的形成被其它类调用。违反这个原则不一定会产生严重后果,但是会对后面的开发维护造成困难。

开闭原则

描述的是对于需求产生变化后,软件实体部分应该进行扩展开发,避免修改。通过扩展实体行为来响应需求变化,而不是通过修改现有软件代码。

迪米特法则

描述的是一个对象应该进行减少对于其它对象的理解。通过封装我们可以屏蔽类内部逻辑,只提供足够用且少量的方法来给外部使用,降低对象之间的耦合性。当一个接口或者一个对象被公开,意味着后面我们进行开发和维护的时候很难再将这个对象收回,重构内部逻辑时也会更加困难。

接口隔离原则

描述的是建立单一的接口,不要建立庞大臃肿的接口,尽量细化接口,接口中的方法尽量行为统一,避免臃肿。对于支付接口来说,定义类通用支付方法,对于获取分期支付信息也属于支付行为的一个环节,但不是所有实体类必须要实现的,可以拆分出来。

依赖倒置原则

描述的是实现类之间不能直接发生依赖关系,其依赖关系是通过接口或者抽象类产生,即面向接口编程。实现类依赖接口或者抽象类,而接口或者抽象类不依赖实现类。

设计模式

https://design-patterns.readthedocs.io/zh_CN/latest/index.html

一些小的点

  1. 坚持阅读英文技术资料,并至少翻译12篇技术文章。x
  2. 戒掉熬夜的坏习惯,习惯性去健身,保持精力的充沛。60%
  3. 刻意提高专注力,并坚持系统性的做技术储备。80%
  4. 常出去走走,看看外面的世界,准备至少两次的远途旅行。100%
  5. 找到一个互相合适的伴侣。100%
  6. 趁年轻努力挣钱,但是不要透支身体。50%
  7. 好好学说话,做一个有趣的人。60%

主要方向

  1. 英语学习,坚持阅读英文技术资料,至少翻译12篇技术文章,基本的口语表达。x
  2. 沟通能力,说话前多思考,减少小动作的出现,改变不好的下意识动作和反应。50%
  3. 正确锻炼,学会并养成跑步习惯,无氧健身增加身体健壮。90%

发音练习

《张浩翔 魅力声音必修课》
预计学习时间 2 天,整理笔记,刻意练习。注意学习的几个阶段。

做到了哪些

  1. 考了救护员证
  2. 去了天津、昆明、大理、丹东
  3. 跑了马拉松
  4. 去山顶露营

第一个半马

云南之旅

丹东之旅

救护员证

  • 六本本职技术书籍/专题
    • effective java done 01.29
    • Java 并发编程实战 done 02.14
    • 深入理解 Java 虚拟机 part 04.01
    • Java 性能优化 21 讲 done 12.01
  • 六本技术扩展书籍/专题
    • 图解密码技术 第三版 done 10.08
    • Linux 内核设计与实现(原书第三版)
    • 现代编译原理
    • 数据密集型应用系统设计
    • MySQL 实战 45 讲 part 08.26
    • Wireshark 数据包分析实战(第 3 版) done 2020.12.13
    • 实现领域驱动设计 part
  • 六本人文社科书籍
    • 精进 done 02.11
    • 我的改变:个人现代化 40 年 done 09.27
    • 高效 PDCA 工作术 done 09.16
    • 薄世宁医学通识讲义 done 10.20
    • 这里是中国 done 10.05
    • 活着 余华 done 12.10
    • 论中国 基辛格 done
    • 美国陷阱 done
  • 整理输出两篇高质量博客文章

丹东是中国的一个边境小城市,在东三省的辽宁,与朝鲜隔鸭绿江相望。丹东春秋去会比较好,还有点景色可以看看,冬天的话来泡温泉吧,还可以顺便来一趟朝鲜游,带着护照来就好了。可惜的是因为一些原因无法泡温泉和去趟朝鲜。所以只是趁着年末逃离下北京,换个环境放松一下,其它的不重要了。

丹东是个有山有水有美食的地方,来这边可以沿着鸭绿江散步,好奇的望望对面神秘的社会主义同僚。去趟鸭绿江美术馆、抗美援朝纪念馆之类的地方看看当地的人文。鸭绿江断桥是一定要去的,走上去一点点感受下当年的气息和脚下的滚滚江水,一座见证历史的铁桥。丹东的🍓很出名,冬天来了可以尝尝,味道还是很甜的。还有当地著名的全州拌饭馆,超级好吃绝对不是吹的,还有有名参鸡汤,夜里的烧烤。。。想想又饿了。

这里的夜景也还不错,丹东这个城市挺小的,发展还不错,赶上季节好可以来这里吃海鲜~

第一个半马…真的没啥挑战性,哈哈哈哈哈。

事情起源于表姐在群里问要不要去参加马拉松,她那有名额,然后就兴冲冲的报名了,报了个半马,然后开始了为期几个月的夜跑锻炼任务,从最初的慢悠悠的每天三公里,到逐步拔高的每次五公里,然后开始选鞋完善装备,提高到了十公里。因为家里有事中途中断了一些日子,之后就三天打鱼两天晒网的锻炼着,直到马拉松开始的那天。

周六早起动身,从北京出发到白洋淀站下车。迎着末夏的烈日,面对明天的半马,还是很兴奋的。都说出问题的都是跑半马的,因为半马大多是新手,不懂得如何把握自己身体和跑步强度,所以还是有点担心,就抱着玩玩看的心态去跑的。

半马路线图,从容城雄安市民服务中心出发一直跑到安新,全马则是跑到雄县。

第一个半马还算是比较轻松的跑过来了吧,期间粗心大意的没有把盐丸当回事,结果起跑就不力,心跳一直过速,直接影响了发挥,边跑变琢磨是怎么回事,后来觉得出汗多了,便找周围的人要了两粒盐丸,然后感觉心跳就慢慢的降到正常水平了。目标不高,完赛就好~,顺便拿起奖牌嘚瑟了一把。因为比赛在周日,担心第二天无法上班,其实多虑了,跑后做好充分的拉伸,第二天依然照常去上班了,腿也没有预期的酸痛,只是身体进行了一周左右的慢慢康复,身体的磨损在逐渐自我修复。

后面的时间可能不会再继续练跑步了,小区周围没有公园,只能在大街上跑,有比较多的尾气,感觉对身体不太好,然后买了辆山地准备以后骑行山间了。买后的一个周末独自骑行去了香山,前后 30 公里左右,感觉还不错,以后准备依赖这个了~

背景介绍

近一年都在做语言栈的转型,也注意到周围很多公司都在做相似的事情,大概的路径是 Python -> Go -> Java,转型的起因也是有诸多的因素,像 Python 这种开发速度快,执行相对慢的语言更适合中小型项目,加上国内语言生态不够成熟,项目做大了会发现大家一刀切的转到其它语言上,当然这些说的是在做 web 后端方向上,Python 在数据分析和人工智能方向上还是势头很猛的。Go 可能还是因为它能承载的并发更高,性能更好而逐渐流行起来。在并发模型上 Java 原生 API 使用上确实做得不好驾驭,Go 则要相对好用很多。还有在某些垂直领域上,Java 的生态已经很成熟,其它语言栈上则需要自己造轮子,相应对于开发人员的水平要求就会低很多了。

在当前互联网领域,后端研发做 web 主要谈的还是通过抽象和建模来提高项目的可迭代性与可维护性,另一方面谈的是工程实现上的优化和性能上的优化。在这些后面依赖的则是中台来保证的基础服务综合稳定性。

在语言栈转型中也踩过一些坑,遇到过一些小问题,当然这些也得益于一个相对靠谱的方案来保证迁移的安全,基于这些经验总结一下,在以后的迁移中使问题可预见和避免采坑。

转型流程

首先要明确转型的三个开发流程 MRO (Migration, Reconstruction, Optimization)

  • 迁移 就是把原语言代码照着抄一遍到新语言项目上,按照新语言的工程实现风格来做就可以。
  • 重构 的目的是来提高项目代码的可维护性和可迭代性,让代码更加优雅和好读懂,可以放到迁移完成来做。
  • 优化 则可以是在模块依赖、调用关系、接口字段等方面调整来降低项目的复杂性和提高合理性。

然后看我们人力和时间是否充足,我想大部分情况下是不充足的,按照最短时间交付的原则,我们应该只做迁移流程,也就是说先对原有代码进行语言上的迁移,这样我们可以快速实现交付。在人力充沛的情况下可以配备两个小组,一个维护现有系统,一个主力开发新系统,或者说锁定需求全力开发新系统。在对快速交付更看中的行业里前一个方案更合适一些。

交付流程

在交付过程中的验证流程 单测验证 -> 测试环境功能验证 -> QA生产回测 -> 灰度验证 -> 完全上线
只有功能和单测代码都迁移完才能算代码部分完成,需要优先保证单测行数覆盖率再去保证分支覆盖率,测试环境的功能验证需要覆盖所有 case 来保证大部分问题都被发现,然后进入小范围的灰度验证,之后逐步提高灰度比率直至完全上线。如果是纯读接口则可以直接进行异步校验,就是请求两遍,然后对比差异来不断的发现和修复 bug,直至问题收敛完全解决。
如果明确只做迁移,那么期间如果有发现旧逻辑的 bug 也不要管,这样才好去对比验证,验证通过上线后再去修复。只有通过明确目的和流程并且遵循这个流程做,才能更快的去交付。

验证方案

针对新代码的验证方案分为别为读写接口做不同的验证方案:

  • 读接口:异步请求到新接口做接口响应值校验,打印出差异数据,然后不断修正逻辑。这样可以避免在线上灰度造成数据的不一致。
  • 写接口:测试用例覆盖,然后测试环境验证,灰度回测,灰度验证,修复问题,继续灰度验证。

平稳交付

在整个交付的过程中,转型前后对 SLA 要提供一致的保证,可以看看下面的几个衡量标准:

服务可用性级别 服务正常运行时间 年宕机时间 日宕机时间
1 90% 36.5day 2.4hour
2 99% 3.65day 14min
3 99.9% 8.76hour 86sec
4 99.99% 52.6min 8.6sec
5 99.999% 5.26min 0.86sec
6 99.9999% 31.5sec 8.6msec

在线 MD 表格生成

一般 3 个 9 的可用性全年宕机时间约为 8.76 小时,针对不同系统不同用户规模对于系统可用性的要求不一样,边缘业务的要求可能会低一些,但是对于核心支付链路场景 TPS 可能不高,但是必须要求保证高可用级别。如何保证或者提升服务的 SLA 是我们接下来要探讨的目标,一般有下面两个影响因素:

  • MTBF (Mean Time Between Failures) 系统服务平均故障时间间隔
  • MTTR (Mean Time To Recover) 系统服务平均故障恢复时长

也就是说我们系统要尽可能的降低故障频率以及出现故障时能尽快的恢复。基于这两点我们在做系统平稳过渡时,要充分测试所有 case ,并且进行内部灰度方案和异步重试对比,发现异常立即回滚查找结局问题后再重新灰度。这里需要做到一键开关,数据可监控和追溯。

持续监控,感知系统稳定性的第一步就是监控,通过监控和系统日志来排查问题和及时响应处理。监控有两个层面,一个是基础设施提供的机器监控以及接口级别的响应稳定性监控,另一个是业务数据层面的多维度监控。系统日志按照等级大致分为 INFO 日志以及 ERROR 日志。

快速交付

关于快速交付,可以了解 下敏捷开发,及早和持续不断的交付有价值的软件。关于 Scrum 开发的介绍可以看: 什么是敏捷

现状及未来

基于公司现状考虑 nginx 不支持长时间和自定义灰度,所以 http 接口层没做改动,只是在内部逻辑上通过 rpc 服务转到新的系统中。基于以上要点可以做到功能的快速交付。截止此文撰写时间,语言栈转型已经将系统核心接口逻辑 100% 迁移到新的系统上,对于日常系统需求已经可以做到在新系统开发和接入了。后面要做的有以下几点:

  1. 将系统外围逻辑迁移到新系统;
  2. 不断监控降噪,细化监控粒度,继续提高服务的稳定性;
  3. 当前对于Python的花式“魔法” 硬翻译还需要不断重构和优化。
  4. 完善监控大盘,通过数据驱动来运营优化我们的流程;
  5. 项目复盘总结以及业务普及宣讲,提升人员对于业务细节的认知。

转型痛点

迁移后再做重构和优化过程。在迁移过程中有一个痛点是新需求过来了,要么锁定需求只做迁移,要么写两遍。基于人力情况可以选择一个小组同时写新旧系统或者一个小组维护新的一个小组维护旧的。
在转型过程中新需求过来有时要写两边,或者要把旧系统流量打到新系统接口上,常常在排查问题时遇到流量忘记转移的情况,所以在迁移过程要尽可能的快速交付上线。

反思

  1. 对于每一位工程师来说语言栈的转型既是挑战也是机遇,只有保持开放学习心态,及时调整和提升才能更好应对,同时增强自身软素质。
  2. 当前互联网环境下分布式是必经之地,而系统绝非 100% 可靠,每一个环节可能的异常在上线后必定遇到,所以针对不同场景我们要在 AP 与 CP 之间做出选择。
  3. 对于支付交易核心链路,一条柱子肯定是不稳的,双链路也未必可靠,但至少更稳一些。曾经遇到过相隔几公里的两条光纤被施工队挖断的情况,双机房访问直接 gg 了,但总归是少见的。
  4. 提系统可用性要避免出问题,除了问题要快快快速响应恢复,有问题先回滚。

多图预警!!!
多图预警!!!
多图预警!!!
多图预警!!!

云南是一个离家好几千公里的地方。最初要去的想法是在一次同学聚会上大家商量的,结果到了十月一只有们两个人过来玩了,倒也好,制定行程和订票比较省事。于是,参加完同学婚礼就开始了我们的云南之旅,从国际庄直飞昆明。


去之前做攻略的时候并没有觉得昆明有什么好玩的地方,所以只是做了一天半的行程,要说昆明吃的地方也就是鲜花饼和米线了。对比过几家不同的,一个是花多纷的鲜花饼,另一个是建新园的米线不错。


玩的地方是真没觉得什么,然后就是去了云南省博物馆看了看,一般我到一个城市会先去了解下这个城市的历史和人文,博物馆建的是很恢弘有气势。看了看滇人、昆明人和汉人之间的历史渊源。



明明天还很早,博物馆就早早往外赶人了,算是逛了一半吧,然后看旁边有个官渡古镇,便抱着试试看的心态去逛了逛,果然跟预料的一样,纯粹的商业化街道让人不会再来第二次,就像北方的太行水镇、古北水镇,北京的王府井小吃街和天津的古文化街。。。

也许第一天太兴奋了吧,晚上不想回去,这边比北京在地理时区上差一个多小时。然后便跑去了云大看妹子,可惜到了都晚上了(😶),有大学地方就有小吃街,果然不出所料。

在昆明的第二天,睡了个懒觉,下午去的海埂公园看的滇池。不得不说,景色是真的不错,空气也很好,来到这里就是一场洗肺之旅。

海埂公园是从南到北的,可以遥望西山,走着走着不知不觉就想着去西山看看,站在山顶来俯瞰滇池和昆明应该很不错。就这样被什么驱使着,拿着地图导航,顺着一个不知名的小路就上⛰了。还真是曲径通幽处,好多次都给走错路了,因为真的挺偏。


山中刚下过雨路有点滑,望着遮住天空的树也不知道累,总归心情是很好的,空气也很好,想到这里总对比起北京令人头疼的雾霾天,天高皇帝远,有点不想回去了,在这种地方真的挺宜居的。

想看到的总归是要看到的,但不是在山顶,而是在爬山的某条路途中。

最后,爬到山顶是不能了,来的有点晚,得趁着天黑前下山回去,结果顺着某德导航走了一条崎岖山路,纯人工走出来的土路,崎岖泥泞,向前看不见头,向后难以攀爬。。。有点绝望了,真不知道这种路怎么会被收录并作为导航路线。。。大概是下图这样子的,真的是手脚并用出来的,最口看到村口灯光的时候特别的激动,是看到希望的激动😂。



已经很晚了,到了有人的地方赶紧打车回去市里找了个吃饭的地方。傣族风味,看评价还是挺地道的,发现和其它吃过的才来说,做法上好像没有太特别的地方,只是这里的都加了好多特别香味的香草。

要去的地方总归要去的,一个号称风花雪月的地方——大理,但是我要说与我和我的小伙伴无关。虽然我没有被过多的安利大理的美,但也还是抱着去放松的心态走一趟的。

后面几天的行程比较集中,便商量租了辆车,两个新手,开启了试车模式,尤其我这个拿本六年没摸过车的纯新手,还是比较紧张和激动的。。。我们开上了苍山,到过洱海,去过古镇((⊙o⊙)…好像哪里不对),先练了半天车。



开过了洱海边的乡间小路、白族人的原始村镇,看到了一片金黄的稻田,如此没见过世面的我自己都很惊讶。。。






站在洱海边遥望苍山,哪些传说的爱情故事也只是传说,我所切实感受到的是景色真的很棒,随手一拍都是能做壁纸的那种。我想和对象一起来的话,住着海景房也是会很浪漫的吧???






待在这样的环境里我想一辈子也不会厌倦吧。晚上开去大理古城吃饭,石井私房菜,一个小巷子里,菜品也不错。邻桌的也是从北京过来旅游的。

也许大理的爱情偶遇会在古城中一个故事里发生,在不经意之间吧。

开车就要到平时不能到的地方去看看,经过重重山路不经意间来到了赵灵儿的故乡。查了查发现这里是南诏文化,巍山自治县,这里也有一个古城,慢悠悠的古城里有着原始的居民,又没有太过浓厚的商业化,保护的还相对比较好。



来大理的第三天,想着去丽江看看,最后因为时间距离问题没去,二刷再说吧。那么之前在洱海西线走了一遍,今天就在东线的环海公路走一遍吧。来到了一个叫双廊古镇的浓浓商业化的地方,有着网红打卡地天空之境,随处可见的海景房,这些都不重要,重要的是回去路上沿海公路,听着小歌吹着海风,心情超级好。当然还要感谢一下驾驶员智哥~



出来玩还是不要太久的,容易疲惫,好时光总是很快的,回家啦~



走啦~


参考攻略

云南游玩交通参考

大理景点分布

行程规划

预算

人生只有贪心,没有动态规划。

数据结构

  • 数组
  • 栈,先进后出
  • 队列,先进先出
    • 双端队列,双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行。
    • 环形队列,环形队列是一种特殊的队列结构,保证了元素也是先进先出的,但与一般队列的区别是,他们是环形的,即队列头部的上个元素是队列尾部,通常是容纳元素数固定的一个闭环。
  • 堆,一种特别的树状数据结构。堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
  • 链表
    • 单向链表。
    • 双向链表。
    • 跳表,一种带多级索引的链表。
  • 散列表,是根据键而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。
    • 二叉树,二叉树是一个连通的无环图,并且每一个顶点的度不大于3。
    • 红黑树,是一种自平衡二叉查找树。
    • 字典树(Trie)
  • 图,图(Graph)是由顶点的有穷非空集合和顶点之间的边的集合组成。
  • 布隆过滤器,一个概率型数据结构,可以用来判断一个元素是否在一个集合中。判断某个元素在,可能会被误判;判断某个元素不在,那么一定不在。

算法思想

分治法

分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

例子:快排、归并排序、MapReduce

贪心算法

贪心算法就是在每一步的选择中都按照当前最优的选择,从而希望最终结果得到最优解。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

例子:最小生成树、哈夫曼编码

动态规划(Dynamic Programming)

动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。
若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

递归+记忆=递推

适用情况:

  1. 具有最优子结构性质。
  2. 无后效性,子问题确定后不会再改变。
  3. 子问题重叠的性质。

例子:背包问题
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://www.zhihu.com/question/23995189/answer/613096905

回溯法(backtracking)

回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  1. 找到一个可能存在的正确的答案
  2. 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。

例子:八皇后问题

https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://www.cnblogs.com/zuzZ/p/8178950.html

分支界限法

与贪婪算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。

概率算法

例子:
数值随机化算法
蒙特卡罗(Monte Carlo)算法
拉斯维加斯(Las Vegas)算法
舍伍德(Sherwood)算法

https://zhuanlan.zhihu.com/p/42619498

练习题

15. 三数之和

题目

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路

初读这道题时忽略了一个点,就是在检查时,如果有两个重复的数字可以都用上组成一个三元组集合,但是在返回结果的时候不能第一个数字参与组成三元组后第二个相同数字继续组成三元组。

有三种思路,先进性排序处理,然后再进行处理。第一种就是做三层枚举;第二种就是两层枚举,在进行 set O(1) 查找;第三种是一层枚举,然后从剩余列表中的左右两边进行查找,满足三元组的添加记录。

下面是主要介绍第三种思路的细节

  1. 排序处理
  2. 从第 0 位置开始遍历
    1. 分别取剩余数组的首尾值进行求和
    2. 如果大于零则向前移动尾部游标
    3. 如果小于零则向后移动头部游标
    4. 如果等于零则添加记录
      1. 添加记录后对首尾游标向中间移动一格
    5. 如果首尾游标没有相交则继续 2.1 步骤处理
  3. 进行下一位置的遍历,直到数组尾部
  4. 返回结果

整个流程思路基本是这样子的,然后我们对于边界情况的处理单独进行描述

  1. 如果当前遍历位置值大于 0 则直接返回结果
  2. 对于我在 ① 中描述的情况,需要在 2.1 之前进行与判断,当前位置与上一位置值相同则跳过,进行排重处理
  3. 同样的情况处理在 4.1 之后也要进行首尾游标移动方向相邻值的排重处理

解题思维

  1. 首先需要做到的是充分理解题意,至少要做到能肉眼推导正确结果。
  2. 解决方案一般都会有多种,合理选择最优方案进行骨架设计 ②,充分考虑时间和空间复杂度。
  3. 然后解决边界条件 ③,优化代码可读性。
  4. 充分进行测试验证算法的正确性。

解题代码

最后放一下解题代码,也是参考别人的方案实现的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;

public class ThreeSum {

public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resp = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
int l = i + 1;
int r = nums.length - 1;
if (i > 0 && nums[i-1] == nums[i]) continue;
while (l < r){
int sum = nums[i] + nums[l] + nums[r];
if ( sum> 0) r--;
else if (sum < 0) l++;
else if (sum == 0){
resp.add(Arrays.asList(nums[i], nums[l] , nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++;
r--;
}
}
}
return resp;
}
}


22. 括号生成

题目

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

1
2
3
4
5
6
7
8
9
10
11
12
[---
title: 51. N皇后
date: 2019-08-20
tags: [算法, leetcode]
id: 1
---
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路

根据递归做暴力处理,同时进行剪枝操作。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
public static void main(String[] args) {
GenerateParenthesis obj = new GenerateParenthesis();
List<String> stringList = obj.generateParenthesis(3);
System.out.println(stringList);
}

public List<String> generateParenthesis(int n) {
List<String> collect = new ArrayList<>();
gen(collect, "", n, n);
return collect;
}

public void gen(List<String> collect, String cur, int left, int right) {
if (left == 0 && right == 0) {
collect.add(cur);
return;
}
if (left > 0) {
gen(collect, cur + "(", left - 1, right);
}
if (right > 0 && right > left) {
gen(collect, cur + ")", left, right - 1);
}
}
}


49、242. 字母异位词

第一题:

242. 有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false

说明:
你可以假设字符串只包含小写字母。

解答第一个思路是使用 HashMap 进行字频统计再对比,第二个思路是字符串排序后进行比较。

第二题:

49. 字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

练习输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.*;

public class Anagram {
public static void main(String[] args) {
System.out.println(isAnagram("anagram", "nagaram"));
System.out.println(isAnagram2("anagram", "nagaram"));
groupAnagrams(new String[]{"eat", "ate", "aaa"});
}

public static boolean isAnagram(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> left = new HashMap<>();
Map<Character, Integer> right = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
left.put(s.charAt(i), left.getOrDefault(s.charAt(i), 0) + 1);
}
for (int j = 0; j < t.length(); j++) {
right.put(t.charAt(j), right.getOrDefault(t.charAt(j), 0) + 1);
}
for (Map.Entry<Character, Integer> c : left.entrySet()) {
if (!c.getValue().equals(right.getOrDefault(c.getKey(), 0))) {
return false;
}
}

return true;
}

public static boolean isAnagram2(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
char[] left = s.toCharArray();
char[] right = t.toCharArray();
Arrays.sort(left);
Arrays.sort(right);
for (int i = 0; i < left.length; i++) {
if (left[i] != right[i]) {
return false;
}
}
return true;
}

public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> res = new HashMap<>();
for (String sr : strs) {
char[] chars = sr.toCharArray();
Arrays.sort(chars);
String sortedSr = new String(chars);
if (!res.containsKey(sortedSr)) {
res.put(sortedSr, new ArrayList<>());
}
List<String> mapVal = res.get(sortedSr);
mapVal.add(sr);
}
List<List<String>> rep = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : res.entrySet()) {
rep.add(entry.getValue());
}
return rep;
}
}


51. N皇后

题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolveNQueens {
public static void main(String[] args) {
SolveNQueens queens = new SolveNQueens();
System.out.println(queens.solveNQueens(5));
}

public List<List<String>> solveNQueens(int n) {
List<List<String>> resp = new ArrayList<>();
Set<Integer> cols = new HashSet<>();
Set<Integer> pie = new HashSet<>();
Set<Integer> na = new HashSet<>();
dfs(n, 0, new ArrayList<>(), resp, cols, pie, na);
return resp;
}

public void dfs(int max, int row, List<String> curState, List<List<String>> resp,
Set<Integer> cols, Set<Integer> pie, Set<Integer> na) {
// 终结条件
if (row >= max) {
if (curState.size() == max) {
resp.add(curState);
}
return;
}
// 循环列
for (int col = 0; col < max; col++) {
if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col)) {
continue;
}
cols.add(col);
pie.add(row + col);
na.add(row - col);
curState.add(trans(col, max));
int size = curState.size();
List<String> newState = (max - row == 1) ? new ArrayList<String>() {{
addAll(curState);
}} : curState;
// 递归层
dfs(max, row + 1, newState, resp, cols, pie, na);
cols.remove(col);
pie.remove(row + col);
na.remove(row - col);
curState.remove(size - 1);
}
}

public String trans(int point, int max) {
char[] chars = new char[max];
for (int i = 0; i < max; i++) {
chars[i] = i == point ? 'Q' : '.';
}
return String.valueOf(chars);
}
}


69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
  由于返回类型是整数,小数部分将被舍去。

思路

二分查找比较

需要注意的地方有两个

  1. 注意开始边界问题
  2. 注意类型长度越界

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class MySqrt {
public static void main(String[] args) {
MySqrt mySqrt = new MySqrt();
System.out.println(mySqrt.mySqrt(2147395599));

}

// 边界问题
// 1. 0\1边界
// 类型长度越界
public int mySqrt(int x) {
if (x == 0) return 0;
if (x == 1) return 1;
return mySqrt(x, 0, x);
}

public int mySqrt(long x, long left, long right) {
long cur = (right - left) / 2 + left;
long cur2 = cur * cur;
if (cur2 == x) {
return (int) cur;
} else if (right - left == 1) {
return (int) left;
}

if (cur2 < x) {
left = cur;
} else if (cur2 > x) {
right = cur;
} else {
return (int) cur;
}
return mySqrt(x, left, right);
}
}

扩展

牛顿迭代法


98. 验证二叉搜索树

题目

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:

1
2
3
  2
/ \
1 3

输出: true
示例 2:

输入:

1
2
3
4
5
  5
/ \
1 4
  / \
  3 6

输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
  根节点的值为 5 ,但是其右子节点值为 4 。

思路

首先拿到这个题看起来思路比较简单,实现起来还有有点困难,而且在思考过程中踩过一个坑,又爬上来的。哎,看题还是要全面点。

  1. 首先想到就是中序遍历了,放到一个列表中,然后比较大小即可。
  2. 或者是做一个递归操作,判断当前节点是否在一个范围即可。

思路是这么两个思路,代码实现起来为了执行效率做了短路处理,就是边遍历边检查,遇到错误就一路返回不再进行后面处理,当然这是思路理顺后的优化。

中序遍历没坑,直接写就行了,有坑的是第二种操作,刚开始觉得只要比较当前节点的父节点和两个子节点就好了,就像下面画的,已 C 点为当前节点进行处理,实际是一个错误的思路,并且情况也分析的不对。

意识到问题后就重新分析,把当前节点作为最底端的节点,我们去比较的都是当前节点和父辈及以上的节点的大小,也就是拆出来四种情况。

其中 表示当前节点,和其它点的相对位置表示左右子节点关系,min -> max 指向当前节点值必须在此区间中才可以,+∞-∞ 为单点情况的边界表示。最后拆分出这四种子情况,只要任一节点符合这四种情况之一即当前节点满足,当所有节点均满足则二叉搜索🌲有效,事实根据这个思路写出的代码验证是可行的。比较开心的是重新思考后的思路写出来的代码一次通过✌️。

代码

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return forEachNode(root, new ArrayList<>());
}

public boolean forEachNode(TreeNode node, List<Integer> val){
if (null == node) {
return true;
}
if (!forEachNode(node.left, val)){
return false;
}
if (!validOrAdd(val, node)){
return false;
}
if (!forEachNode(node.right, val)){
return false;
}
return true;
}
public boolean validOrAdd(List<Integer> val, TreeNode node){
if(val.size() > 0 && val.get(val.size() - 1) >= node.val){
return false;
}else{
return val.add(node.val);
}
}
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return subValidBSTLeft(root, null, null);
}

public boolean subValidBSTLeft(TreeNode node, Integer min, Integer max) {
if (null == node){
return true;
}
if (null == min && null == max){
}else if (null == min && null !=max && node.val < max){
}else if (null != min && null == max && min < node.val){
}else if (null != min && null != max && min < node.val && node.val < max){
}else {
return false;
}
// left
if (!subValidBSTLeft(node.left, min, node.val)){
return false;
}
// right
if (!subValidBSTLeft(node.right, node.val, max)){
return false;
}
return true;
}
}

102. 二叉树的层次遍历

问题

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resp = new ArrayList<>();
levelOrder(root, 0, resp);
return resp;
}
public void levelOrder(TreeNode cur, int cur_level, List<List<Integer>> resp) {
if(null == cur){
return;
}
if(cur_level == resp.size()){
resp.add(new ArrayList<>());
}
resp.get(cur_level).add(cur.val);
levelOrder(cur.left, cur_level+1, resp);
levelOrder(cur.right, cur_level+1, resp);
}
}

一次过


104. 二叉树的最大深度

问题

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

解答

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxDepth(TreeNode root) {
return maxDepth(root, 0);
}
public int maxDepth(TreeNode cur, int level) {
if(null == cur) return level;
int left_level = maxDepth(cur.left, level + 1);
int right_level = maxDepth(cur.right, level + 1);
return left_level > right_level ? left_level: right_level;
}
}

一次过


111. 二叉树的最小深度

题目

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最小深度  2.

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int minDepth(TreeNode root) {
return minDepth(root, 0);
}

public int minDepth(TreeNode cur, int level) {
if (null == cur) return level;
if (null == cur.left && null == cur.right) {
return level + 1;
} else if (null != cur.left && null == cur.right) {
return minDepth(cur.left, level + 1);
} else if (null == cur.left && null != cur.right) {
return minDepth(cur.right, level + 1);
} else {
int left_level = minDepth(cur.left, level + 1);
int right_level = minDepth(cur.right, level + 1);
return left_level > right_level ? right_level : left_level;
}
}
}

141. 环形链表

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

正常的解题思路,通过记录走过的节点来判断是否有环。

时间复杂度:O(n),对于含有 n 个元素的链表,我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1) 的时间。

空间复杂度:O(n),空间取决于添加到哈希表中的元素数目,最多可以添加 n 个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<Integer> points = new HashSet<Integer>();
ListNode cur = head;
while (null != cur){
int curHashCode = cur.hashCode();
if(points.contains(curHashCode)){
return true;
}
points.add(curHashCode);
cur = cur.next;
}
return false;
}
}

第二种解题思路是双指针大小步,一个指针每次走一步,另一个指针每次走两步,如果有环的话则两个指针最终会相遇。

在最糟糕的情形下,时间复杂度为 O(N+K),也就是 O(n)。

空间复杂度:O(1),我们只使用了慢指针和快指针两个结点,所以空间复杂度为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (null == head){
return false;
}else if (null == head.next){
return false;
}else if (head == head.next.next){
return true;
}
ListNode minCur = head.next;
ListNode maxCur = head.next.next;
while (minCur != maxCur){
if (null == minCur.next){
return false;
}else if (null == maxCur.next){
return false;
}else if (null == maxCur.next.next){
return false;
}
minCur = minCur.next;
maxCur = maxCur.next.next;
if (minCur == maxCur){
return true;
}
}
return false;
}
}

146. LRU缓存

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

链接:https://leetcode-cn.com/problems/lru-cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import OrderedDict

class LRUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self._cache = OrderedDict()
self._size = capacity

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self._cache:
return -1
val = self._cache.pop(key)
self._cache[key] = val
return val

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self._cache:
self._cache.pop(key)
self._cache[key] = value
else:
if len(self._cache) == self._size:
self._cache.popitem(last=False)
self._cache[key] = value


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

有序字典的解法
时间复杂度 O(1)
空间复杂度 O(capacity)

Java 解法需要 LinkedHashMap TODO

LRU(Least Recently Used)最少最近使用,一种页面置换算法。

LFU(Least Frequently Used)最近最不常用。

其它

LRU


206. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class ReverseLinkedList {
public static void main(String[] args) {
ListNode listNode = ListNode.of(
1,
ListNode.of(
2,
ListNode.of(
3,
ListNode.of(
4,
ListNode.of(
5, null
)
)
)
)
);
ListNode next = listNode;
while (null != next) {
System.out.println(next.val);
next = next.next;
}

System.out.println("===");
ListNode reverse = reverse3(listNode);

ListNode next2 = reverse;
while (null != next2) {
System.out.println(next2.val);
next2 = next2.next;
}
}

/**
* 官方推荐的
* @param head
* @return
*/
public static ListNode reverse2(ListNode head) {
// prev -> curr -> nextTemp
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}

/**
* 自己写的
* @param head
* @return
*/
public static ListNode reverse(ListNode head) {
// cur -> prev -> tmp
ListNode cur = head;
ListNode next = head.next;
head.next = null;
while (null != cur) {
ListNode tmp = null;
if (null != next) {
tmp = next.next;
next.next = cur;
}
if (null == next) {
break;
}
cur = next;
next = tmp;
}
return cur;
}

/**
* 复写的
* 1. 记录前一个节点,当前节点
* 2. 迭代
* 3. 取出当前节点到临时变量
* 4. -- 现在有 prev -> curr -> next 三个节点
* 5. 将 curr.next -> prev,改变指向方向
* 6. 依次挪动节点位置 prev = curr , curr = nextTemp
* 7. 最后返回 prev
*
* 时间复杂度 O(n)
* 空间复杂度 O(1)
* @param head
* @return
*/
public static ListNode reverse3(ListNode head) {
// prev -> curr -> next
ListNode prev = null;
ListNode curr = head;
while (null != curr) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}

208. 实现 Trie (前缀树)

题目

实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

分析

前缀树
Trie
字典树

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class Trie {
private final int SIZE = 26;
private Node root;

private class Node {
private boolean isStr;
private int num;
private Node[] child;

public Node() {
child = new Node[SIZE];
isStr = false;
num = 1;
}
}

public Trie() {
root = new Node();
}

public void insert(String word) {
if (null == word || word.isEmpty()) {
return;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null) {
Node tmp = new Node();
pNode.child[index] = tmp;
} else {
pNode.child[index].num++;
}
pNode = pNode.child[index];
}
pNode.isStr = true;
}

public boolean search(String word) {
if (null == word || word.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null || (word.length() - i == 1 && pNode.child[index].isStr == false)) {
return false;
}
pNode = pNode.child[index];
}
return true;
}

public boolean startsWith(String prefix) {
if (null == prefix || prefix.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (pNode.child[index] == null) {
return false;
}
pNode = pNode.child[index];
}
return true;
}
}


703. 数据流中的第K大元素

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.PriorityQueue;

public class KthLargest {
private PriorityQueue<Integer> minHeap;
private int kSize;

public KthLargest(int k, int[] nums) {
kSize = k;
minHeap=new PriorityQueue<Integer>(kSize);
for (int i = 0; i< nums.length; i++){
add(nums[i]);
}
}

public int add(int val) {
if (minHeap.size() < kSize){
minHeap.offer(val);
}else if (minHeap.peek() < val){
minHeap.poll();
minHeap.offer(val);
}
return minHeap.peek();
}
}

Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。

关于堆操作:https://shmilyaw-hotmail-com.iteye.com/blog/1775868

操作说明:

方法名功能描述
add(Ee)在队列头部增加一个元素,如果容量已满,则抛出异常,成功则返回true。
clear()清空
contains(Objecto)检查是否包含当前参数元素
offer(Ee)在队列头部增加一个元素,如果容量已满,则返回false,成功加入,返回true。
peek()返回队列头部节点,但不移除队列头节点。
poll()将队列头部元素移出队列并返回。
remove(Objecto)将队列头部元素移出队列并返回,如果队列为空,则抛出异常。
size()返回长度