기술나눔

Likou 역추적 방법

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

역추적이란 무엇입니까?

특정 노드를 검색할 때 현재 노드(및 해당 하위 노드)가 필수 대상이 아닌 것으로 확인되면 원래 노드로 돌아가 검색을 계속하고 현재 노드의 수정된 상태를 복원합니다.
두 가지 작은 팁을 기억하세요:첫 번째는 참조(&)로 상태를 전달하는 것이고, 두 번째는 재귀가 완료된 후 모든 상태 수정 사항을 변경하는 것입니다.
수정을 역추적하는 데에는 일반적으로 두 가지 상황이 있습니다. 하나는 순열 및 조합과 같은 마지막 출력을 수정하는 것이고, 다른 하나는 액세스 대상을 수정하는 것입니다.
예를 들어, 행렬에서 문자열을 검색하는 것을 기억하세요.

46.전체 배치

주제

중복된 숫자가 없는 배열이 주어지면nums, 반환가능한 모든 순열 .당신은 할 수어떤 순서로든답변을 반환합니다.

예시 1:

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

예 2:

输入：nums = [0,1]
输出：[[0,1],[1,0]]

예시 3:

输入：nums = [1]
输出：[[1]]

힌트:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums모든 정수서로 다르다​​​​​​​
답변
배열의 모든 정렬된 조합을 출력하려면 역추적 방법을 사용할 수 있습니다.
먼저 위치를 결정한 다음 이를 각 후속 위치와 교환합니다. 변경 후 다음 장소로 이동합니다. 그런 다음 이 일련의 단계가 완료되면 교체된 것을 교체해야 합니다. 그것이 역추적 방법이다.
  1. class Solution {
  2. public:
  3.     vector<vector<int>> permute(vector<int>& nums) {
  4.         vector<vector<int>> ans;
  5.         back(nums,0,ans);
  6.         return ans;
  7.     }
  8.     void back(vector<int>& nums,int n,vector<vector<int>>& ans){
  9.         int i;
  10.         if(n==nums.size()-1)
  11.             ans.push_back(nums);
  12.         for(i=n;i<nums.size();i++){
  13.             swap(nums[i],nums[n]);
  14.             back(nums,n+1,ans);
  15.             swap(nums[i],nums[n]);
  16.         }
  17.     }
  18. };

77. 조합

77. 조합

주제

두 개의 정수가 주어지면n그리고k, 반환 범위[1, n]모두 가능하다k숫자의 조합.

당신은 누를 수 있습니다어떤 주문이든답변을 반환합니다.

예시 1:

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

예 2:

输入：n = 1, k = 1
输出：[[1]]

힌트:

  • 1 <= n <= 20
  • 1 <= k <= n

题解

count를 설정하고 각각의 개수를 계산합니다. count==k이면 배열에 넣습니다. 이는 이전의 순열과 조합과는 다릅니다. 이는 배열을 선택하는 것과 약간 비슷합니다.

1-n부터 시작하여 매번 결과를 저장할 추가 배열을 설정합니다. Count는 동적으로 변경됩니다. i를 할당한 후 count가 1씩 증가하고 dfs의 (i+1, n)에서 숫자가 선택됩니다. 계산-- 역추적 후.

  1. class Solution {
  2. public:
  3.     vector<vector<int>> combine(int n, int k) {
  4.         vector<vector<int>> ans;
  5.         vector<int> c(k,0);
  6.         int count;
  7.         dfs(n,k,1,ans,c,count);
  8.         return ans;
  9.     }
  10.     void dfs(int n,int k,int level,vector<vector<int>>& ans,vector<int>& c,int& count){
  11.         int i;
  12.  
  13.         if(count==k){
  14.             ans.push_back(c);
  15.             return ;
  16.         }
  17.             
  18.         for(i=level;i<=n;i++){
  19.             c[count++]=i;
  20.             dfs(n,k,i+1,ans,c,count);
  21.             --count;
  22.         }
  23.     }
  24. };

79. 단위 검색

79. 단어 검색

주제

주어진m x n2D 캐릭터 그리드board그리고 문자열 단어word .만약에word그리드에 존재하면 반환됩니다.true; 그렇지 않으면 반환false 。

단어는 알파벳 순서로 인접한 셀의 문자로 구성되어야 하며, 여기서 "인접" 셀은 가로 또는 세로로 인접한 셀을 의미합니다. 동일한 셀의 문자는 반복해서 사용할 수 없습니다.

예시 1:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

예 2:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

예시 3:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

힌트:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board그리고word영문 대문자와 소문자로만 구성

답변

비슷한 루틴.

dfs + 역추적 방법은 동일한 위치를 여러 번 방문하는 것을 방지하기 위해 먼저 방문을 정의하여 각 검색 중에 위치가 표시되었는지 여부를 표시합니다.

위치에 대해서는 경계를 넘는지 여부를 판단하기 위해 경계 판단이 필요합니다. 그런 다음 방문한 적이 있는지, 성공적으로 발견되었는지, 해당 위치의 문자가 대상 문자와 다른지 여부를 확인합니다.

