Skip to content

Latest commit

 

History

History
1068 lines (862 loc) · 25.1 KB

ch06.md

File metadata and controls

1068 lines (862 loc) · 25.1 KB
Raw

数据结构基础 图 + 搜索

章节 题目来源 链接 分类 备注
祖父节点值为偶数的节点和 Leetcode.com 祖父节点值为偶数的节点和 树 DFS
紫书 6.4.2 6-14 Abbott的复仇 BFS
水域大小 程序员面试金典 水域大小 BFS + Flood Fill 广搜 + 染色
扫雷 谷歌 扫雷 BFS BFS + Flood Fill
迷宫 acwing.com 迷宫 BFS 模板题
迷宫问题 acwing.com 迷宫问题 BFS 模板题+每次记录前驱节点
矩阵中的路径 剑指offer 矩阵路径 DFS 模板题
紫书 6.4.3 6-15 拓扑排序 6-15 Uva10305 Ordering Tasks 拓扑排序 模板题
判断是否是拓扑序列 acwing.com 判断是否是拓扑序列 拓扑排序 检查序列的入度
可达性统计 acwing.com 可达性统计 拓扑排序 bitset的使用
奖金 acwing.com 奖金 拓扑排序 反着建图

📅 6.26

祖父节点值为偶数的节点和

题意

计算所有父节点的父节点值为偶数的节点的值

思路分析

这是树 + DFS的题目。已知根节点，判断他是否有孙子节点，如果有则将其累加，最后递归下去。

AC代码

class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        if(root == null) return 0;
        int res = 0;
        if(root.val % 2 == 0){
            if(root.left != null){
                if(root.left.left != null) res += root.left.left.val;
                if(root.left.right != null) res += root.left.right.val;
            }
            if(root.right != null){
                if(root.right.left != null) res += root.right.left.val;
                if(root.right.right != null) res += root.right.right.val;
            }
        }
        return res + sumEvenGrandparent(root.left) + sumEvenGrandparent(root.right);
    }
}

📅 6.18

水域大小

题意

输入一个数组，0代表水域，求每个连通的水域的大小，8个方向都算连通

思路分析

宽搜确定每个水域大小 染色保证不会重复

AC代码

Python 
from collections import deque


class Solution:
    def pondSizes(self, land: List[List[int]]) -> List[int]:
        rows = len(land)
        cols = len(land[0])
        path = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]
        def bfs(row, col):
            s = 0
            queue = deque([(row, col)])
            while queue:
                size = len(queue)
                while size > 0:
                    size -= 1
                    x, y = queue.popleft()
                    s += 1
                    for k in range(8):
                        nx = x + path[k][0]
                        ny = y + path[k][1]
                        if nx >= 0 and nx < rows and ny >= 0 and ny < cols and land[nx][ny] == 0:
                            land[nx][ny] = -1
                            queue.append((nx, ny))
            return s
        res = []
        for i in range(rows):
            for j in range(cols):
                if land[i][j] == 0:
                    land[i][j] = -1
                    size = bfs(i, j)
                    res.append(size)
        res.sort()
        return res

扫雷

题意

扫雷游戏，有一个方格，其中若无地雷，则有一数字标识周围雷的数量（8个格子中雷的数量），如果此数字是0， 则点击时会自动递归点击周围8个方格。已知所有雷的位置，问最少点几次可以完成游戏;

思路分析

  1. 先计算出每个方格的数字，如果当前点是雷，则标注为-1, for循环遍历及可计算
  2. 之后先点击数字是0的格子，利用dfs扩展，点过的点标注为-1。这里注意每次dfs之前要判断一下，当前点是不是数字为0
  3. 之后点击剩余的格子， 及for循环遍历计算剩余的不是-1的点

AC代码

Cpp 
#include <iostream>


using namespace std;
const int N = 310;
char str[N][N];
int g[N][N];
int path[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
int n;

// 如果当前点是0 则可以扩展点击
void dfs(int i, int j){
    int c = g[i][j];
    g[i][j] = -1;
    if(c != 0) return;
    for(int k = 0; k < 8; k ++){
        int nx = i + path[k][0];
        int ny = j + path[k][1];
        if(nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] != -1){
            dfs(nx, ny);
        }
    }
}

