登录
  • #刷题
  • #leetcode

[FaceBook高频Medium] 即使是 Brute Force 解法,也要敢于 “亮剑”

realSimonX
5558
14
这两题都是 FaceBook 高频 Medium 题。

750. Number Of Corner Rectangles



这道题教会我们,要敢于给出题解,哪怕暂时想到的方法是 brute force 的。

先说最直接的想法。

我们枚举任意两行r1和r2,看这两行中存在多少列,满足在该列中第r1行和第r2行中对应的元素都是1。假设有counter列满足条件,那么这两行可以构成的的recangles的数量就是 counter * (counter - 1) / 2。最后返回所有rectangles的数量即可。

如果我们假设 grid 一共有 m 行 n 列,那么算法的时间复杂度就是 O(m^2n),空间复杂度是O(1)。

很多时候我们希望自己能一下子就命中最优解法,这固然好。但是更实际的情况是,在拿到一道题的时候,你并不知道这道题要怎么解,先想 brute force 方法,反而能够帮助你想更高级的方法。更何况,有些时候,高级方法并不一定更优,比如这道题。

-----------------------------------------------------------------------------------------------------------------------------------

这道题也是可以用 Dynamic Programming (DP) 来解的。

DP 主要就是要进行问题的拆解。想象一下,如果在原有的矩阵的基础上增加了一行,数量会怎么变化。



线段代表其两端是 1,红色线段是新加入的一行。我们只需要对比新加入的那行跟之前的线段有没有匹配上的就行了。

[mw_shl_code=python,true]class Solution(object):

def countCornerRectangles(self, grid):

count = collections.Counter()

ans = 0

for row in grid:

for c1, v1 in enumerate(row):

if v1:

for c2 in xrange(c1+1, len(row)):

if row[c2]:

ans += count[c1, c2]

count[c1, c2] += 1

return ans[/mw_shl_code]

时间复杂度:O(R*C^2)。其中 R, CR,C 指的是行和列。

空间复杂度:使用了 O(C^2) 的额外空间。

-----------------------------------------------------------------------

548. Split Array with Equal Sum



这道题给了我们一个数组,让我们找出三个位置,使得数组被分为四段,使得每段之和相等,问存不存在这样的三个位置,注意三个位置上的数字不属于任何一段。

这道题其实跟上次我们提到的问题是一样的。

拿到一道题,我们第一相当的肯定是,这道题我该用什么数据结构,该用什么算法,是 动态规划 还是 深度优先搜索。但是往往在实际面试的时候,恰恰有些题目他就是什么数据结构和算法也没有用,就是考一考你的全局规划思维和灵活度。

揣测此类问题到底在考察面试者什么能力的出题动机意义其实不大。这个就像是我们当年高考的时候,即使很多年过去,我们的思维能力与视野也长进了很多倍,仍然很难说清楚那些题目到底在考察什么能力。也许有些题目对于面试官来说有意义,但是对绝大数人就是随机的一些题目吧。而我们要做,就是在练习中中适应这些,将来在面试中能够自如应对这些题目。

拿到这一题,很多人可能或多或少的想把这道题往 动态规划 上面套,但是发现其实很难进行问题分解。那么根据我们上次文章的原则:“即使是 brute force 的方法,也要敢于亮剑。”,我们先来看看暴力解法可以这么解这道题目。

最暴力的方法很简单,肯定是套三个循环,遍历三个数的位置。

----

有了基础的解法,下面我们来看一看怎么优化这个基础算法:

- 对于这种有三个位置的问题,一个非常常见的做法就是,我们先固定中间那个点,这样在遍历另外两个点的时候,就可以有效的减少可能性。所以对这一题,我们只要改变一下循环的顺序,就可以把时间复杂度用 `O(n^3)` 变成 `O(n^2)`。

- 在进行查询的两边是否有求和相同的 subarray 的时候,我们可以用到 Hashmap 的数据结构,加快查找。

- 我们在求和的时候,可以用到一种叫做 `PreSum` 的技术。这个技术其实很简单,就是我们维护一个数组 `res`,`res` 数组的第 n 个元素保存 被求和数组 前 n 个数的和。当我们想得到 `[n, m]` 的求和时候,我们需要计算一下 `res[m]-res[n]`,这是典型的拿空间换时间。

- 另外一个非常常见的做法是,我们可以提前终止一些根本不可能的方案。这道题里面,在我们确定中间点 `j` 的时候,我们可以 check 一下,如果 `j` 前的和与 `j` 后的相差超过数组中最大值减最小值, 那就可以剪掉。

最后贴一下解法:

[mw_shl_code=python,true]# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

def findClosestLeaf(self, root: TreeNode, k: int) -> int:

isLeaf = [False] * 1001 # 至多1000个结点



from collections import defaultdict

g = defaultdict(set)



# DFS遍历建图

def dfs(root):

# print("...")

if root != None and root.left == None and root.right == None:

# print("是叶子结点...")

isLeaf[root.val] = True

if root.left:

g[root.val].add(root.left.val)

g[root.left.val].add(root.val)

dfs(root.left)

if root.right:

g[root.val].add(root.right.val)

g[root.right.val].add(root.val)

dfs(root.right)

# 执行建图过程

dfs(root)



# BFS查找距离目标值结点最近的叶子结点

visited = { k }

que = [k] # 模拟队列

while len(que) != 0:

top = que.pop()

if isLeaf[top]:

return top

for val in g[top]:

if val not in visited:

if isLeaf[val]:

return val

que.insert(0, val)

visited.add(val)

return -1[/mw_shl_code]

码字不易,贫农求一波米~~~【加米不消耗自己的米,嘻嘻😜】
14条回复
热度排序

发表回复