首页 > 思杰笔试第四题求解答
头像
三分甜Stella
编辑于 2020-09-10 15:17
+ 关注

思杰笔试第四题求解答

题目:两点之间路径, 求第k条,用回溯法

(0,0)到(M,N)  只能平移或垂直,求第k条比如(2,2,1)  输出  HHVV

(2,2,2 输出HVHV

我的代码回溯res中只有第一条路径,求找问题出在哪或者其他代码
//m个h,n个v,有h就添加h,没有就添加v,然后回溯
public class  ccc {

      static List < List<Character> > res=new ArrayList<>();

    static  char c[]={'h','v'};

     public static String solution(int m,int n,int k){      

        int count[]={m,n};

          List<Character> list=new ArrayList<>();    

          dfs(m,n,count,list,0);

          StringBuilder aa=new StringBuilder();

         for(int i=0;i<m+n;i++)

        aa.append(res.get(k-1).get(i));

        return aa.toString();

     }

    static void dfs(int m,int n,int count[],List<Character> list,int index)

     {

         if (index==m+n)

        {res.add(new ArrayList<>(list));

        return;

        }

        for(int i=0;i<2;i++)

        {if(count[i]<=0)

          continue;

          list.add(c[i]);

          count[i]--;

          dfs(m,n,count,list,index+1);

          list.remove(list.size()-1);

    

        }

         return;

        

    }

 

    public static void main(String []args){

           System.out.println(solution(3,3,1));

 

    }


    }

 



全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