两个leetcode问题疑惑

1.http://www.lintcode.com/en/problem/search-for-a-range/

请问search for a range里面，找最后一个的index，为什么要按 if A[mid] > target:

                end = mid

else:

                start =  mid 这个顺序，反过来就不行呢？

2. http://www.lintcode.com/en/problem/find-peak-element/

为什么最后比较 if A[start] < A[end]:

            return end

        else:

            return start  

就能找出来尖峰了？

从lz给出的这些代码碎片推断，该作者的习惯是每次缩小范围时都设置
end= mid 和start=mid（九章算法就是这种风格）。这样的好处是代码看起来比较对称，但是不能保证一定能够收敛到范围内只有一个元素的情况。所以只能在范围内有两个元素时退出循环，再看一下这两个元素哪一个才是真正的解。第2题中，循环退出时start和end必定是相邻的，且之前的二分法保证尖峰必在这二者中（不在的话说明二分法根本就没写对），那么肯定定是其中的大者为峰。

顺带一提，我个人更偏好于search时使用非对称的范围缩减策略，如：
if (...) end = mid; else start = mid+1; 之类的
这样就不需要循环后再判断，但是需要确认的地方较多。比如退出条件是<还是<=，是用start=mid+1还是end=mid-1，这些要根据具体的题目来定。

第1题不是很确定你说的“反”是什么意思。

3.http://www.jiuzhang.com/solution ... tated-sorted-array/
为什么要num［mid］和num［end］比较，为什么不能和start比较

第一题里，这个else包含了A[mid]  = target 的情况，既然你是找后一个index，相等的情况下自然要去推start指针往右，而不能倒过来。

第二题不是很确定你说的源代码是什么。。我常用的解法是根据初始定义 A[0] < A[1] && A[A.length - 2] > A[A.length - 1].， 这样在 数组 0 到 A.length - 1 的位置一定存在peak; 每次找到mid的时候去比较 A[mid - 1] , A[mid] , A[mid + 1] , 如果这三个数是单调递增，那么说明mid右面一定有peak （和数组最初定义的原理一样），如果单调递减，那么左面一定有个peak，可以依据这个缩小搜索范围。

第三题也可以和start比较啊，A[mid] 和其中一端比较是为了帮你确定mid 到底是在rotated array的哪一部分上；你的A[mid] > A[end] 说明你的mid在左半部分上；同样道理如果你的 A[mid] < A[start] 也可以说明mid处在数组的右半部分上 （相对rotated pivot point而言）

mnmunknown 发表于 2015-9-17 11:17
第一题里，这个else包含了A[mid]  = target 的情况，既然你是找后一个index，相等的情况下自然要去推start ...

谢谢亲的回答， 我对于第三题还是有点疑问：
如果可以和start比的话，
if num[mid] < num[start]:
                start = mid  
else:
                end = mid
但是还是没发通过

chendanlan 发表于 2015-9-17 11:48
谢谢亲的回答， 我对于第三题还是有点疑问：
如果可以和start比的话，
if num[mid] < num[start]:

不好意思我以为你说的是search in rotated sorted array...

和start比较有一个问题。在start , end 为初始值的情况下，A[mid] < A[start] 可以很确定的告诉你mid在右边那段上，应该往mid左面找；然而A[mid] > A[start] 的情形下却是不确定的，其中一种可能是你的mid在一开始的左半边，这种情形下应该动start; 另一种可能性是你的mid已经在右半边然而start也在右半边，这时候再动start就会出错了。也就是说如果只是根据A[mid] 和 A[start] 决定动那个指针的话， 同样的判断逻辑无法一直保证正确的结果。

和start比较在search in rotated sorted array I & II 里就不会出现这个问题，因为除了找mid的位置之外，后面还有区间的单调性确定。

1. public class Solution {
   
2.     public boolean search(int[] A, int target) {
   
3.         if(A == null || A.length == 0) return false;
   
4.         
   
5.         int start = 0;
   
6.         int end = A.length - 1;
   
7.         
   
8.         while(start + 1 < end){
   
9.             int mid = start + (end - start) / 2;
   
10.             if(A[mid] == target) return true;
    
11.             if(A[mid] > A[start]){
    
12.                 if(A[start] <= target && target <= A[mid]){
    
13.                     end = mid;
    
14.                 } else {
    
15.                     start = mid;
    
16.                 }
    
17.             }
    
18.             else if(A[mid] < A[start]){
    
19.                 if(A[mid] <= target && target <= A[end]){
    
20.                     start = mid;
    
21.                 } else {
    
22.                     end = mid;
    
23.                 }
    
24.             } else {
    
25.                 start++;
    
26.             }
    
27.         }
    
28.         if(A[start] == target || A[end] == target) return true;
    
29.         
    
30.         return false;
    
31.     }
    
32. }

复制代码

mnmunknown 发表于 2015-9-18 08:56
不好意思我以为你说的是search in rotated sorted array...

和start比较有一个问题。在start , end 为 ...

谢谢谢谢谢谢！！！！

4.请问 这道题 http://www.jiuzhang.com/solution ... el-order-traversal/ 我改成了python 版本，为什么没发通过啊？

1. class Solution:
   
2.     """
   
3.     @param root: The root of binary tree.
   
4.     @return: Level order in a list of lists of integers
   
5.     """
   
6.     def levelOrder(self, root):
   
7.         # write your code here
   
8.         result = []
   
9.         if root is None:
   
10.             return result
    
11.         q = Queue.Queue(0)
    
12.         q.put(root)
    
13.         while not q.empty:
    
14.             level = []
    
15.             size = q.qsize()
    
16.             for i in range(size):
    
17.                 head = q.get()
    
18.                 level.append(head)
    
19.                 if head.left is not None:
    
20.                     q.put(head.left)
    
21.                 if head.right is not None:
    
22.                     q.put(head.right)
    
23.             result.append(level)
    
24.         return result

复制代码

chendanlan 发表于 2015-9-22 09:12
4.请问 这道题 http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal/ 我改成了python 版 ...

已解决！！

stellari 发表于 2015-9-17 10:39
从lz给出的这些代码碎片推断，该作者的习惯是每次缩小范围时都设置
end= mid 和start=mid（九章算法就是这 ...

对称的话，那种情况下不能收敛到只有一个元素呢