int main(){
    int T;
    scanf("%d", &T);
    for(int I = 1; I <= T; I ++){
      scanf("%d", &n);
      for(int i = 0; i < n; i ++){
          scanf("%s", str[i]);
      }
      
    // 先统计每个点的周围的雷的个数
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            if(str[i][j] == '*'){
                g[i][j] = -1;
            } else {
                g[i][j] = 0;
                for(int k = 0; k < 8; k ++){
                    int nx = i + path[k][0];
                    int ny = j + path[k][1];
                    if(nx >= 0 && nx < n && ny >= 0 && ny <= n && str[nx][ny] == '*'){
                        g[i][j] ++;
                    }
                }
            }
        }
    }
    // 先点0点
    // 如果当前点是0 则让其扩展
    int res = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            if(g[i][j] == 0){
                res ++;
                dfs(i, j); 
            }        
        }
    }
    
    // 点其他点
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            if(g[i][j] != -1){
                res ++;
            }
        }
    }
    printf("Case #%d: %d\n", I, res);
    }
}
Python

📅 6.4 打卡

T = int(input())
for case in range(1, T + 1):
    n = int(input())
    strr = [[0 for i in range(n + 1)] for _ in range(n + 1)]
    g = [[0 for i in range(n + 1)] for _ in range(n + 1)]
    path = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]
    
    # 把输入节点的周围八个点都点一遍
    def dfs(i, j):
        c = g[i][j]
        # 讲此点标记
        g[i][j] = -1
        if c != 0:
            return 
        for item in path:
            nx = i + item[0]
            ny = j + item[1]
            if nx >= 0 and nx < n and ny >= 0 and ny < n and g[nx][ny] != -1:
                dfs(nx, ny)
    
    # 输入
    for i in range(n):
        t = list(map(str, input().strip().split()))
        for j in range(n):
            strr[i][j] = t[0][j]
    
    # 计算每个点的周围的雷的个数
    for i in range(n):
        for j in range(n):
            if strr[i][j] == '*':
                g[i][j] = -1
            else:
                cnt = 0
                for item in path:
                    nx = i + item[0]
                    ny = j + item[1]
                    if nx >= 0 and nx < n and ny >= 0 and ny < n and strr[nx][ny] == '*':
                        cnt += 1
                g[i][j] = cnt
    
    res = 0
    # 先点0 的点
    for i in range(n):
        for j in range(n):
            if g[i][j] == 0:
                dfs(i, j)
                res += 1
                
    # 统计现在还有多少剩余点
    for i in range(n):
        for j in range(n):
            if g[i][j] != -1:
                res += 1
    
    print('Case #{}: {}'.format(case, res))
Java

📅打卡 🆕 Java版本

import java.io.*;
import java.util.*;


class Main{


    public static final int N = 310;
    public static int n;
    public static char[][] str = new char[N][N];  
    public static int[][] g = new int[N][N];
    public static int[][] path = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
    
