logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
Win10只能共享内置硬盘，不能共享USB的外置硬盘 (转载)
avatar
Win10只能共享内置硬盘，不能共享USB的外置硬盘 (转载)# PDA - 掌中宝
e*3
1 楼
给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
比如:
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
x*k
2 楼
avatar
g*9
3 楼
【 以下文字转载自 Hardware 讨论区 】
发信人: gam1069 (gam1069), 信区: Hardware
标 题: Win10只能共享内置硬盘，不能共享USB的外置硬盘
发信站: BBS 未名空间站 (Mon Dec 24 14:01:01 2018, 美东)
因为更换成Bell的宽带，换了Modem,内网IP地址都变了。海美迪的播放器就找不到PC的
共享硬盘。重新设置但是只能找到电脑内置的硬盘共享。如果是USB的外置硬盘，即使
设置了一样的共享，播放器还是找不到。
我已经打开了SMB1.0,允许了非安全的连接，种种尝试都试了还是不行。求助！
avatar
a*5
4 楼
从给定的点开始DFS（或者BFS，时间复杂度一样）找这个联通区域的所有点。每次找的
时候如果这个点的坐标超出了当前已经找到的坐标范围就更新。最后得道的坐标范围就
是结果。
WORST CASE编历矩阵里的所有点。M*N。

【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
c*g
5 楼
小清新av

【在 x***k 的大作中提到】

avatar
g*9
6 楼
经过尝试，我自己解决了这个问题。以前都是共享整个驱动器给电视盒子播放电影，
Win10取消了默认的Everyone用户访问驱动器root的权限。需要手动添加。
avatar
l*u
7 楼
从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。

【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
h*u
8 楼
啊哦
avatar
h*e
9 楼
这个方法不对。
要求是最小矩形，应该可以是斜着的矩形吧。
如下图：
010
101
010
最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2

【在 l*********u 的大作中提到】
: 从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。
avatar
a*l
10 楼
质量堪忧。
avatar
a*m
11 楼
不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
只是有优化可以做。

【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
b*r
12 楼
丑还是丑
avatar
l*u
13 楼
good point
斜着的矩形,只能45度吧。转XY轴45度，再来4次。

【在 h*****e 的大作中提到】
: 这个方法不对。
: 要求是最小矩形，应该可以是斜着的矩形吧。
: 如下图：
: 010
: 101
: 010
: 最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
: 而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2
avatar
e*3
14 楼

面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.

【在 a********m 的大作中提到】
: 不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
: 只是有优化可以做。
avatar
b*e
15 楼
Google问这题。有人贴过O(n*log(n))的方法：
只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。

【在 e********3 的大作中提到】
:
: 面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.
avatar
e*3
16 楼

我一开始也是想2分，但是后面发现不大对。比如：
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 0 1 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 0
假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
那边分？

【在 b***e 的大作中提到】
: Google问这题。有人贴过O(n*log(n))的方法：
: 只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
: 全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。
avatar
b*e
17 楼
Here's what I suggest you do:
Read my post, carefully, character by character, and apply the algorithm as
described to you example. Hopefully you'll see how it works.

【在 e********3 的大作中提到】
:
: 我一开始也是想2分，但是后面发现不大对。比如：
: 0 0 0 0 0 0 0 0
: 0 1 1 1 1 1 1 0
: 0 1 0 1 0 1 0 0
: 0 0 0 1 1 0 0 0
: 0 0 1 1 0 0 0 0
: 假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
: 那边分？
avatar
a*m
18 楼
看不懂。
咱来个简单case帮助理解。
100000*100000的图，只有最后一行的最后一个点是黑的，其他都是白。你说说怎么二
分吧。

as

【在 b***e 的大作中提到】
: Here's what I suggest you do:
: Read my post, carefully, character by character, and apply the algorithm as
: described to you example. Hopefully you'll see how it works.
avatar
e*3
19 楼
给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
比如:
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
a*5
20 楼
从给定的点开始DFS（或者BFS，时间复杂度一样）找这个联通区域的所有点。每次找的
时候如果这个点的坐标超出了当前已经找到的坐标范围就更新。最后得道的坐标范围就
是结果。
WORST CASE编历矩阵里的所有点。M*N。

【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
l*u
21 楼
从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。

