#### [1\. 两数之和](https://leetcode-cn.com/problems/two-sum/) [数组] [哈希表]
```java
/** 错误的结果 */
static final int[] ERROR_RESULT = new int[]{};
public int[] twoSum(int[] nums, int target) {
int len;
if (nums == null || (len = nums.length) < 2) { // 参数校验
return ERROR_RESULT;
}
Map<Integer, Integer> map = new HashMap<>(len);
for (int i = 0; i < len; ++i) {
int num = nums[i];
Integer value = map.get(target - num);
if (value != null) { // map.containsKey(num) == true
return new int[]{value, i};
} else {
map.put(num, i);
}
}
return ERROR_RESULT; // error
}
```
#### [2\. 两数相加](https://leetcode-cn.com/problems/add-two-numbers/)
```java
public ListNode addTwoNumbers(ListNode L1, ListNode L2) {
ListNode head = null;
ListNode tail = null;
int carry = 0;
int v1;
int v2;
while (L1 != null || L2 != null) { // 遍历两个链表，直到其中两个链表全部遍历完
if (L1 != null) {
v1 = L1.val;
L1 = L1.next; // 访问下一结点
} else {
v1 = 0;
}
if (L2 != null) {
v2 = L2.val;
L2 = L2.next; // 访问下一结点
} else {
v2 = 0;
}
int sum = v1 + v2 + carry;
carry = sum / 10;
if (head == null) { // 开始
tail = new ListNode(sum % 10);
head = tail;
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
}
if (carry > 0) { // 进位
tail.next = new ListNode(carry);
}
return head;
}
```
#### [3\. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
```java
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
Map<Character, Integer> window = new HashMap<>();
int leftIndex = 0;
int result = 0;
for(int i=0;i <s.length();i++) {
char c = s.charAt(i);
Integer oldIndex = window.get(c); //
if (oldIndex != null) { // map.containsKey(c)
leftIndex = Math.max(leftIndex, oldIndex + 1); // 设置窗口范围
}
window.put(c, i); // 例行更新窗口
result = Math.max(result, i - leftIndex + 1); // 与当前窗口长度比较
}
return result;
}
```
#### [7\. 整数反转](https://leetcode-cn.com/problems/reverse-integer/)
```java
public int reverse(int x) {
int result = 0;
int min = Integer.MIN_VALUE / 10;
int max = Integer.MAX_VALUE / 10;
while( x != 0) {
if (result < min || result > max) {
return 0;
}
int digit = x % 10;
x/= 10;
result = result * 10 + digit;
}
return result;
}
```
#### [9\. 回文数](https://leetcode-cn.com/problems/palindrome-number/)
```java
public boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
if (x < 10) {
return true;
}
String str = Integer.toString(x);
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
```
#### [11\. 盛最多水的容器](https://leetcode-cn.com/problems/container-with-most-water/)
```java
public int maxArea(int[] heights) {
int len;
if (heights == null || (len = heights.length) < 2) { // 参数校验
return 0;
}
int left = 0; // 左指针
int right = len - 1; // 右指针
int maxArea = Integer.MIN_VALUE; // 结果：最大面积
while (left < right) {
int minHeight = Math.min(heights[left], heights[right]); // 较小高度
maxArea = Math.max(maxArea, minHeight * (right - left)); // width = right - left
while (heights[left] <= minHeight && left < right) { // 加快搜索速度
++left;
}
while (heights[right] <= minHeight && left < right) { // 加快搜索速度
--right;
}
}
return maxArea;
}
```
#### [12\. 整数转罗马数字](https://leetcode-cn.com/problems/integer-to-roman/)
```java
static Map<Integer, String> map = new LinkedHashMap<>();
static {
map.put(1000, "M");
map.put(900, "CM");
map.put(500, "D");
map.put(400, "CD");
map.put(100, "C");
map.put(90, "XC");
map.put(50, "L");
map.put(40, "XL");
map.put(10, "X");
map.put(9, "IX");
map.put(5, "V");
map.put(4, "IV");
map.put(1, "I");
}
/**
* 整数转罗马数字
* @params num {@code 1 <= num <= 3999}
*/
public String intToRoman(int num) {
if ( num < 1 || num > 3999) {
return "";
}
StringBuilder sb = new StringBuilder();
for (Map.Entry<Integer, String> entry: map.entrySet()) {
int key = entry.getKey();
if (key <= num) {
int count = num / key;
String v = entry.getValue();
for (int i=0; i< count; ++i) {
sb.append(v);
}
num = num % key;
}
if (num <= 0) {
break;
}
}
return sb.toString();
}
```
#### [13\. 罗马数字转整数](https://leetcode-cn.com/problems/roman-to-integer/)
```java
public int romanToInt(String s) {
int n;
if(s == null || (n=s.length()) == 0 ) {
return 0;
}
int result = 0;
int i = 0 ;
while (i < n) {
char c = s.charAt(i);
if (c == 'I') { // I, IV, IX
++i;
if (i < n) { // IV, IX
char nextc = s.charAt(i);
if (nextc == 'V') { // IV
result += 4;
++i;
} else if (nextc == 'X') { // IX
result += 9;
++i;
} else { // I
result += 1;
}
} else { // I
result += 1;
}
} else if (c == 'V') { // V
++i;
result += 5;
} else if (c == 'X') { // X, XL, XC
++i;
if (i < n) { // XL, XC
char nextc = s.charAt(i);
if (nextc == 'L') { // XL
result += 40;
++i;
} else if (nextc == 'C') { // XC
result += 90;
++i;
} else { // X
result += 10;
}
} else { // X
result += 10;
}
} else if (c == 'L') { // L
++i;
result += 50;
} else if (c == 'C') {
++i;
if (i < n) {
char nextc = s.charAt(i);
if (nextc == 'D') { // CD
result += 400;
++i;
} else if (nextc == 'M') { // CM
result += 900;
++i;
} else { // C
result += 100;
}
} else { // C
result += 100;
}
} else if(c == 'D') { // D
++i;
result += 500;
} else if (c == 'M') {
++i;
result += 1000;
} else { // error
return 0;
}
}
return result;
}
```
#### [14\. 最长公共前缀](https://leetcode-cn.com/problems/longest-common-prefix/)
```java
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int size = strs.length;
int firstLen = strs[0].length();
for (int j = 0; j < firstLen; j++) {
for (int i = 1; i < size; i++) {
if (strs[i].length() == j || strs[i].charAt(j) != strs[0].charAt(j)) {
return strs[0].substring(0, j);
}
}
}
return strs[0];
}
```
#### [15\. 三数之和](https://leetcode-cn.com/problems/3sum/)
```java
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length <= 2) {
return Collections.emptyList();
}
int len = nums.length;
int[] arr = Arrays.copyOf(nums, len);
Arrays.sort(arr);
List<List<Integer>> result = new ArrayList<>();
for (int i=0; i < len; ++i) {
int curr = arr[i];
if (curr > 0) {
return result;
}
if (i > 0 && curr == arr[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while(left < right) {
int sum = curr + arr[left] + arr[right];
if (sum == 0) {
result.add(Arrays.asList(curr, arr[left], arr[right]));
while (left < right && arr[left] == arr[left + 1]) { // 去重
++left;
}
while (left < right && arr[right] == arr[right - 1]) { // 去重
--right;
}
++left;
--right;
} else if (sum < 0) {
++left;
} else {
--right;
}
}
}
return result;
}
```
#### [16\. 最接近的三数之和](https://leetcode-cn.com/problems/3sum-closest/)
```java
public int threeSumClosest(int[] nums, int target) {
int len; // 数组长度
if (nums == null || (len = nums.length) < 3) {
return 0;
}
Arrays.sort(nums);
int minDiff = Integer.MAX_VALUE;
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < len; i++) {
int left = i + 1;
int right = len - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < target) {
++left;
} else if (sum > target) {
--right;
} else {
return target;
}
int currDiff = Math.abs(sum - target);
int lastDiff = Math.abs(result - target);
if (currDiff < lastDiff) {
minDiff = currDiff;
result = sum;
}
while(left < right && nums[left] == nums[left + 1]) {
++left;
}
while(left < right && nums[right] == nums[right - 1]) {
--right;
}
}
}
return result;
}
```
#### [18\. 四数之和](https://leetcode-cn.com/problems/4sum/)
```java
public List<List<Integer>> fourSum(int[] nums, int target) {
int len;
if (nums == null || (len = nums.length) < 4) {
return Collections.emptyList();
}
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < len - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // 去重
}
for (int j = i + 1; j < len - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue; // 去重
}
int left = j + 1;
int right = len - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum < target) {
++left;
} else if (sum > target) {
--right;
} else { // sum == target
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
++left;
--right;
// 去重
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
}
}
}
}
return result;
}
```
#### [19\. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
```java
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
ListNode node = new ListNode( -1, head);
ListNode left = head;
ListNode delete = node;
while(n-- > 0) {
left = left.next;
}
while (left != null) {
left = left.next;
delete = delete.next;
}
delete.next = delete.next.next;
return node.next;
}
```
#### [20\. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
```java
public boolean isValid(String s) {
int len;
if (s == null || (len = s.length()) == 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i< len; ++i) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
continue;
}
char key = 0;
if (c==')') {
key = '(';
} else if (c == ']') {
key = '[';
} else if (c == '}') {
key = '{';
}
if (stack.empty() || stack.peek() != key) {
return false;
} else {
stack.pop();
}
}
return stack.empty();
}
```
#### [21\. 合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
```java
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
ListNode pre = new ListNode(-1);
ListNode node = pre;
while (true) {
if (list1 == null) {
node.next = list2;
break;
}
if (list2 == null) {
node.next = list1;
break;
}
if (list1.val <= list2.val) {
ListNode tmp = list1;
list1 = list1.next;
node.next = tmp;
} else {
ListNode tmp = list2;
list2 = list2.next;
node.next = tmp;
}
node = node.next;
}
return pre.next;
}
```
#### [22\. 括号生成](https://leetcode-cn.com/problems/generate-parentheses/)
```java
List<String> ans = new ArrayList<String>();
StringBuilder tmp = new StringBuilder();
public List<String> generateParenthesis(int n) {
if (n <= 0) {
return ans;
}
recursion(0, 0, n, 0);
return ans;
}
public void recursion(int left, int right, int n, int curr){
if (curr == 2 * n) {
ans.add(tmp.toString());
return;
}
if (left < n) {
tmp.append('(');
recursion(left + 1, right, n, curr + 1);
tmp.deleteCharAt(tmp.length() - 1);
}
if (right < left) {
tmp.append(')');
recursion(left, right + 1, n, curr + 1);
tmp.deleteCharAt(tmp.length() - 1);
}
}
```
#### [23\. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/)
```java
public ListNode mergeKLists(ListNode[] lists) {
int len;
if (lists == null || (len = lists.length) == 0) {
return null;
}
return merge(lists, 0, len - 1);
}
public ListNode merge(ListNode[] lists, int left, int right) {
if (left == right) {
return lists[left];
}
int mid = left + (right - left) / 2;
ListNode list1 = merge(lists, left, mid);
ListNode list2 = merge(lists, mid + 1, right);
return mergeTwoList(list1, list2);
}
private ListNode mergeTwoList(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val <= list2.val) {
list1.next = mergeTwoList(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoList(list1, list2.next);
return list2;
}
}
```
#### [24\. 两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
```java
public ListNode swapPairs(ListNode head) {
if (head == null) {
return null;
}
ListNode fake = new ListNode(-1, head);
ListNode curr = fake;
while (curr.next != null && curr.next.next != null) {
ListNode node1 = curr.next;
ListNode node2 = curr.next.next;
curr.next = node2;
node1.next = node2.next;
node2.next = node1;
curr = node1;
}
return fake.next;
}
```
#### [25\. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)
```java
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) {
return head;
}
ListNode fake = new ListNode(-1, head);
ListNode left = fake;
ListNode right = fake;
while (right.next != null) {
for (int i = 0; i < k && right != null; i++) {
right = right.next;
}
if (right == null) { // 长度小于k，则不用翻转
break;
}
// 分割链表
ListNode start = left.next; // 开始结点
ListNode next = right.next; // 暂存
right.next = null; // 分割链表
left.next = reverse(start);
start.next = next; // 链接链表
left = start;
right = left;
}
return fake.next;
}
ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
#### [26\. 删除有序数组中的重复项](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)
```java
public int removeDuplicates(int[] nums) {
int len = 0;
if (nums == null || (len = nums.length) <= 1) {
return len;
}
int repeat = nums[0];
int slow = 1;
int fast = 1;
while (fast < len) {
if (nums[fast] != repeat) { // 不再重复
repeat = nums[fast];
nums[slow++] = nums[fast];
}
fast++;
}
return slow;
}
```
#### [27\. 移除元素](https://leetcode-cn.com/problems/remove-element/)
```java
public int removeElement(int[] nums, int val) {
int len;
if (nums == null || (len = nums.length) == 0) {
return 0;
}
int left = 0;
int right = 0;
while (right < len) {
if (nums[right] != val) {
nums[left++] = nums[right];
}
++right;
}
return len - (right - left); //
}
```
#### [31\. 下一个排列](https://leetcode-cn.com/problems/next-permutation/)
```java
public void nextPermutation(int[] nums) {
int len;
if (nums == null || (len = nums.length) <= 1) {
return;
}
int i = len - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = len - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
```
#### [35\. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/)
```java
public int searchInsert(int[] nums, int target) {
if (nums == null){
return -1;
}
int len = nums.length;
if (len == 0) {
return 0;
}
int low = 0;
int high = len - 1;
while(low <= high) {
int mid = low + (high - low) / 2;
int midValue = nums[mid];
if (target == midValue) {
return mid;
}
if (target < midValue) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
```
#### [46\. 全排列](https://leetcode-cn.com/problems/permutations/)
```java
public List<List<Integer>> permute(int[] nums) {
int len;
if (nums == null || (len = nums.length) == 0) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
backtrace(nums, new ArrayList<>(), new boolean[len], result); // ArrayList 添加元素与移除最后一位，比LinkedList快，且内存占用比LinkedList小
return result;
}
void backtrace(int[] nums, List<Integer> tracker, boolean[] visited, List<List<Integer>> result) {
if (nums.length == tracker.size()) {
result.add(new ArrayList<>(tracker));
return;
}
for (int i = 0; i < nums.length; ++i) {
if (visited[i]) { // 已访问
continue;
}
tracker.add(nums[i]); // 做选择
visited[i] = true; // 标记已访问
backtrace(nums, tracker, visited, result); // 进入下一层
tracker.remove(tracker.size() - 1); // 取消选择
visited[i] = false; // 标记未访问
}
}
```
#### [47\. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/)
```java
public List<List<Integer>> permuteUnique(int[] nums) {
int len;
if (nums == null || (len = nums.length) == 0) {
return Collections.emptyList();
}
Arrays.sort(nums); // 对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」
List<List<Integer>> result = new ArrayList<>();
backtrace(nums, new boolean[len], new ArrayList<>(), result);
return result;
}
void backtrace(int[] nums, boolean[] visited, List<Integer> tracker, List<List<Integer>> result) {
if (tracker.size() == nums.length) {
result.add(new ArrayList<Integer>(tracker));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) { // 已访问
continue;
}
if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { // 重复的数字只被填入一次
continue;
}
tracker.add(nums[i]); // 做选择
visited[i] = true; // 标记已访问
backtrace(nums, visited, tracker, result); // 进入下一层
tracker.remove(tracker.size() - 1); // 取消选择
visited[i] = false; // 标记未访问
}
}
```
#### [53\. 最大子数组和](https://leetcode-cn.com/problems/maximum-subarray/)
```java
public int maxSubArray(int[] nums) {
if (nums == null) {
return Integer.MIN_VALUE;
}
int pre = 0;
int max = Integer.MIN_VALUE;
for (int num : nums) {
pre = Math.max(pre + num, num);
max = Math.max(pre, max);
}
return max;
}
```
#### [60\. 排列序列](https://leetcode-cn.com/problems/permutation-sequence/)
```java
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
// 构造nums
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = i + 1; // sorted
}
List<List<Integer>> result = new ArrayList<>();
backtrace(nums, new boolean[n], new ArrayList<>(), result);
List<Integer> item = result.get(k - 1);
StringBuilder sb = new StringBuilder();
for (Integer i : item) {
sb.append(i);
}
return sb.toString();
}
void backtrace(int[] nums, boolean[] visited, List<Integer> tracker, List<List<Integer>> result) {
if (tracker.size() == nums.length) {
result.add(new ArrayList<>(tracker));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
tracker.add(nums[i]);
visited[i] = true;
backtrace(nums, visited, tracker, result);
tracker.remove(tracker.size() - 1);
visited[i] = false;
}
}
```
#### [61\. 旋转链表](https://leetcode-cn.com/problems/rotate-list/)
```java
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k <= 0) {
return head;
}
int len = 1;
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
len++;
}
int add = len - k % len;
if (add == len) {
return head;
}
curr.next = head; // 连接成环
curr = head;
while (curr != null && --add > 0) {
curr = curr.next;
}
ListNode next = curr.next;
curr.next = null;
return next;
}
```
#### [70\. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)
```java
public int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int n0 = 1;
int n1 = 1;
int n2 = 2;
for (int i = 2; i <= n; ++i) {
n2 = n0 + n1;
n0 = n1;
n1 = n2;
}
return n2;
}
```
#### [72\. 编辑距离](https://leetcode-cn.com/problems/edit-distance/)
```java
public int minDistance(String word1, String word2) {
int len1 = word1 == null ? 0 : word1.length();
int len2 = word2 == null ? 0 : word2.length();
if (len1 * len2 == 0) {
return len1 + len2;
}
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= len2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[len1][len2];
}
```
#### [75\. 颜色分类](https://leetcode-cn.com/problems/sort-colors/)
```java
public void sortColors(int[] nums) {
int len;
if (nums == null || (len =nums.length) == 0) {
return;
}
int[] result = new int[3];
for (int i = 0; i < len; ++i) {
++result[nums[i]];
}
for (int i = 0, k = 0; i < result.length; ++i) {
while (result[i]-- > 0) {
nums[k++] = i;
}
}
}
```
#### [82\. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
```java
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode summy = new ListNode(-1, head);
ListNode cur = summy;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int repeat = cur.next.val;
while (cur.next != null && cur.next.val == repeat) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return summy.next;
}
```
#### [86\. 分隔链表](https://leetcode-cn.com/problems/partition-list/)
```java
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
ListNode left = new ListNode(-1);
ListNode right = new ListNode(-1);
ListNode leftFake = left;
ListNode rightFake = right;
ListNode curr = head;
while (curr != null) {
if (curr.val < x) {
left.next = curr;
left = left.next;
} else {
right.next = curr;
right = right.next;
}
curr = curr.next;
}
right.next = null;
left.next = rightFake.next;
return leftFake.next;
}
```
#### [94\. 二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
```java
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
traverse(root, result);
return result;
}
void traverse(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
traverse(node.left, result);
result.add(node.val);
traverse(node.right, result);
}
```
#### [98\. 验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/)
```java
public boolean isValidBST(TreeNode root) {
return root != null && traverse(root);
}
long pre = Long.MIN_VALUE;
boolean traverse(TreeNode node) {
if (node == null ) {
return true;
}
boolean l = traverse(node.left);
if (node.val <= pre) {
return false;
}
pre = node.val;
boolean r = traverse(node.right);
return l && r;
}
```
#### [100\. 相同的树](https://leetcode-cn.com/problems/same-tree/)
```java
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
return (p != null && q != null)
&& p.val == q.val
&& isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
```
#### [101\. 对称二叉树](https://leetcode-cn.com/problems/symmetric-tree/)
```java
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return false;
}
return traverse(root.left, root.right);
}
boolean traverse(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) {
return true;
}
return (node1 != null && node2 != null)
&& node1.val == node2.val
&& traverse(node1.left, node2.right)
&& traverse(node1.right, node2.left);
}
```
#### [102\. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
```java
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
List<Integer> lineList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
TreeNode last = root; // 当前层最后一个结点
TreeNode nextLast = root; // 下一层的最后一个结点
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll(); // 当前访问的结点
lineList.add(node.val);
TreeNode child = node.left;
if (child != null) {
queue.offer(child);
nextLast = child;
}
child = node.right;
if (child != null) {
queue.offer(child);
nextLast = child;
}
if (node == last) { // 访问到一层的最后一个结点
result.add(new ArrayList<>(lineList));
lineList.clear();
last = nextLast; // 后面由nextLast更新
}
}
return result;
}
```
#### [103\. 二叉树的锯齿形层序遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)
```java
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while(!queue.isEmpty()) {
LinkedList<Integer> list = new LinkedList<>();
int size = queue.size();
for(int i = 0; i< size; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
list.addLast(node.val);
} else {
list.addFirst(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
leftToRight = !leftToRight;
result.add(new ArrayList(list));
}
return result;
}
```
#### [104\. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
```java
int mMaxDepth = 0;
int mDepth = 0;
public int maxDepth(TreeNode root) {
traverse(root);
return mMaxDepth;
}
void traverse(TreeNode node) {
if (node == null) {
mMaxDepth = Math.max(mMaxDepth, mDepth);
return;
}
mDepth++;
traverse(node.left);
traverse(node.right);
mDepth--;
}
```
#### [107\. 二叉树的层序遍历 II](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
```java
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if(root == null) {
return Collections.emptyList();
}
LinkedList<List<Integer>> result = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i=0;i<size;i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.addFirst(list);
}
return result;
}
```
#### [108\. 将有序数组转换为二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/)
```java
public TreeNode sortedArrayToBST(int[] nums) {
int len = 0;
if (nums == null || (len = nums.length) == 0) {
return null;
}
return buildBinSearchTree(nums, 0, len - 1);
}
TreeNode buildBinSearchTree(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = buildBinSearchTree(nums, left, mid - 1);
node.right = buildBinSearchTree(nums, mid + 1, right);
return node;
}
```
#### [109\. 有序链表转换二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/)
```java
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head, null);
}
public TreeNode buildTree(ListNode left, ListNode right) {
if (left == right) {
return null;
}
ListNode mid = getMedian(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(left, mid);
root.right = buildTree(mid.next, right);
return root;
}
public ListNode getMedian(ListNode left, ListNode right) {
ListNode fast = left;
ListNode slow = left;
while (fast != right && fast.next != right) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
```
#### [110\. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/)
```java
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return Math.abs(depth(root.left) - depth(root.right)) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
int depth(TreeNode node) {
if(node == null) {
return 0;
}
return Math.max(depth(node.left), depth(node.right)) + 1;
}
```
#### [111\. 二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/)
```java
/** 二叉树的最小深度 */
int mMinDepth = Integer.MAX_VALUE;;
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
traverse(root, 1);
return mMinDepth;
}
void traverse(TreeNode node, int depth) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
mMinDepth = Math.min(mMinDepth, depth);
return;
}
traverse(node.left, depth + 1);
traverse(node.right, depth + 1);
}
```
#### [112\. 路径总和](https://leetcode-cn.com/problems/path-sum/)
```java
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return root.val == sum;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
```
#### [113\. 路径总和 II](https://leetcode-cn.com/problems/path-sum-ii/)
```java
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(root.val);
dfs(root, targetSum - root.val, path, result);
return result;
}
void dfs(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) {
if (node.left == null && node.right == null && remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
if (node.left != null) {
path.add(node.left.val);
dfs(node.left, remaining - node.left.val, path, result);
path.remove(path.size() - 1);
}
if (node.right != null) {
path.add(node.right.val);
dfs(node.right, remaining - node.right.val, path, result);
path.remove(path.size() - 1);
}
}
```
#### [114\. 二叉树展开为链表](https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/)
```java
public void flatten(TreeNode root) {
if (root == null) {
return;
}
List<TreeNode> nodeList = new ArrayList<>();
traverse(root, nodeList);
for (int i = 1; i< nodeList.size(); ++i) {
root.right = nodeList.get(i);
root.left = null;
root = root.right;
}
}
private void traverse(TreeNode node, List<TreeNode> result) {
if (node == null) {
return;
}
result.add(node);
if (node.left != null) {
traverse(node.left, result);
}
if (node.right != null) {
traverse(node.right, result);
}
}
```
#### [130\. 被围绕的区域](https://leetcode-cn.com/problems/surrounded-regions/)
```java
static final char CHAR_A = 'A';
static final char CHAR_X = 'X';
static final char CHAR_O = 'O';
public void solve(char[][] board) {
int width; // 宽
int height; // 高
if (board == null || (width = board.length) <= 1 || (height = board[0].length) <= 1) {
return;
}
for (int i = 0; i < width; i++) {
dfs(board, i, 0, width, height);
dfs(board, i, height - 1, width, height);
}
for (int j = 0; j < height; j++) {
dfs(board, 0, j, width, height);
dfs(board, width - 1, j, width, height);
}
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (board[i][j] == CHAR_A) {
board[i][j] = CHAR_O;
} else if (board[i][j] == CHAR_O) {
board[i][j] = CHAR_X;
}
}
}
}
void dfs(char[][] board, int i, int j, int width, int height) {
if (i < 0 || i >= width || j < 0 || j >= height || board[i][j] != CHAR_O) {
return;
}
board[i][j] = CHAR_A;
dfs(board, i + 1, j, width, height);
dfs(board, i - 1, j, width, height);
dfs(board, i, j + 1, width, height);
dfs(board, i, j - 1, width, height);
}
```
#### [139\. 单词拆分](https://leetcode-cn.com/problems/word-break/)
```java
/**
* <pre>
* 1 <= s.length <= 300
* 1 <= wordDict.length <= 1000
* 1 <= wordDict[i].length <= 20
* s 和 wordDict[i] 仅有小写英文字母组成
* wordDict 中的所有字符串 互不相同
* </pre>
*/
public boolean wordBreak(String s, List<String> wordDict) {
int sLen;
if (s == null || (sLen = s.length()) < 1 || wordDict == null || wordDict.isEmpty()) {
return false;
}
boolean[] dp = new boolean[sLen + 1];
dp[0] = true;
for (int i = 1; i <= sLen; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && contains(wordDict, s, j, i)) {
dp[i] = true;
break;
}
}
}
return dp[sLen];
}
/**
* wordDict.contains(s.substring(j, i)) 优化版
*/
boolean contains(List<String> wordDict, String s, int start, int end) {
for (int i = 0; i < wordDict.size(); ++i) {
String word = wordDict.get(i);
int wordLen = word.length();
if ((end - start) != wordLen) {
continue;
}
boolean allEquals = true;
for (int j = start, k = 0; j < end;) {
if (s.charAt(j++) != word.charAt(k++)) {
allEquals = false;
break;
}
}
if (allEquals) {
return true;
}
}
return false;
}
```
#### [141\. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/)
```java
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode left = head;
ListNode right = head.next;
while(left != right && right != null && right.next != null) {
left = left.next;
right = right.next.next;
}
return left == right;
}
```
#### [142\. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
```java
/**
* 环形链表(2)
* @param head 给定一个链表的头结点 head
* @return 返回链表开始入环的第一个结点。如果链表无环，则返回 null
*/
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode left = head;
ListNode right = head;
while (true) {
if (right == null || right.next == null) {
return null;
}
left = left.next;
right = right.next.next;
if (left == right) {
break;
}
}
right = head;
while(left != right) {
left = left.next;
right = right.next;
}
return right;
}
```
#### [144\. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
```java
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
traverse(root, result);
return result;
}
void traverse(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
traverse(node.left, result);
traverse(node.right, result);
}
```
#### [145\. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
```java
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
traverse(root, result);
return result;
}
void traverse(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
traverse(node.left, result);
traverse(node.right, result);
result.add(node.val);
}
```
#### [155\. 最小栈](https://leetcode-cn.com/problems/min-stack/)
```java
/**
* 最小栈
*/
class MinStack {
Stack<Integer> realStack = new Stack<>();
Stack<Integer> minStack = new Stack();
/**
* 构造方法
*/
public MinStack() {
}
public void push(int val) {
realStack.push(val);
if (minStack.empty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (realStack.empty()) {
return;
}
int val = realStack.pop();
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return realStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
```
#### [160\. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
```java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // headA 和 headB 不存在环
if (headA == null || headB == null) {
return null;
}
int lenA = getLength(headA);
int lenB = getLength(headB);
if (lenA > lenB) {
int len = lenA - lenB;
while (len-- > 0) {
headA = headA.next;
}
} else if (lenB > lenA) {
int len = lenB - lenA;
while (len-- > 0) {
headB = headB.next;
}
}
while (headA != null && headB != null) {
if (headA == headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
private int getLength(ListNode node) {
int len = 0;
while (node != null) {
node = node.next;
++len;
}
return len;
}
```
#### [169\. 多数元素](https://leetcode-cn.com/problems/majority-element/)
```java
public int majorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int result = nums[0];
int count = 1;
for (int i = 1; i < nums.length; ++i) {
if (count == 0) {
count = 1;
result = nums[i];
} else if (result == nums[i]) {
++count;
} else {
--count;
}
}
return result;
}
```
#### [172\. 阶乘后的零](https://leetcode-cn.com/problems/factorial-trailing-zeroes/)
```java
public int trailingZeroes(int n) {
int result = 0;
while (n != 0) {
n /= 5;
result+=n;
}
return result;
}
```
#### [198\. 打家劫舍](https://leetcode-cn.com/problems/house-robber/)
```java
public int rob(int[] nums) {
int len;
if (nums == null || (len = nums.length) == 0) {
return 0;
}
if (len == 1) {
return nums[0];
} else if (len == 2) {
return Math.max(nums[0], nums[1]);
}
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < len; ++i) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[len - 1];
}
```
#### [206\. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)
```java
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
```
#### [208\. 实现 Trie (前缀树)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/)
```java
private Trie[] children = new Trie[26];
private boolean isEnd = false;
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
int index = c - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
```
#### [213\. 打家劫舍 II](https://leetcode-cn.com/problems/house-robber-ii/)
```java
public int rob(int[] nums) {
int len;
if (nums == null || (len = nums.length) == 0) {
return 0;
} else if (len == 1) {
return nums[0];
} else if (len == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, len - 2) , robRange(nums, 1, len - 1));
}
int robRange(int[] nums, int start, int end) {
int n0 = nums[start];
int n1 = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int tmp = n1;;
n1 = Math.max(n0 + nums[i], n1);
n0 = tmp;
}
return n1;
}
```
#### [217\. 存在重复元素](https://leetcode-cn.com/problems/contains-duplicate/)
```java
public boolean containsDuplicate(int[] nums) {
int len;
if(nums == null || (len = nums.length) == 0) {
return false;
}
Set<Integer> set = new HashSet<>(len);
for(int i = 0;i < len;i++) {
if (!set.add(nums[i])) {
return true;
}
}
return false;
}
```
#### [226\. 翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)
```java
public TreeNode invertTree(TreeNode root) {
traverse(root);
return root;
}
void traverse(TreeNode node) {
if(node == null) {
return;
}
traverse(node.left);
traverse(node.right);
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
```
#### [234\. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
```java
public boolean isPalindrome(ListNode head) {
if (head == null) {
return false;
}
Stack<ListNode> stack = new Stack<>();
ListNode curr = head;
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
curr = head;
while (curr != null) {
if (curr.val != stack.pop().val) {
return false;
}
curr = curr.next;
}
return true;
}
```
#### [235\. 二叉搜索树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
```java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
return traverse(root, p, q);
}
TreeNode traverse(TreeNode root, TreeNode p, TreeNode q) {
if ((root.val - p.val) * (root.val - q.val) <= 0) { // 一个在左，一个在右
return root;
}
// 都在左或都在右
if (p.val < root.val) { // 都在左
return traverse(root.left, p, q);
} else { // 都在右边
return traverse(root.right, p, q);
}
}
```
#### [257\. 二叉树的所有路径](https://leetcode-cn.com/problems/binary-tree-paths/)
```java
public List<String> binaryTreePaths(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
List<String> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(root.val);
dfs(root, path, result);
return result;
}
void dfs(TreeNode node, List<Integer> path, List<String> result) {
if (node.left == null && node.right == null) {
result.add(toString(path));
return;
}
if (node.left != null) {
path.add(node.left.val);
dfs(node.left, path, result);
path.remove(path.size() - 1);
}
if (node.right != null) {
path.add(node.right.val);
dfs(node.right, path, result);
path.remove(path.size() - 1);
}
}
String toString(List<Integer> path) {
StringBuilder sb = new StringBuilder();
String sep = "";
for (Integer val : path) {
sb.append(sep).append(val);
sep = "->";
}
return sb.toString();
}
```
#### [258\. 各位相加](https://leetcode-cn.com/problems/add-digits/)
```java
public int addDigits(int num) {
if (num <= 0) {
return 0;
}
while (num >= 10) {
int sum = 0;
while(num > 0) {
sum += num % 10;
num /= 10;
}
num = sum;
}
return num;
}
```
#### [278\. 第一个错误的版本](https://leetcode-cn.com/problems/first-bad-version/)
```java
public int firstBadVersion(int n) {
if (n <= 0) {
return -1;
}
int result = n;
int low = 1;
int high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isBadVersion(mid)) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return result;
}
```
#### [653\. 两数之和 IV - 输入 BST](https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/)
```java
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
Map<Integer, TreeNode> map = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()) {
TreeNode node = stack.pop();
TreeNode value = map.get(k - node.val);
if (value != null && value != node) {
return true;
} else {
map.put(node.val, node);
}
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
return false;
}
```
- 1 设计接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 栈接口Stack
- 1.4 队列接口Queue
- 1.5 Union-Find算法接口UF
- 2 实现接口
- 2.1 结点类Node
- 2.2 数组迭代器ArrayIterator
- 2.3 链表迭代器ListIterator
- 2.4 背包(Bag)的实现
- 2.4.1 能动态调整数组大小的Bag
- 2.4.2 链式Bag的实现
- 2.5 栈(Stack)的实现
- 2.5.1 能动态调整数组大小的Stack
- 2.5.2 链式Stack的实现
- 2.6 队列(Queue)的实现
- 2.6.1 能动态调整数组大小的Queue
- 2.6.2 链式Queue的实现
- 2.7 Union-Find算法的实现
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 测试
- 2.8.1 测试Stack
- 2.8.2 测试Union-Find
- 3 排序算法
- 3.1 定义排序工具的类结构
- 3.2 选择排序
- 3.3 插入排序
- 3.4 希尔排序
- 3.5 归并排序
- 3.5.1 归并排序的合并方法
- 3.5.2 自顶向下的归并排序
- 3.5.3 自底向上的归并排序
- 3.6 快速排序
- 3.6.1 常规快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改进方法-小数据量转成插入排序
- 3.6.4 快速排序的改进方法-三向切分
- 3.7 堆排序
- 3.8 最终的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 优先队列(MaxPriorityQueue)
- 4.3 二叉查找树(BST)
- 4.4 红黑二叉查找树(RedBlackBST)
- 4.5 B-树(BTree)
- 5 图
- 5.1 无向图(Graph)
- 5.2 有向图(Digraph)
- 6 贪心
- Dijkstra算法-单元最短路径
- 7 动态规划
- 7.1 最长公共子序列问题
- 7.2 0-1背包问题
- 7.3 加工顺序问题
- 8 搜索法
- 8.1 图的着色问题
- 8.2 深度优先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集树
- 8.3.3 排列树
- 8.3.4 满m叉树(组合树)
- 8.4 广度优先搜索
- 8.5 分支限界法
- 9 随机化算法
- 9.1 数值随机化算法
- 9.2 蒙特卡罗算法
- 9.3 拉斯维加斯算法
- 9.4 舍伍德算法
- 10 数论算法
- 10.1 Stein求最大公约数
- 10.2 矩阵求斐波那切数列
- LeetCode刷题笔记