[question brushing diary] classic questions must be brushed for the introduction of C + +

πŸ˜€ Hello, I'm Bai Chen. I'm not very able to stay up late 😫, But people who want to get better ✈. If you like this article, give it a compliment πŸ‘οΌŒ Pay attention πŸ‘€ Bai Chen! Your support is my biggest motivation! πŸ’ͺπŸ’ͺπŸ’ͺ

🏹 preface

Bai Chen reviewed my C + + learning journey during this period and found many bumps and difficulties. Therefore, Bai Chen sorted out the good problems and big holes I encountered when I started learning C + + 🧐.

The sorting questions are divided into two categories: multiple-choice questions and programming questions.

  • choice question

Bai Chen sorted out many knowledge points that are easy to make mistakes and difficult to master at the beginning, which is equivalent to a repeat of the important and difficult knowledge points. I hope you can deepen your understanding of the important and difficult knowledge points.

  • Programming problem

Among them, it is mainly about C + + input and output, the use of STL (Standard Template Library), dynamic planning, data structure and other topics. The topics are not very difficult, but they are very representative and classic. They should be seen and mastered by every C + + beginner.

πŸ—‘ C + + entry must brush classic topics

πŸͺ“ 1. Multiple choice questions

πŸ• 1.1 type conversion of class


πŸ“˜ Answer analysis:

πŸ” 1.2 number of copy construction calls


πŸ“˜ Answer analysis:

🍟 1.3 friend function

πŸ“˜ Answer analysis:

🌭 1.4 static data members

πŸ“˜ Answer analysis:

πŸ“˜ Answer analysis:

🍿 1.5 new create object


πŸ“˜ Answer analysis:

πŸ§‚ 1.6 template format

πŸ“˜ Answer analysis:

πŸ₯“ 1.7 empty class size


πŸ“˜ Answer analysis:

The empty class system allocates a byte of space to represent the space occupation

πŸ₯š 1.8 destructor


πŸ“˜ Answer analysis:

πŸ“˜ Answer analysis:

🍳 1.9 assignment operator

πŸ“˜ Answer analysis:

πŸ§‡ 1.10 constructor call

πŸ“˜ Answer analysis:

πŸ₯ž 1.11 initialization list

🧈1.12 const


πŸ“˜ Answer analysis:

🍞1.13 delete this


πŸ“˜ Answer analysis:

This is correct, but not recommended.

πŸ₯1.14 c_str()


πŸ“˜ Answer analysis:

Although in terms of content, a == b, a and b are two different objects, and the location stored in the space is also different, C_ The return value of STR is const char *, that is, the address in the space, so it cannot be equal.

So choose A.

πŸ₯¨1.15 resize/reserve


πŸ“˜ Answer analysis:

str.reserve(111); // Adjust the capacity to 111

str.resize(5); // Adjust the number of elements to 5

str.reserve(50); // The adjusted capacity is 50. Since the adjusted capacity is less than the existing space capacity, the capacity will not be reduced

So size=5 capacity=111

So the answer is: C

πŸ₯―1.16 cerr

πŸ₯– 1.17 base and derived classes

πŸ§€ 1.18 inherited object model

πŸ”¨ 2. Programming questions

πŸ₯ 2.1 string addition

✈ Original title link: String addition

Simulation:

πŸŽ‰ Specific ideas:

We can simulate normal addition, starting from single bit and adding bit by bit. In the process of simulation, we should pay attention to:

  • We take out that each element of the string is a character, so we can't add it directly. We must subtract '0' to get the real value of this number.
  • When each bit of a number has been traversed, if another number has not been traversed, fill 0 in the high position of the number.
  • If the sum of two numbers is greater than or equal to 10, carry.
  • Insert a single digit obtained by this addition into the string to be returned each time.
  • Finally, the returned string is reversed, so we need to reverse it.

πŸŽƒ Code implementation:

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1;
        int flag = 0;
        string ret;
		// When the given number is not traversed or needs to be carried, it enters the loop
        while (i >= 0 || j >= 0 || flag != 0)
        {
            // Judge whether a number has been traversed
            int val1 = i >= 0 ? num1[i] - '0' : 0;
            int val2 = j >= 0 ? num2[j] - '0' : 0;
            // See if there is carry
            // flag == 1, carry; otherwise, no carry
            flag = flag == 1 ? val1 + val2 + 1 : val1 + val2;
			// Insert the number of digits added this time after the returned string
            ret += flag % 10 + '0';
            flag /= 10;
            i--;
            j--;
        }
		// Reverse string
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

