1. 移动窗口
场景：数组中的子数组，子字符串等
核心思想：移动End，如果条件不满足/满足，则不停移动start
模版 LeetCode 209
int start = 0;
int end = 0;
int len = Integer.MAX_VALUE;;
int sum = 0;
while (end < nums.length) {
sum = sum + nums[end];
while (sum >= target) {
len = Math.min(len, end - start + 1);
sum -= nums[start];
start++;
}
end++;
System.out.println("sum="+ sum + ",start=" + start + ",end=" + end);
}
return len == Integer.MAX_VALUE? 0: len;
2. 双指针
场景：有序数组两数之和
核心思想：一头一尾两个指针，如果>目标或<目标，则移动头部/尾部指针，直到相遇
模版：LeetCode 167
int head = 0;
int tail = numbers.length - 1;
while (head < tail) {
if(numbers[head] + numbers[tail] > target) {
tail --;
} else if(numbers[head] + numbers[tail] < target) {
head ++;
} else {
return new int[]{head + 1, tail + 1};
}
}
3.链表反转
核心思想：三个基本变量 current，pre，newCurrent，代表记录的当前节点，记录的上一个节点和将要去的
下一个节点
模版：LeetCode206
ListNode pre = null;
ListNode current = head;
ListNode newCurrent;
while(current != null) {
newCurrent = current.next;
current.next = pre;
pre = current;
current = newCurrent;
}
return pre;
4. 链表快慢指针
场景：判断链表是否有环
核心思想：使用快慢指针
模版：LeetCode141
ListNode fast = head;
ListNode slow = head;
while(fast != null) {
fast = fast.next;
if(fast == null) {//有边界则不是环
return false;
}
fast = fast.next;
if(fast == slow) {
return true;
}
slow = slow.next;
}
return false;
5. 链表中间节点
场景：找出链表的中间节点，要求On和O1
核心思想：使用快慢指针，块指针速度是慢指针两倍，如果快指针到了链表尾端，慢指针必然在链表中间
模版：LeetCode876
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
6. 链表删除重复节点
场景1：删除重复的 LeetCode83
核心思想：
模板：
if (head == null) {
return head;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
场景2：有重复的全部删除 LeetCode82
核心思想：使用虚拟头节点，记录current节点，循环删除相同的
模板：链表已经排序的情况
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {//发现重复
int x = cur.next.val;
while (cur.next != null && cur.next.val == x) {//循环删除
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
7. 链表LRU
核心思想：使用双向链表，使用过的插到链表头部，超出长度则将尾部重用，赋予新节点并插到链表头部，
可以用dummyHead当做第一个虚拟节点，dummyTail当做最后一个虚拟节点，方便链表元素的移动
模板：LeetCode146
private class DoubleListNode {
int key;
int value;
DoubleListNode pre;
DoubleListNode next;
public DoubleListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
int capacity;
DoubleListNode head;
DoubleListNode tail;
DoubleListNode[] hash;
int count;
DoubleListNode dummyHead;//虚拟头
DoubleListNode dummyTail;//虚拟尾
public LRUCache(int capacity) {
this.capacity = capacity;
hash = new DoubleListNode[10001];
dummyHead = new DoubleListNode(-1, 0);
dummyTail = new DoubleListNode(-1, 0);
dummyHead.next = dummyTail;
dummyTail.pre = dummyHead;
}
public int get(int key) {
DoubleListNode node = hash[key];
if(node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DoubleListNode node = hash[key];
if(node == null) {
if(count < capacity) {//不需要清除尾部
count++;
node = new DoubleListNode(key, value);
hash[key] = node;
addToHead(node);
} else {//将尾部变成新的数据
DoubleListNode realTail = dummyTail.pre;
hash[realTail.key] = null;//清除最后一个在hash表中的值
realTail.key = key;
realTail.value = value;
hash[key] = realTail;
moveToHead(realTail);
}
} else {//存在则更新value
node.key = key;
node.value = value;
moveToHead(node);
}
}
private void addToHead(DoubleListNode node) {
DoubleListNode oldRealHead = dummyHead.next;
oldRealHead.pre = node;
node.next = oldRealHead;
node.pre = dummyHead;
dummyHead.next = node;
}
private void moveToHead(DoubleListNode node) {
node.next.pre = node.pre;
node.pre.next = node.next;
addToHead(node);
}
8. 二分查找
场景：有序数组，查找或插入目标数
模版：LeetCode35
int left = 1;
int right = n;
while(true) {
if(left == right) {
return left;
}
int mid = left + (right - left) / 2;
int res = guess(mid);
if(res == 0) {
return mid;
} else if(res == 1) {
left = mid + 1;
} else {
right = mid;
}
}
9. 二叉树遍历
DFS：深度优先
核心思想：递归（需要注意栈溢出）
模板：LeetCode104
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
BFS: 广度优先
模板：利用队列，可以解决栈溢出问题 LeetCode104
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
中序遍历
场景：验证二叉搜索树
模板：LeetCode98
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 访问左子树
if (!isValidBST(root.left)) {
return false;
}
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
if (root.val <= pre) {
return false;
}
pre = root.val;
// 访问右子树
return isValidBST(root.right);
}
10. 回溯
思路：采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案
排列型回溯
模版: LeetCode17
public static List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<String>();
if (digits.length() == 0) {
return combinations;
}
Map<Character, String> phoneMap = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
return combinations;
}
public static void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
if (index == digits.length()) {
combinations.add(combination.toString());
} else {
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {
combination.append(letters.charAt(i));
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.deleteCharAt(index);//回溯, 上一个递归拼好了ae，需要把e删掉，继续用a拼其他的
}
}
}
子集型回溯
思路：枚举法，取1,12,123,13...
模版：LeetCode78
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));//之前的list会被修改，需要copy之前的list到答案
if(i == nums.length){
return;
}
/**
* []
* [1]
* [1, 2]
* [1, 2, 3]
* [1, 3]
* [2]
* [2, 3]
* [3]
*/
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
组合型回溯
思路：
模板：LeetCode22
//暴力法，没有用到左括号顺序一定大于右括号顺序的规则
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
dfs(new char[2 * n], 0, res);
return res;
}
public static void dfs(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if(valid((current)))
result.add(new String(current));
} else {
current[pos] = '(';
dfs(current, pos + 1, result);
current[pos] = ')';
dfs(current, pos + 1, result);
}
}
public static boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
全排列回溯
思路：与普通排列区别：for循环要从0开始
模板：LeetCode46
public static List<List<Integer>> permute(int[] nums) {
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
dfs(nums, len, 0, path, used, res);
return res;
}
public static void dfs(int[] nums, int len, int depth,
List<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (path.size() == len) {
res.add(new ArrayList<>(path));
return;
}
// 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
dfs(nums, len, i + 1, path, used, res);
// 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
used[i] = false;
path.remove(path.size() - 1);
}
}
}
11. 动态规划
把问题变成若干小问题：
f(i) = f(i - 1) + f(i - 2) 注意边界
模板：
int len = nums.length;
if(len == 0) {
return 0;
}
if(len == 1) {
return nums[0];
}
int[] stats = new int[len];
stats[0] = nums[0];//第一个
stats[1] = Math.max(nums[0], nums[1]);//第二个
for (int i = 2; i < len; i++) {
stats[i] = Math.max(stats[i - 1]/**这个点不选**/, stats[i - 2] + nums[i]/**这个点选，i-1就不选)**/);
}
return stats[len - 1];
背包
0-1背包
完全背包
单调栈
思路：找上一个更大元素，在找的过程中填坑
模板：LeetCode:739
public int[] dailyTemperatures(int[] temperatures) {
if(temperatures.length == 0) {
return new int[0];
}
Stack<Struct> stack = new Stack();
int[] res = new int[temperatures.length];
stack.push(new Struct(temperatures[0], 0));
for (int i = 1; i < temperatures.length; i++) {
while (!stack.isEmpty()) {
Struct top = stack.peek();
if(top.value < temperatures[i]) {
res[top.pos] = i - top.pos;
stack.pop();
} else {
break;
}
}
stack.push(new Struct(temperatures[i], i));
}
return res;
}
public class Struct {
public Struct(int value, int pos) {
this.value = value;
this.pos = pos;
}
int value;
int pos;
}