    public static void dfs(int i, int j){
        int c = g[i][j];
        g[i][j] = -1;
        if(c != 0){
            return;
        }
        for(int k = 0; k < 8; k ++){
            int nx = i + path[k][0];
            int ny = j + path[k][1];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] != -1){
                dfs(nx, ny);
            }
        }
    }
    
    
    public static void main(String[] args) throws IOException{
        int T = 0;
        // Scanner in = new Scanner(new BufferedInputStream(System.in));
        // T = in.nextInt();
        AReader in = new AReader(System.in);
        T = in.nextInt();
        
        for(int I = 1; I <= T; I ++){
            n = in.nextInt();
            
            
            for(int i = 0; i < n; i ++){
                String s = in.nextLine();
                for(int j = 0; j < n; j ++){
                    // str[i][j] = in.nextChar();
                    str[i][j] = s.charAt(j);
                }
            }
            
            // 先将每个点标记周围又多少个雷
            for(int i = 0; i < n; i ++){
                for(int j = 0; j < n; j ++){
                    if(str[i][j] == '*'){
                        g[i][j] = -1;
                    } else {
                        int cnt = 0;
                        for(int k = 0; k < 8; k ++){
                            int nx = i + path[k][0];
                            int ny = j + path[k][1];
                            if(nx >= 0 && nx < n && ny >= 0 && ny < n && str[nx][ny] == '*'){
                                cnt ++;
                            }
                        }
                        g[i][j] = cnt;
                    }
                }
            }
            
            int res = 0;
            // 
            for(int i = 0; i < n; i ++){
                for(int j = 0; j < n; j ++){
                    if(g[i][j] == 0){
                        dfs(i, j);
                        res ++;
                    }    
                }
            }
            
            for(int i = 0; i < n; i ++){
                for(int j = 0; j < n; j ++){
                    if(g[i][j] != -1){
                        res ++;
                    }
                }
            }
            System.out.println("Case #" + I + ": " + res);
            
        }
    }
}
// 输入输出模板来自 https://www.rainng.com/java-acm-fast-io/
class AReader implements Closeable {
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    public AReader(InputStream inputStream) {
        reader = new BufferedReader(new InputStreamReader(inputStream));
        tokenizer = new StringTokenizer("");
    }
    private String innerNextLine() {
        try {
            return reader.readLine();
        } catch (IOException ex) {
            return null;
        }
    }
    public boolean hasNext() {
        while (!tokenizer.hasMoreTokens()) {
            String nextLine = innerNextLine();
            if (nextLine == null) {
                return false;
            }
            tokenizer = new StringTokenizer(nextLine);
        }
        return true;
    }
    public String nextLine() {
        tokenizer = new StringTokenizer("");
        return innerNextLine();
    }
    public String next() {
        hasNext();
        return tokenizer.nextToken();
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    @Override
    public void close() throws IOException {
        reader.close();
    }
}

class AWriter implements Closeable {
    private BufferedWriter writer;
    public AWriter(OutputStream outputStream) {
        writer = new BufferedWriter(new OutputStreamWriter(outputStream));
    }
    public void print(Object object) throws IOException {
        writer.write(object.toString());
    }
    public void println(Object object) throws IOException {
        writer.write(object.toString());
        writer.write("\n");
    }
    @Override
    public void close() throws IOException {
        writer.close();
    }
}

迷宫

题意

输入一个迷宫，输出从左上角走到右下角的最短距离

思路分析

bfs模板题

AC代码

Cpp 
#include <iostream>
#include <queue>
#include <cstring>


using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int d[N][N];

int g[N][N];

void bfs(){
    int cnt = 0;
    queue<PII> q;
    int path[4][4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    q.push({0, 0});
    d[0][0] = 0;
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++){
            int nx = t.first + path[i][0];
            int ny = t.second + path[i][1];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && d[nx][ny] == -1 && g[nx][ny] == 0){
                q.push({nx, ny});
                d[nx][ny] = d[t.first][t.second] + 1;
            }
        }
    }
    printf("%d\n", d[n - 1][m - 1]);
}

int main(){
    
    scanf("%d %d", &n, &m);
    
    memset(d, -1, sizeof(d));
    
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            scanf("%d", &g[i][j]);
        }
    }
    
    bfs();
    return 0;
}

迷宫问题

题意

找到最短路径

思路分析

因为找到的最短路径，所以每个点的先驱节点应该是确定的，所以采用bfs + 每次记录先驱节点。之后通过最后一个点倒序走到起始点。

AC代码

Cpp 
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;
const int N = 1010;
int g[N][N];
typedef pair<int, int> PII;
PII pre[N][N];
int n;
bool flag[N][N];

void bfs(){
    queue<PII> q;
    vector<PII> d;
    q.push({0, 0});
    pre[0][0] = {0, 0};
    flag[0][0] = true;
    int path[4][4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        if(t.first == n - 1 && t.second == n -1) return;
        for(int i = 0; i < 4; i ++){
            int x = t.first + path[i][0];
            int y = t.second + path[i][1];
            if(x >= 0 && x < n && y >= 0 && y < n && flag[x][y] == false && g[x][y] == 0){
                q.push({x, y});
                flag[x][y] = true;
                pre[x][y] = { t.first, t.second };
            }
        }
        
    }
    
    
}

int main(){
    
    scanf("%d", &n);
    
    for(int i = 0; i < n;i ++){
        for(int j = 0; j < n; j ++){
            scanf("%d", &g[i][j]);
        }
    }
    
    bfs();
    vector<PII> res;
    int i = n - 1, j = n - 1;
    while(make_pair(i, j) != make_pair(0, 0)){
        res.push_back(make_pair(i, j));
        PII pre_pii = pre[i][j];
        i = pre_pii.first;
        j = pre_pii.second;
    }
    
    res.push_back({0, 0});
    
    for(auto it = res.rbegin(); it != res.rend(); it ++){
        printf("%d %d\n", it -> first, it -> second);
    }
    
    return 0;
}

