경로 시퀀스가 ​​좌표를 두 번 이상 방문하는지 확인

일부 응용 프로그램에서는 경로 시퀀스가 ​​좌표를 두 번 방문하는지 확인하는 데 관심이 있을 수 있습니다. 이는 예를 들어 차량이 두 지점 사이를 앞뒤로 움직이는지 감지하는 GPS 추적 시스템에 유용합니다. 이 기사에서는 경로 시퀀스가 ​​좌표를 두 번 방문하는지 확인하는 방법과 이를 C++로 구현하는 방법에 대해 설명합니다.

알고리즘

이 문제를 해결하기 위해 해시 테이블을 사용하여 지금까지 방문한 모든 좌표를 추적할 수 있습니다. 먼저 시퀀스의 첫 번째 좌표에 액세스하여 해시 테이블에 추가합니다. 그런 다음 시퀀스의 각 후속 좌표에 대해 해당 좌표가 이미 해시 테이블에 있는지 확인합니다. 그렇다면 이전에 이 좌표에 액세스한 적이 있다는 것을 알고 true를 반환할 수 있습니다. 그렇지 않은 경우 해시 테이블에 추가하고 다음 좌표로 이동합니다. 중복된 좌표를 찾지 않고 모든 좌표를 방문하면 false를 반환할 수 있습니다.

예

위 알고리즘을 C++로 구현한 것입니다−

으아악

출력

으아악

테스트 케이스 예시

"위, 아래, 아래, 왼쪽, 왼쪽, 오른쪽, 위, 위, 아래, 위" 경로를 나타내는 "UDDLLRUUUDU" 시퀀스를 생각해 보세요.

원점(0, 0)에서 시작하여 경로를 따라 이동하면서 좌표를 업데이트합니다.

각 단계에서 이전에 새 좌표를 방문한 적이 있는지 확인합니다. 그렇다면 시퀀스가 ​​좌표를 두 번 방문했다는 것을 알고 true를 반환합니다. 그렇지 않은 경우 좌표를 방문한 것으로 표시하고 계속합니다.

다음은 주어진 시퀀스에 대해 알고리즘이 작동하는 방식입니다. -

• 원점(0, 0)부터 시작

• “U” − (0, 1)까지 이동합니다. (0, 1)을 방문한 것으로 표시합니다.

• “D” − (0, 0)으로 아래로 이동합니다. (0, 0)을 방문한 것으로 표시합니다.

• “D”−는 (0, -1)로 아래로 이동합니다. (0, -1)을 방문한 것으로 표시합니다.

• “L” − (-1, -1)으로 왼쪽으로 이동합니다. (-1, -1)을 방문한 것으로 표시합니다.

• “L” − 왼쪽으로 (-2, -1)로 이동합니다. (-2, -1)을 방문한 것으로 표시합니다.

• "R" − (-1, -1)로 오른쪽으로 이동합니다. 이 좌표는 이전에 방문한 적이 있으므로 true를 반환합니다.

시퀀스가 좌표에 두 번 액세스하므로 함수는 true를 반환합니다.

따라서 주어진 시퀀스 "UDDLLRUUUDU"에 대해 함수는 두 번 액세스된 좌표에 시퀀스를 올바르게 반환합니다.

결론

이 기사에서는 경로 시퀀스가 ​​좌표를 두 번 방문하는지 확인하는 방법에 대해 논의했습니다. 우리는 지금까지 방문한 모든 좌표를 추적하고 각 단계에서 중복을 확인하기 위해 해시 테이블을 사용합니다. 우리는 또한 알고리즘의 C 구현도 제공합니다

위 내용은 경로 시퀀스가 ​​좌표를 두 번 이상 방문하는지 확인의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!