基本思路 根据丑数的定义，我们有如下结论： 是最小的丑数。 对于任意一个丑数 ，其与任意的质因数（、、）相乘，结果（、、）仍为丑数。 优先队列（小根堆）解法 有了基本的分析思路，一个简单的解法是使用优先队列： 起始先将最小丑数 放入队列 每次从队列取出最小值 ，然后将 所对应的丑数 、 和 进行入队。 对步骤 2 循环多次，第 次出队的值即是答案。 为了防止同一丑数多次进队，我们需要使用数据结构 来记录入过队列的丑数。 代码： import java.util.*; public class Solution { int[] nums = new int[]{2,...

模拟 + 哈希表 如果不考虑 random 指针的话，对一条链表进行拷贝，我们只需要使用两个指针：一个用于遍历原链表，一个用于构造新链表（始终指向新链表的尾部）即可。这一步操作可看做是「创建节点 + 构建 next 指针关系」。 现在在此基础上增加一个 random 指针，我们可以将 next 指针和 random 指针关系的构建拆开进行： 先不考虑 random 指针，和原本的链表复制一样，创建新新节点，并构造 next 指针关系，同时使用「哈希表」记录原节点和新节点的映射关系； 对原链表和新链表进行同时遍历，对于原链表的每个节点上的 random 都通过「哈希表」找到对应的新 rando...

朴素解法 一个朴素的解法自然是两层枚举，逐个检查哪个节点相同。 代码： public class Solution { public ListNode FindFirstCommonNode(ListNode a, ListNode b) { for (ListNode h1 = a; h1 != null ; h1 = h1.next) { for (ListNode h2 = b; h2 != null ; h2 = h2.next) { if (h1 == h2) return h1; ...

「位数检查」解法 一个朴素的做法是，对 int 的每一位进行检查，并统计 的个数。 代码： public class Solution { public int NumberOf1(int n) { int ans = 0; for (int i = 0; i < 32; i++) { ans += ((n >> i) & 1); } return ans; } } 时间复杂度：， 为 int 的位数，固定为 位 空间复杂度： 「右移统计」解法 对于方法一...

动态规划 为了方便，使用 ss 代指 str，使用 pp 代指 pattern。 整理一下题意，对于字符串 p 而言，有三种字符： 普通字符：需要和 s 中同一位置的字符完全匹配 '.'：能够匹配 s 中同一位置的任意字符 '*'：不能够单独使用 '*'，必须和前一个字符同时搭配使用，数据保证了 '*' 能够找到前面一个字符。能够匹配 s 中同一位置字符任意次。 所以本题关键是分析当出现 a* 这种字符时，是匹配 0 个 a、还是 1 个 a、还是 2 个 a ... 本题可以使用动态规划进行求解： 状态定义：f(i,j) 代表考虑 s 中以 i 为结尾的子串和 p 中的 j 为结尾的子...

【本题】双栈解法 对于「任何表达式」而言，我们都使用两个栈 nums 和 ops： nums ： 存放所有的数字 ops ：存放所有的数字以外的操作 然后从前往后做，对遍历到的字符做分情况讨论： 空格 : 跳过 ( : 直接加入 ops 中，等待与之匹配的 ) ) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums + - * : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉（只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算），使...

基本分析 前两天我们刚讲过 NC 93 设计LRU缓存结构，简单理解 LRU 就是「移除最久不被使用的元素」。 因此对于 LRU 我们只需要在使用「哈希表」的同时，维护一个「双向链表」即可： 每次发生 get 或 put 的时候就将元素存放双向链表头部 当需要移除元素时，则从双向链表尾部开始移除 LFU 简单理解则是指「移除使用次数最少的元素」，如果存在多个使用次数最小的元素，则移除「最近不被使用的那个」（LRU 规则）。同样的 get 和 put 都算作一次使用。 因此，我们需要记录下每个元素的使用次数，并且在 的复杂度内「修改某个元素的使用次数」和「找到使用次数最小的元素」。 桶排序...

基本思想 首先要明确，题目所定义的 “对称” 是对每层而言，同时考虑空节点。 因此，如果我们使用常规的遍历方式进行检查的话，需要对空节点有所表示。 局部检查（层序遍历） 我们使用 0x3f3f3f3f 作为无效值，并建立占位节点 emptyNode 用来代指空节点（emptyNode.val = 0x3f3f3f3f）。 一个朴素的做法是：使用「层序遍历」的方式进行「逐层检查」，对于空节点使用 emptyNode 进行代指，同时确保不递归 emptyNode 对应的子节点。 具体做法如下： 起始时，将 root 节点入队； 从队列中取出节点，检查节点是否为 emptyNode 节点来决定...

基本思路 无论使用何种「遍历方式」进行二叉树存储，为了方便，我们都需要对空节点有所表示。 其实题目本身的样例就给我们提供了很好的思路：使用层序遍历的方式进行存储，对于某个叶子节点的空节点进行存储，同时确保不递归存储空节点对应的子节点。 层序遍历 我们使用 0x3f3f3f3f 作为无效值（当然也可以不使用数字，使用某个特殊字符进行表示，只要能在反序列时有所区分即可），并建立占位节点 emptyNode 用来代指空节点（emptyNode.val = INF）。 序列化：先特判掉空树的情况，之后就是常规的层序遍历逻辑： 起始时，将 root 节点入队； 从队列中取出节点，检查节点是否有左/右...

基本分析 LRU 是一种十分常见的页面置换算法。 将 LRU 翻译成大白话就是：当不得不淘汰某些数据时（通常是容量已满），选择最久未被使用的数据进行淘汰。 题目让我们实现一个容量固定的 LRUCache 。如果插入数据时，发现容器已满时，则先按照 LRU 规则淘汰一个数据，再将新数据插入，其中「插入」和「查询」都算作一次“使用”。 可以通过 🌰 来理解，假设我们有容量为 的 LRUCache 和 测试键值对 [1-1,2-2,3-3] ，将其按照顺序进行插入 & 查询： 插入 1-1，此时最新的使用数据为 1-1 插入 2-2，此时最新使用数据变为 2-2 查询 1-1，此时最新...

朴素解法 一个朴素的做法是，根据题目对于 TreeLinkNode 的定义，利用 next 属性存储「当前节点的父节点」这一特点。 从入参节点 pNode 出发，不断利用 next 属性往上查找，直到找到整棵树的头节点，令头节点为 root。 然后实现二叉树的「中序遍历」，将遍历过程中访问的节点存放到列表 list 中，之后再对 list 进行遍历，找到 pNode 所在的位置 idx，即可确定 pNode 是否存在「下一个节点」以及「下一节点」是哪一个。 代码： import java.util.*; public class Solution { List<TreeLin...

迭代解法 首先一个比较「直观且通用」的思路是，采用「边遍历边构造」的方式： 建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面； 使用 tail 代表当前有效链表的结尾； 通过原输入的 pHead 指针进行链表扫描。 对原链表进行遍历，只要原链表尚未到达结尾，我们就重复如下决策（保留/跳过逻辑）： 保留：pHead 已经没有下一个节点，pHead 可以被保留（插入到答案结尾指针 tail 后面）；pHead 有一下个节点，但是值与 pHead 不相同，pHead 可以被保留； 跳过：当发现 pHead 与下一个节点值相同，需要对「连续相同一段」进行跳过...