一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 593|回复: 9
收起左侧

[算法题] 两个leetcode问题疑惑

[复制链接] |试试Instant~ |关注本帖
chendanlan 发表于 2015-9-17 10:22:24 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
请问search for a range里面,找最后一个的index,为什么要按 if A[mid] > target:
                end = mid
else:
                start =  mid 这个顺序,反过来就不行呢?
为什么最后比较 if A[start] < A[end]:
            return end
        else:
            return start  
就能找出来尖峰了?


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

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

第1题不是很确定你说的“反”是什么意思。
回复 支持 反对

使用道具 举报

 楼主| chendanlan 发表于 2015-9-17 10:58:08 | 显示全部楼层
3.http://www.jiuzhang.com/solution ... tated-sorted-array/
为什么要num[mid]和num[end]比较,为什么不能和start比较
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2015-9-17 11:17:42 | 显示全部楼层
第一题里,这个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而言)
回复 支持 反对

使用道具 举报

 楼主| chendanlan 发表于 2015-9-17 11:48:36 | 显示全部楼层
mnmunknown 发表于 2015-9-17 11:17
第一题里,这个else包含了A[mid]  = target 的情况,既然你是找后一个index,相等的情况下自然要去推start ...

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

使用道具 举报

mnmunknown 发表于 2015-9-18 08:56:29 | 显示全部楼层
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. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| chendanlan 发表于 2015-9-22 09:11:04 | 显示全部楼层
mnmunknown 发表于 2015-9-18 08:56
不好意思我以为你说的是search in rotated sorted array...

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

谢谢谢谢谢谢!!!!
回复 支持 反对

使用道具 举报

 楼主| chendanlan 发表于 2015-9-22 09:12:29 | 显示全部楼层
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 10:33:21 | 显示全部楼层
chendanlan 发表于 2015-9-22 09:12
4.请问 这道题 http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal/ 我改成了python 版 ...

已解决!!
回复 支持 反对

使用道具 举报

Howie 发表于 2015-9-22 10:45:34 | 显示全部楼层
stellari 发表于 2015-9-17 10:39
从lz给出的这些代码碎片推断,该作者的习惯是每次缩小范围时都设置
end= mid 和start=mid(九章算法就是这 ...

对称的话,那种情况下不能收敛到只有一个元素呢
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 02:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表