πŸ₯₯ 2.2 string multiplication

✈ Original title link: String multiplication

Method 1: analog vertical + addition

πŸŽ‰ Specific ideas:

Let's first look at how the multiplication in the example is calculated with the vertical formula:

  • We found that from right to left, each bit of num2 needs to be multiplied by num1, and the weight of the number obtained by multiplying num1 once needs to be multiplied by 10.

  • num2 each bit multiplied by num1 is a single digit * num1, so we can save the result of single digit multiplied by num1 and call it directly when using it.

  • After getting the string of num2 multiplied by num1, save it. Finally, like the vertical, add the results of each bit in turn to get the final answer.

πŸŽƒ Code implementation:

class Solution {
public:
    // Addition of reuse questions
    string Add(const string& num1, const string& num2)
    {
        string ret;
        int add = 0;
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        while (end1 >= 0 || end2 >= 0 || add != 0)
        {
            int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;
            int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;

            add = n1 + n2 + add;
            ret += add % 10 + '0';
            add /= 10;
        }

        reverse(ret.begin(), ret.end());
        return ret;
    }
    
    string multiply(string num1, string num2) {
        // When 0 appears, it returns "0" directly
        if (num1 == "0" || num2 == "0")
            return "0";

        int len1 = num1.size(), len2 = num2.size();
        // Save the value of 0 ~ 9 times num1
        vector<string> save(10);
        // Save the value of num2 multiplied by num1 for each bit
        vector<string> ret(len2 + 1);
        // 0 times any number is 0
        save[0] = "0";
        // Save the last return value
        ret[len2] = "0";
        // Record weight
        int pos = 0;
		
        // Save the value of 0 ~ 9 times num1
        for (int i = 1; i < 10; ++i)
        {
            save[i] = Add(save[i - 1], num1);
        }
		// Save the value of num2 multiplied by num1 for each bit
        for (int i = len2 - 1; i >= 0; --i)
        {
            int val = num2[i] - '0';
            ret[i] = save[val];
            // Fill 0 after the string according to the weight
            for (int j = 0; j < pos; ++j)
                ret[i] += '0';
            // The weight is increased by one for each number multiplied
            pos++;
        }
		// The whole adds up
        for (int i = 0; i < len2; ++i)
        {
            ret[len2] = Add(ret[len2], ret[i]);
        }

        return ret[len2];
    }
};

2. Optimize vertical + analog multiplication

πŸŽ‰ Specific ideas:

  1. First, let's discuss how many digits the result of multiplying m digits by n digits is.

  1. From the above formula, the longest number obtained by final multiplication is m + n m+n m+n, so we can open up one in advance m + n m+n m+n length array to store this number.

  2. Since we want to use multiplication for simulation, we can optimize our vertical multiplication

After the optimization, we can get the specific method through the vertical formula:

  • The original step of multiplying one shaping at a time is disassembled into one number at a time and only one number at a time
  • So you don't have to worry about overflow
  • And we can add the multiplication result directly to the corresponding bit of the above array, just like the vertical type above
  1. After all the vertical operations are completed, the array obtained by processing is carried to ensure that each bit is a single digit.
  2. Then convert the array into a string and return.

πŸŽƒ Code implementation:

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";

        int m = num1.size(), n = num2.size();
        vector<int> num(m + n);
        string ret;

        // Simulate every bit by every bit
        for (int i = n - 1; i >= 0; --i)
        {
            int val2 = num2[i] - '0';
            for (int j = m - 1; j >= 0; --j)
            {
                int val1 = num1[j] - '0';
                int mul = val1 * val2;
                // Add the multiplied result to the corresponding bit
                num[i + j + 1] += mul;
            }
        }
        // carry
        for (int i = m + n - 1; i > 0; --i)
        {
            num[i - 1] += num[i] / 10;
            num[i] %= 10;
        }
        // Judge whether there is the highest position
        int i = num[0] == 0 ? 1 : 0;

        for (; i < m + n; ++i)
        {
            ret += num[i] + '0';
        }

        return ret;
    }
};

