发表更新课程 / NJU ICS/OS7 分钟读完 (大约1004个字)

南京大学 计算机系统基础 课程实验 2022

实验网站，2020 南京大学计算机系统基础习题课。

PA0 - 世界诞生的前夜: 开发环境配置

使用 vimtutor 命令启动 vim 教程。

教程：GNU/Linux，Makefile，GDB，tmux，Git，Linux C编程一站式学习。

课程：The Missing Semester of Your CS Education。

其他：Visualizing Git Concepts with D3。

使用 apt-get install 经常遇到 “The following packages have unmet dependencies” 错误，原因是因为依赖的包和现有的包版本冲突，之前我都是手动 apt-get remove，但是经常遇到该问题。STFW 之后，这里推荐的 aptitude 工具比较方便，发生冲突时会询问是否降级。（apt-get，aptitude，apt 的区别，是否有必要使用 aptitude？讨论。）

使用 make 经常遇到 “No such file or directory” 之类缺失头文件的错误，目前是遇到两种情况。一种是缺失对应的包，直接 apt-get install 即可解决；另一种是有对应的包，但是当前项目中 .mk 文件配置的程序名称和现有名称不一致（例如，配置的是 llvm-config，而现有的是 llvm-config-11），修改 .mk 文件即可解决。

PA1 - 开天辟地的篇章: 最简单的计算机

手册：riscv-isa-manual，riscv-elf-psabi-doc，etc，NEMU ISA API。

可以在目标命令之前添加 time 命令，从而计算目标命令的执行时间。使用 make 命令的 -j 选项，可以启用多线程编译。make -j4 表示创建 4 个线程并行编译，具体创建多少个线程，可以根据 lscpu 命令查询得到的系统中的 CPU 数量来确定。使用 ccache 工具可以缓存目标文件，从而加速执行 make clean 之后，再次执行 make 的速度。

如何实现宏 IFDEF 和 MUXDEF。其中 IFDEF 表示，如果定义了 CONFIG_DEVICE 宏，才会调用 init_device() 函数。而 MUXDEF 表示，如果定义了 CONFIG_TRACE 宏，则预处理结果为 ON，否则预处理结果为 OFF。

1
2
IFDEF(CONFIG_DEVICE, init_device());
MUXDEF(CONFIG_TRACE, "ON", "OFF")

在 nemu/include/macro.h 文件中有如下定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// macro concatenation
#define concat_temp(x, y) x ## y
#define concat(x, y) concat_temp(x, y)

// macro testing
// See https://stackoverflow.com/questions/26099745/test-if-preprocessor-symbol-is-defined-inside-macro
#define CHOOSE2nd(a, b, ...) b
#define MUX_WITH_COMMA(contain_comma, a, b) CHOOSE2nd(contain_comma a, b)
#define MUX_MACRO_PROPERTY(p, macro, a, b) MUX_WITH_COMMA(concat(p, macro), a, b)

// define placeholders for some property
#define __P_DEF_0  X,
#define __P_DEF_1  X,

// define some selection functions based on the properties of BOOLEAN macro
#define MUXDEF(macro, X, Y)  MUX_MACRO_PROPERTY(__P_DEF_, macro, X, Y)

// simplification for conditional compilation
#define __IGNORE(...)
#define __KEEP(...) __VA_ARGS__

// keep the code if a boolean macro is defined
#define IFDEF(macro, ...) MUXDEF(macro, __KEEP, __IGNORE)(__VA_ARGS__)

我们可以使用如下代码进行测试，同时给出宏展开的步骤。需要注意的是，只有当 CONFIG_DEVICE 被定义为 0 或 1 时，才会执行函数调用。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

#define CONFIG_DEVICE 1

void init_device() {
    printf("Hello, Linux World!\n");
}

int main(void) {
    IFDEF(CONFIG_DEVICE, init_device());
    return 0;
}
1
2
3
4
5
6
7
8
9
10
IFDEF(CONFIG_DEVICE, init_device());
IFDEF(1, init_device());
MUXDEF(1, __KEEP, __IGNORE)(init_device());
MUX_MACRO_PROPERTY(__P_DEF_, 1, __KEEP, __IGNORE)(init_device());
MUX_WITH_COMMA(concat(__P_DEF_, 1), __KEEP, __IGNORE)(init_device());
MUX_WITH_COMMA(__P_DEF_1, __KEEP, __IGNORE)(init_device());
MUX_WITH_COMMA(X,, __KEEP, __IGNORE)(init_device());
CHOOSE2nd(X, __KEEP, __IGNORE)(init_device());
__KEEP(init_device());
init_device();
发表更新算法 / LeetCode3 分钟读完 (大约486个字)

