반응형 투포인터5 [LeetCode] 3. Longest Substring Without Repeating Characters [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (중복 문자 없는 가장 긴 부분 문자열) 중복 문자가 없는 가장 긴 부분 문자열의 길이를 출력하라. 2. 풀이 해시와 투 포인터를 이용한 풀이 부분 문자열의 처음과 끝에 포인터를 위치 중복이 없으면 끝을 오른쪽으로 이동 중복이 있을 경우 처음을 오른쪽으로 이동 3. 코드 해시와 투 포인터를 이용한 풀이 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ret, start = 0, 0 used = {} for idx, char in enumerate(s): if char in used and start 2021. 11. 23. [LeetCode] 42. Trapping Rain Water [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (빗물 트래핑) (출처) 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 2. 풀이 (출처) 위 그림처럼 최대 높이의 막대까지 각각 좌우 기둥 최대 높이와 현재 높이와의 차이만큼 물 높이를 더해 나간다. 스택을 이용한 풀이 (출처) 위 그림처럼 높아질 경우 변경된 높이만큼 물을 추가한다. 3. 코드 투 포인터를 이용한 풀이 class Solution: def trap(self, height: List[int]) -> int: # 종료 조건 if not height: return 0 ret = 0 left, right = 0, len(height)-1 left_max, right_max = he.. 2021. 11. 23. [LeetCode] 15. 3Sum [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (세 수의 합) 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. (중복된 엘리먼트 조합은 제외!!) 2. 풀이 투 포인터를 이용한 풀이 (출처) 오름차순으로 정렬 for문을 통해 (해당 value, 다음 value, 마지막 value) 3개의 합을 계산한다. 합이 0보다 크면 다음 value를 오른쪽으로 한칸 이동 합이 0보다 작으면 마지막 value를 왼쪽으로 한칸 이동 value가 이전값과 중복될 경우 continue 3. 코드 투 포인터를 이용한 풀이 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: ret =.. 2021. 11. 23. [LeetCode] 5. Longest Palindromic Substring [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (가장 긴 팰린드롬 부분 문자열) 가장 긴 펠린드롬 부분 문자열을 출력하라. (정답이 여러개 일 수 있는데 나는 가장 첫번째 부분 문자열을 출력하겠다.) 2. 풀이 투 포인터를 이용한 풀이 (출처) 그림과 같이 2칸, 3칸으로 구성된 투 포인터를 슬라이딩 윈도우처럼 오른쪽으로 한칸씩 이동하며 팰린드롬을 확인한다. 3. 코드 class Solution: def longestPalindrome(self, s: str) -> str: # 팰린드롬 판별 및 포인터 확장 def expand(left, right): while left >= 0 and right 2021. 11. 23. [LeetCode] 344. Reverse String [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (문자열 뒤집기) 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며，리턴 없이 리스트 내부를 직접 조작하라. 2. 풀이 투 포인터를 이용한 풀이 reverse()를 이용한 문제 풀이 3. 코드 투 포인터를 이용한 풀이 class Solution: def reverseString(self, s: List[str]) -> None: left, right = 0, len(s) - 1 while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1 reverse()를 이용한 풀이 class Solution: def reverseString(.. 2021. 11. 23. 이전 1 다음 반응형