πŸ‡ 2.3 delete duplicates in ordered array

✈ Original title link: Remove duplicates from ordered arrays

Method 1: violent solution

πŸŽƒ Code implementation:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        vector<int>::iterator begin = nums.begin();

        while (begin != nums.end())
        {
            if (begin + 1 != nums.end() && *begin == *(begin + 1))
                begin = nums.erase(begin);
            else
                begin++;
        }

        return nums.size();
    }
};

Method 2: fast and slow pointer

πŸŽƒ Code implementation:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        size_t slow = 0, fast = 0;
        size_t len = nums.size();

        while (fast < len)
        {
            if (nums[slow] != nums[fast])
            {
                nums[slow + 1] = nums[fast];
                slow++;
            }

            fast++;
        }

        return slow + 1;
    }
};

🍈 2.4 Yanghui triangle

✈ Original title link: Yanghui triangle

This is a very typical topic of dynamic programming, and the idea is also very simple.

πŸŽ‰ Specific ideas:

  • Status: d p [ i ] [ j ] dp [ i ] [ j ] dp[i][j] is the number of positions
  • Initial state: when j = = 0 ∣ ∣ i = = j Time , d p [ i ] [ j ] = 1 When J = = 0 | I = = J, DP [i] [J] = 1 When j==0 ∣∣ i==j, dp[i][j]=1
  • State transition equation: d p [ i ] [ j ] = d p [ i βˆ’ 1 ] [ j βˆ’ 1 ] + d p [ i βˆ’ 1 ] [ j ] dp [i] [j] = dp [i - 1] [j - 1] + dp [i - 1] [ j ] dp[i][j]=dp[iβˆ’1][jβˆ’1]+dp[iβˆ’1][j].

πŸŽƒ Code implementation:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows, vector<int>(1, 1));
        for (int i = 0; i < numRows; ++i)
        {
            ret[i].resize(i + 1, 1);
        }

        for (int i = 2; i < numRows; ++i)
        {
            for (int j = 1; j < ret[i].size() - 1; ++j)
            {
                ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
            }
        }

        return ret;
    }
};

πŸ‰ 2.5 the number I that appears only once

✈ Original title link: A number that appears only once

First, we need to understand several properties of XOR operation:

  1. Commutative law: a βŠ• b = b βŠ• a , a βŠ• b βŠ• a = a βŠ• a βŠ• b a βŠ• b = b βŠ• a, a βŠ• b βŠ• a = a βŠ• a βŠ• b aβŠ•b=bβŠ•a,aβŠ•bβŠ•a=aβŠ•aβŠ•b
  2. Binding law: ( a βŠ• b ) βŠ• a = a βŠ• ( b βŠ• a ) (a βŠ• b) βŠ• a = a βŠ• (b βŠ• a) (aβŠ•b)βŠ•a=aβŠ•(bβŠ•a)
  3. Any number exclusive or with 0 is itself: a βŠ• 0 = 0 βŠ• a = a a βŠ• 0 = 0 βŠ• a = a aβŠ•0=0βŠ•a=a
  4. Any number exclusive or with itself is 0: a βŠ• a = 0 aβŠ•a=0 aβŠ•a=0

Secondly, the title clearly points out that only one number appears once and the other numbers appear twice. Therefore, according to the above nature, we can turn it into:

a 1 βŠ• a 1 βŠ• a 2 βŠ• a 2 βŠ• . . . βŠ• a k βŠ• a k + 1 βŠ• a k + 1 βŠ• . . . βŠ• a m βŠ• a m = 0 βŠ• a k = a k a_1 βŠ•a_1βŠ•a_2βŠ•a_2βŠ•...βŠ•a_kβŠ•a_{k+1}βŠ•a_{k+1}βŠ•...βŠ•a_mβŠ•a_m = 0βŠ•a_k=a_k a1β€‹βŠ•a1β€‹βŠ•a2β€‹βŠ•a2β€‹βŠ•...βŠ•akβ€‹βŠ•ak+1β€‹βŠ•ak+1β€‹βŠ•...βŠ•amβ€‹βŠ•am​=0βŠ•ak​=ak​

That is, directly XOR all the numbers in a given array, and the final number is the number that appears only once.

