码恋
ALL YOUR SMILES, ALL MY LIFE.
目录
开年王炸，《算法通关之路》
开年王炸，《算法通关之路》
序
距离上一篇文章发布还是去年 8 月份了，已经沉寂了大半年。
这半年主要做了两件事，一是健身减肥，二是算法算法算法。
体重从 23 年初的 84.5 公斤到现在的 69.4 公斤，BMI 在正常范围内了，身上的肥肉也肉眼可见的消失，肌肉线条也清晰可见。随之而来的精神状态也越来越好，算是在身体上最大的收获了。
而在算法方面，
坦白来讲，先前我是比较排斥的。大家可能都有感受，平时的工作中很少用到，可能只有在面试中会用到。
因为内心始终有反向的情绪，认为刷题是一种痛苦的事情，但是如果想保持自己在行业中找工作的竞争力，只能硬着头皮刷。
结果可想而知，属于是刷一道忘一道那种。
在这其中，我经历了三个阶段，也是我解决问题的通式，在这里我分享给大家。
- 第一阶段 （习惯反馈）
迎难而上，那道题忘了就重复做，不管其他，先解出来再说，死记硬背也要记下来。
比如二叉树二各种遍历，写一次忘一次，我就每天都写一遍，甚至形成了肌肉记忆。
在这个过程中，每次忘记后都会痛苦的记忆回现，然后纯粹按照记忆写出来。
-
第二阶段 （思考强化）
在解题的过程中，逐渐开始思考，为何这样写。慢慢理解解题过程，形成自己的知识路径。
-
第三阶段 （兴趣驱动）
从习惯做一件事发生质变，逐渐对这件事产生兴趣。由兴趣驱动，从一开始的负面情绪转换为正反馈。
如上，可以推导出做任何困难事情的解决通式：
习惯反馈 -> 思考强化 -> 兴趣驱动
对一件事情感兴趣了，才能在自身能力范围内讲它做到极致，也就是我们从小接受的最最简单的教育，培养兴趣。但是没人告诉我们如何培养兴趣，今天，你知道了。
我在刷题的过程中，记录了一些比较典型的题解，下面的内容是我在刷题过程中的总结，还有一大部分内容没有完善，但是不影响阅读，后面我会持续更新。
一、数据结构
1. 数组
- 移除元素
给你一个数组nums和一个值val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用O(1)额外空间并 原地 修改输入数组 。public int removeElement(int[] nums, int val) { int i = 0, j = nums.length - 1; while (i <= j) { if (nums[i] == val) { while (nums[j] == val && i < j) { j--; } int temp = nums[i]; nums[i] = nums[j]; nums[j--] = temp; } i++; } return j + 1; }
2. 字符串
常见的字符串操作方法
length()返回字符串的长度。charAt(int index)返回字符串中指定索引位置的字符。substring(int beginIndex, int endIndex)返回指定索引范围内的子字符串，[beginIndex, endIndex) , 含前不含后。toCharArray()字符串转字符数组indexOf(String str)返回指定字符串在原字符串中第一次出现的索引位置。lastIndexOf(String str)返回指定字符串在原字符串中最后一次出现的索引位置。contains(CharSequence sequence)检查字符串是否包含指定的字符序列。startsWith(String prefix)检查字符串是否以指定的前缀开始。endsWith(String suffix)检查字符串是否以指定的后缀结束。toLowerCase()将字符串转换为小写形式。toUpperCase()将字符串转换为大写形式。trim()去除字符串两端的空格。split(String regex)使用指定的正则表达式将字符串拆分为字符串数组。replace(CharSequence target, CharSequence replacement)将字符串中指定的字符序列替换为另一个字符序列。isEmpty()检查字符串是否为空。equals(Object obj)比较字符串是否与给定的对象相等。compareTo(String anotherString)按字典顺序比较字符串。StringBuilder和StringBuffer类：可用于高效地构建和修改字符串。
常见的字符（Character）操作方法
isLetter(char ch)检查字符是否是一个字母（A-Z，a-z）。isDigit(char ch)检查字符是否是一个数字（0-9）。isWhitespace(char ch)检查字符是否为空白字符（空格、制表符、换行符等）。isUpperCase(char ch)检查字符是否为大写字母。isLowerCase(char ch)检查字符是否为小写字母。toUpperCase(char ch)将字符转换为大写形式。toLowerCase(char ch)将字符转换为小写形式。isLetterOrDigit(char ch)检查字符是否是一个字母或数字。isWhitespace(int codePoint)检查 Unicode 代码点是否为空白字符。isUpperCase(int codePoint)检查 Unicode 代码点是否为大写字母。isLowerCase(int codePoint)查 Unicode 代码点是否为小写字母。toUpperCase(int codePoint)将 Unicode 代码点转换为大写形式。toLowerCase(int codePoint)将 Unicode 代码点转换为小写形式。digit(char ch, int radix)返回字符在指定进制下的数值。getNumericValue(char ch)返回字符的数值。
典型题
- 最长回文子串
public String longestPalindrome(String s) { if (s.length() < 2) { return s; } int start = 0; int maxLen = 0; for (int i = 0; i < s.length(); i++) { // 以 i 为中心点扩散（aba） int len1 = palindrome(s, i, i); // 以 i，i+1 为中心点扩散 （abba） int len2 = palindrome(s, i, i+1); int len = Math.max(len1, len2); if (len > maxLen) { start = i - (len - 1) / 2; maxLen = len; } } return s.substring(start, start + maxLen); } private int palindrome(String s, int start, int end) { while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) { start--; end++; } return end - start - 1; } - 字符串匹配算法
字符串匹配是指从主串 S 中找出是否存在子串 T 的过程。
(1) BF 算法：暴力穷举
public int bf(String s, String t) {
// 主串下标
int i = 0;
// 子串下标
int j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++;
j++;
} else {
// 回溯，i 变为子串的下一个坐标，j 为 0
i = i - j + 1;
j = 0;
}
}
if (j == t.length()) {
return i - j;
}
return -1;
}
(2) KMP 算法
public int getKMP(String t, String p) {
int index = -1;
int pLength = p.length();
int tLength = t.length();
// 模式串的长度当然要小于等于主串长度
if (pLength <= tLength) {
int[] next = getNext(p);
int k = -1;
for (int i = 0; i < tLength; i++) {
// 当前字符和最长前缀下一个字符不同，则往前回溯
while (k > -1 && t.charAt(i) != p.charAt(k + 1)) {
// 已经比较了位置k+1的字符不同，往前回溯的话应该往k位置，k位置的最长前缀的位置k=next[k]
k = next[k];
}
// System.out.print(t.charAt(i) + " " + p.charAt(k + 1));
if (t.charAt(i) == p.charAt(k + 1)) {
// 这个k+1,其实就是模式串的下一个字符下标
k = k + 1;
// System.out.print(" " + k + "\n");
if (k == pLength - 1) {
index = i - pLength + 1;
break;
}
}
}
}
return index;
}
public int[] getNext(String p) {
int[] next = new int[p.length()];
next[0] = -1;
// 最长前缀的位置
int k = -1;
for (int i = 1; i < p.length(); i++) {
// 当前字符和最长前缀下一个字符不同，则往前回溯
while (k > -1 && p.charAt(i) != p.charAt(k + 1)) {
// 已经比较了位置k+1的字符不同，往前回溯的话应该往k位置，k位置的最长前缀的位置k=next[k]
k = next[k];
}
// 当前字符和当前字符前面字符串的最长前缀的下一个字符相同，则k+1
if (p.charAt(i) == p.charAt(k + 1)) {
k = k + 1;
}
next[i] = k;
}
return next;
}
3. 链表
典型题
-
反转链表
// 循环方式 public ListNode reverseList(ListNode head) { ListNode cur = head; ListNode prev = null; while (null != cur) { ListNode temp = cur.next; cur.next = prev; prev = cur; cur = temp; } return prev; } // 递归 public ListNode reverseList(ListNode head) { return reverse(head, null); } private ListNode reverse(ListNode cur, ListNode prev) { if (null == cur) { return prev; } ListNode temp = cur.next; cur.next = prev; return reverse(temp, cur); } -
检测链表是否有环
public boolean hasCycle(ListNode head) { // 快慢指针 if (null == head || null == head.next) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (null == fast || null == fast.next) { return false; } slow = slow.next; fast = fast.next.next; } return true; } -
找到有环链表开始入环的第一个节点
思路：根据两个指针走过的路径之间的关系，找出慢指针什么时候走到环的入口- 第一种结果，链表无环
慢指针每次走 1 步， 快指针每次走 2 步， 如果链表无环，则快指针会走到链表尾部，返回 null - 第二种结果，链表有环
在快指针走到环中时，等待慢指针也走到环中后，因为快指针走的快，快慢之间的距离每次 -1，所以某个时间肯定会相遇。
设快指针走过的路径为 f , 慢指针走过的路径为 s , 从头结点到入口处的路径为 a （不包含入口节点）,环的长度为 b。
当两个指针相遇时则有：
f = 2s; 快指针走的步数是慢指针的 2 倍
f = s + nb; 快指针走的步数等于慢指针走的步数 + n 个环的长度，这里 n 未知；
上述两式相减得出：
s = nb; f = 2nb; 则 f 走了 2n 个环的长度，s 走了 n 个环的长度。
经过上述推导，我们得出一个重要结论，两指针第一次相遇时，慢指针走了 nb ，即 n 个环的长度。 - 分析：
设慢指针走过的路径为 k ，则有 k = a + nb; 即先走 a 步到环的入口，然后每走一圈就会到达环的入口处。
在两指针第一次相遇时，s 走了 nb， 即绕环走了 n 圈，此时有一个指针只要再走 a 步，两个指针就会在入口处重合。
从哪里到入口节点要 a 的长度呢，答案是链表头部 head。 - 解决方案：设快慢指针，先让快慢指针第一次重合，然后用以指针从 head 开始走，再次重合时 slow 指针即为环的入口。
public ListNode detectCycle(ListNode head) { if (null == head || null == head.next) { return null; } ListNode fast = head; ListNode slow = head; // 找到第一次相遇 while (true) { if (null == fast || null == fast.next) { return null; } fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } // fast 重置到头结点 fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return slow; } - 第一种结果，链表无环
4. 栈
典型题
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
- 解法：遍历字符串，如果是左括号则右括号入栈，右括号则查看栈顶元素是否相等，有则出栈，否则不符合要求。重复上述操作，直到字符串末尾，如果此时栈为空，则符合要求。
public boolean isValid(String s) {
if (null == s || s.length() < 2) {
return false;
}
Deque<Character> stack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '{') {
stack.push('}');
} else if (ch == '[') {
stack.push(']');
} else if (ch == '(') {
stack.push(')');
} else if (stack.isEmpty() || ch != stack.pop()) {
return false;
}
}
return stack.isEmpty();
}
5. 队列
6. 哈希表
哈希表比较简单，常用来对不同元素计数、映射等，一个常用的技巧是为了减少内存占用以及扩容等带来的空间时间消耗，可以将哈希表简化为数组来使用。
[242. 有效的字母异位词](https://leetcode.cn/problems/valid-anagram/)
给定两个字符串 `s` 和 `t` ，编写一个函数来判断 `t` 是否是 `s` 的字母异位词。
注意：若 `s` 和 `t` 中每个字符出现的次数都相同，则称 `s` 和 `t` 互为字母异位词。
public boolean isAnagram(String s, String t) {
if (null == s && null == t) {
return true;
}
if (null == s || null == t) {
return false;
}
if (s.length() != t.length()) {
return false;
}
int[] hash = new int[26];
char[] sArray = s.toCharArray();
char[] tArray = t.toCharArray();
for (int i = 0; i < s.length(); i++) {
hash[sArray[i] - 'a']++;
hash[tArray[i] - 'a']--;
}
for (int item : hash) {
if (item != 0) {
return false;
}
}
return true;
}
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> map = new HashMap<>(); // 统计前两个数组的和，以及对应的数量 for (int i : nums1) { for (int j : nums2) { int sum = i + j; map.put(sum, map.getOrDefault(sum, 0) + 1); } } // 结果计数 int res = 0; // 统计另外两个数组的和 for (int i : nums3) { for (int j : nums4) { int sum = i + j; // 有与之对应的相加为 0 的则计数 res += map.getOrDefault(-sum, 0); } } return res; }
7. 树
（1）二叉树
-
满二叉树、完全二叉树（可用数组存储）
满二叉树，除最下边一层没有子节点外，其他节点都有左右两个子节点。(节点数 2^h-1)int leftDept = 0, rightDept = 0; TreeNode left = root.left; TreeNode right = root.right; while (null != left) { left = left.left; leftDept++; } while (null != right) { right = right.right; rightDept++; } if (leftDept == rightDept) { // 若左右高度相同则为满二叉树 return true; }完全二叉树，二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
-
二叉树的遍历
- 前序遍历 (根左右)
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (null == root) { return list; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); list.add(node.val); if (null != node.right) { stack.push(node.right); } if (null != node.left) { stack.push(node.left); } } return list; } - 中序遍历 （左根右）
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (null == root) { return list; } Stack<TreeNode> stack = new Stack<>(); while (null != root || !stack.isEmpty()) { if (null != root) { stack.push(root); root = root.left; } else { TreeNode node = stack.pop(); list.add(node.val); root = node.right; } } return list; } - 后序遍历 （左右根）
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (null == root) { return list; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); list.add(node.val); if (null != node.left) { stack.push(node.left); } if (null != node.right) { stack.push(node.right); } } Collections.reverse(list); return list; } - 层序遍历
public List<List<Integer>> levelTraversal(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (null == root) { return result; } Queue<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> list = new ArrayList<>(); while (size-- > 0) { TreeNode node = queue.poll(); list.add(node.val); if (null != node.left) { queue.offer(node.left); } if (null != node.right) { queue.offer(node.right); } } result.add(list); } return result; }
- 前序遍历 (根左右)
- 二叉树的最大深度
public int maxDepth(TreeNode root) { if (null == root) { return 0; } int deepLeft = maxDepth(root.left); int deepRight = maxDepth(root.right); return Math.max(deepLeft, deepRight) + 1; } - 翻转二叉树
基本思路是左右子树互换。public TreeNode invertTree(TreeNode root) { if (null == root) { return root; } reverse(root, root.left, root.right); return root; } private void reverse(TreeNode parent, TreeNode left, TreeNode right) { parent.left = right; parent.right = left; if (null != left) { reverse(left, left.left, left.right); } if (null != right) { reverse(right, right.left, right.right); } }
（2）二叉搜索树
-
也叫二叉查找树，左子节点小于父节点，右子节点大于父节点
-
中序遍历有序
98. 验证二叉搜索树
给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。public boolean isValidBST(TreeNode root) { return doIsValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean doIsValidBST(TreeNode node, int min, int max) { if (null == node) { return true; } if (node.val <= min || node.val >= max) { return false; } return doIsValidBST(node.left, min, node.val) && doIsValidBST(node.right, node.val, max); }给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。其中自己也可以是自己的祖先。思路：
-
一个比较容易想到的方法是，遍历二叉搜索树，找出从根节点到两个目标节点的路径。倒序比较同时出现的节点即为所求。
- 回溯方法，从一个节点中寻找 p , q，如果找到则返回。即在左右子树中分别寻找 p, q，如果找到则一定是最近的公共祖先。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (null != root) {
// 如果 p,q 都小于父节点，则它们在左子树中
if (p.val < root.val && q.val < root.val) {
root = root.left;
// 如果 p,q 都大于父节点，则它们在右子树中
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
// 一左一右，当前即为所求
return root;
}
}
return null;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (null == root || p == root || q == root) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return null == left ? right : null == right ? left : root;
}
给定一个二叉搜索树的根节点 root 和一个值 key ，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
public TreeNode deleteNode(TreeNode root, int key) {
if (null == root) {
return root;
}
if (root.val == key) {
// 1. 待删节点的左右子树都为空，直接删除，返回空
// 2. 左节点为空时，则上一层直接连接右子节点
if (null == root.left) {
return root.right;
// 3. 右节点为空时，则上一层直接连接左子节点
} else if (null == root.right) {
return root.left;
} else {
// 4. 左右子节点都不为空时，将待删除的节点的左子树放到他的右子节点的最左边节点的左子树下
// 先找到右子树最左边的节点
TreeNode node = root.right;
while (null != node.left) {
node = node.left;
}
// 右子树最左节点的左节点连接待删节点的左子树
node.left = root.left;
// 返回被删节点的右子节点
return root.right;
}
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
}
if (key > root.val) {
root.right = deleteNode(root.right, key);
}
return root;
}
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
思路：
如果 root 在区间 [low, high] 中，则最终返回的根节点不变；否则就需要调整返回的节点。
1. 先移动 root 到目标区间。
2. 左右子树剪枝。
public TreeNode trimBST(TreeNode root, int low, int high) {
if (null == root) {
return null;
}
// 首先让 root 移动到区间 [low, high]
while (null != root && (root.val > high || root.val < low)) {
if (root.val > high) {
root = root.left;
} else {
root = root.right;
}
}
TreeNode cur = root;
// 左边剪枝
while (null != cur && null != cur.left) {
if (cur.left.val < low) {
cur.left = cur.left.right;
} else {
cur = cur.left;
}
}
cur = root;
// 右边剪枝
while (null != cur && null != cur.right) {
if (cur.right.val > high) {
cur.right = cur.right.left;
} else {
cur = cur.right;
}
}
return root;
}
（3） B 树
（4）B+ 树
8. 图
9. 堆 （PriorityQueue: 大顶堆，小顶堆）
典型题
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
思路：维护一个 size 为 k 的小顶堆，堆顶则为目标值。
class KthLargest {
private PriorityQueue<Integer> heap;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
this.heap = new PriorityQueue<>();
for (int num : nums) {
add(num);
}
}
public int add(int val) {
if (heap.size() < k) {
heap.offer(val);
} else if (val > heap.peek()) {
heap.poll();
heap.offer(val);
}
return heap.peek();
}
}
10. 跳表
- 简单理解：就是给链表增加多级索引，提高查找效率。
- 时间复杂度：查找一个元素的时间复杂度是 O(logn)。
- 动态更新索引：当不停地向跳表中插入元素时，如果不同时更新索引，就会导致部分索引中含有许多数据，导致查询性能的退化。所以，在插入元素时，通过随机函数的方式，同时将元素插入到索引中，以维持跳表的性能。
- 实现过程
- 节点存储结构
Node.class ， 可以看做是一个多层链表，数组下标即为对应层数。 - 查找
从顶层开始向下查找，每层小于目标节点的指针后移，找到每层的索引节点，直到第一层，再判断第一层节点值是否是目标值。 - 插入
随机层数，可按照最大层数每层随机是否加 1 产生，如果随机出的层数大于当前层数，则每次只增加 1 层。
找到每层的前一个节点，并在小于最大层数时更新索引层。
然后每层插入数据。 - 删除
找到每层的前一个节点，然后分别删除。
- 节点存储结构
- 代码实现
public class SkipList { /** 最大层数 */ private static final int MAX_LEVEL = 16; /** 当前跳表的层数 */ private int levelCount = 1; private ThreadLocalRandom random = ThreadLocalRandom.current(); /** 存储链表的头结点 */ private Node head = new Node(MAX_LEVEL); /** * 查找对应值的节点 * * @param value * @return */ public Node find(int value) { Node p = head; // 从最高层往下面查找 for (int i = levelCount - 1; i >= 0; i--) { while (null != p.forwords[i] && p.forwords[i].value < value) { p = p.forwords[i]; } } if (null != p.forwords[0] && p.forwords[0].value == value) { return p.forwords[0]; } else { return null; } } /** * 插入数据 * * @param value */ public void insert(int value) { // 随机层数 int level = null == head.forwords[0] ? 1 : randomLevel(); // 每次只增加 1 层 if (level > levelCount) { level = ++levelCount; } Node newNode = new Node(level); newNode.value = value; // 存储每层的前一个节点 Node[] perNodes = new Node[level]; for (int i = 0; i < level; i++) { perNodes[i] = head; } Node p = head; // 查找每层要插入数据的前一个节点 for (int i = levelCount - 1; i >= 0; i--) { while (null != p.forwords[i] && p.forwords[i].value < value) { p = p.forwords[i]; } // 新增的索引层 if (level > i) { perNodes[i] = p; } } // 插入数据 for (int i = 0; i < level; i++) { newNode.forwords[i] = perNodes[i].forwords[i]; perNodes[i].forwords[i] = newNode; } } /** * 删除 * * @param value */ public void delete(int value) { Node p = head; // 找到每层的前一个节点 Node[] perNodes = new Node[levelCount]; for (int i = levelCount - 1; i >= 0; i--) { while (null != p.forwords[i] && p.forwords[i].value < value) { p = p.forwords[i]; } perNodes[i] = p; } // 删除每层中值为 value 的节点 if (null != p.forwords[0] && p.forwords[0].value == value) { for (int i = levelCount - 1; i >= 0; i--) { if (null != perNodes[i].forwords[i] && perNodes[i].forwords[i].value == value) { perNodes[i].forwords[i] = perNodes[i].forwords[i].forwords[i]; } } } } /** * 随机层数 * * @return */ private int randomLevel() { int level = 1; for (int i = 1; i < MAX_LEVEL; i++) { if (random.nextInt() % 2 == 1) { level++; } } return level; } /** 存储跳表节点的数据结构 */ public static class Node { /** 存储节点数据 */ private int value; /** 存储下一个节点所有层的数据 */ private Node[] forwords; public Node(int maxLevel) { this.forwords = new Node[maxLevel]; } @Override public String toString() { return "Node{" + "value=" + value + ", forwords=" + Arrays.toString(forwords) + '}'; } } - Redis Zset 实现
二、算法
1. 排序
(1) 排序算法
冒泡排序 O(n^2)
public void bubbleSort(int[] nums) {
if (null == nums || nums.length <= 1) {
return;
}
for (int i = 0; i < nums.length; i++) {
// 标志当前轮次是否有元素交换
boolean flag = false;
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
// 有元素交换
flag = true;
}
}
// 没有元素交换，说明已经排好序
if (!flag) {
break;
}
}
}
插入排序 O(n^2)
- 过程
循环数组，倒序搜索插入位置，比当前元素大的都往后移动，最后将当前元素插入到指定位置。
public void insertionSort(int[] nums) {
if (null == nums || nums.length <= 1) {
return;
}
for (int i = 0; i < nums.length; i++) {
int value = nums[i];
int j = i - 1;
// 寻找插入位置
for (; j >= 0; j--) {
// 比当前数字大的往后移动
if (nums[j] > value) {
nums[j+1] = nums[j];
} else {
break;
}
}
// 插入数据
nums[j + 1] = value;
}
}
快速排序 O(nlogn)
- 过程
分区函数：一般以区间最后一个元素为分区点，小于分区点的放前边，大于分区点的放后边，然后返回分区点的坐标；根据分区点将区间一分为二做递归，注意不包含分区点。 - 分区函数
最简单的是定义两个临时数组，比分区点大的扔一个数组，另一个放比分区点小的，然后再拷贝回原数组，返回分区点坐标。但是这样的话就不是原地排序了，两个临时数组也浪费空间。
=原地排序的巧妙实现，定义分区点 pivot，循环区间数组，小于 pivot ==的就和前一个元素交换。最后定义的分区点与找到的实际分区点互换，就完成了==分区操作。=
public void quickSort(int[] nums) {
if (null == nums || nums.length <= 1) {
return;
}
doQuickSort(nums, 0, nums.length - 1);
}
private void doQuickSort(int[] nums, int p, int r) {
if (p >= r) {
return;
}
// 分区
int q = partition(nums, p, r);
// 递归
doQuickSort(nums, p, q - 1);
doQuickSort(nums, q + 1, r);
}
private int partition(int[] nums, int p, int r) {
int i = p;
// 以最后一个元素为分区点
int pivot = nums[r];
for (int j = p; j < r; j++) {
// 小于的分区点的就与 i 互换
if (nums[j] < pivot) {
if (i == j) {
i++;
} else {
int temp = nums[j];
nums[j] = nums[i];
nums[i++] = temp;
}
}
}
// 最后分区点 pivot 与找到的分区点互换
int temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
return i;
}
归并排序 O(nlogn)
- 过程
分治，将区间一分为二；递归两个区间；然后排序合并：申请区间大小的临时数组，循环两个区间，较小的数组加入临时数组。然后剩余元素加入临时数组，最后临时数组拷贝至元素对应区间。
public void mergeSort(int[] nums) {
if (null == nums || nums.length <= 1) {
return;
}
doMergeSort(nums, 0, nums.length - 1);
}
private void doMergeSort(int[] nums, int p, int r) {
if (p >= r) {
return;
}
// 分治
int q = p + (r - p >> 1);
// 递归
doMergeSort(nums, p, q);
doMergeSort(nums, q + 1, r);
// 排序合并
merge(nums, p, q, r);
}
private void merge(int[] nums, int p, int q, int r) {
// 先申请 r-p 的临时数组
int[] temps = new int[r - p + 1];
int i = p;
int j = q + 1;
int k = 0;
// 较小的加入临时数组
while (i <= q && j <= r) {
if (nums[i] < nums[j]) {
temps[k++] = nums[i++];
} else {
temps[k++] = nums[j++];
}
}
// 剩余元素加入
int begin = i, end = q;
if (j <= r) {
begin = j;
end = r;
}
while (begin <= end) {
temps[k++] = nums[begin++];
}
// 拷贝至原数组
for (int a = 0; a <= r - p; a++) {
nums[p + a] = temps[a];
}
}
(2) 线性排序 （不对元素之间进行比较）
桶排序 O(n)
-
典型问题
有 10 GB 订单数据，需要按照金额的大小排序。
方法：先扫描一遍数据，找到订单金额的最大最小值。比如最小值为 1 元， 最大值为 10 W 元，将订单数据按照金额放到 100 个桶中分别存储，如果数据分布比较均匀的话，每个桶内分别做快排，然后再按照桶的顺序输出，就完成了排序。如果数据分布不均匀，就再继续划分桶，直到内存够用可以做一个桶的排序。
计数排序 O(n)
-
步骤
- 求范围
遍历求得最大值 max，申请 max + 1 大小的数组 c 存储每个数的数量 - 计数
遍历存储每个数字的数量到数组 c - 累加
=数组 c 累加，得到每个数字前边有多少个数= - 存储位置
申请原数组同样大小的数组 temp，从后往前遍历原数组，当前数字应该存储到 temp 的下标 index = c[i] - 1， =其中 c[i] 代表前边有多少个数，减 1 就是下标= 。然后将数据存储 temp， 同时 c[i]-- ，即数量减 1
- 求范围
-
答疑
为什么计数时，要从后往前遍历数组呢？
答：排序算法关注效率 / 稳定 / 原地，从后往前遍历是基于数据稳定的思想。在获得数据要存储的下标 index 时，index = c[i] - 1，意思是同样的数据最后一个位置，所以从后往前遍历的数组时，最后的元素还是放在后面。 -
典型问题
50 w 高考考生分数排名问题。
假设分数为整数，则按照分数从 0 - 900 划分为 901 个桶，循环所有考生分数数据，按照分数放入不同的桶内，即完成排名。如果分数有小数，可以转换为整数的形式，比如乘以 10 倍，则划分为 9010 个桶。 -
代码
public static void countingSort(int[] nums, int n) { if(n <= 1) { return; } // 查找数组的范围 int max = nums[0]; for(int i = 1; i < n; i++) { if(nums[i] > max) { max = nums[i]; } } // 申请 [0,max] 大小的数组 int[] c = new int[max + 1]; // 统计各元素个数，加入数组 c for(int i = 0; i < n; i++) { c[nums[i]]++; } // 累加 for(int i = 1; i < max; i++) { c[i] = c[i - 1] + c[i]; } // 临时数组 r ， 存储排序后的结果 int[] r = new int[n]; // 计算排序 for(int i = n - 1; i >=0; i--) { // c[nums[1]] 是当前元素前边有多少个数，-1 就是在新数组中的下标 int index = c[nums[i]] - 1; // 赋值 r[index] = nums[i]; // 取出一个后，当前数组的数量应该 -1 c[nums[i]] --; } // 拷贝至原数组 for(int i = 0; i < n; i++) { nums[i] = r[i]; } }
基数排序 O(n)
-
典型问题
如何给 10 w 个手机号排序？
手机号码是 11 位的，假设我们从第一位开始比较的话，如果一个号码第一位大于另一个号码的第一位，那后面就不用比较了。所以我们可以按位做比较，而每一位的范围是 0- 9 ，可以使用计数排序 （O(n)），这样最多排序 11 次，时间复杂度是 O(11*n) ，即可以做到 O(n) 的时间复杂度。
(3) Arrays.sort()
在 JDK 8 中，Arrays.sort() 重载了很多方法，按照不同排序实现可以分为基本类型排序和对象类型排序。
-
基本类型排序
使用DualPivotQuicksort.sort()双轴快排实现。- 选择两个轴点（一般选择数组的首尾元素）。
- 将数组划分为三个部分：小于第一个轴点、介于两个轴点之间、大于第二个轴点。
- 对小于第一个轴点和大于第二个轴点的两个部分递归地应用双轴快速排序算法。
- 对介于两个轴点之间的部分进行排序。
- 重复以上步骤，直到整个数组有序。
实际上，JDK 为了追求性能，针对不同数据做了很多优化。在
DualPivotQuicksort类的伊始，就可以看到定义的几个常量。在元素数量小于 47 的时候使用插入排序，大于 47 小于 286 时使用双轴快排，大于 286 用 Timsort 归并排序，并且会在 Timsort 中记录数据的连续有序段的位置，如果有序段的数量太多，即数据近乎乱序，则使用用双轴快排，当然快排的递归调用的过程中，若排序的子数组数量小于 47，则使用插入排序。
双轴快速排序算法的优势在于，它能够更好地处理含有大量重复元素的数组，从而提高排序效率。与传统的快速排序相比，双轴快速排序减少了递归的深度，减少了比较和交换的次数，因此在某些情况下能够更快地完成排序。 -
对象类型排序
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); }从代码可以看出：对于对象类型的排序是根据设置的是否使用遗留的归并排序算法进行排序。如果条件为true，则使用遗留的归并排序算法；如果条件为false，则使用改进的Timsort 算法，用于排序实现了 Comparable 接口的对象数组。
-
TimSort
Timsort是一种著名的排序算法，结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的特性。它是由Tim Peters在2002年设计并实现的，后来被Python和Java等编程语言采用。
Timsort算法的主要逻辑如下：- 首先，将待排序的数组分割为多个小块，每个小块称为一个Run。Timsort会通过一些启发式方法确定合适的Run大小，通常为32到64个元素。
- 对于每个Run，使用插入排序算法对其进行排序。插入排序对于小规模的数组非常高效。
- 将排好序的Runs逐步合并。采用归并排序的思想，将相邻的两个Runs合并为较大的Runs，直到所有的Runs都被合并为一个完整的有序数组。
- 在合并过程中，Timsort会使用一种特殊的合并策略，保证合并后的结果仍然是有序的。这个策略主要是基于最长递增子序列（Longest Increasing Subsequence，LIS）的概念。
- 在合并过程中，Timsort会维护一个辅助栈（minrun stack），用于记录每个Run的起始索引和长度。
- 当合并两个Runs时，Timsort会尽量保持合并后的Run长度在一定的范围内，以保证后续的合并操作效率。
- 如果某个Run的长度不满足要求，Timsort会进行适当的调整，使得长度符合要求。
- 通过这种方式，Timsort可以在合并过程中尽量减少比较和交换的次数。
Timsort算法的特点是在处理大规模、随机性较弱的数组时表现良好。它结合了插入排序和归并排序的优点，利用了数据的局部性和部分有序性，从而在实际应用中取得了很好的效果。
2. 二分查找
-
场景
在有序或部分有序数列中，查找目标元素。根据题意分析左右区间的收缩条件，收缩时左右边界的取值，并根据循环结束的条件是否要增加后置判断。 -
要点
- 终止条件
- 区间边界的更新
- 返回值选择
-
时间复杂度 O(logn)。
-
代码模板
- 左闭右闭区间
public int binarySearch(int[] nums, int target) { int left = 0, right - nums.length - 1; while (left <= right) { int mid = left + (right - left >>1); if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else { return mid; } } return -1; } - 左闭右开区间
public int binarySearch(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left >>1); if (nums[mid] > target) { right = mid; } else if (nums[mid] < target) { left = mid + 1; } else { return mid; } } return -1; }
- 左闭右闭区间
-
典型问题
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left >> 1); // 找到目标值提前返回 if (nums[mid] == target) { return mid; } if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return left; }已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
public int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left >> 1); // 最左端点小于最右端点，则区间有序递增，left 为最小值 if (nums[left] < nums[right]) { return nums[left]; } else if (nums[left] <= nums[mid]) { // 左区间端点小于等于中间值，则最小值在 mid 右边 left = mid + 1; } else { // 左区间端点大于中间值，则最小值在 mid 左边，mid 也可能为结果 right = mid; } } return nums[left]; }给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
public int[] searchRange(int[] nums, int target) { int i = 0, j = nums.length - 1; // 找目标的左边界 int left = binarySearch(nums, i , j, target); if (left >= nums.length || nums[left] != target) { return new int[]{-1, -1}; } // 寻找 target+1 的左边界 int right = binarySearch(nums, i, j, target+1); return new int[]{left, right-1}; } private int binarySearch(int[] nums, int left, int right, int target) { while (left <= right) { int mid = left + ((right - left) >> 1); // 右区间不断收缩，直到小于 target, 则为左边界 if (nums[mid] >= target) { right = mid - 1; } else { left = mid + 1; } } // 最终循环结束后 left + 1 = right, 此时 left 为第一个值 return left; }
3. 搜索
深度优先和广度优先遍历，参考二叉树遍历，图的遍历等。
4. 回溯
4.1 解题模板
public void backTracking(int[] nums, int index) {
// 判断终止条件
if (false) {
// 加入结果集
result.add(path);
return;
}
// 循环, 这里根据题设是否需要开始坐标：同一数据集求组合则需要
for (int i = index; i < nums.length; i++) {
// 按照条件剪枝、去重
path.add(nums[i]);
backTracking(nums, i + 1);
path.removeLast();
}
}
4.2 主要关注
- 终止条件，什么时候将路径加入结果集。
- 循环时的下标控制，同一数据集求组合时循环需要开始下标；如果两个数据集求组合，不相互影响则循环不需要开始下标，求全排列不需要开始下标。
- 循环时伴随的结果集控制条件的变化。
- 不符合条件的剪枝，在 path 计入路径之前判断。
- 去重逻辑，使用 used[i] 判断，当
nums[i - 1] == nums[i]时，如果used[i - 1] == true则同一树枝重复；反之同一层重复。通过理解题意需要的是同层还是同树枝来判断如何去重。
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
private List<List<Integer>> result;
private LinkedList<Integer> path;
public List<List<Integer>> combine(int n, int k) {
result = new ArrayList<>();
path = new LinkedList<>();
backTracking(n, k, 1);
return result;
}
private void backTracking(int n, int k, int start) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
backTracking(n, k, i+1);
path.removeLast();
}
}
4.3 何时用回溯
- 组合问题：N 个数里面按一定规则找出 k 个数的集合
- 排列问题：N 个数按一定规则全排列，有几种排列方式
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个 N 个数的集合里有多少符合条件的子集
- 棋盘问题：N 皇后，解数独等等
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意： 解集不能包含重复的组合。
private List<List<Integer>> result;
private LinkedList<Integer> path;
private int sum;
private boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.result = new ArrayList<>();
this.path = new LinkedList<>();
this.sum = 0;
used = new boolean[candidates.length];
Arrays.fill(used, false);
Arrays.sort(candidates);
combine(candidates, target, 0);
return result;
}
private void combine(int[] candidates, int target, int index) {
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
for (int i = index; i < candidates.length && candidates[i] <= target - sum; i++) {
// 当 candidates[i - 1] == candidates[i] 时，used[i - 1] == true 表示同一树枝重复 ，used[i - 1] == false 表示同一层重复
if (i > 0 && candidates[i - 1] == candidates[i] && !used[i - 1]) {
continue;
}
path.add(candidates[i]);
sum += candidates[i];
used[i] = true;
combine(candidates, target, i + 1);
path.removeLast();
sum -= candidates[i];
used[i] = false;
}
}
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
回溯的模板还是一套，但是要注意与组合不同，去重时当前数字不能重复使用。
private List<List<Integer>> result;
private LinkedList<Integer> path;
private boolean[] used;
public List<List<Integer>> permute(int[] nums) {
this.result = new ArrayList<>();
this.path = new LinkedList<>();
this.used = new boolean[nums.length];
Arrays.fill(used, false);
backTracking(nums, 0);
return result;
}
private void backTracking(int[] nums, int start) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 当前数字不允许重复出现
if (used[i]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backTracking(nums, start + 1);
path.removeLast();
used[i] = false;
}
}
5. 递归
求解递归问题是要注意三点：1. 递归的终止条件；2.递归下一步的值变化；3.递归的不同分支。
DFS （深度优先遍历）常使用递归的方式实现，在遍历过程中排除不符合题意的情况称为 **剪枝** ；
数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的** 括号组合。
示例 1：
输入： n = 3
输出： ["((()))","(()())","(())()","()(())","()()()"]
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
dfs(result, 0, 0, 0, n, "");
return result;
}
private void dfs(List<String> result, int index, int left, int right, int n, String str) {
if (left > n || right > left) {
return;
}
if (index == 2 * n) {
result.add(str);
return;
}
dfs(result, index + 1, left + 1, right, n, str + "(");
dfs(result, index + 1, left, right + 1, n, str + ")");
}
6. 动态规划
-
场景：
-
模式
- 用什么存储结果，一般是 dp 数组
- 状态转移方程，即下一个解与上一个解有什么关系
- 初始化，即初始值
- 确定结果
-
典型问题
7. 位运算
-
运算符：&（与）、|（或）、^(异或，相同为 0，不相同为 1)、~(按位取反)、<<(左移)、>>(右移：正数高位补 0，负数高位补 1)、>>>(无符号右移：高位补 0)
-
常见用法
- n&1 判断最后一位的 0 或 1
-
典型问题
- 汉明重量
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。public int hammingWeight(int n) { int count = 0; for (int i = 0; i < 32; i++) { if (((n >>> i) & 1) == 1) { count++; } } return count; } - 汉明距离
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }
- 汉明重量
-
颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。如输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。public int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { result <<= 1; result |= (n & 1); n >>= 1; } return result; }
8. 单调栈
9. 滑动窗口
- 基本思想 ：滑动窗口的基本思想是维护一个固定大小的窗口，窗口内包含一定范围的元素，然后通过移动窗口的左右边界来寻找满足特定条件的子数组或子字符串。
- 操作过程 ：通常，滑动窗口算法包括以下步骤：
- 初始化窗口的左边界和右边界。
- 根据条件，移动右边界以扩展窗口，或移动左边界以缩小窗口。
- 在每次移动窗口时，更新满足条件的结果（例如，找到最短子数组、最长子字符串、子数组的和等）。
- 重复上述步骤，直到遍历完整个数组或字符串。
- 典型问题
- 最短连续子数组
给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其总和大于等于target的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。public int minSubArrayLen(int target, int[] nums) { int min = Integer.MAX_VALUE; int left = 0, right = 0; int sum = 0; while (right < nums.length) { sum += nums[right]; while (sum >= target) { min = Math.min(min, right - left + 1); sum -= nums[left++]; } right++; } return min == Integer.MAX_VALUE ? 0 : min; }
10. 前缀和
前缀和（Prefix Sum）用于高效计算数组中某个范围内元素的累积和。前缀和技巧通常用于解决需要频繁查询连续子数组和的问题，可以显著降低时间复杂度。
-
基本思想 ：前缀和的基本思想是在遍历数组时，维护一个额外的数组，其中存储了原数组的前缀和。前缀和数组的第 i 个元素表示原数组中前 i 个元素的累积和。这个数组可以通过一次遍历原数组计算得出。
-
计算过程 ：通常，计算前缀和的过程包括以下步骤：
- 初始化前缀和数组，长度为原数组长度加 1。
- 遍历原数组，计算前缀和数组中的每个元素，其中
prefixSum[i] = prefixSum[i-1] + nums[i-1]，其中nums是原数组。 - 前缀和数组的第 0 个元素通常初始化为 0，表示累积和的初始值。
-
典型问题
- 给定一个含有
n个正整数的数组和一个正整数target。
找出该数组中满足其总和大于等于
target的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int[] prefixSum = new int[n + 1]; for (int i = 1; i <= n; i++) { // prefix[0] = 0, 故下标从 1 开始累计 prefixSum[i] = prefixSum[i - 1] + nums[i - 1]; } int minLength = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // 注意：因为 prefix[0] = 0 ，所以二分查找时，左边界从 i+1 开始 int j = binarySearch(prefixSum, i + 1, n, prefixSum[i] + target); if (j != -1) { minLength = Math.min(minLength, j - i); } } return minLength == Integer.MAX_VALUE ? 0 : minLength; } private int binarySearch(int[] prefixSum, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (prefixSum[mid] >= target) { right = mid - 1; } else { left = mid + 1; } } return left <= prefixSum.length - 1 ? left : -1; } - 给定一个含有
11. 贪心
贪心算法是指从局部最优解可以推出全局最优解的一种算法。
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 **摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。 - 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
public int wiggleMaxLength(int[] nums) {
if (null == nums || nums.length == 0) {
return 0;
}
if (nums.length < 2) {
return 1;
}
int preDiff = 0;
int curDiff = 0;
int count = 1;
for (int i = 1; i < nums.length; i++) {
curDiff = nums[i] - nums[i - 1];
// 统计所有正负交错的数量即可
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
count++;
preDiff = curDiff;
}
}
return count;
}
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
public int maxProfit(int[] prices) {
if (null == prices || prices.length < 2) {
return 0;
}
int profit = 0;
for (int i = 1; i < prices.length; i++) {
profit += Math.max(prices[i] - prices[i - 1], 0);
}
return profit;
}
三、特殊算法
1. 摩尔计数法 (求众数)
- 场景：求众数，比如求数组中元素数量多于 1/3 的数。
- 时间复杂度 O(n) ，空间复杂度 O(1)
- 模式：
-
定义候选数字
设要求多于 1/m 数量的数字，则候选数字的数量最多有 m-1 个，首先定义 m-1 个变量。 -
对抗
循环数组，遇到与候选数字相同的则加1，结束循环；如果候选数字数量变为 0 时则替换候选数字为当前数字，数量加 1，结束循环；否则，所有候选数字数量全部减 1。 -
计数筛选
循环数组，统计各候选数字数量，满足数量大于 1/m 的加入结果集。- 典型问题
229. 多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。public List<Integer> majorityElement(int[] nums) { List<Integer> res = new ArrayList<>(); if (null == nums && nums.length == 0) { return res; } // 摩尔投票法： 找出大于 n/m 次的元素，则最多有 m-1 个元素 // 对抗 int num1 = nums[0], num2 = nums[0]; int count1 = 0, count2 = 0; for (int num : nums) { if (num1 == num) { count1++; continue; } if (num2 == num) { count2++; continue; } if (count1 == 0) { num1 = num; count1++; continue; } if (count2 == 0) { num2 = num; count2++; continue; } count1--; count2--; } // 计数 count1 = 0; count2 = 0; for (int num : nums) { if (num == num1) { count1++; } else if (num == num2) { count2++; } } if (count1 > nums.length / 3) { res.add(num1); } if (count2 > nums.length / 3) { res.add(num2); } return res; }
-
2. 旋转数组
3. 短路递归求加法
剑指 Offer 64. 求 1+2+...+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
public int sumNums(int n) {
boolean x = n > 1 && (n += sumNums(n-1)) > 0;
return n;
}
4. 快速幂求 Pow(x, n)
- 模式：快速幂，求 x 的 n 次幂无需 x 乘 n 次。每次 x 平方，最后看 n 的奇偶，奇数时再乘以 x 即可
实现 pow( x , n ) ，即计算 x 的整数 n 次幂函数（即，x^n ）。
public double myPow(double x, int n) {
if (x == 0) {
return 0;
}
if (n == 0) {
return 1.0;
}
// 负数次幂转化为 1/x 的 -n 次幂
long m = n;
if (m < 0) {
x = 1 / x;
m = -m;
}
double res = 1.0;
// 快速幂，求 x 的 n 次幂无需 x 乘 n 次。每次 x 平方，
// 最后看 n 的奇偶，奇数时再乘以 x 即可
while (m > 0) {
// 判断奇偶，奇数时多乘一个
if ((m&1) == 1) {
res *= x;
}
// x 的平方
x*= x;
// m / 2 向下取整
m >>= 1;
}
return res;
}
5. 抽屉原理求重复数
- 模式：抽屉原理，设 mid 为在 [1, n] 区间内二分的点下标，统计小于等于 mid 的数量 count，如果 count 严格大于 mid, 则重复数字在 [left, mid] 中，否则在 【mid+1, right】中。
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left >> 1);
int count = 0;
for (int num : nums) {
if (num <= mid) {
count++;
}
}
if (count > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
6. 滑动窗口最大值
给你一个整数数组 `nums`，有一个大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 `k` 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
思考：
求 K 个元素最大值，很容易想到大顶堆，但是时间复杂度是 `O(N*logk)` ，复杂度偏高。
本题中每个元素都要走一遍，在每次的循环中需要求得窗口内最大元素，所以每次只保留窗口中的最大元素即可，同时还要注意窗口移动时左侧元素要剔除出去，考虑使用双端队列，时间复杂度为 `O(N)`。
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
// 存放窗口中最大值的下标
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 删除左侧不在窗口中的元素：超出窗口大小的坐标
if (i >= k && deque.peek() < i - k + 1) {
deque.remove();
}
// 从右边开始，小于 nums[i] 的元素全部删除
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.removeLast();
}
deque.add(i);
if (i - k + 1 >= 0) {
result[i - k + 1] = nums[deque.peek()];
}
}
return result;
}
- 序
- 一、数据结构
- 1. 数组
- 2. 字符串
- 常见的字符串操作方法
- 常见的字符（Character）操作方法
- 典型题
- 3. 链表
- 典型题
- 4. 栈
- 典型题
- 5. 队列
- 6. 哈希表
- 7. 树
- （1）二叉树
- （2）二叉搜索树
- （3） B 树
- （4）B+ 树
- 8. 图
- 9. 堆 （PriorityQueue: 大顶堆，小顶堆）
- 典型题
- 10. 跳表
- 二、算法
- 1. 排序
- (1) 排序算法
- 冒泡排序 O(n^2)
- 插入排序 O(n^2)
- 快速排序 O(nlogn)
- 归并排序 O(nlogn)
- (2) 线性排序 （不对元素之间进行比较）
- 桶排序 O(n)
- 计数排序 O(n)
- 基数排序 O(n)
- (3) Arrays.sort()
- 2. 二分查找
- 3. 搜索
- 4. 回溯
- 4.1 解题模板
- 4.2 主要关注
- 4.3 何时用回溯
- 5. 递归
- 6. 动态规划
- 7. 位运算
- 8. 单调栈
- 9. 滑动窗口
- 10. 前缀和
- 11. 贪心
- 三、特殊算法
- 1. 摩尔计数法 (求众数)
- 2. 旋转数组
- 3. 短路递归求加法
- 4. 快速幂求 Pow(x, n)
- 5. 抽屉原理求重复数
- 6. 滑动窗口最大值