一亩三分地论坛

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

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

[CareerCup] CC150里的1.1第二种解法哪个大牛给说说

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-8-13 21:02:34 | 显示全部楼层 |阅读模式

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

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

x
实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)
  1.     public boolean isUniqueChars2(String str) {
  2.         int checker = 0;
  3.         for (int i = 0; i < str.length(); i++) {
  4.             int val = str.charAt(i) - 'a';
  5.             if ((checker & (1 << val)) > 0) {
  6.                 return false;
  7.             } else {
  8.                 checker |= (1 << val);
  9.             }
  10.         }
  11.         return true;
  12.     }
复制代码
看不懂啊


fengyunzhe820 发表于 2014-8-13 22:12:06 | 显示全部楼层
这个也是经典的解法吧,我感觉对以后的匹配特别是重复匹配很有借鉴,最近我也刚开始刷刷到第三节,所以很弱弱哒回答一下,就是这边是这样的。

每次都是用一个32位的int来indicate有没有看到过这个字符,看到了就在相对应的那一位上面设置为1
如果以后再看到这一位是1,那就是有重复了,而且用这个办法效率还蛮高的

楼主可以google一下bit manipulation java看一看这些操作符号是什么意思就可以了。
一起刷题共勉哈哈
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-8-13 22:15:54 | 显示全部楼层
fengyunzhe820 发表于 2014-8-13 22:12
这个也是经典的解法吧,我感觉对以后的匹配特别是重复匹配很有借鉴,最近我也刚开始刷刷到第三节,所以很弱 ...

谢谢啊~文科生转CS伤不起啊T T
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-8-14 14:58:03 | 显示全部楼层
fengyunzhe820 发表于 2014-8-13 22:12
这个也是经典的解法吧,我感觉对以后的匹配特别是重复匹配很有借鉴,最近我也刚开始刷刷到第三节,所以很弱 ...

你说的是第一个解法?这是解二,貌似不是这么回事吧?1<<val这句该怎么理解啊
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-8-14 15:48:36 | 显示全部楼层
fengyunzhe820 发表于 2014-8-13 22:12
这个也是经典的解法吧,我感觉对以后的匹配特别是重复匹配很有借鉴,最近我也刚开始刷刷到第三节,所以很弱 ...

谢谢回复啊,刚刚问大神已经全懂了!
回复 支持 反对

使用道具 举报

fengyunzhe820 发表于 2014-8-15 03:50:29 | 显示全部楼层
TonyJang 发表于 2014-8-14 15:48
谢谢回复啊,刚刚问大神已经全懂了!

两个解法本质思路一样~只是第二个用了比较经典的节省空间开销的匹配方法,操作系统里面用得很多。弄懂了就好,加油~
回复 支持 反对

使用道具 举报

暑假小学生 发表于 2014-8-15 23:32:10 | 显示全部楼层
是不是不考虑大小写?
回复 支持 反对

使用道具 举报

jetfish1900 发表于 2014-8-17 15:50:53 | 显示全部楼层
暑假小学生 发表于 2014-8-15 23:32
是不是不考虑大小写?

是没有考虑。这是用bit vector实现的一种方式,放到更大的数据,就是bitmap的方式。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 20:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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