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 的大作中提到】
: 要怎么做才能不超时？
: 我就是按照传统的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 的大作中提到】
: 你这个isValid明显做了很多重复比较
: 只需要检查row[idx] 跟 row[1..idx-1]是否冲突，一层循环就够了
:
: -i)
|
w***y
发帖数: 6251 | 5 多谢楼上的各位，改了isValid就可以过了
我回头再去学习一下更优化的解法 |
b****g
发帖数: 192 | 6 更优化的算法是什么样的？我就用和你一样的方法，过了leetcode测试不超时，我就颠了
【在 w***y 的大作中提到】
: 多谢楼上的各位，改了isValid就可以过了
: 我回头再去学习一下更优化的解法
|
