一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
把贵司信息放这里
查看: 4321|回复: 13
收起左侧

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

  [复制链接] |试试Instant~ |刷题, leetcode
我的人缘0

分享帖子到朋友圈
本楼: 👍   100% (5)
 
 
0% (0)   👎
全局: 👍   100% (133)
 
 
0% (0)    👎
本帖最后由 SimonXDong 于 2019-12-1 23:03 编辑

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

[Python] 纯文本查看 复制代码
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




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

最后贴一下解法:

[Python] 纯文本查看 复制代码
# 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

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



本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x

评分

参与人数 35大米 +202 收起 理由
ZoeY.Zou + 1 很有用的信息!
quxiaotian + 1 给你点个赞!
MickeyXie + 1 给你点个赞!
余宇Sabrina + 1 欢迎分享你知道的情况,会给更多积分奖励!
fbl1999 + 1 给你点个赞!
shawhull + 1 赞一个
JeanWu + 15
carrieliu + 1 厉害
14417335 + 16
Jinelle.H + 1 赞一个

查看全部评分


上一篇:有没有同学刷题刷太猛导致头疼
下一篇:FaceBook 最新高频题目统计 [12.01 感恩节更新]
我的人缘0
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   96% (28)
 
 
3% (1)    👎
第一题有点不太明白,新加入的一行是如何与之前的几行匹配的呢?

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

使用道具 举报

我的人缘0
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   94% (1683)
 
 
5% (101)    👎
点赞 希望地里可以有更多这样的原创内容。。

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

使用道具 举报

我的人缘0
 楼主| SimonXDong 2019-12-2 01:58:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (133)
 
 
0% (0)    👎
小六毛 发表于 2019-12-1 23:46
点赞 希望地里可以有更多这样的原创内容。。

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

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

使用道具 举报

我的人缘0
admin 2019-12-3 07:16:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (2048)
 
 
5% (130)    👎
地里欢迎原创内容!当然也包括算法题目讨论!

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

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (5)
 
 
0% (0)    👎
第二题 可以优化到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].
回复

使用道具 举报

我的人缘0
akdhfikbk 2019-12-4 07:04:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (162)
 
 
1% (3)    👎
望地里可以有更多这样的原创内容
我自己也想po几个,正在打磨中
回复

使用道具 举报

我的人缘0
liudingusa 2019-12-4 10:52:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
感谢楼主分享原创内容
正在刷也没看过这题
回复

使用道具 举报

我的人缘0
groundzyy1 2019-12-4 15:33:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (879)
 
 
3% (34)    👎
小六毛 发表于 2019-12-1 23:46
点赞 希望地里可以有更多这样的原创内容。。

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

第一题不太会是高频吧,因为是dp解
回复

使用道具 举报

我的人缘0
ChrisZcmu 2019-12-5 11:13:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (31)
 
 
0% (0)    👎
感谢楼主分享,正在刷题好像也没印象

评分

参与人数 1大米 +1 收起 理由
MickeyXie + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-1-25 06:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表