第 130 场力扣夜喵双周赛（VP）

正方形中的最多点数

题目

输入长度为 \(n\) 的二维数组 \(points\) 和字符串 \(s\)，\(points[i]\) 表示第 \(i\) 个点的坐标，\(s[i]\) 表示第 \(i\) 个点的标签。如果以 \((0,0)\) 为中心且边平行于坐标轴的正方形内（包括边上的点，且边长可以为 \(0\)），不包含标签相同的两个点，则该正方形是合法的。输出合法正方形可以包含的最多点数。其中 \(points\) 中的点互不相同，\(s\) 只包含小写英文字母。

数据范围：\(1\leq n\leq 10^{5}\)，\(-10^{9}\leq points[i][0],points[i][1]\leq 10^{9}\)。

思路

首先可以想到，正方形的边长越长，包含的点就越多，越可能不合法。具有单调性，可以使用二分求解。在二分的过程中，判断正方形是否合法，如果合法则更新答案。时间复杂度为 \(O(n\log{U})\)，其中 \(U=\max_{i=0}^{n-1}(|x_{i}|,|y_{i}|)\)。更好的做法是观察到，如果正方形包含某个点 \((x,y)\)，则正方形的边长 \(len\) 必须满足 \(len\geq 2\times\max(|x|,|y|)\)。其中，\(\max(|x|,|y|)\) 是点 \((x,y)\) 到点 \((0,0)\) 的切比雪夫距离。实际上，我们只需要维护每种标签点的最小切比雪夫距离 \(min_{i}\)，以及除此之外所有点的最小切比雪夫距离 \(k\)。因为，如果正方形包含某个标签 \(i\)，必定是包含具有该标签的切比雪夫距离最小的那个点，而这个点需要满足 \(min_{i}<k\)。详情见代码，时间复杂度为 \(O(n)\)。优化思路参考灵神题解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        int n = points.length;
        int[] min = new int[26];
        Arrays.fill(min, Integer.MAX_VALUE);

        int k = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            int z = Math.max(Math.abs(x), Math.abs(y));
            int c = s.charAt(i) - 'a';
            if (z < min[c]) {
                k = Math.min(k, min[c]);
                min[c] = z;
            } else {
                k = Math.min(k, z);
            }
        }

        int ans = 0;
        for (int x : min) {
            if (x < k) {
                ans++;
            }
        }
        return ans;
    }
}

分割字符频率相等的最少子字符串

题目

输入长度为 \(n\) 的字符串 \(s\)（只包含小写英文字母），输出 \(s\) 最少能被分割为多少个平衡子字符串。平衡字符串就是字符串中不同字符出现频次都相同的字符串。

数据范围：\(1\leq n\leq 1000\)。

思路

