常见算法模板-东家

双指针:

只有一个输入, 从两端开始遍历

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

目录CONTENT

常见算法模板

双指针:

只有一个输入, 从两端开始遍历

有两个输入, 两个都需要遍历完

滑动窗口

构建前缀和

高效的字符串构建

链表: 快慢指针

反转链表

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

单调递增栈

二叉树: DFS (递归)

二叉树: DFS (迭代)

二叉树: BFS

图: DFS (递归)

图: DFS (迭代)

图: BFS

找到堆的前 k 个元素

二分查找

重复元素，最左边的插入点

重复元素，最右边的插入点

贪心问题

寻找最小值

寻找最大值

回溯

动态规划: 自顶向下法

构建前缀树（字典树）

评论区