编程flag

Study PV:

前言

其实我一直觉得自己编程能力很差，还记得高三时技术程序大题总是做不对。大一也只上了一门python课，c++完全都是自己看书，加上Robomaster队里搬运网上的代码。在大一暑假，我报名了一个sjtu的data structure课程，midterm是以leetcode面试的形式展开（据说Prof.Xin Hongyi自掏腰包花了900块RMB），我喜提三道程序大题只得3分（50分满分）。我至今忘不了那种沮丧与自我怀疑，然后考完立刻跟Prof聊了近一个小时…

现在依然很感动，感谢辛弘毅教授

然而我最大的毛病就是好了伤疤忘了疼，今天是8.4，我可以说相较于前一至两个月，我的编程能力还处于原地。所以以此帖为誓，在接下来的三年里，定期做题保持手感。

其实我是一个很笨的人，所以要更加努力。

Update：找到了一个也愿意做编程题的大佬，希望因此能坚持下去

Update：最终还是落到了孤身一人的境地，希望自己一直保有做题的念头

Step One: Decal

Leetcode 101 | Introduction to Algorithmic Thinking是一个由UC Berkeley学生自己组织的课程。

Beginning to try python instead.

Week One

From slides

Designing efficient solutions:

  1. Understand the problem
    Think about problems that you’ve done before that are similar to this one
    Run through a few small examples
    Ask clarifying questions
  2. Brute force solution
    Often all permutations, all pairs etc.
    May not help you that much, because the optimal solution is often very different from the brute force
    But it’s better to have something rather than nothing
  3. Try to match problem solving patterns to this problem
    You have a toolbox of data structures and algorithms at your disposal
    In cs61a, you learned a recursive way of thinking you can apply to a range of problems
    This course is designed to expand your toolbox
  4. Implement your solution
    Once you figure out your approach, this is often muscle memory
    Run a test case
    Should I optimize further?

Two data structures:
sets and dictionary

Contains Duplicate

判断是否有重复出现的元素
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

1
2
3
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

这里很巧妙地运用了set，但是time complexity是 O(n)
也可以用loop的写法（突然想起来Bloom Filter）：

1
2
3
4
5
6
7
8
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        s = set()
        for i in nums:
            if i in s:
                return True
            s.add(i)
        return False

这样的话time complexity虽然也是O(n)，但实际上是O(cn)，c是一个between 0 and 1的constant

Two Sum

找出array里面两个元素，使得他们的和等于目标元素的值
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i , n in enumerate(nums):
            m = target - n
            if m in d:
                return [d[m],i]
            else:
                d[n] = i

直接使用dictionary即可解决 (使用hash map)

* Best Time to Buy and Sell Stock

找到元素间最大的差值，且小的在前大的在后
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price ,max_price = float("inf") , 0
        for price in prices:
            min_price = min (min_price,price)
            profit = price - min_price
            max_price = max(max_price,profit)
        return max_price

随时跟踪最小值和最大差值
这里没必要去跟踪最大值，要不然会引入新的变量

还有一种是跟踪相邻元素累计差值的，Kadane’s Algorithm，原先实现在largest sum contiguous array上，似乎c++更容易实现：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.size(); i++) {
            maxCur = max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }
};

当差值小于0以后就重新赋值为0
这里可以举一个例子。[1,3,5,9,2,4],计算 (3-1)+(5-3)+(9-5) = 9-1并储存到maxSoFar，接下来从0开始，计算(4-2)

Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

思路很好想，先做一个排序，之后逐一比较。
只是写的时候很容易复杂化。

1
2
3
4
5
6
7
8
9
10
11
 vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if(intervals.size()<=1) return intervals;
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> output;
    output.push_back(intervals[0]);
    for(int i=1; i<intervals.size(); i++) {
        if(output.back()[1] >= intervals[i][0]) output.back()[1] = max(output.back()[1] , intervals[i][1]);
        else output.push_back(intervals[i]); 
    }
    return output;
}

这个时候功底就显现出来了QwQ，为啥别人的这么简洁
这里的output.back()可以留意一下

Python的差不多，留意写法

1
2
3
4
5
6
7
8
def merge(self, intervals):
    out = []
    for i in sorted(intervals, key=lambda i: i.start):
        if out and i.start <= out[-1].end:
            out[-1].end = max(out[-1].end, i.end)
        else:
            out += i,
    return out

* Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
输出除该元素外其他元素的乘积，复杂度O(n)且不能用除法

思路：保存两个list，分别存有从左到该元素的乘积以及从右到该元素的乘积
solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    left = []
    right = [1]*n  ##预先设置好list的大小，从右向左改变内部的值。如果每次都resize会导致O(n^2)
    output = []
        
    left_prod = 1
    for el in nums:
        left.append(left_prod)
        left_prod *= el
        
    right_prod = 1
    i = n-1
    while i >= 0:
        right[i] = right_prod
        right_pod *= nums[i]
        i-=1
        
    for i in range(n):
        output.append(left[i]*right[i])
        
    return output

Optimized：只用一个list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    output = [1] * n

    for i in range(1, n):
        output[i] = output[i - 1] * nums[i - 1]
    
    prod = 1
    i = n - 1
    while i >= 0:
        output[i] *= prod
        prod *= nums[i]
        i -= 1
    
    return output

Week Two

Add Two Numbers

给出两个linked list，每一位相加
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

思路正常，看看python怎么写
这里尤其注意dummy = cur = ListNode(0)这样写是可以的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = cur = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry%10)
            cur = cur.next
            carry //= 10
        return dummy.next

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

思路好想，这里主要注意一下recursive方法

Iterative Solution. 一个一个修改node。注意edge case的处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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]:
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt      
        return pre

Recursive Solution.
有些难以理解。首先想清楚base case是什么（空的和只有一个）。然后先递归找到最末端的node。这里new_head 的值找到以后就不会再变化，相当于把new_head 一层一层pass上去。同时修改每个node的指向

1
2
3
4
5
6
7
8
9
10
11
12
13
# 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]:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Reverse Linked List ii

翻转linked list其中一部分node的顺序。
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

第一次做用了stack，才发现python里没有delete这种操作。“ If nothing points to the node (or more precisely in Python, nothing references it) it will be eventually destroyed by the virtual machine anyway.”
python的del不同于C的free和C++的delete，实际上类似于解引用 。

