讨论/题目交流/第22题 求问为何我的代码将结果输出了两遍/
第22题 求问为何我的代码将结果输出了两遍
求问我的这种方法为何出了问题,将标准答案输出了两遍谢谢阿
class Solution {
    public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<>();
    String str = "" ;
    // System.out.println(str);
    helper(str,n,n,list);
    return list;
    }
    private void helper(String str,int left,int right, List<String> list)
    {   //String curstr = str;
       System.out.print(left);
       System.out.print(right);
       System.out.println(str);
        if(left==0 && right==0)
            {   
                list.add(str);
                System.out.println(list);
                return;
            } 
        if(left>right)
            {return;}
        if (left>0)
        {
             left -=1;
             str = str+"(";          
            helper(str,left,right,list);
        }
        if(right>0)
        {
            right -=1;
            str = str+")";
            helper(str,left,right,list);
        }
     }    
    }
展开讨论
小东马发起于 2020-04-01
共 1 个讨论

当然是你逻辑有问题啦
n = 3举例
进到if left > 0部分时
进去是(, 2, 3
代表的是所有以(开头的答案

等出来后进到if right > 0部分时
进去是(), 2, 2
代表的是所有以()开头的答案

由此可见第二部分的答案已经被包含在第一部分其中了
不过当然,直接把第二部分去掉答案也是不对的
我们其实希望的是第二部分输出的是以 )开头的答案
因此正确的改法是在if left > 0里面改动的东西要复原,比如leftstr
具体做法因人而异,不过你的方法感觉会超时,要优化
直接修改的话,我修改了一下,逻辑是对的,但比较慢

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        String str = "" ;
        helper(str,n,n,list);
        return list;
    }
    private void helper(String str,int left,int right, List<String> list)
    {
        if(left==0 && right==0)
        {   
            list.add(str);
            System.out.println(list);
            return;
        } 
        if(left>right)
            {return;}
        if (left>0)
        {      
            //简单点说,你在这里对str和left的修改,会影响下面right部分的正确结果
            helper(str+"(",left - 1,right,list);
        }
        if(right>0)
        {
            helper(str+")",left,right - 1,list);
        }
     }    
}