Daily question brushing record (II)

The first question is : Binary number to string

LeetCode: Interview questions 05.02. Binary number to string
describe :
Binary number to string . Given a value between 0 and 1 The real number between （ Such as 0.72）, The type is double, Print its binary expression . If the number cannot be accurately used 32 Binary representation within bits , Then print “ERROR”.

Their thinking :

It is preferred to know the method of converting decimal to binary ,
Decimal to binary , It's all the time *2 , Then extract the integer part , Until 0
for example : 0.625

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

obtain 101
Notice the ERROR , When always *2, The data obtained exceeds 32 position , Namely ERROR

Code implementation :

class Solution {
    
    public String printBin(double num) {
    
   		//  Here is the initialization 
        StringBuilder sb = new StringBuilder("0.");
        while(num != 0){
    
        	// *2  To get the results 
            num = num * 2;
            //  Get this integer number ,  To add to sb in 
            sb.append(num - 1 >=0 ? 1 : 0);
            //  Remove the integer part 
            num = num % 1;
            //  Determine whether the current exceeds 32 position 
            if(sb.length() > 32) return "ERROR";
        }
        return sb.toString();
    }
}

The second question is : Pairing exchange

LeetCode: Interview questions 05.07. Pairing exchange
describe :
Pairing exchange . Programming , Exchange the odd and even digits of an integer , Use as few instructions as possible （ in other words , position 0 And bit 1 In exchange for , position 2 And bit 3 In exchange for , And so on ）.

Their thinking :

send Odd bits shift left , Even bits shift right , then Both or operations Get results
 
Give Way Odd number And 0x55555555( Odd bits are 1, Even digits are 0) And operation Move left
Give Way Even digit And 0xaaaaaaaa( Odd bits are 0, Even digits are 1) And operation Move right
 
Let the result of both Or operations

Code implementation :

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

Third question : Integer conversion

LeetCode: Interview questions 05.06. Integer conversion
describe :
Integer conversion . Write a function , Determine how many bits need to be changed to change the integer A Converted to an integer B.

Their thinking :

Here is how many digits of these two numbers are different

1. First let's A and B Xor operation Get the binary of the number 1 The number of is the number of different digits
2. To judge this number 1 The number of .
   Here you can use C = C & (C-1) until C=0, There are several cycles here , Namely 1 The number of

Code implementation :

class Solution {
    
    public int convertInteger(int A, int B) {
    
    	//  XOR gets this number 
        int tmp = A ^ B;
        int count = 0;
        //  Cycle a few times   It's a bit 1 The number of 
        while(tmp!=0){
    
            tmp = tmp & (tmp-1);
            count++;
        }
        return count;
    }
}

Fourth question : Magic index

LeetCode : Interview questions 08.03. Magic index
describe :
Magic index . In the array A[0…n-1] in , There's a magic index , Meet the conditions A[i] = i. Given an ordered array of integers , Write a way to find magic index , If any , In the array A Find a magic index in , without , Then return to -1. If there are multiple magic indexes , Returns the smallest index value .

Their thinking :

Here you can directly traverse , See if the subscript matches the value , After traversal, it returns -1;
Optimize :
Because the title says that it is an ordered integer array , You can jump and traverse directly .
index = Math.max( index+1, nums[index])

Code implementation :

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

Fifth question : Permutations of non repeating strings

LeetCode : Interview questions 08.07. Permutations of non repeating strings
describe :
Permutations of non repeating strings . Write a method , Calculates all permutations of a string , Each character of the string is different

Their thinking :

Use backtracking solutions , bfs,
Pay attention to the pruning here , You cannot reuse the same , Use one boolean Array to prune
Because this question is a non repeating string , There is no need to consider having multiple identical characters

Code implementation :

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);
            }
        }
    }
}

Sixth question : There are permutations and combinations of repeated strings

LeetCode : Interview questions 08.08. There are permutations and combinations of repeated strings
There are permutations and combinations of repeated strings . Write a method , Calculates all permutations of a string .

Their thinking :

Same as the previous question , The pruning here is not just the one that reduces reuse
Still need pruning , Same characters .
for example :

• there q Minus Branches of the same character
• here qq and ee Minus Reusable branches

Code implementation :

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);
        }
    }
}