第一题: 二进制数转字符串

LeetCode: 面试题 05.02. 二进制数转字符串
描述:
二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。

解题思路:

首选要了解小数转二进制的方法,
小数转二进制,就是一直*2 , 然后摘取整数部分, 直到为0
例如: 0.625

0.625 * 2 = 1.25 => 1
0.25 * 2 = 0.5 => 0
0.5 * 2 = 1.0 => 1

得到 101
注意这里的ERROR , 当一直*2,得到的数据超过32位,就是ERROR

代码实现:

class Solution {
    public String printBin(double num) {
   		// 这里初始化一下
        StringBuilder sb = new StringBuilder("0.");
        while(num != 0){
        	// *2 获取结果
            num = num * 2;
            // 得到这个整数位, 并添加到sb中
            sb.append(num - 1 >=0 ? 1 : 0);
            // 除去这个整数部位
            num = num % 1;
            // 判断当前是否超出了32位
            if(sb.length() > 32) return "ERROR";
        }
        return sb.toString();
    }
}

第二题: 配对交换

LeetCode: 面试题 05.07. 配对交换
描述:
配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。

解题思路:

使奇数位左移, 偶数位右移, 然后两者或运算取得结果
 
让奇数位 与 0x55555555(奇数位为1, 偶数位为0) 与运算 左移
让偶数位 与 0xaaaaaaaa(奇数位为0, 偶数位为1) 与运算 右移
 
让两者的结果 或运算

代码实现:

class Solution {
    public int exchangeBits(int num) {
        int x = (num & 0x55555555) << 1;
        int y = (num & 0xaaaaaaaa) >> 1;
        return x|y;
    }
}

第三题: 整数转换

LeetCode: 面试题 05.06. 整数转换
描述:
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。

解题思路:

这里就是判断这两个数有几位是不同的

1. 首先让 A 和 B 进行异或运算 得到的数字的二进制上1的个数就是不同的位数
2. 判断这个数字的1的个数.
   这里可以使用 C = C & (C-1) 直到 C=0, 这里循环几次, 就是1的个数

代码实现:

class Solution {
    public int convertInteger(int A, int B) {
    	// 异或得到这个数
        int tmp = A ^ B;
        int count = 0;
        // 循环几次 就是位1的个数
        while(tmp!=0){
            tmp = tmp & (tmp-1);
            count++;
        }
        return count;
    }
}

第四题: 魔术索引

LeetCode : 面试题 08.03. 魔术索引
描述:
魔术索引。 在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

解题思路:

这里可以直接遍历, 看下标是否和值匹配, 遍历结束没有就返回-1;
优化:
由于题目中说了是有序整数数组, 可以直接跳跃遍历.
index = Math.max( index+1, nums[index])

代码实现:

class Solution {
    public int findMagicIndex(int[] nums) {
        int index = 0;
        while(index < nums.length){
            if(index == nums[index]){
                return index;
            }
            // 这里跳跃
            index = Math.max(index+1,nums[index]);
        }
        return -1;
    }
}

第五题: 无重复字符串的排列组合

LeetCode : 面试题 08.07. 无重复字符串的排列组合
描述:
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同

解题思路:

使用回溯解, bfs,
注意这里的剪枝, 不能重复使用同一个, 使用一个boolean数组来进行剪枝
由于此题是无重复字符串, 这里就不需要考虑有多个相同的字符

代码实现:

class Solution {
    private List<String> list = new ArrayList<>();
    public String[] permutation(String S) {
        boolean[] tmp = new boolean[S.length()];
        StringBuilder sb = new StringBuilder();
        backstrack(S,tmp,0,sb);
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public void backstrack(String s, boolean[] tmp, int start,StringBuilder sb) {
        if (start == s.length()) {
            list.add(sb.toString());
            return;
        }
        for(int i = 0; i < s.length(); i++) {
            if(!tmp[i]){
                tmp[i] = true;
                sb.append(s.charAt(i));
                backstrack(s,tmp,start+1,sb);
                tmp[i] = false;
                sb.deleteCharAt(start);
            }
        }
    }
}

第六题: 有重复字符串的排列组合

LeetCode : 面试题 08.08. 有重复字符串的排列组合
有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

解题思路:

和上一题一样, 这里的剪枝不只是减重复使用的那一个
还需剪枝, 相同字符的情况.
例如:

• 这里的q是减去 相同字符的枝
• 这里qq 和 ee是减去 重复使用的枝

代码实现:

class Solution {
    private List<String> list = new ArrayList<>();
    private boolean[] tmp = new boolean[10];
    public String[] permutation(String S) {
        StringBuilder sb = new StringBuilder();
        char[] arr = S.toCharArray();
        Arrays.sort(arr);
        backstrack(arr,sb,0);
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public void backstrack(char[] arr,StringBuilder sb, int start) {
        if(start == arr.length){
            list.add(sb.toString());
            return;
        }
        for(int i = 0; i < arr.length; i++) {
            if(i>0 && arr[i] == arr[i-1] && !tmp[i-1]){
                continue;
            }
            if(tmp[i]) {
                continue;
            }
            tmp[i] = true;
            sb.append(arr[i]);
            backstrack(arr,sb,start+1);
            tmp[i] = false;
            sb.deleteCharAt(start);
        }
    }
}