MathWorks题库
收到了MathWorks的面试呀！赶紧来抱个佛脚。
Huffman树
用构建Huffman树的做法做，本质上是greedy，复杂度是 \(O(n^2)\) 。
from typing import *
class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
res = 0
while len(arr) != 1:
largestLeafValue = float("-inf")
product = float("inf")
index = -1
for i in range(0, len(arr) - 1):
a = arr[i]
b = arr[i + 1]
if a * b < product:
index = i
product = a * b
largestLeafValue = max(a, b)
res += product
arr[index: index + 2] = [largestLeafValue]
return res
s = Solution()
print(s.mctFromLeafValues([6, 2, 4])) # 32
验证数组是否是二分搜索树的先根遍历
这道题好难，我一开始没想出来。我只知道二分搜索树的中根遍历能得到一个从小到大排好序的数组，但是不知道前根遍历有什么性质。
然后就想先重建树、然后再取树的先根遍历，再利用先根遍历的性质来验证。但是一时间没有想到怎样在 \(O(n)\) 内重建树。
后来想了两天，终于想到了一个绝妙的方法！翻了一圈discussion都没有发现我这个方法。
这个方法的本质还是重建树，但是是尽最大努力来重建树，一旦发现接下来没办法继续重建，就说明数组不是BST的先根遍历。听我慢慢讲。
最关键的事情是，在重建过程中，遇到某个数字需要插入到BST里的时候，需要满足两方面条件
不能违背preorder的性质
不能违背BST的性质
也就是说，要想把接下来一个数字插入到BST里、形成更大的一颗BST之前，这个数字不是随便什么地方都能插入的，要满足插入之后，树的preorder仍然是原数组，同时树仍然是BST。所以如果发现下一个数字没地方插入的时候，说明有问题。
那存在随便一个数字可能有多个位置可以插入的情况吗？没有，BST的性质保证了某个数字只能出现在某个固定的区间里，不可能出现在多个区间里。
所以定义一个叫做 插槽 的东西，来表示在不违背preorder的性质下，下一个数字能插入的位置。
先看上图的上半部分。
在5和2已经插入、将要插入6的时候，发现在不违背preorder的性质的前提下，BST里面只有3个位置可能可以插入6这个数字。什么叫做不违背preorder的性质呢？思考一下，如果把6放在这3个位置中的某个位置，整棵树经过preorder之后仍然得到 [5, 2, 6] ，所以这是不违背preorder的性质的。
既然这3个位置都不违反preorder的性质，那么为啥一定放到右上那个位置呢？因为每个插槽里的数也是有范围的，这个范围由BST的性质决定。比如 2 的左边插槽里只能放一个 \((-\infty, 2)\) 区间里的数字，不能放别的，如果放了超出这个范围的数字，那么这棵树就不是BST了。比如放个3，那么这棵树就不是BST了。
我们把每个可用插槽的范围都写出来，发现6只能放在右上的插槽里。所以到这里一切还可以。
再看图的下半部分，出现问题了。什么问题呢？现在6已经插入了BST了，将要插入1。插入6之后，在6的下面创造了两个新的插槽，这两个插槽分别可以放入范围在 \((5, 6)\) 区间内和 \((6, +\infty)\) 区间内的数字。
现在将要插入1，在不违背preorder性质的前提下，只有6的两个子节点这两个插槽可以插入1。为啥不能插入刚才 2 那里的两个插槽呢？因为如果插在那里了，preorder就不是 [5, 2, 6, 1] 了，而变成了 [5, 2, 1, 6] 了，和原数组不符合了。所以1只能插在6的下面这两个插槽里面。
所以这里我们总结出了一个很重要的规律，就是每当有一个新的数字要插入BST的时候，我们应该从小到大检查每个可用插槽能接受数字的范围，如果某个插槽里不能放入当前要插入的数字，这个插槽就应该永久删除、不可使用了。即，一旦有某个数字不能放入某个插槽，那么一定有这个数字之后的任何一个数字都无法放入那个插槽，否则违反preorder性质。
刚才插入6的时候，我们排除了2下方的两个插槽 \((-\infty, 2)\) 和 \((2, 5)\) ，插入6之后，之后的数字再也没法插入这两个插槽了，所以它们不再是可用插槽。
现在1只有两个可用插槽，应该放入哪个插槽呢？我们发现都不行，因为一个插槽需要插入 \((5, 6)\) 另一个需要插入 \((6, +\infty)\) ，1不属于其中的任何一个区间。所以重建树的过程到这里就卡住了。
所以可以表明对于 [5, 2, 6, 1, 3] ，我们找不到某个BST使得它的preorder正好是这个数组。
另外说下如果能成功插入数字的话，会产生哪两个新的可用插槽。很显然，假设数字 \(v\) 填入了插槽 \((a, b)\) ，那么会产生 \((a, v)\) 和 \((v, b)\) 这两个新的插槽。比如刚才6填入 \((5, +\infty)\) 之后，产生了 \((5, 6)\) 和 \(（6， +\infty)\) 这两个插槽。
可能还是很难理解。我看了discussion里的答案，也不能理解他们的做法。后来问了 @tzb ，他给出了和discussion里同样的做法，给我讲了一遍，我还是不能理解。因为我没法理解stack里的数到底是什么意义。
在我的解法里，stack里面的元素有明确的意义，是插槽能接受数字的范围，是一个区间。
当需要插入一个新的数字的时候，会不停pop掉stack顶端的区间。如果发现数字不能放入那个区间，那个区间也不会回到stack，会直接扔掉，符合刚才的分析；如果发现数字可以放入那个区间，那么说明数字可以放入那个插槽。放入之后，新的节点会产生2个新的插槽，这两个插槽的区间也会进入stack。
from typing import *
# class Solution:
# def verifyPreorder(self, preorder: List[int]) -> bool:
# if preorder:
# root = preorder[0]
# rightTreeIndex = -1
# for i, v in enumerate(preorder[1: ], 1):
# if v >= root:
# rightTreeIndex = i
# break
# else:
# return self.verifyPreorder(preorder[1: ])
# for v in preorder[rightTreeIndex: ]:
# if v < root:
# return False
# else:
# return self.verifyPreorder(preorder[rightTreeIndex: ]) and self.verifyPreorder(preorder[1: rightTreeIndex])
# else:
# return True
# 这样可以做，但是实在是太慢了
# 我自己的做法
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stack = [(float("-inf"), float("inf"))] # 第一个数字当然只能插入到根节点的位置。而且因为现在BST里面还没有元素，所以第一个插槽的范围是(-inf, inf)
for v in preorder: # 开始重建BST，尝试插入preorder中的每个数字
while len(stack) != 0 and stack[-1][1] < v: # 检测stack顶端的插槽能否放入当前数字
stack.pop() # 如果不能放入当前数字，就直接扔掉这个插槽，因为反正之后的数字也没法放进去
if len(stack) != 0 and stack[-1][0] < v < stack[-1][1]: # 数字可以放入某个插槽
interval = stack.pop() # 把数字填入这个插槽
stack.append((v, interval[1])) # 填入数字之后，又产生了两个新的可用插槽。也可以理解为把刚才的插槽分解成了两个插槽
stack.append((interval[0], v))
else: # 说明stack空了，没有找到任何一个插槽能放下当前数字
return False # BST重建失败
return True # 重建成功，每个数字都放入了BST中正确的位置
# leetcode某个discussion的做法，我不懂
# class Solution:
# def verifyPreorder(self, preorder: List[int]) -> bool:
# stack = []
# lower = float("-inf")
# for v in preorder:
# while len(stack) != 0 and stack[-1] < v:
# lower = stack.pop()
# if v < lower:
# return False
# else:
# stack.append(v)
# return True
# tzb的做法，我不懂。感觉和discussion的做法差不多
# class Solution:
# def verifyPreorder(self, preorder: List[int]) -> bool:
# stack = []
# isBST = True
# root = float("-inf")
# for v in preorder:
# if v < root:
# isBST = False
# break
# while len(stack) != 0 and v > stack[-1]:
# root = stack.pop()
# stack.append(v)
# return isBST
s = Solution()
print(s.verifyPreorder([5, 2, 6, 1, 3])) # false
print(s.verifyPreorder([5, 2, 1, 3, 6])) # true
print(s.verifyPreorder([10, 7, 4, 8, 6, 40, 23])) # false
所有substring里字典序最大的那个substring
首先可以确定，解一定是这个字符串的一个后缀，因为对于任意以第 \(i\) 个字符开始的substring，字典序最大的那个substring一定是从第 \(i\) 个字符到字符串的结尾。
确定了解是后缀之后，我们要搜索的空间从 \(O(n^2)\) 降低到了 \(O(n)\) ，因为一个长度为 \(n\) 的字符串总共有 \(O(n)\) 个后缀。但是复杂度仍然是 \(O(n^2)\) ，因为比较两个substring字典序的复杂度是 \(O(n)\) 。
想到了一个叫做后缀树的东西，但是后缀树的 \(O(n)\) 构造实在是太难了，完全没看懂。
后来发现了一个叫做后缀数组suffix array的东西，可以不用构造后缀树，用一种叫做 倍增构造法 的算法，就可以在 \(O(n)\) 内得到原字符串 s 的每个后缀 s[i: ] 放在一起按字典序从小到大排序之后的 排名 。然后再找到那个排名正好是 \(n - 1\) 的后缀，就是答案了。
from typing import *
# import heapq
# class Node:
# def __init__(self):
# self.children: Dict[str, Node] = {}
# self.heap: List[str] = []
# heapq.heapify(self.heap)
# self.value: Any = None
# class Solution:
# def lastSubstring(self, s: str) -> str:
# suffixTree = self.getSuffixTree(s)
# res = []
# head = suffixTree
# while len(head.children) != 0:
# largest = heapq.nlargest(1, head.heap)[0]
# res.append(largest)
# head = head.children[largest]
# return "".join(res)[: -1]
# def getSuffixTree(self, s: str) -> Node:
# root = Node()
# for i in reversed(range(0, len(s))):
# suffix = s[i: ]
# head = root
# for v in suffix + "\x00":
# if v not in head.children:
# head.children[v] = Node()
# heapq.heappush(head.heap, v)
# head = head.children[v]
# return root
# 后缀树构造太慢了
class Solution:
def lastSubstring(self, s: str) -> str:
ranks = self.getRankArray(s) # ranks[i]表示s[i: ]按字典序从小到大排序后的排名
for i, v in enumerate(ranks):
if v == len(s) - 1:
return s[i: ]
def getRankArray(self, s: str) -> List[int]:
k = 1
xy = list(s)
rankMapping = dict((v, i) for i, v in enumerate(sorted(set(xy))))
while True:
# rank = [rankMapping[v] for v in xy]
# if len(rank) == len(set(rank)):
if len(rankMapping) == len(s):
return [rankMapping[v] for v in xy]
else:
for i in range(len(xy)):
if i + k < len(s):
# xy[i] = (rank[i], rank[i + k])
xy[i] = (rankMapping[xy[i]], rankMapping[xy[i + k]])
else:
# xy[i] = (rank[i], 0)
xy[i] = (rankMapping[xy[i]], 0)
# rankMapping = dict((v, i) for i, v in enumerate(sorted(set(xy))))
rankMapping.clear()
for i, v in enumerate(sorted(set(xy))):
rankMapping[v] = i
k += 1
s = Solution()
print(s.lastSubstring("abab")) # bab
print(s.lastSubstring("leetcode")) # tcode
离所有大楼距离之和最近的空地
我的做法是对每个大楼，都用BFS计算出图上每个空地到这栋大楼的最小距离，然后再遍历图上的每块空地，找出能到达所有大楼的、同时到达所有大楼的最小距离之和最小的那块空地。
这样复杂度应该是 \(O(m^2 n^2)\) 。超时了。
from typing import *
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
rowCount = len(grid)
columnCount = len(grid[0])
buildings = set()
obstacles = set()
for rowIndex, row in enumerate(grid):
for columnIndex, box in enumerate(row):
position = (rowIndex, columnIndex)
if box == 1:
buildings.add(position)
elif box == 2:
obstacles.add(position)
positionDistanceMapping = dict()
queue = []
traveled = set()
for building in buildings:
# queue = [building]
queue.clear()
queue.append(building)
traveled.clear()
distance = 0
while queue:
size = len(queue)
for _ in range(size):
node = queue.pop(0)
rowIndex, columnIndex = node
neighbors = [
(rowIndex - 1, columnIndex),
(rowIndex + 1, columnIndex),
(rowIndex, columnIndex - 1),
(rowIndex, columnIndex + 1)
]
for neighbor in neighbors:
if 0 <= neighbor[0] < rowCount and 0 <= neighbor[1] < columnCount and grid[neighbor[0]][neighbor[1]] == 0 and neighbor not in traveled:
queue.append(neighbor)
traveled.add(node)
if node not in buildings and node not in obstacles:
if node not in positionDistanceMapping:
positionDistanceMapping[node] = dict()
positionDistanceMapping[node][building] = distance
else:
positionDistanceMapping[node][building] = distance
distance += 1
res = float("+inf")
for position, distanceToBuildings in positionDistanceMapping.items():
if len(distanceToBuildings) != len(buildings):
continue
else:
res = min(res, sum(distanceToBuildings.values()))
if res == float("+inf"):
return -1
else:
return res
s = Solution()
print(s.shortestDistance([[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]])) # 7
print(s.shortestDistance([[2,0,0,2,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,1,2,0,2,0,1,1,0],[0,1,0,1,1,2,0,0,2,0,0,2,0,2,2,0,2,0,2,0,0,0,0,0,0,0,0,0],[1,0,0,1,2,0,0,2,0,2,0,0,0,0,0,0,0,0,0,2,0,2,0,0,0,0,0,2],[0,0,2,2,2,1,0,0,2,0,0,0,0,0,0,0,0,0,2,2,2,2,1,0,0,0,0,0],[0,2,0,2,2,2,2,1,0,0,0,0,1,0,2,0,0,0,0,2,2,0,0,0,0,2,2,1],[0,0,2,1,2,0,2,0,0,0,2,2,0,2,0,2,2,2,2,2,0,0,0,0,2,0,2,0],[0,0,0,2,1,2,0,0,2,2,2,1,0,0,0,2,0,2,0,0,0,0,2,2,0,0,1,1],[0,0,0,2,2,0,0,2,2,0,0,0,2,0,2,2,0,0,0,2,2,0,0,0,0,2,0,0],[2,0,2,0,0,0,2,0,2,2,0,2,0,0,2,0,0,2,1,0,0,0,2,2,0,0,0,0],[0,0,0,0,0,2,0,2,2,2,0,0,0,0,0,0,2,1,0,2,0,0,2,2,0,0,2,2]])) #
一组一组地颠倒链表
这题真的写了巨久。写完过了发现其实很简单。
因为题目要求最后不满 \(k\) 个的元素不要动，所以我就先遍历一遍链表，得到链表的总长度，然后看一下总共需要颠倒多少 段 。
知道了需要颠倒多少段之后，就开始一段一段分别颠倒就好了。
from typing import *
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if head != None and k != 1: # 如果k是1的话，等于不需要颠倒
sentinel = ListNode(None) # 假节点
sentinel.next = head
length = 0
while head != None: # 先遍历一遍链表，得到长度
head = head.next
length += 1
segmentCount = length // k # 需要颠倒的段的数量
previousSegmentEnd = sentinel # 前一段的最后一个节点
for segmentIndex in range(segmentCount): # 颠倒那么多段
head = previousSegmentEnd.next.next
previous = previousSegmentEnd.next
for index in range(k - 1): # 因为是分段颠倒，所以每段只需要颠倒k - 1个链
temp = head.next
head.next = previous
previous = head
head = temp
# 颠倒完这一段了，出for之后，head指向的是下一段的第一个节点、previous指向的是当前段颠倒之后的第一个节点
temp = previousSegmentEnd.next # temp现在是当前段颠倒后的最后一个节点
previousSegmentEnd.next = previous # 把上一段最后一个节点的下一个节点指向当前段颠倒后的第一个节点
temp.next = head # 当前段颠倒后的最后一个节点的下一个节点指向下一段的第一个节点
previousSegmentEnd = temp # 把当前段颠倒后的最后一个节点设置为上一段最后一个节点，进入下一个段
return sentinel.next
elif head != None and k == 1:
return head
else:
return head
# 用于测试
def linkedListToList(self, head: ListNode) -> List:
res = []
while head:
res.append(head.val)
head = head.next
return res
def listToLinkedList(self, array: List) -> ListNode:
sentinel = ListNode(None)
head = sentinel
for v in array:
head.next = ListNode(v)
head = head.next
return sentinel.next
s = Solution()
print(s.linkedListToList(s.reverseKGroup(s.listToLinkedList([1, 2, 3, 4, 5]), 3))) # 3 2 1 4 5
print(s.linkedListToList(s.reverseKGroup(s.listToLinkedList([1, 2, 3, 4, 5, 6]), 3))) # 3 2 1 6 5 4
print(s.linkedListToList(s.reverseKGroup(s.listToLinkedList([1, 2, 3, 4, 5]), 2))) # 2 1 4 3 5
哪些词语可以用一行键盘打出
很简单，搞一个字符到键盘排号的映射。
class Solution:
def findWords(self, words: List[str]) -> List[str]:
charRowMapping = {} # 搞一个字符到排号的映射
charRowMapping.update({v: 0 for v in "qwertyuiop"}) # 第一排的所有字符
charRowMapping.update({v: 1 for v in "asdfghjkl"}) # 第二排的所有字符
charRowMapping.update({v: 2 for v in "zxcvbnm"}) # 第三排的所有字符
res = []
for word in words:
if len(set(charRowMapping[v] for v in word.lower())) == 1: # 如果单词里面所有的字符都在同一排
res.append(word)
return res
还写了个rust版的
struct Solution;
use std::collections::HashMap;
use std::collections::HashSet;
impl Solution {
pub fn find_words(words: Vec<String>) -> Vec<String> {
let mut charRowMapping: HashMap<char, i32> = HashMap::new();
charRowMapping.extend("qwertyuiop".chars().map(|v| (v, 0)));
charRowMapping.extend("asdfghjkl".chars().map(|v| (v, 1)));
charRowMapping.extend("zxcvbnm".chars().map(|v| (v, 2)));
let mut res: Vec<String> = vec![];
for word in words.iter() {
let rows: HashSet<i32> = word.to_lowercase().chars().map(|v| *charRowMapping.get(&v).unwrap()).collect();
if rows.len() == 1 {
res.push(word.clone());
}
}
return res;
}
}
HashMap.extend() 真好用啊。
数组的度
度定义为出现最多次数的元素出现的次数，找一个尽可能短的、度和原数组一样大的substring。
做法很简单，记录每 种 元素出现的次数、第一次出现的位置、最后一次出现的位置。那么符合要求的substring就是那个出现次数最多、最后一次出现的位置和第一次出现的位置之差最小的substring啦。
为什么呢，因为反正只要满足substring里含有那么多的那种元素就可以了，没有必要包含第一次出现之前的其他种类的元素和最后一次出现的位置之后的其他种类的元素，即使包括了那些元素，也只会徒增substring的长度，而substring的度不变，所以这样吃力不讨好的事情何必去做呢。
from typing import *
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
counter: Dict[Hashable, List[int, int, int]] = {} # key是数字，value是一个list，第一个元素表示key出现的次数、第二个元素表示key第一次出现的位置、第三个元素表示key最后一次出现的位置
maxFrequency = 0 # 一边构造counter，一边记下最高频次
for i, v in enumerate(nums):
if v in counter: # 已经出现过了
counter[v][0] += 1 # 频次+1
counter[v][2] = i # 更新最后出现的位置
else: # 没有见过
counter[v] = [1, i, i] # 记下来
maxFrequency = max(maxFrequency, counter[v][0])
res = float("inf")
for k, v in counter.items():
if v[0] == maxFrequency: # 如果是出现频次最高的元素
res = min(res, v[2] - v[1] + 1) # 最短相同度substring一定是从这个元素第一次出现的位置到最后一次出现的位置之后那个substring
return res
s = Solution()
print(s.findShortestSubArray([1, 2, 2, 3, 1])) # 2
print(s.findShortestSubArray([1, 2, 2, 3, 1, 4, 2])) # 6
颠倒链表
颠倒链表，返回颠倒后的第一个节点。
题目没有规定什么，所以可以有3种写法
我最喜欢的就是先变成list，颠倒，再变回来
一边遍历，一边从后往前建一个新的链表
原地颠倒
面试估计会要你写原地颠倒，因为省空间。
from typing import *
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head:
previous = head # previous指向第一个节点
head = head.next # head指向第二个节点
previous.next = None # 第一个节点颠倒之后变成最后一个节点，最后一个节点后面没有节点了
while head:
temp = head.next
head.next = previous
previous = head
head = temp
# 出while之后，head是null，previous是颠倒后的第一个节点
return previous # 所以返回previous
else:
return head
有多少条能到达终点的路径
给一个地图，机器人开始在左上角，终点在右下角，地图上标0的地方都是可以走的，标1的地方是障碍不能走。机器人每一步只能要么往下走、要么往右走。问机器人要到达终点总共有多少条不同的路径。
用DP，设 dp[i, j] 是从起点到 \((i, j)\) 的路径数量。思考一下 dp[i, j] 和前面的项有什么关系。
如果 \((i, j)\) 上是障碍物的话，那么无论如何都到达不了 \((i, j)\) ，所以这时候 dp[i, j] = 0 。
如果 \((i, j)\) 上不是障碍物的话，那么怎样才能到达 \((i, j)\) 呢？只有两种方法：从上方的 \((i - 1, j)\) 往正下方走一格；或者从左边的 \((i, j - 1)\) 往右边走一格。那么到达 \((i - 1, j)\) 和 \((i, j - 1)\) 总共有多少种方法呢？根据定义，是 dp[i - 1, j] + dp[i, j - 1] ，所以到达 \((i, j)\) 的方法总共就有这么多种。
from typing import *
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1: # 为了对付屑test case
return 0
rowCount = len(obstacleGrid)
columnCount = len(obstacleGrid[0])
dp = dict()
# 初始条件
dp[0, 0] = 1
for columnIndex in range(1, columnCount):
if obstacleGrid[0][columnIndex] == 0:
dp[0, columnIndex] = dp[0, columnIndex - 1]
else:
dp[0, columnIndex] = 0
for rowIndex in range(1, rowCount):
if obstacleGrid[rowIndex][0] == 0:
dp[rowIndex, 0] = dp[rowIndex - 1, 0]
else:
dp[rowIndex, 0] = 0
# 开始填表
for rowIndex, row in enumerate(obstacleGrid[1: ], 1):
for columnIndex, box in enumerate(row[1: ], 1):
if box == 0:
dp[rowIndex, columnIndex] = dp[rowIndex - 1, columnIndex] + dp[rowIndex, columnIndex - 1]
else:
dp[rowIndex, columnIndex] = 0
return dp[rowCount - 1, columnCount - 1]
s = Solution()
print(s.uniquePathsWithObstacles([
[0,0,0],
[0,1,0],
[0,0,0]
])) # 2
print(s.uniquePathsWithObstacles([
[0, 0, 0],
])) # 1
print(s.uniquePathsWithObstacles([
[0, 1, 0],
])) # 0
print(s.uniquePathsWithObstacles([[1]])) # 0 屑test case
print(s.uniquePathsWithObstacles([[0]])) # 1 屑test case
还写了个rust的。
struct Solution;
use std::collections::HashMap;
impl Solution {
pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
let rowCount: usize = obstacle_grid.len();
let columnCount: usize = obstacle_grid[0].len();
if obstacle_grid[0][0] == 1 || obstacle_grid[rowCount - 1][columnCount - 1] == 1 {
return 0;
}
let mut dp: HashMap<(usize, usize), i32> = HashMap::new();
dp.insert((0, 0), 1);
for columnIndex in 1..columnCount {
if obstacle_grid[0][columnIndex] == 0 {
dp.insert((0, columnIndex), *dp.get(&(0, columnIndex - 1)).unwrap());
} else {
dp.insert((0, columnIndex), 0);
}
}
for rowIndex in 1..rowCount {
if obstacle_grid[rowIndex][0] == 0 {
dp.insert((rowIndex, 0), *dp.get(&(rowIndex - 1, 0)).unwrap());
} else {
dp.insert((rowIndex, 0), 0);
}
}
for (rowIndex, row) in obstacle_grid.iter().enumerate().skip(1) {
for (columnIndex, value) in row.iter().enumerate().skip(1) {
if *value == 0 {
dp.insert((rowIndex, columnIndex), *dp.get(&(rowIndex - 1, columnIndex)).unwrap() + *dp.get(&(rowIndex, columnIndex - 1)).unwrap());
} else {
dp.insert((rowIndex, columnIndex), 0);
}
}
}
return *dp.get(&(rowCount - 1, columnCount - 1)).unwrap()
}
}
备注
[[1]], [[0]] 这算什么屑test case？
用stack实现queue
from typing import *
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
queue = []
while self.stack:
queue.append(self.stack.pop())
res = queue.pop()
while queue:
self.stack.append(queue.pop())
return res
def peek(self) -> int:
"""
Get the front element.
"""
queue = []
while self.stack:
queue.append(self.stack.pop())
res = queue.pop()
queue.append(res)
while queue:
self.stack.append(queue.pop())
return res
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.stack) == 0
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
还写了个rust的。
use std::collections::VecDeque;
struct MyQueue {
stack: VecDeque<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyQueue {
/** Initialize your data structure here. */
fn new() -> Self {
return MyQueue {
stack: VecDeque::new(),
};
}
/** Push element x to the back of queue. */
fn push(&self, x: i32) {
self.stack.push_back(x);
}
/** Removes the element from in front of queue and returns that element. */
fn pop(&self) -> i32 {
let mut queue: VecDeque<i32> = VecDeque::new();
while !self.stack.is_empty() {
queue.push_back(self.stack.pop_back().unwrap());
}
let res: i32 = queue.pop_back().unwrap();
while !queue.is_empty() {
self.stack.push_back(queue.pop_back().unwrap());
}
return res;
}
/** Get the front element. */
fn peek(&self) -> i32 {
let mut queue: VecDeque<i32> = VecDeque::new();
while !self.stack.is_empty() {
queue.push_back(self.stack.pop_back().unwrap());
}
let res: i32 = queue.pop_back().unwrap();
queue.push_back(res);
while !queue.is_empty() {
self.stack.push_back(queue.pop_back().unwrap());
}
return res
}
/** Returns whether the queue is empty. */
fn empty(&self) -> bool {
return self.stack.is_empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* let obj = MyQueue::new();
* obj.push(x);
* let ret_2: i32 = obj.pop();
* let ret_3: i32 = obj.peek();
* let ret_4: bool = obj.empty();
*/
有多少条能到达终点的路径
63 的简单版本，没有障碍。
from typing import *
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
rowCount = m
columnCount = n
dp = dict()
dp[0, 0] = 1
for columnIndex in range(1, columnCount):
dp[0, columnIndex] = 1
for rowIndex in range(1, rowCount):
dp[rowIndex, 0] = 1
for rowIndex in range(1, rowCount):
for columnIndex in range(1, columnCount):
dp[rowIndex, columnIndex] = dp[rowIndex - 1, columnIndex] + dp[rowIndex, columnIndex - 1]
return dp[rowCount - 1, columnCount - 1]
s = Solution()
print(s.uniquePaths(3, 2)) # 3
print(s.uniquePaths(7, 3)) # 28
按anagram分组
如果两个字符串的直方图相同，则互为anagram。比如 eat, tea 都是由1个 e 、1个 a 和1个 t 组成，所以它们互为anagram。
我的做法是搞一个hash map，key是某种变换后的结果，互为anagram的字符串经过这个变换得到相同的东西，value是所有互为anagram的字符串。
怎样找到一种合适的变换使得互为anagram的字符串经过这个变换变成相同的东西呢？既然定义里面说了直方图相同，那么用 Counter 不就好了？可惜 Counter 不能被hash，所以做不了key。
所以只能给字符串里的字符排序，很显然如果两个字符串互为anagram的话，它们里面的字符按ascii从小到大排序之后形成的字符串是相同的；如果两个字符串不互为anagram的话，再怎么排序得到的字符串都不同。
from typing import *
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = dict()
for v in strs:
root = "".join(sorted(v))
if root in res:
res[root].append(v)
else:
res[root] = [v]
return list(res.values())
2020/1/8
面试体验
2020/1/10号下午2点面的，面试我的是一个印度小姐姐。
先是问了我最喜欢的项目是什么，在这个项目里遇到了什么问题，怎么解决的。
然后开始狂问面向对象设计，问面向对象里的封装、继承概念，问面向对象有什么优势。
问了机器学习里的一些概念，问最小二乘法的原理，问过拟合是怎么回事，怎么看出过拟合了。
然后就是线代，问了如何判断一个矩阵是否可逆，逆矩阵、转置后的矩阵的行列式和原矩阵的关系，特征值的含义。
问了一些Python的语法，字符串的immutable特性。用Python实现了一些很简单的操作。
然后就问我有没有什么问题要问她。
是的没错，一道算法题都没问……
看来要恶补OOP设计的内容了呀。
2020/1/10