一、个人情况 本人国内211本，英国G5计算机硕。去年9月毕业回国时对国内校招情况完全没有概念，是无实习无职业规划无产品认知的三无小白，并且眼高手低心高气傲，只投大厂。凭我当时的垃圾简历竟然也收到了阿里字节等大厂面试，但是都是一面挂。 通过和朋友交流以及不断了解求职现状后，意识到没有产品实习对求职有两大硬伤： 简历不好看，难过简历关。就算过了简历关，到了面试的时候就发现和面试官没东西聊，只能问些宝洁八大问或者产品场景题、逻辑题之类的问题 缺乏实习经历意味着对产品工作缺乏了解。实习是最快速学习产品的途径，只是看书或者自己"体验产品"的话，也是有用的，但是很难对产品工作有实际落地的认识。如果你不是某方面特别突出（比如表达能力，逻辑思维，产品感觉等等特别强），面试官当然更愿意选择有过实习经历的同学，这样更好带 于是当时决定秋招、实习投递双管齐下，找到了某大厂日常实习，开始了一边实习一边秋招的日子。 那是一段非常黑暗的时光：一方面其实那份实习并不算含金量特别高，甚至有些水，当时的mentor也并不擅长带人，所以感觉对产品的学习依然是进度很慢曲线很陡的；另一方面自己在秋招战场上频频受挫，当时没有意识到自己不仅仅是缺乏产品认知，更加是极度缺乏面试技巧，对”面试“这件事没有认识，常常是接到面试通知就赶过去，在面试官面前没有准备没有逻辑的瞎说一通，然后挂掉。所以一直到12月都没有收获offer，那之后我就心灰意冷、停止投简历，准备面对来年3月的春招了。在这期间，我痛定思痛，认真系统的整个复盘总结了自己整个求职的状况，从疫情开始后我就一直在家准备求职，我认为这段时间是我进步最快速的一段时间。 在经过3月、4月的投简历，面试后，我依然频频折戟，但最终收获了个人还算满意的offer，所以决定把自己的经历和感悟写下来，不仅是给牛友提供经验，更是对我漫长艰难的求职经历的一次总结。 二、简历及面试技巧 1.简历如何写？ 写简历说简单也简单，说难也难。 关键在两点： 自己要对项目熟悉。所谓的STAR法则等等，都是建立在你对项目完全熟悉之后，帮助你将项目有逻辑表述出来的技巧。所以在应用任何技巧/方法论之前，首先自己把项目想明白，了解透，才会知道如何去写 熟悉项目之后，就可以运用老生常谈的STAR法则了。确实非常有用，STAR法则中的Action是占比简历最大的部分，用于详细描述做一件事的经过。S、T、R可以用在一句话描述经历中：在某背景/问题（S）下，通过做某任务/手段（T），达到某目标（R）；或者也可以用12字法则：动词开头，结果导向，数据证明。其实是一样的，殊途同归。 除此之外，有意识的在简历中埋点。比如认为自己某一个故事特别出彩/特别能证明自己的某个能力，那么详细描写，并且加粗显示以吸引面试官的注意。另外，最有价值的经历一定要放在最开头，因为面试官通常都是从第一个项目问起，有些没耐心的可能问一个就结束了。 2.面试怎么准备？ a：如何准备面试 我把面试常见的问题分成三类： 简历相关问题 - 做了什么，为什么要做，怎么做的，结果如何 - 遇到什么问题，如何解决的 - 收获与成长 - 改善点，未来发展 - 挑战、质疑类问题 通用类问题 - 为什么当pm - pm的职责与能力，如何体现 - 什么是产品 - 什么性格适合做产品 ... 开放专业题 - 常用产品与公司产品的优缺点，如何改进，未来发展 - 场景题（如何提升某数据...怎么解决某问题...如何设计某产品...） (俗称产品思维题，推荐书籍《产品经理面试攻略》刷刷题，虽然书比较老，但是思路还是很不错) 面试前针对性的做准备即可，另外有几点注意： 什么叫熟悉简历？论坛上常常看到大牛奋力呼吁：一定要熟悉简历啊！！！可是对于小白来说，什么叫熟悉简历、怎么去熟悉简历呢？其实非常简单，反复的看反复的想，对项目的每一个细微的疑惑都要记下来、想清楚，不然极有可能后续被面试官偶然挖出来，成为挂你的依据。不仅是把项目表面的逻辑细节搞清楚，还可以更深层次的想一些比较宏观的问题：这个项目的核心价值是什么？为什么要这么做？这些思考后续可以成为面试中能抛的亮点 有意识的总结项目。如何总结？三点：项目的难点+可优化点（即如果你再做一遍会怎么做）+个人收获。 不要说你想不出来，任何项目应该都是可以挖出这三点的。每个项目准备好这三点后，就可以应对自如面试官这类问题啦。一般是比较后面的，偏宏观的面试会问。有些面试官可能不会问这方面的，那么！就可以自己主动抛亮点！比如：我觉得这个项目其实有可以优化的地方blabla，要知道面试就是一场抛亮点的游戏啊！ b、面试技巧 要知道，面试是绝对有技巧的。不要想当然的觉得我只要有实力就可以了！面试中等着面试官来挖我简历就行了！这样做只会降低你的面试成功概率。我认为面试中实力和技巧是占一半一半的，这和面试这件事的特点有关：面试是一个时间非常短并且随机性非常强的过程。这两个特点决定了我们在面试中一定要尽可能的占据主动权，有意识的引导面试官往自己准备过的优势去。那么该如何做呢？ 有以下几点需要注意： 建立自己的能力模型。 不仅是产品岗，任何非技术岗求职这都是必备的一点。仔细观察各种产品JD，一般会要求你具备逻辑思维、表达能力...等等，事实上产品岗是有相应的能力模型的，可以自己总结也可以百度搜索，比如著名的腾讯产品能力模型等。实际上，面试官在评估你时，也是评估你能力模型上各项能力的水准。做准备时有针对性的根据各项能力准备，比如你想说自己具备数据分析能力，那么你有相关项目来说故事吗？没有就不要用这个能力，不然只会让面试官觉得你假大空。从自己项目故事中挖掘相应能力即可，一般三个左右够用。 有意识的抛自己的亮点。 因为面试是随机性很强的，面试过程中风向瞬息万变，那么尽可能让面试官不费力的看到自己的亮点就变得非常重要，可以极大的增加面试成功的概率。那么该怎么抛呢？像前面说，项目总结类问题可以自己主动说；以及像有些问题，比如“你觉得产品需要具备哪些能力”，这就是很好的自由发挥题啊！（你可以说：我认为产品需要ABC能力，我在个人经历中的DEF证明了我有相关能力）当然这个技巧也不要做的太过刻意哈，不要和面试官硬拗，要做到自然有礼貌有尊重 结构化表达。 这个对我面试提升非常大，将答案/项目结构化表述出来能够直接让面试官觉得你有逻辑思维。具体该如何结构化表达呢？参照金字塔原理：结论先行，分点讨论。比如“你觉得疫情对xx行业有什么影响”，答“分短期和长期两块。短期：123，长期：123”。这样不管你的内容是什么，面试官一定首先会觉得听得神清气爽，觉得你逻辑强人！另外，除了这种开放类问题，描述项目的时候就按照star法则描述就可以了，也会比较有逻辑。逻辑表达可以说是面试中至关重要的一块，掌握这一点面试成功率飙升50%不是梦 精神面貌。 面试过程中，面试官首先感受到的是你的气场，性格等等，这比能力评估之类的工作更直接。所以给面试官一个好的精神面貌非常重要，要亲和，自信有礼貌。老实说我自己在这一点做得很差，有时压力太大人很抑郁真的很难笑出来，应该对我的面试成功率有影响。以后一定要多多注意这方面 面试复盘。 人人都说，面试复盘非常重要！可具体该怎么做？我觉得复盘绝不是机械的整理出面试被问到的问题，思考答案而已。事实上每场面试问的问题其实大同小异。。。重要是总结出这场面试我那些地方做的好，让我过了？我哪些地方没做好，所以没让我过？我本来可以如何做的更好的？所谓任何失败中都潜藏着成功，任何成功中都潜藏着失败。这才是复盘的真正含义。 3.校招新人必备的职场认知 面试通过了就高枕无忧的了吗？错！面试通过只完成了拿offer流程的一半。有些公司备胎池很深的会让很多人通过，然后在offer审批环节挂掉。也有可能突然公司没hc了，你说这找谁说理去？所以作为弱势的求职者，没有签订具有法律效力的offer前一定不要松懈，要持续不断的一直面试。毕竟跟公司把我们当备胎相比，我们把公司当备胎对公司造成的影响要小得多。每年牛客上都有好多好多毁oc，毁意向，毁offer甚至试用期辞退的血淋淋的例子，你怎么知道下一个不是你？这样的事情我觉得和个人实力无关，甚至也和哪家公司无关，只和运气有关。所以我认为，给自己多上道保险吧。 三、个人经验总结 尽管最终收获了offer，我依然觉得自己在求职这件事上非常失败。漫长的求职之旅，艰难的进步，极长的战线，最后我也并没有收获传统意义上大家向往的大厂offer。所以虽然求职之旅告一段落，下一阶段希望能好好做事，但我还是认为有必要总结自己整个过程中暴露出的缺点，关键的致命点和得到的收获，以便时时提醒自己。 1.没有再找实习 在某大厂实习过两三个月后，当时我本可以跳去找别的实习，最好是带转正的，这样无疑校招会轻松很多。可我愣是没有。一方面是当时项目未完结，觉得找太多实习不如把另一份实习做精。另一方面当时实力欠缺，而且对找实习这个事动力不强。我觉得“动力”这件事是我最伤的点，说一千技巧道一万方法论，如果自己没有足够强的内驱力和动力的话事情很难做成功。也许我可以想想为什么我常常是“不想”、“不愿”、“懒得”做事 2.面试是一场概率游戏，依赖很大的信任成本 和世界上的任何事情一样，面试是一场概率游戏。并不是你努力了就能成功，努力只能增大你成功的概率，并不能确保你的成功。也并不是你哪一点没做好就会失败，只是增大你的失败概率而已。前面说的那些要点，即使全部做到了也未必能面试成功。即使成功了，差运气也能让你拿不到offer。所以如果建立起概率游戏的概念的话，能以更加平静的心态面对得失成败，正确客观的认识自己。 另外，面试也是一件很依赖信任成本的事情。作为一个完全陌生的人，你如何说服面试官你是可以胜任他手中工作的？首先就是降低他对你的信任成本。高学历，大厂实习，漂亮的项目数据，优秀的笔试成绩都是降低信任成本的手段。另外，根据我的经验，一面也是一个尤其能降低信任成本的地方。因为严格意义上说，只有一面面试官对你是陌生的，后面的面试官有面试评价作参考。所以一面尽可能的表现好的话，一份好的面试评价会让后面的面试官下意识的对你有好印象，让你在后面的面试中走的更顺利。 3.心态建设 对多数人而言，校招是很磨人的过程，你可能好长时间拿不到面试，可能面试总是挂，可能手上的offer没有同学的亮眼，可能公司的业务，行业，领导你并不喜欢。在这个过程中，稳住自己的心态非常重要。一方面少接收刺激性的贩卖焦虑的信息，比如贩卖焦虑的公众号取关，和常常被倾倒负能量的朋友减少交流等等，尽可能保持内心平静，不要太容易被外界风吹草动摇自己的初心。另一方面尝试用长期的，动态的，发展的眼光看待自己的职业发展。当前的失败不代表你永久的失败，谁说你不能在以后的日子里继续努力，后发制人？不管现实状况如何让你受挫，觉得自己很失败，我们首先不能自己打倒自己。外在条件如何令人失望是我们无法控制的，但我们不能自己贬低自己，自己打倒自己，人生是漫漫长路，永远不要放弃自己。 与各位共勉。祝各位求职顺利，也祝自己能够在产品这条路上做出一点成绩。 4.有策略的应对挑战，带着脑子思考问题 今天突然想明白为什么会在在家期间进步很大了，因为我找到了打面试这场仗的方法，或者说开始学会使用策略/打法去应对找工作这个挑战。之前找工作，可能就是无脑找，只知道要努力，做简历，面试复盘。但不会带进主观能动性的思考去想，该怎么准备，用什么策略应对，什么打发是最适合自己情况的。那么自然现实会打脸，结果会很差。之后我开始想，简历怎么做会让看得人觉得匹配度高，表述清晰；面试应该针对性的准备哪些内容，应该如何引导面试官，如何展现自己等等。其实背后都有适合自己的策略的，也可以说是产品思维吧，用户是谁，产品要解决什么需求等等。我想这个思路也适合其他任何事情。像王宝强说过的，“想到和得到之间还有个做到”。 我觉得“做到”又分两层：1.首先是做，要动起来；2.要有方法的做，而不是死脑筋的做。这两点才能确保自己“做到”了。 （dbp写到这里都觉得自己太菜了。。大佬请无视） 5.别人的建议真的适合你吗？ 大量的经验贴、技术贴，教你怎么找工作，包括这篇也是。但是我发现，其实别人从自身经历总结出的经验也许并不适合你，比如我在文中说的面试要自信热情等等，也许你已经做的很好了，而你自身存在尚待解决的问题文中没有提到。就像每个人都是独一无二的一样，每个人也都存在自身独特的问题。没有任何方法论是吃遍天下的，如果你想快速提高，也许开始自我负责，开始思考who you are，what you want，开始独立自主的思考最适合自己的方法，这才是最有效的 （我废话真多。。菜鸡的热泪啊）

最近在找工作刷leetcode，为了面向就业刷题，狠心开了几个月会员（leetcode会员好尼玛贵），大家都是学生党没什么钱，有的朋友没办法开会员，今天我就把leetcode面试的高频题分类整理了，有需要的朋友自取！ （PS，希望大家都能好好刷题找到好工作！！！） 数组 回溯算法 二分查找 位运算 广度优先遍历 深度优先遍历 设计 分治算法 动态规划 哈希表 堆 链表 数学 栈 排序 字符串 树

当时去参加面试的时候，路过他们的一排会议室，发现每个会议室的彩绘图案都不一样，当时很好奇地问了一下HR小姐姐，听说是员工自己画的，感觉这家公司好有爱哦，文化氛围很好，安利给大家。

概述 1、什么是Redis 2、Redis有哪些优缺点 3、为什么要用 Redis /为什么要用缓存 4、为什么要用 Redis 而不用 map/guava 做缓存? 5、Redis为什么这么快 数据类型 1、Redis有哪些数据类型 2、Redis的应用场景 持久化 1、什么是Redis持久化？ 2、Redis 的持久化机制是什么？各自的优缺点？ 3、如何选择合适的持久化方式 4、Redis持久化数据和缓存怎么做扩容？ 5、过期键的删除策略 6、Redis的过期键的删除策略 7、Redis key的过期时间和永久有效分别怎么设置？ 8、我们知道通过expire来设置key 的过期时间，那么对过期的数据怎么处理呢? 内存相关 1、MySQL里有2000w数据，redis中只存20w的数据，如何保证redis中的数据都是热点数据 2、Redis的内存淘汰策略有哪些 3、Redis主要消耗什么物理资源？ 4、Redis的内存用完了会发生什么？ 5、Redis如何做内存优化？ 线程模型 1、Redis线程模型 事务 1、什么是事务？ 2、Redis事务的概念 3、Redis事务的三个阶段 4、Redis事务相关命令 5、事务管理（ACID）概述 6、Redis事务支持隔离性吗 7、Redis事务保证原子性吗，支持回滚吗 8、Redis事务其他实现 集群方案 1、哨兵模式 2、官方Redis Cluster 方案(服务端路由查询) 3、基于客户端分配 4、基于代理服务器分片 Redis 主从架构 1、Redis集群的主从复制模型是怎样的？ 2、生产环境中的 redis 是怎么部署的？ 3、说说Redis哈希槽的概念？ 4、Redis集群会有写操作丢失吗？为什么？ 5、Redis集群之间是如何复制的？ 6、Redis集群最大节点个数是多少？ 7、Redis集群如何选择数据库？ 分区 1、Redis是单线程的，如何提高多核CPU的利用率？ 2、为什么要做Redis分区？ 3、你知道有哪些Redis分区实现方案？ 4、Redis分区有什么缺点？ 分布式问题 1、Redis实现分布式锁 2、如何解决 Redis 的并发竞争 Key 问题 3、分布式Redis是前期做还是后期规模上来了再做好？为什么？ 4、什么是 RedLock 缓存异常 1、缓存雪崩 2、缓存穿透 3、缓存击穿 4、缓存预热 5、缓存降级 6、热点数据和冷数据 7、缓存热点key 常用工具 1、Redis支持的Java客户端都有哪些？官方推荐用哪个？ 2、Redis和Redisson有什么关系？ 3、Jedis与Redisson对比有什么优缺点？ 其他问题 1、Redis与Memcached的区别 2、如何保证缓存与数据库双写时的数据一致性？ 3、Redis常见性能问题和解决方案？ 4、Redis官方为什么不提供Windows版本？ 5、一个字符串类型的值能存储最大容量是多少？ 6、Redis如何做大量数据插入？ 7、假如Redis里面有1亿个key，其中有10w个key是以某个固定的已知的前缀开头的，如果将它们全部找出来？ 8、使用Redis做过异步队列吗，是如何实现的 9、Redis如何实现延时队列 10、Redis回收进程如何工作的？ 11、Redis回收使用的是什么算法？ 答案详解如下： https://blog.nowcoder.net/n/e4ba3dea1fbf49a3b80955b49cf7d841

