dta25920 2019-06-18 12:26
浏览 24
已采纳

为什么我的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.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形