大家都多少薪水啊

刚入职实习生 目前做市场 但后面肯定要承担业绩做成销售的 听公司里的老人说了 这几年公司陆续来了五六十个实习生 最后一个都没有留下来 一开始还觉得是不是大家都比较浮躁 因为我们行业要做成第一单确实比较难对新人来说 但我实习了一个月后我发现真的很难留下来 不仅是没有业绩 而是感觉公司里所有人都没有想帮你成长的心比如我现在在做项目 这个板块之前公司一直没有开展起来 但刚好和我学的专业相关 所以老板就让我负责 你没听错 是我 我一个人 虽然老板说会提供帮助 但我每次问他他都说下次找谁谁谁 最后是另外一个实习生主动来帮我 也就是说这个新项目就是我们两个实习生在负责 心很累我没什么经验 不知道是不是很多企业都是这样的 我自己太玻璃心 还是公司制度就是有问题每天上班比上坟还沉重

现在主要在纠结两个工作，实在实在要被逼签了，自己也很想赶快了解了秋招这件大事！！！！！ 请大家走过路过！救救孩子！！！！ 一个是快手，大sp，mmu，视频算法，薪资比较高，户口方面hr说按照面试评价和提前实习来排序，现在并不能知道有没有排到的希望 一个是小米，os上比较高的那档，ailab，工作应该也是视频相关，但是比起快手还是差了15w左右，确定可以解决北京户口，但是要签三年合同 主要考量： 1. 北京户口的最大用处应该是小孩上学和找工作，但是北京教育资源严重不平衡，学区房估计还要几年可能也付不了首付，其他用处暂时没有发现，欢迎大家补充 2. 拿北京户口的机会只有一次，但是目前单身，所以不知道以后是否一定在北京，如果几年后去了别的城市放弃了户口，选择小米是不是比较亏 3. 快手和小米相比，自认为快手会有比较好的发展，可能两三年后和小米的差距应该就不是简单的十多万了，从以后发展和跳槽来说可能要好一点（只是自认为 如果有过来人欢迎指导纠正） 4. 我已经想要听天由命了，甚至想去选快手，如果老天明年从天而降一个户口砸中我，说明天要留我，如果砸不中，那就江湖再见吧

以下乃一家之言，有用，则吾心甚慰，无用，君权当一笑。 一家之言，常有多家之辩，望诸君善待吾之善心，莫急言于在下。 吾求无错，奈何水平所限，失误再所难免，请各位提之，吾当改之。 吾所求岗位均为研发岗位，故技术人才更适用之。 从电子战领域转向Java后端开发，不到一年，踩了不少坑，走了不少弯路，激烈的校招一直逼迫我快速地吸收知识，加强能力，让我难有喘息的机会。但学习过程中，内心明白效率的重要性，因此始终尽最大努力保证高效地学习，深入地思考，注重将知识融汇贯通，构建合理强大而稳定的知识结构，功夫不负有心人，终取得不错的成绩。在此，将我的学习路径整理成文，供有志于Java后端开发的工程师参考。谨以此文，纪念这高效的一年。 注1：本文首发于我的公众号~ 注2：本文希望大家能够扎实基本功，稳扎稳打地练习自己的能力。如果是为了准备校招，大家要酌情选择一些比较复杂的资料的核心章节，例如《深入理解计算机系统》这样的大部头，选择里面的核心章节阅读即可，例如关于硬件部分的就可以忽略不看。 目录 0.概述 1.初阶 2.进阶 3.综合 0. 概述 在《2019秋招经验谈》这篇文章中，我通过我的练级之路篇介绍了我是如何转行的，开启Java后端开发工程师之路的，通过认知思维篇讲述了在开启练级之路之前你需要具备的心态以及思维，通过专业技术篇介绍了Java后端开发工程师需要掌握的核心知识，通过面试技巧篇介绍了作为一个技术人如何在别人面前展示自己的能力，通过面试篇介绍了多家公司的面经，学习资料篇则介绍了一些非常经典的学习资料，但是只是资料的罗列，并没有指明应该如何系统地开始学习，本文将系统的介绍Java开发工程师的练级攻略。 在正式开始介绍Java练级攻略之前，我需要强调以下几个问题： 时刻保持自信。即使遇到困难，也是暂时的，不要因此泄气，跳过它，继续学习，待你学完后面的知识，你便会豁然开朗。 始终保持思考。一定要学习思考，思考为什么要这样，而不是那样。当你具备一定知识的时候，还要举一反三的思考，将知识融汇贯通，变成能力，最终构建出自己的知识和能力体系。 一定要动手。无论示例多简单，都一定要自己手过一遍，好记性不如烂笔头，大量的思考笔记，大量的编程实践是永远少不了的。你可以读的少，但是不能码的少。 不要犹豫。既然选择了一条路，你就坚持走下去，不要想这条路对不对，你只有走了才知道对不对，不要犹豫，开始了，就有收获，走下去，就有结果。 迭代学习。不要想着一口吃成个胖子，要讲究迭代学习，即首先了解知识结构，然后再逐层深入，一层层深度逐渐解决问题，这样的迭代学习，不仅会让你的效率提高，而且会让你对知识有不同层面的理解。 接下来，正式开始Java练级攻略。 1. 初阶 初阶的学习，主要是全面了解各个科目的整体的知识结构，在脑海中对每个科目的知识结构能有个全面的印象，主要解决的是怎么做的问题。 1.1 Java核心知识 作为Java后端开发工程师，Java是我们的武器，因此精通Java是必须的。首先我们需要整体掌握Java的知识结构，在此推荐以下2本书（任选其一即可）： 书籍：《Head First Java》：具有大量插图，非常适合入门 书籍：《Java核心技术(卷一):基础知识 》 ：sun公司官方出版，与《Java编程思想》齐名的Java图书泰斗 1.2 数据结构与算法 数据结构与算法是一个工程师的内功，当我们掌握了Java的核心知识之后，开始数据结构与算法的学习，是一个不错的选择，一来掌握数据结构与算法，二来也强化Java核心知识的理解，为Java的进阶打下坚实的基础。 关于数据结构与算法，在这里推荐以下资料： 书籍：《算法·第四版》 视频：CS61B 刷题：算法练级计划 1.3 TCP/IP协议 TCP/IP协议族对于Java后端工程师来讲，是必不可少的，因此，在学习数据结构与算法的同时，可以开启计算机网络的学习，在这里推荐以下2本书（任选其一即可）： 书籍：《TCP/IP详解·卷1》 书籍：《计算机网络：自顶向下方法(原书第6版)》 1.4 操作系统（OS） 操作系统的学习对于我们认知计算机系统是非常有必要的，在这里推荐以下的材料： 书籍：《Operating Systems: Three Easy Pieces》（非常非常好的书，强烈推荐） 视频：操作系统（清华大学） 视频：Linux学习视频 1.5 数据库MySQL 对于Java后端工程师来说，数据库必不可少，以下推荐： 视频：与MySQL的零距离接触 书籍：《MySQL必知必会》 1.6 数据库Redis Redis广泛的应用于缓存和分布式系统中，因此对于Redis的学习非常重要，推荐以下材料： 书籍：《Redis实战》 官网：https://redis.io/(一定要把官网上的命令好好过一遍，把官网的文章好好读一下，非常好) 1.7 Git & Github 非常流行的版本控制系统，推荐以下资料： 视频：GitHub&Git入门基础 视频：廖雪峰Git教程 动画：Learn Git Branching 2. 进阶 进阶学习的目的主要是从应用知识转向思考其底层，深入的研究各个科目的底层逻辑，主要解决的是为什么的问题？ 2.1 Java核心知识进阶 掌握核心知识基础之后，需要掌握一些Java的高级用法，推荐以下材料： 书籍：《Java编程思想》 书籍：《Effective Java》 同时，在这里还需要阅读Core Java的底层源码。见《2019秋招经验谈》专业技术篇。 2.2 JVM 掌握Java核心知识之后，我们便需要掌握JVM，推荐以下材料： 书籍：《深入理解Java虚拟机》 视频：Java生产环境下性能监控与调优详解（选做） 2.3 Java并发与多线程 并发与多线程是Java一项很核心的能力，推荐以下资料 (2选1，建议选择后者) ： 书籍：《Java并发编程的艺术》 书籍：《Java并发编程实战》 2.4 数据结构与算法进阶 数据结构与算法的进阶很简单，就是大量的刷题，推荐以下材料： 书籍：《剑指offer》 书籍：《程序员代码面试指南》左神 视频：不想看书的，可以直接看左神的视频（我就不用多说了，懂的自然懂） 视频：初级 视频：中高级 刷题：剑指offer 刷题：leetcode 刷题：算法练级计划（通过面试题刷算法） 海量数据处理： 博客： July博客 书籍：《编程珠玑》 动态规划： 经典动态规划问题 2.5 TCP/IP协议进阶 推荐以下材料： 书籍：《图解TCP/IP》（若看完了初阶的书，这本书可以作为复习，或者选择不看） 书籍：《图解HTTP》（若看完了初阶的书，这本书可以作为复习，或者选择不看） 2.6 操作系统（OS）进阶 推荐以下材料： 书籍：《深入理解计算机系统》 书籍：《鸟哥的linux私房菜》 2.7 数据库MySQL进阶 推荐以下材料： 书籍：《MySQL技术内幕 Innodb存储引擎》 书籍： 《高性能MySQL》 2.8 数据库Redis进阶 推荐以下材料： 书籍：《Redis设计与实现》 3. 综合 综合部分主要是介绍如何将前面学过的知识应用起来，即解决的是融会贯通，形成体系的问题。 3.1 面向对象与设计模式 推荐资料如下： 视频：设计模式(马士兵) 书籍：《Head First 设计模式》 3.2 项目（应用） 项目：叶神的高级项目课 目标: 熟悉Java后端开发流程，搞定Java后端项目 涉及技术栈：Spring Boot、MySQL、Redis、Nginx、Python、异步框架、全文搜索技术、排名算法、敏感词过滤算法、项目部署、项目设计、设计模式等 面试相关项目问题：见帖子《2019秋招经验谈》 2.5节：招商银行信用卡中心（信息技术部）面试的问题，对这个项目问的非常详细，给大家一个参考。 至此，关于项目，从项目本身到项目在面试中可能遇到的问题，便都准备完毕了。 参考资料： Spring官网：https://spring.io/ MyBatis官网：http://www.mybatis.org/mybatis-3/ 3.3 项目进阶（底层研究） 推荐以下材料： 书籍：《深入分析JavaWeb技术内幕》 书籍：《大型网站技术架构·核心原理与案例分析》 书籍：《Spring技术内幕》 （这本写的太好了） 最后分布式系统相关资料： System Design Primer CAP理论 一致性模型 可用性模式 DNS CDN 负载均衡 反向*** 应用层的微服务和服务发现 关系型数据库和NoSQL 缓存 异步通讯 安全等 写到这里，我想Java后端开发工程师入门应该是够了，甚至可以说已经有了一定的深入了。回顾一下，发现写了很多，但是大家不要吓到，徐徐图之，人生本来就是一个练级迭代的过程，希望你能保持自信，不断思考，坚持到底，搞定这份攻略。 最后，鉴于水平有限，有可能有遗漏的地方或者是不对的地方，烦请大家补充和指正。谢谢大家。如果有用的话，欢迎大家转发分享给同学，也希望大家点个赞鼓励一下~ 希望这份攻略能够帮助到大家,也欢迎大家与我留言评论交流~ 推荐阅读 1.Java攻略: 《Java练级攻略》 2.算法攻略：《算法练级计划》 3.校招攻略：《2019秋招经验谈》

