V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
KHHj7U2DNR
V2EX  ›  问与答

C++和 Golang 几乎一样的代码,为什么输出不一致?

  •  
  •   KHHj7U2DNR · 2019-06-18 18:26:49 +08:00 · 2370 次点击
    这是一个创建于 2020 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Leetcode 第 47 题,有重复数字的排列数,原题地址

    我对照着大佬写的 C++代码,自己写了一份 Golang 代码,运行结果总是不一致。

    为了解决这个 bug,我专门下载了 goland 和 clion 两个 IDE,Golang 和 C++两边对照着调试,单步调试了好几个小时,还是找不到问题出在哪里。

    我单步调试发现了一点点线索,在进行若干个递归步骤后,go 代码会从某行直接跳到下面的某行,没有执行中间的代码(在源码中通过注释标出)。

    下面的两段代码都是直接可运行的代码,特地恳请大佬们帮忙 Debug !

    代码比较简单,不需要理解解题步骤,大佬们肉眼对照找一下区别就好了。

    感激不尽!

    Golang 代码

    package main
    
    /*
     * @lc app=leetcode id=47 lang=golang
     *
     * [47] Permutations II
     */
    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)
    }
    

    C++代码

    #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;
        }
    }
    
    13 条回复    2019-06-18 23:32:45 +08:00
    KHHj7U2DNR
        1
    KHHj7U2DNR  
    OP
       2019-06-18 18:32:25 +08:00
    附上两段代码分别运行的结果:
    ![运行结果]( https://s2.ax1x.com/2019/06/18/VLQA29.jpg)
    BCy66drFCvk1Ou87
        2
    BCy66drFCvk1Ou87  
       2019-06-18 19:12:50 +08:00 via Android   ❤️ 1
    不想看题,gakki 粉要拔刀了
    KHHj7U2DNR
        3
    KHHj7U2DNR  
    OP
       2019-06-18 19:16:43 +08:00
    😭😭😭
    有没有大佬来帮帮我呀,我今天一整天啥都干没干,就卡在这里了。
    😭😭😭
    KHHj7U2DNR
        4
    KHHj7U2DNR  
    OP
       2019-06-18 20:50:32 +08:00
    sad, 代码问题发到 v2 上都没人愿意帮看的,发到 stackoverflow 上 10 分钟破案。
    原因有点复杂,与 C++代码的某个隐式操作有关。
    想了解具体的可以看这里: https://stackoverflow.com/questions/56649138
    BCy66drFCvk1Ou87
        5
    BCy66drFCvk1Ou87  
       2019-06-18 20:58:50 +08:00
    看了回答发现回答者是个北京人,hhh
    BCy66drFCvk1Ou87
        6
    BCy66drFCvk1Ou87  
       2019-06-18 20:59:51 +08:00
    @HuasLeung 卧槽看错了那是你……
    zhaode
        7
    zhaode  
       2019-06-18 21:02:01 +08:00 via Android
    题主这就是传参的问题,cpp 里面那个 nums 是按值穿的所以会拷贝,你一开始写的 go 代码传进去的是引用,在 helper 里的操作会修改掉外部 nums,而 cpp 不会修改,所以不一样
    Akiyu
        8
    Akiyu  
       2019-06-18 21:10:51 +08:00
    哦, 看了一下, 这原因不复杂, 也不是什么神秘的 C++隐式操作, 你应该是没有复制数组

    在 C++ 中:
    void helper(vector<int> num, int start, int j, vector<vector<int> > &res)
    这里的 num 签名没有带 '&', 这会是一次完整的拷贝

    而 Go 中:
    func helper(res *[][]int, nums []int, start int)
    这里的传递应该是一个 slice, 是引用类型的 (我猜的, 反正不会发生数据拷贝, 就相当于拷贝指针一样)
    (很多数组(slice)的传递都是引用, 我曾经遇到过坑, 至于解法, 就 leetcode 的解法, copy)

    -----------------------------

    至于为什么不看嘛...
    其实代码写得太长太多, 不是闲得没事做, 没人爱看的...
    (老外还挺热心的...)

    -----------------------------

    我是写 C++ 的, 同时在学 Go, 不介意的话
    [email protected], 邮箱我你的联系方式, 扩个列
    KHHj7U2DNR
        9
    KHHj7U2DNR  
    OP
       2019-06-18 22:52:40 +08:00 via Android
    @Akiyu 我也在学 go, 不太会 c++哈
    Akiyu
        10
    Akiyu  
       2019-06-18 23:02:41 +08:00
    @KHHj7U2DNR
    这个不重要, 我就想扩个列, 如果介意的话就算了
    Akiyu
        11
    Akiyu  
       2019-06-18 23:11:30 +08:00
    @KHHj7U2DNR
    我也在做 leetcode: https://leetcode.com/yucangs/
    我没有其他意思, 就是单纯看到一个对 c++有兴趣
    同时也在学 go, 在做 leetcode, 想扩个列, 互相学习一下而已
    skadi
        12
    skadi  
       2019-06-18 23:24:11 +08:00
    建议重学 cpp
    KHHj7U2DNR
        13
    KHHj7U2DNR  
    OP
       2019-06-18 23:32:45 +08:00 via Android
    @skadi 根本没注意到 num 是个 vector, 就以为是个普通数组,debug 的时候一直以为是翻译代码出了问题。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2453 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 15:51 · PVG 23:51 · LAX 07:51 · JFK 10:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.