πŸŽƒ Code implementation:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int num = 0;
        for(auto i : nums)
            num ^= i;

        return num;
    }
};

🍊 2.6 number II that appears only once

✈ Original title link: The number II that appears only once

🧨 Traversal method: one

  • There is nothing to say about this method. Direct violent sorting and traverse to select the number that appears only once.

πŸŽƒ Code implementation:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if(nums.size() == 1)
            return nums[0];
        sort(nums.begin(), nums.end());
        int len = nums.size();

        if(nums[0] != nums[1])
        {
            return nums[0];
        }

        if(nums[len - 1] != nums[len - 2])
        {
            return nums[len - 1];
        }
        for(int i = 1; i < len - 1; ++i)
        {
            if(nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
                return nums[i];
        }

        return 0;
    }
};

Time complexity O ( n βˆ— l o g 2 n ) O(n*log_2n) O(n * log2 n), spatial complexity O ( 1 ) O(1) O(1) .

🧨 Method 2: hash table

  • Traverse the array, use the hash table to count the number of occurrences of the number in the array, and finally find the number that appears only once.

πŸŽƒ Code implementation:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> harsh;
        for (int e: nums) {
            ++harsh[e];
        }
        int ret = 0;
        for (auto [num, cnt]: harsh) {
            if (cnt == 1) {
                ret = num;
                break;
            }
        }
        return ret;
    }
};

Time complexity O ( n ) O(n) O(n), spatial complexity O ( n ) O(n) O(n) .

🧨 Method 3: Statistics of binary digits

  • Establish an array to count how many times 1 appears on each bit of the binary of all numbers.
  • Because all the numbers except one appear three times, the sum of the times that each binary bit of the other numbers is 1 must be divided by 3.
  • Therefore, we only need to count the bits in the binary bit that cannot be divided by 3, and the number composed of these bits is the number that only appears once.

πŸŽƒ Code implementation:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int cnt[32] = { 0 };
        int ret = 0;
		
        // Count the number of all binary numbers as 1
        for (int i = 0; i < 32; ++i)
        {
            for (auto e : nums)
            {
                if ((e >> i) & 1 == 1)
                {
                    cnt[i]++;
                }
            }
        }
		// The result is to wait for bits or that cannot be divided by 3
        for (int i = 0; i < 32; ++i)
        {
            if ((cnt[i] % 3))
                ret |= 1 << i;
        }

        return ret;
    }
};

Time complexity O ( n ) O(n) O(n), spatial complexity O ( 1 ) O(1) O(1) .

πŸ‹ 2.7 number III that appears only once

✈ Original title link: Number III that appears only once

✨ Method 1: sorting + traversal

  • Sort directly, and then traverse to select the number that appears only once.

πŸŽƒ Code implementation:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
		
        int len = nums.size();
        vector<int> ret;
        // Special case: judge the first element and the second element
        if(nums[0] != nums[1])
        {
            ret.push_back(nums[0]);
        }
		// Special case: judge the last element and the penultimate element
        if(nums[len - 1] != nums[len - 2])
        {
            ret.push_back(nums[len - 1]);
        }

        if(ret.size() == 2)
            return ret;
		// General judgment: judge other elements in the array
        for(int i = 1; i < len - 1; ++i)
        {
            if(nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
                ret.push_back(nums[i]);
        }

        return ret;
    }
};

Time complexity O ( n βˆ— l o g 2 n ) O(n*log_2n) O(n * log2 n), spatial complexity O ( 1 ) O(1) O(1) .

✨ Method 2: hash table

  • Violence hash, directly count the number of occurrences of each number, and finally select the number that appears only once.

πŸŽƒ Code implementation:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num: nums) {
            ++freq[num];
        }
        vector<int> ans;
        for (const auto& [num, occ]: freq) {
            if (occ == 1) {
                ans.push_back(num);
            }
        }
        return ans;
    }
};

✨ Method 3: binary XOR method

