切片结构使用太多内存

问题描述：

I tried to solve this problem with BFS, but for input "99 100" my program uses more than 260 Mb and online-judge system throws MEMORY_LIMIT_EXCEEDED. I guess the problem is the way I use QUEUE. So what do you think is the problem? And how should I solve it?

Here is my code. And thanks in advance!:

package main

import (
    "fmt"
)

type pair struct {
    nn int
    dd int
}

func main() {
    var n, m int
    fmt.Scanf("%d%d", &n, &m)

    if n >= m {
        fmt.Println(n - m)
    } else {
        device := make([]pair, 1)
        device[0] = pair{n, 0}

        ans := 0
        for {
            // pop front element
            tmp := device[0]
            device = device[1:]

            if tmp.nn == m { // reached destination
                ans = tmp.dd
                break
            }

            // add neighbors to the queue
            device = append(device, pair{tmp.nn - 1, tmp.dd + 1})
            device = append(device, pair{tmp.nn * 2, tmp.dd + 1})
        }

        fmt.Println(ans)
    }
}

EDIT: More readable and working(ACCEPTED) code:

package main

import (
    "fmt"
)

type pair struct {
    location int
    dist     int
}

func main() {
    var n, m int
    fmt.Scanf("%d%d", &n, &m)

    if n >= m {
        fmt.Println(n - m)
    } else {
        visited := make([]bool, m+2)

        queue := make([]pair, 1)
        queue[0] = pair{n, 0}

        ans := 0
        visited[n] = true
        for {
            // pop front element
            tmp := queue[0]
            queue = queue[1:]

            // reached destination
            if tmp.location == m {
                ans = tmp.dist
                break
            }

            // add neighbors to the queue
            if tmp.location*2 <= m+1 && visited[tmp.location*2] == false {
                queue = append(queue, pair{tmp.location * 2, tmp.dist + 1})
                visited[tmp.location*2] = true
            }
            if tmp.location-1 >= 0 && visited[tmp.location-1] == false {
                queue = append(queue, pair{tmp.location - 1, tmp.dist + 1})
                visited[tmp.location-1] = true
            }
        }

        fmt.Println(ans)
    }
}

答

Your algorithm is not BFS, because, you can visit the same state more than one.

For example, 4 -> 3 -> 6 and 4 -> 8 -> 7 -> 6, which 6 will end up to be processed twice.

Secondly, for number x that is greater than the target, the minimum number of step is always

x - target + step to reach x

so you should not add it into the queue.

By doing those two modifications, the space complexity will be limited to O(m) which should help you to solve the problem.

Sample code

ans := -1
dist := make([]int, m + 1)
q := make([]int,1)
q[0] = n

for i := 0; i < len(q); i++ {
    node := q[i]
    if node == m {
       if ans == -1 || ans > dist[m]{
          ans = dist[m]
       }
       break;
    }
    a := node*2
    b := node - 1
    if a >= m {
       if ans == -1 || ans > (1 + dist[node] + a - m) {
          ans = 1 + dist[node] + a - m
       }
    }else if dist[a] == 0 && a != n {
       q = append(q, a)
       dist[a] = 1 + dist[node]
    }
    if dist[b] == 0 && b != n {
       q = append(q, b)
       dist[b] = 1 + dist[node]
    } 
}
return ans

答

A first glance tell me that for each dd you have, there is going to be a 2^dd elements in the queue. And with the answer expected to be larger than, say, 50, it is a guranteed memory limit exceed.

A very simple and common optimisation is to track the visted nodeds (nn in your case). Create a map[int]bool (since the dd is only increasing so there is no reason to record the value of last visted) and don't add to queue.

Another optimisation, as metioned in the comments, is no to add nn larger than targets into the queue. That is a little bit complicated, as you need to record a value res = min(res, dd+nn-target) where nn is the value larger than target and dd is the step to get to the value. You also want to break if current dd is larger then res.

The code of the accepted answer has a bug. It never tries to determine if b is smaller than zero. A runtime panic of index of range is likely to happen given a designed test case.

切片结构使用太多内存

相关推荐