Bowen's Tech Blog

From workshop

From bruce force, to a perfect solution.

From local optimum to a whole optinum. According to experience.

Steps

1. Determine wether can use Greedy
2. Choose the strategy of Greddy
3. Calculate

Some samples

1. Arrange the activitices
   • Minuim end time of meeting
2. Minunm sum of weight of tree from graph
   • Prim
   • Krusal
3. Huffman coding
   prefix-tree binary code; choose the two min weighted elements to be the leaves of tree(from down to up)

Overview

There are several similar data structure.

• HashTable / Dictionary
  • Key/value
  • dic = {} in Python
  • dic[key] = value
• HashSet
  • No repeated values
  • se = set() in Python
  • se.add(item) se.remove(item)

The time complexity of search in HashTable’s key or HashSet is O(1)

Useful functions

• collections.Counter(list) can count the element in the list and generate a dictionary
• for key, value in dic.items() can iterate the key and value at the same time
• sorted(dic.keys()) is sorting the keys
• dic.get(key, value) return the dic[key] if the key in dic, otherwise return value you give

Samples

Used for quick search

No.1 Two Sum

1
2
3
4
5
6

dic = {} 
for i, item in enumerate(nums):
    if target - item in dic:
        return [i, dic[target-item]]
    else:
        dic[item] = i

No.138 Copy List with Random Pointer

No.202 Happy Number

No.136 Single Number

1
2
3
4
5
6
7

se = set()
for num in nums:
    if num in se:
        se.remove(num)
    else:
        se.add(num)
return se.pop()

No.217 Contains Duplicate

Used for record the index

No.3 Longest Substring Without Repearting Characters

Used for record the count

No.49 Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12

dic = {}
for str_ in strs:
    form = dict(collections.Counter(str_))
    form_t = [0 for _ in range(26)]
    for (key, value) in form.items():
        form_t[ord(key) - 97] = value
    form_t = str(form_t)
    if form_t in dic:
        dic[form_t].append(str_)
    else:
        dic[form_t] = [str_]
return dic.values()

No.347 Top K Frequent Elements
Swap the key and values

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

form = dict(collections.Counter(nums))
form_r = {}
for key, value in form.items():
    if value in form_r:
        form_r[value].append(key)
    else:
        form_r[value] = [key]

sort_fre = sorted(form_r)[::-1]
ans = []
count = 0
index = 0
while count < k:
    ans.extend(form_r[sort_fre[index]])
    count += len(form_r[sort_fre[index]])
    index += 1
    
return ans

No.387 First Unique Character in a String

No.242 Valid Anagram

No.350 Intersection of Two Arrays II

No.36 Valid Sudoku

No.454 4Sum II

Overview

1
2
3
4

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

• Add a node into LinkedList is O(1).
• Remove a node from LinkedList is O(1) but search it is O(n).

Samples

Traversing and merge

No.2 - Add Two Numbers
Two pointers.

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

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    p1, p2 = l1, l2
    carry = 0
    ans = ListNode(0)
    p = ans
    while p1 != None and p2 != None:
        sum_ = p1.val + p2.val + carry
        carry = 1 if sum_ >= 10 else 0
        sum_ = sum_ if sum_ < 10 else sum_ - 10
        p.next = ListNode(sum_)
        p, p1, p2 = p.next, p1.next, p2.next
    
    p1 = p1 if p1 != None else p2

    while p1 != None and carry:
        sum_ = p1.val + carry
        carry = 1 if sum_ >= 10 else 0
        sum_ = sum_ if sum_ < 10 else sum_ - 10
        p.next = ListNode(sum_)
        p, p1 = p.next, p1.next
    
    p.next = p1
    if carry == 1:
        p.next = ListNode(1)
    
    return ans.next

No.21 - Merge Two Sorted Lists
Several pointers.

No.23 - Merge k Sorted Lists
Priority queue

No.328 - Odd Even Linked List

Other basic function

No.237 - Delete Node in a Linked List

1
2
3
4
5
6
7

def deleteNode(self, node):
    """
    :type node: ListNode
    :rtype: void Do not return anything, modify node in-place instead.
    """
    node.val = node.next.val
    node.next = node.next.next

