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;
}
}
1
KHHj7U2DNR OP 附上两段代码分别运行的结果:
![运行结果]( https://s2.ax1x.com/2019/06/18/VLQA29.jpg) |
2
BCy66drFCvk1Ou87 2019-06-18 19:12:50 +08:00 via Android 1
不想看题,gakki 粉要拔刀了
|
3
KHHj7U2DNR OP 😭😭😭
有没有大佬来帮帮我呀,我今天一整天啥都干没干,就卡在这里了。 😭😭😭 |
4
KHHj7U2DNR OP sad, 代码问题发到 v2 上都没人愿意帮看的,发到 stackoverflow 上 10 分钟破案。
原因有点复杂,与 C++代码的某个隐式操作有关。 想了解具体的可以看这里: https://stackoverflow.com/questions/56649138 |
5
BCy66drFCvk1Ou87 2019-06-18 20:58:50 +08:00
看了回答发现回答者是个北京人,hhh
|
6
BCy66drFCvk1Ou87 2019-06-18 20:59:51 +08:00
@HuasLeung 卧槽看错了那是你……
|
7
zhaode 2019-06-18 21:02:01 +08:00 via Android
题主这就是传参的问题,cpp 里面那个 nums 是按值穿的所以会拷贝,你一开始写的 go 代码传进去的是引用,在 helper 里的操作会修改掉外部 nums,而 cpp 不会修改,所以不一样
|
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], 邮箱我你的联系方式, 扩个列 |
9
KHHj7U2DNR OP @Akiyu 我也在学 go, 不太会 c++哈
|
10
Akiyu 2019-06-18 23:02:41 +08:00
@KHHj7U2DNR
这个不重要, 我就想扩个列, 如果介意的话就算了 |
11
Akiyu 2019-06-18 23:11:30 +08:00
@KHHj7U2DNR
我也在做 leetcode: https://leetcode.com/yucangs/ 我没有其他意思, 就是单纯看到一个对 c++有兴趣 同时也在学 go, 在做 leetcode, 想扩个列, 互相学习一下而已 |
12
skadi 2019-06-18 23:24:11 +08:00
建议重学 cpp
|
13
KHHj7U2DNR OP @skadi 根本没注意到 num 是个 vector, 就以为是个普通数组,debug 的时候一直以为是翻译代码出了问题。
|