2022-04-08 14:08:00

交叉编译

交叉编译一般是指在一个平台上生成另一个平台上的可执行代码，因为有一些目标平台性能很弱，编译需要花费很长的时间，所以需要在性能较高的平台上通过交叉编译来得到目标程序。
在golang和rust中交叉编译都是很容易实现的。

Golang

golang交叉编译一般不需要额外的工具，只需要在golang编译时指定GOOS（操作系统）和GOARCH（CPU架构）即可。
可以使用go tool dist list来查看所有支持的目标平台。
但是如果代码中使用了cgo，那么通常还需要指定一个CC（一般为gcc）来进行编译。
如果目标平台使用glibc库，可以快捷的使用xgo来进行交叉编译。
但是有些目标平台是使用的是musl库，或者是使用其他版本的C库，就需要手动安装交叉编译工具链了。

通过CC指定musl-gcc之后，编译出来的程序就可以在musl库的目标平台下运行了，但是其他版本的C库又不行了，这里要引入一个新的概念，叫做静态编译，即直接将用到的库链接到目标程序中，这样就不在依赖其他的库了。
二进制程序依赖的库可以通过ldd file查看。
在golang中，在ldflags中加入--extldflags '-static -fpic'参数即可开启静态编译，这时使用musl编译出来的二进制文件就可以在所有的目标平台运行了，无论使用的是什么C库。

为什么不直接使用glibc来进行静态编译呢？
直接使用glibc编译出来的二进制文件用ldd查看也是没有依赖的，但是在musl库系统下就是无法运行，我也不知道为什么。

Rust

rust有专门用于交叉编译的库：cross，使用cross build命令直接指定target他就可以工作了。

如果需要手动交叉编译，在rust中进行交叉编译通常比golang中多一步，需要使用rustup target add来添加目标target，同样的所有目标target都可以通过rustup target list来查看。
然后就是和golang一样需要一个gcc，但是有少数时候又不需要，例如在x86_64-unknown-linux-gnu上编译目标平台为x86_64-unknown-linux-musl的hello-world程序就不需要安装额外的musl-gcc，至于为什么这样，我也不知道。
另外Rust可能还需要在.cargo/config中添加一个[target.'x86_64-unknown-linux-gnu'.linker = "xxx"]来指定使用的gcc，编译时也需要加入--target host来指定目标平台。

网上很多文章说需要rustup toolchain install，其实是错误的（我认为）

交叉编译工具链下载

• musl: https://musl.cc/
• gnu: https://gnutoolchains.com/download/
• all: https://toolchains.bootlin.com/

参考

• https://github.com/japaric/rust-cross
• https://blog.hcl.moe/archives/2630

2022-03-23 14:08:00

Leetcode 440. 字典序的第K小数字

题目描述：

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例 1:

1
2
3

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:

1
2

输入: n = 1, k = 1
输出: 1

提示:

• 1 <= k <= n <= 109

思路

通过观察字典序的排列可以发现以下规律：

• 以i+1开头的字典序肯定大于以i开头的
• i*10 => 字典序+1
• i+1 => 字典序+(i+1作为前缀的最小值 - i作为前缀的最小值)

要找到在[1,n]中第k小的数字，我们肯定需要从以i作为前缀的开始数，首先需要计算出以i为前缀的个数，以i为前缀的个数即：以i+1为前缀的最小值-以i为前缀的最小值，且这些值都必须小于n。

找到以i为前缀的个数count后，有两种情况：

• k>count，说明以i为前缀的个数不够，还需要继续去找i+1的，k-=count，将i+1；
• k<=count，则说明第k小的数字就是以i开头的，那么通过将i*10将字典序+1，然后重复上面的步骤就可以找出第k小字典序的数字了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn find_kth_number(n: i32, k: i32) -> i32 {
        let (mut k, mut cur, n) = ((k - 1) as i64, 1 as i64, n as i64);
        while k > 0 {
            let (mut count, mut first, mut last) = (0, cur, cur + 1);
            while first <= n {
                count += last.min(n + 1) - first;
                first *= 10;
                last *= 10;
            }
            if count <= k {
                cur += 1;
                k -= count;
            } else {
                cur *= 10;
                k -= 1;
            }
        }
        cur as i32
    }
}

2022-03-22 14:08:00

Leetcode 2039. 网络空闲的时刻

题目描述：

给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。

题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。

编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。

在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：

• 如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器 i 每 patience[i] 秒都会重发一条信息，也就是说，数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。
• 否则，该数据服务器 不会重发 信息。

当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。

请返回计算机网络变为 空闲 状态的 最早秒数 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

输入：edges = [[0,1],[1,2]], patience = [0,2,1]
输出：8
解释：
0 秒最开始时，
- 数据服务器 1 给主服务器发出信息（用 1A 表示）。
- 数据服务器 2 给主服务器发出信息（用 2A 表示）。

