j**l
发帖数: 2911 | 1 这里总结一下，对很多基本二分查找的变体题目，比如找rotated的有序数组的reset
point (pivot)，比如返回相同元素的连续段的第一个或者最后一个，我们可以考虑如
下思路。
如果我们让while处理三个元素(含)以上的情形，边界情况的困难往往就被消除了
然后while外头处理两个元素或一个元素的情形是很容易的
while (high - low > 1)
{
// 处理至少三个元素，无需边界处理
}
// 处理至多两个元素
当然，我发过相关的帖子，如果你遇到固执的面试官，不理解你为何那样处理，非要
很隐晦地暗示你必须采用如下的传统处理(最适用基本二分查找，因为几乎没有边界处
理)
while (low <= high)
{
// 一堆容易出错的边界处理
}
那也只能顺其所好，考虑周全，好好把while里头各种边界情况写好吧。否则面完后被
拒不说，还被背地里扣上不能很好follow面试官的suggestion的帽子。 |
h**6
发帖数: 4160 | 2 有的时候，需要求最大满足条件 A 的数，或者最小满足不条件 A 的数。
首先，设定初始值，使得 low 一定满足条件 A ，high 一定满足不条件 A。
然后，根据 mid 是否满足条件 A ，调整 low 或者 high。
调整过程中，应始终保持 low 满足条件 A ，high 满足不条件 A。
当 high=low+1 时循环结束，根据题目要求返回 low 或者 high。 |
h**6
发帖数: 4160 | 3 题目举例：
把一个正整数数组，分成连续的 k 段，求每一段的和的最大值的最小值。 |
s*********t
发帖数: 1663 | 4 我记得好像有个题是让数组分K段，求最大值与最小值的差，使其最小
完全没思路
【在 h**6 的大作中提到】
: 题目举例：
: 把一个正整数数组，分成连续的 k 段，求每一段的和的最大值的最小值。
|
h**6
发帖数: 4160 | 5
这题有两种解法，可以使用 DP 法，也可以使用二分法。
DP 法：
设 dp[m][x] 表示把数组的前 m 项分成 x 段时，每段和的最大值的最小值。
时间复杂度为 O(n^2*k)
二分法：
设每一段和都不超过 s，求原数组是否能分成不超过 k 段。
时间复杂度为 O(32n)，其中32是 int 位数，也是二分法最多需要进行的次数。
【在 h**6 的大作中提到】
: 题目举例：
: 把一个正整数数组，分成连续的 k 段，求每一段的和的最大值的最小值。
|
I**A
发帖数: 2345 | 6 啊，我题目都没看懂
【在 s*********t 的大作中提到】
: 我记得好像有个题是让数组分K段，求最大值与最小值的差，使其最小
: 完全没思路
|
I**A
发帖数: 2345 | 7 忘了赞一个。。
【在 j**l 的大作中提到】
: 这里总结一下，对很多基本二分查找的变体题目，比如找rotated的有序数组的reset
: point (pivot)，比如返回相同元素的连续段的第一个或者最后一个，我们可以考虑如
: 下思路。
: 如果我们让while处理三个元素(含)以上的情形，边界情况的困难往往就被消除了
: 然后while外头处理两个元素或一个元素的情形是很容易的
: while (high - low > 1)
: {
: // 处理至少三个元素，无需边界处理
: }
: // 处理至多两个元素
|
K******g
发帖数: 1870 | 8 请问能把题目说清楚一下吗？“分成连续的k段”有很多种分法，然后要求的是不同分
法中每段的和的最大值的最小吗？
【在 h**6 的大作中提到】
: 题目举例：
: 把一个正整数数组，分成连续的 k 段，求每一段的和的最大值的最小值。
|