πŸŽ‰ Specific ideas:

  • First, we need to understand several properties of XOR operation:
  1. Commutative law: a βŠ• b = b βŠ• a , a βŠ• b βŠ• a = a βŠ• a βŠ• b a βŠ• b = b βŠ• a, a βŠ• b βŠ• a = a βŠ• a βŠ• b aβŠ•b=bβŠ•a,aβŠ•bβŠ•a=aβŠ•aβŠ•b
  2. Binding law: ( a βŠ• b ) βŠ• a = a βŠ• ( b βŠ• a ) (a βŠ• b) βŠ• a = a βŠ• (b βŠ• a) (aβŠ•b)βŠ•a=aβŠ•(bβŠ•a)
  3. Any number exclusive or with 0 is itself: a βŠ• 0 = 0 βŠ• a = a a βŠ• 0 = 0 βŠ• a = a aβŠ•0=0βŠ•a=a
  4. Any number exclusive or with itself is 0: a βŠ• a = 0 aβŠ•a=0 aβŠ•a=0

Secondly, it is clearly pointed out in the title that only two figures appear once, and the other figures appear twice. Therefore, according to the above nature, we can turn them into:

a 1 βŠ• a 1 βŠ• a 2 βŠ• a 2 βŠ• . . . βŠ• a k βŠ• a k + 1 βŠ• a k + 1 . . . βŠ• a n βŠ• a n + 1 βŠ• a n + 1 βŠ• . . . βŠ• a m βŠ• a m = a k βŠ• a n a_1 βŠ•a_1βŠ•a_2βŠ•a_2βŠ•...βŠ•a_kβŠ•a_{k+1}βŠ•a_{k+1}...βŠ•a_nβŠ•a_{n+1}βŠ•a_{n+1}βŠ•...βŠ•a_mβŠ•a_m = a_kβŠ•a_n a1β€‹βŠ•a1β€‹βŠ•a2β€‹βŠ•a2β€‹βŠ•...βŠ•akβ€‹βŠ•ak+1β€‹βŠ•ak+1​...βŠ•anβ€‹βŠ•an+1β€‹βŠ•an+1β€‹βŠ•...βŠ•amβ€‹βŠ•am​=akβ€‹βŠ•an​

Finally, we get the XOR values of two numbers that only appear once. According to the definition of XOR, the numbers on the binary bits of the two numbers are different, and the result on the different bits is 1, eg. 1000 ⊕ 1110 = 0110. We can get that the second and third bits of the two numbers are different from right to left.

  • When we get the different binary bits of the target number, we can group the array according to the order. After grouping, there is only one single number left in each group.
  • Select the number I twice.

πŸŽƒ Code implementation:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int num = 0;
        int len = nums.size();
        vector<int> ret;
		// XOR all numbers together
        for(auto e : nums)
        {
            num ^= e;
        }

        int i = 0;
        // Find out the binary bits of two different numbers
        for(i = 0; i < 32; ++i)
        {
            if((num >> i) & 1 == 1)
                break;
        }
		
        // Group according to different binary bits for XOR, and finally get two results directly
        int ret1 = 0, ret2 = 0;
        for(auto e : nums)
        {
            if((e >> i) & 1 == 1)            
                ret1 ^= e;            
            else
                ret2 ^= e;
        }

        ret.push_back(ret1);
        ret.push_back(ret2);

        return ret;
    }
};

Time complexity O ( n ) O(n) O(n), spatial complexity O ( 1 ) O(1) O(1) .

🍌 2.8 letter combination of telephone number

✈ Original title link: Letter combination of telephone number

πŸŽ‰ Specific ideas:

This is a very classic backtracking algorithm problem, and the idea is actually very simple:

  1. Traverse the number string given by the topic and find the corresponding letter string according to the number.
  2. Add characters after the current in the order of traversed elements until the traversal is completed.
  3. When traversing the numeric string given by the title, save the string obtained at this time.

πŸŽƒ Code implementation:

// Hash table for comparison
static string harsh[] = {"", "", "abc", "def", "ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"};
class Solution {
public:
    void Dfs(string& digits, int index, string curStr, vector<string>& ret)
    {
        // When the length of the current string is equal to digits, if the current string is not empty, insert it
        if(curStr.size() == digits.size())
        {
            if(!curStr.empty())
                ret.push_back(curStr);
            return;
        }
        // Find the number corresponding to the current digits
        int curInd = digits[index] - '0';
        // Traverse the corresponding string in this hash table
        for(auto& ch: harsh[curInd])
        {
            // Try each result. The index is the subscript of digits, and add one at a time
            // Each time you add the current corresponding hash table character after the current string, try all possibilities
            Dfs(digits, index + 1, curStr + ch, ret);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        Dfs(digits, 0, "", ret);
        return ret;
    }
};

🍍 2.9 maximum sum of continuous subarrays

✈ Original title link: Maximum sum of continuous subarrays

This problem is a classic dynamic programming problem. Some students may do it directly with greed + backtracking at the first glance, but if this problem uses greedy algorithm, in some cases, the overall optimal result will not be obtained.

πŸŽ‰ Specific ideas:

This is a classic dynamic programming problem:

