代码随想录知识星球精华（最强八股文）第五版（算法篇）.pdf资源-CSDN文库

版权申诉

190 浏览量 2025-01-07 16:31:39 上传评论收藏 29.68MB PDF 举报

资源推荐

资源详情

资源评论

代码随想录知识星球精华（最强⼋股⽂）第五版

（算法篇）

代码随想录知识星球精华（最强⼋股⽂）第五版为九份PDF，分别是：

代码随想录知识星球⼋股⽂概述

C++篇

go篇

Java篇

前端篇

算法题篇

计算机基础篇

问答精华篇

⾯经篇

本篇为最强⼋股⽂之算法篇。

题⽬解析

数组

数组中两个数的最⼤异或值

异或运算每⼀位单独运算（不进位加法），所以优先找⼆进制⾼位的异或结果为 1 的位置。

尽量让每⼀位的异或结果为 1 ，这样才是 num[i] ^ num[j]的最⼤值

保存前 i - 1 个数到字典树中，然后在字典树中查找与 i 匹配的异或结果最⼤值，保留。

遍历数组时，由于先将前⼀个数存⼊字典树中，然后再找当前数字在字典树中的异或最⼤值，所以遍历完所有数字

之后，也就找到了最⼤的异或值。

在字典树中查找时，查找数字的每⼀位在字典树中相反的值，0 找 1 ，1 找 0 ，这样保证找到当前的异或最⼤值

找出所有⼦集的异或总和再求和

暴⼒可以直接过，直接枚举所有⼦集情况

(1) dfs递归的求出每个⼦集

求出异或结果和，并加起来

递归实现dfs，nums表示数组，i 表示枚举到的位置，xorSum表示已经累计的异或总和

递归内容，对于每个位置的元素都有加⼊或不加⼊⼦集，分别进⾏递归

递归结束条件，枚举完所有位置 i == nums.length

(2)位运算求出每个⼦集，⽤⼆进制枚举

⽤⼀个⻓度为 n 的⼆进制数来表示所有的⼦集，每⼀位对应nums 的每⼀位取还是不取（1表示取，0表示不取）

这正好能够表示 nums 数组所有的⼦集情况（n 个数的⼦集个数为 2 ^ n）

再枚举这个⼆进制数的每⼀位，如果这⼀位为 1 ，那么将该位 nums 进⾏异或，最后将每种⼦集的结果累加即可

链表

环形链表

1、先要判断是否有环

判断是否有环，这个在环形链表I 当中使⽤fast指针每次移动两个结点和slow指针每次移动⼀个结点当两者相等时

表示有环。

(fast相对slow指针相对运动，每次接近⼀个结点，直到重合，所以fast不会错过slow)

2、再找出环的⼊⼝位置

环的⼊⼝位置，新建⼀个指针从head开始移动和slow指针⼀起，每次移动⼀格，两者相遇结点即为环⼊⼝结点

证明：

设链表⻓度为 a + b ，a为环⼊⼝距离(不包括链表⼊⼝结点)，b为环⻓度，f为fast指针，s为slow指针

f=2s （快指针每次2步，路程刚好2倍）