1 秒时，
- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。

2 秒时，
- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
- 服务器 2 重发一条信息（用 2C 表示）。
...
4 秒时，
- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
...
7 秒时，回复信息 2D 到达服务器 2 。

从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
所以第 8 秒是网络变空闲的最早时刻。

示例 2：

1
2
3
4

输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出：3
解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始，网络变空闲。

提示：

• n == patience.length
• 2 <= n <= 105
• patience[0] == 0
• 对于 1 <= i < n ，满足 1 <= patience[i] <= 105
• 1 <= edges.length <= min(105, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= ui, vi < n
• ui != vi
• 不会有重边。
• 每个服务器都直接或间接与别的服务器相连。

思路

这里每个服务器最后变的空闲的时间都是相互独立的，所以我们算出每一个服务器接收最后一条消息的时间然后取最大的那一个就行了。

要计算这个的时间，首先肯定是需要计算每个服务器到服务器0的最短距离，这里刚开始使用的是迪杰斯特拉，但是提交之后超时了，然后观察到所有服务器的距离都是1，所以直接BFS就可以得到距离。

然后考虑怎么计算每个服务器的接受到最后一条消息的时间，接受最后一条消息的时间=发出最后一条消息的时间+2*服务器距离+1，所以最后需要计算的是最后一条消息发出的时间，如果距离$距离×2<=发送的间隔时间$的话，那么最后一条消息就是第一条消息，否则：

在停止发消息前，经历了$2×距离-1$的时间，再此期间则会发送$\Big\lfloor\dfrac{2 \times 距离- 1}{\textit{patience}[i]}\Big\rfloor$条消息，那么最后一条消息的时间就是：

$\Big\lfloor\dfrac{2 \times 距离- 1}{patience[i]}\Big\rfloor \times patience[i]$

代码

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

use std::collections::VecDeque;
impl Solution {
    pub fn network_becomes_idle(edges: Vec<Vec<i32>>, patience: Vec<i32>) -> i32 {
        let num_point = patience.len();
        let mut graph = vec![vec![]; num_point];
        edges.iter().for_each(|x| {
            graph[x[0] as usize].push(x[1] as usize);
            graph[x[1] as usize].push(x[0] as usize);
        });
        let mut distance = vec![num_point as i32; num_point];
        let mut visited = vec![false; num_point];
        visited[0] = true;
        distance[0] = 0;
        let mut queue = VecDeque::new();
        queue.push_back(0);
        while !queue.is_empty() {
            let cur = queue.pop_front().unwrap();
            graph[cur].iter().for_each(|&x| {
                if !visited[x] {
                    distance[x] = distance[cur] + 1;
                    visited[x] = true;
                    queue.push_back(x);
                }
            })
        }
        let mut ans = 0;
        for i in 1..num_point {
            ans = ans.max(2 * distance[i] + 1 + if distance[i] * 2 <= patience[i] {
                0
            } else {
                // 计算最后一次消息是什么时候发的
                (2 * distance[i] - 1) / patience[i] * patience[i]
            })
        }
        ans
    }
}

2022-03-20 14:08:00

问题

大部分的hexo主题自带的数学公式支持都是使用mathjax，但是这个插件的支持不是很好，有很多的公式无法正常显示。在网上搜索一番后，似乎是因为和markdown语法的冲突，发现很多人都推荐使用hexo-renderer-markdown-it-plus，它使用katex来支持数学公式的渲染但是安装之后又发现另一个问题，公式无法换行，在摸索了很长时间之后，最终发现是katex的版本的问题，然后找到了另一个渲染的库：@upupming/hexo-renderer-markdown-it-plus。现将使用的过程记录如下：

解决方法

首先需要替换默认的markdown渲染器：

1
2

npm un hexo-renderer-marked --save
npm i @upupming/hexo-renderer-markdown-it-plus --save

然后需要引入katex的样式文件，这里要注意官方的文档里用的还是0.9.0的老版本同样不支持换行，所以需要改成0.10.2的版本，这里使用字节的cdn：

1

<link href="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-1-M/KaTeX/0.10.2/katex.min.css" rel="stylesheet">

现在就可以随意的书写数学公式了，比如：

$S(x,y)=\left[l_N(x,y)\right]^{\alpha_N}\prod_{j=1}^{N}\left[c_j(x,y)\right]^{\beta_i}\left[l_N(x,y)\right]^{\gamma_j}$

拓展

这里可能还会有一个问题就是，如果公式很长但是屏幕又很窄，公式就有可能超出屏幕，让主题变得很难看，可以添加一个css来改进这个问题：

1
2
3
4

.katex-display {
  overflow-x: auto;
  overflow-y: clip;
}

2022-03-11 14:08:00

Leetcode 798. 得分最高的最小轮调

题目描述：

给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，这样可以使数组变为 [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]] 的形式。此后，任何值小于或等于其索引的项都可以记作一分。

