Scribbling

Each of programming language has their own way of 'Integer Representation'. In most languages, integers are represented with 32 bits and the most significant bit (the leftmost bit) is for the sign of it. As a result, usual '32-bit int representation' has range of [-2**31+1, 2**31]. * 2**31 (INT_MAX) is 0xFFFFFFFF * -2*31+1 (-INT_MAX) is 0x80000000 (by 2's complement) However, python has somewhat..

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],..

Below is my own python implementation of AVL Tree. Feel free to use it and refer to the bottom most part of the code to see how it works. As there are already so many materials dealing with the algorithms of AVL data structure, I won't explain about them at this article. Instead, I upload a concise implementation of AVL tree. class TreeNode: def __init__(self, val): self.val = val self.left = No..

Below is the python implementation of segment tree data structure. Segment tree is often used to query range sum within O(logN) time complexity. As it is storing range information of the data, this data structure can be useful when you are looking for information on the basis of various ranges. * Below implementation is for range sums. class SegmentTreeNode: def __init__(self, start, end, val, l..

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