【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
h*e
22 楼
这个方法不对。
要求是最小矩形，应该可以是斜着的矩形吧。
如下图：
010
101
010
最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2

【在 l*********u 的大作中提到】
: 从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。
avatar
a*m
23 楼
不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
只是有优化可以做。

【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
l*u
24 楼
good point
斜着的矩形,只能45度吧。转XY轴45度，再来4次。

【在 h*****e 的大作中提到】
: 这个方法不对。
: 要求是最小矩形，应该可以是斜着的矩形吧。
: 如下图：
: 010
: 101
: 010
: 最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
: 而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2
avatar
e*3
25 楼

面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.

【在 a********m 的大作中提到】
: 不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
: 只是有优化可以做。
avatar
b*e
26 楼
Google问这题。有人贴过O(n*log(n))的方法：
只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。

【在 e********3 的大作中提到】
:
: 面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.
avatar
e*3
27 楼

我一开始也是想2分，但是后面发现不大对。比如：
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 0 1 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 0
假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
那边分？

【在 b***e 的大作中提到】
: Google问这题。有人贴过O(n*log(n))的方法：
: 只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
: 全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。
avatar
b*e
28 楼
Here's what I suggest you do:
Read my post, carefully, character by character, and apply the algorithm as
described to you example. Hopefully you'll see how it works.

【在 e********3 的大作中提到】
:
: 我一开始也是想2分，但是后面发现不大对。比如：
: 0 0 0 0 0 0 0 0
: 0 1 1 1 1 1 1 0
: 0 1 0 1 0 1 0 0
: 0 0 0 1 1 0 0 0
: 0 0 1 1 0 0 0 0
: 假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
: 那边分？
avatar
a*m
29 楼
看不懂。
咱来个简单case帮助理解。
100000*100000的图，只有最后一行的最后一个点是黑的，其他都是白。你说说怎么二
分吧。

as

【在 b***e 的大作中提到】
: Here's what I suggest you do:
: Read my post, carefully, character by character, and apply the algorithm as
: described to you example. Hopefully you'll see how it works.
avatar
b*r
30 楼
大牛的意思是这样的：（以向上找为例）
因为给定的点是1，所以从任何2分的地方向该给定点靠近（如果该行没1）或者远离（
如果该行有1）。因为所有的1是连通的，所以，如果有的新发现的1点比该给定点更靠
近边界，那么，某个2分的线必然会碰到在某一行的1点。
用这点我们可以保证一定发现最高的1点。

【在 a********m 的大作中提到】
: 看不懂。
: 咱来个简单case帮助理解。
: 100000*100000的图，只有最后一行的最后一个点是黑的，其他都是白。你说说怎么二
: 分吧。
:
: as
avatar
l*8
31 楼
这个好像leetcode上有的吧。记得好像只要recursive在周围四个点只要有1就转进过去
就行了，有几个1就转几次，然后找四面的极值。记得把当前点mark成0或者2（如果你
过后要恢复的话），或者你拿个set记下来visit过的1点，set会慢一点。

【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
avatar
w*1
32 楼
这题和那个题还不太一样，不用翻转邻居什么的
不过核心思想都是BFS/DFS，这题更直接一点

【在 l******8 的大作中提到】
: 这个好像leetcode上有的吧。记得好像只要recursive在周围四个点只要有1就转进过去
: 就行了，有几个1就转几次，然后找四面的极值。记得把当前点mark成0或者2（如果你
: 过后要恢复的话），或者你拿个set记下来visit过的1点，set会慢一点。
相关阅读
N4 not charged国内电信的Note II 机器带到美国能上Verizon吗？HTC butterflyGS3 $499算不算deal?尼玛，据说我共把skype也禁了。求助！android有时候屏幕突然滑动不了了，要按一下返回或者homeoutlook高手进来看看Nexus 10 怎么到处都缺货收到walmart的gift card了android怎么样才能后台听youtube，前台跑其他app？Samsung Galaxy Tab 2 可以UPDATE了kindle fire如何接到电视看？包子求win7请问目前最可靠的黑市场是那个？检测不出来?安猪里的qq不能传视频文件？！什么是root今天H2O见鬼了 一直给我发送通知 扣款0.00Google要玩我天朝玩剩下的了？N4要upgrade去Jelly Bean4.2.1吗？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。