No.138 - Copy List with Random Pointer
Deep Copy

Recursively

No.206 - Reverse Linked List

No.234 - Palindrome Linked List

Combine with other data strucure

No.19 - Remove Nth Node From End of List
With List

No.206 - Reverse Linked List
Stack

No.141 - LinkeList List Cycle
HashTable

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def hasCycle(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    p = head
    se = set()
    while(p != None):
        if(p in se):
            return True
        else:
            se.add(p)
            p = p.next
    return False

No.160 - Intersection of Two Linked Lists
HashTable

No.138 - Copy List with Random Pointer
HashTable

Overview

Queue and stack are just like a store. You just want to put and pick the items one by one. The time complexity of put and pick is O(1)

Python makes queue and stack easier because we can use list to finish the functions of queue and stack.

1
2
3
4
5
6
7
8
9

my_queue = []
my_queue.append(4)
my_queue.append(5)
print(my_queue.pop(0))    # we get 4

my_stack = []
my_stack.append(4)
my_stack.append(5)
print(my_stack.pop())    # we get 5

Samples

Travel the tree

No.94 - Binary Tree Inorder Traversal

No.103 - Binary Tree Zigzag Level Order Traversal

Pair Match

No.20 - Valid Parentheses

Store the data in order[Some special questions]

No.42 - Trapping Rain Water

To be continued…

Overview

There are 7 main sorting algorithm, which are also connected with other conceptions. Will be finished in the future.

Insert sort

$O(n^2)$

• Insert the value into a sorted list - swap with element of bottom one by one

Hill sort

$O(nlog(n))$

Select sort

$O(n^2)$

• Choose the smallest/largest element and put into the sorted array

Heap sort

$O(nlog(n))$

• Put items into heap, and pop one by one out
• Use heap can find the top K values easily. Create a heap with length of K, put items into it one by one

Bubble sort

$O(n^2)$

• Choose a value, if it is larger than the next one, replace them, until this value arrive the boundary of end
• Update the boundary of end, do the previous choosing and moving steps again

Quick sort (binary sort)

$O(nlog(n))$

• Choose a pivot, put all values smaller than pivot into left, all values larger than pivot into right
• Do quick sort for left and right
• Connect left, pivot and right

Merge sort

$O(nlog(n))$

• Divide a list into left and right
• Do the merge sort for left and right
• Put the sorted left and right together

Some functions in Python

• sorted(a, key=lambda x:x[0])

Some samples

• Find the 0-Kth largeset elements
  • Heap O(klong(n))
• Find the Kth largeset element
  • Move the smaller elements to left, larger elemetns to right, until the right part only have K elements

Reference

[1] https://www.cnblogs.com/ktao/p/7800485.html

Fenwick Tree

Fenwick tree is also called Binary Indexed Tree. This kind of data structure can do the calculation of sum from 0 to ith of a list very efficiently.

It can also be used to calculate the frequency. Below is a code used to calculate the number of values from 0 to i.

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

class fenwickTree:
    def __init__(n):
        self.array = [0] * n

    def add(i):
        while i < len(self.array):
            self.array[i] += 1
            i += i & -i

    def query(i):
        ans = 0
        while i >= 0:
            ans += self.array[i]
            i -= i & -i
        return ans

Relevant application is in Leetcode No.315.

Heap

Heap is a useful data structure which can store the elements in order. In Python, there is a built in heap library called Heapq.

No.253 - Meeting Room

• Make the start time of meeting in order
• Use heap to store the end time of each meeting
• When the meeting with earliest end time is smaller than the coming meeting with earliest start time, pop that meeting, otherwise not. Then heappush the new end time of the new coming meeting.

Overview

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
3. Combine the solutions to the subproblems into the solution for the original problem.

Samples and exercise

Binary search

Decrease the time from $O(n)$ to $O(log(n))$

No.4 Median of Two Sorted Arrays
This exercise need we use binary search to find the proper value.

Majority elements

If an element is the majority element(appears more than n/2 times), it should be the majority element in the left half sequence or in the right sequence, otherwise it cannot be the majority element.

Quick sort

Binary sort.

Merge sort

Merge two in-order sequence to a whole sequence. The best time is $O(nlog(n))$

No.23 Merge k Sorted Lists

Number of inverse pairs

Reference

[1] https://blog.csdn.net/xlinsist/article/details/79198842
[2] https://blog.csdn.net/qq_29793171/article/details/80057088

Overview

Sometimes normal recursive method will cost a lot of time and not very efficient. In these cases, the DP(Dynamic Programming) can be a good choice. The key of DP is to record the previous solutions.

If a problem has two featrues:

• Optimal Substructure
  • The solution of a problem depends on the solution of its subproblem
• Overlapping subproblem
  • The subproblem needs to be used several times when dealing with the main problem
    Then we can think about using DP.

Two forms

There are two main ways to do DP. The bottom-up is the most common DP method.

Top-down(recursion with memory)

Establish a memory data structure(like a list) to store the previous values, avoiding the repeat calculation on that value.

Bottom-up(real DP)

Iterate from the bottom. This is better than the previous one because there is no recursive thus no extra cost.

Template

I felt DP is like a 2-demensional array, which can be reduced to a 1-D array. Usually the row i means the action at step i; the column j means a similar result to the original question.

1
2
3
4
5
6

dp = [[.. for i in range(m)] for j in range(n)] # Create 
dp[0][0] = ...    # init
for i in ...
    for j in ...
        dp[i][j] = ...	# transition
return dp[x][y]

Models

Linear Model

SubArray

dp[i] means subarray s[:i] and you must use s[i-1], return max(dp)

No.53 - Max sum subarray

1
2
3
4
5

if dp[i - 1] > 0:
    dp[i] = dp[i-1] + nums[i]
else:
    dp[i] = nums[i]
return max(dp)

No.300 - Longest Increasing Subsequence

No.152 - Maximum Product Subarray
dp1 contains the max product; dp2 contains the min product

List from 0 to i

dp[i] means s[:i], return dp[len(s)]

No.139 - Word Break

No.91 - Decode Ways

No.70 - Climbing Stairs

No.279 - Perfect Squares

No.62 - Unique Paths

Interval Model

The problem can be described as p[i, j]

Palindromic Substring

No.5 - Longest Palindromic Substring
dp[i][j] means wether s[i: j + 1] is a palindromic substring

1
2
3
4
5
6
7
8
9

for i in range(len(s)):
    dp[i][i] = True

for i in range(len(s), -1, -1):
    for j in range(i, len(s)):
        if i + 1 > j - 1:
            dp[i][j] = dp[i][j] or s[i] == s[j]
        else:
            dp[i][j] = dp[i][j] or dp[i + 1][j - 1] and s[i] == s[j] 

1
2
3
4
5
6
7
8
9
10
11
12
13

# This function will recursively check the left and right value of a previous palindromic string
def check(s, bg, ed):
    if bg >= 0 and ed < len(s) and s[bg] == s[ed]:
        return check(s, bg - 1, ed + 1)
    else:
        return s[bg + 1: ed]

for i in range(len(s)):
    # This palindromic substring is with odd num
    longest_palin_string1 = check(s, i, i)

    # This palindromic substring is with even num, we just took the (i, i+1) because the condition of (i-1,i) is already considered in previous steps
    longest_palin_string2 = check(s, i, i + 1)

TBD

No.10 - Two string matching with special character

1
2
3
4
5

if j + 1 == '*':
    p[i][j] = p[i][j+2] or (current_match and p[i+1][j])
else:
    p[i][j] = current_match and p[i+1][j+1]

No.44 - Wildcard Matching

No.322 - Change Coin

1
2
3
4

for coin in coins:
    for j in range(coin, amount+1):
        d[j] = min(d[j], d[j - coin] + 1)
return d[amount]

Package Model

The problem can be described as a decision problem at step i

No.198 - House Robber

1

dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

恭喜宝贝儿拿到微软的奥佛！！！！！
牛逼！！！！！

Notes of crash course computer science.