• 例如，数组为 nums = [2,4,1,3,0]，我们按 k = 2 进行轮调后，它将变成 [1,3,0,2,4]。这将记为 3 分，因为 1 > 0 [不计分]、3 > 1 [不计分]、0 <= 2 [计 1 分]、2 <= 3 [计 1 分]，4 <= 4 [计 1 分]。

在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。如果有多个答案，返回满足条件的最小的下标 k 。

示例 1：

1
2
3
4
5
6
7
8
9
10

输入：nums = [2,3,1,4,0]
输出：3
解释：
下面列出了每个 k 的得分：
k = 0,  nums = [2,3,1,4,0],    score 2
k = 1,  nums = [3,1,4,0,2],    score 3
k = 2,  nums = [1,4,0,2,3],    score 3
k = 3,  nums = [4,0,2,3,1],    score 4
k = 4,  nums = [0,2,3,1,4],    score 3
所以我们应当选择 k = 3，得分最高。

示例 2：

1
2
3
4
5

输入：nums = [1,3,0,2,4]
输出：0
解释：
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k，即 0。

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] < nums.length

思路

首先的思路当然是暴力求解，直接遍历K在0到nums.length这个范围内的所有得分，然后取得分最高的k值（若有多个取较小的k）即可，这样写思路很清晰代码也是比较简单的，但是这道题目的数据量是$10^5$，这样做的时间复杂度是$O(N^2)$，肯定是会超时的，所以需要去优化。

首先我们将问题转化，先求出数组中每个值要取得得分时k的范围，假设下标为i，则需要：

$nums_i \leq (i-k+n)\%n \\0 \leq (i-k+n)\%n \leq n-1 \\\Downarrow \\k \leq (i-nums_i+n)\\%n \\k \leq (i+n)\%n \\k \geq (i+1)\%n$

最终得到k的范围为：

$k \in \left\{\begin{aligned}&\lbrack(i+1)\%n,(i-nums_i+n)\%n\rbrack && (i+1)\%n \leq (i-nums_i+n)\%n \\&\lbrack0,(i-nums_i+n)\%n\rbrack \cup \lbrack(i+1)\%n, n-1\rbrack && (i+1)\%n > (i-nums_i+n)\%n \\\end{aligned}\right.$

我们就可以在$O(n)$的时间内求得每项可以得分的k的区间，这样问题就转换为了求k取多少时落在这些区间里最多（k取较小值）？

然后我们可以这样来求解：先初始化一个长度为n，值为0的数组，然后对于上述的每个区间，将这个数组下标落在区间里的值加一，遍历完之后值最大的那个下标即为得分最高的k值。但是这样做的时间复杂度依然为$O(n^2)$，因为有n+个区间，每个区间的长度的数量级也为n，所以这里需要引入一个算法：差分数组

差分数组

差分数组就是专门对数组的某个区间进行相同的操作，且时间复杂度为$O(1)$的一个算法，他的本质其实是前缀和的逆操作。步骤如下：

首先求对应数组的差分数组：

$a_1,a_2,...a_{n-1},a_n \Rightarrow 0,a_2-a_1,a_3-a_2-a_1,...,a_n-a_{n-1}-a_{n-2}-...-a_1$

就本题来说初始的数组是$[0;n]$，那对应的差分数组仍为$[0;n]$；当我们需要对某个区间进行操作时只需要对端点处进行修改，如对$[a,b]$都+1则只需要

$nums_a+=1 \\ nums_{b+1}-=1$

即对左侧端点进行这个修改，对右侧的右边一个进行逆修改。

然后是差分数组如何还原，进行前缀和运算就行了，因为前缀和是对数组前i项的累加，对左侧端点的修改就影响了后面的所有值，而对右侧端点的右边一个逆修改相当于消除了对之后的影响，于是就变成了对$[a,b]$的操作，且这里所有的操作都是$O(1)$的。

然后使用这种算法再对上面的先初始化一个长度为n，值为0的数组，然后对于上述的每个区间，将这个数组下标落在区间里的值加一，遍历完之后值最大的那个下标即为得分最高的k值问题求解就很简单了。

代码

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

impl Solution {
    pub fn best_rotation(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut diff = vec![0; n+1];
        for i in 0..nums.len() {
            let left = (i+1)%n;
            let right = (i-(nums[i] as usize)+n)%n;
            diff[left]+=1;
            diff[right+1]-=1;
            if left > right {
                diff[0]+=1;
                diff[n]-=1;
            }
        }
        let mut ans = 0;
        let mut tmp = 0;
        let mut sum = 0;
        for k in 0..n {
            sum += diff[k];
            if sum > tmp {
                tmp = sum;
                ans = k;
            }
        }
        ans as i32
    }
}