[TOC]
leetcode 代码成长记录
学习数据结构与算法的代码示例，目前提供 Java语言支持。编程是一门实践的手艺，多多练习，多多思考，把这里列举的所有算法，数据结构，以及对应的常见 leetcode 习题都自己手敲几遍，增强自己的编码基本功，写出高性能和高质量的代码！
文章介绍看这里 十大经典排序算法
| 序号 | 排序名称 | 代码实现 |
|---|---|---|
| 1 | 冒泡排序 | java |
| 2 | 插入排序 | java |
| 3 | 希尔排序 | java |
| 4 | 选择排序 | java |
| 5 | 快速排序 | java |
| 6 | 归并排序 | java |
| 7 | 计数排序 | java |
| 8 | 基数排序 | java |
| 9 | 桶排序 | java |
| 10 | 堆排序 | java |
二叉树解题的思维模式分两类：
-
**是否可以通过遍历一遍二叉树得到答案？**如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
-
**是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？**如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
| 序号 | 题目 | 解题代码 | 题目难度 | 备注 |
|---|---|---|---|---|
| 1 | 144. 二叉树的前序遍历 | Java，Go | 简单 | |
| 2 | 94. 二叉树的中序遍历 | Java，Go | 简单 | |
| 3 | 145. 二叉树的后序遍历 | Java，Go | 简单 | |
| 4 | 104. 二叉树的最大深度 | Java，Go | 简单 | |
| 5 | 543. 二叉树的直径 | Java，Go | 简单 | |
| 6 | 102. 二叉树的层序遍历 | Java，Go | 简单 | |
| 7 | 226. 翻转二叉树 | Java，Go | 简单 | |
| 8 | 116. 填充每个节点的下一个右侧节点指针 | Java，Go | 简单 | |
| 9 | 114. 二叉树展开为链表 | Java，Go | 中等 | |
| 10 | 654. 最大二叉树 | Java，Go | ||
| 11 | 105. 从前序与中序遍历序列构造二叉树 | Java，Go | ||
| 12 | 106. 从中序与后序遍历序列构造二叉树 | Java，Go | ||
| 13 | 889. 根据前序和后序遍历构造二叉树 | Java，Go | ||
| 14 | 297. 二叉树的序列化与反序列化 | Java，Go | ||
| 15 | 652. 寻找重复的子树 | Java，Go | ||
| 归并排序详解及应用 | ||||
| 16 | 912. 排序数组 | Java，Go | 中等 | |
| 17 | 315. 计算右侧小于当前元素的个数 | Java，Go | 困难 | |
| 18 | 493. 翻转对 | Java，Go | 困难 | |
| 19 | 327. 区间和的个数 | Java，Go | 困难 | |
| 中序遍历解决升序问题 | ||||
| 20 | 230. 二叉搜索树中第K小的元素 | Java，Go | 中等 | |
| 21 | 538. 把二叉搜索树转换为累加树 | Java，Go | 中等 | |
| Java，Go |
- 常见的leetcode习题：
| 题号 | 题目名称 | 解题代码 | 难度 |
|---|---|---|---|
| 26 | 删除有序数组的重复项 | java | 简单 |
| 122 | 买卖股票的最佳时机 | java | 中等 |
- 常见的leetcode习题：
| 题号 | 题目名称 | 解题代码 | 难度 |
|---|---|---|---|
| 20 | 有效的括号 | java | 简单 |
| 天数 | 第一题 | 第二题 | 第三题 | 第四题 | 备注 |
|---|---|---|---|---|---|
| 第一天-2022-03-29 | 剑指 Offer 03. 数组中重复的数字 | 剑指 Offer 04. 二维数组中的查找 | 剑指 Offer 05. 替换空格 | 剑指 Offer 06. 从尾到头打印链表 | |
| 思路 | 解法1：hashSet遍历数组，有相同的直接返回,将不重复的添加到数组 解法2：先排序，遍历数组，如果前一位等于后一位，说明重复，直接返回 |
二分法 从矩阵 matrix 左下角元素（索引设为 (i, j) ）开始遍历，并与目标值对比： 当 matrix[i] [j] > target 时，执行 i-- ，即消去第 i 行元素； 当 matrix[i][j] < target 时，执行 j++ ，即消去第 j 列元素； 当 matrix[i] [j] = target 时，返回 true ，代表找到目标值。 若行索引或列索引越界，则代表矩阵中无目标值，返回 false 。 |
初始化一个 StringBuilder，记为 res ； 遍历列表 s 中的每个字符 c ： 当 c 为空格时：向 res 后添加字符串 "%20" ； 当 c 不为空格时：向 res 后添加字符 c ；将列表 res 转化为字符串并返回。 | 入栈： 遍历链表，将各节点值 push 入栈。（Python 使用 append() 方法，Java借助 LinkedList 的addLast()方法）。 * 出栈： 将各节点值 pop 出栈，存储于数组并返回。（Python 直接返回 stack 的倒序列表， * Java 新建一个数组，通过 popLast() 方法将各元素存入数组，实现倒序输出）。 | |
| 第二天2022-03-30 | 剑指 Offer 07. 重建二叉树 | 剑指 Offer 09. 用两个栈实现队列 | 剑指 Offer 10- I. 斐波那契数列 | 剑指 Offer 10- II. 青蛙跳台阶问题 | |
| 思路 | 构造二叉树，第一件事一定是找根节点，然后想办法构造左右子树。 前序遍历结果第一个就是根节点的值，然后再根据中序遍历结果确定左右子树的节点。 |  初始化两个链表， 栈 B 元素实现栈 A 元素倒序 ,然后通过B.removeLast()将元素移出去。栈A作为辅助元素 |
1，动态规划 public static int fib(int n) { int a = 0, b = 1, sum; for (int i = 0; i < n; i++) { sum = (a + b) % 1000000007; a = b; b = sum; } return a; }。2，递归 public static int fib2(int n) { n = help(n); return n; } private static int help(int n) { if (n < 2) return n; return (help(n - 1) + help(n - 2)) % 1000000007; } |
1. 动态规划 public static int numWays(int n) { int a = 0, b = 1, sum; for (int i = 0; i < n; i++) { sum = (a + b) % 1000000007; a = b; b = sum; } return a; } |
重建二叉树 |
| 第三天2022-03-31 | 剑指 Offer 11. 旋转数组的最小数字 | 剑指 Offer 12. 矩阵中的路径 | 剑指 Offer 13. 机器人的运动范围 | 剑指 Offer 14- I. 剪绳子 | |
| 思路 | 1，先排序，再返回数组第一个元素 Arrays.sort(numbers); return numbers[0]; 2，二分法 int left = 0, right = numbers.length - 1; while (left < right) { int mid = (left + right) / 2; if (numbers[mid] > numbers[right]) left = mid + 1; else if (numbers[mid] < numbers[right]) right = mid; else right--; } return numbers[left]; |
深度优先遍历 DFS | 深度优先遍历 DFS | if (n == 1 || n == 2) return 1; if (n == 3) return 2; int sum = 1; while (n > 4) { sum *= 3; n -= 3; } return sum * n; | 12，13，14 |
| 第三天2022-04-01 | 剑指 Offer 14- II. 剪绳子 II | 剑指 Offer 15. 二进制中1的个数 | 剑指 Offer 16. 数值的整数次方 | 剑指 Offer 17. 打印从1到最大的n位数 | |
| 思路 | 把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2 三种情况。`if (n == 1 | n == 2) return 1; if (n == 3) return 2; long sum = 1; while (n > 4) { sum *= 3; sum %= 1000000007; n -= 3; } return (int) (sum * n % 1000000007);` | 逻辑与运算：1， int res = 0; while(n != 0) { res += n & 1; n >>>= 1; } return res; **2，**int res = 0; while(n != 0) { res += n & 1; n >>>= 1; // Java 中无符号右移为 ">>>>>>" } return res; | ||
| 第四天2022-04-06 | 剑指 Offer 18. 删除链表的节点 | 剑指 Offer 19. 正则表达式匹配 | 剑指 Offer 20. 表示数值的字符串 | 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 | |
| 思路 | 递归：if (head == null) return null; if (head.val == val) return head.next; head.next = deleteNode(head.next, val); return head; | 困难 | //判定为数字，则标记numFlag if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { numFlag = true; //判定为. 需要没出现过.并且没出现过e } else if (s.charAt(i) == '.' && !dotFlag && !eFlag) { dotFlag = true; //判定为e，需要没出现过e，并且出过数字了 } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) { eFlag = true; numFlag = false;//为了避免123e这种请求，出现e之后就标志为false //判定为+-符号，只能出现在第一位或者紧接e后面 } else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) { //其他情况，都是非法的 | 双指针 left , right 分列数组左右两端，循环执行： 指针 left 从左向右寻找偶数； 指针 right 从右向左寻找奇数； 将 偶数 nums[left]和 奇数 nums[right]交换。 可始终保证： 指针 left 左边都是奇数，指针 right 右边都是偶数 。 | |
| 第四天2022-04-07 | 剑指 Offer 22. 链表中倒数第k个节点 | 剑指 Offer 24. 反转链表 | 剑指 Offer 25. 合并两个排序的链表 | 剑指 Offer 26. 树的子结构 | |
| 思路 | 双指针 | 递归if (head == null || head.next == null) return head; ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; | 1，如果链表l1为null，直接返回l2 2，如果链表l2为null，直接返回l1 3，如果链表l1等于链表l2，返回链表l1 4，如果链表l1的值小于l2，返回l1，否则返回l2 | ||
| 第五天2022-04-08 | 剑指 Offer 27. 二叉树的镜像 | 剑指 Offer 28. 对称的二叉树 | 剑指 Offer 29. 顺时针打印矩阵 | 剑指 Offer 30. 包含min函数的栈 | |
| 思路 | 递归public TreeNode mirrorTree3(TreeNode root) { if (root == null) return null; TreeNode rootLeft = mirrorTree(root.left); TreeNode rootRight = mirrorTree(root.right); root.right = rootLeft; root.left = rootRight; return root; } | 递归。当 L 和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回 true ； 当 L 或 R 中只有一个越过叶节点： 此树不对称，因此返回 false ； 当节点 L 值 != 节点 R 值： 此树不对称，因此返回 false ； | 初始化两个栈。数据栈和辅助栈。辅助栈记录每次有元素进栈后或者出栈后，元素的最小值 | ||
| 第六天2022-04-10 | 剑指 Offer 31. 栈的压入、弹出序列 | 剑指 Offer 32 - I. 从上到下打印二叉树 | 剑指 Offer 32 - II. 从上到下打印二叉树 II | 剑指 Offer 32 - III. 从上到下打印二叉树 III | |
| 思路 | 判断合不合法，用个栈试一试: 把压栈的元素按顺序压入，当栈顶元素和出栈的第一个元素相同，则将该元素弹出 | 队列 | |||
| 剑指 Offer 34. 二叉树中和为某一值的路径 | 剑指 Offer 35. 复杂链表的复制 | 剑指 Offer 36. 二叉搜索树与双向链表 | 剑指 Offer 37. 序列化二叉树 | ||
| 先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。 |
dfs(cur): 递归法中序遍历；终止条件： 当节点 cur 为空，代表越过叶节点，直接返回； 递归左子树，即 dfs(cur.left) ； 构建链表： 当 pre 为空时： 代表正在访问链表头节点，记为 head ； 当 pre 不为空时： 修改双向节点引用，即 pre.right = cur ， cur.left = pre ； 保存 cur ： 更新 pre = cur ，即节点 cur 是后继节点的 pre ； 递归右子树，即 dfs(cur.right) ； |
||||
| 剑指 Offer 38. 字符串的排列 | 剑指 Offer 39. 数组中出现次数超过一半的数字 | 剑指 Offer 40. 最小的k个数 | 剑指 Offer 41. 数据流中的中位数 | ||
| 思路 | 需要的数字出现次数多于一半 那么排序后必定在中间 class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } } | 通俗易懂Arrays.sort(arr); return Arrays.copyOf(arr,k); | 优先队列 / 堆 | ||
| 剑指 Offer 42. 连续子数组的最大和 | 剑指 Offer 43. 1～n 整数中 1 出现的次数 | 剑指 Offer 44. 数字序列中某一位的数字 | |||
| dp | |||||
必须会手写：快排，归并，堆排序。快排的优化方法
掌握布隆过滤器，bit_map（思想和计数排序一样），在海量数据问题中会用到，海量数据问题是大厂面试特别喜欢考察的问题。
海量数据问题：数据量远远大于内存应该如何去进行解决，比如我抖音二面遇到的在内存受限（比如16M）情况下如何求十亿个整数的中位数还有很多海量数据问题例如在2.5亿个整数中找出不重复的整数（内存不足以容纳这2.5亿个整数）问题基本上都是分文件，哈希，排序（归并，快排，堆排），优先级队列，布隆过滤器，bit_map，前缀树中的几种组合。
如何对一个文件进行压缩（哈夫曼编码）
 |
 |
 |
 |