定义 \(dp[i+1]\) 表示字符串 \([0,i]\) 最少能被分割的平衡子字符串数目，则转移方程为 \(dp[i+1]=\min(dp[j]+1)\)，其中 \(0\leq j\leq i\) 且字符串 \([j,i]\) 必须是平衡字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            dp[i + 1] = i + 1;
            int k = 0, max = 0;
            int[] cnt = new int[26];
            for (int j = i; j >= 0; j--) {
                k += cnt[s.charAt(j) - 'a'] == 0 ? 1 : 0;
                max = Math.max(max, ++cnt[s.charAt(j) - 'a']);
                if (i - j + 1 == k * max) {
                    dp[i + 1] = Math.min(dp[i + 1], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
}

大数组元素的乘积

不会。

发表更新算法 / LeetCode6 分钟读完 (大约857个字)

第 397 场力扣周赛

矩阵中的最大得分

题目

输入一个 \(m\times n\) 的矩阵 \(grid\)，输出选择任意单元格作为起点，至少移动一次能够得到的最大得分。每次移动只能向正右方和正下方的单元格移动，不必相邻。假设从单元格 \((x_{1},y_{1})\) 移动到 \((x_{2},y_{2})\)，则本次移动的得分为 \(grid[x_{2}][y_{2}]-grid[x_{1}][y_{1}]\)。

数据范围：\(2\leq m,n\leq 1000\)，\(4\leq m\times n\leq 10^{5}\)，\(1\leq grid[i][j]\le 10^{5}\)。

思路

比赛时想到计算过程存在重叠子问题，可以使用记忆化搜索。定义 \(f[i][j]\) 表示以 \((i,j)\) 为起点能够得到的最大得分，初始化 \(f[i][j]\) 为负无穷。当 \(i<m-1\) 且 \(j<n-1\) 时，状态转移方程为 \(f[i][j]=\max{(f[i+1][j]+grid[i+1][j]-grid[i][j],f[i][j+1])+grid[i][j+1]-grid[i][j]}\)。也可以将记忆化搜索转化为自底向上的形式，或者定义 \(f[i][j]\) 表示以 \((i,j)\) 为终点能够得到的最大得分。

通过观察可以发现，对于某个移动路径，得分只和起点和终点有关，中间的值都被抵消了。也就是说，某个起点能够得到的最大得分，是其右下角的最大值减去起点的值，反之亦然。所以也可以定义 \(f[i][j]\) 表示 \((i,j)\) 右下角的最大值或者左上角的最小值，然后进行递推。

时间复杂度为 \(O(mn)\)，空间复杂度为 \(O(mn)\)。灵神题解有个空间复杂度为 \(O(n)\) 的做法，思路是维护每列的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size(), n = grid.get(0).size();
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        dfs(0, 0, grid, dp);
        
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
    
    private int dfs(int x, int y, List<List<Integer>> grid, int[][] dp) {
        int m = grid.size(), n = grid.get(0).size();
        if (dp[x][y] == Integer.MIN_VALUE) {
            if (x + 1 < m) {
                int diff = grid.get(x + 1).get(y) - grid.get(x).get(y);
                dp[x][y] = Math.max(dp[x][y], diff + dfs(x + 1, y, grid, dp));
            }
            if (y + 1 < n) {
                int diff = grid.get(x).get(y + 1) - grid.get(x).get(y);
                dp[x][y] = Math.max(dp[x][y], diff + dfs(x, y + 1, grid, dp));
            }
        }
        return Math.max(0, dp[x][y]);
    }
}

找出分数最低的排列

题目

输入从 \(0\) 到 \(n-1\) 的一个排列 \(nums\)，输出从 \(0\) 到 \(n-1\) 的排列 \(perm\)，使得 \(score(perm)=\sum_{i=0}^{n-1}{|perm[i]-nums[perm[(i+1)\bmod n|}\) 的值最小。如果有多个满足条件的排列，则返回字典序最小的那个。

数据范围：\(2\leq n\leq 14\)。

思路

通过观察可以发现，对于一个给定的排列 \(perm\)，将其循环移动不会改变 \(score(perm)\) 的值。要使满足条件的 \(perm\) 字典序最小，那么必然有 \(perm[0]=0\)。暴力的想法是枚举所有排列，但是时间复杂度为 \(n!\times n\)。由于枚举过程中，存在重复子问题，可以使用记忆化搜索来降低时间复杂度到 \(O(2^{n}n^{2})\)。定义 \(f[mask][pre]\) 表示已经选择集合 \(mask\) 中的数，上一个选择的数是 \(pre\)，剩余的数排列能够得到的最小分数。同理，定义 \(g[mask][pre]\) 表示下一个选择什么数能够使得分数最小，以及相同分数的排列字典序最小。可以看下灵神题解，不使用记忆化搜索，自底向上的解法也是非常经典的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int[] findPermutation(int[] nums) {
        int n = nums.length;
        int[][] f = new int[1 << n][n];
        int[][] g = new int[1 << n][n];
        for (int i = 0; i < (1 << n) - 1; i++) {
            Arrays.fill(f[i], -1);
        }
        for (int i = 0; i < n; i++) {
            f[(1 << n) - 1][i] = Math.abs(i - nums[0]);
        }
        dfs(1, 0, nums, f, g);

        int[] ans = new int[n];
        for (int i = 0, mask = 0, cur = 0; i < n; i++) {
            ans[i] = cur;
            mask |= 1 << cur;
            cur = g[mask][cur];
        }
        return ans;
    }

    private int dfs(int mask, int pre, int[] nums, int[][] f, int[][] g) {
        int n = nums.length;
        if (mask == (1 << n) - 1 || f[mask][pre] != -1) {
            return f[mask][pre];
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if ((mask >> i & 1) == 0) {
                int cur = dfs(mask | 1 << i, i, nums, f, g) + Math.abs(pre - nums[i]);
                if (cur < res) {
                    res = cur;
                    g[mask][pre] = i;
                }
            }
        }
        return f[mask][pre] = res;
    }
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×