这是一个消费税:
在某些图形问题中,顶点可以具有权重,而不是边缘权重或者与边缘权重相加.设Cv为顶点v的代价,C(x,y)为边的代价(x,y).该问题涉及在图G中找到顶点a和b之间的最便宜的路径.路径的成本是路径上遇到的边和顶点的成本之和.
(a)假设图中的每条边的权重为零(非边的成本为∞).对于所有顶点1≤v≤n,假设Cv = 1(即所有顶点具有相同的成本) .提供一种有效的算法来找到从a到b的最便宜路径及其时间复杂度.
(b)现在假设顶点成本不是恒定的(但都是正数),边缘成本保持如上.提供一种有效的算法来找到从a到b的最便宜路径及其时间复杂度.
(c)现在假设边缘和顶点成本都不是恒定的(但都是正数).提供一种有效的算法来找到从a到b的最便宜路径及其时间复杂度.
这是我的答案:
(a)使用正常的BFS;
(b)使用dijkstra算法,但用顶点权重代替权重;
(C)
也使用dijkstra的算法
如果只考虑边缘权重,那么对于dijkstra算法的关键部分,我们有:
if (distance[y] > distance[v]+weight) {
distance[y] = distance[v]+weight; // weight is between v and y
}
现在,通过考虑顶点权重,我们有:
if (distance[y] > distance[v] + weight + vertexWeight[y]) {
distance[y] = distance[v] + weight + vertexWeight[y]; // weight is between v and y
}
我对吗？
我猜我对(c)的回答太简单了,是吗？
我希望使用OCaml访问Yahoo Finance API.从本质上讲,它只是一堆HTTP请求来获取雅虎财经的报价.
我应该使用哪个模块？
我希望有异步HTTP请求.
在算法设计手册中,有这样的消费税
4-26考虑使用比较对n 0和1的序列进行排序的问题.对于两个值x和y的每次比较,算法学习x <y,x = y或x> y中的哪一个.
(a)给出一个算法,在最坏的情况下进行n-1次比较.表明您的算法是最佳的.
(b)给出一种算法,在平均情况下对2n/3次比较进行排序(假设n个输入中的每一个都是0或1,概率相等).表明您的算法是最佳的.
对于(a),我认为这很容易.我可以选择[n-1]作为枢轴,然后执行类似于快速分区的操作,扫描0到n - 2,找到左侧全部为0且右侧全部为1的中间点,这需要进行n - 1次比较.
但对于(b),我无法得到线索.它说"n个输入中的每一个都是0或1,概率相等",所以我想我可以假设0和1的数字相等？但是我怎样才能得到与1/3相关的结果？将整个阵列分成3组？
谢谢
在CLRS消费税22.1-8(我自学,不在任何大学)
假设每个数组条目Adj [u]不是链表,而是包含顶点v的哈希表,其中(u,v)∈E.如果所有边缘查找都具有相同的可能性,那么确定是否是边缘在图中？这个方案有什么缺点？为每个边缘列表建议一个替代数据结构来解决这些问题.与哈希表相比,您的替代方案是否有缺点？
因此,如果我用哈希表替换每个链表,则存在以下问题:
我有以下部分答案:
对于其他两个问题,我无法得到线索.
任何人都可以给我一个线索？
这是一个消费税:
要么证明以下内容,要么给出一个反例:
(a)无向图的最小生成树中的一对顶点之间的路径是否必须是最短(最小权重)路径？
(b)假设图的最小生成树是唯一的.在无向图的最小生成树中,一对顶点之间的路径是否必须是最短(最小权重)路径？
我的回答是
(一个)
不,例如,对于图0,1,2,0-1是4,2-2是2,2-0是5,那么0-2的真正最短路径是5,但是mst是0-1-2 ,在mst,0-2是6
(b)中
我的问题进入了这个(b).
我不明白怎么whether the MST is unique会影响最短的路径.
首先,我的理解是,当边的权重不明显时,可能同时存在多个MST,对吧？
其次,即使MST是唯一的,上述(a)的答案仍然适用于(b),对吧？
algorithm graph shortest-path minimum-spanning-tree data-structures
给定nxm的矩阵填充0和1
例如:
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
如果矩阵在(i,j)处有1,则用1填充列j和行i
即,我们得到:
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
所需复杂度:O(n*m)时间和O(1)空间
注意:您不能在矩阵条目中存储除"0"或"1"之外的任何内容
以上是Microsoft面试问题.
我想了两个小时了.我有一些线索,但不能再继续了.
好.这个问题的第一个重要部分是Even using a straight forward brute-force way,它不容易解决.
如果我只使用两个循环迭代矩阵中的每个单元格,并更改相应的行和列,则无法完成,因为生成的矩阵应基于原点矩阵.
例如,如果我看到a[0][0] == 1,我无法改变row 0和column 0所有1,因为这将影响row 1因为row 1原来没有0.
我注意到的第二件事是,如果一行r只包含 …
我有一个UILabel与CALayer阴影on.And我只是将它周围通过UIView动画.
性能很差,我可以看到动画根本不流畅.
我认为这是UILabel导致动画问题的阴影,因为如果我关闭阴影,动画会变得像平常一样平滑.
我试过用 view.layer.shouldRasterize = YES;
但动画表现仍然存在.
谁能给我一些提示？
谢谢
这是"算法设计手册"一书中的练习(3-15).
设计一种数据结构,允许用户在O(1)时间内搜索,插入和删除整数X(即,恒定时间,与存储的整数总数无关).假设1≤X≤n并且有m + n个可用空间单位,其中m是任何时候表中可以包含的最大整数数.(提示:使用两个数组A [1..n]和B [1..m].)不允许初始化A或B,因为这将执行O(m)或O(n)操作.这意味着阵列中充满了随机垃圾,所以你必须非常小心.
我并不是真的想要答案,因为我甚至不明白这个练习是什么问题.
从第一句话开始:
设计一种数据结构,允许用户在O(1)时间内搜索,插入和删除整数X.
我可以轻松地设计这样的数据结构.例如:
因为1 <= X <= n,所以我只有n个槽的位向量,并且让X为数组的索引,当插入时,例如5,则a [5] = 1; 当删除时,例如5,则a [5] = 0; 当搜索,例如5,那么我可以简单地返回[5],对吗？
我知道这个练习比我想象的要难,但这个问题的关键点是什么？
我学习Left-Lean-Red-Black tree,从Prof.Robert Sedgewick
http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
虽然我已经理解了insert这个2-3 tree和那个LLRB,但是我花了大约40个小时现在已经有2个星期了,我仍然无法删除LLRB.
谁能真正解释deletion的LLRB给我吗？
stringOCaml中的类型是否支持utf8？
或者我应该为utf8字符串使用什么库？