DarkAlexWang's Blog
0%

Posted on In Views: Valine:
Symbols count in article: 11k Reading time ≈ 10 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

概念

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
DP问题是Leetcode中的经典问题，也是面试中经常考到的类别之一，没有通用的模版，有些DP题思考的过程也比较繁琐.所以这篇总结可能会不断更新，以便达到更好的效果

适用场景

  1. 找Max， Min的问题
  2. 发现可能性的问题
  3. 输出所有解的个数问题

不适用场景

  1. 列出所有具体方案（起码是指数级别的复杂度，通常是递归，backtracking）
  2. 集合问题

考虑

  1. 状态
  2. 转移方程
  3. 初始化条件
  4. 返回结果
    Read more »

Posted on In Views: Valine:
Symbols count in article: 8.9k Reading time ≈ 8 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

流程

HR联系-> 确认电话面试时间-> 电话面试 -> 后续跟进（move on fail）
Data Engineer

参考

  1. 易梦前尘前辈的地里帖子 链接
  2. Github总结 [链接] (https://github.com/shi-edward/Company-Algorithm-Solution/tree/master/src/indeed)
    Read more »

Posted on In Views: Valine:
Symbols count in article: 72 Reading time ≈ 1 mins.

浅谈一下爱情的看法

奢侈品，想买就要付出高昂代价，不买也不会死。许多人梦寐以求却得不到，因此市面上假货水货很多。奢侈品，如果能拥有，确实是好东西。

Posted on Edited on In Views: Valine:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

Update (2019/01) 大幅更新了本文。
本文没有考虑的：滑雪系列，开飞机跳伞潜水，海钓，露营

郊野

赏花

  1. [ ] Filoli Garden (位于Woodside，以🌷出名，推荐时节：三月)
  2. [ ] Blossom trail (位于Fresno，displays of blooming fruit trees & wildflowers. 推荐时节：2～3月)

Hiking

  1. [ x ] Yosemite (瀑布观赏时节 5月至10月)
  2. [ x ] Skyline Blvd （适合自驾观赏）
  3. [ x ] Muir Woods National Monument (从18年起，需要提前注册车辆并且乘坐shuttle门口)
  4. [ x ] Lick Observatory (在CA-130，Mt Hamilton的山顶上，需要至少45分钟的盘山路）
  5. [ x ] Mt Diablo
  6. [ x ] Sierra Vista Point
  7. [ ] CA-120 Mono Lake （CA-120会有半年的大雪封山状况）
  8. [ x ] Big Basin Redwoods State Park (多种多样的路线)
  9. [ x ] Lassen National Forest (火山公园)
  10. [ ] Kings Canyon National Park
  11. [ ] Death Valley National Park
Read more »

Posted on Edited on In Views: Valine:
Symbols count in article: 11k Reading time ≈ 10 mins.

Tree的性质

Divide and Conquer模版

1
2
3
4
5
6
7
8
9
10
11
12
def traversal(root):
	# none or leaf
	if not root:
		# do sth
	
	# divide
	left = traversal(root.left)
	right = traversal(root.right)
	
	# Conquer
	res = # merge 
	return res

小技巧

T O(n) 一般是遍历所有点
S O(h) 用堆栈来做的话是遍历所有点
O(n) 用队列实现遍历所有点

Read more »

Posted on Edited on In Views: Valine:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

heapq–堆数据结构

heapq模块是python的一个标准库，它实现了一个堆数据结构，堆数据结构是一种二叉树。

什么是堆数据结构？

官网给出的定义是：
This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero.
我们可以这样理解：
堆是完全二叉树或者近似二叉树，它的各个节点的键值都有固定对应的的数字，根节点（即root,最上面起始位置）是0，若父节点为heap[k]，则子节点为heap[2k+1]和heap[2k+2]。父节点对应的值总是小于或者等于子节点，称为最小堆。对应的，父节点的值总是大于或者等于子节点，称为最大堆。在heapq中，使用的是最小堆。

正因为堆的这种特殊结构，使得通过heapq模块，可以快速获取一个列表的前N个最大(小)值，即Top N。

Read more »

Posted on In Views: Valine:
Symbols count in article: 5.1k Reading time ≈ 5 mins.

Union Find 总结

介绍

概念

并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

适用场景

适合于判断，给出一组结点，判断他们是否联通。从判断是否为图（一个节点的两个边都会指向同一节点–构成三角形从而不再是树）到岛屿问题（如果节点不与其它节点联通，则会孤立成一个岛屿）

实现思路

建立n个分组，每个分组代表一堆可以互相联通的结点
遍历每对结点，找到他们各自所属的分组A, B
如果A != B，则将A, B分组union起来，表示A, B分组联通了
如果A == B，则跳过 （说明A，B已经在一个组里）

Read more »

Posted on In Views: Valine:
Symbols count in article: 4.1k Reading time ≈ 4 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

Maze

这一系列题目的要求是小球滚动直到遇到障碍才停止，最后找到出口，求出valid，shorest，shortest的变种；所以用BFS可以比较简洁的解决这一系列的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
queue = [start]

direction = [(1,0),(-1,0),(0,1),(0,-1)]

while queue:
	i, j = queue.pop(0) # python 用List模仿实现Queue
	maze[i][j] = -1 # visited
	# 终止条件
	if (i,j) == destination:
		xxx

	# 遍历四个方向
	for x, y in direction: # local dir
		row = i
		col = j

		while xxx and xxx : # condition
			row += x
			col += y

	if visited and not in the queue:
		queue.append()
Read more »

Posted on Edited on In Views: Valine:
Symbols count in article: 3.2k Reading time ≈ 3 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

BackingTracking系列

4／35
[x] Easy
[x] Medium
[] Hard

Tips

凡是含有duplicate的都需要之前sorted，才能保证没有结果中没有重复

经典7道题

46. Permutations

1
2
3
4
5
6
7
8
9
10
11
1-2-3
 -3-2
def backtracking(self, nums, temp, ans):
    if len(nums) == len(temp): # quit loop
        ans.append(list(temp))
    for i in range(len(nums)):
        if nums[i] in temp: # cut duplicate
            continue
        temp.append(nums[i])
        self.backtracking(nums, temp, ans)
        temp.pop()

47. Permutations II

由于输入可能包含重复数字，所以就要保证去重。先排序然后创建Array记录访问过的数字，然后前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了

1
2
3
4
5
6
7
8
9
10
11
def backtracking(self, nums, temp, ans, used):
    if len(temp) == len(nums):
        ans.append(list(temp))
    for i in range(len(nums)):
        if used[i] or i>0 and nums[i]==nums[i-1] and not used[i-1]: # 判断条件
            continue
        temp.append(nums[i])
        used[i] = True # 记录访问
        self.backtracking(nums, temp, ans, used)
        used[i] = False
        temp.pop()

78. Subsets

终止条件不同，因为要返回每一个set，所以每次backtracking的时候都要返回tempList；然后保证唯一性就是backtrack的时候index+1

1
2
3
4
5
6
def backtracking(self, nums, temp, res, start):
    res.append(list(temp))
    for i in range(start,len(nums)):
        temp.append(nums[i])
        self.backtracking(nums, temp, res, i+1)
        temp.pop()

90. Subsets II

因为input含有duplicate，所以在进入backtracking之前需要检查

1
2
3
4
5
6
7
8
def backtracking(self, nums, temp, res, start):
    res.append(list(temp))
    for i in range(start,len(nums)):
        if i > start and nums[i] == nums[i-1]:
            continue
        temp.append(nums[i])
        self.backtracking(nums, temp, res, i+1)
        temp.pop()

39 Combination Sum

本质上是一样的，每次传的时候target-candidates[i], 然后因为每个数字可以重复使用，所以index可以保持不变

1
2
3
4
5
6
7
8
9
10
def backtracking(self, candidates, target, res, temp, start):
    if target<0:
        return
    elif target == 0:
        res.append(list(temp))
    else:
        for i in range(start, len(candidates)):
            temp.append(candidates[i])
            self.backtracking(candidates, target - candidates[i], res, temp, i)
            temp.pop()

40 Combination Sum II

变化就是不可以重复利用数字，index+1

1
2
3
4
5
6
7
8
9
10
11
12
def backtracking(self, candidates, target, res, temp, start):
    if target<0:
        return
    elif target == 0:
        res.append(list(temp))
    else:
        for i in range(start, len(candidates)):
            if i > start and candidates[i-1] == candidates[i]:
                continue
            temp.append(candidates[i])
            self.backtracking(candidates, target - candidates[i], res, temp, i+1)
            temp.pop()

216 Combination Sum III

与上一道题的区别就是，输入为[1…9]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        self.backtracking(k,n,[],res,1)
        return res

    def backtracking(self, k, target, temp, res, start):
        if len(temp) > k:
            return
        elif len(temp) == k and target == 0:
            res.append(list(temp))
        else:
            for i in range(start, 10):
                temp.append(i)
                self.backtracking(k, target - i, temp, res, i+1)
                temp.pop()

Medium

22 Generate Parentheses

recursion rule 就是判断left，right的count啦，直到满足right == n

1
2
3
4
5
6
7
def dfs(self,temp, left, right, res,n):
    if left < n:
        self.dfs(temp+'(',left+1,right,res,n)
    if right < left:
        self.dfs(temp+')',left, right+1, res,n)
    if right==n:
        res.append(temp)

320. Generalized Abbreviation

这道题debug了好久，困惑于如何使得数字和字母不会在base case的时候重复导出

1
2
3
4
4
3d
2r1 2rd
...
1
2
3
4
5
6
7
8
9
10
def backtrack(res, word, pos, string, count):
    if pos == len(word):
        if count>0:
            string += str(count)
        res.append(string)
    else:
        backtrack(res,word,pos+1,string,count+1)
        ## 这个track保证了index每次不断加1 从而在base的时候输出，然后每一次count同时加1，为了记录count
        backtrack(res, word, pos+1, string + (str(count) if count>0 else "")+ word[pos], 0)
        ## 这个是为了退一步，先保存当前的count数字，然后因为数字不能连续，所以+word【index】，同时把count清0

二维backtracking

Posted on Edited on In Views: Valine:
Symbols count in article: 3.7k Reading time ≈ 3 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

LinkedList系列总结

24/27
[x] Easy
[x] Medium
[x] Hard
这种题，多画图，一步步来，确定哪个node指向哪个node就会好一点,之后把图放上来，会更容易复习！

基础

dummyNode

适用于头节点需要进行操作，增删改，亦或者保存头节点，不被后续操作改变

1
2
3
dummy = ListNode(0)
dummy.next = head
curr = head

reverseList

Iterative版本，简要来说就是记录下一节点，当前节点指向上一节点，同步移动上一节点和当前节点。最后的curr为空，prev为头也就是最初链表的最后一个元素

1
2
3
4
5
6
7
8
prev = None
curr = head
while curr:
    nextNode = curr.next
    curr.next = prev
    prev = curr
    curr = nextNode
return prev

Recursive版本的，一直到底，然后倒叙指针

1
2
3
4
5
second = head.next
head.next = None
rest = self.reverseList(second)
second.next = head
return rest

变种1 92. Reverse Linked List II
除了移动节点之外，关键是链接头和尾

1
2
pre.next.next = curr //pre.next 为最初的头，.next则链接后来的尾和最初的尾 1-2-3-4-5，1-4-3-2-5，2-5
pre.next = newHead // 1-4
Read more »