public boolean isUnique(String astr) {
char[] ch = new char[26];
for (char c : astr.toCharArray()) {
if (ch[c - 'a'] != 0) return false;
ch[c - 'a']++;
}
return true;
}
Last updated
public boolean isUnique(String astr) {
int mark = 0;
for (char ch : astr.toCharArray()) {
//拿到每个字符的移动的位数 [0-25]开始
int bit = ch - 'a';
//如果这一位被对冲掉，返回false
if ((mark & (1 << bit)) != 0) {
return false;
} else {
//拼凑mark
mark |= (1 << bit);
}
// PrintUtils.toBinaryString(mark, 26);
}
return true;
}public boolean hasAlternatingBits(int n) {
int t = -1;//初始值
while (n > 0) {
//拿到最右边的一位
int bit = n & 1;
//如果当前的bit位于上一位t是相同的，则返回false
//异或（ ^ ）每一位进行比较，相同为0，不同为1
if ((t ^ bit) == 0) return false;
//当前位bit 赋值给上一位 t
t = bit;
//右移一位
n >>= 1;
}
return true;
}public boolean hasAlternatingBits(int n) {
n = n ^ (n >> 1);
return (n & n + 1) == 0;
}public boolean hasAlternatingBits(int n) {
//调用库函数
char[] bits = Integer.toBinaryString(n).toCharArray();
for (int i = 0; i < bits.length - 1; i++) {
if (bits[i] == bits[i + 1]) {
return false;
}
}
return true;
}统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：
方法1：
- 第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000
- 第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000
- 第三次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000 我们发现，每计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：
count = 0
while(a){
a = a & (a - 1);
count++;
}
方法2：见下面的「返回i的二进制最低位位1的权值」
count = 0
while(a){
a -= a & (-a);
count++;
}
方法3：
count = 0
while(a){
count+=a&1;
a >>>= 1;//无符号右移 相当于 /2
}public int countPrimeSetBits(int left, int right) {
int res = 0;
for (int a = left; a <= right; a++) {
if (isPrime(count(a))) res++;
}
return res;
}
public int count(int a) {
int cnt = 0;
while (a > 0) {
cnt += a & 1;
a >>= 1;
}
return cnt;
}
/**
* 判断一个数是否是素数
*/
public boolean isPrime(int a) {
if (a < 2) return false;
for (int i = 2; i * i <= a; i++) {
if (a % i == 0) return false;
}
return true;
}public int countPrimeSetBits(int left, int right) {
List<Integer> primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19);
int cnt = 0;
for (int i = left; i <= right; i++) {
int bits = 0;
for (int x = i; x > 0; x >>= 1) {
bits += x & 1;
}
if (primes.contains(bits)) cnt++;
}
return cnt;
}public int countPrimeSetBits(int left, int right) {
List<Integer> primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19);
int[] f = count(right);
int cnt = 0;
for (int i = left; i <= right; i++) {
if (primes.contains(f[i])) cnt++;
}
return cnt;
}
public int[] count(int x) {
if (x == 0) return new int[]{};
int[] f = new int[x + 1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= x; i++) {
f[i] = f[i >> 1] + f[i & 1];
}
return f;
}public int binaryGap(int n) {
//前一个为1的位置的索引，当前的索引
int prev = -1, cur = 0;
int gap = 0;
while (n > 0) {
//记录下当前位为1的索引，如果满足更新gap的条件，开始更新
if ((n & 1) == 1) {
if (prev != -1) gap = Math.max(gap, cur - prev);
prev = cur;
}
n >>= 1;//向右移位，去掉一位
PrintUtils.toBinaryString(n,8);
cur++;//当前位+1
}
return gap;
}