按照惯例先自我介绍一下： 楼主985本科，计算机专业，大三下之前还一直倾向于保研，大三下开始突然脑子发热死活不想读研究生了，因此在七月份开始准备找工作。申请的大多是Java开发的岗位，目前拿到了百度、美团和华为的offer。在大神眼中算不上什么好offer，但是对个人而言已经比较满意了，也不想再找了，所以用此篇面经结束我的秋招，与君共勉~ 下面是我的一些面经，好多东西也记不清楚了，忘大家见谅。按照面试的顺序来吧，投的公司不是很多，不想离家太远。 网易内推(一面挂)： （1）自我介绍 （2）HashMap中hash冲突的解决方案 （3）ConcurrentHashMap的实现原理以及volatile在内存模型中的含义等等 （4）Redis事务和Redis的持久化 （5）网络协议的一些知识，记得非常清楚的是通过命令获取连接一个网站所经过的路由器，只知道通过设置IP协议中的TTL来实现，但是具体不知，答的不是很好 （6）设计模式中的一些知识 总结：内推需谨慎，没准备好的话不参加内推也罢，多一次机会都是骗人的。这次最大的收获应该就是简历上的东西一定要完完全全明白，不清楚的千万不要写到简历上去，徒增尴尬。 华为优招（拿到offer）： 仔细想来还真不知道华为问了什么，一面在吹水，二面就问了一下是如何准备的，把我会的东西给他讲了一个遍，最后设计了一个通信系统就结束了。 途牛（死活没消息）： 一面： （1）快排的基本思想和优化 （2）数据库索引，各种索引都设计到了，又给面试官讲了一些数据库优化路径的东西 （3）多线程之间的通信，问的具体问题已经不记得了 二面： （1）项目，主要问到了Spring IOC和事务的相关知识，还有几个功能的实现 （2）Netty框架，问的不深，简单的问了几个问题 三面（HR） 新美大： 一面：对着简历一条一条的问过来 （1）Java的相关知识，HashMap和LinkedHashMap的相关知识，LRU设计 （2）设计员工类的equals方法和hashcode方法 （3）JVM虚拟机双亲委派模型以及双亲委派模型被破坏的情况 （4）Lock和synchronized的异同点 （5）算法实现：给定一个字符串判断是否是一个合法的IP地址，如果是保存成int类型，同时也写int转IP地址的函数 （6）JVM虚拟机垃圾收集器，G1比CMS更优秀在那些地方等 （7）写一个SQL语句，大体要求是将(A,B)字段重复的记录删掉只保留最大的C字段的那条记录 （8）Java同步器的使用场景 还有一些相关的问题记得不是很清楚了，面的非常充实 二面： （1）项目的相关知识，这里又问到了ThreadLocal的实现 （2）Spring MVC的工作流程、Spring IOC的实现过程，因为在这里提到了ConcurrentHashMap，所以又问了ConcurrentHashMap的实现 （3）项目中Redis的使用，是否了解新浪微博对Redis的使用，这里就把自己的了解说了一些 （4）面试官拿出来一本试题册，上面有多个题，然后挑了几道给我做 （5）实现一个售票的服务，需求是10000张票，5个窗口，进行卖票。大体思路是：开五个线程，每个线程对应一个阻塞队列，每次找出这五个阻塞队列中元素最少的队列添加元素。 （6）Java重载跟重写 三面： 三面是总监级别的吧，没问很多细节的东西 （1）针对项目，为什么要做这个东西，价值是哪里，如何推广，如何进行需求分析等等 （2）项目中有去重功能的实现，就问了百度网页去重和谷歌网页去重是如何实现的，我只了解大概，就把自己知道的说了，并解释了自己的网页去重是如何实现的，主要是用的谷歌的SimHash算法，并解释了为什么不用百度的去重算法 （3）你觉得看论文有用吗 （4）就问我对部门的一些要求，简单介绍了他的部门等等等等 四面（HR） 百度： 我申报的是软件开发岗位，百度派到南京的面试官大多是C++的面试官 一面： 上来就告诉我不懂Java，所以我们来写代码，所以我就写了一个小时的代码 写的代码有：LRU的实现：用双向链表和数组、字典树的构建和查找，分析时间复杂度、两个链表做加法，不申请另外的内存空间，主要看你考虑的全不全 二面： 不懂Java，所以聊操作系统和Mysql中InnoDB的相关实现 （1）写代码 找出二叉树中和值最大的路径并打印出来 （2）select和epoll的区别 （3）数据库索引的一些知识，簇集索引、组合索引为主，当插入的值为NULL时，数据库会怎样等等 （4）数据库事务，隔离级别中可重复度的具体实现 （5）Redis的底层实现，没看过，只知道是C写的 三面： 三面真的处处都是坑 上来问平时喜欢干嘛，当说到有时打打牌时，问题来了，让我把他当成一个完全不会斗地主的人，给我两分钟时间教会他如何斗地主 假如让我设计一个斗地主的游戏怎么设计，分为真人对战和跟机器人打 对工作地点的要求啊之类的常规问题 到这里我的秋招基本结束了，有想过放弃，但是当放弃保研的时候也知道了自己只剩这一条路要走，虽然不敢说自己每天都有很努力的在学习，但是至少我这两个多月里每天都有在学习。努力才可能有回报！ 给大家推荐一些书，希望能对大家有所帮助 （1）《深入理解JVM虚拟机》，对JVM的相关知识均来源于此书与一些博客 （2）Java并发的东西我更推荐大家去看《Java并发编程的艺术》，总感觉比翻译的更容易理解一些 （3）《Effective Java》 （4）数据结构看课本 （5）计算机网络看《TCP/IP详解》卷一和潘爱民的计算机网络 （6）操作系统看课本 （7）数据库看课本和《高性能Mysql》 （8）Spring框架看《Spring in action》和《Spring技术内幕》，不一定看书，看博客之类的都可以 （9）有用过Redis的可以看《Redis实战》和《Redis设计与实现》 刷题的话就多刷LeetCode和《剑指Offer》，还是挺有帮助的 项目一定要弄透彻，从数据库表设计到每个功能的实现以及可能问到的问题多想想并且准备好。 最后，助大家找到满意的工作，不要放弃，放弃了就真什么都没有了，走就要走完，这样只要也不会后悔。 大家加油！

最后还是要离开广州了，感谢在广州的一年半，感谢中移互联网的不离不弃，之前放弃的offer又打来电话挽留。 一度很想很想留在广州，每每路过琶洲大桥，看着远处的广州塔，无限感慨，还有10天就要离开这片心心念念很多年的热土，手机号的归属地也是广东广州，打算一直留着作为纪念，证明我来过。 在中移互联网11个月的工作里，一度很想留下，每天都在留下与离开之间挣扎与纠结。 总是迫切地要离开某种生活，临走前突然发现我舍不得工作日的下午一起偷偷溜出去买冰棍的那个同事，舍不得公寓楼下经常帮我寄快递的那个保安，舍不得电梯里每天遇到的小狗，舍不得家门口开到深夜的烧烤摊。一切都很好，是我执意要离开，是我不配拥有这一切。 (这段是微博一个博主的帖子，拿来用。) 深夜碎碎念。讲讲我的找工作历程。 5.30日也就是昨天，中移互联网打来电话，问我要不要在考虑下中移互联网的工作机会，这是给我的第二次机会，HR说了很多动听的话，我一度又开始怀疑自己的选择。我想我还是放弃了，如果我选了中移，我可能一辈子都不太想离开舒适区了。 5.4日，中移发了第一次录用通知，我选择了华为。 4.3日，农行广州发来录用通知。 1.31日，携程租车发来录用通知，其实想去上海看看国际化大都市，想感受下纸醉金迷的生活，想想能去凌空SOHO办公，也算是弥补了当年离开北京还没来得及去望京SOHO办公的遗憾，抓了很多次阄，次次华为。此时内心最想留在中移。后面还是放弃了携程。 12.1华为发来offer，毁约游戏公司。期间纠结了三天三夜。 11.30在大广州遇见了我本科的校友，当即签约创业游戏公司。想做游戏主程开发，但实际上我并不喜欢游戏，大约是本科签约的游戏公司天天都被逼着玩游戏，从此以后就戒了。但是觉得创业公司有活力有冲劲，再加上本科校友是合伙人。想想人生应该任性一次，随心所选。人生只有一次，按部就班多么无聊。 以为自己真的有魄力承担创业公司的一切风险，最后在现实面前我怂了。看着老东家捕鱼达人一点点没落，当年大张旗鼓的从方恒国际入住望京SOHO，意气风发要去美国上市，股票期权。现如今问起以前的同事，基本上都离了职，看看QQ上的同事，都换了公司，从当年的1500人到现在的100人。真心问自己情怀能不能当饭吃。所以最终还是没选择校友的游戏公司，到现在还是觉得心痛，心想，我要是年轻几岁还像当年一样不怕输多好。 12.8埃森哲CDC录用通知。 11.29招商信诺录用通知。 11.28亚信加薪录用通知。 11.23亚信第一次录用通知。 9.28广州汇智通信录用通知。 期间有两个月没有找到合适的工作，面了广州电信，电信研究院，烽火通信，有米科技，招商金科面啥挂啥，笔啥挂啥。 一度怀疑自己是不是该留个公司保底，心情一度很低落。后面突然就出奇的顺利，一直没敢投BAT觉得自己太菜，不过有点后悔应该尝试一下的。 为什么我还试了很多不知名的公司，因为有面试我就会去，就当做是攒面试经验，或者多了解了解别的公司。 当初一方面一心想留在广州，另一方面觉得自己水平不够，所以知名的公司都没怎么投递，BAT京东头条等等，这是比较后悔的一点，应该多去试试，那么多内推机会真的该珍惜下的。 秋招的时候白天上班，晚上下了班去大学城笔试面试，实在太累，打算好好春招找找工作。不知道什么时候突然有了中年危机，以前本科毕业的时候觉得四十岁离我太遥远，现在想想也就是十几年的事情，好像近在眼前。所以，春招又投了一波国企银行。但是，事实证明，我还是不太喜欢国企的氛围，我努力让自己爱上不加班，每天955的生活，但是，我更多的却是恐慌，我可能没法接受，两年后大家薪资50%涨幅，甚至翻翻，而我依然原地踏步，还要骗自己时薪高，自废武功。 以下这段是人生感慨，如果当年考上华工，可能会去做一名管培生吧，如果后来又考上中传，可能现在不知道是不是捧某个十八线小艺人，也可能是在某个不知名电视台拍生活小窍门的影片，可能也没啥机会像彭浩翔一样拍出志明与春娇的电影。 可是，人生不是因为未知才精彩么。中传的单科一分之差，就差不多改变了命运。 还有以上的公司，一般国企笔试就是行测＋计算机基础知识(一般都是行测)面试就是聊人生，职业规划。互联网公司一般最喜欢问数据库优化，集群，java虚拟机优化，多线程，事务。关于薪资方面，牛客网上的薪水可信度还是很高的。 面试的话基本上牛客网上的面试帖子多看看，问题都搞懂了，面试这些公司都是轻松愉快的。 最后，感谢牛客的小伙伴的内推，感谢每一个热心解答问题同学。祝各位前程似锦。 推一把这段时间做的小程序，大家可以在小程序搜索栏搜索“为爱留言”体验小程序，有意见大家可以随意提。 最后的最后，还有7个工作日离开，还有10天离开广州，附一张大半夜不睡觉去猎德大桥拍的广州塔和这11个月来git提交的代码。 人生就是有很多的无奈，选择华为很大一部分原因是因为西安是我的家乡。可我还想去上海看看，还想留在广州。 也感谢给我每一个工作机会的公司，祝，好。 晚安，明天倒数搬砖日。 感谢大广州给我的如此多的机会。 思绪比较乱想到哪里写哪里。 让我与你握别 再轻轻抽出我的手 知道思念从此生根 浮云白日 山川庄严温柔 让我与你握别 再轻轻抽出我的手 华年从此停顿 热泪在心中汇成河流 是那样万般无奈的凝视 渡口旁找不到一朵可以相送的花 就把祝福别在襟上吧 再见广州。

人在杭州滨江  公司具体名字我不想说。 这秋招都快结束了裁员，我人傻了。 下午开始校招群里面就开始炸群，没入职的就直接打电话约谈说被毁约了。 我以为我实习了4个多月没事，毕竟这周我还在做需求。 但是下午四点半吧就被主管约谈说你要走人，早上的时候我还在跨部门拉研发们一起开会过prd，下午就被约谈，6点就走人了。 校招生四十多个左右吧，据我所知的就留下了不超过五个研发。 没意思，你玩呗。

本来呢,我是想写一个面经的,后来想了想,面经只是当时的一些临场发挥,好像用处并不是很大,大多数问题,别人的帖子也能看到,就不写了.而且我的经历也不多,秋招就去面了美团和去哪儿,9月20左右就签了,懒得找了.滴滴,腾讯,招银什么的签了之后就懒得去面试了,所以就写个准备的经验吧. 先来个自我介绍,某末流985,软件工程专业,本科生,专业250人,专业排名211的渣渣,到拿了offer计算机网络还挂着.没有跟过导师,没项目,没实习经验.本来一直打游戏,之后身边的人都去实习之后,怕失业,遂从5月底开始戒了LOL努力学习,一下就是我从5月底到9月的所有的经验总结了.希望群里的巨巨看到别歧视我啊. 首先我认为:找工作,应该要明确自己想干嘛,能干嘛.不过这些问题,我也帮不了,自己解决吧.然后就是深入学习了.接下来以我这学渣为例.我投的是后台开发. 项目:因为没项目,所以自己弄个项目,上网看视频跟着做也行,临时抱老师大腿跟着做也行,我就是给老师的项目小小地升级下就拿去扯了...不过不是单纯的扯,我是把整个项目的架构思路,设计原理,中间件的原理和部分中间件源码给看了.比如项目里面用到了Nginx,我就在网上把Nginx负载均衡的原理和代码给弄明白了.然后面试的时候说源码和原理,讲负载均衡的时候,再把里面的epoll的原理和数据结构说下,就这么弄,然后项目就算过去了... 语言,算法,数据结构:语言会问一点,但不深入.我用的c++,所以我就看了一些STL的源码,还有一些C++常见的坑,其实看完efftive c++和c++prime这种我感觉就差不多了,然后算法和数据结构呢,算法我是刷牛客的,数据结构我是看STL然后就融会贯通一下感觉都差不多.面试的时候就问了const是怎么实现的;在STL库里面,那些数据结构是怎样实现的,map,set,list这些,把原理讲一遍就好;还有个红黑树,b树,b+树的原理,什么插入删除啊这种,弄懂了就差不多了;当时还问了我STL里的sort函数用了哪几个排序,什么时候用;还好机智的我看过,不然就黑了...数据结构会上面那几种结构就差不多了,面试的时候我被问的最多的就链表...树都很少问.算法就是字符串匹配,排序这种,也不算很难,手写也不难,看看就行了. 网络和操作系统:网络部分我重点准备HTTP,TCP这两个,然后再加上别人的面经里的经典问题,有能力的看看TCP/IP详解就更好了;操作系统我是先看了下书(就那本老师推荐的教材),然后照着别人的面经准备的.网络是滴滴1面问的多,别的就问个HTTP和HTTPS的不同;HTTP1.0和1.1的区别;TCP和UDP;cookie和session这种东西的一些基本的问题,好好看看书就会了.不过当时滴滴问的多点,比如网络粘包产生的原因和解决方法;session的实现方式;cookie的安全性;访问网页突然变慢了,让你找原因;DNS欺骗的原理和防御;这种感觉还挺难.操作系统就问了些基本的,fork和exec的区别;进程线程的区别;进程间通信;死锁这种基础的. 以上就是我技术上的东西了,感觉找工作就这么几块知识点语言,网络,操作系统,数据结构和算法,再加个项目,全部弄懂那太厉害了,不过你总要有个深入的点,能达到面试官的要求,能怎么问都问不倒就更厉害了.要是你之前像我这么菜的话,那就得多学多看了,别想着天上掉馅饼,脚踏实地地学.努力就好,尽人事,待天命. 现在网络这么发达,网上一搜就能找到很多有用的知识,多看多学多用,免费的这么好的东西,不用就有点可惜了.最后祝大家都能找到满意的工作.

