|
|
p*u
发帖数: 136 | 3 不知道有没有理解错意思，感觉这题目没啥意思。
1，如果是有向图，而且没有重复边
2，如果一定存在这样的节点
直接找到adj matrix的边数为0的节点就是结果了
因为节点有n-1个入度，所以其他所有节点都有边 |
|
l*********e
发帖数: 28 | 4 1. 是有向图。不知道什么叫重复边，但是可能和同时存在。
2. 不知道这样的节点是否存在。 |
|
f*******w
发帖数: 1243 | 5 树就是图的一种啊，为什么不能BFS, DFS
你说说一个树和一个有向图在表现形式上有什么区别？
BFS就是level order
DFS的话可以是inorder, preorder, postorder |
|
g*********e
发帖数: 14401 | 6
毫不扯淡。
比如你有个有向图，图里每个node都可以是一个小图，你要给这个大图做优化，递归最
好写。
还是这个图，求它的topo order算dependency，就得dfs。
电路里面做静态时序分析，那都是dp。
用位来存储一些数据结构，或者做查找表，节约空间。更抠的还有把flag存到指针低位
的 |
|
d********i
发帖数: 582 | 7 请问下题如何用有向图来实现？谢谢。
题目：
printing a tree structure with giving collection of pairs of
child> relation. Need to first find the root, and validate wether the given
relations is a valid tree, and then printing.
问题一： 如何判断有valid tree
问题二： 如果print?
例:
给一个set，里面是一堆pair，每个pair里是两个string，一个first，一个second。
如果这堆pair能够构成一个树状结构，按照一定的格式打印这棵树
first-second关系类似paretnt-child关系
eg
set: (a, b) (b, c) (a, d) (d, e) (d, f) (d, g)
树状结构是root = a, root.left = b, root.right = d blah blah
打印结果：[space] 就是一个空格. 1point... 阅读全帖 |
|
h*******e
发帖数: 1377 | 8 俄确实，无向图那么做可以达到O（n^2)， 至于有向图， 似乎在第三层二分加速后复
杂度是O(n^2 logn) |
|
s********k
发帖数: 2352 | 9 设计有向图application. 用户可以创建 线，长方形，圆形，文本。。。 manipulate
them independently - move them, re-size them, etc.
How would you model the representation of the document in an object oriented
language?
classes?
methods?
这个会用到什么设计模式吗？ |
|
r******t
发帖数: 250 | 10 你自己说的问题不准确还敢继续秀？你以为 topological order 是什么？
你知道那个词是哪里来的吗？以你的实力你会的那叫有向图的 topological sort 明白？ |
|
|
n****s
发帖数: 2 | 12 先按是否能装下做有向图， 然后拓扑排序。
然后建数组，第k个元素储存，前k个拓扑排序之后箱子的所有最优解，dp |
|
r****7
发帖数: 2282 | 13 首先这个结果不唯一，而且可能性很多，只能取一个
按位比较然后得到一个字符的有向图然后拓扑排序吧 |
|
M******9
发帖数: 10 | 14 上面部分没有具体说的题目真心不难，其实Leetcode上的题目真正理解了肯定没问题，
我列下类似方法的题目或者变形(绝大部分对应leetcode上的题目，有些是实际问题背
景，稍微转化下就是了):
One Edit Distance
Binary Search in Rotated Sorted Array
Sqrt, Power using binary search
Regular Expression Matching
LRU
Max number of Points on line
Combination Sum
Decode ways
K-th biggest/smallest number in unsorted stream/array
Log hit类题目
给定一个string，在字典中查找共同前缀最长的单词
判断树是否BST, 是否symmetric, root到最大值节点路径
判断图是否bipartite,判断有向图是否tree |
|
M******9
发帖数: 10 | 15 上面部分没有具体说的题目真心不难，其实Leetcode上的题目真正理解了肯定没问题，
我列下类似方法的题目或者变形(绝大部分对应leetcode上的题目，有些是实际问题背
景，稍微转化下就是了):
One Edit Distance
Binary Search in Rotated Sorted Array
Sqrt, Power using binary search
Regular Expression Matching
LRU
Max number of Points on line
Combination Sum
Decode ways
K-th biggest/smallest number in unsorted stream/array
Log hit类题目
给定一个string，在字典中查找共同前缀最长的单词
判断树是否BST, 是否symmetric, root到最大值节点路径
判断图是否bipartite,判断有向图是否tree |
|
|
r****7
发帖数: 2282 | 17 有向图，带环就invalid，不带环就valid |
|
r****7
发帖数: 2282 | 18 有向图，带环就invalid，不带环就valid |
|
b*********e
发帖数: 26 | 19 最后一题bfs从一个点开始把图里所有点都遍历一遍就好了吧？如果完全遍历就可以，
不能就不可以
如果是有向图的话就用topological sort之类的，应该也是可以在O（N）解决的。 |
|
|
b******i
发帖数: 914 | 21 看我给的原帖的link，这个没详细说，
我估计图也有可能是无向的，有向图还真不知道准确定义是什么 （入+出 == 1 ?） |
|
r****7
发帖数: 2282 | 22 2肯定是无向图吧，有向图的话degree 1就没法从一个到别的了
从一个terminator开始找到不同的terminators记下所有的路就可以了
tree
called
single
the |
|
f********a
发帖数: 165 | 23 说是一次party完以后，有的人负责酒水费用有的人负责汽油费用有的人负责。。这样
形成一个有向图的结构，A欠B多少钱，B欠C多少钱，C可能欠A、B分别多少钱，问怎么
reduce/combine到最后形成一些pairs，比如A欠B 20，C欠A20，reduce到最后只需要C
给B20块就行。这个pairs表达的transactions做到最小。
有人说用二分图最大权匹配，还是没有懂到怎么做。。。 |
|
i****7
发帖数: 26 | 24 电面1：
顺序统计树，找第K个节点。
电面2：
1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
2）Next permutation
3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
Onsite:
1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
（国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
2）一个有向图，找出互相指向的点对数，（e.g. A指向B，B指向A，算一对）
Follow up， 写一个类，这个图会变化（加点，删点，加边，删边），维护这样的
点对数。
Follow up， 扯了扯大数据时候怎么分配到各个计算机上。
3）论文演讲
4）家族树，每个点左右指针指向自己的父亲和母亲，每个点存对应二叉堆的索引。
A）给一个这种树，给每个点标出对应二叉堆的索引值。
B）任意给一个节点（不需要输入根节点），输出这个点所在的层数。... 阅读全帖 |
|
A*******e
发帖数: 2419 | 25 2）一个有向图，找出互相指向的点对数，（e.g. A指向B，B指向A，算一对）
Follow up， 写一个类，这个图会变化（加点，删点，加边，删边），维护这样的
点对数。
Follow up， 扯了扯大数据时候怎么分配到各个计算机上。
有向社交图，类似微博找互相关注。
每个节点维护一个关注对象，数组、链表、BST，或散列。
对节点A遍历对象，看对象节点是否指向自己。
加点时不会加边把？这样计数不变。
删点时先查有多少互相关注，减去。
加减边时看情况加减1或不变。
有向社交图分布存储问题。能想到的几点：
1. 互相关注的对象尽量放在一台机器上？互相关注会形成完全图，但完全图太大时还
是得分开。
2. 受关注多的名人分开放，或有镜像，免得一台宕机，多数用户受影响。
还有啥？ |
|
r*********r
发帖数: 53 | 26 判断图是否有环：
我觉得可以直接用dfs，每一步记录当前访问的node，如果当前访问的node之前被访问
过那么就是有环的。
如果图是有向图，我们还可以用topological sorting 来判断。 |
|
|
r*********r
发帖数: 53 | 28 空间是省不了的吧……
如果是有向图，那么可以用topological sorting, 时间复杂度会低一些，大概是O(V+E
). 但是空间还是省不了。
呢？ |
|
m*********t
发帖数: 527 | 29 这东西就是个有向图，而且已经把所有的 edge 给你了。把图建好，然后不管是 DFS 还
是 BFS 都能找到起点到终点的路径（前提是存在） |
|
h**p
发帖数: 211 | 30 上面有人说了，总结下2种方法（需要建立有向图）
#1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连 |
|
k******a
发帖数: 44 | 31 我觉得这个设计包含两个部分，
1. Object Meta data的storage
2. Friend relationship的管理.
对于1，可以用distributed hash map + memcached解决
对于2，可以参考facebook的TAO设计。就是说维护A-FRIEND-B的GRAPH。对于两个朋友
，使用两个有向边维护。为什么用graph，而不是一般的map设计（比如，A的朋友表示
为A->[B, C, D, ....]）？我觉得主要是scale问题。对于facebook这样这么大的用户
量，用户之间联系这么复杂的，使用map引起的写操作和写锁会非常难处理。对于这个
friend的有向图，主要是处理A-FRIEND-B这样的三元组的读写。那么可以使用
distributed hash map+index。并且用cache加速读操作。可以通过直接写cache，
batch写disk得方法解决写速度问题。
剩下的问题就是函数本身。先取Object,看property,如果是friends，查看owner的朋友
是否包含viewer，然后true/false。
为... 阅读全帖 |
|
l******s
发帖数: 3045 | 32 第一题是有向图+hashmap
第二题，如果题意理解正确为写函数int possbileAmount(int n) n is the length，
可以DFS或BFS，数学方法肯定可以推导，但恐怕半个小时之内推不出来。 |
|
|
r****7
发帖数: 2282 | 34 借个不就是有向图的dfs嘛
把递归的结果存起来如果递归遇到了指定的index就是要被删的节点。 |
|
c*******t
发帖数: 123 | 35 太棒了！
我相信你是对的。
我思路和你类似，隐约觉得应该把第二个条件按起点和终点分开，做成有向图。
但思路没有继续下去，没想到第二个条件可以拆开成两个子条件。
太感谢了！
A0- |
|
l*3
发帖数: 2279 | 36 此题可以不用哈密顿回路做。考虑欧拉回路即可。
首先说明一下，这个string的长度就是10003，也就是说每连续4个都是互不相同的4位
数，不会有浪费
构建方法就是：
考虑一个有向图，每个node是一个三位数，edge是四位数，node和node的连接关系是这
样的，我举个例子：
node v = (a, b, c)
其中 0 \le a, b, c \le 9
从这个node出发的edge有:
(a, b, c, 0), 连到 (b, c, 0)
(a, b, c, 1), 连到 (b, c, 1)
....
(a, b, c, 9), 连到 (b, c, 9)
这样每个node都有10个edge-in 10个 edge-out，全图是可以欧拉回路遍历的，遍历走
过的所有边就是你要的sequence |
|
|
r****l
发帖数: 741 | 38 看这些例子O（N）可解
俩字典，test1:([test1,test2])
Test2:([test1,test2]),value是同一个list/linkedlist
每加一个Link,看能不能和原来的连起来。其实就是
没法连，连一个，连两个三种情况
while loop就好。连起来的话两个字典要同步更新
每一步还要更新最长List
如果同一个Node可能指向不同的node,就麻烦得多
遍历有向图？ |
|
发帖数: 1 | 39 准备一个一维数组存每个点的parent，另外一个一维数组记录是否访问过。
先找in-degree = 0的点，然后dfs，遍历时候记录每个点的parents，记录访问情况
如果是环，任意取一点dfs，同样记录每个点的parents，记录访问情况
最后用union find 找到最终root，然后数不同root的个数。
这样方法是否可行，看到有人说必须用strong-connect component，不知为何，还望举
例说明 |
|
r*****s
发帖数: 1815 | 40 没有特别看清楚lz对于环指向环的情况是怎么处理的
感觉这样做下去最终就收敛回强连通了。。 |
|
|
|
发帖数: 1 | 43 等等，难道这个算出的不是SCC？
1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root |
|
z*********n
发帖数: 1451 | 44
不是。。。SCC得做transpose graph。。还是叫补图，还是叫反图那个 |
|
r*****s
发帖数: 1815 | 45 对啊，这算法不就是SCC吗。。。。
: 等等，难道这个算出的不是SCC？
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root
|
|
r*****s
发帖数: 1815 | 46 啊 翻算法导论去了。。。
: 不是。。。SCC得做reverse graph。。还是叫补图，还是叫反图那个
|
|
|
发帖数: 1 | 48 例子：edges:a->b, b->c, b->d。 a的indegree=0，是dfs的起点
按完成顺序是[c,d,b,a]或者[d,c,b,a]
在按照记录顺序的逆序走一遍，不是还是原来的dfs么？
而且这个方法很像强连通，除了你没有翻转edge的方向。 |
|
发帖数: 1 | 49 大概懂你意思了，第一遍dfs遍历，类似于做了个toposort，因为第一遍时候你无法确
定没有visited的点是一个新的起点还是一个在path上的点
第二遍遍历的时候因为已经toposort过了。没有visited的点肯定是一个新的起点。
这个好厉害。。。 |
|
z*********n
发帖数: 1451 | 50
是“原来”的DFS，你所谓的“原来”是你根据indegree人脑找出了一个最合理的起
点，其实就是问题的最终解了，这个算法能做出来这个解，不正好说明它是对的么？
但你注意，我这算法里没有算indegree这步，可能我“原来”的dfs起点是c啊，或者是
b啊，你看看结果是不是也是你那个“原来”的dfs |
|
