常见算法模板
双指针:
只有一个输入, 从两端开始遍历
java:
public int fn(int[] arr) {
int left = 0;
int right = arr.length - 1;
int ans = 0;
while (left < right) {
// 一些根据 letf 和 right 相关的代码补充
if (CONDITION) {
left++;
} else {
right--;
}
}
return ans;
}
Python
def fn(arr):
left = ans = 0
right = len(arr) - 1
while left < right:
# 一些根据 letf 和 right 相关的代码补充
if CONDITION:
left += 1
else:
right -= 1
return ans
有两个输入, 两个都需要遍历完
java
public int fn(int[] arr1, int[] arr2) {
int i = 0, j = 0, ans = 0;
while (i < arr1.length && j < arr2.length) {
// 根据题意补充代码
if (CONDITION) {
i++;
} else {
j++;
}
}
while (i < arr1.length) {
// 根据题意补充代码
i++;
}
while (j < arr2.length) {
// 根据题意补充代码
j++;
}
return ans;
}
python
def fn(arr1, arr2):
i = j = ans = 0
while i < len(arr1) and j < len(arr2):
# 根据题意补充代码
if CONDITION:
i += 1
else:
j += 1
while i < len(arr1):
# 根据题意补充代码
i += 1
while j < len(arr2):
# 根据题意补充代码
j += 1
return ans
滑动窗口
java
public int fn(int[] arr) {
int left = 0, ans = 0, curr = 0;
for (int right = 0; right < arr.length; right++) {
// 根据题意补充代码来将 arr[right] 添加到 curr
while (WINDOW_CONDITION_BROKEN) {
// 从 curr 中删除 arr[left]
left++;
}
// 更新 ans
}
return ans;
}
python
def fn(arr):
left = ans = curr = 0
for right in range(len(arr)):
# 根据题意补充代码来将 arr[right] 添加到 curr
while WINDOW_CONDITION_BROKEN:
# 从 curr 中删除 arr[left]
left += 1
# 更新 ans
return ans
构建前缀和
java
public int[] fn(int[] arr) {
int[] prefix = new int[arr.length];
prefix[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
return prefix;
}
python
def fn(arr):
prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[-1] + arr[i])
return prefix
高效的字符串构建
java
public String fn(char[] arr) {
StringBuilder sb = new StringBuilder();
for (char c: arr) {
sb.append(c);
}
return sb.toString();
}
python
# arr 是一个字符列表
def fn(arr):
ans = []
for c in arr:
ans.append(c)
return "".join(ans)
链表: 快慢指针
java
public int fn(ListNode head) {
ListNode slow = head;
ListNode fast = head;
int ans = 0;
while (fast != null && fast.next != null) {
// 根据题意补充代码
slow = slow.next;
fast = fast.next.next;
}
return ans;
}
python
def fn(head):
slow = head
fast = head
ans = 0
while fast and fast.next:
# 根据题意补充代码
slow = slow.next
fast = fast.next.next
return ans
反转链表
java
public ListNode fn(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
python
def fn(head):
curr = head
prev = None
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
找到符合确切条件的子数组数
java
public int fn(int[] arr, int k) {
Map<Integer, Integer> counts = new HashMap<>();
counts.put(0, 1);
int ans = 0, curr = 0;
for (int num: arr) {
// 根据题意补充代码来改变 curr
ans += counts.getOrDefault(curr - k, 0);
counts.put(curr, counts.getOrDefault(curr, 0) + 1);
}
return ans;
}
python
from collections import defaultdict
def fn(arr, k):
counts = defaultdict(int)
counts[0] = 1
ans = curr = 0
for num in arr:
# 根据题意补充代码来改变 curr
ans += counts[curr - k]
counts[curr] += 1
return ans
单调递增栈
java
public int fn(int[] arr) {
Stack<Integer> stack = new Stack<>();
int ans = 0;
for (int num: arr) {
// 对于单调递减的情况，只需将 > 翻转到 <
while (!stack.empty() && stack.peek() > num) {
// 根据题意补充代码
stack.pop();
}
stack.push(num);
}
return ans;
}
python
def fn(arr):
stack = []
ans = 0
for num in arr:
# 对于单调递减的情况，只需将 > 翻转到 <
while stack and stack[-1] > num:
# 根据题意补充代码
stack.pop()
stack.append(num)
return ans
二叉树: DFS (递归)
java
public int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int ans = 0;
// 根据题意补充代码
dfs(root.left);
dfs(root.right);
return ans;
}
python
def dfs(root):
if not root:
return
ans = 0
# 根据题意补充代码
dfs(root.left)
dfs(root.right)
return ans
二叉树: DFS (迭代)
java
public int dfs(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
int ans = 0;
while (!stack.empty()) {
TreeNode node = stack.pop();
// 根据题意补充代码
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
return ans;
}
python
def dfs(root):
stack = [root]
ans = 0
while stack:
node = stack.pop()
# 根据题意补充代码
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ans
二叉树: BFS
java
public int fn(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int ans = 0;
while (!queue.isEmpty()) {
int currentLength = queue.size();
// 做一些当前层的操作
for (int i = 0; i < currentLength; i++) {
TreeNode node = queue.remove();
// 根据题意补充代码
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return ans;
}
python
from collections import deque
def fn(root):
queue = deque([root])
ans = 0
while queue:
current_length = len(queue)
# 做一些当前层的操作
for _ in range(current_length):
node = queue.popleft()
# 根据题意补充代码
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return ans
图: DFS (递归)
以下图模板假设节点编号从 0 到 n - 1 ，并且图是以邻接表的形式给出的。根据问题的不同，您可能需要在使用模板之前将输入转换为等效的邻接表。
java
Set<Integer> seen = new HashSet<>();
public int fn(int[][] graph) {
seen.add(START_NODE);
return dfs(START_NODE, graph);
}
public int dfs(int node, int[][] graph) {
int ans = 0;
// 根据题意补充代码
for (int neighbor: graph[node]) {
if (!seen.contains(neighbor)) {
seen.add(neighbor);
ans += dfs(neighbor, graph);
}
}
return ans;
}
python
def fn(graph):
def dfs(node):
ans = 0
# 根据题意补充代码
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
ans += dfs(neighbor)
return ans
seen = {START_NODE}
return dfs(START_NODE)
图: DFS (迭代)
java
public int fn(int[][] graph) {
Stack<Integer> stack = new Stack<>();
Set<Integer> seen = new HashSet<>();
stack.push(START_NODE);
seen.add(START_NODE);
int ans = 0;
while (!stack.empty()) {
int node = stack.pop();
// 根据题意补充代码
for (int neighbor: graph[node]) {
if (!seen.contains(neighbor)) {
seen.add(neighbor);
stack.push(neighbor);
}
}
}
return ans;
}
python
def fn(graph):
stack = [START_NODE]
seen = {START_NODE}
ans = 0
while stack:
node = stack.pop()
# 根据题意补充代码
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
stack.append(neighbor)
return ans
图: BFS
java
public int fn(int[][] graph) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> seen = new HashSet<>();
queue.add(START_NODE);
seen.add(START_NODE);
int ans = 0;
while (!queue.isEmpty()) {
int node = queue.remove();
// 根据题意补充代码
for (int neighbor: graph[node]) {
if (!seen.contains(neighbor)) {
seen.add(neighbor);
queue.add(neighbor);
}
}
}
return ans;
}
python
from collections import deque
def fn(graph):
queue = deque([START_NODE])
seen = {START_NODE}
ans = 0
while queue:
node = queue.popleft()
# 根据题意补充代码
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
return ans
找到堆的前 k 个元素
java
public int[] fn(int[] arr, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(CRITERIA);
for (int num: arr) {
heap.add(num);
if (heap.size() > k) {
heap.remove();
}
}
int[] ans = new int[k];
for (int i = 0; i < k; i++) {
ans[i] = heap.remove();
}
return ans;
}
python
import heapq
def fn(arr, k):
heap = []
for num in arr:
# 做根据题意补充代码，根据问题的条件来推入堆中
heapq.heappush(heap, (CRITERIA, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for num in heap]
二分查找
java
public int fn(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
// 根据题意补充代码
return mid;
}
if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// left 是插入点
return left;
}
python
def fn(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
# 根据题意补充代码
return
if arr[mid] > target:
right = mid - 1
else:
left = mid + 1
# left 是插入点
return left
重复元素，最左边的插入点
java
public int fn(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid
} else {
left = mid + 1;
}
}
return left;
}
python
def fn(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] >= target:
right = mid
else:
left = mid + 1
return left
重复元素，最右边的插入点
java
public int fn(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
python
def fn(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] > target:
right = mid
else:
left = mid + 1
return left
贪心问题
寻找最小值
java
public int fn(int[] arr) {
int left = MINIMUM_POSSIBLE_ANSWER;
int right = MAXIMUM_POSSIBLE_ANSWER;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
public boolean check(int x) {
// 这个函数的具体实现取决于问题
return BOOLEAN;
}
python
def fn(arr):
def check(x):
# 这个函数的具体实现取决于问题
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left
寻找最大值
java
public int fn(int[] arr) {
int left = MINIMUM_POSSIBLE_ANSWER;
int right = MAXIMUM_POSSIBLE_ANSWER;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
public boolean check(int x) {
// 这个函数的具体实现取决于问题
return BOOLEAN;
}
python
def fn(arr):
def check(x):
# 这个函数的具体实现取决于问题
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid - 1
return right
回溯
java
public int backtrack(STATE curr, OTHER_ARGUMENTS...) {
if (BASE_CASE) {
// 修改答案
return 0;
}
int ans = 0;
for (ITERATE_OVER_INPUT) {
// 修改当前状态
ans += backtrack(curr, OTHER_ARGUMENTS...)
// 撤消对当前状态的修改
}
}
python
def backtrack(curr, OTHER_ARGUMENTS...):
if (BASE_CASE):
# 修改答案
return
ans = 0
for (ITERATE_OVER_INPUT):
# 修改当前状态
ans += backtrack(curr, OTHER_ARGUMENTS...)
# 撤消对当前状态的修改
return ans
动态规划: 自顶向下法
java
Map<STATE, Integer> memo = new HashMap<>();
public int fn(int[] arr) {
return dp(STATE_FOR_WHOLE_INPUT, arr);
}
public int dp(STATE, int[] arr) {
if (BASE_CASE) {
return 0;
}
if (memo.contains(STATE)) {
return memo.get(STATE);
}
int ans = RECURRENCE_RELATION(STATE);
memo.put(STATE, ans);
return ans;
}
python
def fn(arr):
def dp(STATE):
if BASE_CASE:
return 0
if STATE in memo:
return memo[STATE]
ans = RECURRENCE_RELATION(STATE)
memo[STATE] = ans
return ans
memo = {}
return dp(STATE_FOR_WHOLE_INPUT)
构建前缀树（字典树）
java
// 注意:只有需要在每个节点上存储数据时才需要使用类。
// 否则，您可以只使用哈希映射实现一个前缀树。
class TrieNode {
// 你可以将数据存储在节点上
int data;
Map<Character, TrieNode> children;
TrieNode() {
this.children = new HashMap<>();
}
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word: words) {
TrieNode curr = root;
for (char c: word.toCharArray()) {
if (!curr.children.containsKey(c)) {
curr.children.put(c, new TrieNode());
}
curr = curr.children.get(c);
}
// 这个位置上的 curr 已经有一个完整的单词
// 如果你愿意，你可以在这里执行更多的操作来给 curr 添加属性
}
return root;
}
python
# 注意:只有需要在每个节点上存储数据时才需要使用类。
# 否则，您可以只使用哈希映射实现一个前缀树。
class TrieNode:
def __init__(self):
# you can store data at nodes if you wish
self.data = None
self.children = {}
def fn(words):
root = TrieNode()
for word in words:
curr = root
for c in word:
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c]
# 这个位置上的 curr 已经有一个完整的单词
# 如果你愿意，你可以在这里执行更多的操作来给 curr 添加属性
return root
评论区