📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2711| 回复: 13
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] CareerCup 9.5

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Given a sorted array of strings which interspersed with empty strings, write a method to fidn the location of a given string.

Example: find "ball" in ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""] will return 4
Example: find "ballcar" in ["at", "", "", "", "", "ball", "car", "", "", "dad", "", ""] will return -1

上一篇:CareerCup 9.4
下一篇:CareerCup 9.6
🔗
oldfishdk 2012-8-4 05:34:11 | 只看该作者
全局:
不知道我想法又没有问题,和一般的binary search有什么区别吗?
  1. int search_str (string *a, int a_size, string tgt)
  2. {
  3.         int idx_beg = 0,
  4.                 idx_end = a_size - 1;

  5.         while (idx_beg<=idx_end) {
  6.                 // assure it will not compare the target string with empty string
  7.                 while (a[idx_beg]=="")
  8.                         idx_beg += 1;
  9.                 while (a[idx_end]=="")
  10.                         idx_end -= 1;
  11.                 int idx_mid = (idx_beg+idx_end)/2;
  12.                 while (a[idx_mid]=="")
  13.                         idx_mid -= 1;
  14.                 if (idx_mid<idx_beg)
  15.                         return -1;
  16.                 // binary search
  17.                 if (a[idx_mid]>tgt) {
  18.                         idx_end = idx_mid - 1;
  19.                 } else if (a[idx_mid]<tgt) {
  20.                         idx_beg = idx_mid + 1;
  21.                 } else if (a[idx_mid]==tgt) {
  22.                         return idx_mid;
  23.                 } else {
  24.                         // error
  25.                         return -1;
  26.                 }
  27.         }

  28.         // no target has been found
  29.         return -1;
  30. }
复制代码

评分

参与人数 1大米 +25 收起 理由
writecoffee1 + 25 自己写testcase跑一下吧,我只能加这么多了

查看全部评分

回复

使用道具 举报

🔗
285845348 2012-8-4 12:15:54 | 只看该作者
全局:
如果定位在""上了,往两边搜索的平均效果可能要好于单方向搜索
回复

使用道具 举报

🔗
 楼主| BinaryWitch 2012-8-4 16:12:33 | 只看该作者
全局:
oldfishdk 发表于 2012-8-4 05:34
不知道我想法又没有问题,和一般的binary search有什么区别吗?

思路差不多,不过程序有些小问题:
1. string* a ?
2. += 1, -= 1 这种写法...
3. 如果头或尾是空的时候继续寻找,但是没有判断越界
4. 如果 mid 是空的时候继续寻找,既然上面的 while 保证 begin 不是空,
    那么 mid 一定可以找到 >= begin 且不是空的,还要 if mid < begin 干吗


回复

使用道具 举报

🔗
oldfishdk 2012-8-4 18:43:34 | 只看该作者
全局:
BinaryWitch 发表于 2012-8-4 16:12
思路差不多,不过程序有些小问题:
1. string* a ?
2. += 1, -= 1 这种写法...

多谢评论了!

1. string* a??
不是很明白,请问什么意思?

2. +=1, -=1.. 偷懒写习惯了..

3. 确实这里的判断多余了,开始写的时候想的是如果idx_mid低于idx_beg的话就表示没有找到目标string,直接返回-1.
回复

使用道具 举报

🔗
oldfishdk 2012-8-4 18:43:55 | 只看该作者
全局:
285845348 发表于 2012-8-4 12:15
如果定位在""上了,往两边搜索的平均效果可能要好于单方向搜索

能详细说一下吗?谢谢
回复

使用道具 举报

🔗
 楼主| BinaryWitch 2012-8-4 18:51:47 | 只看该作者
全局:
BinaryWitch 发表于 2012-8-4 16:12
思路差不多,不过程序有些小问题:
1. string* a ?
2. += 1, -= 1 这种写法...

string* 是你传的参数类型
写 ++ -- 才是”偷懒“
回复

使用道具 举报

🔗
285845348 2012-8-5 05:11:42 | 只看该作者
全局:
oldfishdk 发表于 2012-8-4 18:43
能详细说一下吗?谢谢

我也不知道对不对,我就是随便一想随便一说哈。
就是二分搜索如果取中间位置的元素,取到了"",然后想左右两边找非""的元素,而不是只向一边找,找到了比较后就能把目标元素限制在更小范围内
回复

使用道具 举报

🔗
parker0203 2012-8-7 06:08:55 | 只看该作者
全局:

评分

参与人数 1大米 +25 萝卜 +2 收起 理由
writecoffee1 + 25 + 2 同学们都好勤奋啊

查看全部评分

回复

使用道具 举报

🔗
lml 2012-8-22 01:33:14 | 只看该作者
全局:
碰到“”也可以去两边二分查找,顺便问下大家,solution的14行当mid指针移到strings[]的末尾,strings[mid]应该为NULL,那14行应该报错吧
回复

使用道具 举报

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

本版积分规则

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