gaki gaki

191. Number of 1 Bits 방법_#1 파이썬에서 정수를 2진수로 변환하는 bin 함수를 사용한다. bin(num:int) => string (2진수) class Solution: def hammingWeight(self, n: int) -> int: c = collections.Counter(bin(n)[2:]) return c["1"]방법_#2 비트 shift 를 활용한다 import collections class Solution: def hammingWeight(self, n: int) -> int: cnt = 0 while (n): if (n & 1): cnt += 1 n = n >> 1 return cnt

방법_#1 단순 반복문으로 푸는 방법 class Solution: def isPowerOfTwo(self, n: int) -> bool: cnt = 0 if (n < 1): return False while (n != 1): m = n % 2 if (m == 0): n /= 2 else: break ; if (n == 1): return True else: return False 방법_#2 비트연산으로 계산하는 방법 2^0 = 1 2^1 = 10 ( 2^1 - 1 = 01) 2^2 = 100 ( 2^2 - 1 = 011) 2^3 = 1000 ( 2^3 - 1 = 0111) 2^4 = 10000 ( 2^4 - 1 = 01111) 이 특징을 활용해서 2 ^ n 과 (2 ^ n) - 1 을 비트연산하면 값이 ..

풀이_#1 재귀를 활용한 풀이 => 메모이제이션을 활용해서 빠름 class Solution: def climbStairs(self, n: int) -> int: dp = [0] * (n+1) dp[1] = 1 if (n >= 2): dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] 풀이_#2 재귀를 활용한 풀이 - 숏코딩, 간략 => 시간초과걸림 def climbStairs1(self, n): if n == 1: return 1 if n == 2: return 2 return self.climbStairs(n-1)+self.climbStairs(n-2)

import copy class Solution: def permute(self, nums: List[int]) -> List[List[int]]: n = len(nums) r = [] visited = set() def rec(l): if len(l) == n: r.append(copy.deepcopy(l)) return ; for i in nums: if i not in visited: visited.add(i) l.append(i) rec(l) l.remove(i) visited.remove(i) l = [] for i in nums: visited.add(i) l.append(i) rec(l) visited.remove(i) l.remove(i) return r풀이_#2 깔끔하고 정돈된 풀이. *..

77. Combinations 풀이_#1 재귀를 돌려서 풀었슴! import copy class Solution: def combine(self, n: int, k: int) -> List[List[int]]: r = [] visited = [0] * (n + 1) def rec(l): if (len(l) == k): r.append(copy.deepcopy(l)) return ; nowNum = l[-1] for i in range(nowNum + 1, n+1): l.append(i) rec(l) l.remove(i) for i in range(1, n + 2 - k): l = [i] rec(l) l.remove(i) return r

[LeetCode] 206. Reverse Linked List 풀이_#1 반복문 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: curr = head if (not curr): return None before = None while(curr): temp = curr.next curr.next = before before = curr curr = temp return..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: node = ListNode() r = node while (list1 or list2): num1, num2 = 101, 101 if (list1): num1 = list1.val if (list2): num2 = list2.val node.next = ListNod..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: node = ListNode() r = node while (list1 or list2): num1, num2 = 101, 101 if (list1): num1 = list1.val if (list2): num2 = list2.val node.next = ListNod..