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

实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)

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.     }

复制代码

看不懂啊

这个也是经典的解法吧，我感觉对以后的匹配特别是重复匹配很有借鉴，最近我也刚开始刷刷到第三节，所以很弱弱哒回答一下，就是这边是这样的。

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

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

fengyunzhe820 发表于 2014-8-13 22:12
这个也是经典的解法吧，我感觉对以后的匹配特别是重复匹配很有借鉴，最近我也刚开始刷刷到第三节，所以很弱 ...

谢谢啊~文科生转CS伤不起啊T T

fengyunzhe820 发表于 2014-8-13 22:12
这个也是经典的解法吧，我感觉对以后的匹配特别是重复匹配很有借鉴，最近我也刚开始刷刷到第三节，所以很弱 ...

你说的是第一个解法？这是解二，貌似不是这么回事吧？1<<val这句该怎么理解啊

fengyunzhe820 发表于 2014-8-13 22:12
这个也是经典的解法吧，我感觉对以后的匹配特别是重复匹配很有借鉴，最近我也刚开始刷刷到第三节，所以很弱 ...

谢谢回复啊，刚刚问大神已经全懂了！

TonyJang 发表于 2014-8-14 15:48
谢谢回复啊，刚刚问大神已经全懂了！

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

是不是不考虑大小写?

暑假小学生 发表于 2014-8-15 23:32
是不是不考虑大小写?

是没有考虑。这是用bit vector实现的一种方式，放到更大的数据，就是bitmap的方式。