矩阵中的路径

思路分析

DFS 模板题

AC代码

Java 
class Solution {
    
    public int rows;
    public int cols;
    public int[][] path = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    
    public boolean dfs(char[][] matrix, String str, int u, int x, int y){
       
        if(u == str.length() - 1){
            return true;
        }
        char ch = matrix[x][y];
        matrix[x][y] = '*';
        
        
        
        for(int i = 0; i < 4; i ++){
            int nx = x + path[i][0];
            int ny = y + path[i][1];
            if(nx >= 0 && nx < rows && ny >= 0 && ny < cols && str.charAt(u + 1) == matrix[nx][ny]){
                if(dfs(matrix, str, u + 1, nx, ny)){
                    return true;
                }
            }
        }
        matrix[x][y] = ch;
        return false;
    }
    
    public boolean hasPath(char[][] matrix, String str) {
        rows = matrix.length;
        if(rows == 0) return false;
        cols = matrix[0].length;
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                if(matrix[i][j] == str.charAt(0) && dfs(matrix, str, 0, i, j)){
                    return true;    
                }
            }
        }
        return false;
    }
}

例题6-15 UVA10305 Ordering Tasks

题意

拓扑排序

思路分析

for(图中的点){
    if(点入度为0){
        入队列
    }
}

while(队列不空){
    node = 队列头弹出一个点
    for(这个node指向所有节点){
        if(如果删掉这条边 node指向的节点的入度为0){
            将node指向的点入队列
        }
    }
}

AC代码

Cpp 
#include <iostream>
#include <cstring>

const int N = 110;
int e[N], ne[N], h[N];
int idx;
int q[N];
int d[N];
int n, m;


void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void top_sort(){
    int hh =0, tt = -1;

    for(int i = 1; i <= n; i ++){
        if(!d[i]){
            q[++ tt] = i;
        }
    }

    while(hh <= tt){
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(-- d[j] == 0){
                q[++ tt] = j;
            }
        }
    }

}

int main(int argc, char const *argv[])
{
    

    while(scanf("%d %d", &n, &m)){
        if(m == 0 && n == 0) break;
        if(m == 0){
            for (int i = 1; i <= n; i++)
            {
                printf("%d ", i);
            }
            puts("");
        } else {

            memset(h, -1, sizeof(h));
            memset(ne, 0, sizeof(ne));
            memset(e, 0, sizeof(e));
            memset(q, 0, sizeof(q));
            memset(d, 0, sizeof(d));
            idx = 0;
            while(m --){
                int a,  b;
                scanf("%d %d", &a, &b);
                add(a, b);
                d[b] ++;
            }
            top_sort();

            for(int i = 0; i < n; i ++){
                printf("%d ", q[i]);
            }

            puts("");
        }
    }

    
}

几道拓扑排序相关的题目

判断是否是拓扑序列

题意

给定一个有向无环图和若干数字序列，判断这个序列是不是这个图的拓扑序列

思路分析

从图的入度下手，拓扑序列，第一个点的入度一定为0，之后删除此点可达的边，下一点的入度也必为0，若下一点入度不为0，则此序列不是拓扑序列，一直检查整个序列。

AC代码

Cpp 
#include <iostream>
#include <cstring>


using namespace std;
const int N = 1010;
const int M = 10010;
int e[M], ne[M], h[N];
int idx;
int q[N];
int d[N];
int res[N];
int n, m;


void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

// 检查此序列是不是拓扑序列
bool test(){
    
    int temp[N];
    
    for(int i = 1; i <= n; i ++){
        temp[i] = d[i];
    }
    
    for(int k = 0; k < n; k ++){
        int i = res[k];
        // 如果此点的入度不为0 则错误
        if(temp[i] != 0){
            return false;
        } else {
            // 将此点的后继节点的入度 -1
            for(int j = h[i]; j != -1; j = ne[j]){
                -- temp[e[j]];
            }
        }
    }
    return true;
}

int main(){
    memset(h, -1, sizeof(h));
    scanf("%d %d", &n, &m);
    while(m --){
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
        d[b] ++;
    }
    int x;
    scanf("%d", &x);
    int cnt = 0;
    while(x --){
        
        for(int i = 0;i < n; i ++){
            scanf("%d", &res[i]);
        }
        
        if(!test()) printf("%d ", cnt);
        cnt ++;
    }
    puts("");
    
    return 0;
}