1.了解红黑树 学习完AVL树，开始了红黑树的学习，关于红黑树，和AVL树是类似的，都是会在我们进行插入操作或者删除操作以后会进行一些操作，来使得整个二叉树保持一个平衡。 红黑树和AVL树的区别在于一个是依照平衡因子来维持整个树，而红黑树是利用颜色来限定平衡。 自从红黑树出现以后，AVL树就慢慢消失了，原因，会在后面讲解。 另外，最为重要的是在STL当中，有很多都应用了红黑树，比如：set, multiset, map, multimap 2.理解红黑树的特点 红黑树为了维持平衡，提出了4个条件。 每个节点只有黑色和红色两种区别 根节点一定是黑色。 不能出现连续的红色 每条路径上黑色节点的数目是相同的。 -每个叶子节点是黑的（这里的叶子节点这里可以理解为NUL节点和叶子节点） 通过这4个条件，就可以维持一棵红黑树的平衡。 3.红黑树节点结构 红黑的节点可以参考AVL树的节点，在AVL中，利用平衡因子维持平衡，在红黑树中，我们要利用颜色，所以，我们在这里给一个颜色。这个颜色当然只能有红的或者是黑的，所以我们在这里利用枚举来保存这个颜色。 enum color {     BLACK,     RED }; //红黑树的节点结构  template<typename K, typename V> struct RBNode {     typedef RBNode<K, V> Node;     RBNode(const K& key,const V& value)         : _left(NULL)         , _right(NULL)         , _parent(NULL)         , _key(key)         , _value(value)         , _color(RED)     {}     Node* _left;     Node* _right;     Node* _parent;     K _key;     V _value;     int _color; }; 4.红黑树的插入算法 我们首先来看红黑树的插入算法，如果你看了我的前两篇文章，关于二叉搜索树的插入算法和AVL树的插入算法以后，我想你能很快有一个大致思路，红黑树，就是插入节点，然后进行调整颜色，调整颜色过程中有些会直接进行变化颜色，有些是要通过旋转变化颜色。 为了简化插入过程，我们需要考虑我们默认插入什么颜色的节点，在这里，你可以想一下，如果你默认插入黑色节点，是否能让每条路径上黑色的节点数目相同？所以，我们默认插入的节点应该是红色节点。 在这里，为了维持那几条规则，所以我们要维护的节点和parent节点，pparent节点和uncle节点。cur就是我们所插入的节点，或者因为插入所做出调整以后影响了上面节点的情况。 在这里，我给出红黑树插入所会遇到的大致几种情况： 下面我们所讨论的统一采用cur，parent，pparent，uncle这几种命名方式。另外，我们插入的cur节点或者向上回溯时的cur皆为红色。 插入根节点 插入节点为根节点的时候，根据第二条规则，我们的根节点为黑色，所以我们记得要对根节点设置为黑色。（注：为了方便其他情况，我们可以采用没种情况都对根节点设置为黑色。） parent节点颜色为红色，uncle节点为红色。（只做变色调整，需要向上回溯）。 这个时候cur的颜色和parent的颜色都为红色，会发生问题，这个时候我们需要进行变色的调整，此时我们来看uncle，uncle为红色。 parent节点为红色，uncle节点为黑色。（旋转调整） 当parent为红色，uncle为黑色的时候，这个时候我们就需要进行旋转调整。 旋转当然分为四种情形： 1.左单旋转：  代码实现： void _BRRolateL(Node *parent)     {         assert(parent);         Node *SubR = parent->_right;         Node *SubRL = SubR->_left;         parent->_right = SubRL;         if (SubRL)             SubRL->_parent = parent;         Node *ppnode = parent->_parent;         SubR->_left = parent;         parent->_parent = SubR;         if (ppnode == NULL)         {             _root = SubR;             SubR->_parent = NULL;         }         else         {             if (ppnode->_left == parent)             {                 ppnode->_left = SubR;             }             else             {                 ppnode->_right = SubR;             }             SubR->_parent = ppnode;         }     } 2.右单旋转： 代码实现： void _BRRolateR(Node *parent)     {         assert(parent);         Node* SubL = parent->_left;         Node* SubLR = SubL->_right;         parent->_left = SubLR;         if (SubLR)             SubLR->_parent = parent;         Node *pparent = parent->_parent;         SubL->_right = parent;         parent->_parent = SubL;         if (pparent == NULL)         {             _root = SubL;             SubL->_parent = NULL;         }         else         {             if (pparent->_left == parent)             {                 pparent->_left = SubL;                 SubL->_parent = pparent;             }             else             {                 pparent->_right = SubL;                 SubL->_parent = pparent;             }         }     } 左右双旋转 ：      _BRRolateL(parent);     std::swap(parent, cur);     _BRRolateR(pparent);     pparent->_color = RED;     parent->_color = BLACK; 右左双旋转 ：      _BRRolateR(parent);     std::swap(parent, cur);     _BRRolateL(pparent);     pparent->_color = RED;    parent->_color = BLACK; 双旋转我采用了单旋转实现所以需要交换parent和cur。 这就是所有的关于插入算法旋转调整的情形。 接下来是插入算法的思路，和AVL树以及二叉搜索树的思路是类似的，都是先进行寻找，找到你所要插入的位置，然后创建节点，插入就好了。这里就不多说了，如果有疑问，可以去看我的AVL树的插入算法讲解和搜索二叉树的插入算法实现讲解。 代码实现：     bool Insert(const K& key, const V& value)     {        if (_root == NULL)         {             _root = new Node(key, value);             _root->_color = BLACK;            return true;         }         Node *cur = _root;         Node *parent = NULL;        while (cur)         {            if (cur->_key < key)             {                parent = cur;                 cur = cur->_right;             }            else if (cur->_key>key)             {                parent = cur;                 cur = cur->_left;             }            else             {                return false;             }         }         cur = new Node(key, value);        if (parent->_key > key)         {            parent->_left = cur;         }        else         {            parent->_right = cur;         }         cur->_parent = parent;        //判断如果parent是根节点，那么直接结束         while (parent!=NULL)         {            //父亲是黑色，cur是红色，符合红黑树，退出             if (parent->_color == BLACK)             {                 break;             }            //父亲和cue都是红色的情况             Node* pparent = parent->_parent;             Node* uncle = NULL;            //考虑parent 是左边的情况             if (pparent->_left == parent)             {                 uncle = pparent->_right;                //考虑叔叔是红色的情况                 if (uncle&&uncle->_color == RED)                 {                     pparent->_color = RED;                     uncle->_color = parent->_color = BLACK;                     cur = pparent;                    parent = cur->_parent;                     continue;                 }                //考虑叔叔不存在或者叔叔是黑色的情况                 else if (uncle == NULL || uncle->_color == BLACK)                 {                    if (cur == parent->_left)                     {                         _BRRolateR(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                    else                     {                         _BRRolateL(parent);                         std::swap(parent, cur);                         _BRRolateR(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                     break;                 }             }            //考虑parent是右边的情况             else             {                 uncle = pparent->_left;                if (uncle&&uncle->_color == RED)                 {                     pparent->_color = RED;                     uncle->_color = parent->_color = BLACK;                     cur = pparent;                    parent = cur->_parent;                 }                else if (uncle == NULL || uncle->_color == BLACK)                 {                    if (cur == parent->_right)                     {                         _BRRolateL(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                    else                     {                        //_BRRolateRL(pparent);                         _BRRolateR(parent);                         std::swap(parent, cur);                         _BRRolateL(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                 }                 break;             }         }         _root->_color = BLACK;        return true;     } 5.红黑树的查找算法 关于红黑树而言，他的查找算法和二叉搜索树和AVL树的也几乎一样。  进行通过key实现查找就好了。 bool Find(const K& key)     {        if (_root == NULL)            return false;         Node *cur = _root;        while(cur)         {            if (cur->_key < key)             {                 cur = cur->_right;             }            else if (cur->_key>key)             {                 cur = cur->_left;             }            else             {                return true;             }         }        return false;     } 6.判断是否是和法红黑树 对于判端一棵树是否是红黑树，其实思路很简单，就是判断红黑树以及它的子树是否满足上述红黑树的特点就好了。 所以，总结下来也就是： 根节点为黑色 没有连续红色节点 每条路径上有相同的黑色节点数 当满足这三个条件的时候，我们就可以认为这棵树是合法的红黑树。 第一个条件好判断，直接可以进行判断，第二个和第三个需要进行递归。 第二个没有连续的红色节点我们的思路就是当这个节点为红色的时候，我们判断它和它的父节点是否颜色相同，如果相同就不是红黑树。 第三个条件的思路就是，因为你需要进行判断红黑树的每条路径黑节点数相同，所以首先你需要给出一个参考，然后每一条路径的黑色节点数和这个参考值进行比对就好了。如果有不相同的，那么就代表这个树不是红黑树。因为我们需要知道每条路径的，所以当一条路径算完以后，另一条路径与它相同的依然可以使用，所以我们进行传值调用。一条路径的结束，也就是找寻到了叶子节点。 bool IsRBTree()     {         //当为空树的时候，是红黑树         if (_root == NULL)         {             return true;         }         //当根节点是红色的时候，直接可以确定不是红黑树         if (_root->_color == RED)         {             return false;         }         //给出一个参考的路径的黑色节点的数目         size_t count = 0;         Node* cur = _root;         while (cur)         {             if (cur->_color == BLACK)                 count++;             cur = cur->_left;         }         //k用来记录一条路径的黑色节点的数目，和count来进行比较         size_t k = 0;         return _IsRBTree(_root, count, k);     } //这里的k需要进行传值，因为这里你需要对每一条路径进行对比，所以在这里，你要找寻完一条路径以后，向上回溯，     bool _IsRBTree(Node* root, const size_t& count, size_t k)     {         if (root == NULL)         {             return true;         }         //当出现两个连续的红色节点的时候，可以确定不是红黑树         if (root->_parent&&root->_color == root->_parent->_color == RED)         {             return false;         }         //如果是黑色节点，k进行++         if (root->_color == BLACK)         {             k++;         }         //如果是叶子节点的话，进行判断k和count是否相等         if (root->_left == NULL&&root->_right == NULL)         {             //k和count不相等，那么就不是红黑树。             if (k == count)                 return true;             else                 return false;         }         //对节点的左右进行检查         return _IsRBTree(root->_left, count, k) && _IsRBTree(root->_right, count, k);     } 转自：http://my.csdn.net/qq_26768741

