第四范式 开发岗 笔试 09.15

第一题

一个长度为 N 的数组，若 a[i] > a[i-1]+a[i+1]，则认为 a[i] 为特殊节点。
0<i<N, a[i] <= 10^5
给定 K (< N)，你可以执行将任意的连续K个位置的值进行加一操作。
问，你可以执行任意次 or 不执行操作后，数组中特殊节点个数最多可能有多少个。

输入：
5 3
[1, 10, 1, 5, 1]
输出：
2

无论怎么操作，最多只有2个特殊节点。
不操作
[1, 10, 1, 5, 1], 特殊 = 2
a[0]-a[3] 进行加一
[2, 11, 2, 5, 1], 特殊 = 2

这个题算是脑筋急转弯题目，若 K 不为 1，那么不操作的结果是最佳的。
对于 a1,a2,a3，若 a2<=a1+a3，是无法让 a2 变成特殊节点的。
K = 2时，有增加 [a0, a1], [a1, a2], [a2, a3] [a3, a4] 四种情况。无论哪种情况或哪几种情况都无法使得 a2 > a1+a3. K >= 3 同理.
所以，若 K != 1，那么无论如何是不能增加特殊节点个数的。相反，可能还减少个数，如 [1, 4, 2] 变成 [2, 5, 3] 就没有特殊节点了。
若 K = 1, 那么造山峰了，a[0], 2^31, a[2], 2^31, a[3], 2^31,.... , a[n-1]. 结果是 (n-1)/2。

public static void main1(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for(int i = 0; i < n; i++){
        int num = sc.nextInt();
        int k = sc.nextInt();
        int arr[] = new int[num];
        for(int j = 0; j < num; j++){
            arr[j] = sc.nextInt();
        }
        func(num, arr, k);
    }
}

public static void func(int n, int arr[], int k){
    if(k == 1){
        System.out.println((n-1)/2);
        return;
    }else{
        int ret = 0;
        for(int i = 1; i < n-1; i++){
            if(arr[i] > arr[i-1]+arr[i+1]){
                ret++;
            }
        }
        System.out.println(ret);
        return;
    }
}

第二题

一个 N * M 的矩阵，arr[i][j] 为 '.' 或者 '*'。
要求打印一个矩阵 retArr

• 若 arr[i][j] = '.'，则 retArr[i][j] = '.'
• 若 arr[i][j] = '*'，则 retArr[i][j] = 将其暂时修改为 '.' 后，直接或间接相邻的 '.' 个数（包括自己），最终数目对 10 进行取余。

就是 arr[i][j] = '.' 代表路；arr[i][j] = '*' 代表墙。
问让某个墙暂时变成路后，直接或间接相邻的路的个数。

输入：
4 5
**..*
..***
.*.*.
*.*.*

输出：
46..3
..732
.6.4.
5.4.3

解释：
例如，左上角的位置，将其暂时更改为 '.' 后，矩阵如下
此时[0][0]位置直接或间接(含自己)有4个'.'
.*..*
..***
.*.*.
*.*.*

这个题看着简单，但是要考虑相邻的四个点可能属于同一个连通区域中，例如 retArr[2][1]=6 的位置。
所以就是一个DFS/BFS+并查集的应用。
DFS/BFS 计算相邻的个数，并查集判断上下左右是否在一个连通区域中。

static int n, m;
static boolean vis[][];  // DFS 判断是否访问过
static int father[][];  // i，j对应的并查集 ID
static int fathercnt;   // 并查集 ID，从0开始
static char cs[][];    // 输入矩阵
static List<Integer> cntList;  // 存储每一个集合对应的个数
public static void main2(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    vis = new boolean[n][m];
    father = new int[n][m];
    fathercnt = 0;
    cntList = new ArrayList<>();

    cs = new char[n][m];
    for(int i = 0; i < n; i++){
        cs[i] = sc.next().toCharArray();
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            // 对于每个未访问过的 '.'，记录当前节点的可行的相邻区域
            if(cs[i][j] == '.' && !vis[i][j]){
                // dfs 获得当前节点相邻区域的大小
                // cntList 存储当前并查集ID对应的区域大小
                cntList.add(dfs(i, j));  
                // 更新并查集ID
                fathercnt++;
            }
        }
    }
    // 打印工作
    for(int i = 0; i < n; i++){
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < m; j++){
            if(cs[i][j] == '.'){
                sb.append('.');
            }else{
                int cnt = 1; // 当前是路
                // 并查集 ID 去重
                Set<Integer> set = new HashSet<>(4);
                for(int t = 0; t < 4; t++){
                    int tx = i + direct[t][0];
                    int ty = j + direct[t][1];
                    if(tx >= 0 && ty >= 0 && tx < n && ty < m && cs[tx][ty] == '.') {
                        set.add(father[tx][ty]);
                    }
                }
                // 去重后，每个集合 ID 对应的数目
                for(int tmp: set){
                    cnt += cntList.get(tmp);
                }
                cnt = cnt % 10;
                sb.append(cnt);
            }
        }
        System.out.println(sb.toString());
    }
}

static int direct[][] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
public static int dfs(int x, int y) {
    vis[x][y] = true;
    // 设置当前 x,y 对应的集合 ID
    father[x][y] = fathercnt;
    int ret = 1;
    for(int i = 0; i < 4; i++){
        int tx = x + direct[i][0];
        int ty = y + direct[i][1];
        if(tx >= 0 && ty >= 0 && tx < n && ty < m && !vis[tx][ty] && cs[tx][ty] == '.') {
            ret += dfs(tx, ty);
        }
    }
    return ret;
}