回顾昨天的 Reverse Linked List ，其实可以想到把linked list部分进行reverse，然后重新链接。尤其注意一下最后链接的部分

solution

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
class Solution:
    # @param head, a ListNode
    # @param m, an integer
    # @param n, an integer
    # @return a ListNode
    def reverseBetween(self, head, m, n):
        if m == n:
            return head

        dummyNode = ListNode(0)
        dummyNode.next = head
        pre = dummyNode

        for i in range(m - 1):
            pre = pre.next
        
        # reverse the [m, n] nodes
        reverse = None
        cur = pre.next
        for i in range(n - m + 1):
            next = cur.next
            cur.next = reverse
            reverse = cur
            cur = next

        pre.next.next = cur
        pre.next = reverse

        return dummyNode.next

* Flatten a Multilevel Doubly Linked List

题目有点长，每个node有next，pre，child三个pointer，child pointer 指向另一个linked list，从而形成“Multilevel Doubly Linked List”。所要做的是将他们flatten成一个linked list。

像一张张人脸ww

这里主要学一下recursion是如何解决的。
首先搭好一个框架：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        ptr = head
        while ptr:
            if ptr.child:
                # do something
            
            else:
                ptr = ptr.next
        
        return head

很显然，我们的flatten function返回一个flattened linked list。因为是recursion解决，我们只用考虑一种情况，就是一共有两层的“Multilevel Doubly Linked List”

example

我们在得到这个”flattened sub linked list”以后，需要对其中一些pointer做调整。也就是一头一尾的pre/next pointer，还要把最头上的child pointer改成None。由此我们完善代码，同时加上一个得到一个linked list末端的tail函数。

其实到这里我们已经写好全部的代码了，我们call flatten可以直接得到”flattened sub linked list”

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
class Solution:
    def tail(self,head):
        tmp = head
        while tmp.next:
            tmp = tmp.next
        return tmp
    
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        ptr = head
        while ptr:
            if ptr.child:
                next_ptr = ptr.next
                flattened_child = self.flatten(ptr.child)
                ptr.next = flattened_child
                flattened_child.prev = ptr
                
                flattened_child_tail = self.tail(flattened_child)
                flattened_child_tail.next = next_ptr
                
                # Don't forget to consider the edge case, whether next_ptr is None or not 
                if next_ptr:
                    next_ptr.prev = flattened_child_tail
                
                ptr.child = None
                ptr = next_ptr #directly go to the node after the flattened sub linked list 
            
            else:
                ptr = ptr.next
        
        return head

太美妙了ww

* Remove Nth Node From End of List

去掉倒数第n个node

Given the head of a linked list, remove the nth node from the end of the list and return its head.

recursion解决：
这里关注一下两个square brackets，以及return一个pair的方法(这种判断语句的写法也太神奇了)

1
2
3
4
5
6
7
8
class Solution:
    def removeNthFromEnd(self, head, n):
        def remove(head):
            if not head:
                return 0, head
            i, head.next = remove(head.next)
            return i+1, (head, head.next)[i+1 == n]   //if i+1== n, return head.next 
        return remove(head)[1]  //return head from a pair (index,node)

双指针解决
hint：Maintain two pointers and update one with a delay of n steps.Do this in one pass.
要学会常用for _ in range()这种语句 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def removeNthFromEnd(self, head, n):
        fast = slow = head
        for _ in range(n):
            fast = fast.next
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

Merge Two Sorted Lists

给定两个sorted linked list. Merge the two lists in a one sorted list and return its head.

方法很好想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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]:
        dummy = output = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                output.next = list1
                output = output.next
                list1 = list1.next
            else:
                output.next = list2
                output = output.next
                list2 = list2.next 
        output.next = list1 if list1 else list2  ##注意这里的tenary operation，跟c++差不多
        
        return dummy.next

* Merge k Sorted Lists

给定k个sorted linked list,进行merge

首先想到的是用类似于merge sort的方法

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
32
33
34
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeHelper(self,l1,l2):
        cur1 = l1
        cur2 = l2
        dummy = output = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                output.next = l1
                output = output.next
                l1 = l1.next
            else:
                output.next = l2
                output = output.next
                l2 = l2.next
        output.next = l1 if l1 else l2
        return dummy.next
    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        
        if not k:
            return
        if k == 1:
            return lists[0]

        mid = k // 2
        l, r = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]) ##注意这里的截取方法
        
        return self.mergeHelper(l, r)

第二种方法是用priority queue。
这里存储list_idx的目的是遇到node.val相同的情况，priority queue会比较后一位，如果没有list_idx则会比较node从而产生error(not a comparable type)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from queue import PriorityQueue
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        q = PriorityQueue(maxsize=k)
        dummy = ListNode(None)
        curr = dummy
        for list_idx, node in enumerate(lists):
            if node: q.put((node.val, list_idx, node))
        while q.qsize() > 0:
            poped = q.get()
            curr.next, list_idx = poped[2], poped[1]
            curr = curr.next
            if curr.next: q.put((curr.next.val, list_idx, curr.next))
        return dummy.next

Week Three

Search a 2D Matrix

给定一个从左往右，从上往下sorted 2D matrix,寻找给定的target

用binary search，主要注意可以把matrix看作list，不要用nested while loop寻找行，列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m,n = len(matrix),len(matrix[0])
        left , right = 0, n*m-1
        while left <= right:
            mid = (left + right) // 2
            ele = matrix[mid // n][mid % n]
            
            if target < ele:
                right = mid - 1
            elif target > ele:
                left = mid + 1
            else:
                return True
        return False

还有一种方法使用bisect.bisect_left()
bisect_left(list, num, beg, end) :- This function returns the position in the sorted list, where the number passed in argument can be placed so as to maintain the resultant list in sorted order. If the element is already present in the list, the left most position where element has to be inserted is returned. This function takes 4 arguments, list which has to be worked with, number to insert, starting position in list to consider, ending position which has to be considered.

1
2
3
4
5
6
7
8
class Solution:
    def searchMatrix(self, matrix, target):
        i = bisect.bisect_left(matrix, [target])   ##找到行
        if i < len(matrix) and matrix[i][0] == target:
            return True
        row = matrix[i-1]
        j = bisect.bisect_left(row, target)
        return j < len(row) and row[j] == target

Find First and Last Position of Element in Sorted Array

给定一个sorted list，返回target出现的起始位和末尾位
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].

  1. 两次binary search

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
        def searchRange(self, nums, target):
            def search(n):
                lo, hi = 0, len(nums) - 1
                while lo <= hi:
                    mid = (lo + hi) // 2
                    if nums[mid] >= n:
                        hi = mid - 1 
                    else:
                        lo = mid + 1
                return lo
            if not len(nums):
                return [-1,-1]
            lo = search(target)
            return [lo, search(target+1)-1] if target in nums[lo:lo+1] else [-1, -1]
            # slicing 如果越界了不会报错，会返回一个empty list

  2. 使用recursion, divide and conquer

