求问一道题

leetcode 406，我模仿n-queens的解法来做，无论如何都不明白为什么不对。。。

1. public static int[][] reconstructQueue(int[][] people) {
   
2.         if(people == null || people.length == 0) return null;
   
3.         int[][] res = new int[people.length][2];
   
4.         placeQueue(people,res,0);
   
5.         return res;
   
6.     }
   
7.    
   
8.     public static void placeQueue(int[][] people, int[][] res, int idx) {
   
9.         int n = people.length;
   
10.         if(idx == n) return;
    
11.         for(int i = 0; i < n; i++) {
    
12.             if(isValid(res,people[i],idx)) {
    
13.                 res[idx] = people[i];
    
14.                 for(int j = 0; j < res.length; j++)
    
15.                         System.out.print("("+res[j][0]+","+res[j][1]+") ");
    
16.                 System.out.println("Index:"+idx);
    
17.                 placeQueue(people,res,idx+1);
    
18.             }
    
19.         }
    
20.     }
    
21.    
    
22.     public static boolean isValid(int[][] res, int[] person, int idx) {
    
23.         int count = 0;
    
24.         for(int i = 0; i < idx; i++) {
    
25.             if(res[i][0] == person[0] && res[i][1] == person[1]) return false;
    
26.             if(res[i][0] >= person[0]) count++;
    
27.         }
    
28.         if(count!=person[1]) return false;
    
29.         
    
30.       
    
31.         return true;
    
32.     }

复制代码

我在自己测试的时候，使用了默认case，然后发现输出如下：
(7,0) (0,0) (0,0) (0,0) (0,0) (0,0) Index:0
(7,0) (7,1) (0,0) (0,0) (0,0) (0,0) Index:1
(7,0) (7,1) (5,2) (0,0) (0,0) (0,0) Index:2
(7,0) (6,1) (5,2) (0,0) (0,0) (0,0) Index:1
(7,0) (6,1) (7,1) (0,0) (0,0) (0,0) Index:2
(7,0) (6,1) (5,2) (0,0) (0,0) (0,0) Index:2
(7,0) (6,1) (5,2) (7,1) (0,0) (0,0) Index:3
(7,0) (6,1) (5,2) (7,1) (4,4) (0,0) Index:4
(5,0) (6,1) (5,2) (7,1) (4,4) (0,0) Index:0
(5,0) (7,0) (5,2) (7,1) (4,4) (0,0) Index:1
(5,0) (7,0) (7,1) (7,1) (4,4) (0,0) Index:2
(5,0) (7,0) (6,1) (7,1) (4,4) (0,0) Index:2
(5,0) (7,0) (6,1) (7,1) (4,4) (0,0) Index:3
(5,0) (7,0) (6,1) (7,1) (4,4) (0,0) Index:4
(5,0) (7,0) (5,2) (7,1) (4,4) (0,0) Index:2
(5,0) (7,0) (5,2) (7,1) (4,4) (0,0) Index:3
(5,0) (7,0) (5,2) (7,1) (4,4) (0,0) Index:4
(5,0) (7,0) (5,2) (6,1) (4,4) (0,0) Index:3
(5,0) (7,0) (5,2) (6,1) (4,4) (0,0) Index:4
(5,0) (7,0) (5,2) (6,1) (4,4) (7,1) Index:5
(5,0) (7,0) (5,2) (6,1) (7,1) (7,1) Index:4

我不明白为什么在index = 5的时候，程序会继续下去。。。求解

这题可以贪心做，每次移动剩余人中最高的人。这样无论这个人被放到哪里，已排过的部分仍然valid，因为已排的人比这个人高，除非他们身高相等。所以如果身高相等我们从k值小的那个人开始处理避免这种情况。

yangluphil 发表于 2016-12-6 16:22
这题可以贪心做，每次移动剩余人中最高的人。这样无论这个人被放到哪里，已排过的部分仍然valid，因为已排 ...

那求问我的做法错在哪里呢？我的应该算是DFS吧

donnice 发表于 2016-12-6 16:39
那求问我的做法错在哪里呢？我的应该算是DFS吧

能说下你做法的思路吗

yangluphil 发表于 2016-12-6 17:01
能说下你做法的思路吗

谢谢，基本就是和N-queen差不多：在一个位置放下一个人，如果valid的话就放下第二个人，直到放满所有人并且都valid的话就return

帮你跑了一下debug， index ＝＝ 5 后面全部都返回了，
可是这个情况只不过是你递归里面的一个子进程而已，然后接着return到 index ＝＝ 4的情况。
因为你的输出就是选择性的（if）所以你看不到你程序的全部过程。
你可以自己用debug去一步一步的跑一下。
实在不行自己画下自己程序的stack

donnice 发表于 2016-12-7 02:19
谢谢，基本就是和N-queen差不多：在一个位置放下一个人，如果valid的话就放下第二个人，直到放满所有人并 ...

楼上说得对你返回的只是一个function call。试试让placeQueue返回一个boolean，idx == n或recursive call返回true时，返回true。这样保证整个recursion终止。

不过这题DFS会非常慢，最好还是贪心做，一步到位。

eric_0609 发表于 2016-12-7 02:45
帮你跑了一下debug， index ＝＝ 5 后面全部都返回了，
可是这个情况只不过是你递归里面的一个子进程而已 ...

对，我也是得出了这个结果

yangluphil 发表于 2016-12-7 03:19
楼上说得对你返回的只是一个function call。试试让placeQueue返回一个boolean，idx == n或recursive call ...

非常感谢！