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

这两题都是 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，红色线段是新加入的一行。我们只需要对比新加入的那行跟之前的线段有没有匹配上的就行了。

1. class Solution(object):
   
2.     def countCornerRectangles(self, grid):
   
3.         count = collections.Counter()
   
4.         ans = 0
   
5.         for row in grid:
   
6.             for c1, v1 in enumerate(row):
   
7.                 if v1:
   
8.                     for c2 in xrange(c1+1, len(row)):
   
9.                         if row[c2]:
   
10.                             ans += count[c1, c2]
    
11.                             count[c1, c2] += 1
    
12.         return ans

复制代码

时间复杂度：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` 后的相差超过数组中最大值减最小值, 那就可以剪掉。

最后贴一下解法：

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, x):
   
4. #         self.val = x
   
5. #         self.left = None
   
6. #         self.right = None
   
7. 
   
8. class Solution:
   
9.     def findClosestLeaf(self, root: TreeNode, k: int) -> int:
   
10.         isLeaf = [False] * 1001 # 至多1000个结点
    
11.         
    
12.         from collections import defaultdict
    
13.         g = defaultdict(set)
    
14.         
    
15.         # DFS遍历建图
    
16.         def dfs(root):
    
17.             # print("...")
    
18.             if root != None and root.left == None and root.right == None:
    
19.                 # print("是叶子结点...")
    
20.                 isLeaf[root.val] = True
    
21.             if root.left:
    
22.                 g[root.val].add(root.left.val)
    
23.                 g[root.left.val].add(root.val)
    
24.                 dfs(root.left)
    
25.             if root.right:
    
26.                 g[root.val].add(root.right.val)
    
27.                 g[root.right.val].add(root.val)
    
28.                 dfs(root.right)
    
29.         # 执行建图过程
    
30.         dfs(root)
    
31.         
    
32.         # BFS查找距离目标值结点最近的叶子结点
    
33.         visited = { k }
    
34.         que = [k] # 模拟队列
    
35.         while len(que) != 0:
    
36.             top = que.pop()
    
37.             if isLeaf[top]:
    
38.                 return top
    
39.             for val in g[top]:
    
40.                 if val not in visited:
    
41.                     if isLeaf[val]:
    
42.                         return val      
    
43.                     que.insert(0, val)
    
44.                     visited.add(val)
    
45.         return -1

复制代码

码字不易，贫农求一波米~~~【加米不消耗自己的米，嘻嘻😜】

第一题有点不太明白，新加入的一行是如何与之前的几行匹配的呢？

补充内容 (2019-12-5 08:56):
搜了一下第一题网上的解答，常数固定空间的暴力解答应该是最优的，题主的dp做法没有太理解

第二题 可以优化到n log(n)
算法：
建立从左到右 和从右到左的 prefix sum array, two pointer 从数组最左和最右 左边sum大最右指针左移， 反之同理.找到左右sum相同的点, 此时左指针i 右指针j 在区间[i,j] 的prefixsum arary 上二分 找值 sum[0,i-1] , 注意每个prefixsum 要减去sum[0,i-1].


补充内容 (2019-12-2 16:54):
二分 虚拟点
dp 从后向前推

想不出来 暴力
第二题 可以优化到n log(n)
算法：
建立从左到右 和从右到左的 prefix sum array, two pointer 从数组最左和最右 左边sum大最右指针左移， 反之同理.找到左右sum相同的点, 此时左指针i 右指针j 在区间[i+1,j-1]的prefixsum arary 上二分 找值 sum[0,i-1] , 注意每个prefixsum 要减去sum[0,i-1].

点赞 希望地里可以有更多这样的原创内容。。

话说这真是fb高频么。。fb高频前50我都刷了呀怎么一点印象没有。。。

小六毛 发表于 2019-12-1 23:46
点赞 希望地里可以有更多这样的原创内容。。

话说这真是fb高频么。。fb高频前50我都刷了呀怎么一点印象没 ...

可能统计规则不同吧。。。

地里欢迎原创内容！当然也包括算法题目讨论！

本文被选为全站置顶文章之一。
作者获得100大米奖励。谢谢你的分享。

望地里可以有更多这样的原创内容
我自己也想po几个，正在打磨中

感谢楼主分享原创内容
正在刷也没看过这题

小六毛 发表于 2019-12-1 23:46
点赞 希望地里可以有更多这样的原创内容。。

话说这真是fb高频么。。fb高频前50我都刷了呀怎么一点印象没 ...

第一题不太会是高频吧，因为是dp解