前几天发了字节面试算法100题，这一篇给牛友们整理了答案，楼主整理过程中又对题目做了归类，所以和之前的题目顺序不完全一致，这一篇包含了100题中动态规划和贪心，数组，排序，栈+队列+链表，二叉树相关的算法题题解。一些不易分类的算法题，场景题和智力题答案下一篇发出来。 整理不易，感觉有用的话点个赞呀，亲！😁😁（牛客网的编辑器插入代码必须一个一个来，楼主从自己的笔记中一点一点复制过来，眼睛要瞎了😭😭😭） 很多题目的题解参照了牛客和力扣中的优秀题解，一些题目中也贴出了题解链接。楼主能力一般，水平有限，难免有错误和遗漏，有问题的地方欢迎牛友们在评论区指正，有更好的解法也可在评论区分享，万分感谢。 【算法题】 动态规划和贪心 算法题：买卖股票的最佳时机（只能有一次买卖，可以最多两次买卖，不限次数） 股票问题通用解法详解参考： https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/ 最复杂的情况是限制交易k次，状态转移方程无法化简，其他情况均可化简为二维或一维动态规划。 复制代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465//一次买卖public class Solution {    public int buy(int[] price) {        int n = price.length;        int ans = 0;        int[][] dp = new int[n][2];        dp[0][0] = 0;        dp[0][1] = Integer.MIN_VALUE;        for(int i = 1;i < n; i++){            dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + price[i]);            dp[i][1] = Math.max(dp[i - 1][1],- price[i]);        }        return dp[i][0];    }} 优化：只与相邻的一个状态有关，那么可以只记录前一个状态，不使用数组，空间降到O (1)public class Solution {    public int buy(int[] price) {        int n = price.length;        int ans = 0;        int dp_i_0 = 0;        int dp_i_1 = Integer.MIN_VALUE;        for(int i = 1;i < n; i++){            dp_i_0 = Math.max(dp_i_0,dp_i_1 + price[i]);            dp_i_1 = Math.max(dp_i_1,- price[i]);        }        return dp_i_0;    }}//不限制次数：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) //有一天冷却期dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。 //有服务费dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)解释：相当于买入股票的价格升高了。在第一个式子里减也是一样的，相当于卖出股票的价格减小了。 //2次买卖原始的动态转移方程，没有可化简的地方dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) int max_k = 2;int[][][] dp = new int[n][max_k + 1][2];for (int i = 0; i < n; i++) {    for (int k = max_k; k >= 1; k--) {        if (i - 1 == -1) {             /* 处理 base case */            dp[i][k][0] = 0;            dp[i][k][1] = -prices[i];            continue;        }        dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);        dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);    }}// 穷举了 n × max_k × 2 个状态，正确。return dp[n - 1][max_k][0]; 剑指原题，剪绳子。 1.动态规划：每次剪一刀之后，剩余部分还可以继续剪，那么就是计算出所有可能的情况，取最大值。自底向上改善递归从上而下重复计算的问题。 时间复杂度O(N^2),空间复杂度O（N） 复制代码12345678910111213141516171819202122232425262728public class Solution {    public int cutRope(int target) {        if(target == 2)            return 1;        if(target == 3)            return 2;        if(target == 4)            return 4;        int[] dp = new int[target + 1];          /*        下面3行是n>=4的情况，跟n<=3不同，4可以分很多段，比如分成1、3，        这里的3可以不需要再分了，因为3分段最大才2，不分就是3。记录最大的。         */        dp[1]=1;        dp[2]=2;        dp[3]=3;        //用来记录最大值        int res = 0;        for(int i = 4;i <= target; i++){            for(int j = 1;j <= i/2;j++){                res = Math.max(res,dp[j]*dp[i - j]);            }            dp[i] = res;        }        return dp[target];    }} 2.贪心算法：可以证明，每段长度为3是最大乘积。 时间复杂度O(logN),因为乘方运算的时间复杂度是logN。当 数据特别大时，只能使用贪心算法，因为动态规划枚举每个状态需要大量的空间。 复制代码1234567891011121314151617public class Solution {    public int cutRope(int target) {        if(target==2){            return 1;        }else if(target==3){            return 2;        }    //pow(n,m)是求n的m次方        if(target%3==0){            return (int)Math.pow(3,target/3);        }else if(target%3==1){            return 4*(int)Math.pow(3,target/3-1);        }else {            return 2*(int)Math.pow(3,target/3);        }    }} 算法：接雨水（leetcode 42） 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例: 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6 思路： 对于每一列来说，他能存的雨水量是他左边最高墙和右边最高墙中较低的那堵墙的高度减去自身墙的高度。所以可以用数组记录每列左右最高墙的高度，然后计算每一列可以存的雨水量。 动态规划：时间复杂度O(N)，空间复杂度O(N)。 复制代码1234567891011121314151617181920212223class Solution {    public int trap(int[] height) {        int len = height.length;        if(len == 0 || len == 1) return 0;        int[] left = new int[len];        int[] right = new int[len];        left[0] = height[0];        right[len - 2] = height[len - 1];        for(int i = 1;i < len - 1;i++){            left[i] = Math.max(height[i - 1],left[i - 1]);        }        for(int i = len - 2;i >= 0;i--){            right[i] = Math.max(height[i + 1],right[i + 1]);        }        int sum = 0;        for(int i = 1; i < len - 1;i++){            int min = Math.min(right[i],left[i]);            if(min > height[i])                sum = sum + (min - height[i]);         }        return sum;    }} 动态规划空间优化： 因为left和right数组中每个元素我们只使用一次，所以没必要保存整个数组，左右只保存一个值就可以。由于left和right遍历时方向不一致，left和计算时的遍历方向一致，很容易更新，而right依然要使用数组来存储，这样空间复杂度仍为O(n)。 如果当前列左侧最高墙的高度比右侧最高墙的高度小，那么能装多少水由左侧决定，也就是说min变量就等于左侧最高墙的高度，反之，右侧最高墙的高度小，那么min就等于右侧最高墙的高度。那么我们 在遍历过程中就可以先比较左右最高墙的高度，选两侧的较小值计算雨水量加入sum。（这里我可能说的不太清楚，如果无法理解请参照力扣中的题解：https://leetcode-cn.com/problems/trapping-rain-water/solution/） 时间复杂度O(N)，空间复杂度O(1)。 复制代码1234567891011121314151617181920212223242526class Solution {    public int trap(int[] height) {        int len = height.length;        if(len == 0 || len == 1) return 0;        int maxLeft = 0;        int maxRight = 0;        //加左右指针        int left = 1;        int right = len - 2;        int sum = 0;        for(int i = 1; i < len - 1;i++){            if(height[left - 1] < height[right + 1]){                maxLeft = Math.max(maxLeft,height[left - 1]);                if(maxLeft > height[left])                    sum +=  maxLeft - height[left];                left++;            }else{                maxRight = Math.max(maxRight,height[right + 1]);                if(maxRight > height[right])                    sum += maxRight - height[right];                right--;            }        }        return sum;    }} 柠檬水找零（LeetCode860） 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。 注意，一开始你手头没有任何零钱。 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。 思路：尽可能有大面值找零，也就是能用10元找零就不用2个5元。是贪心算法思想的体现。 复制代码123456789101112131415161718192021222324class Solution {    public boolean lemonadeChange(int[] bills) {        int five = 0,ten = 0;        for(int value : bills){            if(value == 5){                five++;            }else if(value == 10){                if(five == 0) return false;                five--;                ten++;            }else{                if(ten >= 1 && five >= 1){                    ten--;                    five--;                }else if(five >= 3){                    five = five - 3;                }else{                    return false;                }            }        }        return true;    }} 数组 双指针遍历：解决有序数组的问题 排序数组，平方后，数组当中有多少不同的数字（相同算一个）。 如果不是排序数组，可以使用hashset来保存数字的平方，重复就存不进去，那么最后就可以直接返回set的大小size即可。时间空间复杂度都是O（n)。 双指针遍历 ：这里是排序数组，既然有重复，肯定是有负数，0,1这些数字。 平方后两头大，中间小，可以用首尾指针共同向中间扫描，扫描时去掉重复元素，同时用一个sum来记录有多少个不同数字。 时间复杂度O(N)，空间复杂度O(1)。 复制代码1234567891011121314151617181920212223242526272829303132333435public class Solution {    public int diffSquareNum(int nums[]) {        int n = nums.length;        if(n == 0 || nums == null){            return 0;        }        int sum = 0;        int left = 0;        int right = n - 1;        while(left <= right){            if(nums[left] + nums[right] == 0){                sum++;                int temp = nums[left];                //这里开始去掉后面重复的数字                while(left <= right && nums[left] == temp)                    left++;                while(left <= right && nums[right] == -temp)                    right--;            }            else if(nums[left] + nums[right] < 0){                sum++;                int temp = nums[left];                while(left <= right && nums[left] == temp)                    left++;            }            else {                sum++;                int temp = nums[right];                while(left <= right && nums[right] == temp)                    right--;            }        }        return sum;    }} 一个数据先递增再递减，找出数组不重复的个数，比如 [1, 3, 9, 1]，结果为3，不能使用额外空间，复杂度o(n) 与上面一题一模一样，双指针从两头向中间逼近。 复制代码12345678910111213141516171819202122232425262728293031323334public class Solution {    public int diffnum(int[] nums){        int n = nums.length;        if(n == 0 || nums == null){            return 0;        }        int left = 0;        int right = n - 1;        int sum = 0;        while(left <= right){            if(nums[left] == nums[right]){                sum++;                int temp = nums[left];                while(left <= right && nums[right] == temp)                    right--;                while(left <= right && nums[left] == temp)                    left++;            }            else if(nums[left] < nums[right]){                sum++;                int temp = nums[left];                while(left <= right && nums[left] == temp)                    left++;            }            else{                sum++;                int temp = nums[right];                while(left <= right && nums[right] == temp)                    right--;            }        }        return sum;    }} 递增数组，找出和为k的数对 双指针遍历 ：用头尾两个指针，分别开始遍历，两个数字和大于k时，右指针向前移动，小于k时左指针向后移动。 复制代码12345678910111213141516171819public class Solution{    public ArrayList findPair(int[] nums,int k){        int n = nums.length;        int i = 0;        int j = n - 1;        ArrayList<Integer> list = new ArrayList<>();        while(i < j){            if(nums[i] + nums[j] < k){                i++;            }else if(num[i] + nums[j] > k){                j--;            }else{                list.add(nums[i]);                list.add(nums[j]);            }        }        return list;    }} 给出一个数组nums，一个值k，找出数组中的两个下标 i，j 使得 nums[i] + nums[j] = k. 这个题目跟上面一题的区别就是不是有序数组，那么解题思路就可以是 排序+双指针遍历 ，时间复杂度就因为排序升为O(NlogN)。 对于这个无序数组另一种解决办法是使用HashMap，数字作为键，下标作为值存入hashmap，然后遍历map查找符合条件的数对，map可以实现O(1)的查找，所以时间复杂度和空间复杂度都是O(N)。（这里需要注意，如果数组中有重复元素，那么这个方法就不能用，因为重复元素存入map时，后面的值（下标）会覆盖掉前面的值。） 复制代码123456789101112131415161718//这种实现方式无法去掉重复的pair，如结果中会同时有（3,6）和（6,3）。public class Solution{    public ArrayList<Pair<Integer, Integer>> findPair(int[] nums, int k) {        ArrayList<Pair<Integer, Integer>> pairs = new ArrayList<>();        HashMap<Integer, Integer> map = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            map.put(nums[i], i);        }        for (Map.Entry<Integer, Integer> set : map.entrySet()) {            int target = k - set.getKey();            //第二个判断条件是为了去除（2，2）这种情况，即同一数字即做加数又做被加数的情况            if (map.containsKey(target) && !map.get(target).equals(set.getValue())) {                pairs.add(new Pair<>(set.getValue(), map.get(target)));            }        }        return pairs;    }} 滑动窗口：解决连续序列问题 和为s的连续正整数序列（剑指offer57-II) 输入一个正整数 target ，输出所有和为 target 的 连续正整数 序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例 1： 输入：target = 9 输出：[[2,3,4],[4,5]] 滑动窗口：窗口左右两端都只能向右移动，当和小于sum时，j++，和大于sum时，i++，和等于sum就记录下窗口中i —j 中的序列，然后窗口继续后移，查找下一个满足条件的序列。 复制代码12345678910111213141516171819202122232425262728class Solution {    public int[][] findContinuousSequence(int target) {        int i = 1;        int j = 1;        int sum = 0;        List<int[]> list = new ArrayList<>();        //序列是由小到大排列，所以如果i>target/2，那么i+i+1肯定大于target        while(i <= target/2){                if(sum < target){                sum += j;                j++;            }else if(sum > target){                sum -= i;                i++;            }else{                int[] res = new int[j - i];                for(int z = i; z < j;z++){                    res[z - i] = z;                }                list.add(res);                // 左边界向右移动                sum -= i;                i++;            }        }        return list.toArray(new int[list.size()][]);    }} 某一个大文件被拆成了N个小文件，每个小文件编号从0至N-1，相应大小分别记为S(i)。给定磁盘空间为C，试实现一个函数从N个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小。 滑动窗口：每次记录窗口内的总和，和小于C，记录剩余空间，再窗口右端右移，和大于C，就窗口左端右移，小于C情况下比较剩余空间取最小值。 复制代码1234567891011121314151617181920212223242526272829public class Solution {    public int[] findMin(int[] s,int c){        int i = 0;        int j = 0;        int minValue = Integer.MAX_VALUE;        int sum = 0;        int left = 0;        int right = 0;        while(j <= s.length){            if(sum <= c){               j++;               sum += s[j];               minValue = Math.min(minValue,c - sum);               if(minValue == c - sum){                   left = i;                   right = j;               }            }else{                i++;                sum -= s[i];            }        }        int nums = new int[right - left];        for(int k = left;k < right;k++){            nums[k - left] = s[k];        }        return nums;    }} 给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata，问能否在这个字符串中找到一个长度为m的连续子串，使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。比如上面这个例子，acbd，3。 （2） 类似leetcode 567： https://leetcode-cn.com/problems/permutation-in-string/ 分析： 本题的子串需要满足长度为m，字符不重复，可以使用长为m的滑动窗口遍历字符串，窗口内每个字符都要出现一次，如果符合条件，就返回窗口起始位置。 如果这里不允许使用substring,indexOf函数，可以将字符串中每个字符出现的次数存入长度为26的数组中进行比较每次数组中对应位置数量是否相等，具体可参照上面LeetCode 567题。 复制代码123456789101112131415161718192021public class Solution {    public int checkInclusion(char[] ch,String s) {        if(ch.length > s.length()){            return -1;        }        for(int i = 0; i < s.length() - ch.length; i++){            //每次匹配长度为m的子串            if(matchs(ch,s.substring(i,i+ch.length)))                return i;        }        return -1;    }    private static boolean matchs(char[] ch,String s){        for(int i = 0; i < s.length();i++){            //返回-1说明字符串中不包含这个字符            if(s.indexOf(ch[i]) == -1)                return false;        }        return true;    }} 有序有重复数组，给定target确定范围 使用滑动窗口。 算法题，一个有序数组，从随机一位截断，把前段放在后边，如 4 5 6 7 1 2 3求中位数 用排序解决，问了下一般排序算法的复杂度，O(nlogn) 扫一遍，找出分界点，O(n) 提示我还有更快的方法，那肯定只有二分了，想了好久mid的判断条件后写了个解法，给面试官叙述了一遍跑样例的过程。 哈希表辅助解决数组问题 算法：求数组的最长连续递增数列，如：4， 200， 3， 1， 100， 2。结果是1 2 3 4，也就是说顺序可以打乱。（leetcode 128） 思路一：排序，然后再遍历一遍找最长连续递增数列，时间复杂度O(NlogN)。 思路二：使用HashMap或者HashSet，将数组元素存入set中，然后遍历set，先找到每个序列的开头元素，即num没有num-1的情况，这时从num开始循环找num+1,记录次数，通过比较找出最大长度。时间和空间复杂度都是O（n) 复制代码1234567891011121314151617181920212223//这里用set，是因为set可以自动去重，用map也不影响结果class Solution {    public int longestConsecutive(int[] nums) {        if (nums.length == 0) return 0;        HashSet<Integer> set = new HashSet<>();        for(int value : nums)            set.add(value);         int longestLength = 0;        for (int num: set) {            if (!set.contains(num - 1)){                int currentNum = num;                int currentLength = 1;                while (set.contains(currentNum + 1)){                    currentNum += 1;                    currentLength += 1;                }                longestLength = Math.max(longestLength,currentLength);            }        }        return longestLength;    }} 一个无序数组，从小到大找到第一个缺的数，比如[8 2 4 3 6 9 7 11 12],第一个缺的就是5 （2） 1.排序，时间复杂度O(NlogN) 2.用数组作为哈希表，将数字i放入数组中的i索引处，然后找中间没有存入数字的位置。时间和空间复杂度都是O(N) 复制代码1234567891011121314151617181920212223public  class Solution {    public int findLost(int[] nums){        int min = nums[0];        int max = nums[0];        for(int value : nums){            min = Math.min(min,value);            max = Math.max(max,value);        }        int[] res = new int[max - min + 1];        for(int i = 0; i < res.length;i++){            res[i] = min - 1;        }        for(int value : nums){            res[value] = value;        }        int i = 0;        while(i < res.length){            if(res[i] = min - 1)                break;        }        return i;    }} 输出给定数字下一个比它大的数字，比如输入：1234， 输出 1243。 https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/ 首先从后往前遍历找到一个数字nums[i]比num[i+1]小，也就是找到递减到递增的转折点，然后再与递减序列中最小的大于num[i]的数字交换，这样交换完之后后面仍然是递减序列，将其转换为递增序列，这样可以保证数字增大，并且增大的幅度最小。 复制代码1234567891011121314151617181920212223242526272829303132333435class Solution {    public void nextPermutation(int[] nums) {        //从倒数第二个数字开始比较        int i = nums.length - 2;        //找nums[i] < nums[i + 1]的i        while(i >= 0 && nums[i] >= nums[i + 1]){            i--;        }        if(i >= 0){            int j = nums.length - 1;            while(j > 0 && nums[i] >= nums[j]){                j--;            }             swap(nums,i,j);        }        reverse(nums,i + 1);    }     public void swap(int[] nums,int i, int j){        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }     public void reverse(int[] nums,int start){        int j = nums.length - 1;        int i = start;        //因为是递减序列，所以可以这样交换成递增的        while(i < j){            swap(nums,i,j);            i++;            j--;        }    }} 算法题(leetcode55题)：给一个数组，例如[1,2,3,4,5]，a[i]表示在该位置可以向前行走的最大距离，判断是否可以到达数组的最后一个元素 思路： 每次走最大的距离，如果能超过末尾元素，说明只要调小步伐就一定可以达到最后位置。 复制代码123456789101112131415public class Solution {    public boolean canJump(int[] nums) {        int n = nums.length;        int rightmost = 0;        for (int i = 0; i < n; ++i) {            if (i <= rightmost) {                rightmost = Math.max(rightmost, i + nums[i]);                if (rightmost >= n - 1) {                    return true;                }            }        }        return false;    }} AB两个排序数组，原地合并数组。（A当中穿插一些无效数字怎么处理？） 思路：因为要原地合并数组，如果从前往后遍历，数组原来的值会被覆盖，所以只能从后往前遍历，将值从后往前存入。存入时比较当前两个指针指向的数字大小，选较大的存入，然后往前移动指针。 （有无效数字的情况楼主没有想到好的解决办法，小伙伴们如果有思路请在评论区解答，感谢！） 复制代码123456789101112class Solution {    public void merge(int[] A, int m, int[] B, int n) {        int i = m - 1,j = n - 1,k = m + n - 1;        while(j >= 0){            if(i < 0 || B[j] >= A[i]){                A[k--] = B[j--];            }else {                A[k--] = A[i--];            }        }    }} 排序相关 快排（3) 复制代码1234567891011121314151617181920212223242526public void quickSort(int[] arr,int L,int R){    if (arr.length == 0) return;    int i = L;    int j = R;    int key = arr[(i + j)/2];    while (i <= j){        while (arr[i] < key)            i++;        while (arr[j] > key)            j--;        if (i <= j){            int temp = arr[i];            arr[i] = arr[j];            arr[j] = temp;            i++;            j--;        }    }    //上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。    //“左边”再做排序，直到左边剩下一个数(递归出口)    if (L < j)        quickSort(arr,L,j);    //“右边”再做排序，直到右边剩下一个数(递归出口)    if(i < R)        quickSort(arr,i,R);} 高考成绩2000万数据，分数0-750，如何快速知道你的排名，如何知道任一分数排名 --->桶排序 （3）桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布 ，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。 算法描述： 设置一个定量的数组当作空桶； 遍历输入数据，并且把数据一个一个放到对应的桶里去； 对每个不是空的桶进行排序； 从不是空的桶里把排好序的数据拼接起来。 复制代码1234567891011121314151617181920212223242526272829303132public class Solution {    public ArrayList<Integer> bucketSort(int[] scores){      //先确定最大最小值，来确定范围      int max = Integer.MIN_VALUE;      int min = Integer.MAX_VALUE;      for(int i = 0; i < scores.length;i++){          max = Math.max(max,scores[i]);          min = Math.min(min,scores[i]);      }      //计算出桶数      //int bucketNum = (max - min)/scores.length + 1;      //这里直接给出751个桶      int bucketNum = 751;      ArrayList<ArrayList<Integer>> list = new ArrayList<>(bucketNum);      for(int i = 0; i < bucketNum; i++){          list.add(new ArrayList<Integer>());      }             //将每个元素放入桶      for(int i = 0; i < scores.length;i++){          //本题中这里放元素也可以简化          //list.get((scores[i] - min)/bucketNum).add(scores[i]);          list.get(scores[i]).add(scores[i]);      }             //桶内排序,本题中可以省略这一步      for(int i = 0; i< list.size();i++){          Collections.sort(list.get(i));      }       return list;    }} 数组中第K大的数（LeetCode215题） 首先想到最简单的排序，然后返回第k大的元素，时间复杂度O(NlogN)。 快排的patition思想：时间复杂度O（n)，空间复杂度O(1) 复制代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051public class Solution {    public int findKthLargest(int[] nums, int k) {        int len = nums.length;        int left = 0;        int right = len - 1;        // 转换一下，第 k 大元素的索引是 len - k        int target = len - k;         while (true) {            int index = partition(nums, left, right);            if (index == target) {                return nums[index];            } else if (index < target) {                left = index + 1;            } else {                right = index - 1;            }        }    }     /**     * 在数组 nums 的子区间 [left, right]      执行 partition 操作，返回 nums[left] 排序以后应该在的位置     * 在遍历过程中保持循环不变量的语义     * 1、[left + 1, j] < nums[left]     * 2、(j, i] >= nums[left]     */    public int partition(int[] nums, int left, int right) {        int pivot = nums[left];        int j = left;        for (int i = left + 1; i <= right; i++) {            if (nums[i] < pivot) {                // 小于 pivot 的元素都被交换到前面                j++;                swap(nums, j, i);            }        }        // 在之前遍历的过程中，满足 [left + 1, j] < pivot，        //并且 (j, i] >= pivot        swap(nums, j, left);        // 交换以后 [left, j - 1] < pivot, nums[j] = pivot,        // [j + 1, right] >= pivot        return j;    }     private void swap(int[] nums, int index1, int index2) {        int temp = nums[index1];        nums[index1] = nums[index2];        nums[index2] = temp;    }} top k，返回前K大的元素 这里可以使用和上题一样的快排patition。 也可以用堆排序，可以取前k个元素构造小根堆，然后遍历后面的元素，如果读取到的元素比堆顶下，直接丢弃，如果比堆顶大，就替换掉堆顶元素，然后调整堆。时间复杂度O(NlogK)。（堆实现参考下一题） 复制代码123456789101112131415161718192021222324252627282930313233343536373839404142public class Solution {    public ArrayList<Integer> topK(int[] nums){        if(nums.length <= k) return nums;        int n = nums.length;        int left = 0;        int right = n - 1;        int target = n - k;        int index = 0;        while(true){            index = partition(nums,left,right)            if(index == target){                break;             }else if(index < target{                left = index + 1;            }else{                right = index - 1;            }        }        ArrayList<Integer> list = new ArrayList<>();        for(int i = target;i < n;i++){            list.add(nums[i]);        }        return list;    }    public int pattition(int[] nums,int left,int right){        int pivot = nums[left];        int j =left;       for(int i = left + 1;i <= right;i++){           if(nums[i] > pivot){               j++;               swap(nums,i,j);           }       }       swap(nums,left,j);       return j;    }    public void swap(int nums,int i,int j){        int temp = nums[i];        nums[i] = nums[j];        nums[j] =temp;    }} 10亿个数字，取最小的100个数 (说思路 最大堆， partition 两者的时间复杂度，写伪代码) 1.最大堆：先取出前100个数，维护一个100个数的最大堆，遍历一遍剩余的元素，在此过程中维护这个最大堆就可以了。 具体步骤如下： step1：取前m个元素（例如m=100），建立一个大根堆。保持一个大根堆得性质的步骤，运行时间为O（logm);建立一个大根堆运行时间为mO(logm）=O(m logm); step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素大，直接丢弃；如果小于堆顶元素，则用该元素替换堆顶元素，然后保持最大堆性质。最坏情况是每次都需要替换掉堆顶的最大元素，因此需要维护堆的代价为(N-m)O(lgm); 最后这个堆中的元素就是前最小的100个。时间复杂度为O(N lgm）。 时间复杂度为O(10亿*lg100)。 首先构造大根堆： 堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求： (0 <= i <= (n-1)/2) ① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆； ② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆； n个节点的完全二叉树array[0，...，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆。 对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。 复制代码123456789101112131415161718192021222324252627//构建大根堆：将array看成完全二叉树的顺序存储结构private int[] buildMaxHeap(int[] array) {    //从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，    //直到根节点0，反复调整堆    for (int i = (array.length - 2) / 2; i >= 0; i--) {        adjustDownToUp(array, i, array.length);    }    return array;}//将元素array[k]自下往上逐步调整树形结构private void adjustDownToUp(int[] array, int k, int length) {    int temp = array[k];    for (int i = 2 * k + 1; i < length - 1; i = 2 * i + 1) {        //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整        if (i < length && array[i] < array[i + 1]) {          //取节点较大的子节点的下标            i++;   //如果节点的右孩子>左孩子，则取右孩子节点的下标        }        if (temp >= array[i]) {  //根节点 >=左右子女中关键字较大者，调整结束            break;        } else {   //根节点 <左右子女中关键字较大者            array[k] = array[i]; //将左右子结点中较大值array[i]调整到双亲节点上            k = i; //【关键】修改k值，以便继续向下调整        }    }    array[k] = temp;  //被调整的结点的值放人最终位置} 堆排序(大根堆)： ①将存放在array[0，...，n-1]中的n个元素建成初始堆； ②将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置； ③但此时堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再重复第②③步，直到堆中仅剩下一个元素为止。 堆排序算法的性能分析： 空间复杂度:o(1)； 时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn); 稳定性：不稳定 复制代码1234567891011//堆排序public int[] heapSort(int[] array) {    array = buildMaxHeap(array); //初始建堆，array[0]为第一趟值最大的元素    for (int i = array.length - 1; i > 1; i--) {        int temp = array[0];  //将堆顶元素和堆底元素交换，即得到当前最大元素正确的排序位置        array[0] = array[i];        array[i] = temp;        adjustDownToUp(array, 0, i);  //整理，将剩余的元素整理成堆    }    return array;} 本题中：构造完堆之后将新的元素与大根堆的堆顶元素比较，如果新元素比堆顶元素大，直接舍弃，如果小就跟堆顶元素交换，然后调整大根堆。 复制代码12345678910111213public int[] findMin(int[] array,int[] all){    array = buildMaxHeap(array);    //前面100个数字（0-99号）已经取出了    for(int i = 100;i <  all.length - 1; i++){        if(all[i] >= array[0]){            continue;        } else {            array[0] = all[i];            adjustDownToUp(array,0,array.length);        }        }    return array;} 2.快排划分的思想： 每次分割之后只考虑比轴小的一部分，直到比轴小的一部分数量在100多个的时候，采用传统排序算法排序，取前100个。 step1：递归对所有数据分成[a,b)，(b,d]两个区间，[a,b)区间内的数都是小于(b,d]区间内的数。 step2：对[a,b)重复 step1操作，直到最左边的区间个数小于100个。注意(b,d]区间不用划分 step3：返回上一个区间 ，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2)，(b2,d2]两个区间，取(a2,b2]区间。如果个数不够，继续 step3操作，如果个数超过100的就重复 step1操作，直到最后右边只有100个数为止。 复杂度为O(10亿*100) 算法：手写jdk中的优先级队列 PriorityQueue（最小堆） 参照上题中堆的实现。 栈，队列和链表最大栈（最小栈） 复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162使用辅助栈：public class MaxStack{    private Stack<Integer> stack;    private Stack<Integer> helper;    public MaxStack(){        stack = new Stack<>();        helper = new Stack<>();    }    public void push(int x) {        if(helper.isEmpty() || helper.peek() <= x){            helper.push(x);        }        stack.push(x);    }    public void pop(){        if(stack.peek() == helper.peek()){            helper.pop();        }        stack.pop();    }    public int peek(){        if(!helper.isEmpty()){            return stack.peek();        }        throw new RuntimeException("栈中元素为空");             }    public int getMax(){        if(!helper.isEmpty()){            return helper.peek();        }        throw new RuntimeException("最大值栈中元素为空");    }}用最大值标记，存入数据栈中，空间复杂度降到O(1)public class MaxStack {    private Stack<Integer> stack;    public MaxStack(){        stack = new Stack<>();    }    int max = Integer.MIN_VALUE;    public void push(int x){        if(max <= x){            if(!stack.isEmpty()){                stack.push(max);            }            max = x;        }        stack.push(x);    }    public void pop(){        if(stack.peek() == max){            stack.pop();            max = stack.pop();        }else{            stack.pop();        }    }    public int getMax(){        return max;    }} 两个栈实现一个队列 复制代码123456789101112131415161718192021222324252627282930public class StackToList{    private Stack<Integer> stack;    private Stack<Integer> helper;         public StackToList{        stack = new Stack<>();        helper = new helper<>();    }    public void push(int x){        stack.push(x);    }    public Integer poll() {        if(stack.isEmpty() && helper.isEmpty())            throw new RuntimeException("队列为空");        dataRemove();        return helper.pop();    }    public Integer peek() {        if(stack.isEmpty() && helper.isEmpty())            throw new RuntimeException("队列为空");        dataRemove();        return helper.peek();    }    public void dataRemove(){       if(helper.isEmpty()){            while(!stack.isEmpty())                helper.push(stack.pop());        }    }} 两个队列实现一个栈： 复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253/**     * @Description: 仅用队列来实现栈     * 采用两个队列，一个数据队列queue 一个辅助队列 help     * 入队时全部入队queue 出队时，将queue队列中数据入队help 将最后一个数 返回 并queue指针和help交换     */    public static class QueueToStack{        private Queue<Integer> queue;        private Queue<Integer> help;        public QueueToStack(){            queue = new LinkedList<Integer>();            help = new LinkedList<Integer>();        }          public void push(int pushInt){            queue.add(pushInt);        }        /**         * @Description: 弹栈操作操作         * 弹栈时，queue队列所有数据迁移至 help 返回最后一个数 并交换指针         */        public Integer pop(){            if (queue.isEmpty())                throw new RuntimeException("栈空！");            while (queue.size()>1){                help.add(queue.poll());            }            int temp = queue.poll();            swap();            return temp;        }          /**         * @Description: 栈的peek操作 只返回栈顶元素         * 原理同pop操作，但是在最后的一个元素要继续入队 help 因为peek只是返回栈顶 并非弹出         */        public Integer peek(){            if (queue.isEmpty())                throw new RuntimeException("栈空");            while (queue.size()>1){                help.add(queue.poll());            }            int temp=queue.poll();            help.add(temp);            swap();            return temp;        }          private void swap() {            Queue<Integer> temp = queue;            queue = help;            help = temp;        }    } 链表实现一个栈 复制代码1234567891011121314151617181920212223242526public class ListNode{    int val;    ListNode next;    ListNode(int val){        this.val =val;    }}public class ListToStack{    public ListToStack(){        ListNode head;    }    public void push(int x){        ListNode node = new ListNode(x);        node.next = head.next;        head.next = node;    }    public int pop(){        ListNode node = head.next;        head.next = node.next;        node.next = null;        return node.val;    }    public int peek(){        return head.next.val;    }} 两个链表，可能相交，找出相交的节点，给出证明（2) 1.若两个单链表一个为有环,一个无环. 那么肯定不能相交. 2.若二者都没有环, 问题就转化为 两个无环单链表是否相交,是否能找到第一个相交的节点，方法就是快慢指针。 3.若二者都有环,那么问题变成了两个有环单链表是否相交. 第一,先找到二者是否相交. 第二,若相交则需要遍历一遍找到相交点. 如果无环：问题转化为如何判断两个无环链表是否相交？ 要想判断是否相交，肯定要看是否能找到相交的点，如果能让两个指针同时走到相交点，也就可以确定两个链表相交。因为相交后两个链表到终点的距离相等，那么只要两个指针能够消除两个链表之间的长度差就可以到达终点的距离相等。假设链表A比B长，pB到达结尾后指向headA，然后继续向前遍历，当pA到达结尾后指向headB，此时两者的长度差就消除了。继续遍历如果两者指向同一节点，返回节点，如果两者都走到结尾依然没有相交，就返回null。 复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344//无环的情况public class ListNode {    int val;    ListNode next;    ListNode(int val){        this.val = val;        next = null;    }} public class Solution {    public ListNode getListNode(ListNode headA,ListNode headB) {        if(headA == null || headB == null){            return null;        }        ListNode pA = headA,pB = headB;        while(pA != pB){            if(pA == null){                pA = headB;            }else{                pA = pA.next;            }            if(pB == null){                pB = headA;            }else{                pB = pB.next;            }        }        return pA;    }}简化版：public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if (headA == null || headB == null) return null;        ListNode pA = headA, pB = headB;        //如果不相交，pA=pB=null        while (pA != pB) {            pA = pA == null ? headB : pA.next;            pB = pB == null ? headA : pB.next;        }        return pA;    }} 如果有环，就转化为如何判断两个有环链表是否相交？ 两个有环链表相交分为两种情况，一种是两个链表在进入环之前相交，另一种是两个链表在环内相交，如果不是在同一个节点进入，就是两个入口在两个节点。 第一种情况：可以将环在环的入口处断开，这样就与无环链表相交一样，可以根据无环链表的方法判断； 第二种情况：两者相交于环内，而且入环口不同。pA的入口节点（标记位loopA），pB的入环口标记为loopB,当他们都遍历一圈停在自己的入口节点时，pA往后遍历，pB不动，pA回到loopA之前，一定会碰到pB,如果碰不到，说明两者不在一个环里。 如果两种都不是，则是没有相交。 找有环链表的入口节点： 快慢指针：设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。 证明结论1：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。 证明结论2： 设： 链表头到环入口长度为--a ；环入口到相遇点长度为--b ；相遇点到环入口长度为--c 则：相遇时 快指针路程=a+(b+c)k+b ，k>=1 其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。 慢指针路程=a+b 快指针走的路程是慢指针的两倍，所以： （a+b）*2=a+(b+c)k+b 化简可得： a=(k-1)(b+c)+c 这个式子的意思是： 链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度。其中k>=1,所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。 复制代码1234567891011121314151617181920212223242526272829pulic class ListNode{    int val;    ListNode next = null;    ListNode(int val){        this.val = val;    }}public class Solution {    public ListNode EntryNodeOfLoop(ListNode pHead){        ListNode fast = pHead;        ListNode slow = pHead;        if(fast == null || fast.next == null){            return null;        }        while(fast != null && fast.next != null){            fast = fast.next.next;            slow = slow.next;            if(fast == slow){                break;            }        }        slow = pHead;        while(fast != slow){            fast = fast.next;            slow = slow.next;        }        return fast;    }} 反转链表 ---->反转链表升级版（每k个反转一下）（4） 普通版： 方法一:递归 复制代码1234567891011121314151617181920public class Listnode{    int val;    ListNode next;    ListNode pre;    ListNode (int val){        this.val = val;    }}//递归public class Solution{    public ListNode revoseList(ListNode head){        if(head == null || head.next == null){            return head;        }        ListNode cur = revoseList(head.next);        head.next.next = head;        head.next = null;        return cur;    }} 方法二：双指针迭代 复制代码12345678910111213141516171819public class Solution{    public ListNode revoseList(ListNode head){        if(head == null || head.next == null){            return head;        }        ListNode pre = null;        ListNode cur = head;        ListNode temp = null;        while(cur != null){            //标记下一个节点，以免丢失            temp = cur.next;            //实现反转            cur.next = pre;            pre = cur;            cur = temp;        }        return pre;    }} K个一组反转链表（LeetCode25题） ： https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/ 复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode reverseKGroup(ListNode head, int k) {        //定义一个头指针，用来将后面所有节点统一处理        ListNode dum = new ListNode();        dum.next = head;        //用来标记每一次反转部分的前一个结点        ListNode pre = dum;        //运动指针，扫描要反转的部分        ListNode end = dum;         while(end.next != null){            //每次扫描完要反转的部分，如果end为空说明达到尾部，直接break            for(int i = 0; i < k && end != null;i++) end = end.next;            if(end == null) break;            //标记要反转部分的开头节点            ListNode start = pre.next;            //标记反转链表后面部分的第一个节点，避免丢失            ListNode next = end.next;            //将要反转部分向后的指针断开，准备反转            end.next = null;            //反转完的链表返回反转后的头结点，接到pre的后面            pre.next = reverse(start);            //反转后start指针应该指向反转完成部分的末尾            start.next = next;            //让pre和end指针继续指向待反转链表的前一个节点            pre = start;            end = pre;        }        return dum.next;    }    public ListNode reverse(ListNode start){        ListNode cur = start;        ListNode pre1 = null;        while(cur != null){            ListNode temp = cur.next;            cur.next = pre1;            pre1 = cur;            cur = temp;        }        return pre1;    }} leetcode 链表求和 给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。 示例： 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912 （如果链表存储数据的顺序反过来怎么加？这个楼主不会，大家有思路请在评论区交流，十分感谢！） 复制代码123456789101112131415161718192021222324252627/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode head = new ListNode(0);        ListNode cur = head;        int carry = 0;//用以计算进位        //只要有一个不为空或者最后有进位都要继续循环        while(l1 != null || l2 != null || carry != 0){            int num1 = l1 == null ? 0 : l1.val;            int num2 = l2 == null ? 0 : l2.val;            int sum = num1 + num2 + carry;            carry = sum / 10;            cur.next = new ListNode(sum % 10);            if(l1 != null) l1 = l1.next;            if(l2 != null) l2 = l2.next;            cur = cur.next;        }        return head.next;    }} 二叉树 二叉树的前序遍历非递归 复制代码123456789101112131415161718192021222324252627282930public class TreeNode{    int val;    TreeNode left;    TreeNode right;    TreeNode(int val){        this.val = val;    }}//非递归public void preOrder(TreeNode root){    if(root == null) return;    Stack<TreeNode> stack = new Stack<>();    stack.push(root);    while(!stack.isEmpty()){        TreeNode node = stack.pop();        System.out.print(node.val);        //因为栈是先进后出，所以先压右孩子，再压左孩子        if(node.right != null)            stack.push(node.right);        if(node.left != null)            stack.push(node.left);    } }//递归public void preOrder(TreeNode root){    if(root == null) return;    System.out.print(root.val);    preOrder(root.left);    preOrder(root.right);} 二叉树的后序遍历非递归(2) 由于压栈顺序是 从上而下，先左后右，出栈时就是从下而上，先右后左，这时可以用一个辅助栈，将弹出的值压入栈中，最后统一弹出，顺序就是后序遍历的先左后右，从下而上。（也可以用LinKedList，弹出后加入链表头，这样也可以逆序） 复制代码12345678910111213141516public void postOrder(TreeNode root){    if(root == null) return;    Stack<TreeNode> s1 = new Stack<>();    Stack<TreeNode> s2 = new Stack<>();    s1.push(root);    while(!s1.isEmpty()){        TreeNode node = s1.pop();        s2.push(node);        if(node.left != null)           s1.push(node.left);       if(node.right != null)           s1.push(node.right);    }    while(!s2.isEmpty())        System.out.print(s2.pop().val + " ");} 中序遍历非递归 复制代码12345678910111213141516171819//中序遍历非递归class Solution {    public List<Integer> inorderTraversal(TreeNode root) {        Stack<TreeNode> stack = new Stack<>();        TreeNode p =root;        ArrayList<Integer> list = new ArrayList<>();        while(p != null || !stack.isEmpty()){            //一直走到最左边的左孩子            while(p != null){                stack.push(p);                p = p.left;            }            p = stack.pop();            list.add(p.val);            p = p.right;        }        return list;    }} 从上往下打印二叉树（层序遍历）（2) 与后序遍历类似，可使用队列，将左右节点节点先后加入队列尾，每次从队列头取出节点进入输出链表。这样可以保证每次取出的元素都是本层现存的第一个元素。 复制代码1234567891011121314151617181920212223242526272829public class TreeNode {    int val;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val){        this.val = val;    }} public class Solution {    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {        ArrayList<Integer> result = new ArrayList<>();        if(root == null)            return result;        LinkedList<Integer> queue = new LinkedList<>();        queue.add(root);        while(!queue.isEmpty()){            TreeNode node = queue.poll();            result.add(node.val);            if(node.left != null){                queue.add(node.left);            }            if(node.right != null){                queue.add(node.right);            }        }        return result;    }} 蛇形遍历二叉树(2) 与层序遍历的区别是当层数为奇数就从左往右遍历，层数是偶数，就从右往左。 复制代码1234567891011121314151617181920212223242526272829303132public class Solution {    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {        ArrayList<Integer> result = new ArrayList<>();        if(root == null)            return result;        LinkedList<Integer> queue = new LinkedList<>();        queue.add(root);        int level = 1;//认为根节点在第一层        while(!queue.isEmpty()){            TreeNode node = queue.poll();            result.add(node.val);            level++;            if(level % 2 == 1){                if(node.left != null){                    queue.add(node.left);                }                if(node.right != null){                    queue.add(node.right);                }            }else {                if(node.right != null){                    queue.add(node.right);                }                if(node.left != null){                    queue.add(node.left);                }            }                    }        return result;    }} 二叉树右视图（2） 就是找层序遍历每层最后一个节点。 复制代码12345678910111213141516171819202122232425262728293031323334353637/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List<Integer> rightSideView(TreeNode root) {        ArrayList<Integer> res = new ArrayList<>();        if(root == null) return res;        int curCount = 1;        int nextCount = 0;        LinkedList<TreeNode> list = new LinkedList<>();        list.add(root);        while(!list.isEmpty()){            TreeNode node = list.poll();            curCount --;            if(node.left != null){                list.add(node.left);                nextCount++;            }            if(node.right != null){                list.add(node.right);                nextCount++;            }            if(curCount == 0){                res.add(node.val);                curCount = nextCount;                nextCount = 0;            }        }        return res;    }} 二叉树各层节点数，递归、非递归，时间、空间复杂度 思路：借助队列实现层序遍历，在遍历的过程中，level记录当前层数，curCount当前层的节点数，nextCount下一层的节点数。每次弹出节点，将当前层节点减一，然后将当前节点的左右子节点加入队列，同时计数。当前层的节点数等于0时，说明这一层遍历完了，同时记录的下一层节点数就是下一层总的节点，直接保存。遍历到队列为空为止。 复制代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354//非递归，时间复杂度O(N),空间复杂度O(N)public Map<Integer,Integer> levelNodeCount(TreeNode root){    HashMap<Integer,Integer> map = new HashMap<>();    if(root == null) return map;    int level = 1;    int curCount = 1;    int nextCount = 0;    map.put(level,curCount);    LinkedList<TreeNode> list = new LinkedList<>();    list.add(root);    while(!list.isEmpty()){        TreeNode node = list.poll();        curCount--;        if(node.left != null){            list.add(node.left);            nextCount++;        }        if(node.right != null){            list.add(node.right);            nextCount++;        }         if(curCount == 0){             level++;             map.put(level,nextCount);             curCount = nextCount;             nextCout = 0;         }       }    return map;}递归：时间复杂度O(N),空间复杂度O(N)这里保存了每一层的每一个节点class Solution {    private List<List<Integer>> res = new ArrayList<>();    public List<List<Integer>> levelOrder(TreeNode root) {        if(root == null)            return res;        helper(root,0);        return res;    }    public void helper(TreeNode root,int level){        //说明level已经比现存的层数(res.size() - 1)多了，需要新建一个新的        if(res.size() == level){            res.add(new ArrayList<Integer>());        }        //存入当前层的列表里，递归过程中每次都会往一个列表里面加入数字，每次都        //加到不同的列表里。        res.get(level).add(root.val);        if(root.left != null)            helper(root.left,level + 1);        if(root.right != null)            helper(root.right,level + 1);      }} 二叉搜索树的第K大的节点 二叉搜索树（二叉排序树）满足：根节点大于左子树，小于右子树。那么二叉树的中序遍历序列就是一个递增序列 。 为方便了找第K大的节点，我们可以调换左右子树的遍历顺序，这样遍历序列是一个递减序列，这样遍历到第K个元素就是我们要找的第K大的节点。 复制代码1234567891011121314151617181920212223242526272829303132333435363738//迭代：class Solution {    public int kthLargest(TreeNode root, int k) {        Stack<TreeNode> stack = new Stack<>();        TreeNode p = root;        int count = 0;        while(p != null || !stack.isEmpty()){            while(p != null){                stack.push(p);                p = p.right;            }            p = stack.pop();            count++;            if(count == k){                return p.val;            }            p = p.left;        }        return 0;    }}//递归class Solution {    int res,index;    public int kthLargest(TreeNode root, int k) {        index = k;        dfs(root);        return res;    }    public void dfs(TreeNode root){        if(root == null) return;        dfs(root.right);        if(index == 0) return;        index--;        if(index == 0) res = root.val;        dfs(root.left);    }} 求完全二叉树的节点个数，小于O(n)，并分析复杂度 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2^h个节点。 分析：首先统计二叉树左右子树的层数，有以下两种情况： left == right。这说明，左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是2^left - 1，加上当前这个root节点，则正好是2^left。再对右子树进行递归统计。 left != right。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点+root节点，总数为2^right。再对左子树进行递归查找。 时间复杂度为O(logN*logN) < O(n)。 复制代码12345678910111213141516171819202122class Solution {    public int countNodes(TreeNode root) {        if(root == null)            return 0;        int left = countlevel(root.left);        int right = countlevel(root.right);        if(left == right){            //移位运算，1向左移动left次，相当于1*2^n            return countNodes(root.right) + (1<<left);        }else{            return countNodes(root.left) + (1<<right);        }         }    private int countlevel(TreeNode root){        int level = 0;        while(root != null){            level++;            root = root.left;        }        return level;      }} 编程题：求二叉树根节点到叶子结点的路径和的最小值（leetcode） 递归：只有左子树，就只计算左子树，只有右子树，就只计算右子树，两个都有，就计算左右子树取最小值。 复制代码12345678910public int minPath(TreeNode root){    if(root == null) return 0;    if(root.left != null && root.right == null){        return 1+minPath(root.left);    }    if(root.left == null && root.right != null){        return 1 + minPath(root.right);    }    return 1 + Math.min(minPath(root.left),minPath(root.right));} 二叉树中的最大路径和 leetcode 124 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列 。该路径至少包含一个节点，且不一定经过根节点。 思路：递归计算单边值，如果单边值小于0就不算，单边值大于0就加到总的路径和里面。 单边最大和等于Math.max(root, root+left, root+right)。计算单边最大和的过程中记录总的最大和。 复制代码1234567891011121314151617181920212223242526       int max = Integer.MIN_VALUE;    public int maxPathSum(TreeNode root) {        if (root == null) {            return 0;        }        dfs(root);        return max;    }     /**     * 返回经过root的单边分支最大和， 即Math.max(root, root+left, root+right)     * @param root     * <a href="/profile/547241" data-card-uid="547241" class="" target="_blank" from-niu="default" data-card-index="3">@return */    public int dfs(TreeNode root) {        if (root == null) {            return 0;        }        //计算左边分支最大值，左边分支如果为负数还不如不选择        int leftMax = Math.max(0, dfs(root.left));        //计算右边分支最大值，右边分支如果为负数还不如不选择        int rightMax = Math.max(0, dfs(root.right));        //left->root->right 作为路径与历史最大值做比较        max = Math.max(max, root.val + leftMax + rightMax);        // 返回经过root的单边最大分支给上游        return root.val + Math.max(leftMax, rightMax);    }    </a> 写代码： 二叉树的最近公共祖先 leetcode 236 稍有不同，原题的2个节点，面试是多个节点，算法的时间复杂度 (2) 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 两个节点 :递归 当我们用递归去做这个题时不要被题目误导，应该要明确一点 这个函数的功能有三个：给定两个节点 p 和 q 如果 p 和 q 都存在，则返回它们的公共祖先； 如果只存在一个，则返回存在的一个； 如果 p 和 q 都不存在，则返回NULL 本题说给定的两个节点都存在，那自然还是能用上面的函数来解决 具体思路： （1） 如果当前结点 root 等于NULL，则直接返回NULL （2） 如果root 等于 p 或者 q ，那这棵树一定返回 p 或者 q （3） 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 left 和 right 表示 （4） 此时若left为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left （5） 如果 left 和 right 都非空，因为只给了 p 和 q 两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先 （6） 如果 left 和right 都为空，则返回空（其实已经包含在前面的情况中了） 时间复杂度是O(n)：每个结点最多遍历一次，空间复杂度是O(n)：需要系统栈空间 复制代码123456789101112class Solution {    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        if(root == null) return null;        if(root == p || root == q) return root;        TreeNode left = lowestCommonAncestor(root.left,p,q);        TreeNode right = lowestCommonAncestor(root.right,p,q);        if(left == null) return right;        if(right == null) return left;        if(right != null && left != null) return root;        return null;    }} 多个节点的情况类似，多加一个判断条件就好了，依然是看左右子树是否存在某个节点。 路径总和 leetcode 112及其延伸 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 复制代码123456789101112131415161718192021222324252627282930313233343536373839404142//递归class Solution {    public boolean hasPathSum(TreeNode root, int sum) {        if(root == null) return false;        sum -= root.val;        if(root.left == null && root.right == null){            return sum==0;        }else{            return (hasPathSum(root.left,sum) || hasPathSum(root.right,sum));        }    }}//迭代：需要同时记录当前剩余的sum和当前节点class Solution {    public boolean hasPathSum(TreeNode root, int sum) {        if(root == null) return false;        Stack<TreeNode> nodeStack = new Stack<>();        Stack<Integer> numStack = new Stack<>();         nodeStack.push(root);        numStack.push(sum - root.val);         while(!nodeStack.isEmpty()){            TreeNode node = nodeStack.pop();            Integer value = numStack.pop();                         if(node.left == null && node.right == null && value == 0){                return true;            }             if(node.left != null){                nodeStack.push(node.left);                numStack.push(value - node.left.val);            }            if(node.right != null){                nodeStack.push(node.right);                numStack.push(value - node.right.val);            }        }        return false;    }} 延伸：（LeetCode113题） 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 递归+回溯： 复制代码123456789101112131415161718192021222324252627282930class Solution {    List<List<Integer>> res;    public List<List<Integer>> pathSum(TreeNode root, int sum) {        res = new ArrayList<>();        if(root == null)            return res;        backTrack(root, sum, 0, new ArrayList<>());        return res;    }     private void backTrack(TreeNode x, int sum, int curSum, List<Integer> vals){        vals.add(x.val);        curSum += x.val;        if(x.left == null && x.right == null){            if(curSum == sum){                res.add(new ArrayList<>(vals));            }            //到达叶子节点后，无论是否符合要求都要            //回退到上一个节点，看上一个节点的右子树是否符合要求            vals.remove(vals.size() - 1);            return;        }        if(x.left != null)            backTrack(x.left, sum, curSum, vals);        if(x.right != null)            backTrack(x.right, sum, curSum, vals);       //回溯，结果不同就回溯到上一个节点判断另一条路可不可以        vals.remove(vals.size() - 1);    }} 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/er-cha-shu-de-qian-xu-bian-li-fen-zhi-si-xiang-by-/ 复制代码123456789101112131415161718192021222324252627class Solution {    private HashMap<Integer,Integer> map = new HashMap<>();    private int[] preorder;    public TreeNode buildTree(int[] preorder, int[] inorder) {        int length = preorder.length;        this.preorder = preorder;        for(int i = 0;i < length;i++){            map.put(inorder[i],i);        }        return buildTree(0,length - 1,0,length - 1);    }     private TreeNode buildTree(int preL,int preR,int inL,int inR){        if(preL > preR || inL > inR){            return null;        }                    int privot = preorder[preL];        TreeNode root = new TreeNode(privot);         int privotIndex = map.get(privot);         root.left = buildTree(preL + 1,preL + (privotIndex - inL),inL,privotIndex -1);        root.right = buildTree(preL + (privotIndex - inL) + 1,preR,privotIndex + 1,inR);        return root;    }}

