双指针
回文字符串
680. 验证回文字符串 Ⅱ
由于每次可以删除一个字符,所以从两端开始向中间扫描,如果有不同的字符则判断删除前一个或者后一个看是否构成回文串。
1 | class Solution { |
环形链表
141. 环形链表
用两个快慢指针,一个每次前进一格,一个每次前进两个。如果有环则这两个指针一定会相遇。
1 | class Solution { |
链表
相交链表
160.相交链表
用两个指针,一个指向A,一个指向B链表,当有一个到末尾的时候指向另一个链表。如果有相交则最后一定会指向同一个结点。
1 | class Solution { |
反转链表
206. 反转链表
递推
用一个指针存储下一个结点和上一个结点
1 | class Solution { |
递归
递归版本稍微复杂一些,其关键在于反向工作。假设列表的其余部分已经被反转,现在我该如何反转它前面的部分?假设列表为:$n_1 → … → n_{k-1} → n_k → n_{k+1} → … → n_m → Ø$
若从节点$ nk+1 $到 $nm $已经被反转,而我们正处于 $nk$。
$n_1 → … → n_{k-1} → n_k → n_{k+1} ← … ← n_m$
我们希望$ n_{k+1} $的下一个节点指向 $n_k$。
所以,
1 | nk.next.next = nk; |
要小心的是$ n_1$ 的下一个必须指向 $Ø$ 。如果你忽略了这一点,你的链表中可能会产生循环。如果使用大小为 2 的链表测试代码,则可能会捕获此错误。
1 | class Solution { |
删除链表的倒数第N个节点
用一个fast指针先向前走n步,然后slow指针和fast指针一起走直到fast走到倒数第二个,然后操作一下删除就可以了。
1 | /** |
树
平衡二叉树
110.平衡二叉树
判断一棵树是不是平衡二叉树,判断左右结点的高度差是否相差不到1,若不是则不为平衡二叉树
1 | class Solution { |
合并二叉树
617. 合并二叉树
将两棵树合并成一棵
1 | class Solution { |
路径总和 III
437. 路径总和 III
最初想的一个暴力的方法,把每个结点可以形成的数都存到vector中遍历相加,很慢。
1 | class Solution { |
正解应该是两个递归,答案应该是当前结点和为sum的个数加上左结点和为sum的个数加上右结点和为sum的个数。
计算和为sum可以dfs直到叶子结点。
1 | class Solution { |
对称二叉树
101. 对称二叉树
判断一棵二叉树是不是对称,想了半天没想出来。
后来把根结点的其中一棵子树反转判断是否和另一棵相等即可。
好像不是正解。先放个代码
1 | /** |
正解可以用一个递归处理。注意判断是不同子树上的两棵子树
1 | class Solution { |
打家劫舍
337. 打家劫舍 III
当前结点取或者不取,简单的树形dp一下,每次记录取或者不取的最大值。一遍dfs
1 | class Solution { |
二叉树中第二小的节点
671. 二叉树中第二小的节点
给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话,那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树,你需要输出所有节点中的第二小的值。如果第二小的值不存在的话,输出 -1 。
如果有节点的值不大于它的子节点的值,所以我们只要判断一下当前结点和左右两个结点的是否相等,如果相等就继续往下处理。
否则就是一组备选答案。
然后dfs回来的时候,看两个结点的值,如果两个值不为-1,则返回两者中较小的。
如果有一个不为-1,则返回这个值。
或者返回-1,表示这棵子树所有的点都和父节点相等。
1 | class Solution { |
二叉树的前序遍历
144. 二叉树的前序遍历
二叉树的前序遍历非递归写法。
用一个栈,先存放右结点,再存放左结点,进行遍历。
1 | class Solution { |
二叉树的后序遍历
145. 二叉树的后序遍历
由于前序是root -> left -> right
而后序是left -> right -> root
所以我们只需要把前序入栈的顺序反一下,再取个反就可以了。
1 | class Solution { |
二叉树的中序遍历
94. 二叉树的中序遍历
中序遍历的非递归写法,用一个额外结点now。
每次遍历左子树直到叶子结点,将一路上所有的左结点都加入栈。
然后将当前的右结点设为now
1 | class Solution { |
分治
数组中的第K个最大元素
215. 数组中的第K个最大元素
arrangeK表示将前k大的k个元素置于数组右侧
1 | class Solution { |
v1.5.2