일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Substring with Concatenation of All Words
- DWG
- Generator
- iterator
- Regular Expression
- shiba
- 30. Substring with Concatenation of All Words
- 밴픽
- t1
- 315. Count of Smaller Numbers After Self
- concurrency
- Convert Sorted List to Binary Search Tree
- Decorator
- Python Code
- attribute
- kaggle
- 파이썬
- 프로그래머스
- data science
- 컴퓨터의 구조
- 715. Range Module
- Protocol
- 시바견
- 109. Convert Sorted List to Binary Search Tree
- Python
- 운영체제
- LeetCode
- 43. Multiply Strings
- Python Implementation
- Class
- Today
- Total
목록Computer Science/Coding Test (225)
Scribbling
Refer to the below post for Knuth Shuffle. https://focalpoint.tistory.com/253 Shuffle Algorithm: Knuth Shuffle This post is about Knuth Shuffle, a shuffle algorithm. - This algorithm allows random shuffle, giving all permuations of array equal likelihood. - No need for additional arrays, so memory complexity.. focalpoint.tistory.com class Solution: def __init__(self, nums: List[int]): self.nums ..
Coming up with O(1) memory solution was very difficult for me. I refered to this post's last solution. https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/1322101/C%2B%2BJavaPython-MaxHeap-MinHeap-Binary-Search-Picture-Explain-Clean-and-Concise [C++/Java/Python] MaxHeap, MinHeap, Binary Search - Picture Explain - Clean & Concise - LeetCode Discuss Level up your coding s..
Making a new list is an easy solution to implement with recursion. class NestedIterator: def __init__(self, nestedList: [NestedInteger]): self.res = [] self._flattener(nestedList) self.ptr = 0 def _flattener(self, nestedList): for nl in nestedList: if nl.isInteger(): self.res.append(nl.getInteger()) else: self._flattener(nl.getList()) def next(self) -> int: ret = self.res[self.ptr] self.ptr += 1..
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