3. 数组中重复的数字 NowCoder 题目描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 复制代码 1 2 3 4 5 Input: {2, 3, 1, 0, 2, 5}   Output: 2 解题思路 要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。 对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。 以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复： 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public boolean duplicate(int[] nums, int length, int[] duplication) {     if (nums == null || length <= 0)         return false;     for (int i = 0; i < length; i++) {         while (nums[i] != i) {             if (nums[i] == nums[nums[i]]) {                 duplication[0] = nums[i];                 return true;             }             swap(nums, i, nums[i]);         }     }     return false; }   private void swap(int[] nums, int i, int j) {     int t = nums[i];     nums[i] = nums[j];     nums[j] = t; } 4. 二维数组中的查找 NowCoder 题目描述 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。 复制代码 1 2 3 4 5 6 7 8 9 10 11 Consider the following matrix: [   [1,   4,  7, 11, 15],   [2,   5,  8, 12, 19],   [3,   6,  9, 16, 22],   [10, 13, 14, 17, 24],   [18, 21, 23, 26, 30] ]   Given target = 5, return true. Given target = 20, return false. 解题思路 要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。 该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean Find(int target, int[][] matrix) {     if (matrix == null || matrix.length == 0 || matrix[0].length == 0)         return false;     int rows = matrix.length, cols = matrix[0].length;     int r = 0, c = cols - 1; // 从右上角开始     while (r <= rows - 1 && c >= 0) {         if (target == matrix[r][c])             return true;         else if (target > matrix[r][c])             r++;         else             c--;     }     return false; } 5. 替换空格 NowCoder 题目描述 将一个字符串中的空格替换成 "%20"。 复制代码 1 2 3 4 5 Input: "A B"   Output: "A%20B" 解题思路 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。 从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public String replaceSpace(StringBuffer str) {     int P1 = str.length() - 1;     for (int i = 0; i <= P1; i++)         if (str.charAt(i) == ' ')             str.append("  ");       int P2 = str.length() - 1;     while (P1 >= 0 && P2 > P1) {         char c = str.charAt(P1--);         if (c == ' ') {             str.setCharAt(P2--, '0');             str.setCharAt(P2--, '2');             str.setCharAt(P2--, '%');         } else {             str.setCharAt(P2--, c);         }     }     return str.toString(); } 本文转自个人博客：CyC2018/CS-Notes 6. 从尾到头打印链表 NowCoder 题目描述 从尾到头反过来打印出每个结点的值。 解题思路 使用递归 要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。 复制代码 1 2 3 4 5 6 7 8 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {     ArrayList<Integer> ret = new ArrayList<>();     if (listNode != null) {         ret.addAll(printListFromTailToHead(listNode.next));         ret.add(listNode.val);     }     return ret; } 使用头插法 使用头插法可以得到一个逆序的链表。 头结点和第一个节点的区别： 头结点是在头插法中使用的一个额外节点，这个节点不存储值； 第一个节点就是链表的第一个真正存储值的节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {     // 头插法构建逆序链表     ListNode head = new ListNode(-1);     while (listNode != null) {         ListNode memo = listNode.next;         listNode.next = head.next;         head.next = listNode;         listNode = memo;     }     // 构建 ArrayList     ArrayList<Integer> ret = new ArrayList<>();     head = head.next;     while (head != null) {         ret.add(head.val);         head = head.next;     }     return ret; } 使用栈 栈具有后进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {     Stack<Integer> stack = new Stack<>();     while (listNode != null) {         stack.add(listNode.val);         listNode = listNode.next;     }     ArrayList<Integer> ret = new ArrayList<>();     while (!stack.isEmpty())         ret.add(stack.pop());     return ret; } 7. 重建二叉树 NowCoder 题目描述 根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 解题思路 前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // 缓存中序遍历数组每个值对应的索引 private Map<Integer, Integer> indexForInOrders = new HashMap<>();   public TreeNode reConstructBinaryTree(int[] pre, int[] in) {     for (int i = 0; i < in.length; i++)         indexForInOrders.put(in[i], i);     return reConstructBinaryTree(pre, 0, pre.length - 1, 0); }   private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {     if (preL > preR)         return null;     TreeNode root = new TreeNode(pre[preL]);     int inIndex = indexForInOrders.get(root.val);     int leftTreeSize = inIndex - inL;     root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);     root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);     return root; } 8. 二叉树的下一个结点 NowCoder 题目描述 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public class TreeLinkNode {       int val;     TreeLinkNode left = null;     TreeLinkNode right = null;     TreeLinkNode next = null;       TreeLinkNode(int val) {         this.val = val;     } } 解题思路 ① 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点； ② 否则，向上找第一个左链接指向的树包含该节点的祖先节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public TreeLinkNode GetNext(TreeLinkNode pNode) {     if (pNode.right != null) {         TreeLinkNode node = pNode.right;         while (node.left != null)             node = node.left;         return node;     } else {         while (pNode.next != null) {             TreeLinkNode parent = pNode.next;             if (parent.left == pNode)                 return parent;             pNode = pNode.next;         }     }     return null; } 9. 用两个栈实现队列 NowCoder 题目描述 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 解题思路 in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Stack<Integer> in = new Stack<Integer>(); Stack<Integer> out = new Stack<Integer>();   public void push(int node) {     in.push(node); }   public int pop() throws Exception {     if (out.isEmpty())         while (!in.isEmpty())             out.push(in.pop());       if (out.isEmpty())         throw new Exception("queue is empty");       return out.pop(); } 10.1 斐波那契数列 NowCoder 题目描述 求斐波那契数列的第 n 项，n <= 39。 f(n)=\left\{\begin{array}{rcl}0&&{n=0}\\1&&{n=1}\\f(n-1)+f(n-2)&&{n>1}\end{array}\right. f(n)= ⎩ ⎨ ⎧ ​ 0 1 f(n−1)+f(n−2) ​ ​ n=0 n=1 n>1 ​ 解题思路 如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。 递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。 复制代码 1 2 3 4 5 6 7 8 9 public int Fibonacci(int n) {     if (n <= 1)         return n;     int[] fib = new int[n + 1];     fib[1] = 1;     for (int i = 2; i <= n; i++)         fib[i] = fib[i - 1] + fib[i - 2];     return fib[n]; } 考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int Fibonacci(int n) {     if (n <= 1)         return n;     int pre2 = 0, pre1 = 1;     int fib = 0;     for (int i = 2; i <= n; i++) {         fib = pre2 + pre1;         pre2 = pre1;         pre1 = fib;     }     return fib; } 由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution {       private int[] fib = new int[40];       public Solution() {         fib[1] = 1;         for (int i = 2; i < fib.length; i++)             fib[i] = fib[i - 1] + fib[i - 2];     }       public int Fibonacci(int n) {         return fib[n];     } } 10.2 矩形覆盖 NowCoder 题目描述 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？ 解题思路 当 n 为 1 时，只有一种覆盖方法： 当 n 为 2 时，有两种覆盖方法： 要覆盖 2*n 的大矩形，可以先覆盖 2*1 的矩形，再覆盖 2*(n-1) 的矩形；或者先覆盖 2*2 的矩形，再覆盖 2*(n-2) 的矩形。而覆盖 2*(n-1) 和 2*(n-2) 的矩形可以看成子问题。该问题的递推公式如下： f(n)=\left\{\begin{array}{rcl}1&&{n=1}\\2&&{n=2}\\f(n-1)+f(n-2)&&{n>1}\end{array}\right. f(n)= ⎩ ⎨ ⎧ ​ 1 2 f(n−1)+f(n−2) ​ ​ n=1 n=2 n>1 ​ 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int RectCover(int n) {     if (n <= 2)         return n;     int pre2 = 1, pre1 = 2;     int result = 0;     for (int i = 3; i <= n; i++) {         result = pre2 + pre1;         pre2 = pre1;         pre1 = result;     }     return result; } 10.3 跳台阶 NowCoder 题目描述 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 解题思路 当 n = 1 时，只有一种跳法： 当 n = 2 时，有两种跳法： 跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题，该问题的递推公式为： f(n)=\left\{\begin{array}{rcl}1&&{n=1}\\2&&{n=2}\\f(n-1)+f(n-2)&&{n>1}\end{array}\right. f(n)= ⎩ ⎨ ⎧ ​ 1 2 f(n−1)+f(n−2) ​ ​ n=1 n=2 n>1 ​ 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int JumpFloor(int n) {     if (n <= 2)         return n;     int pre2 = 1, pre1 = 2;     int result = 1;     for (int i = 2; i < n; i++) {         result = pre2 + pre1;         pre2 = pre1;         pre1 = result;     }     return result; } 10.4 变态跳台阶 NowCoder 题目描述 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 解题思路 动态规划 复制代码 1 2 3 4 5 6 7 8 public int JumpFloorII(int target) {     int[] dp = new int[target];     Arrays.fill(dp, 1);     for (int i = 1; i < target; i++)         for (int j = 0; j < i; j++)             dp[i] += dp[j];     return dp[target - 1]; } 数学推导 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么 复制代码 1 f(n-1) = f(n-2) + f(n-3) + ... + f(0) 同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去... ，那么 复制代码 1 f(n) = f(n-1) + f(n-2) + ... + f(0) 综上可得 复制代码 1 f(n) - f(n-1) = f(n-1) 即 复制代码 1 f(n) = 2*f(n-1) 所以 f(n) 是一个等比数列 复制代码 1 2 3 public int JumpFloorII(int target) {     return (int) Math.pow(2, target - 1); } 11. 旋转数组的最小数字 NowCoder 题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 解题思路 将旋转数组对半分可以得到一个包含最小元素的新旋转数组，以及一个非递减排序的数组。新的旋转数组的数组元素是原数组的一半，从而将问题规模减少了一半，这种折半性质的算法的时间复杂度为 O(logN)（为了方便，这里将 log₂N 写为 logN）。 此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组，哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。 通过修改二分查找算法进行求解（l 代表 low，m 代表 mid，h 代表 high）： 当 nums[m] <= nums[h] 时，表示 [m, h] 区间内的数组是非递减数组，[l, m] 区间内的数组是旋转数组，此时令 h = m； 否则 [m + 1, h] 区间内的数组是旋转数组，令 l = m + 1。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public int minNumberInRotateArray(int[] nums) {     if (nums.length == 0)         return 0;     int l = 0, h = nums.length - 1;     while (l < h) {         int m = l + (h - l) / 2;         if (nums[m] <= nums[h])             h = m;         else             l = m + 1;     }     return nums[l]; } 如果数组元素允许重复，会出现一个特殊的情况：nums[l] == nums[m] == nums[h]，此时无法确定解在哪个区间，需要切换到顺序查找。例如对于数组 {1,1,1,0,1}，l、m 和 h 指向的数都为 1，此时无法知道最小数字 0 在哪个区间。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int minNumberInRotateArray(int[] nums) {     if (nums.length == 0)         return 0;     int l = 0, h = nums.length - 1;     while (l < h) {         int m = l + (h - l) / 2;         if (nums[l] == nums[m] && nums[m] == nums[h])             return minNumber(nums, l, h);         else if (nums[m] <= nums[h])             h = m;         else             l = m + 1;     }     return nums[l]; }   private int minNumber(int[] nums, int l, int h) {     for (int i = l; i < h; i++)         if (nums[i] > nums[i + 1])             return nums[i + 1];     return nums[l]; } 12. 矩阵中的路径 NowCoder 题目描述 判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如下面的矩阵包含了一条 bfce 路径。 解题思路 使用回溯法（backtracking）进行求解，它是一种暴力搜索方法，通过搜索所有可能的结果来求解问题。回溯法在一次搜索结束时需要进行回溯（回退），将这一次搜索过程中设置的状态进行清除，从而开始一次新的搜索过程。例如下图示例中，从 f 开始，下一步有 4 种搜索可能，如果先搜索 b，需要将 b 标记为已经使用，防止重复使用。在这一次搜索结束之后，需要将 b 的已经使用状态清除，并搜索 c。 本题的输入是数组而不是矩阵（二维数组），因此需要先将数组转换成矩阵。 复制代码 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 private final static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; private int rows; private int cols;   public boolean hasPath(char[] array, int rows, int cols, char[] str) {     if (rows == 0 || cols == 0) return false;     this.rows = rows;     this.cols = cols;     boolean[][] marked = new boolean[rows][cols];     char[][] matrix = buildMatrix(array);     for (int i = 0; i < rows; i++)         for (int j = 0; j < cols; j++)             if (backtracking(matrix, str, marked, 0, i, j))                 return true;       return false; }   private boolean backtracking(char[][] matrix, char[] str,                              boolean[][] marked, int pathLen, int r, int c) {       if (pathLen == str.length) return true;     if (r < 0 || r >= rows || c < 0 || c >= cols             || matrix[r][c] != str[pathLen] || marked[r][c]) {           return false;     }     marked[r][c] = true;     for (int[] n : next)         if (backtracking(matrix, str, marked, pathLen + 1, r + n[0], c + n[1]))             return true;     marked[r][c] = false;     return false; }   private char[][] buildMatrix(char[] array) {     char[][] matrix = new char[rows][cols];     for (int r = 0, idx = 0; r < rows; r++)         for (int c = 0; c < cols; c++)             matrix[r][c] = array[idx++];     return matrix; } 13. 机器人的运动范围 NowCoder 题目描述 地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动，每一次只能向左右上下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 例如，当 k 为 18 时，机器人能够进入方格 (35,37)，因为 3+5+3+7=18。但是，它不能进入方格 (35,38)，因为 3+5+3+8=19。请问该机器人能够达到多少个格子？ 解题思路 使用深度优先搜索（Depth First Search，DFS）方法进行求解。回溯是深度优先搜索的一种特例，它在一次搜索过程中需要设置一些本次搜索过程的局部状态，并在本次搜索结束之后清除状态。而普通的深度优先搜索并不需要使用这些局部状态，虽然还是有可能设置一些全局状态。 复制代码 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 private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; private int cnt = 0; private int rows; private int cols; private int threshold; private int[][] digitSum;   public int movingCount(int threshold, int rows, int cols) {     this.rows = rows;     this.cols = cols;     this.threshold = threshold;     initDigitSum();     boolean[][] marked = new boolean[rows][cols];     dfs(marked, 0, 0);     return cnt; }   private void dfs(boolean[][] marked, int r, int c) {     if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c])         return;     marked[r][c] = true;     if (this.digitSum[r][c] > this.threshold)         return;     cnt++;     for (int[] n : next)         dfs(marked, r + n[0], c + n[1]); }   private void initDigitSum() {     int[] digitSumOne = new int[Math.max(rows, cols)];     for (int i = 0; i < digitSumOne.length; i++) {         int n = i;         while (n > 0) {             digitSumOne[i] += n % 10;             n /= 10;         }     }     this.digitSum = new int[rows][cols];     for (int i = 0; i < this.rows; i++)         for (int j = 0; j < this.cols; j++)             this.digitSum[i][j] = digitSumOne[i] + digitSumOne[j]; } 14. 剪绳子 Leetcode 题目描述 把一根绳子剪成多段，并且使得每段的长度乘积最大。 复制代码 1 2 3 4 5 n = 2 return 1 (2 = 1 + 1)   n = 10 return 36 (10 = 3 + 3 + 4) 解题思路 贪心 尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。 证明：当 n >= 5 时，3(n - 3) - n = 2n - 9 > 0，且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下，将绳子剪成一段为 2 或者 3，得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0，所以剪成一段长度为 3 比长度为 2 得到的乘积更大。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public int integerBreak(int n) {     if (n < 2)         return 0;     if (n == 2)         return 1;     if (n == 3)         return 2;     int timesOf3 = n / 3;     if (n - timesOf3 * 3 == 1)         timesOf3--;     int timesOf2 = (n - timesOf3 * 3) / 2;     return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2)); } 动态规划 复制代码 1 2 3 4 5 6 7 8 public int integerBreak(int n) {     int[] dp = new int[n + 1];     dp[1] = 1;     for (int i = 2; i <= n; i++)         for (int j = 1; j < i; j++)             dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));     return dp[n]; } 15. 二进制中 1 的个数 NowCoder 题目描述 输入一个整数，输出该数二进制表示中 1 的个数。 n&(n-1) 该位运算去除 n 的位级表示中最低的那一位。 复制代码 1 2 3 n       : 10110100 n-1     : 10110011 n&(n-1) : 10110000 时间复杂度：O(M)，其中 M 表示 1 的个数。 复制代码 1 2 3 4 5 6 7 8 public int NumberOf1(int n) {     int cnt = 0;     while (n != 0) {         cnt++;         n &= (n - 1);     }     return cnt; } Integer.bitCount() 复制代码 1 2 3 public int NumberOf1(int n) {     return Integer.bitCount(n); } 16. 数值的整数次方 NowCoder 题目描述 给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent，求 base 的 exponent 次方。 解题思路 下面的讨论中 x 代表 base，n 代表 exponent。 x^n=\left\{\begin{array}{rcl}(x*x)^{n/2}&&{n\%2=0}\\x*(x*x)^{n/2}&&{n\%2=1}\end{array}\right. x n ={ (x∗x) n/2 x∗(x∗x) n/2 ​ ​ n%2=0 n%2=1 ​ 因为 (x*x)^n/2 可以通过递归求解，并且每次递归 n 都减小一半，因此整个算法的时间复杂度为 O(logN)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public double Power(double base, int exponent) {     if (exponent == 0)         return 1;     if (exponent == 1)         return base;     boolean isNegative = false;     if (exponent < 0) {         exponent = -exponent;         isNegative = true;     }     double pow = Power(base * base, exponent / 2);     if (exponent % 2 != 0)         pow = pow * base;     return isNegative ? 1 / pow : pow; } 17. 打印从 1 到最大的 n 位数 题目描述 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。 解题思路 由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 char 数组进行存储。 使用回溯法得到所有的数。 复制代码 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 public void print1ToMaxOfNDigits(int n) {     if (n <= 0)         return;     char[] number = new char[n];     print1ToMaxOfNDigits(number, 0); }   private void print1ToMaxOfNDigits(char[] number, int digit) {     if (digit == number.length) {         printNumber(number);         return;     }     for (int i = 0; i < 10; i++) {         number[digit] = (char) (i + '0');         print1ToMaxOfNDigits(number, digit + 1);     } }   private void printNumber(char[] number) {     int index = 0;     while (index < number.length && number[index] == '0')         index++;     while (index < number.length)         System.out.print(number[index++]);     System.out.println(); } 18.1 在 O(1) 时间内删除链表节点 解题思路 ① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。 ② 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。 综上，如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public ListNode deleteNode(ListNode head, ListNode tobeDelete) {     if (head == null || tobeDelete == null)         return null;     if (tobeDelete.next != null) {         // 要删除的节点不是尾节点         ListNode next = tobeDelete.next;         tobeDelete.val = next.val;         tobeDelete.next = next.next;     } else {         if (head == tobeDelete)              // 只有一个节点             head = null;         else {             ListNode cur = head;             while (cur.next != tobeDelete)                 cur = cur.next;             cur.next = null;         }     }     return head; } 18.2 删除链表中重复的结点 NowCoder 题目描述 解题描述 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public ListNode deleteDuplication(ListNode pHead) {     if (pHead == null || pHead.next == null)         return pHead;     ListNode next = pHead.next;     if (pHead.val == next.val) {         while (next != null && pHead.val == next.val)             next = next.next;         return deleteDuplication(next);     } else {         pHead.next = deleteDuplication(pHead.next);         return pHead;     } } 19. 正则表达式匹配 NowCoder 题目描述 请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而 '*' 表示它前面的字符可以出现任意次（包含 0 次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，但是与 "aa.a" 和 "ab*a" 均不匹配。 解题思路 应该注意到，'.' 是用来当做一个任意字符，而 '*' 是用来重复前面的字符。这两个的作用不同，不能把 '.' 的作用和 '*' 进行类比，从而把它当成重复前面字符一次。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public boolean match(char[] str, char[] pattern) {       int m = str.length, n = pattern.length;     boolean[][] dp = new boolean[m + 1][n + 1];       dp[0][0] = true;     for (int i = 1; i <= n; i++)         if (pattern[i - 1] == '*')             dp[0][i] = dp[0][i - 2];       for (int i = 1; i <= m; i++)         for (int j = 1; j <= n; j++)             if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')                 dp[i][j] = dp[i - 1][j - 1];             else if (pattern[j - 1] == '*')                 if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {                     dp[i][j] |= dp[i][j - 1]; // a* counts as single a                     dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a                     dp[i][j] |= dp[i][j - 2]; // a* counts as empty                 } else                     dp[i][j] = dp[i][j - 2];   // a* only counts as empty       return dp[m][n]; } 20. 表示数值的字符串 NowCoder 题目描述 复制代码 1 2 3 4 5 6 7 true   "+100" "5e2" "-123" "3.1416" "-1E-16" 复制代码 1 2 3 4 5 6 7 false   "12e" "1a3.14" "1.2.3" "+-5" "12e+4.3" 解题思路 使用正则表达式进行匹配。 复制代码 1 2 3 4 5 6 7 8 []  ： 字符集合 ()  ： 分组 ?   ： 重复 0 ~ 1 次 +   ： 重复 1 ~ n 次 *   ： 重复 0 ~ n 次 .   ： 任意字符 \\. ： 转义后的 . \\d ： 数字 复制代码 1 2 3 4 5 public boolean isNumeric(char[] str) {     if (str == null || str.length == 0)         return false;     return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?"); } 21. 调整数组顺序使奇数位于偶数前面 NowCoder 题目描述 需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。 解题思路 方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public void reOrderArray(int[] nums) {     // 奇数个数     int oddCnt = 0;     for (int x : nums)         if (!isEven(x))             oddCnt++;     int[] copy = nums.clone();     int i = 0, j = oddCnt;     for (int num : copy) {         if (num % 2 == 1)             nums[i++] = num;         else             nums[j++] = num;     } }   private boolean isEven(int x) {     return x % 2 == 0; } 方法二：使用冒泡思想，每次都当前偶数上浮到当前最右边。时间复杂度 O(N²)，空间复杂度 O(1)，时间换空间。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public void reOrderArray(int[] nums) {     int N = nums.length;     for (int i = N - 1; i > 0; i--) {         for (int j = 0; j < i; j++) {             if (isEven(nums[j]) && !isEven(nums[j + 1])) {                 swap(nums, j, j + 1);             }         }     } }   private boolean isEven(int x) {     return x % 2 == 0; }   private void swap(int[] nums, int i, int j) {     int t = nums[i];     nums[i] = nums[j];     nums[j] = t; } 22. 链表中倒数第 K 个结点 NowCoder 解题思路 设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public ListNode FindKthToTail(ListNode head, int k) {     if (head == null)         return null;     ListNode P1 = head;     while (P1 != null && k-- > 0)         P1 = P1.next;     if (k > 0)         return null;     ListNode P2 = head;     while (P1 != null) {         P1 = P1.next;         P2 = P2.next;     }     return P2; } 23. 链表中环的入口结点 NowCoder 题目描述 一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。 解题思路 使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。假设相遇点在下图的 z1 位置，此时 fast 移动的节点数为 x+2y+z，slow 为 x+y，由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。 在相遇点，slow 要到环的入口点还需要移动 z 个节点，如果让 fast 重新从头开始移动，并且速度变为每次移动一个节点，那么它到环入口点还需要移动 x 个节点。在上面已经推导出 x=z，因此 fast 和 slow 将在环入口点相遇。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public ListNode EntryNodeOfLoop(ListNode pHead) {     if (pHead == null || pHead.next == null)         return null;     ListNode slow = pHead, fast = pHead;     do {         fast = fast.next.next;         slow = slow.next;     } while (slow != fast);     fast = pHead;     while (slow != fast) {         slow = slow.next;         fast = fast.next;     }     return slow; } 24. 反转链表 NowCoder 解题思路 递归 复制代码 1 2 3 4 5 6 7 8 9 public ListNode ReverseList(ListNode head) {     if (head == null || head.next == null)         return head;     ListNode next = head.next;     head.next = null;     ListNode newHead = ReverseList(next);     next.next = head;     return newHead; } 迭代 使用头插法。 复制代码 1 2 3 4 5 6 7 8 9 10 public ListNode ReverseList(ListNode head) {     ListNode newList = new ListNode(-1);     while (head != null) {         ListNode next = head.next;         head.next = newList.next;         newList.next = head;         head = next;     }     return newList.next; } 25. 合并两个排序的链表 NowCoder 题目描述 解题思路 递归 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public ListNode Merge(ListNode list1, ListNode list2) {     if (list1 == null)         return list2;     if (list2 == null)         return list1;     if (list1.val <= list2.val) {         list1.next = Merge(list1.next, list2);         return list1;     } else {         list2.next = Merge(list1, list2.next);         return list2;     } } 迭代 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public ListNode Merge(ListNode list1, ListNode list2) {     ListNode head = new ListNode(-1);     ListNode cur = head;     while (list1 != null && list2 != null) {         if (list1.val <= list2.val) {             cur.next = list1;             list1 = list1.next;         } else {             cur.next = list2;             list2 = list2.next;         }         cur = cur.next;     }     if (list1 != null)         cur.next = list1;     if (list2 != null)         cur.next = list2;     return head.next; } 26. 树的子结构 NowCoder 题目描述 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean HasSubtree(TreeNode root1, TreeNode root2) {     if (root1 == null || root2 == null)         return false;     return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); }   private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {     if (root2 == null)         return true;     if (root1 == null)         return false;     if (root1.val != root2.val)         return false;     return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right); } 27. 二叉树的镜像 NowCoder 题目描述 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public void Mirror(TreeNode root) {     if (root == null)         return;     swap(root);     Mirror(root.left);     Mirror(root.right); }   private void swap(TreeNode root) {     TreeNode t = root.left;     root.left = root.right;     root.right = t; } 28 对称的二叉树 NowCoder 题目描述 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 boolean isSymmetrical(TreeNode pRoot) {     if (pRoot == null)         return true;     return isSymmetrical(pRoot.left, pRoot.right); }   boolean isSymmetrical(TreeNode t1, TreeNode t2) {     if (t1 == null && t2 == null)         return true;     if (t1 == null || t2 == null)         return false;     if (t1.val != t2.val)         return false;     return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left); } 29. 顺时针打印矩阵 NowCoder 题目描述 下图的矩阵顺时针打印结果为：1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public ArrayList<Integer> printMatrix(int[][] matrix) {     ArrayList<Integer> ret = new ArrayList<>();     int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;     while (r1 <= r2 && c1 <= c2) {         for (int i = c1; i <= c2; i++)             ret.add(matrix[r1][i]);         for (int i = r1 + 1; i <= r2; i++)             ret.add(matrix[i][c2]);         if (r1 != r2)             for (int i = c2 - 1; i >= c1; i--)                 ret.add(matrix[r2][i]);         if (c1 != c2)             for (int i = r2 - 1; i > r1; i--)                 ret.add(matrix[i][c1]);         r1++; r2--; c1++; c2--;     }     return ret; } 30. 包含 min 函数的栈 NowCoder 题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的 min 函数。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private Stack<Integer> dataStack = new Stack<>(); private Stack<Integer> minStack = new Stack<>();   public void push(int node) {     dataStack.push(node);     minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node)); }   public void pop() {     dataStack.pop();     minStack.pop(); }   public int top() {     return dataStack.peek(); }   public int min() {     return minStack.peek(); } 31. 栈的压入、弹出序列 NowCoder 题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。 例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。 解题思路 使用一个栈来模拟压入弹出操作。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {     int n = pushSequence.length;     Stack<Integer> stack = new Stack<>();     for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {         stack.push(pushSequence[pushIndex]);         while (popIndex < n && !stack.isEmpty()                 && stack.peek() == popSequence[popIndex]) {             stack.pop();             popIndex++;         }     }     return stack.isEmpty(); } 32.1 从上往下打印二叉树 NowCoder 题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 例如，以下二叉树层次遍历的结果为：1,2,3,4,5,6,7 解题思路 使用队列来进行层次遍历。 不需要使用两个队列分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {     Queue<TreeNode> queue = new LinkedList<>();     ArrayList<Integer> ret = new ArrayList<>();     queue.add(root);     while (!queue.isEmpty()) {         int cnt = queue.size();         while (cnt-- > 0) {             TreeNode t = queue.poll();             if (t == null)                 continue;             ret.add(t.val);             queue.add(t.left);             queue.add(t.right);         }     }     return ret; } 32.2 把二叉树打印成多行 NowCoder 题目描述 和上题几乎一样。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {     ArrayList<ArrayList<Integer>> ret = new ArrayList<>();     Queue<TreeNode> queue = new LinkedList<>();     queue.add(pRoot);     while (!queue.isEmpty()) {         ArrayList<Integer> list = new ArrayList<>();         int cnt = queue.size();         while (cnt-- > 0) {             TreeNode node = queue.poll();             if (node == null)                 continue;             list.add(node.val);             queue.add(node.left);             queue.add(node.right);         }         if (list.size() != 0)             ret.add(list);     }     return ret; } 32.3 按之字形顺序打印二叉树 NowCoder 题目描述 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {     ArrayList<ArrayList<Integer>> ret = new ArrayList<>();     Queue<TreeNode> queue = new LinkedList<>();     queue.add(pRoot);     boolean reverse = false;     while (!queue.isEmpty()) {         ArrayList<Integer> list = new ArrayList<>();         int cnt = queue.size();         while (cnt-- > 0) {             TreeNode node = queue.poll();             if (node == null)                 continue;             list.add(node.val);             queue.add(node.left);             queue.add(node.right);         }         if (reverse)             Collections.reverse(list);         reverse = !reverse;         if (list.size() != 0)             ret.add(list);     }     return ret; } 33. 二叉搜索树的后序遍历序列 NowCoder 题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。 例如，下图是后序遍历序列 1,3,2 所对应的二叉搜索树。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public boolean VerifySquenceOfBST(int[] sequence) {     if (sequence == null || sequence.length == 0)         return false;     return verify(sequence, 0, sequence.length - 1); }   private boolean verify(int[] sequence, int first, int last) {     if (last - first <= 1)         return true;     int rootVal = sequence[last];     int cutIndex = first;     while (cutIndex < last && sequence[cutIndex] <= rootVal)         cutIndex++;     for (int i = cutIndex; i < last; i++)         if (sequence[i] < rootVal)             return false;     return verify(sequence, first, cutIndex - 1) && verify(sequence, cutIndex, last - 1); } 34. 二叉树中和为某一值的路径 NowCoder 题目描述 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 下图的二叉树有两条和为 22 的路径：10, 5, 7 和 10, 12 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();   public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {     backtracking(root, target, new ArrayList<>());     return ret; }   private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {     if (node == null)         return;     path.add(node.val);     target -= node.val;     if (target == 0 && node.left == null && node.right == null) {         ret.add(new ArrayList<>(path));     } else {         backtracking(node.left, target, path);         backtracking(node.right, target, path);     }     path.remove(path.size() - 1); } 35. 复杂链表的复制 NowCoder 题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。 复制代码 1 2 3 4 5 6 7 8 9 public class RandomListNode {     int label;     RandomListNode next = null;     RandomListNode random = null;       RandomListNode(int label) {         this.label = label;     } } 解题思路 第一步，在每个节点的后面插入复制的节点。 第二步，对复制节点的 random 链接进行赋值。 第三步，拆分。 复制代码 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 public RandomListNode Clone(RandomListNode pHead) {     if (pHead == null)         return null;     // 插入新节点     RandomListNode cur = pHead;     while (cur != null) {         RandomListNode clone = new RandomListNode(cur.label);         clone.next = cur.next;         cur.next = clone;         cur = clone.next;     }     // 建立 random 链接     cur = pHead;     while (cur != null) {         RandomListNode clone = cur.next;         if (cur.random != null)             clone.random = cur.random.next;         cur = clone.next;     }     // 拆分     cur = pHead;     RandomListNode pCloneHead = pHead.next;     while (cur.next != null) {         RandomListNode next = cur.next;         cur.next = next.next;         cur = next;     }     return pCloneHead; } 36. 二叉搜索树与双向链表 NowCoder 题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private TreeNode pre = null; private TreeNode head = null;   public TreeNode Convert(TreeNode root) {     inOrder(root);     return head; }   private void inOrder(TreeNode node) {     if (node == null)         return;     inOrder(node.left);     node.left = pre;     if (pre != null)         pre.right = node;     pre = node;     if (head == null)         head = node;     inOrder(node.right); } 37. 序列化二叉树 NowCoder 题目描述 请实现两个函数，分别用来序列化和反序列化二叉树。 解题思路 复制代码 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 private String deserializeStr;   public String Serialize(TreeNode root) {     if (root == null)         return "#";     return root.val + " " + Serialize(root.left) + " " + Serialize(root.right); }   public TreeNode Deserialize(String str) {     deserializeStr = str;     return Deserialize(); }   private TreeNode Deserialize() {     if (deserializeStr.length() == 0)         return null;     int index = deserializeStr.indexOf(" ");     String node = index == -1 ? deserializeStr : deserializeStr.substring(0, index);     deserializeStr = index == -1 ? "" : deserializeStr.substring(index + 1);     if (node.equals("#"))         return null;     int val = Integer.valueOf(node);     TreeNode t = new TreeNode(val);     t.left = Deserialize();     t.right = Deserialize();     return t; } 38. 字符串的排列 NowCoder 题目描述 输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。 解题思路 复制代码 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 private ArrayList<String> ret = new ArrayList<>();   public ArrayList<String> Permutation(String str) {     if (str.length() == 0)         return ret;     char[] chars = str.toCharArray();     Arrays.sort(chars);     backtracking(chars, new boolean[chars.length], new StringBuilder());     return ret; }   private void backtracking(char[] chars, boolean[] hasUsed, StringBuilder s) {     if (s.length() == chars.length) {         ret.add(s.toString());         return;     }     for (int i = 0; i < chars.length; i++) {         if (hasUsed[i])             continue;         if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1]) /* 保证不重复 */             continue;         hasUsed[i] = true;         s.append(chars[i]);         backtracking(chars, hasUsed, s);         s.deleteCharAt(s.length() - 1);         hasUsed[i] = false;     } } 39. 数组中出现次数超过一半的数字 NowCoder 解题思路 多数投票问题，可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 O(N)。 使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素相等时，令 cnt++，否则令 cnt--。如果前面查找了 i 个元素，且 cnt == 0，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int MoreThanHalfNum_Solution(int[] nums) {     int majority = nums[0];     for (int i = 1, cnt = 1; i < nums.length; i++) {         cnt = nums[i] == majority ? cnt + 1 : cnt - 1;         if (cnt == 0) {             majority = nums[i];             cnt = 1;         }     }     int cnt = 0;     for (int val : nums)         if (val == majority)             cnt++;     return cnt > nums.length / 2 ? majority : 0; } 40. 最小的 K 个数 NowCoder 解题思路 快速选择 复杂度：O(N) + O(1) 只有当允许修改数组元素时才可以使用 快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素，这种找第 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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {     ArrayList<Integer> ret = new ArrayList<>();     if (k > nums.length || k <= 0)         return ret;     findKthSmallest(nums, k - 1);     /* findKthSmallest 会改变数组，使得前 k 个数都是最小的 k 个数 */     for (int i = 0; i < k; i++)         ret.add(nums[i]);     return ret; }   public void findKthSmallest(int[] nums, int k) {     int l = 0, h = nums.length - 1;     while (l < h) {         int j = partition(nums, l, h);         if (j == k)             break;         if (j > k)             h = j - 1;         else             l = j + 1;     } }   private int partition(int[] nums, int l, int h) {     int p = nums[l];     /* 切分元素 */     int i = l, j = h + 1;     while (true) {         while (i != h && nums[++i] < p) ;         while (j != l && nums[--j] > p) ;         if (i >= j)             break;         swap(nums, i, j);     }     swap(nums, l, j);     return j; }   private void swap(int[] nums, int i, int j) {     int t = nums[i];     nums[i] = nums[j];     nums[j] = t; } 大小为 K 的最小堆 复杂度：O(NlogK) + O(K) 特别适合处理海量数据 应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。 维护一个大小为 K 的最小堆过程如下：在添加一个元素之后，如果大顶堆的大小大于 K，那么需要将大顶堆的堆顶元素去除。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {     if (k > nums.length || k <= 0)         return new ArrayList<>();     PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);     for (int num : nums) {         maxHeap.add(num);         if (maxHeap.size() > k)             maxHeap.poll();     }     return new ArrayList<>(maxHeap); } 41.1 数据流中的中位数 NowCoder 题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 解题思路 复制代码 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 /* 大顶堆，存储左半边元素 */ private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1); /* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */ private PriorityQueue<Integer> right = new PriorityQueue<>(); /* 当前数据流读入的元素个数 */ private int N = 0;   public void Insert(Integer val) {     /* 插入要保证两个堆存于平衡状态 */     if (N % 2 == 0) {         /* N 为偶数的情况下插入到右半边。          * 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，          * 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */         left.add(val);         right.add(left.poll());     } else {         right.add(val);         left.add(right.poll());     }     N++; }   public Double GetMedian() {     if (N % 2 == 0)         return (left.peek() + right.peek()) / 2.0;     else         return (double) right.peek(); } 41.2 字符流中第一个不重复的字符 NowCoder 题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时，第一个只出现一次的字符是 "l"。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 private int[] cnts = new int[256]; private Queue<Character> queue = new LinkedList<>();   public void Insert(char ch) {     cnts[ch]++;     queue.add(ch);     while (!queue.isEmpty() && cnts[queue.peek()] > 1)         queue.poll(); }   public char FirstAppearingOnce() {     return queue.isEmpty() ? '#' : queue.peek(); } 42. 连续子数组的最大和 NowCoder 题目描述 {6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 public int FindGreatestSumOfSubArray(int[] nums) {     if (nums == null || nums.length == 0)         return 0;     int greatestSum = Integer.MIN_VALUE;     int sum = 0;     for (int val : nums) {         sum = sum <= 0 ? val : sum + val;         greatestSum = Math.max(greatestSum, sum);     }     return greatestSum; } 43. 从 1 到 n 整数中 1 出现的次数 NowCoder 解题思路 复制代码 1 2 3 4 5 6 7 8 public int NumberOf1Between1AndN_Solution(int n) {     int cnt = 0;     for (int m = 1; m <= n; m *= 10) {         int a = n / m, b = n % m;         cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);     }     return cnt; } Leetcode : 233. Number of Digit One 44. 数字序列中的某一位数字 题目描述 数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。 解题思路 复制代码 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 public int getDigitAtIndex(int index) {     if (index < 0)         return -1;     int place = 1;  // 1 表示个位，2 表示 十位...     while (true) {         int amount = getAmountOfPlace(place);         int totalAmount = amount * place;         if (index < totalAmount)             return getDigitAtIndex(index, place);         index -= totalAmount;         place++;     } }   /**  * place 位数的数字组成的字符串长度  * 10, 90, 900, ...  */ private int getAmountOfPlace(int place) {     if (place == 1)         return 10;     return (int) Math.pow(10, place - 1) * 9; }   /**  * place 位数的起始数字  * 0, 10, 100, ...  */ private int getBeginNumberOfPlace(int place) {     if (place == 1)         return 0;     return (int) Math.pow(10, place - 1); }   /**  * 在 place 位数组成的字符串中，第 index 个数  */ private int getDigitAtIndex(int index, int place) {     int beginNumber = getBeginNumberOfPlace(place);     int shiftNumber = index / place;     String number = (beginNumber + shiftNumber) + "";     int count = index % place;     return number.charAt(count) - '0'; } 45. 把数组排成最小的数 NowCoder 题目描述 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 {3，32，321}，则打印出这三个数字能排成的最小数字为 321323。 解题思路 可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public String PrintMinNumber(int[] numbers) {     if (numbers == null || numbers.length == 0)         return "";     int n = numbers.length;     String[] nums = new String[n];     for (int i = 0; i < n; i++)         nums[i] = numbers[i] + "";     Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));     String ret = "";     for (String str : nums)         ret += str;     return ret; } 46. 把数字翻译成字符串 Leetcode 题目描述 给定一个数字，按照如下规则翻译成字符串：1 翻译成“a”，2 翻译成“b”... 26 翻译成“z”。一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 abbeh，lbeh，aveh，abyh，lyh。实现一个函数，用来计算一个数字有多少种不同的翻译方法。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int numDecodings(String s) {     if (s == null || s.length() == 0)         return 0;     int n = s.length();     int[] dp = new int[n + 1];     dp[0] = 1;     dp[1] = s.charAt(0) == '0' ? 0 : 1;     for (int i = 2; i <= n; i++) {         int one = Integer.valueOf(s.substring(i - 1, i));         if (one != 0)             dp[i] += dp[i - 1];         if (s.charAt(i - 2) == '0')             continue;         int two = Integer.valueOf(s.substring(i - 2, i));         if (two <= 26)             dp[i] += dp[i - 2];     }     return dp[n]; } 47. 礼物的最大价值 NowCoder 题目描述 在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘 复制代码 1 2 3 4 1    10   3    8 12   2    9    6 5    7    4    11 3    7    16   5 礼物的最大价值为 1+12+5+7+7+16+5=53。 解题思路 应该用动态规划求解，而不是深度优先搜索，深度优先搜索过于复杂，不是最优解。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int getMost(int[][] values) {     if (values == null || values.length == 0 || values[0].length == 0)         return 0;     int n = values[0].length;     int[] dp = new int[n];     for (int[] value : values) {         dp[0] += value[0];         for (int i = 1; i < n; i++)             dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];     }     return dp[n - 1]; } 48. 最长不含重复字符的子字符串 题目描述 输入一个字符串（只包含 a~z 的字符），求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int longestSubStringWithoutDuplication(String str) {     int curLen = 0;     int maxLen = 0;     int[] preIndexs = new int[26];     Arrays.fill(preIndexs, -1);     for (int curI = 0; curI < str.length(); curI++) {         int c = str.charAt(curI) - 'a';         int preI = preIndexs[c];         if (preI == -1 || curI - preI > curLen) {             curLen++;         } else {             maxLen = Math.max(maxLen, curLen);             curLen = curI - preI;         }         preIndexs[c] = curI;     }     maxLen = Math.max(maxLen, curLen);     return maxLen; } 49. 丑数 NowCoder 题目描述 把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public int GetUglyNumber_Solution(int N) {     if (N <= 6)         return N;     int i2 = 0, i3 = 0, i5 = 0;     int[] dp = new int[N];     dp[0] = 1;     for (int i = 1; i < N; i++) {         int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;         dp[i] = Math.min(next2, Math.min(next3, next5));         if (dp[i] == next2)             i2++;         if (dp[i] == next3)             i3++;         if (dp[i] == next5)             i5++;     }     return dp[N - 1]; } 50. 第一个只出现一次的字符位置 NowCoder 题目描述 在一个字符串中找到第一个只出现一次的字符，并返回它的位置。 复制代码 1 2 Input: abacc Output: b 解题思路 最直观的解法是使用 HashMap 对出现次数进行统计，但是考虑到要统计的字符范围有限，因此可以使用整型数组代替 HashMap，从而将空间复杂度由 O(N) 降低为 O(1)。 复制代码 1 2 3 4 5 6 7 8 9 public int FirstNotRepeatingChar(String str) {     int[] cnts = new int[256];     for (int i = 0; i < str.length(); i++)         cnts[str.charAt(i)]++;     for (int i = 0; i < str.length(); i++)         if (cnts[str.charAt(i)] == 1)             return i;     return -1; } 以上实现的空间复杂度还不是最优的。考虑到只需要找到只出现一次的字符，那么需要统计的次数信息只有 0,1,更大，使用两个比特位就能存储这些信息。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int FirstNotRepeatingChar2(String str) {     BitSet bs1 = new BitSet(256);     BitSet bs2 = new BitSet(256);     for (char c : str.toCharArray()) {         if (!bs1.get(c) && !bs2.get(c))             bs1.set(c);     // 0 0 -> 0 1         else if (bs1.get(c) && !bs2.get(c))             bs2.set(c);     // 0 1 -> 1 1     }     for (int i = 0; i < str.length(); i++) {         char c = str.charAt(i);         if (bs1.get(c) && !bs2.get(c))  // 0 1             return i;     }     return -1; } 51. 数组中的逆序对 NowCoder 题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 解题思路 复制代码 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 private long cnt = 0; private int[] tmp;  // 在这里声明辅助数组，而不是在 merge() 递归函数中声明   public int InversePairs(int[] nums) {     tmp = new int[nums.length];     mergeSort(nums, 0, nums.length - 1);     return (int) (cnt % 1000000007); }   private void mergeSort(int[] nums, int l, int h) {     if (h - l < 1)         return;     int m = l + (h - l) / 2;     mergeSort(nums, l, m);     mergeSort(nums, m + 1, h);     merge(nums, l, m, h); }   private void merge(int[] nums, int l, int m, int h) {     int i = l, j = m + 1, k = l;     while (i <= m || j <= h) {         if (i > m)             tmp[k] = nums[j++];         else if (j > h)             tmp[k] = nums[i++];         else if (nums[i] <= nums[j])             tmp[k] = nums[i++];         else {             tmp[k] = nums[j++];             this.cnt += m - i + 1;  // nums[i] > nums[j]，说明 nums[i...mid] 都大于 nums[j]         }         k++;     }     for (k = l; k <= h; k++)         nums[k] = tmp[k]; } 52. 两个链表的第一个公共结点 NowCoder 题目描述 解题思路 设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。 当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。 复制代码 1 2 3 4 5 6 7 8 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {     ListNode l1 = pHead1, l2 = pHead2;     while (l1 != l2) {         l1 = (l1 == null) ? pHead2 : l1.next;         l2 = (l2 == null) ? pHead1 : l2.next;     }     return l1; } 53. 数字在排序数组中出现的次数 NowCoder 题目描述 复制代码 1 2 3 4 5 6 Input: nums = 1, 2, 3, 3, 3, 3, 4, 6 K = 3   Output: 4 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int GetNumberOfK(int[] nums, int K) {     int first = binarySearch(nums, K);     int last = binarySearch(nums, K + 1);     return (first == nums.length || nums[first] != K) ? 0 : last - first; }   private int binarySearch(int[] nums, int K) {     int l = 0, h = nums.length;     while (l < h) {         int m = l + (h - l) / 2;         if (nums[m] >= K)             h = m;         else             l = m + 1;     }     return l; } 54. 二叉查找树的第 K 个结点 NowCoder 解题思路 利用二叉查找树中序遍历有序的特点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 private TreeNode ret; private int cnt = 0;   public TreeNode KthNode(TreeNode pRoot, int k) {     inOrder(pRoot, k);     return ret; }   private void inOrder(TreeNode root, int k) {     if (root == null || cnt >= k)         return;     inOrder(root.left, k);     cnt++;     if (cnt == k)         ret = root;     inOrder(root.right, k); } 55.1 二叉树的深度 NowCoder 题目描述 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 解题思路 复制代码 1 2 3 public int TreeDepth(TreeNode root) {     return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right)); } 55.2 平衡二叉树 NowCoder 题目描述 平衡二叉树左右子树高度差不超过 1。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 private boolean isBalanced = true;   public boolean IsBalanced_Solution(TreeNode root) {     height(root);     return isBalanced; }   private int height(TreeNode root) {     if (root == null || !isBalanced)         return 0;     int left = height(root.left);     int right = height(root.right);     if (Math.abs(left - right) > 1)         isBalanced = false;     return 1 + Math.max(left, right); } 56. 数组中只出现一次的数字 NowCoder 题目描述 一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。 解题思路 两个不相等的元素在位级表示上必定会有一位存在不同，将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。 diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public void FindNumsAppearOnce(int[] nums, int num1[], int num2[]) {     int diff = 0;     for (int num : nums)         diff ^= num;     diff &= -diff;     for (int num : nums) {         if ((num & diff) == 0)             num1[0] ^= num;         else             num2[0] ^= num;     } } 57.1 和为 S 的两个数字 NowCoder 题目描述 输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是 S。如果有多对数字的和等于 S，输出两个数的乘积最小的。 解题思路 使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。 如果两个指针指向元素的和 sum == target，那么得到要求的结果； 如果 sum > target，移动较大的元素，使 sum 变小一些； 如果 sum < target，移动较小的元素，使 sum 变大一些。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {     int i = 0, j = array.length - 1;     while (i < j) {         int cur = array[i] + array[j];         if (cur == sum)             return new ArrayList<>(Arrays.asList(array[i], array[j]));         if (cur < sum)             i++;         else             j--;     }     return new ArrayList<>(); } 57.2 和为 S 的连续正数序列 NowCoder 题目描述 输出所有和为 S 的连续正数序列。 例如和为 100 的连续序列有： 复制代码 1 2 [9, 10, 11, 12, 13, 14, 15, 16] [18, 19, 20, 21, 22]。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {     ArrayList<ArrayList<Integer>> ret = new ArrayList<>();     int start = 1, end = 2;     int curSum = 3;     while (end < sum) {         if (curSum > sum) {             curSum -= start;             start++;         } else if (curSum < sum) {             end++;             curSum += end;         } else {             ArrayList<Integer> list = new ArrayList<>();             for (int i = start; i <= end; i++)                 list.add(i);             ret.add(list);             curSum -= start;             start++;             end++;             curSum += end;         }     }     return ret; } 58.1 翻转单词顺序列 NowCoder 题目描述 复制代码 1 2 3 4 5 Input: "I am a student."   Output: "student. a am I" 解题思路 题目应该有一个隐含条件，就是不能用额外的空间。虽然 Java 的题目输入参数为 String 类型，需要先创建一个字符数组使得空间复杂度为 O(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 public String ReverseSentence(String str) {     int n = str.length();     char[] chars = str.toCharArray();     int i = 0, j = 0;     while (j <= n) {         if (j == n || chars[j] == ' ') {             reverse(chars, i, j - 1);             i = j + 1;         }         j++;     }     reverse(chars, 0, n - 1);     return new String(chars); }   private void reverse(char[] c, int i, int j) {     while (i < j)         swap(c, i++, j--); }   private void swap(char[] c, int i, int j) {     char t = c[i];     c[i] = c[j];     c[j] = t; } 58.2 左旋转字符串 NowCoder 题目描述 复制代码 1 2 3 4 5 6 Input: S="abcXYZdef" K=3   Output: "XYZdefabc" 解题思路 先将 "abc" 和 "XYZdef" 分别翻转，得到 "cbafedZYX"，然后再把整个字符串翻转得到 "XYZdefabc"。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public String LeftRotateString(String str, int n) {     if (n >= str.length())         return str;     char[] chars = str.toCharArray();     reverse(chars, 0, n - 1);     reverse(chars, n, chars.length - 1);     reverse(chars, 0, chars.length - 1);     return new String(chars); }   private void reverse(char[] chars, int i, int j) {     while (i < j)         swap(chars, i++, j--); }   private void swap(char[] chars, int i, int j) {     char t = chars[i];     chars[i] = chars[j];     chars[j] = t; } 59. 滑动窗口的最大值 NowCoder 题目描述 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。 例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public ArrayList<Integer> maxInWindows(int[] num, int size) {     ArrayList<Integer> ret = new ArrayList<>();     if (size > num.length || size < 1)         return ret;     PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);  /* 大顶堆 */     for (int i = 0; i < size; i++)         heap.add(num[i]);     ret.add(heap.peek());     for (int i = 0, j = i + size; j < num.length; i++, j++) {            /* 维护一个大小为 size 的大顶堆 */         heap.remove(num[i]);         heap.add(num[j]);         ret.add(heap.peek());     }     return ret; } 60. n 个骰子的点数 Lintcode 题目描述 把 n 个骰子仍在地上，求点数和为 s 的概率。 解题思路 动态规划 使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。 空间复杂度：O(N²) 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public List<Map.Entry<Integer, Double>> dicesSum(int n) {     final int face = 6;     final int pointNum = face * n;     long[][] dp = new long[n + 1][pointNum + 1];       for (int i = 1; i <= face; i++)         dp[1][i] = 1;       for (int i = 2; i <= n; i++)         for (int j = i; j <= pointNum; j++)     /* 使用 i 个骰子最小点数为 i */             for (int k = 1; k <= face && k <= j; k++)                 dp[i][j] += dp[i - 1][j - k];       final double totalNum = Math.pow(6, n);     List<Map.Entry<Integer, Double>> ret = new ArrayList<>();     for (int i = n; i <= pointNum; i++)         ret.add(new AbstractMap.SimpleEntry<>(i, dp[n][i] / totalNum));       return ret; } 动态规划 + 旋转数组 空间复杂度：O(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 public List<Map.Entry<Integer, Double>> dicesSum(int n) {     final int face = 6;     final int pointNum = face * n;     long[][] dp = new long[2][pointNum + 1];       for (int i = 1; i <= face; i++)         dp[0][i] = 1;       int flag = 1;                                     /* 旋转标记 */     for (int i = 2; i <= n; i++, flag = 1 - flag) {         for (int j = 0; j <= pointNum; j++)             dp[flag][j] = 0;                          /* 旋转数组清零 */           for (int j = i; j <= pointNum; j++)             for (int k = 1; k <= face && k <= j; k++)                 dp[flag][j] += dp[1 - flag][j - k];     }       final double totalNum = Math.pow(6, n);     List<Map.Entry<Integer, Double>> ret = new ArrayList<>();     for (int i = n; i <= pointNum; i++)         ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));       return ret; } 61. 扑克牌顺子 NowCoder 题目描述 五张牌，其中大小鬼为癞子，牌面为 0。判断这五张牌是否能组成顺子。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public boolean isContinuous(int[] nums) {       if (nums.length < 5)         return false;       Arrays.sort(nums);       // 统计癞子数量     int cnt = 0;     for (int num : nums)         if (num == 0)             cnt++;       // 使用癞子去补全不连续的顺子     for (int i = cnt; i < nums.length - 1; i++) {         if (nums[i + 1] == nums[i])             return false;         cnt -= nums[i + 1] - nums[i] - 1;     }       return cnt >= 0; } 62. 圆圈中最后剩下的数 NowCoder 题目描述 让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0...m-1 报数 .... 这样下去 .... 直到剩下最后一个小朋友，可以不用表演。 解题思路 约瑟夫环，圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。 复制代码 1 2 3 4 5 6 7 public int LastRemaining_Solution(int n, int m) {     if (n == 0)     /* 特殊输入的处理 */         return -1;     if (n == 1)     /* 递归返回条件 */         return 0;     return (LastRemaining_Solution(n - 1, m) + m) % n; } 63. 股票的最大利润 Leetcode 题目描述 可以有一次买入和一次卖出，买入必须在前。求最大收益。 解题思路 使用贪心策略，假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public int maxProfit(int[] prices) {     if (prices == null || prices.length == 0)         return 0;     int soFarMin = prices[0];     int maxProfit = 0;     for (int i = 1; i < prices.length; i++) {         soFarMin = Math.min(soFarMin, prices[i]);         maxProfit = Math.max(maxProfit, prices[i] - soFarMin);     }     return maxProfit; } 64. 求 1+2+3+...+n NowCoder 题目描述 要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 A ? B : C。 解题思路 使用递归解法最重要的是指定返回条件，但是本题无法直接使用 if 语句来指定返回条件。 条件与 && 具有短路原则，即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。利用这一特性，将递归的返回条件取非然后作为 && 的第一个条件语句，递归的主体转换为第二个条件语句，那么当递归的返回条件为 true 的情况下就不会执行递归的主体部分，递归返回。 本题的递归返回条件为 n <= 0，取非后就是 n > 0；递归的主体部分为 sum += Sum_Solution(n - 1)，转换为条件语句后就是 (sum += Sum_Solution(n - 1)) > 0。 复制代码 1 2 3 4 5 public int Sum_Solution(int n) {     int sum = n;     boolean b = (n > 0) && ((sum += Sum_Solution(n - 1)) > 0);     return sum; } 65. 不用加减乘除做加法 NowCoder 题目描述 写一个函数，求两个整数之和，要求不得使用 +、-、*、/ 四则运算符号。 解题思路 a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。 递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。 复制代码 1 2 3 public int Add(int a, int b) {     return b == 0 ? a : Add(a ^ b, (a & b) << 1); } 66. 构建乘积数组 NowCoder 题目描述 给定一个数组 A[0, 1,..., n-1]，请构建一个数组 B[0, 1,..., n-1]，其中 B 中的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。要求不能使用除法。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 public int[] multiply(int[] A) {     int n = A.length;     int[] B = new int[n];     for (int i = 0, product = 1; i < n; product *= A[i], i++)       /* 从左往右累乘 */         B[i] = product;     for (int i = n - 1, product = 1; i >= 0; product *= A[i], i--)  /* 从右往左累乘 */         B[i] *= product;     return B; } 67. 把字符串转换成整数 NowCoder 题目描述 将一个字符串转换成一个整数，字符串不是一个合法的数值则返回 0，要求不能使用字符串转换整数的库函数。 复制代码 1 2 3 4 5 6 7 Iuput: +2147483647 1a33   Output: 2147483647 0 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int StrToInt(String str) {     if (str == null || str.length() == 0)         return 0;     boolean isNegative = str.charAt(0) == '-';     int ret = 0;     for (int i = 0; i < str.length(); i++) {         char c = str.charAt(i);         if (i == 0 && (c == '+' || c == '-'))  /* 符号判定 */             continue;         if (c < '0' || c > '9')                /* 非法输入 */             return 0;         ret = ret * 10 + (c - '0');     }     return isNegative ? -ret : ret; } 68. 树中两个节点的最低公共祖先 解题思路 二叉查找树 Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree 二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。 复制代码 1 2 3 4 5 6 7 8 9 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {     if (root == null)         return root;     if (root.val > p.val && root.val > q.val)         return lowestCommonAncestor(root.left, p, q);     if (root.val < p.val && root.val < q.val)         return lowestCommonAncestor(root.right, p, q);     return root; } 普通二叉树 Leetcode : 236. Lowest Common Ancestor of a Binary Tree 在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最低公共祖先。 复制代码 1 2 3 4 5 6 7 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {     if (root == null || root == p || root == q)         return root;     TreeNode left = lowestCommonAncestor(root.left, p, q);     TreeNode right = lowestCommonAncestor(root.right, p, q);     return left == null ? right : right == null ? left : root; }

连续最大和 分析: 经典水题。没啥好说的. 时间复杂度: O(n) 参考code: #include <iostream> #include <algorithm> using namespace std; int main(){ int n; scanf("%d",&n); int sum = 0, mx = -99999999; for(int j = 0; j < n; j++){ int temp; scanf("%d",&temp); if(sum < 0) sum = temp; else sum += temp; mx = max(sum, mx); } printf("%d\n",mx); } 餐馆 分析: 贪心。先把顾客进行消费金额降序,人数升序排序。 然后枚举每波顾客去二分当前最适合的 桌子的容量，维护答案即可,注意答案可能爆int。 这题裸暴力过不了。 不能拆桌。时间复杂度：O(mlogm + nlogm) 参考code: #include <iostream> #include <map> #include <vector> #include <map> using namespace std; struct node{ int b,c; }; int cmp(node x,node y){ if (x.c == y.c) { return x.b < y.b; } return x.c > y.c; } int n,m; long long ans; std::vector<node> v; std::multimap<int, int> mp; int main(){ scanf("%d%d",&n,&m); for(int i = 0; i < n; i++){ int x; scanf("%d",&x); mp.insert(std::pair<int, int>(x, 1)); } for(int i = 0; i < m; i++){ int x, y; scanf("%d%d",&x,&y); node tmp; tmp.b = x, tmp.c = y; v.push_back(tmp); } sort(v.begin(),v.end(),cmp); for(int i = 0; i < m; i++){ std::map<int,int>::iterator it = mp.lower_bound(v[i].b); if (it != mp.end()) { mp.erase(it); ans += v[i].c; } } printf("%lld\n",ans); }

在通过第二章的方法将数据排序之后，我们常常需要进行查找操作，本章就来介绍查找的方法。我们会使用符号表这个词来表示一张抽象的表格，其实就可以把它看成键值对，而键值对就是字典，键对应单词，值对应单词的意思，发音等。 我们先列出符号表symbol table的API: 然后我们的工作就是选择适当的数据结构去实现它，你可以看到，不同的数据结构对效率的影响有多大 无序链表实现符号表 一个简单选择是链表，每个节点存储一个键值对，具体实现看代码： class SequentialSearchST{ private: Node first; //链表首节点 class Node{ Key key; Value val; //泛型 Node next; public: Node(Key key, Value, val, Node next){ this.key = key; this.val = val; this.next = next; } }; public: //查找给定的键，返回相关联的值 Value get(Key key){ for(Node x = first; x!= NULL; x = x.next){ if(key==x.key){ return x.val; } } return NULL; } //插入给定的键，若存在则更新val void put(Key key, Value val){ for(Node x = first; x!= NULL; x = x.next){ if(key == x.key){ x.val = val; return; } } //如果没找到，就头插该节点 first = new Node(key, val, first); } }; 有一个很好的地方在于，put没找到值插入时很方便，直接头插，但无论是put还是get，都需要遍历整个链表，都是O(n)的复杂度，不够快， 有序数组实现符号表 它使用的数据结构是一对平行的数据，一个存储键一个存储值（这种技巧在很多算法题也经常可以用） 因为我们一直保持键的有序性，所以在接下来的代码中，你可以看到我们多次利用rank函数，它返回表中小于给定键的键的数量 class BinarySearchST { vector<Key> keys; vector<value> val; int N; public: int size(){ return N; } //后面实现，先假设它实现了 int rank(Key key); Value get(Key key){ if(isEmpty()) return NULL; int i = rank(key); if(i<N && keys[i] == key) return vals[i]; //找到了 else return NULL; } void put(Key key, Value val){ int i = rank(key); //找到就更新val if(i<N && keys[i] == key) {vals[i]=val; return;} //如果没找到就要插入，插入的话就要让i-N的元素后移来腾位置 for(int j=N; j>i; j--){ keys[i] = keys[i-1]; vals[j] = vals[j-1]; } keys[i] = key; vals[i] = val; N++; } }; //就是个二分查找 int BinarySearchST::rank(Key key){ int lo = 0, hi = N-1; while(lo<=hi){ int mid = lo + (hi-lo)/2; if(key<keys[mid]) hi= mid-1; else if(key>keys[mid]) lo = mid+1; else return mid; } return lo; } //问一个小问题，如果查找的元素不在符号表中，返回的数字还是小于该键的数量吗？ //答案：是的，不清楚的可以看下图 这个数据结构通过维持键数组的有序性，再通过二分查找，使得get复杂度下降到O(logN)，但是还有一点不好，就是插入的时候要腾位置，复杂度还是O(logN)

秋招以来，经历了近10场top快消公司和互联网公司的案例分析。 论形式有小组讨论、商业游戏、个人展示；论小组人数，有少至4人、也有多至十几人； 论复杂程度有一面纸进行1h的、也有一大本资料进行大半天的； 论进程，有将其放在很前面的，也有放到终面环节的。 不方便透露具体的case内容，但就几种面试情形分享一下自己的破局之法，以及一些突发情况的处理手段 （只挂过一场case～）。 情形1: case简单人多时许多互联网公司的初筛喜欢采用这种模式，便于快速淘汰掉大量申请人。Case往往挺短，而且无关业务；时长最多1h，参与人数甚至超过10人；考核者是hr；通过率往往是10%左右。这种情形下，让面试官记住你你就赢了。可如何在人多且case没技术含量的时候被人记住呢？那就要当leader或者军师。想当Leader，你必须在一开始就发言，并且是有自信地把框架提出来（群面里有的leader是后发型的，但在这种case简单的情况下不适用）。但光提出来是坐不稳的，还要自信这个框架能获得大家认可（简单case的框架一般显而易见），并且可以知道后面如何进一步使用这个框架。最后，你还得是一个气场足的人。如果你不敢当leader，或者当了一半被截胡了，那么军师也是一个不错的选择。军师要当一个和leader打配合的二把手，在leader框架的基础上，提出很多解决问题的点子。很多人觉得在群面时，不会有朋友，其实不然。军师就是那个主动“拉拢”leader的人，leader本就需要认同者，军师的idea又是建设在leader框架上的，leader自然会给你留表现空间。举个例子。曾遇到过一个case，让你根据几位候选人的自我介绍，选出最适合当产品经理的人。有一个小姐姐一开始就提出这是个针对能力特征优先级排序的问题，我们看看谁的特点和这个岗位匹配度最高。得嘞，那她岂不是已经把题目解完了吗。但不愿意游戏就此结束的我这时说“我非常认同X号的想法。不过有一个小问题，每个候选热特点很多，直接比较不容易，我建议我们先用三个关键词进行总结候选人特点再排序。而且排序标准除了匹配度，还要参考一下其后天培养难度，因为我们XX集团也是一家注重员工潜力的公司。”我的发言没有一点儿反对leader的意思，全是为了更好推进任务进行提出的建议，体现了团队合作与解决问题能力。后面我和leader的合作非常顺利，我俩也都进了下一轮。所以在面对leader已经出现的时候，别和ta对着干，毕竟ta有先发优势。首先再抠抠题眼看看leader有没有把大家带偏，理由充足了后就可“篡位”。如果leader的框架的确正确，那就当军师吧。其一可以从颗粒度入手，leader毕竟是搞框架的人，没法在细节层面都顾上，这就是军师的发挥空间；其二是做好行业、公司的功课，看可不可结合业务来解题，展现知识面和务实性格。 情形2: case复杂人少时往往会给一份很厚的、与业务相关的case，候选人大概3-6位，assessor有hr也有业务部门的人员，时长从1h到半天。这往往是已经到了很后面的考核环节了，是为了在更综合复杂的情况下看你身上的有没有公司需要的能力与品质。形式一般是先自由阅读材料，然后组内讨论，最后一个总结pre和Q&A；但duang参加某快消巨头的biz game时也遇到过角色扮演（CMO、CFO等）进行四个季度的商业决策。 Anyway，要注意的都是以下几点： 1.    短时间内如何阅读长而难的材料？ 十几页的、纯英文的、充满data和新概念的case确实很难在十几分钟内读完，但问题就在于真的不用读完！先粗略阅读，弄清材料的的框架（比如材料是分为customer base、marketing、product、channel、supply、finance）；然后马上看任务（比如要输出目标客户、产品、渠道、营销方式、产量、预算，考核方式是一个market share、profit margin、branding、supply excellence的综合分）；然后就可以形成一个解题思路了（确定目标客户，匹配对应产品，再选好渠道，然后根据预算，设计对应的市场活动和产量）；最后就要根据解题思路和材料里的细节内容去解题了。 2.    应该扮演什么角色呢？ 一般而言，在大家对于case还一脸懵逼时，能做好前一点的人很容易占取主动权，当上leader。可是当你遇上神仙打架的时候咋办？切记不要慌，这个时候往往没有人可以真的控场。框架被人说了没事，既然case这么复杂，一定会有很多的发挥空间。而且神仙在一起，往往会有很多思维碰撞，做到逻辑清楚理由充分的发言即可。有逻辑有框架、用事实说服他人是会被所有考官喜欢的特点，但是之前最好做足公司文化的功课（比如有的公司喜欢有冒险精神的人，你提出的idea就可以激进一点）。这个文化匹配很重要！唯一挂过的那场群面，当上了leader，并且最后的点也大部分是我提出来的。但是估计是表现得过于aggressive，和公司peace的风格不太符合，于是被残忍挂掉了hhh。其次，虽然会给资料，但你若是可展现对公司业务的理解会是一项很大的plus（比如公司战略、最近的市场举措等）。             至于要不要争取pre的机会，当然是要呀！不过要注意，本来不擅长pre的朋友还是不要啦，会适得其反。 Q&A环节也相当于小型pre现场，那个时候再展现自己也可。Pre不需要辞藻华丽，有框架感并且逻辑清晰最重要；并且不要自作聪明地加入一些自己的想法，我们是在代表整个组pre哦～ 最后还想说几点： 1.     有的群面会用“中途换组”、“分开小组再合并”等操作来考核你，千万别慌！在一场面试里，在前半场的组里是负责产品，中途被换去了另一个组。在那个组里走的同学原来是负责供应链的，我作为后来者只能接受新职责。这考察的是你的适应能力和学习能力。新小组的同学们非常nice地想给我讲讲他们现在的情况，讲了大概一分钟被我打断了。因为他们讲的很全，但我觉得时间有限，我没必要知道他们之前的所有事情。于是我问了他们各自的职责，然后用针对性“问问题”的形式快速了解。比如，我问了他们目前选择的目标客户是什么？用了什么渠道？现在盈利和品牌等业绩表现如何？之前的总战略是什么？…后面在中途复盘assessor问我们对换组有何感想，我上台说：一来，让我明白了管培生项目轮岗的意义，这有助于我们对生意有全盘认知，做的决策也会更多综合考量。我之前的岗位给了我产品思维，让我在新的供应链岗位上，会考虑产品策略。二来，在进入新的环境时，我不是被动等别人来给我辅导，而是主动用提问来高效了解情况。当我看到下面的assessor频频点头时，我知道他们给我加分了。还有一场面试，小组刚开始就被劈成两半单独讨论，然后又被合并。这个时候这两半各形成了不用的观点。这考核的是“说服能力“以及”在团队里的坚持与妥协“。首先你要仔细分析对方的观点，如果觉得不对，你就要有主见；框架性的语言和。 2.     心态问题。很多人都是一种要把其他同学干趴下的心态，这往往会让你不受控制的戾气重以及感情用事，得失心会影响你的理性。我大三时也是用上战场的心态去群面，但战况惨烈。秋招就变得“佛“起来，真心在想如何解决的问题以及为了整个团队好，结果反而通过率极高。但是“佛”不是说不好好想问题哦，而是说不要总想着抢leader以及多说话之类的～ 爆肝了一晚整理出了自己的群面心得，希望可以给大噶带来帮助。

答案是诚实的投其所好，这二者兼有，缺一不可。 如何理解？ 首先诚信是职场的基本原则，不要为了得到工作故意去欺骗，因为一个谎话要用另一个谎话去接住，很容易露陷，有经验的面试官基本也都自由一套办法，去验证你的真实程度。 所以最好不用选择欺骗的方法，诚信是底线。 但是我们还是要投其所好，有选择性的去回答，而不是对方问什么不经过思考的回答。 如何投其所好？ 面试一切问题回答的核心都要回答为什么你可以胜任这份工作来，一切回答最后的归结点都是你具备相应的能力，可以胜任这份工作。 经常遇到一些过于诚实的应聘者，问你觉得你最大的缺点是什么，然后回答n个和工作岗位直接冲突的点，给了面试官n个不选他的理由。 或者问你为什么来应聘这份工作，就诚实的回答就是刚好看到了来试一试吧… 我们鼓励真诚，但是我们要适当的去修饰你的真诚，既然选择了来求职，就要用你最诚恳的态度和准备，来告诉对方为什么要选择你。 如果自己都说服不了自己，如果你不拿出最大的诚意去争取，对方为什么要给你机会呢？

很多人在求职时，如果长时间收不到面试邀请的时候，会产生一种行为——海投简历。觉得投得越多，机会越多。所以不管岗位要求、行业类型、工资高低……先投它个500份再说。 这样确实省时省力，从概率学的角度来看，好像也会拿到更多的面试机会。如果说投15-20份简历能收获一份面试邀请，那投500份简历就能拿到25次面试机会。 然而事实真的是这样吗？答案是否定的。 为什么呢？ 01 不讲条件的概率算法，是耍流氓！ 投递简历应该是在仔细阅读JD，分析自己与JD中描述信息相符合的前提下投递，这样精准的投放，能够有更大概率获得面试机会。 而海投简历的行为，为了能够在短时间内对大量岗位进行投递，往往不会仔细阅读JD，甚至不阅读JD，那么岗位需求、工作职责等信息并不能够完全了解，无法做出判断自己是否适合该岗位工作，获得面试机会概率远小于精准投放。 除了转化率不高，海投还有很多其他方面的弊端，请接着往下看。 02 海投简历是无个人信息保护意识的表现 简历包含了详细的个人信息，已经不仅是电话号码这种个人信息，因此，我们需要更加注重个人信息的保护。 海投简历意味着可能你并不知道给哪家公司投了简历,这些公司都是干什么的？他们拿到你的信息会做什么？被不相关的公司掌握个人信息，且这些信息是你主动发给他的，是不是有点自投罗网的刺激感。 虽然你找工作必须要投递简历，虽然我们会对发布的职位信息进行审核，但防人之心不可无，个人信息的保护意识要加强，连什么公司在招人你都没认真了解就投递简历，未免有些显得过于儿戏。 03 接到面试岗位可能不符合个人要求 可以肯定的说,海投是能获得面试机会的，要不也不会有很多同学选择海投的方式，但海投得到的面试岗位一定符合你的个人要求吗？ 每个人对工作都有一定的预期：薪资、工作地点、公司规模、所属行业、岗位属性、发现前景、福利待遇等等。 而海投时，你可能真的不会认真去看JD上关于这些内容的介绍，但对于HR来说， 看到你投递的简历了，就认为你对该岗位有意向，认为该岗位符合你的基本需求，这样在你的条件符合用人单位的需求时，就会给与你联系进行面试。 这种情况下的面试，岗位可能很难符合你的个人要求。 04 可能错失心仪的公司和岗位 海投了那么简历，如果刚好有符合你预期的，又邀请你来面试，那也是一件皆大欢喜的事情。 可是还有一个现实问题，你海投了那么多份简历，真的能对投递的每个岗位都有个印象吗？如果没有，那么在因为这个而失去错失机会，是不是很可惜啊。 有些公司的HR会在电话邀约面试时，做一些基本信息的了解，其中可能包括“求职意向”的调查，想知道约你来面试你是否会放鸽子，以及如果一切顺利你的入职意向有多少。 通常的话术是： HR：小明你好，我是XX公司HR，看到你投递了我们公司的xx职位，想先对你做一些简单的了解。 小明：xx公司？ HR：xx公司，xx岗位， 小明：哦…… HR：看到你的简历之前不是从事我们公司相关行业的，想了解一下你对我们公司及行业了解多少。 …… 基本聊到这儿，有经验的HR就知道你是海投的，没有诚意、不稳定等这种标签就会马上被贴给你，礼貌寒暄几句，就没有然后了。 05 海投简历的求职者，面试时往往准备不充分 海投简历求职者在投递简历时，没有对岗位、行业、公司做一定的筛选，是无法保证所投递的岗位是自己擅长及知识结构所覆盖的，就算来到了面试环节，在面试准备上往往不能做到非常充分，降低了获取offer的可能性。 相对而言，精准投递简历求职者能够更好的做面试准备，了解掌握面试岗位所需要的背景知识及技能结构，甚至对公司情况做到非常了解，更容易获得offer。 求职，特别是想要找个好工作，一直以来都不是一个容易的事。现在竞争越发激烈的情况下，为了能获得一份工作而选择海投简历是可以理解的， 但还需希望求职者都能科学求职。认真阅读JD，精准投递简历，充分做好面试准备，每一步都踏踏实实的去做，相信找到一个理想的工作，也不是那么困难。 加油！祝每位求职者都前程无忧。