技能看板

（1）Python中heapq默认是小根堆。在选择TopK中前K小的元素问题中，需要大根堆，因此在存储的时候，存储的是元素的负值。温情提示：

heapq.heapify(arr);
heapq.heappop(arr);
heapq.heappush(arr);

（2）Python中对二维数据的边界处理

假设grid是一个二维数组，对grid的边界处理如下：
if not grid or not grid[0]:
	return 0

针对二维数组的初始化：

rows, cols = [[0] * len(cols) for _ in range(rows)]

（3）统计元素出现的次数

counter = {}
for val in vals:
	counter[val] = counter.get(val, 0) + 1

counter排序：
counter = sorted(counter, key=lambda x: (x[1], x[0]), reverse=True)

Python自带容器类型中的计数器：
import collections
[val[0] for val in collections.Counter(vals).most_common(k)]

题目列表

1.两数之和

将求和问题转化为一个检索问题。曾经看到业界前辈的两个观点：（1）将架构问题转化为算法问题（2）O(lgN)的问题可以转化为O(1)的问题

2.两数相加

有难度。需要模拟加法操作。但是可以通过朴素的解法求解：（1）链表反转 （2）创建链表

3.无重复字符的最长子串

有难度。

4.每日气温

有难度。暴力法+单调栈

5.出现频率最高的前K个元素

比较直接的方法可以参考技能看板中的(3)的解法，这里更有意思的是基于大根堆的方法：

dic = collections.Counter(nums)
#自己实现heap，是基于数组做的
heap, ans = [], []
for i in dic:
	heapq.heappush(heap, (-dic[i], i))#堆中可以存储一个元组
for _ in range(k):
	ans.append(heapq.heappop(heap)[1])
return ans

6.最长递增子序列的长度

动态规划的经典题目，优雅有趣。相关的题目比较多，注意区分是长度还是值。代码如下：

定义dp[i]为：以第i个数字结尾的最长上升子序列的长度。

if not nums:
	return 0
dp = [1] * len(nums)
for i in range(len(nums)):
	#计算dp[i]的时候，遍历i之前的区间范围
	for j in range(i):
		if nums[i] > nums[j]:
			dp[i] = max(dp[i], dp[j]+1)
return max(dp)

比较有意思的另外一个思路是：二分法。

7.乘积最大子数组

注意：这道题目由于是计算乘积，对于乘积来说，“负负得正”。这里给出一种比较清晰的解法：

def maxProduct(nums):
	maxDp = [nums[0]]
	minDp = [nums[0]]
	for i in nums[1:]:
		#定义三个状态，从三个状态中选择后做值更新
		tmp = (i * maxDp[-1], i * minDp[-1], i)
		maxDp.append(max(tmp))
		minDp.append(min(tmp))
	return max(maxDp)

作为对比的经典题目：最大子序和。代码如下：

假设f(i)表示以i结尾的最大子序。则f(i) = max(f(i-1)+nums[i], nums[i])
def maxSubArray(nums):
	for i in range(1, len(nums)):
		nums[i] = max(nums[i-1]+nums[i], nums[i])
	return max(nums)

8.编辑距离

LC中的hard类题目。给定两个字符串A和B，用dp[i][j]表示A的前i个字母和B的前j个字母之间的编辑距离，则d[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i][j])

9.买卖股票的最大价值

我们关心的是历史过程中股票的最小价格和收益
def maxProfit(prices):
	minPrice = float("inf")
	maxProfit = 0
	for price in prices:
		minPrice = min(minPrice, price)
		maxProfit = max(maxProfit, price-minPrice)
	return maxProfit

10.单词拆分

TIPS：博主自己在曾经的一次面试时，两道medium中就有一道该题目。

定义dp[i]表示到第i个字符的时候，是否为能够被拆分成字典里的单词，
则状态转移矩阵为：dp[j] = dp[i] and s[i:j+1] in wordDict

def wordBreak(s, wordDict):
	dp = [True] + [False] * len(s)
	for i in range(len(s)):
		if flag[i]:
			for j in range(i+1, len(s)):
				if s[i:j] in wordDict:
					dp[j] = True
	return dp[-1]