In the new week, come on ~, make progress a little every day ~.

Algorithm problem (Niuke network)

1. Fibonacci sequence

The Fibonacci sequence starts with the third term and is equal to the sum of the first two terms.

Code details:

class Solution {
public:
    int Fibonacci(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1; //Initialize one or two items
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2]; //Equal to the sum of the first two terms
        }
        return dp[n];
    }
};

 2. Longest Palindromic Substring

I can't think of it. After looking at the answer, dynamic planning, central expansion and manacher algorithm, I finally chose central expansion. Dynamic planning is too chaotic, and manacher is a little difficult to understand.

Code details:

class Solution {
public:
    /**
     * The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly
     *
     * 
     * @param A string character string 
     * @return int integer
     */
    int getLongestPalindrome(string A) {
        // write code here
        for(int i = 0;i < A.size();i += 2){ //Unified parity string
            A.insert(i, "#");
        }
        A.push_back('#');
        int max_length = 1; //Store the length of the longest palindrome substring
        
        for(int i = 0;i < A.size();++i){
            int l = i-1,r = i+1; //Create left and right pointers
            int length = (A[i] == '#')?0:1; //Note whether it is' # '
            while(l >= 0 && r < A.size()){
                if (A[l] == '#'){
                    l--,r++;
                    continue; //The '#' character is not calculated
                } 
                
                if (A[l--] == A[r++]){
                    length += 2;
                }
                else{
                    break;
                }
            }
            max_length = max(max_length,length);
        }
        
        return max_length;
    }
};

3. Sum of three numbers

It is a little different from the sum of two numbers. Use the double pointer method, a fixed one, and the left and right pointers look in from both ends.

Code details:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        int n = num.size();
        vector<vector<int>> res; //Store final answer
        if (n < 3) return res;//Boundary judgment
        sort(num.begin(), num.end()); //Rearrange numbering sequence
        
        for(int i = 0; i < n; ++i){
            if (num[i] > 0) break; //Greater than zero, followed by greater than zero
            if (i > 0 && num[i] == num[i-1]) continue;
            int l = i + 1,r = n - 1; //Create left and right pointers
            while(l < r){
                if (num[i] + num[l] + num[r] > 0){ //If the sum is greater than zero, r is large
                    --r;
                }
                else if (num[i] + num[l] + num[r] < 0){ //Similarly
                    ++l;
                }
                else{
                    int m = res.size();
                    //Determine whether it is equal to the last pressed array
                    if(m > 0 && (res[m-1][0] != num[i] || res[m-1][1] != num[l] || res[m-1][2] != num[r])){
                        res.push_back({num[i],num[l],num[r]});
                    }
                    else if (m == 0){
                        res.push_back({num[i],num[l],num[r]});
                    }
                    
                    --r,++l; //There may be other arrays that add up to zero
                }
            }
        }
        
        return res;
    }
};

Algorithm problem (brother hero's nine day training - the first day)

1.Sum of two integers

The +, - operators are not allowed. It seems that we can only use bit operations. After reading the answer, I didn't understand it very much, so I had to memorize it by rote.

Code details:

class Solution {
public:
    int getSum(int a, int b) {
        while(b != 0){
            unsigned int carry = (unsigned int)(a & b) << 1; //Get unsigned carry
            a = a ^ b; //Add up
            b = carry;
        }

        return a;
    }
};

Adoption details:

 2.Addition without plus sign

It's so magical. Why is the difficulty of the same subject different? I also thought of converting binary into array and operating in the array, similar to the string addition yesterday.

Code details:

class Solution {
public:
    int add(int a, int b) {
        while(b != 0){
            unsigned int carry = (unsigned) (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

Pass record: 

 3.No addition, subtraction, multiplication and division

How one question, how many ways to ask it, may want us to practice makes perfect!

Code details:

class Solution {
public:
    int add(int a, int b) {
        while(b != 0){
            unsigned int carry = unsigned (a & b) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }
};

Adoption details: 

4.Recursive multiplication 

Finally, it's not addition, but I can't. hahaha. After reading the answer, I probably know that it seems to be to turn multiplication into addition for operation, but I don't understand bit operation very well. I'll memorize it first for the time being.

Code details:

class Solution {
public:
    int multiply(int A, int B) {
        int ans=0;
        for(long long a = max(A,B), b = min(A,B); b; b >>= 1,a += a){ 
            if(b & 1) ans += a; 
        }       
        return ans;
    }
};

Adoption details:

 5.Divide two numbers

Hahaha, after reading the solution, forget it. It's too difficult to put it down for the time being.

Interview questions

1. Realization of polymorphism

First, what is polymorphism? Definition of polymorphism: the same operation acts on different objects, which can have different interpretations and produce different execution results. There are two types of polymorphism: compile and run.

So why polymorphism? In order to enhance the scalability of the program, there are less codes to be changed and added in the later modification.

So how to achieve polymorphism (that is, interview questions)? The key is to call virtual functions through base class pointers or references. Every class with virtual function will have a virtual function table, and any object of this class will have a pointer to the virtual function.

2. The difference between overloaded assignor and copy constructor

First, what is assignment overloading? Overloaded operator = function. When assigning a value to an object, the overloaded assignment operator will be called. So what is a copy constructor? When an object is initialized by copying, the copy constructor is called.

The biggest difference is that the assignment operator does not generate a new object, while the copy constructor generates a new object.

3. When is the copy constructor called

1. When one object of the class is used to initialize another object of the class

2. The formal parameter of the function is the object of the class. When calling the function.

3. The return value of the function is the object of the class. When the function completes the return call.

4. Four types of conversion operators

 

It's 23:43 again. A beautiful day is over. Look forward to the sun tomorrow morning. Come on~~~