Leetcode sword finger offer special (I) integer

001. Integer division

subject ： Given two integers a and b , Find the quotient of their division a/b , It is required that the multiplication sign... Shall not be used ‘*’、 devide ‘/’ And the remainder symbol ‘%’ .

Be careful ：
1） Integer division involves truncating the decimal part
2） The environment can only store 32 Bit signed integer , If overflow output 2³¹ − 1

Method ：
We have to deal with symbols first , take a The absolute value of A and b The absolute value of B.
1） Violence looms ： Find the biggest B×Z<=A, By constantly adding B To approach A, Add B The number of times Z That's the answer. . Consider the most extreme situation , That is to say A=2³¹ − 1、B=1, Will timeout .
2） Binary analog division ： find (B<<i)<= A<(B<<(i+1)), You can know the number of business i Is it 1, let A=(A-B<<i) Then repeat the previous steps , If you can't move left, it means there are decimals .
3） Two points search ： Force the method given by the official , Based on the violent approximation of method one , Did a binary search optimization search Z, But every time I get Z It is necessary to judge whether it is too big or too small by multiplication . Because you can't use the multiplier “ * ”, You can use “ Fast ride ” To achieve multiplication .

Fast ride ： It's actually binary analog multiplication

// Fast ride , Calculation x ride y Product of 
long long ksc(long long x,long long y,long long p){
    
	long long res=0;
	while(y){
    
		if(y&1)res=(res+x)%p;
		x=(x<<1)%p; 
		y>>=1;
	}return res;
}

Code ： Method 2 was used , Binary analog division .

class Solution {
    
public:
    long long divide(long long a, long long b) {
    // use long long, Because the absolute value of a negative number will exceed int
        // Symbol processing 
        bool flag=false;
        if((a>=0&&b>=0)||(a<0&&b<0))
            flag=true;
        // Absolute value 
        a=(a<0?-a:a);
        b=(b<0?-b:b);
        // Analog binary division 
        long long ans=0;
        while(a>=b){
    
            long long x=0,tmp=1;
            while((b<<x)<=a){
    
                x++;
            }
            x--;
            a=a-(b<<x);
            ans=ans+(tmp<<x);
        }
        // Result symbol processing 
        if(flag==false)
            ans=-ans;
        // Carry out overflow treatment according to the requirements of the topic 
        if(ans>2147483647||ans<-2147483648)
            ans=2147483647;
        return ans;
    }
};

002. Binary addition

subject ： Given two 01 character string a and b , Please calculate their sum , And output... In the form of binary string .

Be careful ： The key is to deal with additive carry , Especially the highest carry .

Method ：
1） Some languages can put 10⁴ The binary number of bits is converted into hexadecimal calculation , for example python and java.
2） use C++ Language can only simulate binary addition .

