DarkAlexWang's Blog
0%

Posted on Edited on In Symbols count in article: 5.5k Reading time ≈ 5 mins.

Stack性质

定义

Stack的定义便是先进后出，在python中用list实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Stack(object):
	def __init__(self):
		self.stack = []
	def push(self, i):
		self.stack.append(i)
	def pop(self):
		if self.stack：
			return self.stack.pop()
		else:
			raise("Error")
	def peek(self):
		return self.stack[-1]

Basic 题目

225. Implement Stack using Queues

只用一个queue，每次append的时候，都要把前面的给pop出来再append进去

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
class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []
        

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.queue.append(x)
        size = len(self.queue)
        while size > 1:
            self.queue.append(self.queue.pop(0))
            size -= 1      

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.queue.pop(0)
        

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.queue[0]
        

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return len(self.queue) == 0
        
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
Read more »

Posted on In Symbols count in article: 12k Reading time ≈ 11 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 Symbols count in article: 9.8k Reading time ≈ 9 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 Symbols count in article: 72 Reading time ≈ 1 mins.

浅谈一下爱情的看法

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

Posted on Edited on In 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 Symbols count in article: 12k Reading time ≈ 11 mins.

Tree的性质

Divide and Conquer模版

1
2
3
4
5
6
7
8
9
10
11
12
13
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 Symbols count in article: 2.4k 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 Symbols count in article: 5.3k 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 Symbols count in article: 4.3k 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 Symbols count in article: 3.3k 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
22
23
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