理解为先

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchRange(self, nums, target):
        def search(lo, hi):
            if nums[lo] == target == nums[hi]:
                return [lo, hi]
            if nums[lo] <= target <= nums[hi]:
                mid = (lo + hi) // 2
                l, r = search(lo, mid), search(mid+1, hi)
                return max(l, r) if -1 in l+r else [l[0], r[1]]
            return [-1, -1]
        if not len(nums):
            return [-1,-1]
        return search(0, len(nums)-1)

Search Insert Position

给定一个sorted array以及target，`返回target在array中的位置或者应该插入的位置
binary search简单应用

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l , r = 0 , len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l

* Search in Rotated Sorted Array

在部分“rotated“的sorted array进行binary search
感觉似乎很简单，但是如果进行分类讨论的话case很难想清楚。以下方法比较好想：

Explanation

Let’s say nums looks like this: [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Because it’s not fully sorted, we can’t do normal binary search. But here comes the trick:

If target is let’s say 14, then we adjust nums to this, where “inf” means infinity:
[12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

If target is let’s say 7, then we adjust nums to this:
[-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

And then we can simply do ordinary binary search.

Of course we don’t actually adjust the whole array but instead adjust only on the fly only the elements we look at. And the adjustment is done by comparing both the target and the actual element against nums[0].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def search(self, nums: 'List[int]', target: int) -> int:
        lo, hi = 0, len(nums) -1
        while lo <= hi:
            mid = (lo + hi) // 2
        
            num = nums[mid] if (nums[mid] < nums[0]) == (target < nums[0]) \ 
                    #如果nums[mid]和target在同一边，则返回nums[mid]
                    else (-math.inf if target < nums[0] else math.inf)
                    # 如果不是的话，将其返回成-INF or INF 以进行之后的binary search
            if num < target:
                lo = mid + 1
            elif num > target:
                hi = mid - 1
            else:
                return mid
        return -1

其实最直接的方法就是分成两个array进行binary search，难的是如何找到pivot。这里使用的方法是寻找最小元素

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
32
33
34
35
class Solution:
    def find_pivot(self,nums):
        pivot = 0
        smallest_value = math.inf
        left = 0
        right = len(nums)-1
        last_element = nums[-1]
        while left <= right:
            middle = (left+right)//2
            if nums[middle] < last_element:
                right = middle - 1
            else:
                left = middle + 1
            
            if nums[middle] < smallest_value:
                pivot = middle
                smallest_value = nums[middle]
        return pivot
    def binary_search(self,nums,left,right,target):
        while left <= right:
            middle = (left+right)//2
            if nums[middle] == target:
                return middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                right = middle - 1
        return -1
    def search(self, nums: 'List[int]', target: int) -> int:
        if nums[0] <= nums[-1]:
            return self.binary_search(nums,0,len(nums)-1,target)
        pivot = self.find_pivot(nums)
        possible_left = self.binary_search(nums,0,pivot-1,target)
        possible_right = self.binary_search(nums,pivot,len(nums)-1,target)
        return max(possible_left,possible_right)

* Random Pick with Weight

给定一个list w以及对应的weight，随机返回list中的index，且要求返回index i的概率是w[i] / sum(w)

最初想法是weight是几就在一个list里面插入多少个相同的index值，但这么做会产生一个很大的list并且time/space complexity会很差。
较好的方法是记录每位index accumulative weight。比如原先的weight list是[1,5,2]，代表index 0概率是1/8，index 2概率是5/8，index 3概率是2/8。我们存另一个accumulative weight list [1,6,8]，之后生成一个随机数，看落在哪个区间里。

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
class Solution:

    def __init__(self, w):
        """
        :type w: List[int]
        """
        self.w = w
        self.n = len(w)
        for i in range(1,self.n):
            w[i] += w[i-1]
        self.s = self.w[-1]

    def pickIndex(self):
        """
        :rtype: int
        """
        seed = random.randint(1,self.s)
        l,r = 0, self.n-1
        while l <= r:
            mid = (l+r)//2
            if seed <= self.w[mid]:
                r = mid - 1
            else:
                l = mid+1
        return l

或者用内置函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:

    def __init__(self, w: List[int]):
        self.probList = w
        for i in range(1,len(w)):
            self.probList[i] += self.probList[i-1] 
            
            

    def pickIndex(self) -> int:
        maximum = self.probList[-1]
        n = random.randint(1,maximum)
        return bisect.bisect_left(self.probList, n) 

# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

甚至更简

1
2
3
4
5
6
class Solution:
    def __init__(self, w):
        self.w = list(itertools.accumulate(w))

    def pickIndex(self):
        return bisect.bisect_left(self.w, random.randint(1, self.w[-1]))

Find the Smallest Divisor Given a Threshold

给定一个list和一个threshold，找到最小的divisor,使得“ divide all the array by it, and sum the division’s result” “less than or equal to threshold”。

好像没啥说的，注意最后return left就行

1
2
3
4
5
6
7
8
9
10
class Solution:
    def smallestDivisor(self, nums, threshold):
        l, r = 1, max(nums) 
        while l <= r:
            mid = (l + r)//2
            if sum(ceil(num/mid) for num in nums) <= threshold: #注意一下这个语句的写法
                r = mid - 1
            else:
                l = mid + 1        
        return l

* Kth Smallest Element in a Sorted Matrix

给定一个rows and columns sorted in ascending order的matrix, return the kth smallest element in the matrix.

方法一：Maxheap
因为python只有minheap，所以插入的元素要取相反数
缺点是没有利用Matrix是sorted这一个特点
The maxHeap will keep up to k smallest elements (because when maxHeap is over size of k, we do remove the top of maxHeap which is the largest one)

1
2
3
4
5
6
7
8
9
10
class Solution:  
    def kthSmallest(self, matrix, k):
        m, n = len(matrix), len(matrix[0])  # For general, matrix doesn't need to be a square
        maxHeap = []
        for r in range(m):
            for c in range(n):
                heappush(maxHeap, -matrix[r][c])
                if len(maxHeap) > k:
                    heappop(maxHeap)
        return -heappop(maxHeap)

方法二：Minheap
从每一行的头一个元素开始，iterate k次

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:  
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])  # For general, the matrix need not be a square
        minHeap = []  # val, r, c
        for r in range(min(k, m)):
            heappush(minHeap, (matrix[r][0], r, 0)) #先把每一行第一个push到minHeap中，并且记录行，列号

        ans = -1  # any dummy value
        for i in range(k):
            ans, r, c = heappop(minHeap)
            if c+1 < n: heappush(minHeap, (matrix[r][c + 1], r, c + 1)) #把该行后一个元素push进去
        return ans

方法三：Binary Search
space complexity：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:  
    def kthSmallest(self, matrix, k):
        m, n = len(matrix), len(matrix[0])  # For general, the matrix need not be a square

        def countLessOrEqual(x):
            cnt = 0
            c = n - 1  # start with the rightmost column
            for r in range(m):
                while c >= 0 and matrix[r][c] > x: 
                    c -= 1  # decrease column until matrix[r][c] <= x
                cnt += (c + 1)
            return cnt

        left, right = matrix[0][0], matrix[-1][-1]
        ans = -1  # any dummy value
        while left <= right:
            mid = (left + right) // 2
            if countLessOrEqual(mid) >= k:  #注意这里是 >= k,因为可能有相同元素出现
                ans = mid
                right = mid - 1  # try to looking for a smaller value in the left side
            else:
                left = mid + 1  # try to looking for a bigger value in the right side

        return ans

Week Four

From slides

Stacks, Heaps, Queues

  1. Stacks in Python
    Can implement with python list, collections.deque, queue.LifoQueue
    Last In, First Out data structure (LIFO)

    Functions associated with stack:
    1. empty(): returns whether stack is empty - O(1)
    2. size(): returns size of stack - O(1)
    3. top(): returns element to topmost element of stack - O(1)
    4. push(e): adds element ‘e’ to top of stack - O(1)
    5. pop(): returns and deletes the topmost element of the stack - O(1)
    2. 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

    stack = []

    # append() function to push
    # element in the stack
    stack.append('a')
    stack.append('b')
    stack.append('c')

    print('Initial stack')
    print(stack)

    # pop() function to pop
    # element from stack in
    # LIFO order
    print('\nElements popped from stack:')
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

    print('\nStack after elements are popped:')
    print(stack)

    # uncommenting print(stack.pop())
    # will cause an IndexError
    # as the stack is now empty
  2. Queues in Python
    Can implement with python list, collections.deque, queue.Queue
    First In, First Out data structure (FIFO)

    Functions associated with queues:
    1. enqueue(): adds item to queue - O(1)
    2. dequeue(): removes item from queue. items are popped in the same order as they are pushed - O(1)
    3. front(): get front item of queue - O(1)
    4. back(): get last item of queue - O(1)
    3. 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
    32
    33
    34
    35
    36
    from queue import Queue

    # Initializing a queue
    q = Queue(maxsize = 3)

    # qsize() give the maxsize
    # of the Queue
    print(q.qsize())  # 0

    # Adding of element to queue
    q.put('a')
    q.put('b')
    q.put('c')

    # Return Boolean for Full
    # Queue
    print("\nFull: ", q.full()) #Full:  True

    # Removing element from queue
    print("\nElements dequeued from the queue")
    print(q.get())  #a
    print(q.get())  #b
    print(q.get())  #c

    # Return Boolean for Empty
    # Queue
    print("\nEmpty: ", q.empty()) #Empty:  True

    q.put(1)
    print("\nEmpty: ", q.empty()) #Empty:  False
    print("Full: ", q.full())   #Full:  False

    # This would result into Infinite
    # Loop as the Queue is empty.
    # print(q.get())

  3. Python heapq class (min-heap)
    Functions associated with heap:
    1. heapify(iterable): converts the iterable into a heap data structure - O(n)
    2. heappush(heap, elem): insert elem into the heap. The order is adjusted, so the heap structure is maintained - O(logn)
    3. heappop(heap): used to remove and return the smallest element from heap. The order is adjusted, so the heap structure is maintained - O(logn)
    4. heap[0]: returns the smallest element on heap - O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# importing "heapq" to implement heap queue
import heapq

# initializing list
li = [5, 7, 9, 1, 3]

# using heapify to convert list into heap
heapq.heapify(li)

# printing created heap
print ("The created heap is : ",end="")
print (list(li))  #The created heap is : [1, 3, 9, 7, 5]

# using heappush() to push elements into heap
# pushes 4
heapq.heappush(li,4)

# printing modified heap
print ("The modified heap after push is : ",end="")
print (list(li))    #The modified heap after push is : [1, 3, 4, 7, 5, 9]

# using heappop() to pop smallest element
print ("The popped and smallest element is : ",end="")
print (heapq.heappop(li))   #The popped and smallest element is : 1

* Decode String

给定类似k[encoded_string]的string，return重复k个的 encoded_string
例如Input: s = “3[a]2[bc]”，Output: “aaabcbc”；Input: s = “3[a2[c]]”，Output: “accaccacc”

用stack解决。每次往stack里面存previous string，number of repetition，用变量记录current string。这样prevString + num*curString就可以做到前后衔接。
核心是如何找到最里层的string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def decodeString(self, s):
        stack = []; curNum = 0; curString = ''
        for c in s:
            if c == '[':
                stack.append(curString)
                stack.append(curNum)
                curString = ''
                curNum = 0
            elif c == ']':
                num = stack.pop()
                prevString = stack.pop()
                curString = prevString + num*curString
            elif c.isdigit():
                curNum = curNum*10 + int(c)
            else:
                curString += c
        return curString

甚至可以用regular expression
每次更新s值
re.sub(pattern, repl, string)
The sub() function searches for the pattern in the string and replaces the matched strings with the replacement (repl). The repl could be a function

1
2
3
4
def decodeString(self, s):
    while '[' in s:
        s = re.sub(r'(\d+)\[([a-z]*)\]', lambda m: int(m.group(1)) * m.group(2), s)
    return s

Valid Parentheses

给定一个string包含 ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, 判断它是否valid。有以下要求：
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

思路很好想，注意可以用dictionary简化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}  #注意通过closing来找opening
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return not stack

Minimum Remove to Make Valid Parentheses

删括号来使得string valid

Given a string s of ‘(‘ , ‘)’ and lowercase English characters. Remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

思路其实延续了昨天的 Valid Parentheses，用一个stack来记录哪几个括号应该删去

注意一下这里的代码简化，实际上压根不用把 “(“, “)” push到stack里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minRemoveToMakeValid(self, s: str) -> str:
    s = list(s)   #直接之后修改s，string类型是immutable
    stack = []
    for i, char in enumerate(s): #记一下这种写法
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                s[i] = ''  #直接修改，避免污染stack
    while stack:
        s[stack.pop()] = ''
    return ''.join(s)

K Closest Points to Origin

给定二维数组，返回距离原点的k nearest neighbor

  1. 用max-heap。其实之前的 Kth Smallest Element in a Sorted Matrix有用到相同的方法，注意一下写法
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        heap = []
        for (x, y) in points:
            dist = -(x*x + y*y)
            if len(heap) == K:
                heapq.heappushpop(heap, (dist, x, y)) #注意heappushpop做了push+pop两个操作
            else:
                heapq.heappush(heap, (dist, x, y))
        
        return [(x,y) for (dist,x, y) in heap]
  1. 用内置函数
    1
    2
    3
    class Solution:
        def kClosest(self, points, K):
            return heapq.nsmallest(K, points, lambda x: x[0] ** 2+ x[1] **2)

* LRU Cache

实现一个Least recently used (LRU) cache。要求get和put O(1) average time complexity.
这道题好奇怪，没有用到stack、queue、heap。O(1)的get首先确定了用dictionary。主要看一下怎么用double linked list记录insertion顺序

  1. 直接一个dictionary解决，因为dictionary会保留insert的顺序 (python 3.7 以后)
    注意iter(),next()两个函数。他们可以用在list, set, tuple, etc.这里是dictionary
    python iter() method returns the iterator object，next() return the value

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class LRUCache:
        def __init__(self, capacity: int):
            self.dict = {}
            self.capacity = capacity   

        def get(self, key: int) -> int:
            if key not in self.dict:   #判断句留意写法
                return -1
            val = self.dict.pop(key)  #Remove it first before inserting it at the end again
            self.dict[key] = val   
            return val        

        def put(self, key: int, value: int) -> None:
            if key in self.dict:    
                self.dict.pop(key)
            else:
                if len(self.dict) == self.capacity:
                    del self.dict[next(iter(self.dict))]     
            self.dict[key] = value

  2. Dict + Double LinkedList
    使用double linkedlist进行O(1)的deletion

    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    class Node:
        def __init__(self, k, v):
            self.key = k
            self.val = v
            self.prev = None
            self.next = None

    class LRUCache:
        def __init__(self, capacity):
            self.capacity = capacity
            self.dic = {}
            self.head = Node(0, 0)
            self.tail = Node(0, 0)
            self.head.next = self.tail
            self.tail.prev = self.head

        def get(self, key):
            if key in self.dic:
                n = self.dic[key]
                self._remove(n)
                self._add(n)
                return n.val
            return -1

        def put(self, key, value):
            if key in self.dic:
                self._remove(self.dic[key])
            n = Node(key, value)
            self._add(n)
            self.dic[key] = n
            if len(self.dic) > self.capacity:
                n = self.head.next
                self._remove(n)
                del self.dic[n.key]

        def _remove(self, node):
            p = node.prev
            n = node.next
            p.next = n
            n.prev = p

        def _add(self, node):
            p = self.tail.prev
            p.next = node
            self.tail.prev = node
            node.prev = p
            node.next = self.tail

  3. OrderedDict
    实际上也是a HashMap and a Doubly Linked List
    并且思路跟方法一差别不大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LRUCache:
    def __init__(self, capacity):
        self.dic = collections.OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.dic:
            return -1
        v = self.dic.pop(key) 
        self.dic[key] = v   # set key as the newest one
        return v

    def put(self, key, value):
        if key in self.dic:    
            self.dic.pop(key)
        else:
            if len(self.dic) == self.capacity:
                self.dic.popitem(last=False)      
        self.dic[key] = value

* Task Scheduler

感觉像是一道数学题。可以从n很大/n很小两个角度去想
解析

collections.Counter返回一个dictionary，记录每个元素的出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:        
        
        # tasks = ["A","A","A","B","B","B"]
        # n = 2 
        
        counts = list(collections.Counter(tasks).values()) # [3,3]
        max_count = max(counts) # 3
        num_of_chars_with_max_count = counts.count(max_count) # 2, A and B
        
        num_of_chunks_with_idles = max_count-1 # 2  -> A  A  A (except the last chunk)

        # either a task will fill an empty place or the place stays idle, 
        # either way the chunk size stays the same  
        length_of_a_chunk_with_idle = n+1  # 3 -> A _ _ A _ _ A 

        # on the final chunk, there will only be most frequent letters 
        length_of_the_final_chunk = num_of_chars_with_max_count  # 2  

        length_of_all_chunks = (num_of_chunks_with_idles*length_of_a_chunk_with_idle) + length_of_the_final_chunk # 2*3 + 2 = 8 
        # -> A B _ A B _ A B 

        return max(len(tasks), length_of_all_chunks)

Week Five

Design Browser History

没啥好说的。这里注意一下self.bound的使用，这样避免了delete list元素的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.curr = 0
        self.bound = 0

    def visit(self, url: str) -> None:
        self.curr += 1
        if self.curr == len(self.history):
            self.history.append(url)
        else:
            self.history[self.curr] = url
        self.bound = self.curr

    def back(self, steps: int) -> str:
        self.curr = max(self.curr - steps, 0)
        return self.history[self.curr]

    def forward(self, steps: int) -> str:
        self.curr = min(self.curr + steps, self.bound)
        return self.history[self.curr]

Min Stack

design a stack, where O(1) time complexity for each function. void push(int val), void pop(), int top(), int getMin()

学习一下解法，trade off between time complexity and space complexity
每一个在stack里的element都保存着current minimum value

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
class MinStack:

    def __init__(self):
        self.stack = []
        
    def push(self, val: int) -> None:
        curMin = self.getMin()  #直接call函数更方便，不需要单独一个self.curMin,否则要update
        if curMin == None or val < curMin: 
            curMin = val
        self.stack.append((val,curMin))
                
        
    def pop(self) -> None:
        self.stack.pop()
                
    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        if not self.stack:
            return None
        return self.stack[-1][1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Design Underground System

Keep track of customer travel times between different stations, and calculate the average time between stations

用hashtable(dictionary)。这里再注意一下counter的使用
重新回忆一下dict.get()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class UndergroundSystem:
    def __init__(self):
        self.ids = {}
        self.pairs = Counter()
        self.freqs = Counter()
        
    def checkIn(self, id, stationName, t):
        self.ids[id] = (stationName, t)

    def checkOut(self, id, stationName, t):
        Name2, t2 = self.ids.pop(id)  #注意dictionary的pop操作
        self.pairs[(Name2, stationName)] += t-t2
        self.freqs[(Name2, stationName)] += 1
        
    def getAverageTime(self, startStation, endStation):
        return self.pairs[startStation, endStation]/self.freqs[startStation, endStation]

# Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)

* Design Twitter

Implement the Twitter class:
Twitter() Initializes your twitter object.
void postTweet(int userId, int tweetId) post a new tweet
List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

首先注意getNewsFeed的要求，然后注意不要method和variavle名字相同…

  1. 用dictionary + list解决，用sorting(最好想的办法)
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tweets = collections.defaultdict(list)
        self.following = collections.defaultdict(set)
        self.order = 0
    def postTweet(self, userId, tweetId):
        """
        Compose a new tweet.
        :type userId: int
        :type tweetId: int
        :rtype: void
        """
        
        self.tweets[userId] += (self.order, tweetId), 
        # identical to self.tweets[userId].append((self.order, tweetId)) 
        # or self.tweets[userId] += [(self.order, tweetId)]
        # comma represent a list
        self.order -= 1 #As default sorting will sort the items in ascending order 

    def getNewsFeed(self, userId):
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        :type userId: int
        :rtype: List[int]
        """
        tw = sorted(tw for i in self.following[userId] | {userId} for tw in self.tweets[i])[:10]
        # for Id in self.following[userId] | {userId}:  #{userId} is a set 
        #    for tw in self.tweets[Id]:
        #        temp.append(tw)
        # tw = sorted(temp)[:10] 
        return [news for i, news in tw]
    

    def follow(self, followerId, followeeId):
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        self.following[followerId].discard(followeeId) 
        #discard will not raise an error when the element is not found     


# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)
  1. dictionary + deque
    heapq.merge()will merge two sorted array, and return a iterator
    * unpacking
    iterator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Twitter(object):

    def __init__(self):
        self.timer = itertools.count(step=-1)
        self.tweets = collections.defaultdict(collections.deque)
        self.followees = collections.defaultdict(set)

    def postTweet(self, userId, tweetId):
        self.tweets[userId].appendleft((next(self.timer), tweetId))

    def getNewsFeed(self, userId):
        tweets = heapq.merge(*(self.tweets[u] for u in self.followees[userId] | {userId}))
        # * unpacks each element of the above array into a function call heapq.merge(). Basically, each element of the array is now a separate argument.

        return [t for _, t in itertools.islice(tweets, 10)]

    def follow(self, followerId, followeeId):
        self.followees[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        self.followees[followerId].discard(followeeId)

Design HashSet

主要是找到比较好的hash function

  1. trival hashing
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
class MyHashSet:
    
    def __init__(self):
        self.size = 10000
        self.buckets = [[] for _ in range(self.size)]
    
    # Adds key to a bucket
    def add(self, key):
        bucket = self._getBucket(key)
        if not key in bucket:
            bucket.append(key)
    
    # Removes key from bucket
    def remove(self, key):
        bucket = self._getBucket(key)
        if key in bucket:
            bucket.remove(key)
    
    # Returns true if buckets contain key
    def contains(self, key):
        bucket = self._getBucket(key)
        return key in bucket
    
    # Returns the bucket corresponding to the key
    def _getBucket(self, key):
        hash = self._getHash(key)
        return self.buckets[hash]
    
    # Trivial hash function
    def _getHash(self, key):
        return key % self.size
  1. 用到了Multiplicative Hash
    generate numbers in [0,M-1]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class MyHashSet: 
        def eval_hash(self, key):
            return ((key*7777777) & (1<<20) - 1)>>5

        def __init__(self):
            self.arr = [[] for _ in range(1<<15)]

        def add(self, key: int) -> None:
            t = self.eval_hash(key)
            if key not in self.arr[t]:
                self.arr[t].append(key)

        def remove(self, key: int) -> None:
            t = self.eval_hash(key)
            if key in self.arr[t]:
                self.arr[t].remove(key)

        def contains(self, key: int) -> bool:
            t = self.eval_hash(key)
            return key in self.arr[t]

Encode and Decode TinyURL

挺奇怪的一道题，没有说明具体的转换方法
解析
About Design URL Shortening service like TinyURL
StefanPochmann yyds

  1. 用list记录longUrl，实际上不算encode：
1
2
3
4
5
6
7
8
9
10
11
class Codec:

    def __init__(self):
        self.urls = []

    def encode(self, longUrl):
        self.urls.append(longUrl)
        return 'http://tinyurl.com/' + str(len(self.urls) - 1)

    def decode(self, shortUrl):
        return self.urls[int(shortUrl.split('/')[-1])]
  1. random generation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Codec:

    alphabet = string.ascii_letters + '0123456789'

    def __init__(self):
        self.url2code = {}
        self.code2url = {}

    def encode(self, longUrl):
        while longUrl not in self.url2code:
            code = ''.join(random.choice(Codec.alphabet) for _ in range(6))
            if code not in self.code2url:
                self.code2url[code] = longUrl
                self.url2code[longUrl] = code
        return 'http://tinyurl.com/' + self.url2code[longUrl]

    def decode(self, shortUrl):
        return self.code2url[shortUrl[-6:]]

*Week Six

因为开学了事情变多而且遇到了一些烦心事（具体什么事可以参考我的wyy），所以这一周做得不是很好。感觉没有掌握sliding window的精髓

Swapping Nodes in a Linked List

交换正数第k个node和倒数第k个node的value
注意一下这种题要想到one pass的方法

用到了two poiners method

  1. swap value
1
2
3
4
5
6
7
8
9
10
11
def swapNodes(self, head: ListNode, k: int) -> ListNode:
    first = last = head
    for i in range(1, k):
        first = first.next

    null_checker = first 
    while null_checker.next:
        last = last.next
        null_checker = null_checker.next
    first.val, last.val = last.val, first.val #python直接交换值的方法
    return head
  1. swap node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        pre_right = pre_left = ListNode(next=head)
        right = left = head
        for i in range(k-1):
            pre_left = left
            left = left.next
    
        null_checker = left
    
        while null_checker.next:
            pre_right = right
            right = right.next
            null_checker = null_checker.next
        
        if left == right:
            return head
    
        pre_left.next, pre_right.next = right, left
        left.next, right.next = right.next, left.next
        return head

Max Consecutive Ones

Given a binary array nums, return the maximum number of consecutive 1’s in the array.

  1. iterate the whole array
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        cnt = 0
        ans = 0
        for num in nums:
            if num == 1:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 0
        return ans
  1. 当作字符串处理
1
2
3
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        return len(max(''.join(map(str, nums)).split('0'))) #注意一下map的使用
  1. 使用groupby 
1
2
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
    return max(sum(g) for _, g in groupby(nums))

Target Sum

给定一个integer array 和一个integer target，在array每一个元素前面加上 + or - 使得sum = target，返回不同组合的个数

用recursion做（DP）

第一遍很好想，但是没optimization所以会time exceed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def findTargetSumWays(self, nums, S):
     index = len(nums) - 1
     curr_sum = 0
     return self.dp(nums, S, index, curr_sum)
     
 def dp(self, nums, target, index, curr_sum):
    # Base Cases
     if index < 0 and curr_sum == target: #index < 0 means that we have used all the items in the array 
         return 1
     if index < 0:
         return 0 
     
    # Decisions
     positive = self.dp(nums, target, index-1, curr_sum + nums[index])
     negative = self.dp(nums, target, index-1, curr_sum + -nums[index])
     
     return positive + negative

optimization的办法是用一个dictionary记录解
注意index在dp的题目中经常需要被使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findTargetSumWays(self, nums, S):
        index = len(nums) - 1
        curr_sum = 0
        self.memo = {}
        return self.dp(nums, S, index, curr_sum)
        
    def dp(self, nums, target, index, curr_sum):
        if (index, curr_sum) in self.memo:
            return self.memo[(index, curr_sum)]
        
        if index < 0 and curr_sum == target:  
            return 1
        if index < 0:
            return 0 
        
        positive = self.dp(nums, target, index-1, curr_sum + nums[index])
        negative = self.dp(nums, target, index-1, curr_sum + -nums[index])
        
        self.memo[(index, curr_sum)] = positive + negative
        return self.memo[(index, curr_sum)]

Longest Substring Without Repeating Characters

第一遍想到的是用queue做，但实际上不用特地pop重复的元素，只需要记录位置

方法叫sliding window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:

    def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        usedChar = {}
        
        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)

            usedChar[s[i]] = i

        return maxLength

Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1‘s in the array if you can flip at most k 0‘s.

还是sliding window,主要组成就是start，end，count。想清楚情况

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        start = 0
        max_length = 0
        for end in range(len(nums)):
            if nums[end] == 0:
                k -= 1
            while k < 0:
                if nums[start] == 0:
                    k += 1
                start += 1 
            max_length = max(max_length,end - start + 1)
        return max_length

Maximum Points You Can Obtain from Cards

每次从array左边或者右边抽取元素，最多抽k个，求最大和

反面应用sliding window,也就是找到连续的最小值

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        size = len(cardPoints) - k
        minSubArraySum = curr = sum(cardPoints[:size])
        
        for i in range(len(cardPoints) - size):
            curr += cardPoints[size + i] - cardPoints[i]
            minSubArraySum = min(minSubArraySum, curr)
            
        return sum(cardPoints) - minSubArraySum

* Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

看着似乎很简单的样子…

发现collections.defaultdict比Counter更容易理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        ctr1 = collections.defaultdict(int)
        ctr2 = collections.defaultdict(int)
        for x in s1: ctr1[x] += 1
        for x in s2[:len(s1)]: ctr2[x] += 1
            
        i = 0; j = len(s1)
        
        while j < len(s2):
            if ctr2 == ctr1: return True
            ctr2[s2[i]] -= 1
            if ctr2[s2[i]] < 1: 
                ctr2.pop(s2[i]) #注意这里的pop清理dictionary的entry 
            ctr2[s2[j]] += 1
            i += 1
            j += 1
            
        return ctr2 == ctr1

Minimum Window Substring

方法很简单，但是细节上还是需要注意，尤其关于move start直到停止的条件

  1. Use two pointers: start and end to represent a window.
  2. Move end to find a valid window.
  3. When a valid window is found, move start to find a smaller window.

注意一下关于Counter里面没包含的entry，初始值是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minWindow(s, t):
    need = collections.Counter(t)            #hash table to store char frequency
    missing = len(t)                         #total number of chars we care
    start, end = 0, 0
    i = 0
    for j, char in enumerate(s, 1):          
        #index j from 1，但是char还是第一个字符开始，因为list slicing最后一个字符不包含
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        if missing == 0:                     #match all chars
            while i < j and need[s[i]] < 0:  #remove chars to find the real start
                need[s[i]] += 1
                i += 1
            need[s[i]] += 1                  #make sure the first appearing char satisfies need[char]>0
            missing += 1                     #we missed this first char, so add missing by 1
            if end == 0 or j-i < end-start:  #update window
                start, end = i, j
            i += 1                           #update i to start+1 for next window
    return s[start:end]

Week Seven

休息一周(ﾉ>ω<)ﾉ，刚好DeCal上面也是Spring Break

Week Eight

没想到一休息就休息了一个月QwQ，感觉好多东西都忘掉了…这个学期开学的确有点overwhelmed…
Anyway，现在开始。

Symmetric Tree

判断一个给定的binary tree是不是symmetric
第一眼想到的方法是DFS从左到右生成两个vector进行比较，但似乎又慢space又大

BFT Search
使用到了queue：

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
bool isSymmetric(TreeNode *root) {
        TreeNode *left, *right;
        if (!root)
            return true;
        
        queue<TreeNode*> q1, q2;
        q1.push(root->left);
        q2.push(root->right);
        while (!q1.empty() && !q2.empty()){
            left = q1.front();
            q1.pop();
            right = q2.front();
            q2.pop();
            if (NULL == left && NULL == right) //注意考虑nullptr的情况
                continue;
            if (NULL == left || NULL == right)
                return false;
            if (left->val != right->val)
                return false;
            q1.push(left->left);
            q1.push(left->right);
            q2.push(right->right);
            q2.push(right->left);
        }
        return true;
    }

改版：甚至不需要queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        return helper(root->left, root->right);
    }
    
    bool helper(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        } else if (!p || !q) {
            return false;
        }
        
        if (p->val != q->val) {
            return false;
        }
        
        return helper(p->left,q->right) && helper(p->right, q->left); 
    }

Same Tree

方法同昨天一样

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p&&!q) return true;
        if(!p || !q) return false;
        if(p->val != q->val) return false;
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

Kth Smallest Element in a BST

给定一个binary search tree， 返回kth smallest value

用in order traversal

recursion 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        return find(root, k);
    }
    int find(TreeNode* root, int& k) {
        if (root) {
            int x = find(root->left, k);
            return !k ? x : !--k ? root->val : find(root->right, k);
        }
        return INT_MIN; // return a arbitrary value
    }
};

使用stack记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode *> st;
        TreeNode *p = root;
        while(p || !st.empty()) //这里的条件似乎可以不用，可以改成while true
        {
            while(p)
            {
                st.push(p);
                p = p->left;
            }
            p = st.top();
            if(--k == 0)
                return p->val;
            st.pop();
            p = p->right; //留意这里的处理
        }
    }
};

Maximum Depth of Binary Tree

返回tree 最大的depth

  1. Depth first traversal: 用recursive
1
2
3
4
int maxDepth(TreeNode *root)
{
    return !root ? 0 : max(maxDepth(root->left),maxDepth(root->right)) + 1; 
}

其实recursive还是挺快的

  1. Breadth first traversal：用queue
    注意一下queue的方法，push() and front()
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
int maxDepth(TreeNode *root)
{
    if(root == NULL)
        return 0;
    
    int res = 0;
    queue<TreeNode *> q;
    q.push(root);
    while(!q.empty())
    {
        ++ res;
        for(int i = 0, n = q.size(); i < n; ++ i) // 注意n=q.size(),先得到queue的size，之后要将整一层去掉
        {
            TreeNode *p = q.front();
            q.pop();
            
            if(p -> left != NULL)
                q.push(p -> left);
            if(p -> right != NULL)
                q.push(p -> right);
        }
    }
    
    return res;
}

*Diameter of Binary Tree

output从tree中一个node到另一个node的最大路径
要想到怎么modify昨天Maximum Depth of Binary Tree的solution
这里可以学习一下既有返回值又modify传入值的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int output = 0;
        helper(root,output);
        return output;
    }
    int helper(TreeNode* root, int& output) {
        if(!root) return 0; 
        int ld = helper(root->left,output);
        int rd = helper(root->right,output);
        output = max(output,ld + rd);
        return max(ld, rd) + 1;
    }
};

*Binary Tree Right Side View

return the values of the nodes you can see from the right view, ordered from top to bottom.

应该先想到BFS的方法：
注意queue是push和front

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
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root) {
            return {};
        }
        vector<int> view;
        queue<TreeNode*> todo;
        todo.push(root);
        while (!todo.empty()) {
            int n = todo.size();
            for (int i = 0; i < n; i++) {
                TreeNode* node = todo.front();
                todo.pop();
                if (i == n - 1) {
                    view.push_back(node -> val);
                }
                if (node -> left) {
                    todo.push(node -> left);
                }
                if (node -> right) {
                    todo.push(node -> right);
                }
            }
        }
        return view;
    }
};

DFS:
觉得真的好简洁好神奇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int>output;
        recursion(root,output,1);
        return output;
    }
    void recursion(TreeNode* root, vector<int> &output, int level) {
        if(!root) return;
        if(output.size() < level) output.push_back(root->val);
        recursion(root->right,output,level+1);
        recursion(root->left,output,level+1);
    }
};

*Shortest Path in Binary Matrix

走迷宫
运用了BFS，这个想法的确好重要

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
32
33
34
35
36
37
class Solution
{
    public:
        
    int shortestPathBinaryMatrix(vector<vector < int>> &grid) {
        return helper(grid,0);
    }
    int helper(vector<vector < int>> &grid, int step = 0)
    {
        queue<pair<int, int>> p;
        p.push({ 0,0 });
        while (!p.empty())
        {
            step++;
            queue<pair<int, int>> p1;
            while (!p.empty())
            {
                auto c = p.front();
                p.pop();
                if (c.first >= 0 && c.first < grid.size() && c.second >= 0 && c.second < grid[0].size() && !grid[c.first][c.second])
                {
                    if (c.first == grid.size() - 1 && c.second == grid[0].size() -1) return step;
                    grid[c.first][c.second] = 1;
                    for (int i = -1; i < 2; i++)
                    {
                        for (int j = -1; j < 2; j++)
                        {
                            p1.push(make_pair(c.first + i, c.second + j));
                        }
                    }
                }
            }
            swap(p,p1);
        }
        return -1;
    }
};

*Course Schedule

detecting a cycle in the directed graph
使用topological sort
注意indegree的概念，以及如何构建adjacent matrix

BFS(Kahn’s algorithm)

1
2
3
4
5
6
7
8
9
10
11
bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> G(n);
    vector<int> degree(n, 0), bfs;
    for (auto& e : prerequisites)
        G[e[1]].push_back(e[0]), degree[e[0]]++;
    for (int i = 0; i < n; ++i) if (!degree[i]) bfs.push_back(i);
    for (int i = 0; i < bfs.size(); ++i)
        for (int j: G[bfs[i]])
            if (--degree[j] == 0) bfs.push_back(j);
    return bfs.size() == n;
}

Powered by Hexo

Copyright © 2013 - 2023 骸骨长廊 All Rights Reserved.

UV : | PV :