- 已关闭。**此问题为not reproducible or was caused by typos。当前不接受答案。
这个问题是由打字错误或无法再重现的问题引起的。虽然类似的问题在这里可能是on-topic,但这个问题的解决方式不太可能帮助未来的读者。
6小时前关门了。
Improve this question
我正在尝试解决这个leetcode744
我已经找到了这个解决方案,但无法确定while循环在哪一点退出?
'
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int start = 0, end = letters.length-1;
while(start<=end){
int mid = start + (end - start)/2;
if(letters[mid]>target){
end = mid - 1;
}
else{
start = mid + 1;
}
}
return letters[start % letters.length];
}
}
'
当我试着试运行时,我总是不停地将start、end和mid值设置为相同的值。使用IDE进行调试时显示,while循环在重复设置mid、start/end值一次后退出。
1条答案
按热度按时间o2g1uqev1#
这是一个典型的二进制搜索问题。
在LC 744的情况下,问题是在由排序字母组成的数组中找到特定字母(a在d之前,i在z之前等)
二进制搜索算法背后的思想是在每次迭代时将搜索区域减半,通过查看位置(开始+结束)/2处的字符,如果它比目标大,则我们知道我们应该只查看数组的左边部分,否则查看数组的右边部分。
在某个点,我们要么匹配目标,但在您的示例中,它将继续,只是增加/减少start/end的值,这导致在某个点,当start〉end时,while循环停止。
不确定我在这里给出了最好的解释,我建议你看看关于Leetcode的讨论,以及下面的资源;