본문 바로가기
반응형

algorithm/leetcode26

Linked List Cycle [leetcode] 코드 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: num_list = [] curr = head while True: if curr == None: return False if curr not in num_list: num_list.append(curr) curr = curr.next else: return True 문제 풀이 과정 설명 나는 지나는 모든 노드를 리스트에 저장한 뒤, 사이클이라면 리스트에 중복되는 노드가 분명.. 2022. 3. 9.
Arithmetic Slices [leetcode] 문제 https://leetcode.com/problems/arithmetic-slices/ Arithmetic Slices - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제풀이 아... 풀었는데 소 뒷걸음 치다 벌레 잡은 격이 느낌이다. 부분배열(contiguous subsequence of the array) 이 등차수열을 만족하는지 확인하고 맞다면 개수를 +1 해주는 문제였다. 부분배열을 검증하는 방법은 해당 배열의 모든 숫자와 등차수열 합공식에 넣은.. 2022. 3. 3.
Remove K Digits [leetcode] 문제링크 문제 풀이 Input: num = "1432219", k = 3 Output: "1219" 첫번째 풀이 처음에는 앞 숫자와 뒤 숫자를 비교해서 뒤 숫자가 크면 해당 숫자를 지우는 로직인줄 알았다. 그럼 위 예시로 보면 1 : “4” 32219→ 4가 크므로 4를 지운다 ⇒ 132219 (k =2) 1 : “3” 2219→ 3이 크므로 3을 지운다 ⇒ 12219 (k=1) 1 : “2” 219→ 2가 크므로 2를 지운다 ⇒ 1219 (k=0 이므로 종료) 그럼 정답으로 1219 이므로 쉽게 푼줄 알았다. 하지만 반례로 Input: num = "12345", k = 2 Output: "123" 위 반례가 있다. 1 : 2 → 2가 크므로 2를 지운다 ⇒ 1345 (k=1) 1 : 3 → 3이 크므로.. 2022. 2. 19.
Swap Nodes in Pairs [leetcode] 문제 문제 풀이 정리 의외로 머리속에서 정리가 안되던 문제였다. 그림을 보면 알겠지만 짝수 일때만 자리를 바꿔줘야 한다. 하지만 List(배열) 이 아니고 Linked List 이기 때문에 인덱스로 접근할 수 없다. 그래서 even_flag를 만들어서 마치 짝수일때만 동작할 수 있도록 한다. 현재 위치가 짝수일 때와 홀수일 때 로직이 다른데 적어보자. 홀수일 때 현재 노드는 이전 노드로 지정한다. (prev = curr) 현재 위치를 다음 노드로 옮긴다.(혹은 지정한다.) (curr = curr.next) 짝수 플래그를 true로 변경한다. if even_flag == False: prev = curr curr = curr.next even_flag = True 짝수일 때 이전 노드의 next를 현재 노.. 2022. 2. 16.
Subsets [leetcode] 문제 Subsets - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제풀이 문제 예시로 나온 답을 보고 풀게 되었다. Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 규칙이 보이는가? output 에 처음에는 [] (빈 리스트) 공집합 하나만 추가해준다. num = 1 일때, output 을 순회하면서 이전 집합에 1을 추가한다. (temp_list = [] + 1 = [1]).. 2022. 2. 13.
Permutation in String [leetcode] 문제 문제 풀이 문자열의 퍼뮤테이션 이 존재하는지 여부 판단 문제이다. 문자열의 퍼뮤테이션은 문자열의 길이가 길어질수록 연산량이 급격히 증가하기 때문에 다른 식으로 풀었는데 바로 dictionary (다른말로 Map) 이다. 순서만 바뀐 문자열의 경우, 사용된 문자와 해당 문자 개수가 같다는 점을 이용해 { “a” : n개, “b” : m개, ...} 등으로 나타내 같은 키 값을 가지고 있는지, 서로 다른 키가 존재하지 않는지 여부 같은 키 값에 대해 동일한 수량을 가지고 있는지 여부 를 검사하면 퍼뮤테이션 연산을 피할 수 있다. 코드상으로는 dictionary를 만드는 함수 dictionary 2개를 서로 비교하는 함수 를 구성했다. #dictionary를 만드는 함수 def dictCreate(sel.. 2022. 2. 11.
K-diff Pairs in an Array [leetcode] 문제 풀이 리스트 안 숫자들 중 차이의 절대값이 k를 만족하는 숫자 쌍 의 개수를 찾는 문제다. 한국말로 한문장 정리하니 “의” 로 연결된게 많아 국어지문 푸는것 같다. 다시 정리하자. 리스트 안 숫자들 중 ⇒ ex. [3,1,4,1,5] 차이의 절대 값 ⇒ ex. |3 - 1| = 2 k를 만족하는 숫자 쌍 count! ⇒ ex. |3-1| == 2 ? (count +1) : nothing! 문제를 보면 리스트의 중복된 숫자가 있어도 1개로 친다고 한다. 그럼 로직상 중복체크도 필요하다는 얘기다. 나는 이렇게 풀었다. 현재 비교할 숫자 = nums[i] 비교 당해야 할 숫자들 = nums[i+1:] (중복을 피하기 위해 i 번째 이후 숫자들만 사용) 중복을 피하기 위해 num_set 생성 ⇒ num_s.. 2022. 2. 9.
Find All Anagrams in a String [leetcode] 문제 https://leetcode.com/problems/find-all-anagrams-in-a-string/ Find All Anagrams in a String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 설명 긴 문자열 (이하 s) 에서 짧은 문자열(이하 p)의 anagram(알파벳 순서를 바꾼 문자열) 을 찾는 문제이다. 해당 문자열이 s에서 발견될 경우, 발견된 위치를 전부 리턴하면 되는 문제이다. anagram은 문자의 순서를 바꿔.. 2022. 2. 2.
Linked List Random Node [leetcode] 문제 Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen. Implement the Solution class: Solution(ListNode head) Initializes the object with the integer array nums. int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen. Example 1.. 2022. 1. 7.
반응형

티스토리툴바