  • Status: f ( x ) f(x) f(x) - from the continuous maximum sum of the previous section to the maximum sum of x position

  • State transition equation: f ( x ) = m a x ( f ( x βˆ’ 1 ) + a [ x ] , a [ x ] ) f(x)=max(f(x-1) + a[x], a[x]) f(x)=max(f(x − 1)+a[x],a[x]) - if the sum of the continuous maximum sum of the previous segment and the current number is greater than the current number, take the sum of the continuous maximum sum of the previous segment and the current number, otherwise, take the current number (equivalent to if the maximum value of the sum of the previous continuous string and the sum of the current number are not as good as the current number, it is better to restart a continuous substring from this position, otherwise continue the previous continuous string)

  • Initial value: f ( 0 ) = a [ 0 ] f(0) = a[0] f(0)=a[0] - substring starting from a[0]

  • Result: from f ( 0 ) βˆ’ f ( n βˆ’ 1 ) f(0) - f(n-1) Select the maximum value from f(0) − f(n − 1). Because the continuous string is uncertain, we should make a final judgment.

  • example: βˆ’ 2 , 1 , βˆ’ 3 , 4 , βˆ’ 1 , 2 , 1 , βˆ’ 5 -2 ,1,-3,4,-1,2,1,-5 βˆ’2,1,βˆ’3,4,βˆ’1,2,1,βˆ’5

  • Serial number01234567
    a [ x ] a[x] a[x]-21-34-121-5
    f ( x ) f(x) f(x)-21-243561

Let's summarize the idea of continuous string vividly:

It is equivalent to you have a large family. If your family's assets are very rich and your assets add up to more than your original assets (you may owe money), you choose to inherit the family property; But if your family is in a bad situation and your family owes money, you can choose to go out and work alone. Don't be implicated by the family. You start to establish a new family again. Your children and grandchildren follow your example and continue the above process.

Finally, your descendants read the genealogy to find the era of the widest instrument in their ancestors, so they compare the assets of generations to get the assets of the widest generation in their ancestors.

πŸŽƒ Code implementation:

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int num = array[0], Max = array[0];
        
        for(int i = 1; i < array.size(); ++i)
        {
            num = max(array[i] + num, array[i]);
            Max = num > Max ? num : Max;
        }
        return Max;
    }
};

πŸ₯­ 2.10 minimum stack

✈ Original title link: Minimum stack

Since this problem requires to find the minimum value in linear time, we can exchange space for time.

πŸŽ‰ Specific ideas:

  • Preset two stacks, one to store the normally entered value -_ st, another dedicated storage minimum -_ min.
  • Stack:
    • The stack value is directly stored in the_ stοΌ›
    • _ When the st stack is empty, it is put into the stack at the same time_ minοΌ›
    • When stacking later, and_ Compare the stack top elements of min, if the value in the stack is less than or equal to_ Min is the top element of the stack_ min.

  • Out of stack:
    • When out of the stack, if_ The stack element of st is equal to_ min, then both stacks are out of the stack;
    • If_ The stack element of st is not equal to_ min stack top element, only_ st stack.

πŸŽƒ Code implementation:

class MinStack {
public:
    MinStack() {}

    void push(int val) {
        _st.push(val);
        if (_min.empty() || val <= _min.top())
        {
            _min.push(val);
        }
    }

    void pop() {
        if (_min.top() == _st.top())
        {
            _min.pop();
        }
        _st.pop();
    }

    int top() {
        return _st.top();
    }

    int getMin() {
        return _min.top();
    }
private:
    stack<int> _st;
    stack<int> _min;
};

🍎 2.11 stack push in and pop-up sequence

✈ Original title link: Push in and pop-up sequence of stack

The main idea of this problem is simulation.

