刷题思路 | ♦️

type

status

date

slug

summary

cpp


using namespace std;

using Matrix = vector<vector<int>>;

void sliding_window(const Matrix &arr, int window_rows, int window_cols) {
  int rows = arr.size();
  int cols = arr[0].size();
  for (size_t i = 0; i < rows - window_cols + 1; i++) {
    for (size_t j = 0; j < cols - window_rows + 1; j++) {
      for (size_t k = 0; k < window_rows; k++) {
        for (size_t l = 0; l < window_cols; l++) {
          printf("%2d ", arr[i + k][j + l]);
        }
        printf("\n");
      }
      printf("\n");
    }
  }
}

二分

在单调递增序列中找 x 或x 的后继使用左中位数

python


def bi(lst:List[int],target:int) -> int:
    left , right = 0,len(lst)    
    while left < right:
        mid = left + (right-left)//2
        # check
        if lst[mid] >= target: 
            right = mid
        else:
            left = mid + 1
    return left    # a[last] < target , return len(lst)

死循环的原因是 left 或者 right 一直保持不变

在单调递增序列中找 x 或x 的前驱使用右中位数

python


def bi(lst:List[int],target:int) -> int:
    left , right = 0,len(lst)    
    while left < right:
        mid = left + (right-left + 1)//2
        # check
        if lst[mid] <= target: 
            left = mid
        else:
            left = mid - 1
    return left    # a[last] < target , return len(lst)

注意负数时向 0 取整的问题

c++ lower_bound upper_bound

python

最大值最小化/最小值最大化

如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做，不满足看做，至少对于这个条件的这一维度是有序的）。换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值。

从小到大枚举这个作为答案的「最大值」，然后去判断是否合法。若答案单调，就可以使用二分搜索法来更快地找到答案。因此，要想使用二分搜索法来解这种「最大值最小化」的题目，需要满足以下三个条件：

答案在一个固定区间内；

可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；

可行解对于区间满足一定的单调性。换言之，如果是符合条件的，那么有或者也符合条件。（这样下来就满足了上面提到的单调性）

python


    while l < r:
        mid = l + (r-l) // 2
        if (check(mid,lst,c)):
            ans = mid
            # l = ...
        else:
            # r = ...

实数二分

二叉树统一迭代

栈，标记法

左中右 → 右中左

python


# pre
def preorder(root:TreeNode) -> List[int]:
				result = []
        st= []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
                st.append(node) #中
                st.append(None)
            else:
                node = st.pop()
                result.append(node.val)
        return result

图

存储

cpp


// 矩阵
int grid[N][N];
// 邻接表
struct Edge {
	int from;
	int to;
	int w;
	edge(int a,int b, int c): from(a), to(b),w(c) {}
};

vector<Edge> e[N];

// 链式前向星
// todo

遍历

cpp



const int N = 55;

int grid[N][N];
int n, m;
bool visited[N];

// top bottom left right
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y) {
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
      continue;
    }
    if (grid[nx][xy] == 1 && !visited[nx][ny]) {
			 visited[nx][ny] = true;
			     dfs(nx, ny);
    }
  }
}

using PII = pair<int,int>

