w***y 发帖数: 6251 | 1 要怎么做才能不超时?
我就是按照传统的N queens写法, 但是大集合到12就超时了
public class Solution {
int res=0;
public int totalNQueens(int n) {
int[] row = new int[n];
res=0;
_solveNQueens(row,0);
return res;
}
public void _solveNQueens(int[] row, int idx){
//when it finishes the last row, output the valid result
if(idx==row.length){
res++;
return;
}
for(int j=0;j
row[idx]=j;
if(isValid(row,idx))
_solveNQueens(row,idx+1);
}
}
public boolean isValid(int[] row, int idx){
for(int i=0;i
for (int j=i+1;j<=idx;j++)
if(row[i]==row[j] || row[i]-row[j]==i-j|| row[i]-row[j]==j-i)
return false;
}
return true;
}
} |
j********x 发帖数: 2330 | 2 你为啥不google呢,leetcode自己的forum都有几个高效的算法。。。 |
r*******e 发帖数: 7583 | 3 你这个isValid明显做了很多重复比较
只需要检查row[idx] 跟 row[1..idx-1]是否冲突,一层循环就够了
-i)
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要怎么做才能不超时? : 我就是按照传统的N queens写法, 但是大集合到12就超时了 : public class Solution { : int res=0; : public int totalNQueens(int n) { : int[] row = new int[n]; : res=0; : _solveNQueens(row,0); : return res; : }
|
b****g 发帖数: 192 | 4 我看也是。不必把之前检查过的再检查一遍。每次只检查当前的就行了
【在 r*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个isValid明显做了很多重复比较 : 只需要检查row[idx] 跟 row[1..idx-1]是否冲突,一层循环就够了 : : -i)
|
w***y 发帖数: 6251 | 5 多谢楼上的各位,改了isValid就可以过了
我回头再去学习一下更优化的解法 |
b****g 发帖数: 192 | 6 更优化的算法是什么样的?我就用和你一样的方法,过了leetcode测试不超时,我就颠了
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢楼上的各位,改了isValid就可以过了 : 我回头再去学习一下更优化的解法
|