Redis 学习笔记 初识 Redis Redis 是一种基于键值对的 NoSQL 数据库，Redis 中的值可以是由 string、hash、list、set、zset 等多种数据结构和算法组成，因此 Redis 可以满足很多应用场景。Redis 将所有数据都存放在内存中，所以它的读写能力也非常高。Redis 还可以将内存的数据利用快照和日志的形式保存到硬盘上，这样在发生类似断电或者机器故障的时候，内存中的数据不会丢失。除了这些功能，Redis 还提供了键国企、发布订阅、事务、流水线、Lua 等附加功能。 Redis 的特性 速度快 正常情况下，Redis 执行命令的速度非常快，官方给出的数字是读写性能可以达到 10 万/秒。Redis 速度快的原因主要归纳为几点：① Redis 的所有数据都放在内存中。② Redis 是使用 C 语言实现的，一般来说 C 语言实现的程序距离底层操作系统更近，因此速度相对会更快。③ Redis 使用了单线程架构，预防了多线程的竞争问题。 基于键值对的数据结构服务器 与很多键值对数据库不同的是，Redis 中的值不仅可以是字符串，还可以是具体的数据结构，这样不仅能应用于多种场景开发，也可以提高开发效率。Redis 的全称是 REmote Dictionary Server，它主要提供五种数据结构：字符串、哈希、列表、集合、有序集合，同时在字符串的基础上演变出了位图和 HyperLogLog 两种数据结构，随着 LBS 基于位置服务的发展，Redis 3.2 加入了有关 GEO 地理信息定位的功能。 丰富的功能 ① 提供了键过期功能，可以实现缓存。② 提供了发布订阅功能，可以实现消息系统。③ 支持 Lua 脚本，可以创造新的 Redis 命令。④ 提供了简单的事务功能，能在一定程度商保证事务特性。⑤ 提供了流水线功能，这样客户端能将一批命令一次性传到 Redis，减少了网络开销。 简单稳定 Redis 的简单主要体现在三个方面：① 源码很少，早期只有 2 万行左右，在 3.0 版本由于添加了集群特性，增加到了 5 万行左右，相对于很多 NoSQL 数据库来说代码量要少很多。② 采用单线程模型，使得服务端处理模型更简单，也使客户端开发更简单。③ 不依赖底层操作系统的类库，自己实现了事件处理的相关功能。虽然 Redis 比较简单，但也很稳定。 客户端语言多 Redis 提供了简单的 TCP 通信协议，很多编程语言可以方便地接入 Redis，例如 Java、PHP、Python、C、C++ 等。 持久化 通常来说数据放在内存中是不安全的，一旦发生断电或故障数据就可能丢失，因此 Redis 提供了两种持久化方式 RDB 和 AOF 将内存的数据保存到硬盘中。 主从复制 Redis 提供了复制功能，实现了多个相同数据的 Redis 副本，复制功能是分布式 Redis 的基础。 高可用和分布式 Redis 从 2.8 版本正式提供了高可用实现 Redis Sentinel，能够保证 Redis 节点的故障发现和故障自动转移。Redis 从 3.0 版本正式提供了分布式实现 Redis Cluster，提供了高可用、读写和容量的扩展性。 Redis 的使用场景 缓存 缓存机制几乎在所有大型网站都有使用，合理使用缓存不仅可以加快数据的访问速度，而且能够有效降低后端数据源的压力。Redis 提供了键值过期时间设置，并且也提供了灵活控制最大内存和内存溢出后的淘汰策略。 排行榜系统 排行榜系统几乎存在于所有网站，Redis 提供了列表和有序集合数据结构，合理使用这些数据结构可以方便构建各各种排行榜系统。 计数器应用 计数器在网站中的作用很重要，例如视频网站有播放数、电商网站有浏览数，为了保证数据实时性，每一次播放和浏览都要做加 1 的操作，如果并发量很大对于传统关系型数据库的性能是很大的挑战。Redis 天然支持计数功能而且性能也非常好。 社交网络 粉丝、共同好友/喜好、推送、下拉刷新等是社交网络的必备功能，由于社交网站的访问量通常很大，而且关系型数据不太适合保存这种类型的数据，Redis 提供的数据结构可以相对容易地实现这些功能。 消息队列系统 消息队列系统是一个大型网站的必备基础组件，因为其具有业务解耦、非实时业务削峰等特性。Redis 提供了发布订阅和阻塞队列的功能，对于一般的消息队列功能基本可以满足。 Redis 不适合非常大的数据量，成本非常高，也不适合冷数据，会浪费内存。 Redis 安装与启动 安装 在 Linux 上安装，下载 Redis 指定版本的源码压缩包到当前目录： 复制代码1wget http://download.redis.io/releases/redis-3.0.7.tar.gz 下载好之后，进行解压： 复制代码1tar xzf redis-3.0.7.tar.gz 建立一个 redis 目录的软连接： 复制代码1ln -s redis-3.0.7 redis 进入 redis 目录： 复制代码1cd redis 编译： 复制代码1make 安装： 复制代码1make install 安装成功后，可以在任何目录执行 redis-cli -v查看 Redis 的版本。 usr/local/bin 目录下的可执行文件说明： 可执行文件 作用 redis-server 启动 Redis redis-cli Redis 命令行客户端 redis-benchmark Redis 基准测试工具 redis-check-aof Redis AOF 持久化文件检测和修复工具 redis-check-dump Redis RDB 持久化文件检测和修复工具 redis-sentinel 启动 Redis Sentinel 启动 有三种方式：默认配置、运行配置、配置文件启动。 默认配置：会使用 Redis 的默认配置启动，直接输入 redis-server 即可，不推荐。 运行配置：可以在运行时自定义配置，没设置的配置依然使用默认值，例如 redis-server --port 6380 指定以 6380 为端口号启动，不推荐。 配置文件：生产环境中推荐的启动方式，将配置写到指定文件里，例如配置写到了 /opt/redis/redis.conf 中，执行如下命令即可启动 Redis：redis-server /opt/redis/redis.conf 客户端连接方式有两种： ① 交互式：例如 redis-cli -h 127.0.0.1 -p 6379 ，之后所有操作都是通过交互方式实现的，不用再执行连接了。 ② 命令方式：例如 redis-cli -h 127.0.0.1 -p 6379 set name kobe 可以直接得到命令的返回结果。如果没有 -h 参数默认连接 127.0.0.1，如果没有 -p，默认连接 6379 端口。 停止 可以使用 redis-cli shutdown 停止 127.0.0.1 上 6379 端口的服务。 Redis 服务端会断开与客户端的连接、生成 RDB 持久化文件，将其保存在磁盘上然后关闭。 除了 shutdown 命令也可以使用 kill 进程号的方式关闭 Redis，但不要使用 kill -9 强制杀死 Redis 服务，不但不会做持久化操作，还会造成缓冲区等资源不能优雅关闭，极端情况会造成 AOF 和复制丢失数据的情况。 总结 Redis 有 8 个特性：速度快、基于键值对的数据结构服务器、功能丰富、简单稳定、客户端语言多、持久化、主从复制、支持高可用和分布式。 Redis 并不是万金油，有些场景不适合使用 Redis 做开发。 生产环境中使用配置文件启动 Redis。 生产环境选取稳定版本的 Redis，版本号第二位是偶数代表稳定。 API 的理解和使用 预备 全局命令 查看所有键：keys * 查看键总数：dbsize 会返回当前数据库中键的总数，不会遍历所有键而是直接获取 Redis 内置的键总数变量，所有时间复杂度是 O(1)。而 keys 会遍历所有键，时间复杂度为 O(n)，当 Redis 保存了大量的键时，线上环境禁止使用。 检查键是否存在：exists key，如果存在返回 1，否则返回 0。 删除键：del key [key..] del 是一个通用命令，无论值是什么数据类型结构都可以删除，返回结果为成功删除的键的个数。 键过期：expire key seconds ，Redis 支持对键添加过期时间，当超过过期时间之后会自动删除。ttl 会返回键的剩余过期时间，返回非负数代表键的过期时间，-1 代表键没有设置过期时间，-2 代表键不存在。 查看键的数据类型结构：type key，如果键不存在则返回 none。 数据结构和内部编码 type 命令实际上返回的是当前键的数据类型结构，它们分别是：string、hash、list、set、zset，但这些只是 Redis 对外的数据结构。实际上每种数据结构都有自己底层的内部编码实现，这样 Redis 会在合适的场景选择合适的内部编码，string 包括了 raw、int 和 embstr，hash 包括了 hashtable 和 ziplist，list 包括了 linkedlist 和 ziplist，set 包括了 hashtable 和 intset，zset 包括了 skiplist 和 ziplist。可以使用 object encoding 查看内部编码。 Redis 这样设计的好处是：① 可以改进内部编码，而对外的数据结构和命令没有影响。② 多种内部编码实现可以在不同场景下发挥各自的优势，例如 ziplist 比较节省内存，但在列表元素较多的情况下性能有所下降，这时 Redis 会根据配置选项将列表类型的内部实现转换为 linkedlist。 单线程架构 Redis 使用了单线程架构和 IO 多路复用模型来实现高性能的内存数据库服务。 每次客户端调用都经历了发送命令、执行命令、返回结果三个过程，因为 Redis 是单线程处理命令的，所以一条命令从客户端到达服务器不会立即执行，所有命令都会进入一个队列中，然后逐个被执行。客户端的执行顺序可能不确定，但是可以确定不会有两条命令被同时执行，不存在并发问题。 通常来说单线程处理能力要比多线程差，Redis 快的原因：① 纯内存访问，Redis 将所有数据放在内存中。② 非阻塞 IO，Redis 使用 epoll 作为 IO 多路复用技术的实现，再加上 Redis 本身的事件处理模型将 epoll 中的连接、读写、关闭都转换为时间，不在网络 IO 上浪费过多的时间。③ 单线程避免了线程切换和竞争产生的消耗。单线程的一个问题是对于每个命令的执行时间是有要求的，如果某个命令执行时间过长会造成其他命令的阻塞，对于 Redis 这种高性能服务来说是致命的，因此 Redis 是面向快速执行场景的数据库。 字符串 字符串类型是 Redis 最基础的数据结构，键都是字符串类型，而且其他几种数据结构都是在字符串类型的基础上构建的。字符串类型的值可以实际可以是字符串（简单的字符串、复杂的字符串如 JSON、XML）、数字（整形、浮点数）、甚至二进制（图片、音频、视频），但是值最大不能超过 512 MB。 常用命令 设置值 set key value [ex seconds] [px millseconds] [nx|xx] ex seconds：为键设置秒级过期时间，跟 setex 效果一样 px millseconds：为键设置毫秒级过期时间 nx：键必须不存在才可以设置成功，用于添加，跟 setnx 效果一样。由于 Redis 的单线程命令处理机制，如果多个客户端同时执行，则只有一个客户端能设置成功，可以用作分布式锁的一种实现。 xx：键必须存在才可以设置成功，用于更新 获取值 get key，如果不存在返回 nil 批量设置值 mset key value [key value...] 批量获取值 mget key [key...] 批量操作命令可以有效提高开发效率，假如没有 mget，执行 n 次 get 命令需要 n 次网络时间 + n 次命令时间，使用 mget 只需要 1 次网络时间 + n 次命令时间。 Redis 可以支持每秒数万的读写操作，但这指的是 Redis 服务端的处理能力，对于客户端来说一次命令处理命令时间还有网络时间。因为 Redis 的处理能力已足够高，对于开发者来说，网络可能会成为性能瓶颈。 计数 incr key incr 命令用于对值做自增操作，返回结果分为三种：① 值不是整数返回错误。② 值是整数，返回自增后的结果。③ 值不存在，按照值为 0 自增，返回结果 1。除了 incr 命令，还有自减 decr、自增指定数字 incrby、自减指定数组 decrby、自增浮点数 incrbyfloat。 不常用命令 追加值 append key value，可以向字符串尾部追加值 字符串长度 strlen key 设置并返回原值 getset key value 设置指定位置的字符 setrange key offset value 获取部分字符串 getrange key start end，start 和 end分别是开始和结束的偏移量，偏移量从 0 开始计算。 内部编码 字符串类型的内部编码有三种: int：8 个字节的长整形 embstr：小于等于 39 个字节的字符串 raw：大于 39 个字节的字符串 典型使用场景 缓存功能 Redis 作为缓存层，MySQL 作为存储层，首先从 Redis 获取数据，如果没有获取到就从 MySQL 获取，并将结果写回到 Redis，添加过期时间。 计数 Redis 可以实现快速计数功能，例如视频每播放一次就用 incy 把播放数加 1。 共享 Session 一个分布式 Web 服务将用户的 Session 信息保存在各自服务器，但会造成一个问题，出于负载均衡的考虑，分布式服务会将用户的访问负载到不同服务器上，用户刷新一次可能会发现需要重新登陆。为解决该问题，可以使用 Redis 将用户的 Session 进行集中管理，在这种模式下只要保证 Redis 是高可用和扩展性的，每次用户更新或查询登录信息都直接从 Redis 集中获取。 限速 例如为了短信接口不被频繁访问会限制用户每分钟获取验证码的次数或者网站限制一个 IP 地址不能在一秒内访问超过 n 次。可以使用键过期策略和自增计数实现。 哈希 哈希类型是指键值本身又是一个键值对结构，哈希类型中的映射关系叫做 field-value，这里的 value 是指 field 对于的值而不是键对于的值。 命令 设置值 hset key field value，如果设置成功会返回 1，反之会返回 0，此外还提供了 hsetnx 命令，作用和 setnx 类似，只是作用于由键变为 field。 获取值 hget key field，如果不存在会返回 nil。 删除 field hdel key field [field...]，会删除一个或多个 field，返回结果为删除成功 field 的个数。 计算 field 个数 hlen key 批量设置或获取 field-value 复制代码12hmget key field [field...]hmset key field value [field value...] hmset 需要的参数是 key 和多对 field-value，hmget 需要的参数是 key 和多个 field。 判断 field 是否存在 hexists key field，存在返回 1，否则返回 0。 获取所有的 field hkeys key，返回指定哈希键的所有 field。 获取所有 value hvals key，获取指定键的所有 value。 获取所有的 field-value hgetall key，获取指定键的所有 field-value。 计数 hincrby key field 和 hincrbyfloat key field，作用和 incrby 和 incrbyfloat 一样，作用域是 field。 计算 value 的字符串长度 hstrlen key field 内部编码 哈希类型的内部编码有两种： ziplist 压缩列表：当哈希类型元素个数和值小于配置值（默认 512 个和 64 字节）时会使用 ziplist 作为内部实现，使用更紧凑的结构实现多个元素的连续存储，在节省内存方面比 hashtable 更优秀。 hashtable 哈希表：当哈希类型无法满足 ziplist 的条件时会使用 hashtable 作为哈希的内部实现，因为此时 ziplist 的读写效率会下降，而 hashtable 的读写时间复杂度都为 O(1)。 使用场景 缓存用户信息，有三种实现： 原生字符串类型：每个属性一个键。 复制代码123set user:1:name tomset user:1:age 23set user:1:city xi'an优点：简单直观，每个属性都支持更新操作。 缺点：占用过多的键，内存占用量较大，用户信息内聚性差，一般不会在生产环境使用。 序列化字符串类型：将用户信息序列化后用一个键保存。 复制代码1set user:1 serialize(userInfo)优点：编程简单，如果合理使用序列化可以提高内存使用率。 缺点：序列化和反序列化有一定开销，同时每次更新属性都需要把全部数据取出进行反序列化，更新后再序列化到 Redis。 哈希类型：每个用户属性使用一对 field-value，但只用一个键保存。 复制代码1hmset user:1 name tom age 23 city xi'an优点：简单直观，如果合理使用可以减少内存空间使用。 缺点：要控制哈希在 ziplist 和 hashtable 两种内部编码的转换，hashtable 会消耗更多内存。 列表 列表类型是用来存储多个有序的字符串，列表中的每个字符串称为元素，一个列表最多可以存储 2^32^-1 个元素。可以对列表两端插入（push）和弹出（pop），还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是一种比较灵活的数据结构，它可以充当栈和队列的角色，在实际开发中有很多应用场景。 列表类型有两个特点：① 列表中的元素是有序的，可以通过索引下标获取某个元素或者某个范围内的元素列表。② 列表中的元素可以重复。 命令 添加操作 从右边插入元素：rpush key value [value...] 从左到右获取列表的所有元素：lrange 0 -1 从左边插入元素：lpush key value [value...] 向某个元素前或者后插入元素：linsert key before|after pivot value，会在列表中找到等于 pivot 的元素，在其前或后插入一个新的元素 value。 查找 获取指定范围内的元素列表：lrange key start end，索引从左到右的范围是 0N-1，从右到左是 -1-N，lrange 中的 end 包含了自身。 获取列表指定索引下标的元素：lindex key index，获取最后一个元素可以使用 lindex key -1。 获取列表长度：llen key 删除 从列表左侧弹出元素：lpop key 从列表右侧弹出元素：rpop key 删除指定元素：lrem key count value，如果 count 大于 0，从左到右删除最多 count 个元素，如果 count 小于 0，从右到左删除最多个 count 绝对值个元素，如果 count 等于 0，删除所有。 按照索引范围修剪列表：ltrim key start end，只会保留 start ~ end 范围的元素。 修改 修改指定索引下标的元素：lset key index newValue。 阻塞操作 阻塞式弹出：blpop/brpop key [key...] timeout，timeout 表示阻塞时间。 当列表为空时，如果 timeout = 0，客户端会一直阻塞，如果在此期间添加了元素，客户端会立即返回。 如果是多个键，那么brpop会从左至右遍历键，一旦有一个键能弹出元素，客户端立即返回。 如果多个客户端对同一个键执行 brpop，那么最先执行该命令的客户端可以获取弹出的值。 内部编码 列表的内部编码有两种： ziplist 压缩列表：跟哈希的 zipilist 相同，元素个数和大小小于配置值（默认 512 个和 64 字节）时使用。 linkedlist 链表：当列表类型无法满足 ziplist 的条件时会使用linkedlist。 Redis 3.2 提供了 quicklist 内部编码，它是以一个 ziplist 为节点的 linkedlist，它结合了两者的优势，为列表类提供了一种更为优秀的内部编码实现。 使用场景 消息队列 Redis 的 lpush + brpop 即可实现阻塞队列，生产者客户端使用 lpush 从列表左侧插入元素，多个消费者客户端使用 brpop 命令阻塞式地抢列表尾部的元素，多个客户端保证了消费的负载均衡和高可用性。 文章列表 每个用户有属于自己的文章列表，现在需要分页展示文章列表，就可以考虑使用列表。因为列表不但有序，同时支持按照索引范围获取元素。每篇文章使用哈希结构存储，例如每篇文章有三个属性，title、timestamp 和 content： hmset article:k title t timestamp 147651524 content c。 向用户文章列表添加文章，user:{id}:articles 作为用户文章列表的键： lpush user:k:articles article:k。 分页获取用户文章列表，例如以下伪代码获取用户 id = 1 的前 10 篇文章。 复制代码123articles = lrange user:1:articles 0 9for article in {articles}    hgetall {article} 使用列表类型保存和获取文章列表存在两个问题：① 如果每次分页获取的文章个数较多，需要执行多次 hgetall 操作，此时可以考虑使用 Pipeline 批量获取，或者考虑将文章数据序列化为字符串类型，使用 mget 批量获取。② 分页获取文章列表时，lrange 命令在列表两端性能较好，但如果列表大，获取中间范围的元素性能会变差，可以考虑将列表做二级拆分，或使用 Redis3.2 的 quicklist。 lpush + lpop = 栈 lpush + rpop = 队列 lpush + ltrim = 优先集合 lpush + brpop = 消息队列 集合 集合类型也是用来保存多个字符串元素，和列表不同的是集合不允许有重复元素，并且集合中的元素是无序的，不能通过索引下标获取元素。一个集合最多可以存储 2^32^-1 个元素。Redis 除了支持集合内的增删改查，还支持多个集合取交集、并集、差集。 命令 集合内操作 添加元素 sadd key element [element...]，返回结果为添加成功的元素个数。 删除元素 srem key element [element...]，返回结果为成功删除的元素个数。 计算元素个数 scard key，时间复杂度为 O(1)，会直接使用 Redis 内部的遍历。 判断元素是否在集合中 sismember key element，如果存在返回 1，否则返回 0。 随机从集合返回指定个数个元素 srandmember key [count]，如果不指定 count 默认为 1。 从集合随机弹出元素 spop key，可以从集合中随机弹出一个元素。 获取所有元素 smembers key 集合间操作 求多个集合的交集 sinter key [key...] 求多个集合的并集 sunion key [key...] 求多个集合的差集 sdiff key [key...] 保存交集、并集、差集的结果 复制代码123sinterstore destination key [key...]sunionstore destination destination key [key...]sdiffstore destination key [key...] 集合间的运算在元素较多的情况下会比较耗时，所以 Redis 提供了这三个指令将集合间交集、并集、差集的结果保存在 destination key 中。 内部编码 集合类型的内部编码有两种： intset 整数集合：当集合中的元素个数小于配置值（默认 512 个时），使用 intset。 hashtable 哈希表：当集合类型无法满足 intset 条件时使用 hashtable。当某个元素不为整数时，也会使用 hashtable。 使用场景 集合类型比较典型的使用场景是标签，例如一个用户可能与娱乐、体育比较感兴趣，另一个用户可能对例时、新闻比较感兴趣，这些兴趣点就是标签。这些数据对于用户体验以及增强用户黏度比较重要。 给用户添加标签 复制代码1234sadd user:1:tags tag1 tag2 tag5sadd user:2:tags tag3 tag4 tag5...sadd user:k:tags tagx tagy tagz 给标签添加用户 复制代码1234sadd tag:1:users user:1 user:3sadd tag:2:users user:1 user:4 user:5...sadd tag:k:users user:x user:y ... 用户和标签的关系维护应该在一个事务内执行，防止部分命令失败造成的数据不一致。 删除用户标签 复制代码1srem user:1:tags tag1 tag5 删除标签下的用户 复制代码1srem tag:1:users user:1 删除也同样应该放在一个事务中。 求两个用户共同感兴趣的标签 复制代码1sinter user:1:tags user:2:tags sadd = 标签 spop/srandmember = 生成随机数，比如抽奖 sadd + sinter = 社交需求 有序集合 有序集合保留了集合不能有重复成员的特性，不同的是可以排序。但是它和列表使用索引下标作为排序依据不同的是，他给每个元素设置一个分数（score）作为排序的依据。有序集合提供了获取指定分数和元素查询范围、计算成员排名等功能。 数据结构 是否允许元素重复 是否有序 有序实现方式 应用场景 列表 是 是 下标 时间轴，消息队列 集合 否 否 / 标签，社交 有序集合 否 是 分值 排行榜，社交 命令 集合内 添加成员 zadd key score member [score member...]，返回结果是成功添加成员的个数 Redis 3.2 为 zadd 命令添加了 nx、xx、ch、incr 四个选项： nx：member 必须不存在才可以设置成功，用于添加 xx：member 必须存在才能设置成功，用于更新 ch：返回此次操作后，有序集合元素和分数变化的个数 incr：对 score 做增加，相当于 zincrby zadd 的时间复杂度为 O(logn)，sadd 的时间复杂度为 O(1)。 计算成员个数 zcard key，时间复杂度为 O(1)。 计算某个成员的分数 zscore key member ，如果不存在则返回 nil。 计算成员排名 zrank key member，从低到高返回排名 zrevrank key member，从高到低返回排名 删除成员 zrem key member [member...]，返回结果是成功删除的个数。 增加成员的分数 zincrby key increment member 返回指定排名范围的成员 zrange key start end [withscores] zrevrange key start end [withscores] zrange 从低到高返回，zrevrange 从高到底返回，如果加上 withscores 选项同时会返回成员的分数。 返回指定分数范围的成员 zrangebyscore key min max [withscores] [limit offset count] zrevrangebyscore key min max [withscores] [limit offset count] zrangebyscore 从低到高返回，zrevrangebyscore 从高到底返回，如果加上 withscores 选项同时会返回成员的分数。[limit offset count] 可以限制输出的起始位置和个数。 返回指定分数范围成员个数 zcount key min max 删除指定排名内的升序元素 zremrangebyrank key start end 删除指定分数范围内的成员 zremrangebyscore key min max 集合间的操作 交集 zinterstore destination numkeys key [key...] [weights weight [weight...]] [aggregate sum|min|max] destination：交集结果保存到这个键 numkeys：要做交集计算键的个数 key [key...]：需要做交集计算的键 weights weight [weight...]：每个键的权重，默认 1 aggregate sum|min|max：计算交集后，分值可以按和、最小值、最大值汇总，默认 sum 并集 zunionstore destination numkeys key [key...] [weights weight [weight...]] [aggregate sum|min|max] 内部编码 有序集合的内部编码有两种： ziplist 压缩列表：当有序集合元素个数和值小于配置值（默认128 个和 64 字节）时会使用 ziplist 作为内部实现。 skiplist 跳跃表：当 ziplist 不满足条件时使用，因为此时 ziplist 的读写效率会下降。 使用场景 有序集合的典型使用场景就是排行榜系统。 例如用户 mike 上传了一个视频并添加了 3 个赞，可以使用有序集合的 zadd 和 zincrby： 复制代码1zadd user:ranking:2020_06_19 3 mike 如果之后再获得一个赞，可以使用 zincrby： 复制代码1zincrby user:ranking:2020_06_19 1 mike 例如需要将用户 tom 从榜单删除，可以使用 zrem： 复制代码1zrem user:ranking:2020_06_19 tom 展示获取赞数最多的十个用户： 复制代码1zrevrange user:ranking:2020_06_19 0 9 展示用户信息及用户分数，将用户名作为键后缀，将用户信息保存在哈希类型中，至于用户分数和排名可以使用 zscore 和 zrank： 复制代码123hgetall user:info:tomzscore user:ranking:2020_06_19 tomzrank user:ranking:2020_06_19 tom 键管理 单个键管理 键重命名 rename key newkey 如果 rename 前键已经存在，那么它的值也会被覆盖。 为了防止强行覆盖，Redis 提供了 renamenx 命令，确保只有 newkey 不存在时才被覆盖。由于重命名键期间会执行 del 命令删除旧的键，如果键对应值比较大会存在阻塞的可能。 随机返回一个键 random key 键过期 expire key seconds：键在 seconds 秒后过期 expireat key timestamp：键在秒级时间戳 timestamp 后过期 如果过期时间为负值，键会被立即删除，和 del 命令一样。 persist 命令可以将键的过期时间清除。 对于字符串类型键，执行 set 命令会去掉过期时间，set 命令对应的函数 setKey 最后执行了 removeExpire 函数去掉了过期时间。 Redis 不支持二级数据结构（例如哈希、列表）内部元素的过期功能，例如不能对列表类型的一个元素设置过期时间。 setex 命令作为 set + expire 的组合，不单是原子执行并且减少了一次网络通信的时间。 键迁移 move move key db move 命令用于在 Redis 内部进行数据迁移，move key db 就是把指定的键从源数据库移动到目标数据库中。 dump + restore dump key restore key ttl value 可以实现在不同的 Redis 势力之间进行数据迁移，分为两步： ① 在源 Redis 上，dump 命令会将键值序列化，格式采用 RDB 格式。 ② 在目标 Redis 上，restore 命令将上面序列化的值进行复原，ttl 参数代表过期时间， ttl = 0 则没有过期时间。 整个迁移并非原子性的，而是通过客户端分步完成，并且需要两个客户端。 migrate 实际上 migrate 命令就是将 dump、restore、del 三个命令进行组合，从而简化了操作流程。migrate 具有原子性，且支持多个键的迁移，有效提高了迁移效率。实现过程和 dump + restore 类似，有三点不同： ① 整个过程是原子执行，不需要在多个 Redis 实例开启客户端。 ② 数据传输直接在源 Redis 和目标 Redis 完成。 ③ 目标 Redis 完成 restore 后会发送 OK 给源 Redis，源 Redis 接收后会根据 migrate 对应的选项来决定是否在源 Redis 上删除对应的键。 命令 作用域 原子性 支持多个键 move Redis 实例内部 是 否 dump + restore Redis 实例之间 否 否 migrate Redis 实例之间 是 是 遍历键 全量遍历键 keys pattern *代表匹配任意字符，? 匹配一个字符，[] 匹配部分字符，例如 [1,3] 匹配 1 和 3， [1-3] 匹配 1 到 3 的任意数字，\用来做转义。 keys * 遍历所有的键，一般不在生产环境使用，在以下情况可以使用： ① 在一个不对外提供服务的 Redis 从节点上执行，不会阻塞客户端的请求，但会影响主从复制。 ② 如果确定键值总数比较少可以执行。 渐进式遍历 Redis 从 2.8 版本后提供了一个新的命令 scan，能有效解决 keys 存在的问题。和 keys 遍历所有键不同，scan 采用渐进式遍历的方式解决阻塞问题，每次 scan 的时间复杂度为 O(1)，但是要真正实现 keys 的功能可能需要执行多次 scan。 复制代码1scan cursor [match pattern] [count number] cursor 是必须参数，代表一个游标，第一次遍历从 0 开始，每次 scan 完会返回当前游标的值，直到值为 0 表示遍历结束。 match pattern 是可选参数，作用是模式匹配。 count number 是可选参数，作用是表明每次要遍历的键个数，默认值为 10。 除了 scan 外，Redis 提供了面向哈希、集合、有序集合的扫描遍历命令，解决了 hgetall、smembers、zrange 可能产生的阻塞问题，对应命令分别为 hscan、sscan、zscan。 渐进式遍历可以有效解决 keys 命令可能产生的阻塞问题，但是如果在 scan 过程中有键的变化，那么遍历效果可能会遇到问题：新增的键没有被遍历到，遍历了重复的键等情况。 数据库管理 切换数据库 select dbIndex Redis 中默认配置有 16 个数据库，例如 select 0 将切换到第一个数据库，数据库之间的数据是隔离的。 flushdb/flushall 用于清除数据库，flushdb 只清除当前数据库，flushall 会清除所有数据库。如果当前数据库键值数量比较多，flushdb/flushall 存在阻塞 Redis 的可能性。 总结 Redis 提供 5 种数据结构，每种数据结构都有多种内部编码实现。 纯内存存储、IO 多路复用计数、单线程架构是造就 Redis 高性能的三个因素。 由于 Redis 的单线程结构，所以需要每个命令能被快速执行完，否则会存在阻塞的可能。 批量操作（例如 mget、mset、hmset 等）能够有效提高命令执行的效率，但要注意每次批量操作的个数和字节数。 persist 命令可以删除任意类型键的过期时间，但 set 也会删除字符串类型键的过期时间。 move、dump + restore、migrate 是 Redis 发展过程中三种迁移键的方式，其中 move 命令基本废弃，migrate 命令用原子性的方式实现了 dump + restore，并且支持批量操作，是 Redis Cluster 实现水平扩容的重要工具。 scan 命令可以解决 keys 命令可能带来的阻塞问题，同时 Redis 还提供了 hscan、sscan、zscan 渐进式遍历 hash、set、zset。 高级功能 慢查询分析 许多系统（例如 MySQL）提供了慢查询日志帮助开发和运维任意定位系统存在的慢操作，慢查询日志是系统在命令执行前后计算每条命令的执行时间，当超过预设阈值，就将这条命令的相关信息（例如发生时间、耗时、命令的详细信息）记录下来，Redis 也提供了类似的功能。 Redis 客户端执行一条命令分为四步：发送命令、命令排队、命令执行、返回结果。慢查询只统计第三步的时间，所有没有慢查询不代表客户端没有超时问题。 当超过 slowlog-log-slower-than 阈值（默认 10000 微秒）时，该命令会被记录在慢查询日志，如果设置阈值为 0 会记录所有命令，如果设置为负值对所有命令都不会记录。Redis 使用了一个列表来存储慢查询日志，一个新的命令满足慢查询条件时被插入到这个列表中，当慢查询日志列表处于最大长度时，最早插入的一个命令将从列表中移出。slowlog-max-len 是慢查询列表的最大长度。 在 Redis 中有两种修改配置的方法，一种是修改配置文件，另一种是使用 config set 命令动态修改，如果要将配置持久化到本地配置文件，需要执行 config rewrite 命令。 虽然慢查询日志存放在 Redis 的内存列表中，但 Redis 并没有暴露这个列表的键，而是通过一组命令来实现对慢查询日志的访问和管理。 获取慢查询日志：slowlog get [n]，n 可以指定条数。 获取慢查询日志列表当前长度：slowlog len。 慢查询日志重置：slowlog reset，实际是队列做清理操作。 使用时注意： slowlog-max-len 配置建议：线上建议调大慢查询列表，记录慢查询时 Redis 会对长命令阶段，并不会占用大量内存。增大慢查询列表可以减缓慢查询被剔除的可能，线上可以设置为 1000 以上。 slowlog-log-slower-than 配置建议：默认 10 毫秒判断为慢查询，需要根据 Redis 并发量调整。由于 Redis 采用单线程响应命令，对于高流量场景，可以设置为 1 毫秒。 慢查询只记录命令执行时间，并不包括命令排队和网络传输时间。因此客户端执行命令的时间会大于命令实际时间，因为命令执行排队机制，慢查询会导致其他所有命令级联阻塞，所以当客户端出现请求超时，需要检查该时间点是否有对应的慢查询，从而分析出是否为慢查询导致命令级联阻塞。 由于慢查询日志是一个 FIFO 的队列，因此慢查询比较多的情况下会丢失部分慢查询命令，为了防止这种情况可以定期执行 slow get 命令将慢查询日志持久化到其他存储中（例如 MySQL）。 Redis Shell Redis 提供了 redis-cli、redis-server、redis-benchmark 等 Shell 工具。 redis-cli redis-cli 除了 -h、-p 还有一些其他的参数： -r：代表命令将执行多次 -i：代表每隔几秒执行一次命令 -x：代表从标准输入读取数据作为 redis-cli 的最后一个参数 -c：连接 Redis Cluster 节点时需要使用的，可以防止 moved 和 ask 异常。 -a：如果 Redis 设置了密码，可以用 -a 选项。 --scan/--pattern：用于扫描指定模式的键，相对于使用 scan 命令。 --slave：把当前客户端模拟成当前 Redis 节点的从节点，可以用来获取当前 Redis 节点的更新操作。 --rdb：该选项会请求 Redis 实例生成并发送 RBD 持久化文件，保存在本地。可使用它做持久化文件的定期备份。 --pipe：用于将命令封装成 Redis 通信协议定义的数据格式，批量发送给 Redis 执行。 --bigkeys：使用 scan 命令对 Redis 的键进行采样，从中找到内存占用比较大的键值，这些键值可能是系统的瓶颈。 --eval：用于指定 Lua 脚本。 --latency：检测网络延迟。 --stat：实时获取 Redis 的重要统计信息。 --no-raw：要求命令的返回结果必须是原始的格式。 --raw：要求返回结果是格式化后的结果。 redis-server 除了启动 Redis 外，还有一个 --test-memory 选项，该选项可以用来检测当前操作系统能否稳定地分配指定容量地内存给 Redis，通过这种检测可以有效避免因为内存问题造成 Redis 崩溃。 redis-benchmark 可以为 Redis 做基准性能测试，它提供了很多选项帮助开发和运维人员测试 Redis 的相关性能。 相关选项： -c：代表客户端的并发数量。 -n：代表客户端请求总量。 -P：每个请求 pipeline 的数据量，默认为 1。 -k：代表客户端是否使用 keepalive，1 为使用，0 为不使用，默认 1。 -t：对指定命令进行基准测试。 --csv：将结果按照 csv 格式输出，便于后续处理。 Pipeline Redis 客户端执行一条命令需要经过发送命令、命令排队、执行命令、返回结果。其中第一步和第四步称为 RTT 往返时间。Redis 提供了批量操作命令，有效地节约 RTT。但大部分命令不支持批量操作，例如要执行 n 次 hgetall 命令，并没有 mhgetall 命令，需要消耗 n 次 RTT。 Pipelin 流水线机制能改善上述问题，它能将一组 Redis 命令进行组装，通过一次 RTT 传输给 Redis，再将这组命令地执行结果按顺序返回给客户端。 Pipeline 执行速度一般比逐条执行要快，客户端和服务端地网络延时越大效果就越明显。 和原生批量命令的区别： 原生批量命令是原子的，Pipeline 是非原子的。 原生批量命令是一个命令对应多个 key，Pipeline 支持多个命令。 原生批量命令是 Redis 服务端支持实现的，而 Pipeline 需要服务端和客户端共同实现。 事务 Redis 提供了简单的事务功能，将一组需要一起执行的命令放到 multi 和 exec 两个命令之间。multi 代表事务开始，exec 命令代表事务结束，它们之间的命令是原子顺序执行的。如果要停止事务的执行，可以使用 discard 命令代替 exec。 事务中的命令错误分为命令错误和运行时错误： 例如 set 写成了 sett，属于语法错误，会造成整个事务无法执行。 例如把 sadd 写成了 zadd，这种就是运行时错误，Redis 不支持回滚，错误前的语句会执行成功，开发人员需要自己修复这类问题。 有些应用场景需要在事务之前，确保事务中的 key 没有被其他客户端修改过才执行事务，否则不执行（类似乐观锁）。Redis 提供了 watch 命令解决这类问题。 例如客户端1 在执行 multi 之前执行了 watch 命令，客户端2 在客户端1 执行 exec 之前修改了 key 的值，此时事务会执行失败，返回 nil。 Redis 提供了简单的事务，之所以说简单是因为它不支持事务中的回滚特性，同时无法实现命令之间的逻辑关系计算。 Bitmaps Bitmaps 本身不是一种数据结构，实际上它就是字符串，但是它可以对字符串的位进行操作。 Bitmaps 单独提供了一套命令，所以在 Redis 使用 Bitmaps 和使用字符串的方法不太相同，可以把 Bitmaps 看作一个以位为单位的数组，数组的每个单元只能存储 0 和 1，数组的下标叫做偏移量。 命令 例：将每个独立用户是否访问过网站存放在 Bitmaps 中，将访问过的用户记作 1，没有访问过的记作 0，偏移量作为用户的 id。 设置值 复制代码1setbit key offset value 设置键的第 offset 个位的值，假设有 20 个用户，id 为 0、5、11、15、19 的用户对网站进行了访问，那么初始化如下： 复制代码12345setbit unique:users:2020-06-20 0 1setbit unique:users:2020-06-20 5 1setbit unique:users:2020-06-20 11 1setbit unique:users:2020-06-20 15 1setbit unique:users:2020-06-20 19 1 很多应用的用户 id 直接以一个指定数字开头，例如 10000，直接将用户 id 与 Bitmaps 的偏移量对应势必会造成一定浪费，通常做法是每次做 setbit 操作时将用户 id 减去这个指定数字。在第一次初始化 Bitmaps 时，如果偏移量非常大，那么整个初始化过程会执行比较慢，可能造成阻塞。 获取值 复制代码1getbit key offset 获取键的第 offset 个位的值，例如获取 id 为 8 的用户是否在 2020-06-20 这天访问过： 复制代码1getbit unique:users:2020-06-20 8 获取指定范围值为 1 的个数 复制代码1bitcount key [start end] 例如获取 2020-06-20 这天访问过的用户数量 复制代码1bitcount unique:users:2020-06-20 start 和 end 代表起始和结束字节数。 Bitmaps 间的运算 复制代码1bitop op destkey key [key...] bitop 是一个复合操作，它可以做交集、并集、非、异或并将结果保存到 destkey 中。 例如计算 2020-06-20 和 2020-06-21 都访问过网站的用户数量： 复制代码12bitop and unique:users:and:2020-06-20_21 unique:users:2020-06-20 unique:users:2020-06-21bitcount unique:users:and:2020-06-20_21 例如计算 2020-06-20 和 2020-06-21 任意一天访问过网站的用户数量： 复制代码12bitop or unique:users:or:2020-06-20_21 unique:users:2020-06-20 unique:users:2020-06-21bitcount unique:users:or:2020-06-20_21 计算第一个值为 tartgetBit 的偏移量 复制代码1bitops key targetBit [start] [end] 例如计算 2020-06-20 当前访问网站的最小用户 id： 复制代码1bitops unique:users:2019-06-20 1 假设网站的活跃用户量很大，使用 Bitmaps 相比 set 可以节省很多内存，但如果活跃用户很少就会浪费内存。 HyperLogLog HyperLogLog 不是一种新的数据结构，实际也是字符串类型，是一种基数算法。提供 HyperLogLog 可以利用极小的内存空间完成独立总数的统计，数据集可以是 IP、Email、ID 等。 添加 pfadd key element [element...]，如果添加成功会返回 1 计算独立用户数 pfcount key [key...] 合并 pfmerge destkey sourcekey [sourcekey...] HyperLogLog 内存占用量非常小，但是存在错误率，开发者在进行数据结构选型时只需要确认如下两条： 只为了计算独立总数，不需要获取单条数据。 可以容忍一定误差率，毕竟 HyperLogLog 在内存占用量上有很大优势。 发布订阅 Redis 提供了基于发布/订阅模式的消息机制，此种模式下，消息发布者和订阅者不进行直接通信，发布者客户端向指定的频道（channel）发送消息，订阅该频道的每个客户端都可以收到该消息。 命令 发布消息 publish channel message，返回结果为订阅者的个数。 订阅消息 subscribe channel [channel..]，订阅者可以订阅一个或多个频道。 客户端在执行订阅命令后会进入订阅状态，只能接收 subscribe、psubscribe、unsubscribe、punsubscribe 的四个命令。新开启的订阅客户端，无法收到该频道之前的消息，因为 Redis 不会对法捕的消息进行持久化。 和很多专业的消息队列系统如 Kafka、RocketMQ 相比，Redis 的发布订阅略显粗糙，例如无法实现消息堆积和回溯，但胜在足够简单，如果当前场景可以容忍这些缺点，也是一个不错的选择。 取消订阅 unsubscribe [channel [channel...]] 客户端可以通过 unsubscribe 命令取消对指定频道的订阅，取消成功后不会再收到该频道的发布消息。 按照模式订阅和取消订阅 psubscribe pattern [pattern...] punsubscribe pattern [pattern...] 这两种命令支持 glob 风格，例如订阅所有以 it 开头的频道：psubscribe it* 查询订阅 查看活跃的频道：pubsub channels [pattern]，活跃频道是指当前频道至少有一个订阅者。 查看频道订阅数：pubsub numsub [channel ...] 查看模式订阅数：pubsub numpat 使用场景 聊天室、公告牌、服务之间利用消息解耦都可以使用发布订阅模式，以服务器解耦为例：视频管理系统负责管理视频信息，用户通过各种客户端获取视频信息。 假如视频管理员在视频管理系统中对视频信息进行了更新，希望及时通知给视频服务端，就可以采用发布订阅模式，发布视频信息变化的消息到指定频道，视频服务订阅这个频道及时更新视频信息，通过这种方式实现解耦。 视频服务订阅 video:changes 频道： 复制代码1subscribe video:changes 视频管理系统发布消息到 video:changes 频道： 复制代码1publish video:changes "video1,video3,video5" 视频服务收到消息，对视频信息进行更新.. GEO Redis 3.2 版本提供了 GEO 地理信息定位功能，支持存储地理位置信息用来实现诸如附近位置、摇一摇这一类依赖于地理位置信息的功能。 增加地理位置信息 复制代码1geoadd key longitude latitude member [longitude latitude member...] longitude、latitude、member 分别是该地理位置的经度、纬度、成员。 例如添加北京的地理位置信息： 复制代码1geoadd cities:locations 116.28 39.55 beijing 返回结果表示成功添加的个数，如果需要更新地理位置信息仍然可以使用 geoadd 命令，返回结果为 0。 获取地理位置信息 复制代码1getpos key member [member...] 获取两个地理位置的距离 复制代码1geodist key member1 member2 [unit] 其中 unit 代表返回结果的单位，包含 m 米、km 公里、mi 英里、ft 英尺。 删除地理位置信息 复制代码1zrem key member GEO 没有提供删除成员的命令，但由于它底层是 zset，可以使用 zrem 删除。 总结 慢查询中有两个重要参数 slowlog-log-slower-than 和 slowlog-max-len。 慢查询不包括命令网络传输和排队时间。 有必要将慢查询定期存放。 Pipeline 可以有效减少 RTT 次数，但每次 Pipeline 的命令数量不能无节制。 Redis 可以使用 Lua 脚本创造出原子、高效、自定义命令组合。 Bitmaps 可以用来做独立用户统计，有效节省内存。 Bitmaps 中 setbit 一个大的偏移量，由于申请大量内存会导致阻塞。 HyperLogLog 虽然在统计独立总量时存在一定误差，但是节省的内存量十分惊人。 Redis 的发布订阅相比许多专业消息队列系统功能较弱，不具备息堆积和回溯能力，但胜在足够简单。 Redis 3.2 提供了 GEO 功能，用来实现基于地理位置信息的应用，底层实现是 zset。 客户端 客户端通信协议 客户端与服务端的通信协议是在 TCP 协议之上构建的，Redis 制定了 RESP（Redis 序列化协议）实现客户端与服务端的正常交互，这种协议简单高效，既能够被机器解析，又容易被人类识别。例如客户端发送一条 set hello world 命令给服务端，按照 RESP 的标准客户端需要将其封装为如下格式： 复制代码1234567*3//表示有3个参数$3//表示参数的字节数SET$5hello$5world 这样 Redis 服务端能够按照 RESP 将其解析为 set hello world，执行后回复的格式为 +OK。 返回结果格式： 状态回复：RESP 中第一个字节为 +。 错误回复：RESP 中第一个字节为 -。 整数回复：RESP 中第一个字节为 :。 字符串回复：RESP 中第一个字节为 $。 多条字符串回复：RESP 中第一个字节为 *。 有 RESP 提供的发送命令和返回结果的协议格式，各种编程语言就可以利用其来实现相应的 Redis 客户端。 Java 客户端 Jedis 在 maven 项目中添加相应的依赖即可： 复制代码1234567<dependencies>    <dependency>        <groupId>redis.clients</groupId>        <artifactId>jedis</artifactId>        <version>2.8.1</version>    </dependency></dependencies> 启动本地 Redis 服务器后，通过以下代码连接 Redis： 复制代码1Jedis jedis = new Jedis("127.0.0.1", 6379); 操作基本数据结构 操作五种数据结构的示例： 复制代码12345678910111213141516171819202122232425262728293031323334353637383940public static void main(String[] args) {    Jedis jedis = new Jedis("127.0.0.1", 6379);    // string    String set = jedis.set("hello", "world");    System.out.println(set);//OK     String hello = jedis.get("hello");    System.out.println(hello);//world     Long counter = jedis.incr("counter");    System.out.println(counter);//1     // hash    jedis.hset("hash", "f1", "v1");    jedis.hset("hash", "f2", "v2");    Map<String, String> hash = jedis.hgetAll("hash");    System.out.println(hash);//{f1=v1, f2=v2}     // list    jedis.rpush("list", "1");    jedis.rpush("list", "2");    jedis.rpush("list", "3");    List<String> list = jedis.lrange("list", 0, -1);    System.out.println(list);//[1, 2, 3]     // set    jedis.sadd("set", "a");    jedis.sadd("set", "b");    jedis.sadd("set", "a");    Set<String> set1 = jedis.smembers("set");    System.out.println(set1);//[b, a]     // zset    jedis.zadd("zset", 33, "tom");    jedis.zadd("zset", 66, "peter");    jedis.zadd("zset", 99, "james");    Set<Tuple> zset = jedis.zrangeWithScores("zset", 0, -1);    System.out.println(zset);//[[[116, 111, 109],33.0], [[112, 101, 116, 101, 114],66.0], [[106, 97, 109, 101, 115],99.0]] } 序列化对象 序列化 Java 对象，导入以下依赖： 复制代码1234567891011<dependency>    <groupId>com.dyuproject.protostuff</groupId>    <artifactId>protostuff-runtime</artifactId>    <version>1.0.11</version></dependency> <dependency>    <groupId>com.dyuproject.protostuff</groupId>    <artifactId>protostuff-core</artifactId>    <version>1.0.11</version></dependency> 创建一个俱乐部实体类： 复制代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667public class Club implements Serializable {     private int id;    private String name;    private String info;    private Date createDate;    private int rank;     public Club(int id, String name, String info, Date createDate, int rank) {        this.id = id;        this.name = name;        this.info = info;        this.createDate = createDate;        this.rank = rank;    }     public int getId() {        return id;    }     public void setId(int id) {        this.id = id;    }     public String getName() {        return name;    }     public void setName(String name) {        this.name = name;    }     public String getInfo() {        return info;    }     public void setInfo(String info) {        this.info = info;    }     public Date getCreateDate() {        return createDate;    }     public void setCreateDate(Date createDate) {        this.createDate = createDate;    }     public int getRank() {        return rank;    }     public void setRank(int rank) {        this.rank = rank;    }     @Override    public String toString() {        return "Club{" +                "id=" + id +                ", name='" + name + '\'' +                ", info='" + info + '\'' +                ", createDate=" + createDate +                ", rank=" + rank +                '}';    }} 序列化工具类： 复制代码123456789101112131415161718192021222324252627282930313233343536public class ProtoStuffSerializeUtils {     private static Schema<Club> schema = RuntimeSchema.createFrom(Club.class);     public static byte[] serialize(final Club club) {        final LinkedBuffer buffer = LinkedBuffer.allocate(LinkedBuffer.DEFAULT_BUFFER_SIZE);        try {            return serializeInternal(club, schema, buffer);        } catch (final Exception e) {            throw new IllegalStateException(e.getMessage(), e);        } finally {            buffer.clear();        }    }     public static Club deserialize(final byte[] bytes) {        try {            Club club = deserializeInternal(bytes, schema.newMessage(), schema);            if (club != null) {                return club;            }        } catch (final Exception e) {            throw new IllegalStateException(e.getMessage(), e);        }        return null;    }     private static <T> byte[] serializeInternal(final T source, final Schema<T> schema, final LinkedBuffer buffer) {        return ProtostuffIOUtil.toByteArray(source, schema, buffer);    }     private static <T> T deserializeInternal(final byte[] bytes, final T result, final Schema<T> schema) {        ProtostuffIOUtil.mergeFrom(bytes, result, schema);        return result;    }} 测试： 复制代码1234567891011121314public static void main(String[] args) {    Jedis jedis = new Jedis("127.0.0.1", 6379);     // 序列化    String key ="club:1";    Club club = new Club(1, "LA", "湖人", new Date(), 1);    byte[] clubBytes = ProtoStuffSerializeUtils.serialize(club);    jedis.set(key.getBytes(), clubBytes);     // 反序列化    byte[] resultBytes = jedis.get(key.getBytes());    Club resultClub = ProtoStuffSerializeUtils.deserialize(resultBytes);    System.out.println(resultClub);//Club{id=1, name='LA', info='湖人', createDate=Sat Jun 20 12:26:54 CST 2020, rank=1}} 连接池 之前的连接方式是直连方式，所谓直连是指 Jedis 每次都会新建 TCP 连接，使用后再断开连接，对于频繁访问 Redis 的场景显然不是高效的使用方式。 生产方式中一般使用连接池的方式对 Jedis 连接进行管理，所有 Jedis 对象预先放在池子中，每次要连接 Redis，只需要在池子中借，用完了再归还给池子。 客户端连接 Redis 使用 TCP 连接，直连的方式每次需要建立 TCP 连接，而连接池的方式是可以预先初始化好的 Jedis 连接，所以每次只需要从 Jedis 连接池借用即可，而借用和归还操作是在本地进行的，只有少量的并发同步开销，远远小于新建 TCP 连接的开销。另外直连的方式无法限制 Jedis 对象的个数，在极端情况下可能会造成连接泄露，而连接池的形式可以有效的保护和控制资源的使用。 优点 缺点 直连 简单方便，适用于少量长期连接的场景。 存在每次连接关闭 TCP 连接的开销，资源无法控制可能出现连接泄露，Jedis 对象线程不安全 连接池 无需每次连接都生成 Jedis 对象降低开销，使用连接池的形式保护和控制资源的使用 相对于直连比较麻烦，尤其在资源的管理上需要很多参数来保证，一旦规划不合理也会出现问题 使用 Jedis 连接池操作的示例： 复制代码12345678910111213141516171819public static void main(String[] args) {    // 使用默认连接池配置    GenericObjectPoolConfig poolConfig = new GenericObjectPoolConfig();    // 初始化连接池    JedisPool jedisPool = new JedisPool(poolConfig, "127.0.0.1", 6379);    // 获取 Jedis 对象    Jedis jedis = null;    try{        jedis = jedisPool.getResource();        //。。。    }catch (Exception e){        e.printStackTrace();    }finally {        if(jedis!=null){            // 不是关闭连接，而是归还连接池            jedis.close();        }    }} 客户端管理 Redis 提供了客户端相关 API 对其状态进行监控和管理。 client list client list 命令能列出与 Redis 服务端相连的所有客户端连接信息，输出的每一行代表一个客户端信息，每行包括了十几个属性，重要的属性解释： id：客户端连接的唯一标识，这个 id 随着 Redis 的连接自增，重启 Redis 后会重置为 0。 addr：客户端连接的 ip 和端口。 fd：socket 的文件描述符，与 lsof 命令结果中的 fd 是同一个，如果 fd = -1代表当前客户端不是外部客户端，而是 Redis 内部的伪装客户端。 name：客户端的名字。 输入缓冲区：qbuf、qbuf-free。 Redis 为每个客户端分配了输入缓冲区，它的作用是将客户端发送的命令临时保存，同时 Redis 会从输入缓冲区拉取命令并执行，输入缓冲区为客户端发送命令到 Redis 执行命令提供了缓冲功能。qbuf 和 qbuf-free 分别代表这个缓冲区的总容量和剩余容量，Redis 没有提供相应的配置来规定每个缓冲区的大小，输入缓冲区会根据输入内容的大小的不同动态调整，只是要求每个客户端缓冲区的大小不能超过 1G，超过后客户端将被关闭。 输入缓冲区使用不当会产生两个问题： 一旦某个客户端的输入缓冲区超过 1G，客户端将被关闭。 输入缓冲区不受 maxmemory 控制，假设一个 Redis 示例设置了该值为 4G，已经存储了 2G，但如果输入缓冲区使用了 3G，可能会产生数据丢失、键值淘汰、OOM 等情况。 输入缓冲区过大主要是因为 Redis 的处理速度跟不上输入缓冲区的输入速度，并且每次进入输入缓冲区的命令包含了大量 bigkey，从而造成了输入缓冲区过大，还有一种情况就是 Redis 发生了阻塞，短期不能处理命令，造成客户端输入的命令挤压在了缓冲区。 监控输入缓冲区异常有两种方法： 定期执行 client list 命令，收集 qbuf 和 qbuf-free 找到异常的连接记录并分析，找出可能出问题的客户端。该方法可以精确分析每个客户端定位问题，但执行速度慢。 通过 info 命令的 info clients 模块，找到最大的输入缓冲区，设置报警阈值。该方法执行速度快，但是不能精确定位客户端。 输出缓冲区：obl、oll、omem Redis 为每个客户端分配了输出缓冲区，它的作用是保存命令执行的结果返回给客户端，为 Redis 和客户端交互返回结果提供缓冲。输出缓冲区按照客户端的不同分为普通客户端、发布订阅客户端、slave 客户端。obl 代表固定缓冲区的长度，oll 代表动态缓冲区列表的长度，omem 代表使用的字节数。 监控输出缓冲区的方法和输入缓冲区一样，提供 client list 和 info clients。 client setName 和 client getName client setName 用于给客户端设置名字，这样比较容易标识出客户端的来源。 如果想直接查看当前客户端的 name，可以使用 client getName。 client setName 和 client getName 命令可以作为标识客户端来源的一种方式，但是通常来说在 Redis 只有一个应用方使用的情况下，IP 和端口作为表示会更加清晰。当多个应用共同使用一个 Redis，那么此时 client setName 可以作为标识客户端的一个依据。 client kill 复制代码1client kill ip:port 此命令用于杀掉指定 IP 地址和端口号的客户端，由于一些原因需要手动杀掉客户端连接时，可以使用该命令。 client pause 复制代码1client pause timeout 该命令用于阻塞客户端，timeout 是阻塞时间，单位为毫秒，在此期间客户端连接将被阻塞。 适用场景： client pause 只对普通和发布订阅客户端有效，对于主从复制无效，因此可以让主从复制保持一致。 可以用一种可控的方式将客户端连接从一个 Redis 节点切换到另一个 Redis 节点。 monitor monitor 命令用于监控 Redis 正在执行的命令。但是一旦并发量过大，monitor 客户端的输出缓冲会暴涨，可能瞬间会占用大量内存。 客户端相关配置 timeout：检测客户端空闲连接的超时时间，一旦空闲时间到了 timeout，客户端将被关闭，如果设置为 0 就不进行检测。 maxclients：客户端最大连接数，这个参数会受到操作系统的限制。 tcp-keepalive：检测 TCP 连接活性的周期，默认值为 0，也就是不进行检测。如果需要设置，建议为 60，Redis 每隔一分钟会对它创建的 TCP 连接进行活性检测，防止大量死连接占用系统资源。 tcp-backlog：TCP 三次握手后，会将接受的连接放入队列中，tcp-backlog 就是队列的大小，默认值是 511，通常来说这个参数不需要调整。 客户端常见异常 无法从连接池获取连接 JedisPool 中的 Jedis 对象个数是有限的，默认是 8 个。如果对象全部被占用并且没有归还，调用者借用 Jedis 时就会阻塞等待，如果超过了最大等待时间 maxWaitMills 就会抛出异常。 还有一种情况就是设置了 blockWhenExhausted = false，那么调用者发现池子中没有资源时会立即抛出异常而不进行等待。 造成没有资源的原因： 客户端：高并发情况下连接池设置过小，供不应求，但正常情况下只需要比默认的 8 个大一点即可。 客户端：没有正确使用连接池，例如没有释放。 客户端：存在慢查询操作，这些慢查询持有的 Jedis 对象归还速度会比较慢。 服务端：客户端正常，服务端由于一些原因造成了客户端命令执行过程的阻塞。 客户端读写超时 Jedis 在调用 Redis 时，如果出现了读写超时，会抛出异常，造成该异常的原因： 读写超时时间设置得过短。 命令本身比较慢。 客户端与服务端网络不正常。 Redis 自身发生了阻塞。 客户端连接超时 Jedis 在调用 Redis 时，如果出现了连接超时，会抛出异常，造成该异常的原因： 连接超时时间设置得过短。 Redis 发生阻塞，造成 tcp-backlog 已满。 客户端与服务端网络不正常。 客户端缓冲区异常 Jedis 在调用 Redis 时，如果出现了客户端数据流异常，会抛出异常，造成该异常的原因： 输出缓冲区满。 长时间闲置连接被服务端主动断开。 不正常并发读写：Jedis 对象同时被多个线程并发操作，可能会出现该问题。 Lua 脚本正在执行 如果 Redis 当前正在执行 Lua 脚本，并且超过了 lua-time-limit，此时 Jedis 调用 Redis 时就会抛出异常。 加载持久化文件 Jedis 调用 Redis 时，如果 Redis 正在加载持久化文件，那么会抛出异常。 Redis 使用内存超过 maxmemory Jedis 执行写操作时，如果 Redis 的使用内存大于 maxmemor 的设置，会抛出异常。 客户端连接数过大 如果客户端连接数超过了 maxclients，新申请的连接会抛出异常。此时新的客户端连接执行任何命令都会返回错误结果。 一般可从两方面解决： 客户端：如果 maxclients 参数不是很小的化，应用方的客户端连接数基本不会超过 maxclients，通常来看是由于应用方对于 Redis 客户端使用不当造成的。此时如果应用方是分布式结构的话，可以通过下线部分应用节点使得 Redis 的连接数先降下来。从而让绝大部分节点可以正常允许，再通过查找程序 bug 或调整 maxclients 进行问题的修复。 服务端：如果客户端无法处理，而当前 Redis 为高可用模式，可以考虑做故障转移。 客户端案例分析 Redis 内存陡增 现象： 服务端：Redis 主节点内存陡增，几乎用满 maxmemory，而从节点内存并没有变化。 客户端：客户端产生了 OOM 异常，也就是 Redis 主节点使用的内存已经超过了 maxmemory 的设置，无法写入新的数据。 分析原因： ① 确实有大量写入，但是主从复制出现问题。 ② 如果主从复制正常，可以排查十分由客户端缓冲区造成主节点内存陡增，使用 info clinets 查询相关信息。如果客户端缓冲队列值很大，通过 client list 命令找到 omem 不正常的连接，一般来说为 0，因此不为 0 就是不正常的连接。有可能是因为客户端执行 monitor 造成的。 处理方法： 使用 client kil 杀掉这个连接，让其他客户端恢复正常即可。需要注意的有三点： 从运维层面禁止 monitor 命令，例如 rename-command 命令重置 monitor 为一个随机字符串。 禁止开发人员在生产中使用 monitor。 限制输出缓冲区的大小。 客户端周期性超时 现象： 客户端：客户端出现大量超时，并且是周期性的。 服务端：没有明显的异常，只是有一些慢查询操作。 分析原因： ① 网络：服务端和客户端之间的网络出现周期性问题，网络正常。 ② Redis 本身：观察 Redis 的日志统计，无异常。 ③ 客户端：发现只要慢查询出现，就会连接超时，因此是慢查询导致了连接超时。 处理方法： 从运维层面，监控慢查询，超过阈值就发出警报。 从开发层面，避免不正确的使用。 总结 RESP 保证了客户端与服务端的正常通信，是各种编程语言开发客户端的基础。 要选择社区活跃客户端，在实际项目中使用稳定版本的客户端。 区分 Jedis 直连和连接池的区别，在生产环境应该使用连接池。 Jedis.close() 在直连下是关闭连接，在连接池则是归还连接。 客户端输入缓冲区不能配置，强制限制在 1G 以内，但是不会受到 maxmemory 限制。 客户端输出缓冲区支持普通客户端、发布订阅客户端、复制客户端配置，但不会受到 maxmemory 限制。 Redis 的 timeout 配置可以自动关闭闲置客户端，tcp-keepalive 参数可以周期性检查关闭无效 TCP 连接。 monitor 命令虽然好用，但是在高并发下存在输出缓冲区暴涨的可能性。 info clients 帮助开发和运维找到客户端可能存在的问题。

