일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 715. Range Module
- t1
- DWG
- Python Implementation
- Substring with Concatenation of All Words
- 43. Multiply Strings
- 시바견
- LeetCode
- Regular Expression
- Decorator
- shiba
- 109. Convert Sorted List to Binary Search Tree
- kaggle
- iterator
- Protocol
- Convert Sorted List to Binary Search Tree
- 컴퓨터의 구조
- 파이썬
- Python
- attribute
- 밴픽
- Python Code
- 30. Substring with Concatenation of All Words
- concurrency
- Generator
- Class
- 운영체제
- data science
- 프로그래머스
- 315. Count of Smaller Numbers After Self
- Today
- Total
목록LeetCode (205)
Scribbling
This problem is a special case of #300, which is LIS. Refer to LIS algorithm here. https://focalpoint.tistory.com/179 LeetCode: 300. Longest Increasing Subsequence - 시바견의 끄적임 1. 가장 간단한 DP 형태 O(N**2)이다. class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [0] * len(nums) dp[0] = 1 for i in range(1, len(nums)): temp = -1 j = i - 1 while j >= 0: if n.. focalpoint.tistory.com class So..
Tip of the day: A problem starts with "Longest" usually has something to do with DP. Though the difficulty is hard, it's not a difficult one. Seeing the below code will be enough for sure, so I won't give any explanation about it. class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) self.matrix = matrix self.visited = [[False] * n fo..
Using double counters. class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: from collections import Counter c1 = Counter(nums1) c2 = Counter(nums2) ret = [] for k in c2.keys(): ret.extend([k] * min(c1[k], c2[k])) return ret
This is a typical DP problem. At first, one should think of backtracking all the cases. That way, you can find the solution but it isn't efficient. In the meantime, you should notice that you will calculate for the same amount repeatedly when backtracking all the cases. Inspired by that idea, apply DP there. Below is the code. INF = int(1e9) class Solution: def coinChange(self, coins: List[int],..
Use dummy head to simplify code. # 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, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy_head = ListNode() cur, p1, p2 = dummy_head, l1, l2 while p1 != None and p2 != None: if p1.val
O(N), O(1) Solution by using input array as a memory. class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: ret = [] for i, num in enumerate(nums): if nums[abs(num) - 1] < 0: ret.append(abs(num)) nums[abs(num) - 1] *= -1 return ret
The first solution is using binary search. class Solution: def missingNumber(self, nums: List[int]) -> int: left, right = 0, len(nums) while left < right: mid = (left + right) // 2 cnt = 0 for num in nums: if num int: ret = len(nums) * (len(nums) + 1) // 2 for num in nums: ret -= num return ret
My own code is always messy. The idea is to sort the list and calculate sums. Time complexity will be O(NlogN) due to sorting. class Solution: def numPairsDivisibleBy60(self, time: List[int]) -> int: time = [t % 60 for t in time] time.sort() ret = 0 l, r = 0, len(time) - 1 while l < r: if time[l] + time[r] == 60: if time[l] == 30: cnt = 0 while l 0 else c[0] c[t] += 1 return ans
My somewhat complicated code using queue. Both time and memory complexities are O(N). # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return '' ret = str(root.val) + ' ' q = [r..
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None odd_ptr = head even_ptr = even_head = ListNode() cur = head.next cnt = 2 while cur != None: if cnt % 2 != 0: odd_ptr.next = cur odd_ptr = cur else: even_pt..