小编Sex*_*ast的帖子
找到数组中两个数字之间的最小绝对差值的最佳算法
有一个数组,可以包含,例如,最多1000元素.它可以产生的数字范围1 to 10^10.现在我必须minimal absolute difference在数组中找到两个数字之间的数字.我想到了两种算法:
对于第一个,我已经定义了一个binarysearch函数,该函数在排序的数组中找到要插入的数字的位置.现在,我只使用给定数组的第一个数字启动排序数组,然后从第二个元素开始迭代给定数组.对于每个数字,我在排序数组中找到它的位置.如果该位置的数字是这个数字,那么差值为0,它是最低的数字,所以我退出循环.否则,我在该点插入已排序数组中的数字,然后检查该数字与该数组中前一个和下一个数字之间的差异.然后我存储此结果的最小值和先前的结果,并以这种方式继续.
第二:我使用quicksort对数组进行排序.(范围太大,所以我认为基数排序不会那么高效).然后我迭代它,如果两个连续的数字相等则以0的答案断开,否则存储该数字与前一个数字和前一个结果之间的差值的最小值.
哪一个会更有效率？
还有更好的算法吗？
Stackoverflow在这方面有很多帖子,但它们没有多大帮助.这是我在Perl中的代码:
sub position {
my @list = @{$_[0]};
my $target = $_[1];
my ($low,$high) = (0, (scalar @list)-1);
while ($low <= $high) {
$mid = int(($high + $low)/2);
if ( $list[$mid] == $target ) {
return $mid;
}
elsif ( $target < $list[$mid] ) {
$high = $mid - 1;
}
else {
$low = $mid + 1;
}
}
$low; …推荐指数
解决办法
查看次数
在contenteditable div中的插入符号中以特殊字符开头
我有一个contenteditable div,我需要在当前的插入位置知道这个词.我试过这个解决方案,但问题是,它不能识别像@和的特殊字符~.因此,如果一个单词开始~,就像~fool,我正在得到fool,而我期待~fool.所以我尝试修改解决方案时考虑到如果在移回选择后,遇到的字符不是空格,我会继续向后移动直到遇到空格.这将成为选择的开始.同样地,我会继续前进,直到找到一个空格,这标志着选择的结束.然后选择会给我这个词.为了获得插入位置,我使用了这个解决方案.结合起来,我的代码现在看起来像这样:
function getCaretPosition(editableDiv) {
var caretPos = 0,
sel, range;
if (window.getSelection) {
sel = window.getSelection();
if (sel.rangeCount) {
range = sel.getRangeAt(0);
if (range.commonAncestorContainer.parentNode == editableDiv) {
caretPos = range.endOffset;
}
}
} else if (document.selection && document.selection.createRange) {
range = document.selection.createRange();
if (range.parentElement() == editableDiv) {
var tempEl = document.createElement("span");
editableDiv.insertBefore(tempEl, editableDiv.firstChild);
var tempRange = range.duplicate();
tempRange.moveToElementText(tempEl);
tempRange.setEndPoint("EndToEnd", range);
caretPos …推荐指数
解决办法
查看次数
构建BST需要知道多少次遍历
我对不同网站上的一些文章非常困惑,这些文章是关于构建Binary Search Tree任何一个遍历(pre,post或in-order),或者它们中任意两个的组合.例如,在这个页面上,它表示给定pre,post或level顺序遍历,以及in-order遍历,可以构造BST.但是在这里和那里,他们向我们展示了BST从pre-order单独构建一个.此外,他们在这里向我们展示了如何构建BST来自给定pre和post-order遍历.在其他一些网站中,我找到了一个BST仅从post-order遍历构建一个解决方案的解决方案.
现在我知道,给定inorder和pre-order遍历,可以独特地形成一个BST.至于我提供的第一个链接,虽然他们说我们不能构造BSTfrom pre-order和post-order,我不能只是对post-order数组进行排序以获得它的inorder遍历,然后使用它和pre-order数组来形成BST？这与第4个链接中的解决方案相同,还是不同？pre-order只有给出,我可以排序,以获得in-order,然后使用它和pre-order得到BST.同样,这是否必须与链接2和3的解决方案不同？
具体来说,什么足以独特地产生BST？如果不需要in-order唯一性,那么我可以简单地对其进行排序以获得遍历,并以BST递归方式从其中构建N个可能的中的一个.
推荐指数
解决办法
查看次数
即使值没有改变,jQuery UI滑块'change'事件也会触发
我试图在用户滑动滑块时触发事件,并在滑动停止时更改值.根据jQuery文档,该change事件对于这种情况是理想的.所以我试试这个:
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>jQuery UI Slider - Default functionality</title>
<link rel="stylesheet" href="http://code.jquery.com/ui/1.10.2/themes/smoothness/jquery-ui.css" />
<script src="http://code.jquery.com/jquery-1.9.1.js"></script>
<script src="http://code.jquery.com/ui/1.10.2/jquery-ui.js"></script>
<link rel="stylesheet" href="/resources/demos/style.css" />
<script>
$(function() {
$( "#slider" ).slider({
change:function() { alert("foo"); }
});
});
</script>
</head>
<body>
<div id="slider"></div>
</body>
</html>
但是,我观察到当我将滑块向右拖动并再次将其拖回到起点(页面加载时滑块的初始位置)时,警报仍然会触发.这是一个jQuery错误吗？如果不是,我该如何解决这个问题？
推荐指数
解决办法
查看次数
如何在后序遍历中构造BST
我知道有一些方法可以从预先遍序遍历(作为数组)构造树.考虑到有序和预订遍历,更常见的问题是构造它.在这种情况下,虽然顺序遍历是多余的,但它确实使事情变得更容易.任何人都可以告诉我如何进行后期遍历？迭代和递归解决方案都是必需的.
我尝试使用堆栈迭代地执行它,但根本无法正确地获得逻辑,因此得到了一个可怕的凌乱的树.同样去递归.
推荐指数
解决办法
查看次数
中位数中位数算法的解释
该Median of medians方法在quicksort类型分区算法中非常流行,以产生相当好的枢轴,从而统一分区数组.其逻辑在维基百科中给出:
所选择的枢轴小于和大于中位数列表中元素的一半,每半个元素大约为n/10个元素(1/2*(n/5)).这些元素中的每一个都是5的中值,使得它少于2个其他元素并且在块之外大于2个其他元素.因此,枢轴在块外部小于3(n/10)个元素,并且大于块外的另外3个(n/10)个元素.因此,所选择的中值将元素分成介于30%/ 70%和70%/ 30%之间的某个位置,这确保了算法的最坏情况线性行为.
有人可以为我清楚地解释一下.我发现很难理解逻辑.
推荐指数
解决办法
查看次数
如何为Prim的算法更新堆中的元素优先级？
我正在研究Prim的算法.代码中有一个部分,切割的下一个顶点将会到达属于该顶点的顶点集MST.在这样做的同时,我们还必须"更新另一组中与离开顶点相邻的所有顶点".这是来自的快照CLRS:
有趣的部分在于行号.11.但是由于我们在这里使用堆,我们只能访问最小元素right(heap[0])？那么我们如何从堆中搜索和更新顶点,即使它们不是最小的顶点,因此除了线性搜索之外我们知道它们在哪里？
algorithm heap minimum-spanning-tree prims-algorithm data-structures
推荐指数
解决办法
查看次数
什么是PHP中的realpath_cache？
任何人都可以告诉我realpath_cachePHP的确切含义是什么？在PHP手册中已经对它做了很多参考,但没有充分解释它.例如,文章中clearstatecache说该参数clear_realpath_cache表示是否清除实际路径缓存.这句话是什么意思？
推荐指数
解决办法
查看次数
如何交错或创建两个字符串的唯一排列(无递归)
问题是打印两个给定字符串的所有可能的交错.所以我用Python编写了一个工作代码,运行方式如下:
def inter(arr1,arr2,p1,p2,arr):
thisarr = copy(arr)
if p1 == len(arr1) and p2 == len(arr2):
printarr(thisarr)
elif p1 == len(arr1):
thisarr.extend(arr2[p2:])
printarr(thisarr)
elif p2 == len(arr2):
thisarr.extend(arr1[p1:])
printarr(thisarr)
else:
thisarr.append(arr1[p1])
inter(arr1,arr2,p1+1,p2,thisarr)
del thisarr[-1]
thisarr.append(arr2[p2])
inter(arr1,arr2,p1,p2+1,thisarr)
return
它出现在字符串中的每个点上,然后对于一个递归调用,它将当前元素视为属于第一个数组,并在下一个调用中将其视为属于另一个数组.因此,如果输入的字符串ab和cd,它打印出来abcd,acbd,cdab,cabd,等p1,并p2都指向数组(因为Python中的字符串是不可改变的,我使用数组!).任何人都可以告诉我,这段代码的复杂程度是什么,是否可以改进？我编写了一个类似的代码来打印k给定数组的所有长度组合:
def kcomb(arr,i,thisarr,k):
thisarr = copy(thisarr)
j,n = len(thisarr),len(arr)
if n-i<k-j or j >k:
return
if j==k:
printarr(thisarr)
return
if i == n:
return
thisarr.append(arr[i])
kcomb(arr,i+1,thisarr,k)
del …推荐指数
解决办法
查看次数
了解滚动散列如何与 Rabin Karp 算法中的模数一起使用
在通过除以素数将散列减少到模值后，我无法理解滚动散列算法的工作原理。
考虑数字中 5 位数字的序列123456。
第一个块是12345. 我存储值，在下一个窗口中，输入 6，输出 1。
所以新的哈希将是(12345-1*10^4)*10 + 6 = 23456. 这是相当直观的。
很明显，这些数字很大，所以我们需要一个模函数来保持它们很小。假设我101为此目的取质数。
所以12345会减少到23. 那么，如何从中得出下一个窗口的滚动哈希23456？
推荐指数
解决办法
查看次数