网站网页制作电话,大田县建设资讯网站,无锡自助建站软件,高端食品wordpress三. 练习
3.1 时间复杂度
用函数 f ( n ) f(n) f(n) 表示算法效率与数据规模的关系#xff0c;假设每次解决问题需要 1 微秒#xff08; 1 0 − 6 10^{-6} 10−6 秒#xff09;#xff0c;进行估算#xff1a;
如果 f ( n ) n 2 f(n) n^2 f(n)n2 那么 1 秒能解决多…三. 练习
3.1 时间复杂度
用函数 f ( n ) f(n) f(n) 表示算法效率与数据规模的关系假设每次解决问题需要 1 微秒 1 0 − 6 10^{-6} 10−6 秒进行估算
如果 f ( n ) n 2 f(n) n^2 f(n)n2 那么 1 秒能解决多少次问题1 天呢如果 f ( n ) l o g 2 ( n ) f(n) log_2(n) f(n)log2(n) 那么 1 秒能解决多少次问题1 天呢如果 f ( n ) n ! f(n) n! f(n)n! 那么 1 秒能解决多少次问题1 天呢
参考解答
1秒 1 0 6 1000 \sqrt{10^6} 1000 106 1000 次1 天 1 0 6 ∗ 3600 ∗ 24 ≈ 293938 \sqrt{10^6 * 3600 * 24} \approx 293938 106∗3600∗24 ≈293938 次1秒 $2^{1,000,000} $ 次一天 2 86 , 400 , 000 , 000 2^{86,400,000,000} 286,400,000,000推算如下 10 ! 3 , 628 , 800 10! 3,628,800 10!3,628,800 1秒能解决 1 , 000 , 000 1,000,000 1,000,000 次因此次数为 9 次 14 ! 87 , 178 , 291 , 200 14!87,178,291,200 14!87,178,291,200一天能解决 86 , 400 , 000 , 000 86,400,000,000 86,400,000,000 次因此次数为 13 次
3.2 二分查找
69. x 的平方根 - 力扣LeetCode
E01. 二分查找-力扣 704 题
要点减而治之可以用递归或非递归实现
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1
例如
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 参考答案略可以用讲过的任意一种二分求解
E02. 搜索插入位置-力扣 35 题
要点理解谁代表插入位置
给定一个排序数组和一个目标值
在数组中找到目标值并返回其索引如果目标值不存在于数组中返回它将会被按顺序插入的位置
例如
输入: nums [1,3,5,6], target 5
输出: 2输入: nums [1,3,5,6], target 2
输出: 1输入: nums [1,3,5,6], target 7
输出: 4参考答案1用二分查找基础版代码改写基础版中找到返回 m没找到 i 代表插入点因此有
public int searchInsert(int[] a, int target) {int i 0, j a.length - 1;while (i j) {int m (i j) 1;if (target a[m]) {j m - 1;} else if (a[m] target) {i m 1;} else {return m;}}return i; // 原始 return -1
}参考答案2用二分查找平衡版改写平衡版中
如果 target a[i] 返回 i 表示找到如果 target a[i]例如 target 2a[i] 3这时就应该在 i 位置插入 2如果 a[i] target例如 a[i] 3target 4这时就应该在 i1 位置插入 4
public static int searchInsert(int[] a, int target) {int i 0, j a.length;while (1 j - i) {int m (i j) 1;if (target a[m]) {j m;} else {i m;}}return (target a[i]) ? i : i 1;// 原始 (target a[i]) ? i : -1;
}参考答案3用 leftmost 版本解返回值即为插入位置并能处理元素重复的情况
public int searchInsert(int[] a, int target) {int i 0, j a.length - 1;while(i j) {int m (i j) 1;if(target a[m]) {j m - 1;} else {i m 1;} }return i;
}E03. 搜索开始结束位置-力扣 34 题
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题
例如
输入nums [5,7,7,8,8,10], target 8
输出[3,4]输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]输入nums [], target 0
输出[-1,-1]参考答案
public static int left(int[] a, int target) {int i 0, j a.length - 1;int candidate -1;while (i j) {int m (i j) 1;if (target a[m]) {j m - 1;} else if (a[m] target) {i m 1;} else {candidate m;j m - 1;}}return candidate;
}public static int right(int[] a, int target) {int i 0, j a.length - 1;int candidate -1;while (i j) {int m (i j) 1;if (target a[m]) {j m - 1;} else if (a[m] target) {i m 1;} else {candidate m;i m 1;}}return candidate;
}public static int[] searchRange(int[] nums, int target) {int x left(nums, target);if(x -1) {return new int[] {-1, -1};} else {return new int[] {x, right(nums, target)};}
}3.3 递归 - single recursion
E03. 二分查找
public static int binarySearch(int[] a, int target) {return recursion(a, target, 0, a.length - 1);
}public static int recursion(int[] a, int target, int i, int j) {if (i j) {return -1;}int m (i j) 1;if (target a[m]) {return recursion(a, target, i, m - 1);} else if (a[m] target) {return recursion(a, target, m 1, j);} else {return m;}
}E04. 冒泡排序
public static void main(String[] args) {int[] a {3, 2, 6, 1, 5, 4, 7};bubble(a, 0, a.length - 1);System.out.println(Arrays.toString(a));
}private static void bubble(int[] a, int low, int high) {if(low high) {return;}int j low;for (int i low; i high; i) {if (a[i] a[i 1]) {swap(a, i, i 1);j i;}}bubble(a, low, j);
}private static void swap(int[] a, int i, int j) {int t a[i];a[i] a[j];a[j] t;
}low 与 high 为未排序范围j 表示的是未排序的边界下一次递归时的 high 发生交换意味着有无序情况最后一次交换以后没有无序时左侧 i 仍是无序右侧 i1 已然有序 视频中讲解的是只考虑 high 边界的情况参考以上代码理解在 low … high 范围内的处理方法
E05. 插入排序
public static void main(String[] args) {int[] a {3, 2, 6, 1, 5, 7, 4};insertion(a, 1, a.length - 1);System.out.println(Arrays.toString(a));
}private static void insertion(int[] a, int low, int high) {if (low high) {return;}int i low - 1;int t a[low];while (i 0 a[i] i) {a[i 1] a[i];i--;}if(i 1 ! low) {a[i 1] t;} insertion(a, low 1, high);
}已排序区域[0 … i … low-1]未排序区域[low … high]视频中讲解的是只考虑 low 边界的情况参考以上代码理解 low-1 … high 范围内的处理方法扩展利用二分查找 leftmost 版本改进寻找插入位置的代码
E06. 约瑟夫问题1 n n n 个人排成圆圈从头开始报数每次数到第 m m m 个人 m m m 从 1 1 1 开始杀之继续从下一个人重复以上过程求最后活下来的人是谁
方法1
根据最后的存活者 a 倒推出它在上一轮的索引号
f(n,m)本轮索引为了让 a 是这个索引上一轮应当这样排规律f(1,3)0x x x a(0 3) % 2f(2,3)1x x x 0 a(1 3) % 3f(3,3)1x x x 0 a(1 3) % 4f(4,3)0x x x a(0 3) % 5f(5,3)3x x x 0 1 2 a(3 3) % 6f(6,3)0x x x a
方法2
设 n 为总人数m 为报数次数解返回的是这些人的索引从0开始
f(n, m)解规律f(1, 3)0f(2, 3)0 1 13%21f(3, 3)0 1 2 0 13%30f(4, 3)0 1 2 3 3 0 13%43f(5, 3)0 1 2 3 4 3 4 0 13%53f(6, 3)0 1 2 3 4 5 3 4 5 0 13%63
一. 找出等价函数
规律下次报数的起点为 k m % n k m \% n km%n
首次出列人的序号是 k − 1 k-1 k−1剩下的的 n − 1 n-1 n−1 个人重新组成约瑟夫环下次从 k k k 开始数序号如下 k , k 1 , . . . , 0 , 1 , k − 2 k,\ k1, \ ...\ ,\ 0,\ 1,\ k-2 k, k1, ... , 0, 1, k−2如上例中 3 4 5 0 1 3\ 4\ 5\ 0\ 1 3 4 5 0 1
这个函数称之为 g ( n − 1 , m ) g(n-1,m) g(n−1,m)它的最终结果与 f ( n , m ) f(n,m) f(n,m) 是相同的。
二. 找到映射函数
现在想办法找到 g ( n − 1 , m ) g(n-1,m) g(n−1,m) 与 f ( n − 1 , m ) f(n-1, m) f(n−1,m) 的对应关系即 3 → 0 4 → 1 5 → 2 0 → 3 1 → 4 3 \rightarrow 0 \\ 4 \rightarrow 1 \\ 5 \rightarrow 2 \\ 0 \rightarrow 3 \\ 1 \rightarrow 4 \\ 3→04→15→20→31→4 映射函数为 m a p p i n g ( x ) { x − k x [ k . . n − 1 ] x n − k x [ 0.. k − 2 ] mapping(x) \begin{cases} x-k x[k..n-1] \\ xn-k x[0..k-2] \end{cases} mapping(x){x−kxn−kx[k..n−1]x[0..k−2] 等价于下面函数 m a p p i n g ( x ) ( x n − k ) % n mapping(x) (x n - k)\%{n} mapping(x)(xn−k)%n 代入测试一下 3 → ( 3 6 − 3 ) % 6 → 0 4 → ( 4 6 − 3 ) % 6 → 1 5 → ( 5 6 − 3 ) % 6 → 2 0 → ( 0 6 − 3 ) % 6 → 3 1 → ( 1 6 − 3 ) % 6 → 4 3 \rightarrow (36-3)\%6 \rightarrow 0 \\ 4 \rightarrow (46-3)\%6 \rightarrow 1 \\ 5 \rightarrow (56-3)\%6 \rightarrow 2 \\ 0 \rightarrow (06-3)\%6 \rightarrow 3 \\ 1 \rightarrow (16-3)\%6 \rightarrow 4 \\ 3→(36−3)%6→04→(46−3)%6→15→(56−3)%6→20→(06−3)%6→31→(16−3)%6→4 综上有 f ( n − 1 , m ) m a p p i n g ( g ( n − 1 , m ) ) f(n-1,m) mapping(g(n-1,m)) f(n−1,m)mapping(g(n−1,m))
三. 求逆映射函数
映射函数是根据 x 计算 y逆映射函数即根据 y 得到 x m a p p i n g − 1 ( x ) ( x k ) % n mapping^{-1}(x) (x k)\%n mapping−1(x)(xk)%n 代入测试一下 0 → ( 0 3 ) % 6 → 3 1 → ( 1 3 ) % 6 → 4 2 → ( 2 3 ) % 6 → 5 3 → ( 3 3 ) % 6 → 0 4 → ( 4 3 ) % 6 → 1 0 \rightarrow (03)\%6 \rightarrow 3 \\ 1 \rightarrow (13)\%6 \rightarrow 4 \\ 2 \rightarrow (23)\%6 \rightarrow 5 \\ 3 \rightarrow (33)\%6 \rightarrow 0 \\ 4 \rightarrow (43)\%6 \rightarrow 1 \\ 0→(03)%6→31→(13)%6→42→(23)%6→53→(33)%6→04→(43)%6→1 因此可以求得 g ( n − 1 , m ) m a p p i n g − 1 ( f ( n − 1 , m ) ) g(n-1,m) mapping^{-1}(f(n-1,m)) g(n−1,m)mapping−1(f(n−1,m))
四. 递推式
代入推导 f ( n , m ) g ( n − 1 , m ) m a p p i n g − 1 ( f ( n − 1 , m ) ) ( f ( n − 1 , m ) k ) % n ( f ( n − 1 , m ) m % n ) % n ( f ( n − 1 , m ) m ) % n \begin{aligned} f(n,m) \ g(n-1,m) \\ \ mapping^{-1}(f(n-1,m)) \\ \ (f(n-1,m) k) \% n \\ \ (f(n-1,m) m\%n) \% n \\ \ (f(n-1,m) m) \% n \\ \end{aligned} f(n,m) g(n−1,m)mapping−1(f(n−1,m))(f(n−1,m)k)%n(f(n−1,m)m%n)%n(f(n−1,m)m)%n 最后一步化简是利用了模运算法则 ( a b ) % n ( a % n b % n ) % n (ab)\%n (a\%n b\%n) \%n (ab)%n(a%nb%n)%n 例如 ( 6 6 ) % 5 2 ( 6 6 % 5 ) % 5 (66)\%5 2 (66\%5)\%5 (66)%52(66%5)%5 ( 6 5 ) % 5 1 ( 6 5 % 5 ) % 5 (65)\%5 1 (65\%5)\%5 (65)%51(65%5)%5 ( 6 4 ) % 5 0 ( 6 4 % 5 ) % 5 (64)\%5 0 (64\%5)\%5 (64)%50(64%5)%5
最终递推式 f ( n , m ) { ( f ( n − 1 , m ) m ) % n n 1 0 n 1 f(n,m) \begin{cases} (f(n-1,m) m) \% n n1\\ 0 n 1 \end{cases} f(n,m){(f(n−1,m)m)%n0n1n1
3.4 递归 - multi recursion
E02. 汉诺塔2
Tower of Hanoi是一个源于印度古老传说大梵天创建世界时做了三根金刚石柱在一根柱子从下往上按大小顺序摞着 64 片黄金圆盘大梵天命令婆罗门把圆盘重新摆放在另一根柱子上并且规定
一次只能移动一个圆盘小圆盘上不能放大圆盘
下面的动图演示了4片圆盘的移动方法 使用程序代码模拟圆盘的移动过程并估算出时间复杂度
思路 假设每根柱子标号 abc每个圆盘用 123 … 表示其大小圆盘初始在 a要移动到的目标是 c 如果只有一个圆盘此时是最小问题可以直接求解 移动圆盘1 a ↦ c a \mapsto c a↦c 如果有两个圆盘那么 圆盘1 a ↦ b a \mapsto b a↦b圆盘2 a ↦ c a \mapsto c a↦c圆盘1 b ↦ c b \mapsto c b↦c 如果有三个圆盘那么 圆盘12 a ↦ b a \mapsto b a↦b圆盘3 a ↦ c a \mapsto c a↦c圆盘12 b ↦ c b \mapsto c b↦c 如果有四个圆盘那么 圆盘 123 a ↦ b a \mapsto b a↦b圆盘4 a ↦ c a \mapsto c a↦c圆盘 123 b ↦ c b \mapsto c b↦c 题解
public class E02HanoiTower {/*源 借 目h(4, a, b, c) - h(3, a, c, b)a - ch(3, b, a, c)*/static LinkedListInteger a new LinkedList();static LinkedListInteger b new LinkedList();static LinkedListInteger c new LinkedList();static void init(int n) {for (int i n; i 1; i--) {a.add(i);}}static void h(int n, LinkedListInteger a, LinkedListInteger b, LinkedListInteger c) {if (n 0) {return;}h(n - 1, a, c, b);c.addLast(a.removeLast());print();h(n - 1, b, a, c);}private static void print() {System.out.println(-----------------------);System.out.println(a);System.out.println(b);System.out.println(c);}public static void main(String[] args) {init(3);print();h(3, a, b, c);}
}E03. 杨辉三角3 分析
把它斜着看 11 11 2 11 3 3 1
1 4 6 4 1行 i i i列 j j j那么 [ i ] [ j ] [i][j] [i][j] 的取值应为 [ i − 1 ] [ j − 1 ] [ i − 1 ] [ j ] [i-1][j-1] [i-1][j] [i−1][j−1][i−1][j]当 j 0 j0 j0 或 i j ij ij 时 [ i ] [ j ] [i][j] [i][j] 取值为 1 1 1
题解
public static void print(int n) {for (int i 0; i n; i) {if (i n - 1) {System.out.printf(% 2 * (n - 1 - i) s, );}for (int j 0; j i 1; j) {System.out.printf(%-4d, element(i, j));}System.out.println();}
}public static int element(int i, int j) {if (j 0 || i j) {return 1;}return element(i - 1, j - 1) element(i - 1, j);
}优化1
是 multiple recursion因此很多递归调用是重复的例如
recursion(3, 1) 分解为 recursion(2, 0) recursion(2, 1) 而 recursion(3, 2) 分解为 recursion(2, 1) recursion(2, 2)
这里 recursion(2, 1) 就重复调用了事实上它会重复很多次可以用 static AtomicInteger counter new AtomicInteger(0) 来查看递归函数的调用总次数
事实上可以用 memoization 来进行优化
public static void print1(int n) {int[][] triangle new int[n][];for (int i 0; i n; i) {// 打印空格triangle[i] new int[i 1];for (int j 0; j i; j) {System.out.printf(%-4d, element1(triangle, i, j));}System.out.println();}
}public static int element1(int[][] triangle, int i, int j) {if (triangle[i][j] 0) {return triangle[i][j];}if (j 0 || i j) {triangle[i][j] 1;return triangle[i][j];}triangle[i][j] element1(triangle, i - 1, j - 1) element1(triangle, i - 1, j);return triangle[i][j];
}将数组作为递归函数内可以访问的遍历如果 t r i a n g l e [ i ] [ j ] triangle[i][j] triangle[i][j] 已经有值说明该元素已经被之前的递归函数计算过就不必重复计算了
优化2
public static void print2(int n) {int[] row new int[n];for (int i 0; i n; i) {// 打印空格createRow(row, i);for (int j 0; j i; j) {System.out.printf(%-4d, row[j]);}System.out.println();}
}private static void createRow(int[] row, int i) {if (i 0) {row[0] 1;return;}for (int j i; j 0; j--) {row[j] row[j - 1] row[j];}
}注意还可以通过每一行的前一项计算出下一项不必借助上一行这与杨辉三角的另一个特性有关暂不展开了 力扣对应题目但递归不适合在力扣刷高分因此只列出相关题目不做刷题讲解了
118. 杨辉三角 - 力扣LeetCode119. 杨辉三角 II - 力扣LeetCode
3.5 链表
E01. 反转单向链表-力扣 206 题
对应力扣题目 206. 反转链表 - 力扣LeetCode
输入head [1,2,3,4,5]
输出[5,4,3,2,1]输入[1,2]
输出[2,1]输入[]
输出[]方法1
构造一个新链表从旧链表依次拿到每个节点创建新节点添加至新链表头部完成后新链表即是倒序的
public ListNode reverseList(ListNode o1) {ListNode n1 null;ListNode p o1;while (p ! null) {n1 new ListNode(p.val, n1);p p.next;}return n1;
}评价简单直白就是得新创建节点对象
方法2
与方法1 类似构造一个新链表从旧链表头部移除节点添加到新链表头部完成后新链表即是倒序的区别在于原题目未提供节点外层的容器类这里提供一个另外一个区别是并不去构造新节点
static class List {ListNode head;public List(ListNode head) {this.head head;}public ListNode removeFirst(){ListNode first head;if (first ! null) {head first.next;}return first;}public void addFirst(ListNode first) {first.next head;head first;}
}代码
public ListNode reverseList(ListNode head) {List list1 new List(head);List list2 new List(null);ListNode first;while ((first list1.removeFirst()) ! null) {list2.addFirst(first);}return list2.head;
}评价更加面向对象如果实际写代码而非刷题更多会这么做
方法3
递归在归时让 5 → 4 5 \rightarrow 4 5→4 4 → 3 4 \rightarrow 3 4→3 …
首先写一个递归方法返回值用来拿到最后一个节点
public ListNode reverseList(ListNode p) {if (p null || p.next null) { // 不足两个节点return p; // 最后一个节点}ListNode last reverseList(p.next);return last;
}注意1递归终止条件是 curr.next null目的是到最后一个节点就结束递归与之前递归遍历不一样注意2需要考虑空链表即 p null 的情况
可以先测试一下
ListNode o5 new ListNode(5, null);
ListNode o4 new ListNode(4, o5);
ListNode o3 new ListNode(3, o4);
ListNode o2 new ListNode(2, o3);
ListNode o1 new ListNode(1, o2);
ListNode n1 new E01Leetcode206().reverseList(o1);
System.out.println(n1);会打印
[5]下面为伪码调用过程假设节点分别是 1 → 2 → 3 → 4 → 5 → n u l l 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1→2→3→4→5→null先忽略返回值
reverseList(ListNode p 1) {reverseList(ListNode p 2) {reverseList(ListNode p 3) {reverseList(ListNode p 4) {reverseList(ListNode p 5) {if (p null || p.next null) {return p; // 返回5}}// 此时p是4, p.next是5}// 此时p是3, p.next是4}// 此时p是2, p.next是3}// 此时p是1, p.next是2
}接下来从 p 4 开始要让 5 → 4 5 \rightarrow 4 5→4 4 → 3 4 \rightarrow 3 4→3 …
reverseList(ListNode p 1) {reverseList(ListNode p 2) {reverseList(ListNode p 3) {reverseList(ListNode p 4) {reverseList(ListNode p 5) {if (p null || p.next null) {return p; // 返回5}}// 此时p是4, p.next是5, 要让5指向4,代码写成 p.next.nextp// 还要注意4要指向 null, 否则就死链了}// 此时p是3, p.next是4}// 此时p是2, p.next是3}// 此时p是1, p.next是2
}最终代码为
public ListNode reverseList(ListNode p) { if (p null || p.next null) { // 不足两个节点return p; // 最后一个节点}ListNode last reverseList(p.next);p.next.next p;p.next null;return last;
}Q为啥不能在递的过程中倒序
A比如
$ 1 \rightarrow 2 \rightarrow 3 $ 如果递的过程中让 2 → 1 2 \rightarrow 1 2→1 那么此时 2 → 3 2 \rightarrow 3 2→3 就被覆盖不知道接下来递给谁而归的时候让 3 → 2 3 \rightarrow 2 3→2 不会影响上一层的 1 → 2 1 \rightarrow 2 1→2
评价单向链表没有 prev 指针但利用递归的特性【记住了】链表每次调用时相邻两个节点是谁
方法4
从链表每次拿到第二个节点将其从链表断开插入头部直至它为 null 结束
设置指针 o1(旧头)、n1(新头)、o2(旧老二)分别指向第一第一第二节点 n 1 o 1 1 → o 2 2 → 3 → 4 → 5 → n u l l \frac{n1 \ o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1n1 o1→2o2→3→4→5→null
将 o2 节点从链表断开即 o1 节点指向第三节点
$ \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$ o 2 2 \frac{o2}{2} 2o2
o2 节点链入链表头部即 o 2 2 → n 1 o 1 1 → 3 → 4 → 5 → n u l l \frac{o2}{2} \rightarrow \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2o2→1n1 o1→3→4→5→null
n1 指向 o2 n 1 o 2 2 → o 1 1 → 3 → 4 → 5 → n u l l \frac{n1 \ o2}{2} \rightarrow \frac{o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2n1 o2→1o1→3→4→5→null
o2 指向 o1 的下一个节点即 n 1 2 → o 1 1 → o 2 3 → 4 → 5 → n u l l \frac{n1}{2} \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{3} \rightarrow 4 \rightarrow 5 \rightarrow null 2n1→1o1→3o2→4→5→null 重复以上 2 ∼ 5 2\sim5 2∼5 步直到 o2 指向 null 还应当考虑边界条件即链表中不满两个元素时无需走以上逻辑
参考答案
public ListNode reverseList(ListNode o1) { if (o1 null || o1.next null) { // 不足两个节点return o1;}ListNode o2 o1.next;ListNode n1 o1;while (o2 ! null) {o1.next o2.next; o2.next n1;n1 o2;o2 o1.next;}return n1;
}方法5
要点把链表分成两部分思路就是不断从链表2的头往链表1的头搬移
n1 指向 null代表新链表一开始没有元素o1 指向原链表的首节点 n 1 n u l l \frac{n1}{null} nulln1 o 1 1 → 2 → 3 → 4 → 5 → n u l l \frac{o1}{1} \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1o1→2→3→4→5→null
开始循环o2 指向原链表次节点 n 1 n u l l \frac{n1}{null} nulln1 o 1 1 → o 2 2 → 3 → 4 → 5 → n u l l \frac{o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1o1→2o2→3→4→5→null
搬移 o 1 1 → n 1 n u l l \frac{o1}{1} \rightarrow \frac{n1}{null} 1o1→nulln1 o 2 2 → 3 → 4 → 5 → n u l l \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2o2→3→4→5→null
指针复位 n 1 1 → n u l l \frac{n1}{1} \rightarrow null 1n1→null o 1 o 2 2 → 3 → 4 → 5 → n u l l \frac{o1 \ o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2o1 o2→3→4→5→null
重复 2 ∼ 4 2\sim4 2∼4 步当 o1 null 时退出循环
参考答案
public ListNode reverseList(ListNode o1) {if (o1 null || o1.next null) {return o1;}ListNode n1 null;while (o1 ! null) {ListNode o2 o1.next;o1.next n1;n1 o1;o1 o2;}return n1;
}评价本质上与方法2 相同只是方法2更为面向对象
E02. 根据值删除节点-力扣 203 题
例如
输入head [1,2,6,3,6], val 6
输出[1,2,3]输入head [], val 1
输出[]输入head [7,7,7,7], val 7
输出[]方法1
图中 s 代表 sentinel 哨兵如果不加哨兵则删除第一个节点要特殊处理例如要删除 6
p1 p2
s - 1 - 2 - 6 - 3 - 6 - null如果 p2 不等于目标则 p1p2 不断后移 p1 p2
s - 1 - 2 - 6 - 3 - 6 - nullp1 p2
s - 1 - 2 - 6 - 3 - 6 - nullp2 6删除它注意 p1 此时保持不变p2 后移 p1 p2
s - 1 - 2 - 3 - 6 - nullp2 不等于目标则 p1p2 不断后移 p1 p2
s - 1 - 2 - 3 - 6 - nullp2 6删除它注意 p1 此时保持不变p2 后移 p1 p2
s - 1 - 2 - 3 - nullp2 null 退出循环
最后代码
public ListNode removeElements(ListNode head, int val) {ListNode sentinel new ListNode(-1, head);ListNode p1 sentinel;ListNode p2;while ((p2 p1.next) ! null) {if (p2.val val) {p1.next p2.next;} else {p1 p1.next;}}return sentinel.next;
}方法2
思路递归函数负责返回从当前节点我开始完成删除的子链表
若我与 v 相等应该返回下一个节点递归结果若我与 v 不等应该返回我但我的 next 应该更新让我能带上后续删过的子链表
removeElements(ListNode p1, int v6){1.nextremoveElements(ListNode p2, int v6){2.nextremoveElements(ListNode p6, int v6){removeElements(ListNode p3, int v6){3.nextremoveElements(ListNode p6, int v6){removeElements(ListNode pnull, int v6){// 没有节点,返回return null}}return 3}}return 2}return 1
}代码
public ListNode removeElements(ListNode head, int val) {if (head null) {return null;}if (head.val val) {return removeElements(head.next, val);} else {head.next removeElements(head.next, val);return head;}
}E03. 删除倒数节点-力扣 19 题
例如
输入head [1,2,3,4,5], n 2
输出[1,2,3,5]输入head [1], n 1
输出[]输入head [1,2], n 1
输出[1]另外题目提示
链表至少一个节点n 只会在合理范围
方法1
思路写一个递归函数用来返回下一个节点的倒数序号
recursion(ListNode p1, int n2) {recursion(ListNode p2, int n2) {recursion(ListNode p3, int n2) {recursion(ListNode p4, int n2) {recursion(ListNode p5, int n2) {recursion(ListNode pnull, int n2) {return 0; // 最内层序号0}return 1; // 上一次返回值1}return 2;}if(返回值 n 2) {// 删除 next}return 3;}return 4;}return 5;
}但上述代码有一个问题就是若删除的是第一个节点它没有上一个节点因此可以加一个哨兵来解决
代码
public ListNode removeNthFromEnd(ListNode head, int n) {ListNode sentinel new ListNode(-1, head);recursion(sentinel, n);return sentinel.next;
}public int recursion(ListNode p, int n) {if (p null) {return 0;}int nth recursion(p.next, n);if (nth n) {p.next p.next.next;}return nth 1;
}Qp.next.next 不怕空指针吗
A
p 是待删除节点的上一个节点如果能递归回到 p那么 p.next 肯定有值不会是 null且题目说明了 n 1不会因为 nth 0 而让 p.next 指向最后的 null
方法2
快慢指针p1 指向待删节点的上一个p2 先走 n 1 步
i0
p2
s - 1 - 2 - 3 - 4 - 5 - nulli1p2
s - 1 - 2 - 3 - 4 - 5 - nulli2p2
s - 1 - 2 - 3 - 4 - 5 - nulli3 从此开始 p1 p2 依次向右平移, 直到 p2 移动到末尾
p1 p2
s - 1 - 2 - 3 - 4 - 5 - nullp1 p2
s - 1 - 2 - 3 - 4 - 5 - null代码
public ListNode removeNthFromEnd(ListNode head, int n) {ListNode s new ListNode(-1, head);ListNode p1 s;ListNode p2 s;for (int i 0; i n 1; i) {p2 p2.next;}while (p2 ! null) {p1 p1.next;p2 p2.next;}p1.next p1.next.next;return s.next;
}方法3
public ListNode removeNthFromEnd(ListNode head, int n) {Composite c recursion(head, n);return c.node;
}static class Composite {ListNode node;int nth;public Composite(ListNode node, int nth) {this.node node;this.nth nth;}
}public Composite recursion(ListNode p, int n) {if (p null) {return new Composite(null, 1);}Composite c recursion(p.next, n);if (c.nth ! n) {p.next c.node;c.node p;}c.nth 1;return c;
}E04. 有序链表去重-力扣 83 题
例如
输入head [1,1,2]
输出[1,2]输入head [1,1,2,3,3]
输出[1,2,3]注意重复元素保留一个
方法1
p1 p2
1 - 1 - 2 - 3 - 3 - nullp1.val p2.val 那么删除 p2注意 p1 此时保持不变
p1 p2
1 - 2 - 3 - 3 - nullp1.val ! p2.val 那么 p1p2 向后移动 p1 p2
1 - 2 - 3 - 3 - nullp1 p2
1 - 2 - 3 - 3 - null p1.val p2.val 那么删除 p2 p1 p2
1 - 2 - 3 - null 当 p2 null 退出循环
代码
public ListNode deleteDuplicates(ListNode head) {// 链表节点 2if (head null || head.next null) {return head;}// 链表节点 2ListNode p1 head;ListNode p2;while ((p2 p1.next) ! null) {if (p1.val p2.val) {p1.next p2.next;} else {p1 p1.next;}}return head;
}方法2
递归函数负责返回从当前节点我开始完成去重的链表
若我与 next 重复返回 next若我与 next 不重复返回我但 next 应当更新
deleteDuplicates(ListNode p1) {deleteDuplicates(ListNode p1) {1.nextdeleteDuplicates(ListNode p2) {2.nextdeleteDuplicates(ListNode p3) {deleteDuplicates(ListNode p3) {// 只剩一个节点返回return 3} }return 2}return 1}
}代码
public ListNode deleteDuplicates(ListNode p) {if (p null || p.next null) {return p;}if(p.val p.next.val) {return deleteDuplicates(p.next);} else {p.next deleteDuplicates(p.next);return p;}
}E05. 有序链表去重-力扣 82 题
例如
输入head [1,2,3,3,4,4,5]
输出[1,2,5]输入head [1,1,1,2,3]
输出[2,3]注意重复元素一个不留
方法1
递归函数负责返回从当前节点我开始完成去重的链表
若我与 next 重复一直找到下一个不重复的节点以它的返回结果为准若我与 next 不重复返回我同时更新 next
deleteDuplicates(ListNode p 1) {// 找下个不重复的deleteDuplicates(ListNode p 1) {deleteDuplicates(ListNode p 1) {deleteDuplicates(ListNode p 2) {2.nextdeleteDuplicates(ListNode p 3) {// 只剩一个节点返回return 3}return 2}}}
}代码
public ListNode deleteDuplicates(ListNode p) {if (p null || p.next null) {return p;}if (p.val p.next.val) {ListNode x p.next.next;while (x ! null x.val p.val) {x x.next;}return deleteDuplicates(x);} else {p.next deleteDuplicates(p.next);return p;}
}方法2
p1 是待删除的上一个节点每次循环对比 p2、p3 的值
如果 p2 与 p3 的值重复那么 p3 继续后移直到找到与 p2 不重复的节点p1 指向 p3 完成删除如果 p2 与 p3 的值不重复p1p2p3 向后平移一位继续上面的操作p2 或 p3 为 null 退出循环 p2 为 null 的情况比如链表为 1 1 1 null
p1 p2 p3
s, 1, 1, 1, 2, 3, nullp1 p2 p3
s, 1, 1, 1, 2, 3, nullp1 p2 p3
s, 1, 1, 1, 2, 3, nullp1 p3
s, 2, 3, nullp1 p2 p3
s, 2, 3, nullp1 p2 p3
s, 2, 3, null代码
public ListNode deleteDuplicates(ListNode head) {if (head null || head.next null) {return head;}ListNode s new ListNode(-1, head);ListNode p1 s;ListNode p2;ListNode p3;while ((p2 p1.next) ! null (p3 p2.next) ! null) {if (p2.val p3.val) {while ((p3 p3.next) ! null p3.val p2.val) {}p1.next p3;} else {p1 p1.next;}}return s.next;
}E06. 合并有序链表-力扣 21 题
例
输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]输入l1 [], l2 []
输出[]输入l1 [], l2 [0]
输出[0]方法1
谁小把谁链给 pp 和小的都向后平移一位当 p1、p2 有一个为 null退出循环把不为 null 的链给 p
p1
1 3 8 9 nullp2
2 4 nullp
s null代码
public ListNode mergeTwoLists(ListNode p1, ListNode p2) {ListNode s new ListNode(-1, null);ListNode p s;while (p1 ! null p2 ! null) {if (p1.val p2.val) {p.next p1;p1 p1.next;} else {p.next p2;p2 p2.next;}p p.next;}if (p1 ! null) {p.next p1;}if (p2 ! null) {p.next p2;}return s.next;
}可以自行验证例中后两种情况
方法2
递归函数应该返回
更小的那个链表节点并把它剩余节点与另一个链表再次递归返回之前更新此节点的 next
mergeTwoLists(p1[1,3,8,9], p2[2,4]) {1.nextmergeTwoLists(p1[3,8,9], p2[2,4]) {2.nextmergeTwoLists(p1[3,8,9], p2[4]) { 3.nextmergeTwoLists(p1[8,9], p2[4]) {4.nextmergeTwoLists(p1[8,9], p2null) {return [8,9]}return 4}return 3}return 2}return 1
}E07. 合并多个有序链表-力扣 23 题
例
输入lists [[1,4,5],[1,3,4],[2,6]]
输出[1,1,2,3,4,4,5,6]
解释链表数组如下
[1-4-5,1-3-4,2-6
]
将它们合并到一个有序链表中得到。
1-1-2-3-4-4-5-6方法1
递归
public ListNode mergeKLists(ListNode[] lists) {if (lists.length 0) {return null;}return merge(lists, 0, lists.length - 1);
}public ListNode split(ListNode[] lists, int i, int j) {System.out.println(i j);if (j i) {return lists[i];}int m (i j) 1;return mergeTwoLists(split(lists, i, m),split(lists, m 1, j));
}还可以用优先级队列求解这个放在后面讲
E08. 查找链表中间节点-力扣 876 题
例如
输入[1,2,3,4,5]
输出此列表中的结点 3 (序列化形式[3,4,5])输入[1,2,3,4,5,6]
输出此列表中的结点 4 (序列化形式[4,5,6])偶数节点时中间点是靠右的那个
解法快慢指针快指针一次走两步慢指针一次走一步当快指针到链表结尾时慢指针恰好走到链表的一半
public ListNode middleNode(ListNode head) {ListNode p1 head; // 慢指针中间点ListNode p2 head; // 快指针while (p2 ! null p2.next ! null) {p1 p1.next;p2 p2.next;p2 p2.next;}return p1;
}E09. 回文链表-力扣 234 题
所谓回文指正着读、反着读结果一样例如
[1,2,2,1]
[1,2,3,2,1]它们都是回文链表不是回文的例子
[1,2,3,1] --反过来-- [1,3,2,1]解法
/*步骤1. 找中间点步骤2. 中间点后半个链表反转步骤3. 反转后链表与原链表逐一比较
*/
public boolean isPalindrome(ListNode head) {ListNode middle middle(head);ListNode newHead reverse(middle);while (newHead ! null) {if (newHead.val ! head.val) {return false;}newHead newHead.next;head head.next;}return true;
}private ListNode reverse(ListNode o1) {ListNode n1 null;while (o1 ! null) {ListNode o2 o1.next;o1.next n1;n1 o1;o1 o2;}return n1;
}private ListNode middle(ListNode head) {ListNode p1 head; // 慢ListNode p2 head; // 快while (p2 ! null p2.next ! null) {p1 p1.next;p2 p2.next.next;}return p1;
}优化后解法
public boolean isPalindrome(ListNode h1) {if (h1 null || h1.next null) {return true;}ListNode p1 h1; // 慢指针中间点ListNode p2 h1; // 快指针ListNode n1 null; // 新头ListNode o1 h1; // 旧头// 快慢指针找中间点while (p2 ! null p2.next ! null) {p1 p1.next;p2 p2.next.next;// 反转前半部分o1.next n1;n1 o1;o1 p1;}if (p2 ! null) { // 节点数为奇数p1 p1.next;}// 同步比较新头和后半部分while (n1 ! null) {if (n1.val ! p1.val) {return false;}p1 p1.next;n1 n1.next;}return true;
}E10. 环形链表-力扣 141 题
本题以及下题实际是 Floyd’s Tortoise and Hare Algorithm Floyd 龟兔赛跑算法4 除了 Floyd 判环算法外还有其它的判环算法详见 https://en.wikipedia.org/wiki/Cycle_detection 如果链表上存在环那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。算法分为两个阶段
阶段1
龟一次走一步兔子一次走两步当兔子能走到终点时不存在环当兔子能追上龟时可以判断存在环
阶段2
从它们第一次相遇开始龟回到起点兔子保持原位不变龟和兔子一次都走一步当再次相遇时地点就是环的入口
为什么呢
设起点到入口走 a 步本例是 7绕环一圈长度为 b本例是 5那么从起点开始走 a 绕环 n 圈都能找到环入口第一次相遇时 兔走了 a 绕环 n 圈本例 2 圈 kk 是它们相遇距环入口位置本例 3不重要龟走了 a 绕环 n 圈本例 0 圈 k当然它绕的圈数比兔少兔走的距离是龟的两倍所以龟走的 兔走的 - 龟走的 绕环 n 圈 而前面分析过如果走 a 绕环 n 圈都能找到环入口因此从相遇点开始再走 a 步就是环入口
阶段1 参考代码判断是否有环
public boolean hasCycle(ListNode head) {ListNode h head; // 兔ListNode t head; // 龟while (h ! null h.next ! null) {t t.next;h h.next.next;if(h t){return true;}}return false;
}E11. 环形链表-力扣 142 题
阶段2 参考代码找到环入口
public ListNode detectCycle(ListNode head) {ListNode t head; // 龟ListNode h head; // 兔while (h ! null h.next ! null) {t t.next;h h.next.next;if (h t) {t head;while (true) {if (h t) {return h;}h h.next;t t.next;}}}return null;
}还有一道扩展题目也可以用判环算法思想来解就是 287 题寻找重复数
Ex1. 删除节点-力扣 237 题
这道题目比较简单留给大家自己练习
例如
输入head [4,5,1,9], node 5
输出[4,1,9]输入head [4,5,1,9], node 1
输出[4,5,9]注意被删除的节点不是末尾节点
参考答案
public class Ex1Leetcode237 {/**** param node 待删除节点, 题目已说明肯定不是最后一个节点*/public void deleteNode(ListNode node) {node.val node.next.val; // 下一个节点值赋值给待删除节点node.next node.next.next; // 把下一个节点删除}public static void main(String[] args) {ListNode o5 new ListNode(5, null);ListNode o4 new ListNode(4, o5);ListNode o3 new ListNode(3, o4);ListNode o2 new ListNode(2, o3);ListNode o1 new ListNode(1, o2);System.out.println(o1);new E0xLeetcode237().deleteNode(o3);System.out.println(o1);}
}输出
[1,2,3,4,5]
[1,2,4,5]Ex2. 共尾链表-力扣 160 题
原题叫做相交链表个人觉得用共尾链表更形象些此题更像是一道脑筋急转弯留给大家练习
例如下图的两个链表 [1, 2, 4, 5] 与 [3, 4, 5] 它们中 [4, 5] 是相同的此时应返回节点 4 非共尾的情况如下图所示此时返回 null 思路称两个链表为 a[1, 2, 4, 5]b[3, 4, 5]图中用 N 代表 null
遍历 a遇到 null 时改道遍历 b与此同时遍历 b遇到 null 时改道遍历 a在此过程中如果遇到相同的节点即为找寻目标返回即可如下图中的第二次出现的 4相同节点应该比较其引用值图中数字只是为了便于区分
1 2 4 5 N 3 4 5 N
3 4 5 N 1 2 4 5 N如果两个链表长度相同则可以更早找到目标例如 a[1, 4, 5]b[3, 4, 5]第一次出现 4 时即可返回
1 4 5 N 3 4 5 N
3 4 5 N 1 4 5 N如果是非共尾的情况如 a[1, 2, 4]b[3, 5]可以看到唯一相等的情况是遍历到最后那个 N 此时退出循环
1 2 4 N 3 5 N
3 5 N 1 2 4 N代码
public ListNode getIntersectionNode(ListNode a, ListNode b) {ListNode p1 a;ListNode p2 b;while (true) {if (p1 p2) {return p1;}if (p1 null) {p1 b;} else {p1 p1.next;}if (p2 null) {p2 a;} else {p2 p2.next;} }
}3.6 数组
E01. 合并有序数组
将数组内两个区间内的有序元素合并
例
[1, 5, 6, 2, 4, 10, 11]可以视作两个有序区间
[1, 5, 6] 和 [2, 4, 10, 11]合并后结果仍存储于原有空间
[1, 2, 4, 5, 6, 10, 11]方法1
递归
每次递归把更小的元素复制到结果数组
merge(left[1,5,6],right[2,4,10,11],a2[]){merge(left[5,6],right[2,4,10,11],a2[1]){merge(left[5,6],right[4,10,11],a2[1,2]){merge(left[5,6],right[10,11],a2[1,2,4]){merge(left[6],right[10,11],a2[1,2,4,5]){merge(left[],right[10,11],a2[1,2,4,5,6]){// 拷贝1011}}}}}
}代码
public static void merge(int[] a1, int i, int iEnd, int j, int jEnd,int[] a2, int k) {if (i iEnd) {System.arraycopy(a1, j, a2, k, jEnd - j 1);return;}if (j jEnd) {System.arraycopy(a1, i, a2, k, iEnd - i 1);return;}if (a1[i] a1[j]) {a2[k] a1[i];merge(a1, i 1, iEnd, j, jEnd, a2, k 1);} else {a2[k] a1[j];merge(a1, i, iEnd, j 1, jEnd, a2, k 1);}
}测试
int[] a1 {1, 5, 6, 2, 4, 10, 11};
int[] a2 new int[a1.length];
merge(a1, 0, 2, 3, 6, a2, 0);方法2
代码
public static void merge(int[] a1, int i, int iEnd,int j, int jEnd,int[] a2) {int k i;while (i iEnd j jEnd) {if (a1[i] a1[j]) {a2[k] a1[i];i;} else {a2[k] a1[j];j;}k;}if (i iEnd) {System.arraycopy(a1, j, a2, k, jEnd - j 1);}if (j jEnd) {System.arraycopy(a1, i, a2, k, iEnd - i 1);}
}测试
int[] a1 {1, 5, 6, 2, 4, 10, 11};
int[] a2 new int[a3.length];
merge(a1, 0, 2, 3, 6, a2);3.7 队列
E01. 二叉树层序遍历-力扣 102 题
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger result new ArrayList();if(root null) {return result;}LinkedListQueueTreeNode queue new LinkedListQueue();queue.offer(root);int c1 1; // 本层节点个数while (!queue.isEmpty()) {int c2 0; // 下层节点个数ListInteger level new ArrayList();for (int i 0; i c1; i) {TreeNode node queue.poll();level.add(node.val);if (node.left ! null) {queue.offer(node.left);c2;}if (node.right ! null) {queue.offer(node.right);c2;}}c1 c2;result.add(level);}return result;}// 自定义队列static class LinkedListQueueE {private static class NodeE {E value;NodeE next;public Node(E value, NodeE next) {this.value value;this.next next;}}private final NodeE head new Node(null, null);private NodeE tail head;int size 0;private int capacity Integer.MAX_VALUE;{tail.next head;}public LinkedListQueue() {}public LinkedListQueue(int capacity) {this.capacity capacity;}public boolean offer(E value) {if (isFull()) {return false;}NodeE added new Node(value, head);tail.next added;tail added;size;return true;}public E poll() {if (isEmpty()) {return null;}NodeE first head.next;head.next first.next;if (first tail) {tail head;}size--;return first.value;}public E peek() {if (isEmpty()) {return null;}return head.next.value;}public boolean isEmpty() {return head tail;}public boolean isFull() {return size capacity;}}
}Ex1. 设计队列-力扣 622 题
由于与课堂例题差别不大这里只给出参考解答
基于链表的实现
public class Ex1Leetcode622 {private static class Node {int value;Node next;Node(int value, Node next) {this.value value;this.next next;}}private final Node head new Node(-1, null);private Node tail head;private int size 0;private int capacity 0;{tail.next head;}public Ex1Leetcode622(int capacity) {this.capacity capacity;}public boolean enQueue(int value) {if(isFull()) {return false;}Node added new Node(value, head);tail.next added;tail added;size;return true;}public boolean deQueue() {if(isEmpty()) {return false;}Node first head.next;head.next first.next;if (first tail) {tail head;}size--;return true;}public int Front() {if(isEmpty()) {return -1;}return head.next.value;}public int Rear() {if(isEmpty()) {return -1;}return tail.value;}public boolean isEmpty() {return head tail;}public boolean isFull() {return size capacity;}
}注意
Leetcode 的实现里 deQueue出队返回值是布尔值并不会返回队头元素它期望用法是先用 Front 返回对头元素再 deQueue 出队
3.8 栈
E01. 有效的括号-力扣 20 题
一个字符串中可能出现 [] () 和 {} 三种括号判断该括号是否有效
有效的例子
()[]{}([{}])()无效的例子
[)([)]([]思路
遇到左括号, 把要配对的右括号放入栈顶遇到右括号, 若此时栈为空, 返回 false否则把它与栈顶元素对比 若相等, 栈顶元素弹出, 继续对比下一组若不等, 无效括号直接返回 false 循环结束 若栈为空, 表示所有括号都配上对, 返回 true若栈不为空, 表示右没配对的括号, 应返回 false
答案用到了课堂案例中的 ArrayStack 类
public boolean isValid(String s) {ArrayStackCharacter stack new ArrayStack(s.length() / 2 1);for (int i 0; i s.length(); i) {char c s.charAt(i);if (c () {stack.push());} else if (c [) {stack.push(]);} else if (c {) {stack.push(});} else {if (!stack.isEmpty() stack.peek() c) {stack.pop();} else {return false;}}}return stack.isEmpty();
}E02. 后缀表达式求值-力扣 120 题
后缀表达式也称为逆波兰表达式即运算符写在后面
从左向右进行计算不必考虑运算符优先级即不用包含括号
示例
输入tokens [2,1,,3,*]
输出9
即(2 1) * 3输入tokens [4,13,5,/,]
输出6
即4 (13 / 5)题目假设
数字都视为整数数字和运算符个数给定正确不会有除零发生
代码
public int evalRPN(String[] tokens) {LinkedListInteger numbers new LinkedList();for (String t : tokens) {switch (t) {case - {Integer b numbers.pop();Integer a numbers.pop();numbers.push(a b);}case - - {Integer b numbers.pop();Integer a numbers.pop();numbers.push(a - b);}case * - {Integer b numbers.pop();Integer a numbers.pop();numbers.push(a * b);}case / - {Integer b numbers.pop();Integer a numbers.pop();numbers.push(a / b);}default - numbers.push(Integer.parseInt(t));}}return numbers.pop();
}E03. 中缀表达式转后缀
public class E03InfixToSuffix {/*思路1. 遇到数字, 拼串2. 遇到 - * /- 优先级高于栈顶运算符 入栈- 否则将栈中高级或平级运算符出栈拼串, 本运算符入栈3. 遍历完成, 栈中剩余运算符出栈拼串- 先出栈,意味着优先运算4. 带 ()- 左括号直接入栈- 右括号要将栈中直至左括号为止的运算符出栈拼串| || || |_____abab-cab*ca*bc(ab)*c*/public static void main(String[] args) {System.out.println(infixToSuffix(ab));System.out.println(infixToSuffix(ab-c));System.out.println(infixToSuffix(ab*c));System.out.println(infixToSuffix(a*b-c));System.out.println(infixToSuffix((ab)*c));System.out.println(infixToSuffix(ab*c(d*ef)*g));}static String infixToSuffix(String exp) {LinkedListCharacter stack new LinkedList();StringBuilder sb new StringBuilder(exp.length());for (int i 0; i exp.length(); i) {char c exp.charAt(i);switch (c) {case , -, *, / - {if (stack.isEmpty()) {stack.push(c);} else {if (priority(c) priority(stack.peek())) {stack.push(c);} else {while (!stack.isEmpty() priority(stack.peek()) priority(c)) {sb.append(stack.pop());}stack.push(c);}}}case ( - {stack.push(c);}case ) - {while (!stack.isEmpty() stack.peek() ! () {sb.append(stack.pop());}stack.pop();}default - {sb.append(c);}}}while (!stack.isEmpty()) {sb.append(stack.pop());}return sb.toString();}static int priority(char c) {return switch (c) {case ( - 0;case *, / - 2;case , - - 1;default - throw new IllegalArgumentException(不合法字符: c);};}
}E04. 双栈模拟队列-力扣 232 题
给力扣题目用的自实现栈可以定义为静态内部类
class ArrayStackE {private E[] array;private int top; // 栈顶指针SuppressWarnings(all)public ArrayStack(int capacity) {this.array (E[]) new Object[capacity];}public boolean push(E value) {if (isFull()) {return false;}array[top] value;return true;}public E pop() {if (isEmpty()) {return null;}return array[--top];}public E peek() {if (isEmpty()) {return null;}return array[top - 1];}public boolean isEmpty() {return top 0;}public boolean isFull() {return top array.length;}
}参考解答注意题目已说明
调用 push、pop 等方法的次数最多 100
public class E04Leetcode232 {/*队列头 队列尾s1 s2顶 底 底 顶abcpush(a)push(b)push(c)pop()*/ArrayStackInteger s1 new ArrayStack(100);ArrayStackInteger s2 new ArrayStack(100);public void push(int x) {s2.push(x);}public int pop() {if (s1.isEmpty()) {while (!s2.isEmpty()) {s1.push(s2.pop());}}return s1.pop();}public int peek() {if (s1.isEmpty()) {while (!s2.isEmpty()) {s1.push(s2.pop());}}return s1.peek();}public boolean empty() {return s1.isEmpty() s2.isEmpty();}}E05. 单队列模拟栈-力扣 225 题
给力扣题目用的自实现队列可以定义为静态内部类
public class ArrayQueue3E {private final E[] array;int head 0;int tail 0;SuppressWarnings(all)public ArrayQueue3(int c) {c - 1;c | c 1;c | c 2;c | c 4;c | c 8;c | c 16;c 1;array (E[]) new Object[c];}public boolean offer(E value) {if (isFull()) {return false;} array[tail (array.length - 1)] value;tail;return true;}public E poll() {if (isEmpty()) {return null;}E value array[head (array.length - 1)];head;return value;}public E peek() {if (isEmpty()) {return null;}return array[head (array.length - 1)];}public boolean isEmpty() {return head tail;}public boolean isFull() {return tail - head array.length;}
}参考解答注意题目已说明
调用 push、pop 等方法的次数最多 100每次调用 pop 和 top 都能保证栈不为空
public class E05Leetcode225 {/*队列头 队列尾cba顶 底queue.offer(a)queue.offer(b)queue.offer(c)*/ArrayQueue3Integer queue new ArrayQueue3(100);int size 0;public void push(int x) {queue.offer(x);for (int i 0; i size; i) {queue.offer(queue.poll());}size;}public int pop() {size--;return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}3.9 双端队列
E01. 二叉树 Z 字层序遍历-力扣 103 题
public class E01Leetcode103 {public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger result new ArrayList();if (root null) {return result;}LinkedListTreeNode queue new LinkedList();queue.offer(root);boolean leftToRight true;int c1 1;while (!queue.isEmpty()) {int c2 0;LinkedListInteger deque new LinkedList();for (int i 0; i c1; i) {TreeNode n queue.poll();if (leftToRight) {deque.offerLast(n.val);} else {deque.offerFirst(n.val);}if (n.left ! null) {queue.offer(n.left);c2;}if (n.right ! null) {queue.offer(n.right);c2;}}c1 c2;leftToRight !leftToRight;result.add(deque);}return result;}public static void main(String[] args) {TreeNode root new TreeNode(new TreeNode(new TreeNode(4),2,new TreeNode(5)),1,new TreeNode(new TreeNode(6),3,new TreeNode(7)));ListListInteger lists new E01Leetcode103().zigzagLevelOrder(root);for (ListInteger list : lists) {System.out.println(list);}}
}Ex1. 设计双端队列-力扣 641 题
与课堂例题也是差别不大请参考
3.10 优先级队列
E01. 合并多个有序链表-力扣 23 题
这道题目之前解答过现在用刚学的优先级队列来实现一下
题目中要从小到大排列因此选择用小顶堆来实现自定义小顶堆如下
public class MinHeap {ListNode[] array;int size;public MinHeap(int capacity) {array new ListNode[capacity];}public void offer(ListNode offered) {int child size;int parent (child - 1) / 2;while (child 0 offered.val array[parent].val) {array[child] array[parent];child parent;parent (child - 1) / 2;}array[child] offered;}public ListNode poll() {if (isEmpty()) {return null;}swap(0, size - 1);size--;ListNode e array[size];array[size] null; // help GCdown(0);return e;}private void down(int parent) {int left 2 * parent 1;int right left 1;int min parent;if (left size array[left].val array[min].val) {min left;}if (right size array[right].val array[min].val) {min right;}if (min ! parent) {swap(min, parent);down(min);}}private void swap(int i, int j) {ListNode t array[i];array[i] array[j];array[j] t;}public boolean isEmpty() {return size 0;}
}代码
public class E01Leetcode23 {public ListNode mergeKLists(ListNode[] lists) {// 1. 使用 jdk 的优先级队列实现
// PriorityQueueListNode queue new PriorityQueue(Comparator.comparingInt(a - a.val));// 2. 使用自定义小顶堆实现MinHeap queue new MinHeap(lists.length);for (ListNode head : lists) {if (head ! null) {queue.offer(head);}}ListNode s new ListNode(-1, null);ListNode p s;while (!queue.isEmpty()) {ListNode node queue.poll();p.next node;p node;if (node.next ! null) {queue.offer(node.next);}}return s.next;}
}提问
能否将每个链表的所有元素全部加入堆再一个个从堆顶移除
回答
可以是可以但对空间占用就高了堆的一个优点就是用有限的空间做事情
3.11 堆
E01. 堆排序
算法描述
heapify 建立大顶堆将堆顶与堆底交换最大元素被交换到堆底缩小并下潜调整堆重复第二步直至堆里剩一个元素
可以使用之前课堂例题的大顶堆来实现
int[] array {1, 2, 3, 4, 5, 6, 7};
MaxHeap maxHeap new MaxHeap(array);
System.out.println(Arrays.toString(maxHeap.array));while (maxHeap.size 1) {maxHeap.swap(0, maxHeap.size - 1);maxHeap.size--;maxHeap.down(0);
}
System.out.println(Arrays.toString(maxHeap.array));E02. 数组中第K大元素-力扣 215 题
小顶堆可删去用不到代码
class MinHeap {int[] array;int size;public MinHeap(int capacity) {array new int[capacity];}private void heapify() {for (int i (size 1) - 1; i 0; i--) {down(i);}}public int poll() {swap(0, size - 1);size--;down(0);return array[size];}public int poll(int index) {swap(index, size - 1);size--;down(index);return array[size];}public int peek() {return array[0];}public boolean offer(int offered) {if (size array.length) {return false;}up(offered);size;return true;}public void replace(int replaced) {array[0] replaced;down(0);}private void up(int offered) {int child size;while (child 0) {int parent (child - 1) 1;if (offered array[parent]) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}private void down(int parent) {int left (parent 1) 1;int right left 1;int min parent;if (left size array[left] array[min]) {min left;}if (right size array[right] array[min]) {min right;}if (min ! parent) {swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}
}题解
public int findKthLargest(int[] numbers, int k) {MinHeap heap new MinHeap(k);for (int i 0; i k; i) {heap.offer(numbers[i]);}for (int i k; i numbers.length; i) {if(numbers[i] heap.peek()){heap.replace(numbers[i]);}}return heap.peek();
}求数组中的第 K 大元素使用堆并不是最佳选择可以采用快速选择算法 E03. 数据流中第K大元素-力扣 703 题
上题的小顶堆加一个方法
class MinHeap {// ...public boolean isFull() {return size array.length;}
}题解
class KthLargest {private MinHeap heap;public KthLargest(int k, int[] nums) {heap new MinHeap(k);for(int i 0; i nums.length; i) {add(nums[i]);}}public int add(int val) {if(!heap.isFull()){heap.offer(val);} else if(val heap.peek()){heap.replace(val);}return heap.peek();}}求数据流中的第 K 大元素使用堆最合适不过 E04. 数据流的中位数-力扣 295 题
可以扩容的 heap, max 用于指定是大顶堆还是小顶堆
public class Heap {int[] array;int size;boolean max;public int size() {return size;}public Heap(int capacity, boolean max) {this.array new int[capacity];this.max max;}/*** 获取堆顶元素** return 堆顶元素*/public int peek() {return array[0];}/*** 删除堆顶元素** return 堆顶元素*/public int poll() {int top array[0];swap(0, size - 1);size--;down(0);return top;}/*** 删除指定索引处元素** param index 索引* return 被删除元素*/public int poll(int index) {int deleted array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素** param replaced 新元素*/public void replace(int replaced) {array[0] replaced;down(0);}/*** 堆的尾部添加元素** param offered 新元素*/public void offer(int offered) {if (size array.length) {grow();}up(offered);size;}private void grow() {int capacity size (size 1);int[] newArray new int[capacity];System.arraycopy(array, 0,newArray, 0, size);array newArray;}// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child size;while (child 0) {int parent (child - 1) / 2;boolean cmp max ? offered array[parent] : offered array[parent];if (cmp) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}public Heap(int[] array, boolean max) {this.array array;this.size array.length;this.max max;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 size / 2 - 1for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left parent * 2 1;int right left 1;int min parent;if (left size (max ? array[left] array[min] : array[left] array[min])) {min left;}if (right size (max ? array[right] array[min] : array[right] array[min])) {min right;}if (min ! parent) { // 找到了更大的孩子swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}
}题解
private Heap left new Heap(10, false);
private Heap right new Heap(10, true);/**为了保证两边数据量的平衡ulli两边数据一样时,加入左边/lili两边数据不一样时,加入右边/li/ul但是, 随便一个数能直接加入吗?ulli加入左边前, 应该挑右边最小的加入/lili加入右边前, 应该挑左边最大的加入/li/ul*/
public void addNum(int num) {if (left.size() right.size()) {right.offer(num);left.offer(right.poll());} else {left.offer(num);right.offer(left.poll());}
}/*** ul* li两边数据一致, 左右各取堆顶元素求平均/li* li左边多一个, 取左边元素/li* /ul*/
public double findMedian() {if (left.size() right.size()) {return (left.peek() right.peek()) / 2.0;} else {return left.peek();}
}本题还可以使用平衡二叉搜索树求解不过代码比两个堆复杂 3.12 二叉树
E04. 对称二叉树-力扣 101 题
public boolean isSymmetric(TreeNode root) {return check(root.left, root.right);
}public boolean check(TreeNode left, TreeNode right) {// 若同时为 nullif (left null right null) {return true;}// 若有一个为 null (有上一轮筛选另一个肯定不为 null)if (left null || right null) {return false;}if (left.val ! right.val) {return false;}return check(left.left, right.right) check(left.right, right.left);
}类似题目Leetcode 100 题 - 相同的树
E05. 二叉树最大深度-力扣 104 题
后序遍历求解
/*思路1. 得到左子树深度, 得到右子树深度, 二者最大者加一, 就是本节点深度2. 因为需要先得到左右子树深度, 很显然是后序遍历典型应用3. 关于深度的定义从根出发, 离根最远的节点总边数,注意: 力扣里的深度定义要多一深度2 深度3 深度11 1 1/ \ / \2 3 2 3\4*/
public int maxDepth(TreeNode node) {if (node null) {return 0; // 非力扣题目改为返回 -1}int d1 maxDepth(node.left);int d2 maxDepth(node.right);return Integer.max(d1, d2) 1;
}后序遍历求解-非递归
/*思路1. 使用非递归后序遍历, 栈的最大高度即为最大深度*/
public int maxDepth(TreeNode root) {TreeNode curr root;LinkedListTreeNode stack new LinkedList();int max 0;TreeNode pop null;while (curr ! null || !stack.isEmpty()) {if (curr ! null) {stack.push(curr);int size stack.size();if (size max) {max size;}curr curr.left;} else {TreeNode peek stack.peek();if(peek.right null || peek.right pop) {pop stack.pop();} else {curr peek.right;}}}return max;
}层序遍历求解
/*思路1. 使用层序遍历, 层数即最大深度*/
public int maxDepth(TreeNode root) {if(root null) {return 0;}QueueTreeNode queue new LinkedList();queue.offer(root);int level 0;while (!queue.isEmpty()) {level;int size queue.size();for (int i 0; i size; i) {TreeNode node queue.poll();if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}}return level;
}E06. 二叉树最小深度-力扣 111 题
后序遍历求解
public int minDepth(TreeNode node) {if (node null) {return 0;}int d1 minDepth(node.left);int d2 minDepth(node.right);if (d1 0 || d2 0) {return d1 d2 1;}return Integer.min(d1, d2) 1;
}相较于求最大深度应当考虑
当右子树为 null应当返回左子树深度加一当左子树为 null应当返回右子树深度加一
上面两种情况满足时不应该再把为 null 子树的深度 0 参与最小值比较例如这样 1/2正确深度为 2若把为 null 的右子树的深度 0 考虑进来会得到错误结果 1 1\3\4正确深度为 3若把为 null 的左子树的深度 0 考虑进来会得到错误结果 1
层序遍历求解
遇到的第一个叶子节点所在层就是最小深度
例如下面的树遇到的第一个叶子节点 3 所在的层就是最小深度其他 47 等叶子节点深度更深也更晚遇到 1/ \ 2 3/ \4 5 /7 代码
public int minDepth(TreeNode root) {if(root null) {return 0;}QueueTreeNode queue new LinkedList();queue.offer(root);int level 0;while (!queue.isEmpty()) {level;int size queue.size();for (int i 0; i size; i) {TreeNode node queue.poll();if (node.left null node.right null) {return level;}if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}}return level;
}效率会高于之前后序遍历解法因为找到第一个叶子节点后就无需后续的层序遍历了
E07. 翻转二叉树-力扣 226 题
public TreeNode invertTree(TreeNode root) {fn(root);return root;
}private void fn(TreeNode node){if (node null) {return;}TreeNode t node.left;node.left node.right;node.right t;fn(node.left);fn(node.right);
}先交换、再递归或是先递归、再交换都可以
E08. 后缀表达式转二叉树
static class TreeNode {public String val;public TreeNode left;public TreeNode right;public TreeNode(String val) {this.val val;}public TreeNode(TreeNode left, String val, TreeNode right) {this.left left;this.val val;this.right right;}Overridepublic String toString() {return this.val;}
}/*中缀表达式 (2-1)*3后缀逆波兰表达式 21-3*1.遇到数字入栈2.遇到运算符, 出栈两次, 与当前节点建立父子关系, 当前节点入栈栈| || || |_____表达式树*/ \- 3/ \2 121-3**/
public TreeNode constructExpressionTree(String[] tokens) {LinkedListTreeNode stack new LinkedList();for (String t : tokens) {switch (t) {case , -, *, / - { // 运算符TreeNode right stack.pop();TreeNode left stack.pop();TreeNode parent new TreeNode(t);parent.left left;parent.right right;stack.push(parent);}default - { // 数字stack.push(new TreeNode(t));}}}return stack.peek();
}E09. 根据前序与中序遍历结果构造二叉树-力扣 105 题
先通过前序遍历结果定位根节点再结合中序遍历结果切分左右子树
public class E09Leetcode105 {/*preOrder {1,2,4,3,6,7}inOrder {4,2,1,6,3,7}根 1pre in左 2,4 4,2右 3,6,7 6,3,7根 2左 4根 3左 6右 7*/public TreeNode buildTree(int[] preOrder, int[] inOrder) {if (preOrder.length 0) {return null;}// 创建根节点int rootValue preOrder[0];TreeNode root new TreeNode(rootValue);// 区分左右子树for (int i 0; i inOrder.length; i) {if (inOrder[i] rootValue) {// 0 ~ i-1 左子树// i1 ~ inOrder.length -1 右子树int[] inLeft Arrays.copyOfRange(inOrder, 0, i); // [4,2]int[] inRight Arrays.copyOfRange(inOrder, i 1, inOrder.length); // [6,3,7]int[] preLeft Arrays.copyOfRange(preOrder, 1, i 1); // [2,4]int[] preRight Arrays.copyOfRange(preOrder, i 1, inOrder.length); // [3,6,7]root.left buildTree(preLeft, inLeft); // 2root.right buildTree(preRight, inRight); // 3break;}}return root;}}代码可以进一步优化涉及新数据结构以后实现
E10. 根据中序与后序遍历结果构造二叉树-力扣 106 题
先通过后序遍历结果定位根节点再结合中序遍历结果切分左右子树
public TreeNode buildTree(int[] inOrder, int[] postOrder) {if (inOrder.length 0) {return null;}// 根int rootValue postOrder[postOrder.length - 1];TreeNode root new TreeNode(rootValue);// 切分左右子树for (int i 0; i inOrder.length; i) {if (inOrder[i] rootValue) {int[] inLeft Arrays.copyOfRange(inOrder, 0, i);int[] inRight Arrays.copyOfRange(inOrder, i 1, inOrder.length);int[] postLeft Arrays.copyOfRange(postOrder, 0, i);int[] postRight Arrays.copyOfRange(postOrder, i, postOrder.length - 1);root.left buildTree(inLeft, postLeft);root.right buildTree(inRight, postRight);break;}}return root;
}代码可以进一步优化涉及新数据结构以后实现
附录
参考文章
落选题目
反转字符数组
public static void main(String[] args) {char[] array abcde.toCharArray();recursion(array, 0, array.length - 1);System.out.println(Arrays.toString(array));
}public static void recursion(char[] array, int i, int j) {if (i j) {return;}swap(array, i, j);recursion(array, i, --j);
}public static void swap(char[] array, int i, int j) {char c array[i];array[i] array[j];array[j] c;
}第一次交换的是 array[0] 和 array[4]第二次交换的是 array[1] 和 array[3]第三次 i j 2开始返回如果 array.length 是偶数则会在 i j 时返回
力扣高评价题目列表
引用自 面试最常考的 100 道算法题分类整理 - 知乎 (zhihu.com) 带 ✔️ 是本课程讲解过的 1. Two Sum (两数之和), Easy, 11757 likes ✔️2. Add Two Numbers (两数相加), Medium, 6524 likes3. Longest Substring Without Repeating Characters (无重复字符的最长子串), Medium, 5845 likes ✔️4. Median of Two Sorted Arrays (寻找两个正序数组的中位数), Hard, 4303 likes5. Longest Palindromic Substring (最长回文子串), Medium, 3896 likes15. 3Sum (三数之和), Medium, 3582 likes53. Maximum Subarray (最大子序和), Easy, 3533 likes7. Reverse Integer (整数反转), Easy, 2970 likes11. Container With Most Water (盛最多水的容器), Medium, 2659 likes42. Trapping Rain Water (接雨水), Hard, 2552 likes20. Valid Parentheses (有效的括号), Easy, 2544 likes ✔️10. Regular Expression Matching (正则表达式匹配), Hard, 2273 likes26. Remove Duplicates from Sorted Array (删除有序数组中的重复项), Easy, 2146 likes ✔️136. Single Number (只出现一次的数字), Easy, 1958 likes ✔️22. Generate Parentheses (括号生成), Medium, 1946 likes206. Reverse Linked List (反转链表), Easy, 1886 likes ✔️21. Merge Two Sorted Lists (合并两个有序链表), Easy, 1832 likes ✔️70. Climbing Stairs (爬楼梯), Easy, 1791 likes ✔️300. Longest Increasing Subsequence (最长递增子序列), Medium, 1773 likes121. Best Time to Buy and Sell Stock (买卖股票的最佳时机), Easy, 1766 likes72. Edit Distance (编辑距离), Hard, 1743 likes14. Longest Common Prefix (最长公共前缀), Easy, 1707 likes198. House Robber (打家劫舍), Medium, 1585 likes9. Palindrome Number (回文数), Easy, 1568 likes146. LRU Cache (LRU 缓存机制), Medium, 1544 likes19. Remove Nth Node From End of List (删除链表的倒数第 N 个结点), Medium, 1494 likes ✔️33. Search in Rotated Sorted Array (搜索旋转排序数组), Medium, 1493 likes46. Permutations (全排列), Medium, 1484 likes101. Symmetric Tree (对称二叉树), Easy, 1483 likes ✔️84. Largest Rectangle in Histogram (柱状图中最大的矩形), Hard, 1472 likes39. Combination Sum (组合总和), Medium, 1466 likes13. Roman to Integer (罗马数字转整数), Easy, 1436 likes23. Merge k Sorted Lists (合并K个升序链表), Hard, 1436 likes ✔️17. Letter Combinations of a Phone Number (电话号码的字母组合), Medium, 1436 likes322. Coin Change (零钱兑换), Medium, 1414 likes32. Longest Valid Parentheses (最长有效括号), Hard, 1400 likes287. Find the Duplicate Number (寻找重复数), Medium, 1325 likes122. Best Time to Buy and Sell Stock II (买卖股票的最佳时机 II), Easy, 1306 likes160. Intersection of Two Linked Lists (相交链表), Easy, 1302 likes ✔️55. Jump Game (跳跃游戏), Medium, 1292 likes76. Minimum Window Substring (最小覆盖子串), Hard, 1280 likes200. Number of Islands (岛屿数量), Medium, 1270 likes78. Subsets (子集), Medium, 1269 likes31. Next Permutation (下一个排列), Medium, 1260 likes96. Unique Binary Search Trees (不同的二叉搜索树), Medium, 1257 likes148. Sort List (排序链表), Medium, 1248 likes236. Lowest Common Ancestor of a Binary Tree (二叉树的最近公共祖先), Medium, 1238 likes ✔️25. Reverse Nodes in k-Group (K 个一组翻转链表), Hard, 1230 likes6. ZigZag Conversion (Z 字形变换), Medium, 1226 likes152. Maximum Product Subarray (乘积最大子数组), Medium, 1223 likes215. Kth Largest Element in an Array (数组中的第K个最大元素), Medium, 1211 likes ✔️8. String to Integer (atoi) (字符串转换整数 (atoi)), Medium, 1168 likes41. First Missing Positive (缺失的第一个正数), Hard, 1163 likes283. Move Zeroes (移动零), Easy, 1162 likes141. Linked List Cycle (环形链表), Easy, 1161 likes ✔️98. Validate Binary Search Tree (验证二叉搜索树), Medium, 1156 likes ✔️124. Binary Tree Maximum Path Sum (二叉树中的最大路径和), Hard, 1152 likes105. Construct Binary Tree from Preorder and Inorder Traversal (从前序与中序遍历序列构造二叉树), Medium, 1149 likes ✔️34. Find First and Last Position of Element in Sorted Array (在排序数组中查找元素的第一个和最后一个位置), Medium, 1137 likes ✔️239. Sliding Window Maximum (滑动窗口最大值), Hard, 1114 likes142. Linked List Cycle II (环形链表 II), Medium, 1097 likes ✔️139. Word Break (单词拆分), Medium, 1097 likes45. Jump Game II (跳跃游戏 II), Medium, 1094 likes169. Majority Element (多数元素), Easy, 1089 likes234. Palindrome Linked List (回文链表), Easy, 1072 likes ✔️62. Unique Paths (不同路径), Medium, 1072 likes189. Rotate Array (旋转数组), Medium, 1057 likes94. Binary Tree Inorder Traversal (二叉树的中序遍历), Easy, 1052 likes ✔️56. Merge Intervals (合并区间), Medium, 1051 likes88. Merge Sorted Array (合并两个有序数组), Easy, 1041 likes ✔️560. Subarray Sum Equals K (和为K的子数组), Medium, 1036 likes279. Perfect Squares (完全平方数), Medium, 1035 likes35. Search Insert Position (搜索插入位置), Easy, 1005 likes24. Swap Nodes in Pairs (两两交换链表中的节点), Medium, 996 likes85. Maximal Rectangle (最大矩形), Hard, 983 likes28. Implement strStr() (实现 strStr()), Easy, 982 likes92. Reverse Linked List II (反转链表 II), Medium, 980 likes155. Min Stack (最小栈), Easy, 979 likes79. Word Search (单词搜索), Medium, 979 likes27. Remove Element (移除元素), Easy, 967 likes51. N-Queens (N 皇后), Hard, 965 likes75. Sort Colors (颜色分类), Medium, 961 likes102. Binary Tree Level Order Traversal (二叉树的层序遍历), Medium, 960 likes ✔️48. Rotate Image (旋转图像), Medium, 960 likes95. Unique Binary Search Trees II (不同的二叉搜索树 II), Medium, 955 likes64. Minimum Path Sum (最小路径和), Medium, 954 likes406. Queue Reconstruction by Height (根据身高重建队列), Medium, 947 likes226. Invert Binary Tree (翻转二叉树), Easy, 941 likes ✔️437. Path Sum III (路径总和 III), Medium, 937 likes104. Maximum Depth of Binary Tree (二叉树的最大深度), Easy, 937 likes ✔️237. Delete Node in a Linked List (删除链表中的节点), Easy, 936 likes ✔️337. House Robber III (打家劫舍 III), Medium, 929 likes18. 4Sum (四数之和), Medium, 918 likes91. Decode Ways (解码方法), Medium, 904 likes207. Course Schedule (课程表), Medium, 897 likes37. Sudoku Solver (解数独), Hard, 897 likes175. Combine Two Tables (组合两个表), Easy, 891 likes416. Partition Equal Subset Sum (分割等和子集), Medium, 886 likes238. Product of Array Except Self (除自身以外数组的乘积), Medium, 885 likes114. Flatten Binary Tree to Linked List (二叉树展开为链表), Medium, 877 likes ✔️ n/)**, Medium, 1260 likes96. Unique Binary Search Trees (不同的二叉搜索树), Medium, 1257 likes148. Sort List (排序链表), Medium, 1248 likes236. Lowest Common Ancestor of a Binary Tree (二叉树的最近公共祖先), Medium, 1238 likes ✔️25. Reverse Nodes in k-Group (K 个一组翻转链表), Hard, 1230 likes6. ZigZag Conversion (Z 字形变换), Medium, 1226 likes152. Maximum Product Subarray (乘积最大子数组), Medium, 1223 likes215. Kth Largest Element in an Array (数组中的第K个最大元素), Medium, 1211 likes ✔️8. String to Integer (atoi) (字符串转换整数 (atoi)), Medium, 1168 likes41. First Missing Positive (缺失的第一个正数), Hard, 1163 likes283. Move Zeroes (移动零), Easy, 1162 likes141. Linked List Cycle (环形链表), Easy, 1161 likes ✔️98. Validate Binary Search Tree (验证二叉搜索树), Medium, 1156 likes ✔️124. Binary Tree Maximum Path Sum (二叉树中的最大路径和), Hard, 1152 likes105. Construct Binary Tree from Preorder and Inorder Traversal (从前序与中序遍历序列构造二叉树), Medium, 1149 likes ✔️34. Find First and Last Position of Element in Sorted Array (在排序数组中查找元素的第一个和最后一个位置), Medium, 1137 likes ✔️239. Sliding Window Maximum (滑动窗口最大值), Hard, 1114 likes142. Linked List Cycle II (环形链表 II), Medium, 1097 likes ✔️139. Word Break (单词拆分), Medium, 1097 likes45. Jump Game II (跳跃游戏 II), Medium, 1094 likes169. Majority Element (多数元素), Easy, 1089 likes234. Palindrome Linked List (回文链表), Easy, 1072 likes ✔️62. Unique Paths (不同路径), Medium, 1072 likes189. Rotate Array (旋转数组), Medium, 1057 likes94. Binary Tree Inorder Traversal (二叉树的中序遍历), Easy, 1052 likes ✔️56. Merge Intervals (合并区间), Medium, 1051 likes88. Merge Sorted Array (合并两个有序数组), Easy, 1041 likes ✔️560. Subarray Sum Equals K (和为K的子数组), Medium, 1036 likes279. Perfect Squares (完全平方数), Medium, 1035 likes35. Search Insert Position (搜索插入位置), Easy, 1005 likes24. Swap Nodes in Pairs (两两交换链表中的节点), Medium, 996 likes85. Maximal Rectangle (最大矩形), Hard, 983 likes28. Implement strStr() (实现 strStr()), Easy, 982 likes92. Reverse Linked List II (反转链表 II), Medium, 980 likes155. Min Stack (最小栈), Easy, 979 likes79. Word Search (单词搜索), Medium, 979 likes27. Remove Element (移除元素), Easy, 967 likes51. N-Queens (N 皇后), Hard, 965 likes75. Sort Colors (颜色分类), Medium, 961 likes102. Binary Tree Level Order Traversal (二叉树的层序遍历), Medium, 960 likes ✔️48. Rotate Image (旋转图像), Medium, 960 likes95. Unique Binary Search Trees II (不同的二叉搜索树 II), Medium, 955 likes64. Minimum Path Sum (最小路径和), Medium, 954 likes406. Queue Reconstruction by Height (根据身高重建队列), Medium, 947 likes226. Invert Binary Tree (翻转二叉树), Easy, 941 likes ✔️437. Path Sum III (路径总和 III), Medium, 937 likes104. Maximum Depth of Binary Tree (二叉树的最大深度), Easy, 937 likes ✔️237. Delete Node in a Linked List (删除链表中的节点), Easy, 936 likes ✔️337. House Robber III (打家劫舍 III), Medium, 929 likes18. 4Sum (四数之和), Medium, 918 likes91. Decode Ways (解码方法), Medium, 904 likes207. Course Schedule (课程表), Medium, 897 likes37. Sudoku Solver (解数独), Hard, 897 likes175. Combine Two Tables (组合两个表), Easy, 891 likes416. Partition Equal Subset Sum (分割等和子集), Medium, 886 likes238. Product of Array Except Self (除自身以外数组的乘积), Medium, 885 likes114. Flatten Binary Tree to Linked List (二叉树展开为链表), Medium, 877 likes ✔️ Josephus problem 主要参考 https://en.wikipedia.org/wiki/Josephus_problem ↩︎ 汉诺塔图片资料均来自 https://en.wikipedia.org/wiki/Tower_of_Hanoi ↩︎ 也称为 Pascal’s triangle https://en.wikipedia.org/wiki/Pascal%27s_triangle ↩︎ 龟兔赛跑动画来自于 Floyd’s Hare and Tortoise Algorithm Demo - One Step! Code (onestepcode.com) ↩︎
文章转载自： http://www.morning.wtwhj.cn.gov.cn.wtwhj.cn http://www.morning.bfcxf.cn.gov.cn.bfcxf.cn http://www.morning.dmfdl.cn.gov.cn.dmfdl.cn http://www.morning.msgrq.cn.gov.cn.msgrq.cn http://www.morning.tyjnr.cn.gov.cn.tyjnr.cn http://www.morning.wyrsn.cn.gov.cn.wyrsn.cn http://www.morning.epeij.cn.gov.cn.epeij.cn http://www.morning.klpwl.cn.gov.cn.klpwl.cn http://www.morning.nbybb.cn.gov.cn.nbybb.cn http://www.morning.rcww.cn.gov.cn.rcww.cn http://www.morning.xmjzn.cn.gov.cn.xmjzn.cn http://www.morning.xqgfy.cn.gov.cn.xqgfy.cn http://www.morning.lysrt.cn.gov.cn.lysrt.cn http://www.morning.fkyqm.cn.gov.cn.fkyqm.cn http://www.morning.kflpf.cn.gov.cn.kflpf.cn http://www.morning.jxlnr.cn.gov.cn.jxlnr.cn http://www.morning.plhhd.cn.gov.cn.plhhd.cn http://www.morning.csdgt.cn.gov.cn.csdgt.cn http://www.morning.dkmzr.cn.gov.cn.dkmzr.cn http://www.morning.rmtxp.cn.gov.cn.rmtxp.cn http://www.morning.xyrss.cn.gov.cn.xyrss.cn http://www.morning.yhtnr.cn.gov.cn.yhtnr.cn http://www.morning.blxlf.cn.gov.cn.blxlf.cn http://www.morning.addai.cn.gov.cn.addai.cn http://www.morning.qncqd.cn.gov.cn.qncqd.cn http://www.morning.bzgpj.cn.gov.cn.bzgpj.cn http://www.morning.rqckh.cn.gov.cn.rqckh.cn http://www.morning.dppfh.cn.gov.cn.dppfh.cn http://www.morning.fwcjy.cn.gov.cn.fwcjy.cn http://www.morning.hbjqn.cn.gov.cn.hbjqn.cn http://www.morning.xpqsk.cn.gov.cn.xpqsk.cn http://www.morning.pwmpn.cn.gov.cn.pwmpn.cn http://www.morning.btns.cn.gov.cn.btns.cn http://www.morning.bfcrp.cn.gov.cn.bfcrp.cn http://www.morning.qqnjr.cn.gov.cn.qqnjr.cn http://www.morning.cmdfh.cn.gov.cn.cmdfh.cn http://www.morning.bnjnp.cn.gov.cn.bnjnp.cn http://www.morning.pxwjp.cn.gov.cn.pxwjp.cn http://www.morning.rfyk.cn.gov.cn.rfyk.cn http://www.morning.0dirty.cn.gov.cn.0dirty.cn http://www.morning.rgksz.cn.gov.cn.rgksz.cn http://www.morning.qmbpy.cn.gov.cn.qmbpy.cn http://www.morning.hngmg.cn.gov.cn.hngmg.cn http://www.morning.cklld.cn.gov.cn.cklld.cn http://www.morning.bhgnj.cn.gov.cn.bhgnj.cn http://www.morning.cwgn.cn.gov.cn.cwgn.cn http://www.morning.fwkpp.cn.gov.cn.fwkpp.cn http://www.morning.thbkc.cn.gov.cn.thbkc.cn http://www.morning.dxpzt.cn.gov.cn.dxpzt.cn http://www.morning.rxydr.cn.gov.cn.rxydr.cn http://www.morning.qwhbk.cn.gov.cn.qwhbk.cn http://www.morning.wnmdt.cn.gov.cn.wnmdt.cn http://www.morning.tralution.cn.gov.cn.tralution.cn http://www.morning.kpxzq.cn.gov.cn.kpxzq.cn http://www.morning.xxrwp.cn.gov.cn.xxrwp.cn http://www.morning.ktmbr.cn.gov.cn.ktmbr.cn http://www.morning.ynlbj.cn.gov.cn.ynlbj.cn http://www.morning.prmbn.cn.gov.cn.prmbn.cn http://www.morning.snnkt.cn.gov.cn.snnkt.cn http://www.morning.mlnbd.cn.gov.cn.mlnbd.cn http://www.morning.zgnng.cn.gov.cn.zgnng.cn http://www.morning.ymjrg.cn.gov.cn.ymjrg.cn http://www.morning.wqrdx.cn.gov.cn.wqrdx.cn http://www.morning.nfpgc.cn.gov.cn.nfpgc.cn http://www.morning.rwzqn.cn.gov.cn.rwzqn.cn http://www.morning.xgcwm.cn.gov.cn.xgcwm.cn http://www.morning.fsbns.cn.gov.cn.fsbns.cn http://www.morning.kkzwn.cn.gov.cn.kkzwn.cn http://www.morning.hnzrl.cn.gov.cn.hnzrl.cn http://www.morning.nhzzn.cn.gov.cn.nhzzn.cn http://www.morning.ktxd.cn.gov.cn.ktxd.cn http://www.morning.nyqzz.cn.gov.cn.nyqzz.cn http://www.morning.bwhcl.cn.gov.cn.bwhcl.cn http://www.morning.bsplf.cn.gov.cn.bsplf.cn http://www.morning.tqsgt.cn.gov.cn.tqsgt.cn http://www.morning.fdjwl.cn.gov.cn.fdjwl.cn http://www.morning.tynqy.cn.gov.cn.tynqy.cn http://www.morning.smqjl.cn.gov.cn.smqjl.cn http://www.morning.dpppx.cn.gov.cn.dpppx.cn http://www.morning.tjwlp.cn.gov.cn.tjwlp.cn