历时20天春招终于上岸了，这期间真的收到朋友们帮助很多:-) ，特来回馈下朋友们，(虽然这个时间段很多人可能都上岸了) ，这是我自己整理的前端面试基础条目（不包含具体内容，你可以用来对自己做一个知识检索），一般面试考点都在其中了（看过的不少面经文章都整理进去了）。 https://github.com/linbudu599/FE-Basics 觉得有帮助的同学可以给个Star～ 如果有什么问题也可以私信我

背景：本科双非建筑学，硕士211计算机专硕 时间轴：2018.07（拿到2018理工场Elite Internship offer）—2019.06（拿到2019理工场Superday 直通卡）—2019.09（par面）——2019.10（offer） 2018年 STEM Day： 2018年还没有研究生入学前参加的PwC STEM Day，当时对Risk assurance下的Cyber Security最感兴趣，积极地第一个就跑去面试，是一个经理面的，先自我介绍，再问我有哪些技能，为什么想进这个部门。当时刚从建筑跨到计算机来，其实没有什么技能，面试官估计看我比较积极，就给了我实习offer。HR说有项目的时候会跟我联系。寒假的时候我申请了寒假实习，做了一份ot，包含逻辑题，算术题，英语写作等。今年三月份的时候联系过我有没有空实习，但他们好像只要研二或研三的，反正最后不了了之了。 2019年 STEM Day： 今年六月份的时候，学院统一安排去的STEM Day，主要也是RA部门招聘，还有Consulting和X-Venturer. RA下面的业务分成Cyber Security、Data Analytics和机器人流程自动化（RPA）。不同业务部门都有人在介绍和答疑，之后自己选择意向的部门排队面试。当天RPA面试的人最少，Data Analytics的人最多。我还是去了Cyber Security面试，本来是两个面试官的，其中一个是去年的那个经理，但是我进去那会儿经理打电话去了，是另一个面试官面的。 自我介绍 目前的研究方向 对web安全了解吗 常用的渗透工具会用哪些 最后应该是看到我去年拿了实习offer，今年就发了直通车，之后还指导我修改了一下简历，告诉了我一些做web安全常用的工具和靶场。 Par面： 09.06号进行了par面。这次面试官有两位，一位是合伙人，一位是RA部门管理方向的小姐姐。人都特别好，叫我不要紧张。距离上次面试之后我去短暂的实习了两个星期，交了一份最新的简历。 自我介绍 问我为什么跨专业（建筑学转为计算机） 为什么选择普华永道 自己有哪些优势，普华永道为什么要选择你 介绍一下目前的研究方向，研究生期间做过哪些工作 实习做了些什么 英语能力怎样 硕士期间主修课程及成绩（本来是应该带成绩单的，那天忘记了，所以面试官问） 是否有男朋友，未来的打算 在上学期间做过最有成就感的一件事情，你在这件事情中扮演的角色，是leader还是执行者. 可以选择深圳所和广州所的话，想去哪个所？ 我们工作很累的，可以接受吗？后面又强调了一次，真的很累的。 可否能提前来实习，如果能的话是哪个时间段可以来。 最后一个问题是par问的：你觉得这位面试官小姐姐好看吗hhhh~ 之后过了很久都没有消息，我以为已经凉了，在PwC网申截止的最后一天又网申了一次，这次没有ot，改成了和安永一样的游戏测评。 做完测评的那天晚上收到了offer letter. 因为参加的是学院与公司一起安排的理工场，加上拿了直通卡，所以省掉了一些环节，正常的流程应该是： 网申-游戏测评-video interview-群面-par面。 我有同学在理工场没有拿到直通车后续参加了群面： 自我介绍（中英文均可） Case群面（英文讨论），case分成了两个小组，首先10分钟读题，然后35分钟讨论，同学抽到的题目是关于企业合作的。有一个白板做演讲展示（需英文，每个人至少两分钟），演讲完之后要回答对方小组的问题（可以中文）。对方小组演讲完之后，本小组要提两个问题。 单独面试（中文） 总结：面经没有什么干货，感觉自己完全是运气加持，在面试的过程中很轻松愉快，从第一次参加STEM Day到后面的面试，广州所的人给我感觉都很耐思。英语很重要！！如果没有拿到直通车，可能我都没有勇气参加群面T T，之前因为英语的问题放弃参加安永SLP，很后悔，应该会认识很多厉害的小伙伴。