πŸŽ‰ Specific ideas:

  • Directly simulate the process of entering and leaving the stack.
  • Enter the stack in sequence according to the given stack entry order. When the input element is the same as the first element of the stack exit sequence, start the stack exit, point to the next element of the stack exit sequence, and cycle this process until the top element of the stack is different from the element of the stack exit sequence or the stack is empty.
  • Loop through the above process until the stack sequence is traversed.
  • At this moment, if there are no elements in the stack, the given sequence of the title is correct. On the contrary, it is incorrect.

πŸŽƒ Code implementation:

class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        stack<int> st;
        int i = 0, j = 0;
        // Loop through the following process until the stack sequence is traversed
        while (i < pushV.size())
        {
            st.push(pushV[i++]);
            // When the top element of the stack is equal to the out of stack sequence, the out of stack starts
            while (!st.empty() && st.top() == popV[j])
            {
                st.pop();
                j++;
            }
        }

        return st.empty();
    }
};

🍏 2.12 evaluation of inverse Polish expression

✈ Original title link: Evaluation of inverse Polish expression

The inverse Polish expression was proposed by lukaswicz, a Polish logician. The characteristic of inverse Polish expression is that there are no parentheses and the operator is always placed after its associated operand. Therefore, the inverse Polish expression is also called suffix expression.

πŸŽ‰ Specific ideas:
The inverse Polish expression strictly follows the operation of "left to right". When calculating the value of the inverse Polish expression, use a stack to store operands, traverse the inverse Polish expression from left to right, and perform the following operations:

  • If an operand is encountered, the operand is put on the stack;

  • If an operator is encountered, the two operands will be out of the stack. The right operand will be out of the stack first, and the left operand will be out of the stack later. Use the operator to operate the two operands and put the new operand obtained by the operation into the stack.

  • After traversing the whole inverse Polish expression, there is only one element in the stack, which is the value of the inverse Polish expression.

The above idea comes from the official

πŸŽƒ Code implementation:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (const auto& str : tokens)
        {
            if (str == "+" || str == "-" || str == "*" || str == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch (str[0])
                {
                case '+':
                    st.push(left + right);
                    break;
                case '-':
                    st.push(left - right);
                    break;
                case '*':
                    st.push(left * right);
                    break;
                case '/':
                    st.push(left / right);
                    break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

🍐 2.13 the kth largest element in the array

✈ Original title link: The kth largest element in the array

πŸ• Method 1: sorting

Sort directly and select the k-th element with a time complexity of O ( n βˆ— l o g Β  n ) O(n*log~n) O(nβˆ—logΒ n).

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};

πŸ• Method 2: heap sorting

Using heap sorting, the time complexity is O ( n + k βˆ— l o g Β  n ) O(n+k*log~n) O(n+kβˆ—logΒ n)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end());
        for (int i = 1; i < k; ++i)
        {
            pq.pop();
        }
        return pq.top();
    }
};

πŸ• Method 3: TopK

TopK problem, directly establish a small stack of k elements, and use the solution of TopK. The time complexity is O ( n + n βˆ— l o g Β  k ) O(n + n*log~k) O(n+n * log k), this is the optimal solution of this problem.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);

        for (int i = k; i < nums.size(); ++i)
        {
            if (nums[i] > pq.top())
            {
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};

Students who have not learned about piles can read this article—— [data structure] full parsing of heap , which explains the heap sorting and TopK problems in detail.

βš” Postscript

Bai Chen wrote this article to help more C + + entry-level learners master the syntax of C + + faster, and can use C + + in practice. I hope you can gain something from this article.

If this article helps you, please support Bai Chen. Your support is the greatest encouragement to Bai Chen 😜.

If there is something wrong with the analysis, please correct it. I will modify it as soon as possible. Thank you for your tolerance.

If you like this series, please support it πŸ˜‹!

If this article helps you, please give me a thumb πŸ‘ And little stars ⭐ Support Bai Chen! If you like Bai Chen's [brush question diary] series, you might as well pay attention to it πŸ‘€ Bai Chen, in order to see the latest updates!!!

I'm Bai Chen who can't stay up late. I'll see you in the next article.

Tags: C C++ Algorithm data structure leetcode

Posted by carrot on Tue, 12 Apr 2022 05:18:24 +0300