void bfs(int x, int y) {
    queue<PII> que;
    que.push({x, y});
    while(!que.empty()) {
        auto cur = que.front();
        que.pop();
        int curx = cur.first;
        int cury = cur.second;
        visited[curx][cury] = true; // 从队列中取出在标记走过
        for (int i = 0; i < 4; i++) {
            int nx = curx + dx[i;
            int ny = cury + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
            if (!visited[nx][ny] && grid[nx][ny] == '1') {
                que.push({nx, ny});
            }
        }
    }

}

最小生成树

最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

Prim

第一步，选距离生成树最近节点

第二步，最近节点加入生成树

第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

python


def main():
    v, e = map(int, input().split())
    grid = [[10001] * (v + 1) for _ in range(v + 1)]
    for _ in range(e):
        x, y, k = map(int, input().split())
        grid[x][y] = k
        grid[y][x] = k

    min_dist = [10001] * (v + 1)
    in_tree = [False] * (v + 1)
    parent = [-1] * (v+1)
    for _ in range(1, v):
        cur = -1
        min_val = 10002
        for j in range(1, v + 1):
            if not in_tree[j] and min_dist[j] < min_val:
                cur = j
                min_val = min_dist[j]
        in_tree[cur] = True
        for j in range(1, v + 1):
            if not in_tree[j] and grid[cur][j] < min_dist[j]:
                min_dist[j] = grid[cur][j]
                parent[j] = cur
    res = sum(min_dist[2 : v + 1])
    print(res)
    for i in range(1,v + 1):
			  print(f"{i}->{parent[i]}")


if __name__ == "__main__":
    main()

Kruskal

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。

边的权值排序，因为要优先选最小的边加入到生成树里

遍历排序后的边

如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

python


class Dsu:
    def __init__(self, n):
        lst = [0] * n
        for i in range(n):
            lst[i] = i
        self.father = lst

    def join(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        self.father[v] = u

    def find(self, val):
        if val == self.father[val]:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]

    def is_same(self, u, v):
        u = self.find(u)
        v = self.find(v)
        return u == v


class Edge:
    def __init__(self, left, right, val):
        self.l = left
        self.r = right
        self.val = val


def kruskal(_v, edges):
    edges.sort(key=lambda e: e.val)
    n = len(edges)
    dsu = Dsu(n + 1)
    ret = 0
    for e in edges:
        x = dsu.find(e.l)
        y = dsu.find(e.r)
        if x != y:
            ret += e.val
            dsu.join(x, y)
    return ret


if __name__ == "__main__":
    v, e = map(int, input().split())
    edges = []
    for _ in range(e):
        v1, v2, val = map(int, input().split())
        edges.append(Edge(v1, v2, val))
    res = kruskal(v, edges)
    print(res)

Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合

Prim 算法时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法时间复杂度为 nlogn，其中 n 为边的数量，适用稀疏图。

拓扑排序

找到入度为0 的节点，加入结果集

将该节点从图中移除

那么如果我们发现结果集元素个数不等于图中节点个数，我们就可以认定图中一定有有向环！

python


from collections import defaultdict, deque


def topological_sort(n, edges):
    in_degree = [0] * n
    umap = defaultdict(list)
    for s, t in edges:
        in_degree[t] += 1
        umap[s].append(t)

    q = deque([i for i in range(n) if in_degree[i] == 0])
    res = []
    while q:
        cur = q.popleft()
        res.append(cur)
        for f in umap[cur]:
            in_degree[f] -= 1
            if in_degree[f] == 0:
                q.append(f)
    if len(res) == n:
        print(" ".join(map(str, res)))
    else:
        print(-1)


if __name__ == "__main__":
    n, m = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(m)]
    topological_sort(n, edges)

最短路径

dijkstra 算法可以同时求起点到所有节点的最短路径

权值不能为负数

第一步，选源点到哪个节点近且该节点未被访问过

第二步，该最近节点被标记访问过

第三步，更新非访问节点到源点的距离（即更新minDist数组）

python


def dijkstra(n, m, edges, start, end):
    grid = [[float("inf")] * (n + 1) for _ in range(n + 1)]
    for p1, p2, val in edges:
        grid[p1][p2] = val
    min_dis = [float("inf")] * (n + 1)
    visited = [False] * (n + 1)
    min_dis[start] = 0
    for _ in range(1, n + 1):
        min_val = float("inf")
        cur = -1
        for v in range(1, n + 1):
            if not visited and min_dis[v] < min_val:
                min_val = min_dis[v]
                cur = v

        if cur == -1:
            break
        visited[cur] = True
        for v in range(1, n + 1):
            if (
                not visited[v]
                and grid[cur][v] != float("inf")
                and min_dis[cur] + grid[cur][v] < min_dis[v]
            ):
                min_dis[v] = min_dis[cur] + grid[cur][v]
    return -1 if min_dis[end] == float("inf") else min_dis[end]

python


import heapq


class Edge:
    def __init__(self, to, val):
        self.to = to
        self.val = val


