ARST打卡第292周

2024-12-07 1333 words 3 minutes

Contents

lc688_骑士在棋盘上的概率社交秘诀_我们如何彼此尊重，还能提出不同意见？【TED演讲】 Solana Developer Bootcamp 2024 - Learn Blockchain and Full Stack Web3 Development vscode访问被ban的节点

Algorithm

lc688_骑士在棋盘上的概率

思路:

这个明显复杂度就是 O(8^k) , k 次 8种选择，也就是 O(2^{3*k}) , 但是这样对 k [0,100] 复杂度就太高了，所以明显还要在 n [1,25] 方面进行优化。

根据题意，马只要走出过棋盘一次，就算走出去了，所以只能模拟所有不走出去的可能概率。

所以就是 dfs 递归计算每次不走出的概率的乘积的和，这样可以一直把 k 降到 0.

但是中途必须递归记忆剪枝减少重复状态。

因为后续都是cursor辅助编程的时代，所以自己这里也用了cursor辅助

 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
41
42
43
44
45
46
47
48
49


impl Solution {
    pub fn knight_probability(n: i32, k: i32, row: i32, column: i32) -> f64 {
        let n = n as usize;
        let k = k as usize;
        let row = row as usize;
        let column = column as usize;
        
        // 8个方向的偏移量
        let dirs = [
            (-2,-1),(-2,1),(-1,-2),(-1,2),
            (1,-2),(1,2),(2,-1),(2,1)
        ];
        
        // dp[step][i][j] 表示从(i,j)出发,走step步不出界的概率
        let mut dp = vec![vec![vec![-1.0; n]; n]; k+1];
        
        fn dfs(step: usize, i: usize, j: usize, n: usize, 
            dp: &mut Vec<Vec<Vec<f64>>>, 
            dirs: &[(i32,i32)]) -> f64 {
            
            // 如果已经走完k步,返回1.0表示这条路径有效
            if step == 0 {
                return 1.0;
            }
            
            // 如果这个状态计算过,直接返回
            if dp[step][i][j] != -1.0 {
                return dp[step][i][j];
            }
            
            let mut prob = 0.0;
            // 遍历8个方向
            for &(di,dj) in dirs {
                let ni = i as i32 + di;
                let nj = j as i32 + dj;
                
                // 如果下一步在棋盘内,递归计算概率
                if ni >= 0 && ni < n as i32 && nj >= 0 && nj < n as i32 {
                    prob += dfs(step-1, ni as usize, nj as usize, n, dp, dirs) / 8.0;
                }
            }
            
            dp[step][i][j] = prob;
            prob
        }
        
        dfs(k, row, column, n, &mut dp, &dirs)
    }
}

时间复杂度分析:

对于这个 DFS + 记忆化搜索的解法：

状态数量：

总共有 k+1 步
每一步可以在 n×n 的棋盘上的任意位置
所以总状态数为 O(k×n×n)

每个状态的计算：

每个状态需要遍历8个方向
每个方向的计算是 O(1)
所以每个状态的计算复杂度是 O(8) = O(1)

总时间复杂度：

O(k×n×n)

空间复杂度分析:

DP数组：

三维数组 dp[k+1][n][n]
空间复杂度 O(k×n×n)

递归栈深度：

最大递归深度为 k
空间复杂度 O(k)

因此总空间复杂度为 O(k×n×n)

这个解法通过记忆化搜索很好地优化了原始的指数级复杂度 O(8^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
28
29


const DIRS: [[i32; 2]; 8] = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2]];

impl Solution {
    pub fn knight_probability(n: i32, k: i32, row: i32, column: i32) -> f64 {
        let n = n as usize;
        let k = k as usize;
        let mut dp = vec![vec![vec![0.0; n]; n]; k + 1];

        for step in 0..= k {
            for i in 0..n {
                for j in 0..n {
                    if step == 0 {
                        dp[step][i][j] = 1.0;
                    } else {
                        for dir in &DIRS {
                            let ni = i as i32 + dir[0];
                            let nj = j as i32 + dir[1];
                            if ni >= 0 && ni < n as i32 && nj >= 0 && nj < n as i32 {
                                dp[step][i][j] += dp[step - 1][ni as usize][nj as usize] / 8.0;
                            }
                        }
                    }
                }
            }
        }

        dp[k][row as usize][column as usize]
    }
}

Review

社交秘诀：我们如何彼此尊重，还能提出不同意见？【TED演讲】

分享者说人人都有论点求胜心，可能引发相互不尊重，那么如果能彼此尊重的情况下还能提出不同意见:

提醒和他人的共同点
宽恕他人，因为宽恕他人虽然很难，但是其实宽恕他人就是宽恕自己，只有自己放下了，那么别人才无法一直占据你的大脑和时间，消耗你的精力

Tips

Solana Developer Bootcamp 2024 - Learn Blockchain and Full Stack Web3 Development

手把手教学，非常好的教程。

vscode访问被ban的节点

一开始思路是想着给 vscode 加独立代理，后面发现可以直接:

代理工具开启tun模式。
设置被ban的节点的域名/ip地址为代理。

这样就可以愉快轻松地用 vscode 访问被ban的节点上的 remote-ssh 了。

Contents

ARST打卡第292周

Algorithm

Review

Tips

Share