리트코드 챌린지 #3

안녕하세요! 오늘은 Two pointers 의 마지막 부분을 마치도록 하겠습니다.

오늘의 문제

오늘의 주제: Two pointers

ID
이름
어려움
문제
해결책


344
리버스 스트링
쉬운
link
link

557
문자열의 역방향 단어 III
쉬운
link
link

876
연결 리스트의 중간
쉬운
link
link

19
목록 끝에서 N번째 노드 제거
중간
link
link


여기에는 2개의 문자열 조작 문제와 2개의 연결 목록 문제가 있습니다.

344. 리버스 스트링

이것은 간단한 반전 문제입니다. 시작과 끝에 동시에 2개의 포인터를 설정하고 포인터에서 값을 바꾼 다음 안쪽으로 이동하십시오. left >= right까지 프로세스를 반복합니다.

복잡성은 O(n) 시간과 O(1) 추가 공간입니다.

참고: JavaScript는 문자열 조작을 지원하지 않는 반면 문제는 제자리 반전을 요구하는 것이었습니다. 따라서 leetcode는 char 배열을 입력으로 보냅니다. 너무 달콤해!

577. 문자열의 역방향 단어 III

이 문제에는 제자리 반전이 필요하지 않으므로 고급 언어의 힘을 남용할 때입니다. ㅋㅋㅋ!
한 줄만 필요합니다. split + join 콤보는 문자열 조작을 처리하는 강력한 도구입니다. 맵과 함께 사용하여 각 세그먼트를 조작하십시오.

return s.split(' ').map(x => x.split('').reverse().join('')).join(' ');

복잡성은 O(n) 시간과 O(n) 추가 공간입니다.

참고: O(1) 추가 공간은 이 문제에서 char 배열 대신 반환으로 새 문자열이 필요하기 때문에 불가능합니다. 그리고 JS는 내부 문자열 조작을 지원하지 않습니다.

876. 연결 목록의 중간

간단한 해결책은 연결된 목록을 한 번 반복하여 길이를 얻는 것입니다. 그리고 길이의 절반을 다시 반복하여 중간을 얻습니다.

또 다른 해결책은 머리에서 시작하는 두 개의 포인터를 유지하는 것입니다. 각 반복에서 포인터 A는 2단계 이동하고 포인터 B는 1단계 이동합니다. 이렇게 하면 포인터 A가 끝에 도달하면 포인터 B는 연결 목록의 중간에 있게 됩니다.

두 솔루션 모두 O(n) 시간과 O(1) 추가 공간이 필요합니다.

19. 목록 끝에서 N번째 노드 제거

마지막 문제와 마찬가지로 간단한 해결책은 먼저 길이를 세는 것입니다. 그리고 다시 반복하여 끝에서 n 번째 노드를 가져옵니다.

또 다른 방법은 처음에 포인터 A를 설정하고 포인터 B를 n 단계 앞으로 설정하는 것입니다. 그런 다음 포인터 B가 끝에 도달하는 동안 두 노드를 동시에 이동하고 포인터 A는 끝에서 n번째 노드에 있습니다.

두 솔루션 모두 O(n) 시간과 O(1) 추가 공간이 필요합니다.

참고: 두 번째 솔루션의 경우 첫 번째 요소 제거와 같은 일부 특수한 경우에 주의해야 합니다(따라서 제거된 헤드 대신 두 번째 요소를 헤드로 반환해야 함).

추가 문제

ID
이름
어려움
문제
해결책


2
두 개의 숫자를 추가
중간
link
link


필터를 설정하는 것을 잊었으므로tag:two pointers 추가 문제는 두 개의 포인터에 관한 것이 아닙니다.

문제는 단순히 우리가 초등학교에서 배운 방식으로 정수 덧셈을 구현하는 것입니다.

가장 오른쪽 숫자부터 시작하여 더하고 모듈로 합계를 기록하고 올림하고 다음 숫자에서 과정을 반복합니다.

조심스럽게 다루어야 할 두 가지가 더 있습니다. 숫자는 같은 길이가 아닐 수 있으며 마지막 캐리를 추가하는 것을 잊지 마십시오.

복잡성은 O(n) 시간과 O(n) 공간입니다.

결론

오늘의 5문제는 지난 시간보다 더 간단합니다. 완료하는 데 약 50 분이 걸렸습니다.
다음에는 3개의 중간 문제가 나옵니다. 더 흥미롭게 읽을 수 있기를 바랍니다.


<-- | | 다음 -->