九章算法班 2024版lg...

• 如何在算法面试中正确的沟通？

a.如何确定自己的算法是正确的？

b.如何套出面试官要求的时间复杂度？

c.如何知道自己Hire or No Hire？

• 如何让面试官在面试中感觉你很牛逼？

a.为什么Coding Style很重要

b.什么是Good Coding Style，什么是Bad Coding Style

• 如何修炼Bug Free的能力

a.一个技巧教你避免99%的Bug

b.出现Bug以后如何快速Debug

• 如何做到刷100题顶过别人刷300题

a.算法面试精选100题（免费福利）

• 算法面试考察范围与频率一览

• 最长回文子串Longest Palindromic Substring

a.为什么不需要学Manacher's Algorithm

b.基于双指针的算法与背向双指针算法简介

c.有哪些Bad Coding Style容易踩，面试真实案例分析

d.基于动态规划的算法与区间型动态规划简介

• 面试评分标准
• 快速提高Coding Quality的十二个技巧

• 字符串查找strStr

a.为什么不需要学KMP算法

b.Rabin-karp算法与哈希函数Hash Function

• 为什么我们不需要学习贪心法
• 三个你必须知道的语言知识

a.如何判断两个字符串是否相等

b.如何遍历字符串

c.null和""有什么区别

• 十个你必须掌握的字符串处理函数

• 四个算法的复杂度维度

a.时间复杂度Time complexity

b.空间复杂度Spatial complexity

c.编程复杂度Programming complexity

d.思维复杂度Complexity of thinking

• 时间复杂度是O(N)的算法有哪些
• 三种双指针题型

a.背向双指针Back-facing double hands

b.同向双指针Codirectional double pointer

c.相向双指针Opposite double pointer

• Valid Palindrome && II
• Two Sum型双指针经典题

a.哈希表的做法

b.排序+双指针的做法

c.哈希表与双指针的比较

• 两个必须熟练掌握的排序算法

a.快速排序算法Quick sort algorithm

b.归并排序算法Merge sort algorithm

• Quick Select快速选择算法

• 时间复杂度的分析技巧——T函数推导法T function derivation method
• 通过时间复杂度倒推算法的技巧
• 递归是什么，如何实现二分
• 什么是堆空间（Heap Memory），什么是栈空间（Stack Memory）
• 什么是Stack Overflow，如何造成的，如何避免

• 二分法的基本原理
• 通用模板

a.什么时候死循环

b.为什么能做到通用

• 使用二分法解决求第一个位置，求最后一个位置和求任意位置的二分问题
• 二分算法的判断条件

• 两数之和的十种变形题

a.数据结构设计

b.不同的二元组个数

c.两数之和小于等于

d.两数之和大于等于

e.三角形个数

f.两数之和最接近

g.三数之和

h.三数之和最接近

i.四数之和

j.K数之和

• 时间复杂度与循环层数的关系
• Partition型相向双指针

a.2-Part-Partitionvs3-Part-Partition

b.彩虹排序算法

c.通过移0的问题看相向双指针与同向双指针的区别

• 第一重境界写出不会死循环二分法
• 第二重境界在排序的输入集上进行二分
• 第三重境界在未排序输入集上进行二分
• 第四重境界在结果集上进行二分
  

• 队列及相关面试题
• Java中的Interface是什么
• 链表和数组实现队列的区别
• 循环队列的实现方法

• 宽度优先搜索的适用场景
• 宽度优先搜索的三种实现方法

a.两个队列的实现方法

b.DummyNode的实现方法

c.一个队列的实现方法

• 无向图和有向图的存储方法

• 递归Recursion，深搜DFS，回溯Backtracking的联系和区别
• 递归三要素是什么
• 通过二叉树学习DFS中的遍历法
• 什么是分治法，遍历法和分治法的区别

a.通过两道实战真题理解分治法和遍历法的区别

• 非递归版本的二叉树中序遍历

a.BST是什么

b.BST Iterator的两种实现方法

• 连通块问题

a.DFS vs BFS在连通块问题上的优劣

b.劝分不劝合的编码理论

• 图的层级遍历与简单图最短路径问题

a.什么是简单图

b.复杂度最短路径有什么算法

c.最长路径用什么算法

d.什么是隐式图

e.通用的BFS模板

f.80%的人都会写错的BFS写法

• 拓扑排序

a.DFS vs BFS在拓扑排序上的优劣

b.拓扑排序的五个考点

i.问有没有拓扑排序

ii.求任意一个拓扑排序

iii.求最小的拓扑排序

iv.求拓扑排序是否唯一

• 用分治法解决二叉树求值求路径的问题