dfs, 주변을 검색해 보세요.

  1. class Solution {
  2. public:
  3.     bool exist(vector<vector<char>>& board, string word) {
  4.         if(board.empty())
  5.             return false;
  6.         int m=board.size(),n=board[0].size();
  7.         vector<vector<bool>> visit(m,vector<bool>(n,false));
  8.         int i,j;
  9.         bool find=false;
  10.         for(i=0;i<m;i++){
  11.             for(j=0;j<n;j++)
  12.                 back(i,j,board,word,find,visit,0);
  13.         }
  14.         return find;
  15.     }
  16.     void back(int i,int j,vector<vector<char>>& board,string& word,
  17.     bool& find,vector<vector<bool>>& visit,int level){
  18.         if(i<0||i>=board.size()||j<0||j>=board[0].size())
  19.             return ;
  20.       
  21.         if(visit[i][j]||find||board[i][j]!=word[level])
  22.             return ;
  23.         if(level==word.size()-1){
  24.             find=true;
  25.             return ;
  26.         }
  27.         visit[i][j]=true;
  28.         back(i+1,j,board,word,find,visit,level+1);
  29.         back(i-1,j,board,word,find,visit,level+1);
  30.         back(i,j+1,board,word,find,visit,level+1);
  31.         back(i,j-1,board,word,find,visit,level+1);
  32.         visit[i][j]=false;
  33.     }
  34. };

51.N 퀸

51. 퀸 N

주제

체스의 규칙에 따르면 퀸은 같은 행이나 열, 같은 대각선에 있는 말을 공격할 수 있습니다.

n 퀸 문제공부하는 방법은 다음과 같습니다.n여왕이 배치됨n×n체스판 위에서 여왕들이 서로 공격할 수 없게 만듭니다.

정수를 줘n, 모두 다른 값을 반환합니다.N 여왕 문제솔루션입니다.

각 솔루션에는 서로 다른 내용이 포함되어 있습니다.n 퀸 문제체스 말 배치 계획은 이 계획에서'Q'그리고'.'그들은 각각 여왕과 빈 자리를 나타냅니다.

예시 1:

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

예 2:

输入：n = 1
输出：[["Q"]]

힌트:

  • 1 <= n <= 9

题意

N Queen에는 세 가지 라벨링 기능이 필요합니다. 하나는 열, 하나는 주 대각선, 다른 하나는 보조 대각선입니다.

각 행에는 반드시 퀸이 배치되므로 한 행씩 순회합니다. 마지막 행을 성공적으로 순회하고 퀸이 성공적으로 배치되면 충분합니다. 따라서 행 표시 기능을 설정할 필요가 없습니다.

이때 첫 번째 행부터 시작하여 열별로 탐색할 수 있습니다. 열이 거짓인지, 주대각선이 거짓인지, 보조 대각선이 거짓인지 확인합니다. 그렇다면 다음 열로 이동합니다. 그렇지 않으면 위치를 Q로 설정한 후 다음 행에 대해 동일한 검색을 수행합니다. 역추적 방법, 검색 후 위치 및 표시 기능을 복원하는 것을 잊지 마십시오.

이것은 대각선과 부대각선입니다. 좌표에 그릴 수 있습니다. 하나는 y=x+b이고 다른 하나는 y=-x+b입니다.

따라서 b=yx, b&gt;0을 만들기 위해 n을 더합니다. 다른 하나는 y+x입니다.

  1. class Solution {
  2. public:
  3.     vector<vector<string>> solveNQueens(int n) {
  4.         vector<vector<string>> ans;
  5.         if(n==0)
  6.             return {};
  7.         vector<string> board(n,string(n,'.'));
  8.         vector<bool> c(n,false),l(2*n-1,false),r(2*n-1,false);
  9.         back(n,ans,board,c,l,r,0);
  10.         return ans;
  11.     }
  12.     void back(int n,vector<vector<string>>& ans,vector<string>& board,vector<bool>& c,
  13.     vector<bool>& l,vector<bool>& r,int row){
  14.         if(row==n){
  15.             ans.push_back(board);
  16.             return ;
  17.         }
  18.         int i;
  19.         for(i=0;i<n;i++){
  20.             if(c[i]||l[row-i+n]||r[row+i]){
  21.                 continue;
  22.             }
  23.             board[row][i]='Q';
  24.             c[i]=l[row-i+n]=r[row+i]=true;
  25.             back(n,ans,board,c,l,r,row+1);
  26.             board[row][i]='.';
  27.             c[i]=l[row-i+n]=r[row+i]=false;
  28.         }
  29.     }
  30. };

요약하다

역추적 방법의 경우 먼저 경계조건과 종료조건을 구합니다. 일반적으로 i번째 집합은 행 수와 같습니다.

경계 조건은 일반적으로 경계를 넘지 않는 것입니다.

일반적으로 마킹 기능을 설정해야 합니다. 그런 다음 한 줄씩 또는 위치별로 액세스하면 방문 태그 기능이 true로 설정됩니다. 그런 다음 다음 또는 다음 줄로 계속 진행합니다(보통 재귀적으로). 그런 다음 완료 후 위의 마킹 기능과 보드를 복원합니다(일반적으로 하나가 답으로 설정됩니다). 일치하면 ans 배열로 push_back합니다.

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편