Tech for good

1. Linear Searchclass Solution: def search(self, nums: List[int], target: int) -> int: for i in range(len(nums)): if target == nums[i]: return i return -1Time Complexity: O(n)2. Binary SearchBinary Search, Tree -> Narrow down the scope w/ starter, end and middle!There are two ways for a Binary Search.1. Two pointer + while loop2. Recursion2.1. Two point..

1. General while loop & for loop# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: length = 0 curr = head while curr: curr = curr.next length += 1 mid = length // 2..

Look through Example g = child A want 1 number of cookie, child B want 2 number of cookies, child C want 3 number of cookiess = cookie A is 1 number of cookie, cookie B is 2 number of cookiesclass Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() child = 0 # pointer to children cookie = 0 # pointer to cookies whi..

Two Pointers Approach (O(n) 시간, O(1) 공간)뒤에서부터 문자열을 처리하면서 '#'을 만나면 백스페이스를 적용한다.각 문자열에 대해 유효한 문자 위치를 찾아 비교한다.포인터를 이동하면서 문자 비교를 진행한다.class Solution: def backspaceCompare(self, s: str, t: str) -> bool: # 두 개의 포인터를 각각 문자열 s와 t의 끝에서 시작 i, j = len(s) - 1, len(t) - 1 # 백스페이스('#')의 개수를 추적하는 변수 back_s, back_t = 0, 0 # 두 문자열 중 하나라도 아직 탐색할 문자가 남아있는 동안 반복 whil..

class Solution: def reverseVowels(self, s: str) -> str: left, right = 0, len(s) - 1 vowels = set('aeiouAEIOU') # 대소문자 모두 포함된 집합 s = list(s) # 문자열을 리스트로 변환 (문자 교환을 위해) while left 주요 사항: in 연산자 사용s[left] in vowels를 사용.대소문자 포함된 set 사용set('aeiouAEIOU')를 사용하여 in 연산을 빠르게 수행.set은 해시 테이블을 기반으로 동작하므로, 요소가 존재하는지 확인하는 연산(in 연산자)이 평균적으로 O(1) (상수 시간)에 수행.반면, list나 tup..

https://neetcode.io/problems/is-palindrome NeetCode neetcode.io첫번째 방법 - String Manipulationclass Solution: def isPalindrome(self, s: str) -> bool: # 1. 알파벳과 숫자만 남기고 소문자로 변환 filtered_s = ''.join(c.lower() for c in s if c.isalnum()) # 2. 문자열을 뒤집어서 원래 문자열과 비교 return filtered_s == filtered_s[::-1]isalnum() -> 문자열이 문자 혹은 숫자로 되어있으면 참 리턴, 아니면 거짓 리턴시간 복잡도문자열 필터링: O..

첫번째 방법 (Two-Pointer + Queue = Greedy)(1) Two-Pointer 두 개의 리스트 (positives, negatives)를 따로 저장한 후, 두 개의 포인터를 이용하여 한 번에 두 리스트를 합치는 방식 차용.여기서 zip(positives, negatives)를 사용하여 두 리스트를 같은 인덱스에서 번갈아가며 가져오는 방식을 적용.(2) Queue Python의 리스트 (list)를 Queue처럼 사용하여 양수와 음수를 저장했다가 순차적으로 가져와서 최종 리스트를 생성하는 방식.positives.append(num) 및 negatives.append(num) 연산은 O(1) 이므로 효율적임.여기서 zip(positives, negatives)를 사용하여 두 리스트를 같은 인..

📌 코드 설명: 문자열 압축 알고리즘이 코드는 연속된 문자를 압축하여 원래 배열을 수정하는 문제를 해결한다.🛠 코드의 핵심 개념투 포인터(Two-Pointer) 기법 사용i → 원본 문자열을 읽어가는 포인터write → 압축된 문자열을 저장하는 포인터반복문을 사용해 같은 문자가 연속되는 그룹을 찾고, 압축하여 저장그룹의 길이가 1이면 문자만 저장그룹의 길이가 2 이상이면 "문자 + 숫자(횟수)" 형태로 저장class Solution: def compress(self, chars: List[str]) -> int: write = 0 # 압축된 결과를 저장할 위치 i = 0 # 원본 배열을 탐색하는 위치 while i 1: for..

해결 방법: 투 포인터(Two Pointers)이 문제를 O(n log n) 정렬로 해결하는 것은 쉽지만, O(n) 시간 복잡도로 해결하려면 투 포인터(Two Pointers) 기법을 사용해야 한다.핵심 아이디어음수가 포함된 정렬된 배열에서, 가장 큰 제곱값은 절댓값이 가장 큰 수에서 나온다.배열에서 절댓값이 가장 큰 숫자는 양쪽 끝에 위치해 있다. (가장 작은 수는 음수이고, 가장 큰 수는 양수이므로)왼쪽(left)과 오른쪽(right)에서 시작하는 두 개의 포인터를 사용하여 가장 큰 제곱값을 뒤에서부터 채운다.class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) # 주어진 배열의 길이..

풀이1) set  자료구조 사용class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return list(set(nums1) & set(nums2))시간 복잡도 분석set(nums1): O(N)set(nums2): O(M)set1 & set2: O(min(N, M))list(...): O(K) (교집합 원소 수를 K라고 가정)➡️ 최종 시간 복잡도: O(N + M) (매우 효율적)풀이2) two-pointer 사용class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: ..