📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
123
返回列表 发新帖
楼主: mycoy
跳转到指定楼层
上一主题 下一主题
收起左侧

Yahoo 电面; LC 33. Search in Rotated Sorted Array, follow-up Questions

🔗
lela900900 2017-1-26 22:46:12 | 只看该作者
全局:
laiguojiuhao 发表于 2017-1-18 06:07
如果元素没有重复的话,感觉可以比较第一个元素和最后一个元素,如果第一个比最后一个大,ascending,否则d ...

额 你这个情况 如果没有rotate的话,单调递增or递减的 过不去啊
回复

使用道具 举报

🔗
laiguojiuhao 2017-1-27 03:12:50 | 只看该作者
全局:
lela900900 发表于 2017-1-26 22:46
额 你这个情况 如果没有rotate的话,单调递增or递减的 过不去啊
  1. s = Solution()
  2. nums = range(10)
  3. for i in range(10):
  4.     print s.search(nums, i)

  5. print

  6. nums = range(10)[::-1]
  7. for i in range(10):
  8.     print s.search(nums, i)
复制代码
我测试了这两种情况都是对的;因为如果单调无论跳到if check 还是else,都是标准的二分搜索
回复

使用道具 举报

🔗
RobertCheng 2017-1-31 15:17:10 | 只看该作者
全局:
楼主你的面试官是 Allen 吗
回复

使用道具 举报

全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
laiguojiuhao 2017-2-1 03:08:09 | 只看该作者
全局:
翻滚吧豆子 发表于 2017-1-31 17:00
如果数组的rotate是0怎么搞??所谓rotate,最后一个和第一个的关系,与第一个和第二个的关系,是等价的 ...

rotate 是 0就是没有rotate?可以handle啊,我已经恢复回复过了
回复

使用道具 举报

🔗
wenchiehcm 2017-2-20 08:35:25 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| mycoy 2017-2-20 10:56:05 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
wantyoulee 2017-2-27 07:25:09 | 只看该作者
全局:
感觉题目挺好的。我写了一个java的版本,但是所有credit归于python版本作业。
  1. /*only consider without duplicate*/
  2. public class SearchInRotatedArray {
  3.         public int search(int[] nums, int target) {
  4.                 if (nums == null || nums.length == 0) {
  5.                         return -1;
  6.                 }
  7.                 int start = 0;
  8.                 int end = nums.length - 1;
  9.                 int mid;
  10.                 boolean isAsc = isAscending(nums);
  11.                 while (start + 1 < end) {
  12.                         mid = start + (end - start) / 2;
  13.                         if (check(isAsc, nums[start], nums[mid])) {/* check mono-tone */
  14.                                 /* always check mono-tune part */
  15.                                 if (isBetween(target, nums[start], nums[mid])) {
  16.                                         end = mid;
  17.                                 } else {
  18.                                         start = mid;
  19.                                 }
  20.                         } else {
  21.                                 if (isBetween(target, nums[end], nums[mid])) {
  22.                                         start = mid;
  23.                                 } else {
  24.                                         end = mid;
  25.                                 }
  26.                         }
  27.                 }
  28.                 if (nums[start] == target) {
  29.                         return start;
  30.                 }
  31.                 if (nums[end] == target) {
  32.                         return end;
  33.                 }
  34.                 return -1;
  35.         }

  36.         private boolean isAscending(int[] nums) {
  37.                 return nums[nums.length - 1] < nums[0];
  38.         }

  39.         private boolean check(boolean isAsc, int a, int b) {
  40.                 if (isAsc) {
  41.                         return a <= b;
  42.                 } else {
  43.                         return a >= b;
  44.                 }
  45.         }

  46.         /* is target in between a and b */
  47.         private boolean isBetween(int target, int a, int b) {
  48.                 return Math.min(a, b) <= target && Math.max(a, b) >= target;
  49.         }

  50.         public static void main(String[] args) {
  51.                 int[] nums = { 5, 4, 3, 2, 1, 9, 8, 7 };
  52.                 int index = new SearchInRotatedArray().search(nums, 8);
  53.                 System.out.println(index);
  54.         }
  55. }
复制代码
回复

使用道具 举报

🔗
天空无语 2017-3-26 05:35:07 | 只看该作者
全局:
升序降序楼主看看呢,判断中间数字和两端数字关系,如果大小介于两个之间说明没有翻转过,否则翻转过 说明就是把原来相连的两个数字分开了 那两个数字就在两端。
  1.     private boolean descendingOrAscending(int[] nums){ // Ascending return true Descending return false
  2.         int left = 0;
  3.         int right = nums.length-1;
  4.         int mid = left + (right-left)/2;
  5.         if(nums[left] <= nums[mid] && nums[right] >= nums[mid]){
  6.             return true;
  7.         }else if(nums[left] >= nums[mid] && nums[right] < nums[mid]){
  8.             return false;
  9.         }else{
  10.             return nums[left] > nums[right];
  11.         }
  12.     }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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