class Solution {
    
public:
    string addBinary(string a, string b) {
    
        //C++ string The use of related functions ,reverse Transposition 
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int i=0,j=0,c=0;//i Traverse a,j Traverse b,c Record carry 
        string ans;
        while(i<a.size()||j<b.size()||c){
    
            // Calculate the sum of current bits , Store in ch in 
            char ch=c+'0';
            if(i<a.size())
                ch+=a[i]-'0';
            if(j<b.size())
                ch+=b[i]-'0';
            // Processing carry , Get the right result 
            if(ch>'1'){
    
                c=1;
                ans.insert(ans.end(),ch-2);
            }
            else{
    
                c=0;
                ans.insert(ans.end(),ch);
            }
            i++;j++;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

003. front n A number in binary 1 The number of

subject ： Given a nonnegative integer n , Please calculate 0 To n In the binary representation of each number between 1 The number of , And output an array .

Method ：
1） violence , By constantly eliminating 2 Take the remainder to calculate 1 The number of , The complexity of time is nlogn.
2） Dynamic programming , For odd numbers , It must be one more than the last even number 1; For even numbers ,1 The number and division of 2 The number of is the same , except 2 Just erase the status 0. The time complexity can be reduced to O(n).

Code ： Method 2

class Solution {
    
public:
    vector<int> countBits(int n) {
    
        vector<int>dp;
        dp.push_back(0);
        for(int i=1;i<=n;i++){
    
            int num=i%2==0?dp[i>>1]:dp[i-1]+1;
            dp.push_back(num);
        }
        return dp;
    }
};

004. A number that appears only once

subject ： Give you an array of integers nums , Except that an element appears only once , Every other element just happens to appear Three times . Please find and return the element that only appears once .

Method ：
1） Using arrays , Count every occurrence of binary 1 Times and then more 3 That's the answer. .
2） use map, Count the number of different numbers , For the last time map Output the number that appears only once .
3） Design with digital circuit , stay 1） On the basis of , Think from the perspective of finite state automata . On every binary bit 1 Of 3, There are three states , That is to say 0、1、2. Using binary to represent three states requires two digits , That is to say 00、01、10, Use them separately two and one To indicate high and low . By drawing the state transition diagram , Then the Karnaugh map is used to get the equation of state .
$\overline{next-one}=two\ast \overline{one}+\overline{one}\ast \overline{num}+one\ast num$
$\overline{next-two}=\overline{two}\ast \overline{one}+\overline{two}\ast \overline{num}+two\ast num$

two one\ Input num	0	1
00	00	01
01	01	10
11( Invalid )	11	00
10	10	00

Code ： Method 3

class Solution {
    
public:
    int singleNumber(vector<int>& nums) {
    
        int one=0,two=0;
        for(int i=0;i<nums.size();i++){
    
            int next_one=(two&(~one))|((~one)&(~nums[i]))|(one&nums[i]);
            int next_two=((~two)&(~one))|((~two)&(~nums[i]))|(two&nums[i]);
            one=~next_one;
            two=~next_two;
        }
        return one;
    }
};

Expand ： If an element occurs an odd number of times , Other elements appear even times , Can be solved by exclusive or . XOR is the same as 0, Different for 1.

005. Maximum product of word length

subject ： Given an array of strings words, Please calculate when two strings words[i] and words[j] Does not contain the same characters , The maximum of the product of their lengths . Suppose that the string contains only English lowercase letters . If there is no pair of strings that do not contain the same characters , return 0.

Method ：
1） violence , Judge whether the conditions are met in each pair of different characters , Calculate the product of length after meeting the conditions , Then see if you need to update the maximum product . Because the maximum range of string length and number is 3000, The worst time complexity will time out .
2） Bit operation optimization ： The title requires to compare the types of lowercase letters of different strings , And calculate the product of the length of the string that meets the condition , So the valid information of each string can be recorded as 26 A bit （ Every bit 01 Indicates whether the corresponding lowercase letter exists ）, Plus its string length . Whether the two strings have the same characters , You can compare and operate special strings , If the same person is 1, Then it must not be 0, It means that there are the same characters .
3） stay 2） On the use of map Optimize ： There will be different strings with the same character types , But we only need to keep the longest , It can be used map Match the maximum length corresponding to different character types . This can save redundant judgment .

Code ： Method 3

class Solution {
    
public:
    int maxProduct(vector<string>& words) {
    
        //map Match the maximum string length corresponding to different letter types 
        map<int,int>mp;
        for(int i=0;i<words.size();i++){
    
            // Store string 26 What happens to letters ,false It means that there is no ,true Express 
            bool w[26]={
    false};
            for(int j=0;j<words[i].length();j++){
    
                w[words[i][j]-'a']=true;
            }
            // hold bool Array storage is converted to int
            int num=0;
            for(int j=0;j<26;j++){
    
                if(w[j])
                    num+=1<<j;
            }
            // Record the maximum string length 
            if(mp[num]<words[i].length())
                mp[num]=words[i].length();
        }
        // Traverse two different letter combinations , Find the maximum length product that meets the requirement of not containing the same characters 
        map<int,int>::iterator iter1,iter2;
        int ans=0;
        for (iter1=mp.begin(); iter1!=mp.end(); iter1++){
    
            for(iter2=iter1;iter2!=mp.end(); iter2++){
    
                if((iter1->first&iter2->first)==0){
    
                    ans=max(ans,iter1->second*iter2->second);
                }
            }
        }
        return ans;
    }
};

feeling ：
1） About thinking about algorithms , At first, I thought that special algorithms were needed to reduce the complexity , Just give up looking at the answer directly . actually , Constantly optimize the violent solution , It can be solved . Encountered algorithm problems at present , If there is no thought , You can often try to use violence first and then slowly optimize , Then think about it from the perspective of special algorithms .

006. Sort the sum of two numbers in the array

subject ： Given a has been according to Ascending order Array of integers for numbers , Please find out two numbers from the array, and the sum of them is equal to the target number target .
Functions should be length based 2 Returns the subscript values of the two numbers in the form of an array of integers .numbers The subscript from 0 Start counting , So the answer array should satisfy 0 <= answer[0] < answer[1] < numbers.length .
Suppose that there is only one pair of qualified numbers in the array , At the same time, a number cannot be used twice .

Method ：
1） Double pointer , Left pointer left From the far left , Right pointer right From the far right , If numbers[left]+numbers[right]>target, that right–; If numbers[left]+numbers[right]<target, that left++; If numbers[left]+numbers[right]==target,left、right That's the answer. .

class Solution {
    
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
    
        vector<int>ans;
        int len=numbers.size();
        int fst=0,lst=len-1;
        while(numbers[fst]+numbers[lst]!=target){
    
            if(numbers[fst]+numbers[lst]<target){
    
                fst++;
            }
            else{
    
                lst--;
            }
        }
        ans.push_back(fst);
        ans.push_back(lst);
        return ans;
    }
};