2022-01-01 swipe questions and punch in every day (happy New Year's Day!!!)

Flying book - daily question

394. String decoding

Given an encoded string, returns its decoded string.

The coding rule is: k[encoded_string], indicating the encoded inside the square brackets_ String is repeated exactly k times. Note that K is guaranteed to be a positive integer.

You can think that the input string is always valid; There are no extra spaces in the input string, and the input square brackets always meet the format requirements.

In addition, you can think that the original data does not contain numbers, and all numbers only represent the number of repetitions k, for example, there will be no input like 3a or 2 [4].

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

This problem can be recursion or stack. I use stack to write. Prepare two stacks and a digital stack sta_num, a string stack sta_str, then prepare a string variable STR and integer num, and start traversing the string s. each time, judge whether s[i] is a numeric character. If yes, convert it into a numeric type and add it to num. if it is a letter, add it to str. when traversing the left parenthesis, it means that the repeated string is to be recorded. We store the number of repetitions num in the stack sta_ In num, save the previously traversed string STR and store it in the string stack sta_str, and then clear num and STR to record the next data. Before encountering the right bracket, the operation is the same as above. When encountering the right bracket, we follow sta_ Stack top element of num, repeat sta_num.top() the current string STR times. After repetition, the top element of the stack is removed from the stack, and the current STR is connected to the top element of the string stack. Repeat the operation, and finally return str.

class Solution {
public:
    string decodeString(string s) {
    stack<int>sta_num;
    stack<string>sta_str;
    string str;
    int num = 0;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
            num = num * 10 + s[i] - '0';
        else if (s[i] == '[')
        {
            sta_num.push(num);
            num = 0;
            sta_str.push(str);
            str.clear();
        }
        else if (s[i] == ']')
        {
            string tmp = str;
            for (int j = 1; j < sta_num.top(); j++)
                str += tmp;
            sta_num.pop();
            str = sta_str.top() + str;
            sta_str.pop();
        }
        else
        {
            str += s[i];
        }
    }
    return str;
}
};

Force deduction - one question per day

2022. Convert one-dimensional array to two-dimensional array

Give you an array of one-dimensional integers with subscripts starting from 0, original and two integers m and n. You need to use all the elements in original to create a two-dimensional array of M rows and N columns.

In original, elements with subscripts from 0 to N - 1 (both included) constitute the first row of the two-dimensional array, elements with subscripts from n to 2 * n - 1 (both included) constitute the second row of the two-dimensional array, and so on.

Please return a two-dimensional array of m x n according to the above process. If such a two-dimensional array cannot be formed, please return an empty two-dimensional array.

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2], [3,4]]
Explanation:
The constructed two-dimensional array should contain 2 rows and 2 columns.
The first n=2 part of the original is [1,2], which constitutes the first row of the two-dimensional array.
The second n=2 part of the original is [3,4], which forms the second row of the two-dimensional array.

First judge whether the elements of a one-dimensional array are equal to m*n. if not, return an empty two-dimensional array. If they are equal, open up the space of M rows and N columns for the two-dimensional array, and then assign the values of the one-dimensional array one by one with the for loop.

class Solution {
public:
    vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
        int num=original.size();
        vector<vector<int>>v;
        if(num!=m*n)return v;
        v.resize(m,vector<int>(n));
        int l=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                v[i][j]=original[l++];
        return v;
    }
};

You can also use a fast for loop, which is faster.

class Solution {
public:
    vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
        int num=original.size();
        vector<vector<int>>v;
        if(num!=m*n)return v;
        v.resize(m,vector<int>(n));
        int k=0,j=0;
        for(auto i:original)
            if(j<n)
                v[k][j++]=i;
            else
            {
                j=0;
                v[++k][j++]=i;
            }
        return v;
    }
};

912. Sort array

Give you an integer array nums, please arrange the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output:[1,2,3,5]

Quick sort.

class Solution {
public:
    void quick_sort(vector<int>&nums,int l,int r)
    {
        if(l>=r)return;
        int x=nums[(l+r)/2],i=l-1,j=r+1;
        while(i<j)
        {
            do i++;while(nums[i]<x);
            do j--;while(nums[j]>x);
            if(i<j)swap(nums[i],nums[j]);
        }
        quick_sort(nums,l,j);
        quick_sort(nums,j+1,r);
    }
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums,0,nums.size()-1);
        return nums;
    }
};

169. Most elements

Given an array of size n, find most of its elements. Most elements refer to elements that appear more than ⌊ n/2 ⌋ in the array.

You can assume that the array is non empty and that there are always many elements in a given array.

Example 1:

Input: [3,2,3]
Output: 3

Advanced:

• This paper attempts to design an algorithm with time complexity O(n) and space complexity O(1) to solve this problem.

This problem can record the occurrence times of each element with a hash table, and then find the element with the largest number of times. The time complexity of this solution is O(n), and the space complexity is O(n).

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int>mymap;
        int ans=0,num=0;
        for(auto i:nums)
        {
            if(ans<++mymap[i])
            {
                ans=mymap[i];
                num=i;
            }
        }
        return num;
    }
};

However, the space complexity of advanced requires O(1), so we need to find a more operational solution. Here we learn a new knowledge point: Moore voting.

Moore's vote means this: if several countries fight with each other, each country has a part of its troops, and each soldier can exchange with the soldiers of another country. After the war, whichever country has soldiers left will win. At this time, if a country has more soldiers than the sum of the soldiers of all other countries, then the country is bound to win. Because even if several other countries join hands to deal with him, there will not be enough soldiers for him.

In this problem, countries are different numbers, and the number of soldiers is the number of these numbers. We can start with the first number, prepare a number to record the current winner num and a number to record the force ANS. Start traversing nums. If num and nums[i] are the same, the force is ans + +. If they are different, it means that they encounter the enemy. Ans –. When ans < 0, the new winner is nums[i]. Record it in num. in this way, the number that wins in the end must occupy more than half of the number. After traversing, return to num. The time complexity is O(n) and the space complexity is O(1).

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans=1,num=nums[0],n=nums.size();
        for(int i=1;i<n;i++)
        {
            if(num==nums[i])
                ans++;
            else if(--ans<0)
            {
                num=nums[i];
                ans=1;
            }
        }
        return num;
    }
};

378. The K-th smallest element in an ordered matrix

Give you an n x n matrix, in which the elements of each row and column are sorted in ascending order to find the k-smallest element in the matrix.
Note that it is the k-th smallest element after sorting, not the k-th different element.

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: the elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th small element is 13

The title says that each row and column are in ascending order, so we can integrate all rows by merging and sorting, and finally return the elements with subscript k-1.

class Solution {
public:
    void merge_sort(vector<int>&v,vector<int>&num)
    {
        int n=v.size(),m=num.size(),i=0,j=0;
        vector<int>arr;
        while(i<n&&j<m)
        {
            if(v[i]<num[j])arr.push_back(v[i++]);
            else arr.push_back(num[j++]);
        }
        while(i<n)arr.push_back(v[i++]);
        while(j<m)arr.push_back(num[j++]);
        v=arr;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        vector<int>v;
        v=matrix[0];
        int n=matrix.size();
        for(int i=1;i<n;i++)
            merge_sort(v,matrix[i]);
        return v[k-1];
    }
};