​

可达性统计

题意

给定一个有向无环图，分别输出从每个点出发能到达的点的数量

分析

假设点u能到达的所有点为f(u), 则f(u) = f(u1) + f(u2) + .... + f(un), u1 ~ un 为u的后继节点。先进行拓扑排序，之后按照拓扑排序的倒序分别统计每个点。

AC代码

Cpp 
#include <iostream>
#include <cstring>
#include <bits/stdc++.h>


using namespace std;
const int N = 30010;
int q[N];
int e[N], ne[N], h[N];
int idx;
int d[N];
bitset<N> f[N];
int n, m;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topsort(){
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++){
        if(d[i] == 0){
            q[++ tt] = i;
        }
    }
    while(hh <= tt){
        auto t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i]){
            auto j = e[i];
            if(-- d[j] == 0){
                q[++ tt] = j;
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    
    memset(h, -1, sizeof(h));
    
    while(m --){
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
        d[b] ++;
    }
    
    topsort();
    // f[i] 中1的个数是点i后续节点的个数 
    for(int i = n - 1; i >= 0; i --){
        int j = q[i];
        f[j][j] = 1;
        for(int i = h[j]; i != -1; i = ne[i]){
            f[j] |= f[e[i]];
        }
    }
    
    for(int i = 1; i <= n; i ++) printf("%d\n", f[i].count());
    return 0;
}

奖金

题意

公司召开了M个人的会议，商讨奖金问题。每个代表发言：我认为a的奖金应该比b高。每人的奖金至少是100元。

思路分析

人与人之间的奖金关系是个有向无环图，其实就是求每个点之后的后继节点最深有多深。这样不如反向建图

在拓扑排序的时候，算出每个点的深度。

AC代码

Cpp 
#include <iostream>
#include <queue>
#include <cstring>


using namespace std;
const int N = 10010;
const int M = 20010;
int e[M], ne[M], idx, h[N];
int d[N];
int dist[N];
int n, m;
int cnt;
typedef pair<int, int> PII;


void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

// 在拓扑排序的时候记录最大深度
void top_sort(){
    queue<PII> q;
    for(int i = 1; i <= n; i ++){
        if(!d[i]){
            q.push({100, i});
            dist[i] = 100;
        }
    }
    while(q.size()){
        auto t = q.front();
        q.pop();
        // 如果cnt == n 说明所有点都进入了队列并弹出 所以是可以拓扑排序的
        // 如果 cnt < n 则说明不存在拓扑序列
        cnt ++;
        int j = t.second;
        // 当前的点的深度
        int distence = t.first;
        for(int i = h[j]; i != -1; i = ne[i]){
            int k = e[i];
            if(-- d[k] == 0){
                // 因为可能有不同的点可以到达这里 所以要用max计算深度
                dist[k] = max(distence + 1, dist[k]);
                q.push({dist[k], k});
            }
        }
    }
}

int main(){
    
    memset(h, -1, sizeof(h));
    
    scanf("%d %d", &n , &m);
    while(m --){
        int a, b;
        scanf("%d %d", &a, &b);
        add(b, a);
        d[a] ++;
    }
    
    top_sort();
    
    int res = 0;
    for(int i = 1; i <= n; i ++){
        res += dist[i];
    }
    
    if(cnt < n){
        puts("Poor Xed");
    } else {
        printf("%d\n", res);
    }
    
    return 0;
}

课程表

思路分析

数组中给出边的拓扑结构，查看该图是否存在拓扑序列

AC代码

Python

class Solution {
public:
    const static int N = 100010;
    int h[N], e[N], ne[N];
    int q[N];
    int d[N];
    int idx;
    int n;

    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    }

    bool top_sort(){
        int hh = 0, tt = -1;
        for(int i = 0; i < n; i ++){
            if(!d[i]){
                q[++ tt] = i;
            }
        }
        while(hh <= tt){
            int t = q[hh ++];
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(-- d[j] == 0){
                    q[++ tt] = j;
                }
            }
        }
        return tt == n - 1;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        n = numCourses;
        memset(h, -1, sizeof(h));
        for(auto pre : prerequisites){
            add(pre[0], pre[1]);
            d[pre[1]] ++;
        }
        return top_sort();
    }
};