我一直在努力解决这个 Hackerrank 挑战:Link

这是你必须做的:

你有一个大矩阵:

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 0 1 1

和一个小矩阵:

1 1 1
1 1 1
1 1 0

你必须找出小矩阵是否存在于大矩阵中。

最多有 5 个测试用例，每个矩阵的最大尺寸为 1000x1000，我需要在 4 秒内解决这个问题。

我的代码在最大可能输入时超时，我想也许我扫描矩阵的方式太慢了。

这是我的代码:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func main() {
    var t, rL, cL, rS, cS, temp int
    var s string
    var sl []string
    var mxL, mxS [][]int
    var found bool
    fmt.Scanf("%d", &t)
    for ; t > 0; t-- {
        // Start scanning input
        // Scanning large matrix
        fmt.Scanf("%d%d", &rL, &cL)
        mxL = make([][]int, rL)
        for i := range mxL {
            mxL[i] = make([]int, cL)
        }
        for i := 0; i < rL; i++ {
            fmt.Scanf("%s", &s)
            sl = strings.Split(s, "")
            for j, v := range sl {
                temp, _ = strconv.Atoi(v)
                mxL[i][j] = temp
            }
        }
        // Scanning small matrix
        fmt.Scanf("%d%d", &rS, &cS)
        mxS = make([][]int, rS)
        for i := range mxS {
            mxS[i] = make([]int, cS)
        }
        for i := 0; i < rS; i++ {
            fmt.Scanf("%s", &s)
            sl = strings.Split(s, "")
            for j, v := range sl {
                temp, _ = strconv.Atoi(v)
                mxS[i][j] = temp
            }
        }
        // Stop scanning input
        // Start searching for small matrix in large matrix
        found = true
        for iL := 0; iL <= rL-rS; iL++ {
            for jL := 0; jL <= cL-cS; jL++ {
                found = true
                if mxL[iL][jL] == mxS[0][0] {
                    for iS := 0; iS < rS; iS++ {
                        for jS := 1; jS < cS; jS++ {
                            if mxS[iS][jS] != mxL[iS+iL][jS+jL] {
                                found = false
                                break
                            }
                        }
                        if !found {
                            break
                        }
                    }
                    if found {
                        break
                    }
                } else {
                    found = false
                }
            }
            if found {
                fmt.Println("YES")
                break
            }
        }
        if !found {
            fmt.Println("NO")
        }
        // Stop searching for small matrix in large matrix
    }
}

我正在使用一片整数片来存储输入。

mxL 是大矩阵，mxS 是小矩阵。

rL 和cL 分别代表大矩阵的行和列。

rS 和cS 分别代表小矩阵的行和列。

最佳答案

好吧，我会向您指出一个想法，然后您可以尝试实现它。因此，创建一个与大数组一样大的新二维数组。称它为 sumArray。现在让这个 sumArray 中的每个单元格代表当前单元格是最左下角单元格的总和。现在你要做的是只检查与你的小数组具有相同总和的单元格，而不是检查数组中的每个元素。

如果这些是你的输入

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 0 1 1

1 1 1
1 1 1
1 1 0

首先对你的小数组求和 --> 8

现在让我向您展示您的求和数组的样子

-1 -1 -1 -1 -1 -1     -1 means that we can't sum at this point because
-1 -1 -1 -1 -1 -1      the dimensions are just smaller than your small array
-1 -1  9  9  9  9      each other cell represent the sum of your original 
 9  9  9  9  9  9      matrix values.
 9  9  9  8  9  9

现在，如果您只扫描这个数组，您会发现您会将搜索空间从每个可能的位置减少到只有总和相等的位置。这并不能保证数组就在这个位置，您仍然需要添加验证步骤，但它会减少您的搜索空间。

关于algorithm - Golang 代码对于 Hackerrank 来说太慢了，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32653087/