博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
1706 - 球会落何处 - 并查集 - 动态规划
阅读量:719 次
发布时间:2019-03-21

本文共 5436 字,大约阅读时间需要 18 分钟。

关注我,学习常用算法与数据结构,一题多解,降维打击。

文章目录

题目描述

[1706]

  • https://leetcode-cn.com/problems/where-will-the-ball-fall/

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将球导向左侧或者右侧。

将球导向右侧的挡板跨过左上角和右下角,在网格中用 1 表示。

将球导向左侧的挡板跨过右上角和左下角,在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 “V” 形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。

返回一个大小为 n 的数组 answer ,其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标,如果球卡在盒子里,则返回 -1 。

示例 1:

在这里插入图片描述

输入:grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]

输出:[1,-1,-1,-1,-1]
解释:示例如图:
b0 球开始放在第 0 列上,最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上,会卡在第 2、3 列和第 1 行之间的 “V” 形里。
b2 球开始放在第 2 列上,会卡在第 2、3 列和第 0 行之间的 “V” 形里。
b3 球开始放在第 3 列上,会卡在第 2、3 列和第 0 行之间的 “V” 形里。
b4 球开始放在第 4 列上,会卡在第 2、3 列和第 1 行之间的 “V” 形里。
示例 2:

输入:grid = [[-1]]

输出:[-1]
解释:球被卡在箱子左侧边上。

提示:

m == grid.length

n == grid[i].length
1 <= m, n <= 100
grid[i][j] 为 1 或 -1

Related Topics
  • 图论
  • 并查集
  • DFS
  • 动态规划

题目剖析&信息挖掘

此题为图论题,考查对于图论模型建模的能力。

转化到图论模型后,可以用并查集解决。
也可以用DFS, 加上记忆化搜索,其实就是动态规划。

解题思路

在这里插入图片描述

此题的关键是如何将矩阵中的格子关系用图论的方法表示出来。

观察例子可以发现,一个小球只会停在格子的上半分部,一个球在一个格子里有2种状态。

要不挡板朝开口左,要不朝右。

在这里插入图片描述

在这里插入图片描述

设当前小球在row, col

当开口朝左时,我们要判断左边格子的开口朝向,如果相同则可以滚到row+1, col+1(与朝向相同,可以优化)说明(row, col) 和(row+1, col+1)是连通的。

当开口朝右也是同理。

如果开口不同向,就是卡住了。

有了以上基础就建立了图模型。

方法一 并查集

还不会,赶紧来学习吧

解析

由于题目说小球要滚出箱子才算出去,那我们先在箱子下面增加一行。

在这里插入图片描述

有了上面的力模型,我们的问题就变成第0排的格子与最后一排第n排中的某个格子相连通。

并查集是点与点的关系,要把每个格子看作一个点,对其进行编号像图一样(可以把二维的数组看成是一维的),其公式为row*m+col。

思路

