Leetcode N-Queens II
N-Queens II
Total Accepted: 4450
Total Submissions: 14913 My Submissions
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
역귀회소법의 유연한 운용.
새로운 사고방식:
이곳의 최적화점은 밑에서 위로 누적하여 합치면 속도가 매우 빠르지만 이 문제는 밑에서 위로 합치면 여전히 어렵다.
4 ~ 5성급 난이도죠.
원래 12개의queens 테스트를 할 때 1000ms가 많은 것 같았는데, 지금은 9개의 용례만 있으면 간단하다.
int totalNQueens(int n)
{
vector<int> q(n,-1);
return queens(q, n);
}
int queens(vector<int> &q, int n, int r = 0)
{
if (r == n) return 1;
int sum = 0;
for (int i = 0; i < n; i++)
{
if (isLegal(q, r, i))
{
q[r] = i;
sum += queens(q, n, r+1);//q[r] = -1;
}
}
return sum;
}
bool isLegal(vector<int> &q, int r, int c)
{
for (int i = 0; i < r; i++)
if (q[i] == c || q[i]-i == c-r || q[i]+i == c+r) return false;
return true;
}Leetcode의 슈퍼비트 연산 프로그램은 무슨 뜻인지 대충 알겠지만 너무 최고예요. 익숙하지 않으면 면접에서 이런 프로그램을 쓸 수 없을 거예요.
그리고 이것은 아마도 연산의 대가가 이런 알고리즘을 만들어 낼 수 있을 것이다. 이 알고리즘을 본 사람들은 모두 놀랄 것이다.
운행 속도가 매우 빠르다. 원래leetcode에서 12queens가 겨우 80ms 정도였다.그러나 현재 leetcode에서 난이도를 낮추었기 때문에 9개의queens의 용례만 있으면 이 슈퍼 알고리즘의 장점을 나타낼 수 없다.
class Solution {
public:
int cnt,upper;
int totalNQueens(int n)
{
cnt = 0;
upper = (1<<n)-1 ;
Queen(0,0,0);
return cnt;
}
void Queen(int row,int ld,int rd)
{
int pos,p;
if(row!=upper)
{
pos = upper & (~(row | ld |rd));
while(pos!=0)
{
p = pos & (-pos);
pos = pos - p;
Queen(row+p,(ld+p)<<1,(rd+p)>>1);
}
}
else ++cnt;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
