Personal-Notes

一些套路

既有题目思路

不贪图运行时间最快，但算法复杂度需要尽可能低
思路要易于理解，代码要尽可能短，每条思路所对应的代码最好要形成模板

新题套路

Problem Solving：把新题解释成既有套路的过程
1. 遇到没思路的新题先举栗子找规律
Code Writing：熟练掌握既有套路
1. BFS -- 熟练度高
2. DFS / Backtracking
3. Binary Search
4. Linked List
5. Tree
6. Two Pointer

面试技巧

当你面试时，你在白板上写，写完之后，面试官很可能就立刻开始给你指bug了，你这时有的bug，都算bug！所以，在写完最后一句话前，最好做个大停顿，过一下之前写的，快速检查下。当然你嘴上可以给面试官解释你现在是在做最终检查，不是说卡住不会了。
最好不要说完思路就动笔就写，需要思考不同的解法，并与面试官交流明确：
1. 要熟悉刷题网站提供的标准解法
2. 要准备一个面试友好的解法
3. 要准备时间空间权衡的分析：有的解法可能时间复杂度不高，但空间复杂度很不错

面试流程

问题分析
交流阶段：厘清各种条件
提出各种方案，满足面试官要求
如果方案不能再规定时间内写完，与面试官交流选定一个方案
coding
test & debug
1. 考虑corner case，做各种assumption
follow up: doc, unit test, regression test, performance tuning, benchmarking

DP

简而言之 DP有六部曲个人建议面试时写在白板上清楚明了一步都不能少基本上你写出这些 implement起来也非常简单了

定义：dp[j]表示什么含义，比如largest subarray sum ending at arr, and must include arr. 注意语言描述, 包括还是不包括arr/matrix[j]
归纳法则：dp 的 dependency 是怎么样的，依赖于dp[i-1] 还是 dp[i+1] 还是 dp[k] for all k < i or all k > i 等等，试着过几个小例子推导一下
初始态：往往是dp[0]，二维往往是第一行，第一列，也就是dp[0], dp[0][j], dp[i][0]
结果：往往的dp[n], max(dp) 等等, 从definition 出发
填充顺序：从induction rule 的 dependency出发判断的从左到右还是从左上到右下
优化: 分为时间和空间两方面。
1. 时间的比较难，因为往往需要你重新define dp state 和 induction rule。
2. 空间比较简单，可以根据induction rule看出来，比如斐波那契数列: dp = dp[i - 1] + dp[i - 2], 那么dp 只依赖于前两个元素，就不需要create 整个 dp array，两个variable即可，空间可以从O(n)优化到O(1)。

最后, 多总题多总结多积累小tips，熟能生巧后dp其实是非常简单，也非常有套路的，一些induction rule 的常见pattern 你一眼就能看出来了。

String基本操作

s2 = "shaunwei"
s2[-3:] = "wei"
s2[5:8] = "wei"
s2.index('w') = 5  # if not found, return -1

链表

链表的技巧不多，主要是记忆操作顺序太繁琐，现想其实也是有时间的。

翻转链表
删除节点
Dummy Node
快慢指针

Tree

遍历：DFS和BFS

前序
中序
后序
BFS

Sorting

选择排序最好理解，每次迭代都从子数组里寻找最小值即可，第k次迭代抽出来的即是第k小值

def swap(self, arr, i, j):
    temp = arr[j]
    arr[j] = arr[i]
    arr[i] = temp


def selectSort(self, arr):
    l = len(arr)
    for i in range(0, l):
        min = 2 ** 31
        m = 0
        for j in range(i, l):
            if arr[j] < min:
                min = arr[j]
                m = j
        self.swap(arr, i, m)
    return arr

插入排序的话需要假设前面第i-1个数字是排好序的，然后把第i个数字插到已经排好序的数组里的恰当位置；既然是插入那么其实用链表比用数组要经济

def insertSort(self, arr):
    l = len(arr)
    for i in range(1, l):
        temp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp
    return arr

合并排序很容易理解，要点是每排完一个数组就把另一个数组剩余值贴后面

def merge(self, arr1, arr2):
    arr = []
    [l1, l2] = [len(arr1), len(arr2)]
    [i1, i2] = [0, 0]
    while i1 < l1 and i2 < l2:
        if arr1[i1] < arr2[i2]:
            arr.append(arr1[i1])
            i1 += 1
        else:
            arr.append(arr2[i2])
            i2 += 1
    if i1 == l1:
        arr += arr2[i2:]
    else:
        arr += arr1[i1:]
    return arr

def mergeSort(self, arr):
    l = len(arr)
    if l == 1:
        return arr
    elif l == 2:
        if arr[0] > arr[1]:
            self.swap(arr, 0, 1)
        return arr
    else:
        l1 = l // 2
        m1 = self.mergeSort(arr[0:l1])
        m2 = self.mergeSort(arr[l1:])
        return self.merge(m1, m2)

快速排序没什么好说的

def quickSort(self, arr):
    l = len(arr)
    if l <= 1:
        return arr
    pivot = arr[int(random.random() * 200) % l]
    a = []
    b = []
    c = []
    for i in arr:
        if i < pivot:
            a.append(i)
        elif i == pivot:
            b.append(i)
        else:
            c.append(i)
    return self.quickSort(a) + b + self.quickSort(c)

Union-find

Quick-find: 确定两个点是否处在同一个连通集里：遍历所有的边(p, q)，每次都把id[p]改成id[q]

class UF:
    id = []
    count = 0

    def __init__(self, N):
        self.count = N
        for i in range(0, N):
            self.id.append(i)

    def dump(self):
        temp = ""
        for i in range(0, self.count):
            temp += (" " + str(i))
        print(temp)
        temp = ""
        for i in self.id:
            temp += (" " + str(i))
        print(temp)
        print()

    def find(self, p):
        return self.id[p]

    def quick_find(self, arr):
        for i in arr:
            pID = self.find(i[0])
            qID = self.find(i[1])
            if pID == qID:
                continue
            else:
                print(pID, qID)
                for j in range(0, self.count):
                    if self.id[j] == pID:
                        self.id[j] = qID
                self.dump()

Hash Table

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution.

从头至尾检索一遍数组，如果Hashmap里没有(target - nums[i])就丢进去{nums[i], i}，否则的话就是遇到了结果，返回(target - nums[i])的角标（Hashmap.get(target - nums[i])）和当前角标。

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0)
            return new int[]{0, 0};
    Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
    int index1 = 0, index2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (hashmap.containsKey(target - nums[i])) {
            index1 = hashmap.get(target - nums[i]);
            index2 = i;
            return new int[]{index1, index2};
        } else {
            hashmap.put(nums[i], i);
        }
    }
    return new int[]{0, 0};
}

pxu/LCPython