算法代码题——模板

---

1. 双指针: 只有一个输入, 从两端开始遍历

def fn(arr):left = ans = 0right = len(arr) - 1while left < right:# 一些根据 letf 和 right 相关的代码补充if CONDITION:left += 1else:right -= 1return ans

int fn(vector<int>& arr) {int left = 0;int right = int(arr.size()) - 1;int ans = 0;while (left < right) {// 一些根据 letf 和 right 相关的代码补充if (CONDITION) {left++;} else {right--;}}return ans;
}

2. 双指针: 有两个输入, 两个都需要遍历完

def fn(arr1, arr2):i = j = ans = 0while i < len(arr1) and j < len(arr2):# 根据题意补充代码if CONDITION:i += 1else:j += 1while i < len(arr1):# 根据题意补充代码i += 1while j < len(arr2):# 根据题意补充代码j += 1return ans

int fn(vector<int>& arr1, vector<int>& arr2) {int i = 0, j = 0, ans = 0;while (i < arr1.size() && j < arr2.size()) {// 根据题意补充代码if (CONDITION) {i++;} else {j++;}}while (i < arr1.size()) {// 根据题意补充代码i++;}while (j < arr2.size()) {// 根据题意补充代码j++;}return ans;
}

3. 滑动窗口

def fn(arr):left = ans = curr = 0for right in range(len(arr)):# 根据题意补充代码来将 arr[right] 添加到 currwhile WINDOW_CONDITION_BROKEN:# 从 curr 中删除 arr[left]left += 1# 更新 ansreturn ans

int fn(vector<int>& arr) {int left = 0, ans = 0, curr = 0;for (int right = 0; right < arr.size(); right++) {// 根据题意补充代码来将 arr[right] 添加到 currwhile (WINDOW_CONDITION_BROKEN) {// 从 curr 中删除 arr[left]left++;}// 更新 ans}return ans;
}

4. 构建前缀和

def fn(arr):prefix = [arr[0]]for i in range(1, len(arr)):prefix.append(prefix[-1] + arr[i])return prefix

vector<int> fn(vector<int>& arr) {vector<int> prefix(arr.size());prefix[0] = arr[0];for (int i = 1; i < arr.size(); i++) {prefix[i] = prefix[i - 1] + arr[i];}return prefix;
}

5. 高效的字符串构建

# arr 是一个字符列表
def fn(arr):ans = []for c in arr:ans.append(c)return "".join(ans)

string fn(vector<char>& arr) {return string(arr.begin(), arr.end())
}

6. 链表: 快慢指针

def fn(head):slow = headfast = headans = 0while fast and fast.next:# 根据题意补充代码slow = slow.nextfast = fast.next.nextreturn ans

int fn(ListNode* head) {ListNode* slow = head;ListNode* fast = head;int ans = 0;while (fast != nullptr && fast->next != nullptr) {// 根据题意补充代码slow = slow->next;fast = fast->next->next;}return ans;
}

7. 反转链表

def fn(head):curr = headprev = Nonewhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_node return prev

ListNode* fn(ListNode* head) {ListNode* curr = head;ListNode* prev = nullptr;while (curr != nullptr) {ListNode* nextNode = curr->next;curr->next = prev;prev = curr;curr = nextNode;}return prev;
}

8. 找到符合确切条件的子数组数

from collections import defaultdictdef fn(arr, k):counts = defaultdict(int)counts[0] = 1ans = curr = 0for num in arr:# 根据题意补充代码来改变 currans += counts[curr - k]counts[curr] += 1return ans

int fn(vector<int>& arr, int k) {unordered_map<int, int> counts;counts[0] = 1;int ans = 0, curr = 0;for (int num: arr) {// 根据题意补充代码来改变 currans += counts[curr - k];counts[curr]++;}return ans;
}

9. 单调递增栈

def fn(arr):stack = []ans = 0for num in arr:# 对于单调递减的情况，只需将 > 翻转到 <while stack and stack[-1] > num:# 根据题意补充代码stack.pop()stack.append(num)return ans

int fn(vector<int>& arr) {stack<integer> stack;int ans = 0;for (int num: arr) {// 对于单调递减的情况，只需将 > 翻转到 <while (!stack.empty() && stack.top() > num) {// 根据题意补充代码stack.pop();}stack.push(num);}
}

10. 二叉树: DFS (递归)]

def dfs(root):if not root:returnans = 0# 根据题意补充代码dfs(root.left)dfs(root.right)return ans

int dfs(TreeNode* root) {if (root == nullptr) {return 0;}int ans = 0;// 根据题意补充代码dfs(root.left);dfs(root.right);return ans;
}

11. 二叉树: DFS (迭代)

def dfs(root):stack = [root]ans = 0while stack:node = stack.pop()# 根据题意补充代码if node.left:stack.append(node.left)if node.right:stack.append(node.right)return ans

int dfs(TreeNode* root) {stack<TreeNode*> stack;stack.push(root);int ans = 0;while (!stack.empty()) {TreeNode* node = stack.top();stack.pop();// 根据题意补充代码if (node->left != nullptr) {stack.push(node->left);}if (node->right != nullptr) {stack.push(node->right);}}return ans;
}

12. 二叉树: BFS

from collections import dequedef fn(root):queue = deque([root])ans = 0while 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

int fn(TreeNode* root) {queue<TreeNode*> queue;queue.push(root);int ans = 0;while (!queue.empty()) {int currentLength = queue.size();// 做一些当前层的操作for (int i = 0; i < currentLength; i++) {TreeNode* node = queue.front();queue.pop();// 根据题意补充代码if (node->left != nullptr) {queue.push(node->left);}if (node->right != nullptr) {queue.push(node->right);}}}return ans;
}

13. 图: DFS (递归)

以下图模板假设节点编号从 0 到 n - 1 ，并且图是以邻接表的形式给出的。

• 根据问题的不同，可能需要在使用模板之前将输入转换为等效的邻接表。

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 ansseen = {START_NODE}return dfs(START_NODE)

unordered_set<int> seen;int fn(vector<vector<int>>& graph) {seen.insert(START_NODE);return dfs(START_NODE, graph);
}int fn dfs(int node, vector<vector<int>>& graph) {int ans = 0;// 根据题意补充代码for (int neighbor: graph[node]) {if (seen.find(neighbor) == seen.end()) {seen.insert(neighbor);ans += dfs(neighbor, graph);}}return ans;
}

14. 图: DFS (迭代)

def fn(graph):stack = [START_NODE]seen = {START_NODE}ans = 0while stack:node = stack.pop()# 根据题意补充代码for neighbor in graph[node]:if neighbor not in seen:seen.add(neighbor)stack.append(neighbor)return ans

int fn(vector<vector<int>>& graph) {stack<int> stack;unordered_set<int> seen;stack.push(START_NODE);seen.insert(START_NODE);int ans = 0;while (!stack.empty()) {int node = stack.top();stack.pop();// 根据题意补充代码for (int neighbor: graph[node]) {if (seen.find(neighbor) == seen.end()) {seen.insert(neighbor);stack.push(neighbor);}}}
}

15. 图: BFS

from collections import dequedef fn(graph):queue = deque([START_NODE])seen = {START_NODE}ans = 0while queue:node = queue.popleft()# 根据题意补充代码for neighbor in graph[node]:if neighbor not in seen:seen.add(neighbor)queue.append(neighbor)return ans

int fn(vector<vector<int>>& graph) {queue<int> queue;unordered_set<int> seen;queue.add(START_NODE);seen.insert(START_NODE);int ans = 0;while (!queue.empty()) {int node = queue.front();queue.pop();// 根据题意补充代码for (int neighbor: graph[node]) {if (seen.find(neighbor) == seen.end()) {seen.insert(neighbor);queue.push(neighbor);}}}
}

16. 找到堆的前 k 个元素

import heapqdef 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]

vector<int> fn(vector<int>& arr, int k) {priority_queue<int, CRITERIA> heap;for (int num: arr) {heap.push(num);if (heap.size() > k) {heap.pop();}}vector<int> ans;while (heap.size() > 0) {ans.push_back(heap.top());heap.pop();}return ans;
}

17. 二分查找

def fn(arr, target):left = 0right = len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:# 根据题意补充代码returnif arr[mid] > target:right = mid - 1else:left = mid + 1# left 是插入点return left

int binarySearch(vector<int>& arr, int target) {int left = 0;int right = int(arr.size()) - 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;}

18. 二分查找: 重复元素，最左边的插入点

def fn(arr, target):left = 0right = len(arr)while left < right:mid = (left + right) // 2if arr[mid] >= target:right = midelse:left = mid + 1return left

int binarySearch(vector<int>& arr, int target) {int left = 0;int right = arr.size();while (left < right) {int mid = left + (right - left) / 2;if (arr[mid] >= target) {right = mid;} else {left = mid + 1;}}return left;
}

19. 二分查找: 重复元素，最右边的插入点

def fn(arr, target):left = 0right = len(arr)while left < right:mid = (left + right) // 2if arr[mid] > target:right = midelse:left = mid + 1return left

int binarySearch(vector<int>& arr, int target) {int left = 0;int right = arr.size();while (left < right) {int mid = left + (right - left) / 2;if (arr[mid] > target) {right = mid;} else {left = mid + 1;}}return left;
}

20. 二分查找: 贪心问题

寻找最小值：

def fn(arr):def check(x):# 这个函数的具体实现取决于问题return BOOLEANleft = MINIMUM_POSSIBLE_ANSWERright = MAXIMUM_POSSIBLE_ANSWERwhile left <= right:mid = (left + right) // 2if check(mid):right = mid - 1else:left = mid + 1return left

int fn(vector<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;
}bool check(int x) {// 这个函数的具体实现取决于问题return BOOLEAN;
}

寻找最大值：

def fn(arr):def check(x):# 这个函数的具体实现取决于问题return BOOLEANleft = MINIMUM_POSSIBLE_ANSWERright = MAXIMUM_POSSIBLE_ANSWERwhile left <= right:mid = (left + right) // 2if check(mid):left = mid + 1else:right = mid - 1return right

int fn(vector<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;
}bool check(int x) {// 这个函数的具体实现取决于问题return BOOLEAN;
}

21. 回溯

def backtrack(curr, OTHER_ARGUMENTS...):if (BASE_CASE):# 修改答案returnans = 0for (ITERATE_OVER_INPUT):# 修改当前状态ans += backtrack(curr, OTHER_ARGUMENTS...)# 撤消对当前状态的修改return ans

int backtrack(STATE curr, OTHER_ARGUMENTS...) {if (BASE_CASE) {// 修改答案return 0;}int ans = 0;for (ITERATE_OVER_INPUT) {// 修改当前状态ans += backtrack(curr, OTHER_ARGUMENTS...)// 撤消对当前状态的修改}return ans;
}

22. 动态规划: 自顶向下法

def fn(arr):def dp(STATE):if BASE_CASE:return 0if STATE in memo:return memo[STATE]ans = RECURRENCE_RELATION(STATE)memo[STATE] = ansreturn ansmemo = {}return dp(STATE_FOR_WHOLE_INPUT)

unordered_map<STATE, int> memo;int fn(vector<int>& arr) {return dp(STATE_FOR_WHOLE_INPUT, arr);
}int dp(STATE, vector<int>& arr) {if (BASE_CASE) {return 0;}if (memo.find(STATE) != memo.end()) {return memo[STATE];}int ans = RECURRENCE_RELATION(STATE);memo[STATE] = ans;return ans;
}

23. 构建前缀树（字典树）

• 注意:只有需要在每个节点上存储数据时才需要使用类。
• 否则，您可以只使用哈希映射实现一个前缀树。

# 注意:只有需要在每个节点上存储数据时才需要使用类。
# 否则，您可以只使用哈希映射实现一个前缀树。
class TrieNode:def __init__(self):# you can store data at nodes if you wishself.data = Noneself.children = {}def fn(words):root = TrieNode()for word in words:curr = rootfor c in word:if c not in curr.children:curr.children[c] = TrieNode()curr = curr.children[c]# 这个位置上的 curr 已经有一个完整的单词# 如果你愿意，你可以在这里执行更多的操作来给 curr 添加属性return root

// 注意:只有需要在每个节点上存储数据时才需要使用类。
// 否则，您可以只使用哈希映射实现一个前缀树。
struct TrieNode {int data;unordered_map<char, TrieNode*> children;TrieNode() : data(0), children(unordered_map<char, TrieNode*>()) {}
};TrieNode* buildTrie(vector<string> words) {TrieNode* root = new TrieNode();for (string word: words) {TrieNode* curr = root;for (char c: word) {if (curr->children.find(c) == curr->children.end()) {curr->children[c] = new TrieNode();}curr = curr->children[c];// 这个位置上的 curr 已经有一个完整的单词// 如果你愿意，你可以在这里执行更多的操作来给 curr 添加属性}}return root;
}