dta25920
2019-06-18 12:26
浏览 23

为什么我的Go解决方案给出的结果与C ++不同?

Two code with exactly same logic gives different solutions.

Is there a bug within Go, or did I make some stupid mistake in my code?

This is a leetcode question LeetCode - Permutations II.

The C++ code below is an ACCEPTED solution written by someone.

C++ Code

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int>>res;
        helper(num, 0, num.size(), res);
        return res;
    }

    void helper(vector<int> num, int start, int j, vector<vector<int> > &res) {
        if (start == j-1) {
            res.push_back(num);
            return;
        }
        for (int i = start; i < j; i++) {
            if (start == i || num[start] != num[i]) {
                swap(num[start], num[i]);
                helper(num, start + 1, j, res);
            }
        }
    }
};

int main() {
    Solution s;
    vector<int> nums({2,1,2});
    vector<vector<int>> res = s.permuteUnique(nums);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << " " << res[i][j];
        }
        cout << endl;
    }
}

I translated the C++ code above to the golang code below:

Golang Code

package main

func permuteUnique(nums []int) [][]int {
    qsort(nums, 0, len(nums)-1)
    res := make([][]int, 0, len(nums))
    helper(&res, nums, 0)
    return res
}

func helper(res *[][]int, nums []int, start int) {
    if start == len(nums)-1 {
        copied := make([]int, len(nums))
        copy(copied, nums)
        *res = append(*res, copied)
        return
    }
    for i := start; i < len(nums); i++ {
        if start == i || nums[start] != nums[i] {               
            nums[i], nums[start] = nums[start], nums[i]
            helper(res, nums, start+1)
        }
    }
}

func main() {
    nums := []int{2,1,2}
    res := permuteUnique(nums)
    for i := 0; i < len(res); i++ {
        for j := 0; j < len(res[0]); j++ {
            print(" ", res[i][j]);
        }
        println()
    }
}

func qsort(nums []int, low, high int) {
    if low >= high {
        return
    }
    i, j, pivot := low, high, nums[low]
    for i < j {
        for i < j && nums[j] >= pivot {
            j--
        }
        nums[i] = nums[j]
        for i < j && nums[i] <= pivot {
            i++
        }
        nums[j] = nums[i]
    }
    nums[i] = pivot
    qsort(nums, low, i-1)
    qsort(nums, i+1, high)
}

Output

Both of code above is able to run instantly. Below is my output:

fondoger@localhost:Desktop$ g++ test.cpp -o app && ./app
 1 2 2
 2 1 2
 2 2 1
fondoger@localhost:Desktop$ go run test.go
 1 2 2
 2 1 2
 2 2 1
 1 2 2

I tried debugging using Goland IDE and Clion IDE for several hours, but I can't find out the truth.

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • dourao1896 2019-06-18 12:34
    已采纳

    Try this:

    func helper(res *[][]int, nums []int, start int) {
        copied := make([]int, len(nums))
        copy(copied, nums)
        nums = copied;
        if start == len(nums)-1 {
            *res = append(*res, nums)
            return
        }
        for i := start; i < len(nums); i++ {
            if start == i || nums[start] != nums[i] {               
                nums[i], nums[start] = nums[start], nums[i]
                helper(res, nums, start+1)
            }
        }
    }
    

    When porting from language to language you need to make sure you "port" implicit features as well. In C++ solution when calling helper function language would make a copy of nums array for every iteration. You didn't clone this behavior to go and got different result. I added coping num at beginning of helper function and it worked well.

    打赏 评论