LeetCode(Easy)-17/1/13

409. Longest Palindrome

  • 题意：给定一些字符，问能构成的最长的回文串长度是多少
  • 思路：每两个相同的字符就可以增加回文串2长度，如果有单个字符，则可以将其放在回文串的中间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int longestPalindrome(String s) {
        int ans = 0;
        char c;
        Set set = new HashSet();
        for(int i = 0;i < s.length();i++){
            c = s.charAt(i);
            if(!set.contains(c)){
                set.add(c);
            }
            else {//有两个相同的c
                set.remove(c);
                ans += 2;
            }
        }
        if(set.size()!=0) ans++;//有单个字符
        return ans;
}

217. Contains Duplicate

  • 题意：判断数组中的每个数字是不是只出现一次
  • 思路：利用的set的性质就可以了，判断一下set的大小是不是等于数组长度

代码

1
2
3
4
5
6
public boolean containsDuplicate(int[] nums) {
        Set s = new HashSet();
        for(int i = 0;i < nums.length;i++)
            s.add(nums[i]);
        return s.size()!=nums.length;
}

231. Power of Two

  • 题意：判断一个数是否是2的乘方
  • 思路：
  1. 利用n&(n-1)==0,例如00100 & 00011 = 00000
  2. 利用对数函数的换底公式2^x=N->log2(N)=X->log10(N)/log10(2)=X,所以只要判X是不是整数就行了

代码

1
2
3
4
5
6
public boolean isPowerOfTwo(int n) {
        // if(n<=0)
        //     return false;
        // return (n&(n-1))==0;
        return (Math.log10(n)/Math.log10(2))%1==0;
    }

326. Power of Three

  • 题意：不使用循环或递归判断一个数是不是3的乘方
  • 思路：
  1. 预处理int范围内最大的3的乘方
  2. 利用对数函数的换底公式

代码

1
2
3
4
5
6
public boolean isPowerOfThree(int n) {
       //1.先求出3^19
       //return n > 0 && (1162261467 % n == 0);
       //2.log10(n)/log10(3)是不是整数
       return (Math.log10(n) / Math.log10(3)) % 1 == 0;
   }

342. Power of Four

  • 题意：不使用循环或递归判断一个数是不是4的乘方
  • 思路：
  1. 对数函数换底公式
  2. 位运算判断大于0，是2的倍数，且1只在偶数位上，0x55555555=01010101010101010101010101010101

代码

1
2
3
4
public boolean isPowerOfFour(int num) {
         //return (Math.log10(num)/Math.log10(4))%1==0;
         return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;
}

191. Number of 1 Bits

  • 题意：求一个数的二进制数1的位数
  • 思路：通过移位，每次判断最后一个位是不是1，>>>无符号右移，即高位补0

代码

1
2
3
4
5
6
7
8
9
10
public int hammingWeight(int n) {
    System.out.println(Integer.toBinaryString(n)); 
    int ans = 0;
    while(n!=0) {
        ans += (n & 1);
        n >>>= 1;
        System.out.println(Integer.toBinaryString(n));
    }
	return ans;
}

Integer.bitCount源码

1
2
3
4
5
6
7
8
public static int bitCount(int i) {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;    
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

留言

2017-01-13
⬆︎TOP