网站首页 > 文章精选 正文
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整数 k。
任务是计算从左上角起点 (0, 0) 出发,到右下角终点 (m-1, n-1) 的所有路径数量,这些路径必须满足以下条件:
- o 每一步只能向右或向下移动(即从 (i, j) 到 (i, j+1) 或 (i+1, j))。
- o 路径上经过的所有数字进行异或(XOR)运算后的结果等于 k。
由于结果可能很大,需要将最终路径数对 1000000007 取模后返回。
1 <= m == grid.length <= 300。
1 <= n == grid[r].length <= 300。
0 <= grid[r][c] < 16。
0 <= k < 16。
输入:grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11。
输出:3。
解释:
3 条路径分别为:
(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2)。
(0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)。
(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)。
题目来自力扣3393。
解决思路
这是一个典型的动态规划问题。我们需要跟踪从起点到每个单元格的所有可能的异或值及其对应的路径数量。
关键点:
- 1. 异或运算的性质:异或运算是可逆的,且顺序不影响最终结果。即 a XOR b XOR c = a XOR (b XOR c)。
- 2. 动态规划状态定义:我们可以定义 f[i][j][x] 表示从起点 (0, 0) 到 (i, j) 的所有路径中,异或结果为 x 的路径数量。
- 3. 状态转移:对于每个单元格 (i, j),其异或值 x 可以通过从上方 (i-1, j) 或左方 (i, j-1) 的单元格转移而来:
- o 如果从上方来,则 x = x_above XOR grid[i][j]。
- o 如果从左方来,则 x = x_left XOR grid[i][j]。
- o 因此,f[i][j][x] = f[i-1][j][x XOR grid[i][j]] + f[i][j-1][x XOR grid[i][j]]。
- 4. 初始条件:起点的异或值是 grid[0][0],因此 f[0][0][grid[0][0]] = 1。
具体步骤:
- 1. 确定异或值的上限:
- o 网格中的最大值决定了异或结果的最大可能值。因为 0 <= grid[r][c] < 16,所以异或结果的最大值是 15(二进制 1111),因此异或值的范围是 0 到 15。
- o 代码中通过 bits.Len(uint(mx)) 计算最大值的二进制位数,然后 1 << bits.Len(uint(mx)) 得到上限 u。由于 mx 最大是 15,u 是 16。
- o 如果 k >= u,直接返回 0,因为异或结果不可能大于等于 u。
- 2. 初始化动态规划表:
- o 创建一个三维数组 f,大小为 (m+1) x (n+1) x u,初始化为 0。
- o 为了方便边界处理,代码中从 (1, 1) 开始对应网格的 (0, 0),因此 f[0][1][0] = 1 或 f[1][0][0] = 1 是初始条件。这相当于从虚拟的起点出发,异或值为 0。
- 3. 填充动态规划表:
- o 遍历网格的每个单元格 (i, j)。
- o 对于每个可能的异或值 x(从 0 到 u-1),计算从上方和左方转移来的路径数量:
- o f[i+1][j+1][x] = (f[i+1][j][x XOR val] + f[i][j+1][x XOR val]) % mod,其中 val = grid[i][j]。
- o 这样,f[i+1][j+1][x] 表示到 (i, j) 时异或值为 x 的路径数量。
- 4. 返回结果:
- o 最终结果是 f[m][n][k],即从 (0, 0) 到 (m-1, n-1) 异或值为 k 的路径数量。
时间复杂度和空间复杂度
- o 时间复杂度:
- o 我们需要遍历每个单元格 (i, j),共 m x n 个。
- o 对于每个单元格,我们需要遍历所有可能的异或值 x,最多 16 种。
- o 因此,时间复杂度是 O(m * n * 16),即 O(m * n),因为 16 是常数。
- o 空间复杂度:
- o 动态规划表 f 的大小是 (m+1) x (n+1) x 16。
- o 因此,空间复杂度是 O(m * n * 16),即 O(m * n)。
总结
通过动态规划方法,我们高效地统计了满足条件的路径数量。时间和空间复杂度都是网格大小的线性倍数(乘以常数 16),适用于给定的约束条件(m, n <= 300)。
Go完整代码如下:
.
package main
import (
"fmt"
"slices"
"math/bits"
)
func countPathsWithXorValue(grid [][]int, k int)int {
const mod = 1_000_000_007
mx := 0
for _, row := range grid {
mx = max(mx, slices.Max(row))
}
u := 1 << bits.Len(uint(mx))
if k >= u {
return0
}
m, n := len(grid), len(grid[0])
f := make([][][]int, m+1)
for i := range f {
f[i] = make([][]int, n+1)
for j := range f[i] {
f[i][j] = make([]int, u)
}
}
f[0][1][0] = 1
for i, row := range grid {
for j, val := range row {
for x := range u {
f[i+1][j+1][x] = (f[i+1][j][x^val] + f[i][j+1][x^val]) % mod
}
}
}
return f[m][n][k]
}
func main() {
grid := [][]int{{2, 1, 5}, {7, 10, 0}, {12, 6, 4}}
k := 11
result := countPathsWithXorValue(grid,k)
fmt.Println(result)
}
Python完整代码如下:
.
# -*-coding:utf-8-*-
import math
def countPathsWithXorValue(grid, k):
mod = 1_000_000_007
mx = 0
for row in grid:
mx = max(mx, max(row))
u = 1 << (mx.bit_length())
if k >= u:
return0
m, n = len(grid), len(grid[0])
# 初始化三维dp数组 f[m+1][n+1][u]
f = [[[0] * u for _ in range(n+1)] for __ in range(m+1)]
f[0][1][0] = 1
for i in range(m):
for j in range(n):
val = grid[i][j]
for x in range(u):
# 从左边(f[i+1][j])和上边(f[i][j+1])转移
f[i+1][j+1][x] = (f[i+1][j][x ^ val] + f[i][j+1][x ^ val]) % mod
return f[m][n][k]
if __name__ == "__main__":
grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]]
k = 11
result = countPathsWithXorValue(grid, k)
print(result)
·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”,并致力于分享全面的编程知识。在这里,您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大规模架构师每日一题”,让 Go 语言和算法助力您的职业发展
·
猜你喜欢
- 2025-07-14 Go并发编程之WaitGroup(go语言 并发)
- 2025-07-14 golang企业微信告警(企业微信告警推送)
- 2025-07-14 2.8 Go语言中的for循环,break和continue
- 2025-07-14 Go语言Context包:最常用包之一的使用指南
- 2025-07-14 Go语言零到一:动态数组——切片(go语言的切片)
- 2025-07-14 2025-06-26:转换数组。用go语言,给你一个整数数组 nums,它被视
- 2025-07-14 go sync.Pool简介(go system)
- 2025-07-14 2025-07-13:统计特殊子序列的数目。用go语言,给定一个只包含正
- 2025-07-14 Go语言数据库编程:GORM 的基本使用
- 2025-07-14 2025-06-28:长度可被 K 整除的子数组的最大元素和。用go语言,给
- 最近发表
- 标签列表
-
- newcoder (56)
- 字符串的长度是指 (45)
- drawcontours()参数说明 (60)
- unsignedshortint (59)
- postman并发请求 (47)
- python列表删除 (50)
- 左程云什么水平 (56)
- 编程题 (64)
- postgresql默认端口 (66)
- 数据库的概念模型独立于 (48)
- 产生系统死锁的原因可能是由于 (51)
- 数据库中只存放视图的 (62)
- 在vi中退出不保存的命令是 (53)
- 哪个命令可以将普通用户转换成超级用户 (49)
- noscript标签的作用 (48)
- 联合利华网申 (49)
- swagger和postman (46)
- 结构化程序设计主要强调 (53)
- 172.1 (57)
- apipostwebsocket (47)
- 唯品会后台 (61)
- 简历助手 (56)
- offshow (61)
- mysql数据库面试题 (57)
- fmt.println (52)