/*并查集,判连通用*/type UnionFindSet struct {
father []int // 存储结点的父亲 height []int // 存储结点的父亲 nodeNum int // 总结点个数}func (us *UnionFindSet) InitUnionSet(n int) {
}// 查询父结点func (us *UnionFindSet) Find(x int) int {
}//合并结点func (us *UnionFindSet) Union(x, y int) bool {
}//编号公式func getIndexByRowAndColumn(row, col, m int) int {
}func findBall(grid [][]int) []int {
n, m := len(grid), len(grid[0]) us := &UnionFindSet{
} us.InitUnionSet((n + 2) * m) for i, row := range grid {
for j, v := range row {
// 判断是否出界 // 判断是否有开口 us.Union(getIndexByRowAndColumn(i, j, m), getIndexByRowAndColumn(i+1, j+v, m)) } } ans := make([]int, m) // 一重循环,对合并是有要求的。具体看代码 for i, _ := range ans {
buttomIndex := us.FindV2(getIndexByRowAndColumn(0, i, m)) if buttomIndex/m == n {
// 如果是最后一行,就是有答案 ans[i]=buttomIndex%m } else {
// 没答案 ans[i]=-1 } } return ans}

注意

  • 查看左右时,一定要先判断边界
  • 合并时要把大的编号作为父亲结点,不用的话,最后一步要用2重循环,总体的复杂度还是m*n。影响是不大。

知识点

  • 矩阵转数组
  • 并查集
  • 数组

复杂度

  • 时间复杂度:O(n*m)
  • 空间复杂度:O(n*m)

参考

代码实现

/*并查集,判连通用*/type UnionFindSet struct {
father []int // 存储结点的父亲 nodeNum int // 总结点个数}func (us *UnionFindSet) InitUnionSet(n int) {
us.nodeNum = n + 1 // 不加也可以,有人喜欢以0开头 us.father = make([]int, us.nodeNum) for i, _ := range us.father {
us.father[i] = i }}func (us *UnionFindSet) FindV2(x int) int {
root := x // 保存好路径上的头结点 for us.father[root] != root {
root = us.father[root] } /* 从头结点开始一直往根上遍历 把所有结点的father直接指向root。 */ for us.father[x] != x {
// 一定要先保存好下一个结点,下一步是要对us.father[x]进行赋值 temp := us.father[x] us.father[x] = root x = temp } return root}//合并结点func (us *UnionFindSet) UnionV2(x, y int) bool {
x = us.FindV2(x) y = us.FindV2(y) if x == y {
return false } // 要保证根部是最底下的格子。 if x > y {
us.father[y] = x } else {
us.father[x] = y } return true}func getIndexByRowAndColumn(row, col, m int) int {
return row*m + col}func findBall(grid [][]int) []int {
n, m := len(grid), len(grid[0]) us := &UnionFindSet{
} us.InitUnionSet((n + 2) * m) for i, row := range grid {
for j, v := range row {
//判断边界 if j+v < 0 || j+v >= m {
continue } // 判断是否 V型 if row[j+v] != v {
continue } us.UnionV2(getIndexByRowAndColumn(i, j, m), getIndexByRowAndColumn(i+1, j+v, m)) } } ans := make([]int, m) for i, _ := range ans {
buttomIndex := us.FindV2(getIndexByRowAndColumn(0, i, m)) if buttomIndex/m == n {
// 到达最后一行 ans[i]=buttomIndex%m } else {
ans[i]=-1 } } return ans}

方法二 动态规划

可以学习一下

解析

还是要以一开始的图模型为基础。

设dp(i, j) 为i行j列的小球最终去哪里。
dp(n,j) = j (n是附加上的一行,已经在外面了,所以直接是答案)
dp(i, j) 需要看所在格子的开口情况,看隔壁是否为V型,如果是答案是-1
否 dp(i, j) = dp(i+1, j+grip[i][j+grip[i][j]]) 转移。
注意要判断边界

思路

var vis [][]bool // 标记是否查询过var dpVal [][]int // 答案值func dp(row, col, n, m int, grid [][]int) int {
}func InitDp(n, m int) {
}func findBall(grid [][]int) []int {
n, m := len(grid), len(grid[0]) InitDp(n, m) ans := make([]int, m) for i, _ := range ans {
ans[i] = dp(0, i, n, m, grid) } return ans}

注意

  • 查看左右时,一定要先判断边界
  • 当row=n时就是从底部落下了,所以当时col就是答案

知识点

  • 矩阵转数组
  • 动态规划
  • 记忆化搜索

复杂度

  • 时间复杂度:O(n*m)
  • 空间复杂度:O(n*m)

参考

代码实现

var vis [][]bool // 标记是否查询过var dpVal [][]int // 答案值func dp(row, col, n, m int, grid [][]int) int {
if col < 0 || col >= m {
// 出界了没有答案 return -1 } if row == n {
// 到底部了直接返答案 return col } // 已经出界直接返回 vis[row][col] = true dpVal[row][col] = -1 // 默认无答案 // 判断边界,且2边是否形成V型 if col+grid[row][col] < 0 || col+grid[row][col] >= m || grid[row][col] != grid[row][col+grid[row][col]] {
// 是V型直接返回 return dpVal[row][col] } dpVal[row][col] = dp(row+1, col+grid[row][col], n, m, grid) // 查看下一层 return dpVal[row][col]}func InitDp(n, m int) {
vis = make([][]bool, n+1) dpVal = make([][]int, n+1) for i := 0; i < n+1; i++ {
vis[i] = make([]bool, m) dpVal[i] = make([]int, m) }}func findBall(grid [][]int) []int {
n, m := len(grid), len(grid[0]) InitDp(n, m) ans := make([]int, m) for i, _ := range ans {
ans[i] = dp(0, i, n, m, grid) } return ans}

相关题目

这里整理了资料

动态规划相关题目


本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

在这里插入图片描述

转载地址:http://fowrz.baihongyu.com/

你可能感兴趣的文章