f = s + nb (相遇时，fast刚好多⾛了n圈）

推出相遇时slow指针⾛了：s = nb

从head结点⾛到⼊环点需要⾛： a + nb，⽽slow已经⾛了nb，那么slow再⾛a步就是⼊环点了

所以，从head开始，和slow指针⼀起⾛，相遇时刚好就是a步

双指针

双指针并不属于某⼀种数据结构，只是⼀种操作⽅法，所以我们在数组、链表、字符串中都⽤到了。

双指针之所以被使⽤，是因为他可以通过两个指针在⼀个for循环下实现两个for循环所做的事情。这样就极⼤的减

少了运⾏时间，将时间复杂度由O(n^2)降为O(n)

双指针具体怎么⽤就要根据需求。

⽐如要是反转字符串：

⼀个指针就要放在字符串开始，另⼀个放在字符串结尾，在元素交换之后，两个指针都往中间⾛。那这样的操作什

么时候截⽌呢，就是要左边的指针⼩于右边指针，这样思路就出来了。

要是换成移除数组中的某个元素：

就要使⽤快慢指针，⼀个在前检测是不是等于要移除的元素，不等于的时候两个指针⼀起⾛就⾏了，但是⼀旦发现

了要移除的元素，后⾯指针+1，前⾯那个不动，这个就可以实现覆盖了，后⾯的覆盖掉前⾯的，不就移除了吗，数

组的存储是连续的，所以我们想要移除的时候就是后⾯元素覆盖前⾯的，达到移除的⽬的。其实替换空格也是这个

道理，多了⼀步根据空格数来扩充空间，左右两个指针分别从原字符串和扩充字符串的最右端开始，右指针就是根

据左指针给的信息（是不是空格）来⾏动。

反转链表就和反转字符串不⼀样，结构决定的：

需要把节点的指针往回指达到反转的⽬的，所以需要两个指针（cur，pre）指向现在这个结点，以及他之前的⼀个

结点（因为你要往前指才能反转），注意，在往前指之前要保存cur.next，不然直接指，那cur.next就丢了，这就

是链表的特殊之处，指完之后两个指针后移就可以，直到cur ==null，这就是循环的条件了。最后返回的是头指针

哦，通过头指针就能找到这个链表。

移除链表元素的时候需要明⽩虚拟头指针的概念，这是为了统⼀操作，不然头指针还得单独操作，放⼀下卡哥的链

接

移除链表元素

虚拟头结点的关键就是你先声明⼀个节点 ListNode dummy= new ListNode()；这个括号⾥⾯存不存值都是可以

的，反正也没啥⽤，然后就要把这个节点指向头结点，这样你才是虚拟头结点啊 dummy.next = head;

哈希表

哈希函数

哈希函数是⼀种映射关系，根据关键词key，经过⼀定函数关系得到元素的位置。

常⻅的哈希函数构造⽅法：

1、直接定址法：

取关键字或关键字的某个线性函数值为散列地址。

H(key) = a * key + b，其中a和b为常数

2、除留余数法：

取关键字被某个不⼤于散列表⻓度 m 的数 p 求余，得到的作为散列地址。

H(key) = key % p, p < m

3、叠加法：

将关键字分为位数相同的⼏部分，然后取这⼏部分的叠加和（舍去进位）作为散列地址。

⽤于关键字位数较多，并且关键字中每⼀位上数字分布⼤致均匀。

4、随机数法：

选择⼀个随机函数，把关键字的随机函数值作为它的哈希值。

通常当关键字的⻓度不等时⽤这种⽅法。

当关键字是整数类型时就可以⽤除留余数法；如果关键字是⼩数类型，选择随机数法会⽐较好

哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希冲突的解决：

1、开放地址法（前提是散列表的⻓度⼤于等于所要存放的元素）

发⽣哈希冲突后，按照某⼀次序找到下⼀个空闲的单元，把冲突的元素放⼊。

2、线性探查法

从发⽣冲突的单元开始探查，依次查看下⼀个单元是否为空，如果到了最后⼀个单元还是空，那么再从表⾸依次判

断。如此执⾏直到碰到了空闲的单元或者已经探查完所有单元。

3、平⽅探查法

从发⽣冲突的单元加上12,22,32,…,n2，直到遇到空闲的单元

4、双散列函数探查法

定义两个散列函数，分别为s1和s2，s1的算法和前⾯⼀致，s2取⼀个1～m-1之间并和m互为素数的数。s2作为步

⻓。

更适合于造表前⽆法确定表⻓的情况；平均查找⻓度较短；适合结点规模较⼤时。

5、分离链接法：

将哈希值相同的元素构成⼀个链表，head放在散列表中。⼀般链表⻓度超过了8就转为红⿊树，⻓度少于6个就变

为链表。缺点：指针需要额外的空间

树

树的遍历

在学习链表和数组这两种线性的数据结构的时候，元素之间的次序是⼗分容易看出的，毕竟元素的位置就是排着

队的，⾃带次序关系，如果想要遍历整个数据结构，⽆⾮就是选择倒着遍历还是正着遍历。

但是在学习⼆叉树这种半线性结构的时候，也想要遍历整棵树，可是树没有数组、链表这么明显的次序关系，所以

需要⼈为的定义次序关系，即前中后序（VLR，LVR，LRV），这⼀个过程本质上就是将树的半线性结构转换成线性

结构。

⽽对于任意⼀个树节点，选择前中后序中的任意⼀种，就等于将这个树节点和它的左右孩⼦的顺序给出。以前只是

机械的记忆顺序。

下⾯举例说明，这是⼀颗⼆叉树。由整体思维可以将这个⼆叉树看成三个⼤的结点。

剩余65页未读，继续阅读

评论收藏

内容反馈

版权申诉

skyJ

粉丝: 3036
资源: 2205

代码随想录知识星球精华（最强八股文）第五版（算法篇）.pdf

代码随想录知识星球精华（最强八股文）第五版（Go篇）.pdf

代码随想录知识星球精华（最强八股文）第五版（面经篇）.pdf

代码随想录知识星球精华（最强八股文）第五版（前端篇）.pdf

代码随想录知识星球精华（最强八股文）第五版（星球资源篇）.pdf

代码随想录知识星球精华（最强八股文）第五版（概述）.pdf

代码随想录最新第三版-最强八股文

代码随想录算法PDF.rar

代码随想录知识星球精华-大厂面试八股文v1.1

代码随想录算法PDF.zip

《代码随想录》最新PDF全集整理发布

「代码随想录」动态规划专题精讲（v1.2）.pdf

代码随想录知识算法讲解PDF

代码随想录的pdf版本，需要准备秋招的小伙伴们看过来呀！

代码随想录-最强八股文（第五版）

新媒体写作知识点.doc

NLP算法岗八股文 密码daimasuixianglu.pdf

「代码随想录」二叉树专题精讲（v2.0）.pdf

「代码随想录」回溯算法精讲（v1.1）.pdf

2024年 8项合集12月最新JavaGuide 面试指北 代码随想录八股文 面经 【8项全部打包】最新面试指北 + JavaGuide + 最新代码随想录八股文 + 50万字Java面试宝

代码随想录+刷题笔记记录

代码随想录 动态规划、回溯、递归、二叉树、贪心

《代码随想录-最强八股文（第五版）》是一部综合性的编程知识合集，旨在帮助程序员，尤其是面试者，提升在前端、后端以及Java和Go等领域的技术素养 这一版本的内容涵盖了大量的面试常见问题，是程序员们准备

「代码随想录」贪心算法专题精讲（v1.0）.pdf

2015-04_P292 软件随想录.pdf

代码质量随想录

「代码随想录」程序员求职攻略（v1.0）.pdf

计算机程序设计艺术

相关实用应用程序（Windows可用）

李飞飞自传 我看见的世界 The World I see

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

最新资源

NLP算法岗八股文密码daimasuixianglu.pdf

2024年 8项合集12月最新JavaGuide 面试指北代码随想录八股文面经【8项全部打包】最新面试指北 + JavaGuide + 最新代码随想录八股文 + 50万字Java面试宝

代码随想录动态规划、回溯、递归、二叉树、贪心

《代码随想录-最强八股文（第五版）》是一部综合性的编程知识合集，旨在帮助程序员，尤其是面试者，提升在前端、后端以及Java和Go等领域的技术素养这一版本的内容涵盖了大量的面试常见问题，是程序员们准备

李飞飞自传我看见的世界 The World I see