a.理解什么是搜索中的回溯

• 用分治法解决二叉树形态变换的问题

a.全局变量在代码中的危害

• 组合类搜索的隐式图模型
• 组合类搜索的时间复杂度和适用条件
• 如何对搜索结果进行去重

a.选代表vs哈希表

• 排列类搜索的隐式图模型
• 排列类搜索的时间复杂度和适用条件
• 通过排列类搜索看搜索与多重循环的区别
• 著名的NP问题：TSP问题（旅行商问题）

a.DFS的解法

b.状态压缩型动态规划

c.随机化算法

• HashMap和HashSet的联系和区别
• 哈希表Hash Table的基本原理
• 什么是哈希函数Hash Function
• 如何解决冲突Collision

a.开散列Open Hash vs 闭散列Closed Hash

• 哈希表扩容问题

• Priority Queue和堆的联系和区别
• 堆的基本原理
• 堆的基本操作Sift Up和Sift Down
• 堆的增删查改
• 堆的初始化Heapify
• 堆排序

• 排列组合类搜索

a.两种组合类DFS的实现方法

b.使用组合类DFS算法解决K数之和问题

c.DFS的框架模板

• 矩阵上的DFS
• 如何解决求所有最短路线的问题
  

• 数据结构设计题的考点
• 数据结构设计题的时间复杂度计算方式
• 在线算法vs离线算法
• 堆Heap的实战真题
• 高级数据结构的Cheat Sheet
  

• 什么时候可以使用记忆化搜索
• DFS和记忆化搜索的区别
• 如何用三行代码让DFS变成记忆化搜索
• 用记忆化搜索解决博弈型动态规划
• 记忆化搜索的缺陷

• 动态规划DP与记忆化搜索的关系
• 多重循环与记忆化搜索实现动态规划的区别
• 什么时候使用动态规划

a.动态规划四要素是什么

• 自底向上的动态规划
• 自顶向下的动态规划

• 动态规划算法的使用场景
• 动态规划题型一览
• 坐标型动态规划

• 01背包01 Backpack
• 带价值的背包Backpack with value
• 多重背包Multiple backpacks

• 三种适用动态规划的场景
• 三种不适用动态规划的场景
• 用记忆化搜索解决字符串相关的DP问题
  

• 动态规划的解题步骤
• 动态规划的空间优化技巧——滚动数组
• 坐标型动态规划的分支——接龙型动态规划
• 通过经典DP题LIS看动态规划如何记录具体方案
• 上下左右都可以走的矩阵如何进行动态规划
  

• Two Sum的第十一种变形题——两数之差
• 全零子串问题
• 数组去重问题

• 数组和字符串上的同向双指针

a.滑动窗口求和

b.K次替换后最长的重复字符子串

• 快慢指针算法

a.链表求交、链表求环

b.链表中位点

• 排序输入集：排序矩阵找数问题
• 未排序输入集：最小的包含所有连通01块的矩阵
• 结果集二分：抄书问题

• 比O(N)小的算法 -O(LogN)

a.快速幂算法Fast exponentiation algorithm

b.辗转相除法Tossing and turning phase division

c.两个排序数组的中位数Median of two sorted arrays

• O(√N)的算法

a.分解质因数Decomposition of prime factors

b.分块检索法Chunked retrieval method

• 使用BFS求所有方案类问题
• 使用BFS序列化二叉树

a.什么是序列化与反序列化

• 双向宽度优先搜索算法

a.双向宽度优先搜索到底优化了多少

b.如何优雅的实现双向宽度优先搜索

• 非递归实现后序遍历
• Morris算法

• 二叉查找数 BST （Binary Search Tree）的增删查改

• 使用求下一个排列的算法实现非递归
• 更通用的非递归实现方法

• N皇后问题及程序结构的艺术
• 数独及搜索顺序的优化算法

• 最小栈Minimal stack
• 最大栈Maximum stack
• 两个栈实现队列Two stacks implement queues
• 两个队列实现栈Two queues implement the stack

• 外排序Outer sorting
• 三种K路归并算法
• 数组合并的相关问题

• 区间型动态规划的题目特点
• 区间型动态规划的循环方式
• 三个例题入门区间动态规划

• 匹配型动态规划的题目特点
• 匹配型动态规划的代码实现
• 三个例题入门匹配型动规

• 划分型动态规划的题目特点
• 划分型动态规划的代码实现
• 三个例题入门划分型动规

• 接龙型动态规划的题目特点
• 接龙型动态规划的代码实现
• 最长上升子序列（LIS）的二分解法
• 三个例题吃透接龙型动态规划