def dijkstra(n, m, edges, start, end):
    grid = [[] for _ in range(n + 1)]
    for p1, p2, val in edges:
        grid[p1].append(Edge(p2, val))

    min_dis = [float("inf")] * (n + 1)
    visited = [False] * (n + 1)

    pq = []
    heapq.heappush(pq, (0, start))
    min_dis[start] = 0

    while pq:
        cur_dist, cur_node = heapq.heappop(pq)
        if visited[cur_node]:
            continue
        visited[cur_node] = True
        for e in grid[cur_node]:
            if not visited[e.to] and cur_dist + e.val < min_dis[e.to]:
                min_dis[e.to] = cur_dist + e.val
                heapq.heappush(pq, (min_dis[e.to], e.to))

    return -1 if min_dis[end] == float("inf") else min_dis[end]

python


#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid;

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid.push_back({p1, p2, val});

    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int> minDist(n + 1 , INT_MAX);
    minDist[start] = 0;
    for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次
        for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛
            int from = side[0]; // 边的出发点
            int to = side[1]; // 边的到达点
            int price = side[2]; // 边的权值
            // 松弛操作 
            // minDist[from] != INT_MAX 防止从未计算过的节点出发
            if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { 
                minDist[to] = minDist[from] + price;  
            }
        }
    }
    if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
    else cout << minDist[end] << endl; // 到达终点最短路径

}

旅行商

并查集（Disjoint Set）

网络连接问题：判断网络中的节点是否连通。

社交网络中的关系：判断两个人是否属于同一个社交圈。

图的连通性问题：判断图中的节点是否在同一个连通分量中。

路径压缩

按 rank 合并

python


class Dsu:
   def __init__(self,n):
        lst = [0] * n
        for i in range(n):
            lst[i] = i
        self.father = lst
    
   def join(self,u,v):
        u = self.find(u)
        v = self.find(v)
        if u==v:
            return
        self.father[v] = u

   def find(self,val):
        if val == self.father[val]:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]

   def is_same(self,u,v):
        u = self.find(u)
        v = self.find(v)
        return u == v

misc

考虑比较两个数a,b 统计数字相同但是位置不同的数的数量

遍历数字，统计频率，注意使用min（考虑两边都有）

python


def my_count_diff(num1,nums2):
    s1 = str(num1)
    s2 = str(num2)
    
    cnt1 = [0] * 10
    cnt2 = [0] * 10


    for i in range(len(s1)):
        c1 = int(s1[i])
        c2 = int(s2[i])

        if c1 != c2:
            cnt1[c1] += 1
            cnt2[c2] += 1
    
    ans = 0
    for i in range(10):
        ans += min(cnt1[i],cnt2[i])
    return ans
            



def count_different_positions(num1, num2):

    # 将数字转为字符串
    str1 = str(num1)
    str2 = str(num2)
    
    # 初始化计数器
    count = 0
    
    # 创建数字频率字典
    freq1 = {}
    freq2 = {}
    
    # 记录每个数字的出现频率
    for digit in str1:
        if digit in freq1:
            freq1[digit] += 1
        else:
            freq1[digit] = 1
            
    for digit in str2:
        if digit in freq2:
            freq2[digit] += 1
        else:
            freq2[digit] = 1
            
    # 计算相同数字但位置不同的数量
    for digit in freq1:
        if digit in freq2:
            count += min(freq1[digit], freq2[digit])
    
    # 计算相同数字在同一位置的数量
    same_position = sum(1 for i in range(4) if str1[i] == str2[i])
    
    # 返回相同数字但位置不同的数量
    return count - same_position

动态规划

给定整数k，构造一个数组a，使得a恰好有k个最长递增子序列

把个数记作 x,把 x 二进制拆分成

2^{m1} + 2^{m2} + 2^{m3} + ...

例如 13 = 2

^3 + 2^2 + 2^0

，我们可以构造 nums=[91,91,92,92,93,93,81,82,82,83,83,71,72,73]，看成三段 [91,91,92,92,93,93], [81,82,82,83,83], [71,72,73]，每一段的最长递增子序列的个数就是前面拆分出的二进制数。这里只是举了个例子，每两段之间的的gap可以调大一些（比如 1000）以满足构造要求。

注意这里LIS的长度为3