Leetcode brush the daily problem and the next problem of the daily problem note 11/30

Writing in the front

This is the 11th day of my participation in Gwen Challenge

About to graduate, only to find himself in the interview algorithm hanging hammer. There is no way to zero based identity and classmates to join the force buckle brush problem army. My classmates are very good, they are usually just modest, verbally said that they will not, and I really will not… Nuggets encourage new people to blog every day, I also join in a lively, record every day brush the first two questions, these two questions I do. I plan to brush five questions every day. For the other questions, I can only memorize the routine by force and will not post them in my blog.

I am really just a vegetable chicken, what do not want to solve the problem from my reference, coding habits also need to improve, if you want to find brush problem master ask questions, I think it is better to go to the palace water sanye brush problem diary this big guy. I try not to see the solution of the problem before I make it, so as not to collide with the content of the big guy.

In addition, I also hope to have the leisure of the big guy to provide some higher clear problem-solving ideas to me, welcome to discuss ha!

Okay, without further ado, let’s start the first two questions on the eleventh day!

2021.6.11 One question of the day

279. Perfect squares

This problem at first glance knows is the backpack problem of infinite items. And then the capacity is the current sum I, and the value is the least number of squares needed, dp[I], which add up to the current sum I. Because I is a sum of squares, none of the square root numbers that make up I is as big as the square root of I. SQRT {\texttt{I}}][0, I] = SQRT {\texttt{I}} [0, I] = SQRT {\texttt{I}} [0, I] Let’s say I picked j, and then I just have to figure out dp[i-j * j]. And then we can write the transition equation.


dp [ i ] = 1 + m i n j = 1 ⌊ i ⌋ dp [ i – j 2 ] \texttt{dp}[\texttt{i}] = 1 + \mathop{min}\limits_{\texttt{j} = 1}^{\lfloor \sqrt{\texttt{i}} \rfloor} \texttt{dp}[\texttt{i} – \texttt{j}^2] 

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                minn = min(minn, dp[i - j * j]);
            }
            dp[i] = minn + 1;
        }
        returndp[n]; }};Copy the code

In fact, the sum of things generally have a mathematical formula, as long as you know, the mathematical formula is always faster than other problem-solving routines. This is a theorem that I didn’t know until I looked at the solution called the sum of four squares theorem.

The sum of four squares theorem proves that any positive integer can be represented as the sum of squares of up to four positive integers. This gives us an upper bound on the answer to this problem.

At the same time, the four-square-sum theorem contains a stronger conclusion: NNN can be expressed as the sum of squares of up to three positive integers if and only if n≠4k×(8m+7)n \neq 4^k \times (8m+7)n =4k×(8m+7). Therefore, when n=4k×(8m+7)n =4 ^k \times (8m+7)n=4k×(8m+7), NNN can only be expressed as the sum of squares of four positive integers. Now we can just go back to 444.

If n≠4k×(8m+7)n \neq 4^k \times (8m+7)n=4k×(8m+7), we need to determine how many perfect squares can represent NNN. We know that the answer will only be one of 1,2,31, 2,3:

If the answer is 111, then NNN must be a perfect square, which is easy to tell;

If the answer is 222, then n=a2+b2n=a^2+b^2n=a2+b2, we simply enumerate all a(1≤a≤n)a(1 \leq a \leq SQRT {n})a(1≤a≤n), Check whether n−a2n – a^2n−a2 is a perfect square.

At 333, it is difficult to solve it in a good time complexity, but we only need to check the two cases where the answer is 111 or 222 to determine the answer by elimination.

This is the idea of the official problem solution, this idea is generally used to solve algorithm problems are dimensionality reduction strike type, the code logic will be much simpler, the premise is that you know that this can be used to calculate the formula, and the scope of application includes the scope given by the problem.

The code is not posted, let me try this solution time and space ranking.

Dimension reduction strikes terror like this.

Then in the comment area found a brother’s violent solution, this solution can be put into the single-chip operation.

Code:


class Solution {
public:
    int numSquares(int n) {
        vector<int> dp={0.1.2.3.1.2.3.4.2.1.2.3.3.2.3.4.1.2.2.3.2.3.3.4.3.1.2.3.4.2.3.4.2.3.2.3.1.2.3.4.2.2.3.3.3.2.3.4.3.1.2.3.2.2.3.4.3.3.2.3.4.2.3.4.1.2.3.3.2.3.3.4.2.2.2.3.3.3.3.4.2.1.2.3.3.2.3.4.3.2.2.3.4.3.3.4.3.2.2.3.1.2.3.4.2.3.2.3.3.2.3.4.4.2.3.3.2.2.3.4.3.1.2.3.4.2.3.4.2.3.2.3.3.3.3.4.2.2.3.3.3.3.3.4.1.2.2.3.2.2.3.4.3.2.3.3.4.2.3.4.2.3.2.3.2.3.3.4.3.1.2.3.3.2.3.4.3.3.2.3.2.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.1.2.3.4.2.3.2.3.3.2.3.4.2.3.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.1.2.3.3.2.3.4.2.2.2.3.3.3.3.4.4.2.2.3.2.2.3.4.3.3.2.3.4.3.3.4.1.2.3.3.2.2.3.4.3.2.3.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.2.1.2.3.2.2.3.4.2.3.2.3.3.3.3.4.3.2.2.3.3.3.3.4.3.2.2.3.4.2.3.4.2.3.3.3.1.2.3.4.2.3.3.3.3.2.3.4.3.2.2.3.2.3.3.4.3.3.2.3.4.2.3.4.3.2.3.3.2.3.3.4.2.1.2.3.3.2.3.4.4.2.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.3.2.3.2.2.3.4.2.3.2.3.3.2.3.4.1.2.3.3.2.2.3.4.3.2.2.3.4.3.3.4.2.3.3.3.3.2.3.4.2.2.3.3.3.3.3.4.3.2.3.3.2.3.3.4.3.1.2.3.4.2.3.4.4.2.2.3.2.3.3.4.3.2.2.3.3.2.3.4.2.3.2.3.2.3.3.4.3.3.3.3.4.2.3.4.3.2.2.3.1.2.3.4.2.3.2.3.3.2.3.4.4.3.3.3.2.3.3.4.3.2.3.3.4.2.3.4.2.3.2.3.3.3.3.4.2.2.2.3.3.3.3.4.3.1.2.3.3.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.2.3.4.3.3.2.3.3.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.1.2.2.3.2.3.3.4.2.2.2.3.3.3.3.4.2.2.3.3.2.3.3.4.3.2.3.3.4.2.3.4.3.3.2.3.2.2.3.4.3.2.3.3.3.3.3.4.4.1.2.3.2.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.3.3.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.2.3.4.3.3.2.3.4.3.3.4.3.2.2.3.1.2.3.4.2.3.3.3.3.2.3.4.3.2.3.3.2.3.3.4.3.2.2.3.4.2.3.4.3.3.2.3.3.2.3.4.2.3.3.3.3.3.3.4.2.3.2.3.2.2.3.4.3.1.2.3.4.2.3.4.3.3.2.3.2.3.3.4.3.2.2.3.3.3.3.4.4.3.2.3.3.2.3.4.3.2.3.3.4.2.3.4.3.2.3.3.2.2.3.4.2.3.2.3.3.3.3.4.1.2.3.3.2.3.3.4.3.2.2.3.4.2.3.4.2.2.2.3.3.3.3.4.2.2.2.3.3.3.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.2.3.4.2.2.3.3.3.3.3.4.3.1.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.3.3.3.4.2.2.3.3.3.2.3.4.4.2.2.3.2.3.3.4.3.3.2.3.4.3.3.4.3.3.2.3.1.2.3.4.2.2.3.3.3.2.3.4.3.3.2.3.2.3.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.3.3.4.2.2.3.3.3.2.3.4.3.3.3.3.3.2.3.4.3.2.2.3.4.3.3.4.4.1.2.3.2.2.3.4.2.3.2.3.3.3.3.4.2.2.3.3.2.2.3.4.3.2.2.3.4.3.3.4.3.3.3.3.3.2.3.4.2.3.3.3.3.3.3.4.4.2.2.3.3.2.3.4.3.2.2.3.4.2.3.4.1.2.3.3.2.3.3.4.3.2.3.3.3.2.3.4.2.3.2.3.2.3.3.4.3.2.3.3.4.2.3.4.3.3.2.3.2.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.3.2.3.4.3.3.4.2.1.2.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.3.3.2.2.3.4.3.3.2.3.4.2.3.4.3.3.3.3.2.2.3.4.3.2.2.3.3.3.3.4.4.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.2.2.2.3.1.2.3.4.2.3.3.3.3.2.3.4.2.3.2.3.2.3.3.4.3.3.3.3.4.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.2.2.3.3.2.3.4.3.3.2.3.4.2.3.4.3.2.3.3.2.3.3.4.2.1.2.3.3.2.3.4.3.2.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.3.3.4.2.3.2.3.3.2.3.4.4.3.3.3.2.3.3.4.3.3.2.3.4.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.3.3.3.4.1.2.3.3.2.2.3.4.3.2.2.3.4.3.3.4.2.2.2.3.3.3.3.4.3.2.2.3.3.2.3.4.3.3.3.3.2.3.3.4.3.3.3.3.4.2.3.4.3.2.2.3.2.3.3.4.2.3.2.3.3.3.3.4.2.2.3.3.3.3.3.4.3.1.2.3.4.2.3.4.3.2.2.3.3.2.3.4.2.2.3.3.3.3.3.4.4.3.2.3.2.3.3.4.3.3.2.3.4.2.3.4.3.2.3.3.2.2.3.4.3.2.2.3.3.2.3.4.2.3.3.3.3.2.3.4.3.2.3.3.4.3.3.4.2.3.3.3.1.2.3.4.2.3.2.3.3.2.3.4.3.3.2.3.2.3.3.4.3.2.2.3.4.2.3.4.4.3.3.3.2.3.3.4.2.2.3.3.3.3.3.4.3.2.2.3.2.2.3.4.3.3.3.3.4.3.3.4.3.3.3.3.2.3.3.4.3.2.2.3.3.2.3.4.4.1.2.3.3.2.3.4.3.3.2.3.4.3.3.4.3.2.2.3.3.3.3.4.2.3.2.3.3.2.3.4.2.2.3.3.2.2.3.4.3.3.3.3.4.2.3.4.2.3.2.3.3.2.3.4.2.3.3.3.3.3.3.4.3.2.2.3.2.3.3.4.3.3.2.3.4.2.3.4.1.2.2.3.2.3.3.4.3.2.3.3.3.2.3.4.2.3.2.3.2.2.3.4.3.2.3.3.4.2.3.4.3.3.3.3.2.2.3.4.2.3.2.3.3.3.3.4.4.2.3.3.3.3.3.4.3.2.2.3.4.3.3.4.2.2.2.3.3.2.3.4.3.3.3.3.3.3.3.4.3.1.2.3.2.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.3.3.4.3.3.2.3.3.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.3.2.3.2.2.3.4.3.2.3.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.3.2.3.1.2.3.4.2.2.3.3.3.2.3.4.4.2.3.3.2.2.3.4.3.3.3.3.4.2.3.4.4.3.3.3.2.3.3.4.2.2.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.3.2.3.4.3.3.4.3.2.3.3.2.3.3.4.2.3.3.3.3.3.3.4.3.3.3.3.2.2.3.4.3.1.2.3.4.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.2.2.2.3.3.2.3.4.3.3.2.3.4.2.3.4.3.2.3.3.3.3.3.4.3.3.2.3.3.2.3.4.4.3.2.3.2.3.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.3.3.4.2.3.2.3.3.2.3.4.1.2.3.3.2.3.3.4.3.2.3.3.4.2.3.4.2.3.2.3.3.3.3.4.2.2.2.3.3.3.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.3.3.4.4.2.3.3.3.2.3.4.3.2.2.3.3.2.3.4.2.3.3.3.3.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.3.3.4.3.1.2.3.3.2.3.4.4.3.2.3.2.3.3.4.3.2.2.3.4.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.2.3.4.3.3.2.3.3.2.3.4.3.3.2.3.4.3.3.4.2.2.3.3.2.3.3.4.2.2.3.3.3.3.3.4.3.2.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.2.3.3.1.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.2.2.3.4.2.3.4.3.3.2.3.3.3.3.4.2.2.3.3.3.3.3.4.4.2.3.3.2.2.3.4.3.2.3.3.4.2.3.4.2.3.2.3.2.3.3.4.3.3.2.3.3.3.3.4.2.3.2.3.2.2.3.4.3.3.3.3.4.2.3.4.3.1.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.3.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.2.3.2.3.3.4.3.3.3.3.4.2.3.4.3.2.3.3.2.3.3.4.3.2.3.3.3.2.3.4.4.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.1.2.2.3.2.2.3.4.2.2.2.3.3.3.3.4.2.3.3.3.3.3.3.4.3.2.2.3.4.2.3.4.2.3.3.3.2.2.3.4.2.3.3.3.3.2.3.4.3.2.3.3.3.2.3.4.3.3.2.3.4.3.3.4.2.3.3.3.2.3.3.4.3.2.2.3.3.2.3.4.2.2.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.1.2.3.2.2.3.4.3.3.2.3.3.3.3.4.4.2.3.3.2.2.3.4.3.2.2.3.4.3.3.4.3.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.2.3.2.3.2.3.3.4.3.3.2.3.4.3.3.4.3.2.2.3.2.3.3.4.3.2.2.3.3.2.3.4.3.3.2.3.3.3.3.4.3.3.3.3.4.2.3.4.4.3.2.3.1.2.3.4.2.3.3.3.3.2.3.4.2.3.3.3.2.3.3.4.3.2.2.3.4.2.3.4.3.2.3.3.3.2.3.4.2.3.3.3.3.3.3.4.4.2.3.3.2.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.3.3.4.3.3.2.3.3.3.3.4.3.3.2.3.3.2.3.4.3.3.3.3.4.3.3.4.2.2.2.3.3.2.3.4.2.1.2.3.3.2.3.4.3.2.2.3.2.3.3.4.3.2.3.3.4.2.3.4.2.3.2.3.2.3.3.4.3.2.3.3.3.2.3.4.3.3.2.3.2.2.3.4.3.3.2.3.4.3.3.4.3.2.3.3.3.3.3.4.2.2.3.3.3.2.3.4.4.3.3.3.3.2.3.4.3.3.2.3.4.3.3.4.3.2.2.3.2.2.3.4.2.3.3.3.3.2.3.4.1.2.3.3.2.3.3.4.3.2.3.3.4.3.3.4.2.3.2.3.3.2.3.4.3.2.3.3.3.3.3.4.3.3.2.3.2.2.3.4.3.2.2.3.4.2.3.4.3.2.2.3.2.3.3.4.3.3.2.3.3.3.3.4.2.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.3.2.3.3.2.2.3.4.2.3.3.3.3.2.3.4.4.2.3.3.2.3.3.4.3.1.2.3.4.2.3.4.3.2.2.3.3.3.3.4.2.2.2.3.3.3.3.4.3.2.2.3.2.2.3.4.3.3.2.3.4.2.3.4.2.3.3.3.3.2.3.4.3.2.2.3.3.2.3.4.3.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.2.3.3.3.3.2.3.4.2.3.2.3.3.3.3.4.2.2.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.3.3.1.2.3.4.2.3.3.3.3.2.3.4.4.2.2.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.3.3.3.3.3.4.2.2.3.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.3.3.4.2.3.2.3.3.2.3.4.3.2.3.3.3.2.3.4.3.2.3.3.4.2.3.4.4.3.3.3.3.3.3.4.2.3.3.3.3.3.3.4.3.1.2.3.2.2.3.4.3.2.2.3.4.2.3.4.3.2.2.3.2.3.3.4.3.2.2.3.3.3.3.4.4.3.3.3.2.2.3.4.3.2.3.3.4.3.3.4.3.3.2.3.2.2.3.4.3.3.3.3.3.2.3.4.2.2.3.3.2.3.3.4.3.3.2.3.4.3.3.4.2.3.2.3.3.2.3.4.2.3.2.3.3.3.3.4.3.2.3.3.3.2.3.4.3.3.2.3.4.2.3.4.1.2.3.3.2.2.3.4.3.2.2.3.3.3.3.4.2.3.3.3.3.3.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.3.3.4.2.2.3.3.3.2.3.4.4.2.3.3.2.3.3.4.3.3.2.3.4.3.3.4.2.3.2.3.2.2.3.4.2.2.3.3.3.3.3.4.3.2.2.3.3.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.3.3.4.2.3.2.3.3.3.3.4.3.1.2.3.3.2.3.4.3.2.2.3.4.3.3.4.3.2.3.3.3.3.3.4.2.3.2.3.3.2.3.4.2.2.3.3.2.2.3.4.3.3.3.3.4.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.3.3.3.4.4.2.2.3.2.3.3.4.3.2.3.3.4.3.3.4.2.2.2.3.2.3.3.4.3.3.2.3.3.2.3.4.3.3.3.3.3.2.3.4.3.3.3.3.4.2.3.4.3.2.2.3.1.2.3.4.2.3.2.3.3.2.3.4.3.3.3.3.2.3.3.4.3.2.2.3.4.2.3.4.2.2.2.3.3.3.3.4.2.3.3.3.3.3.3.4.3.3.3.3.2.2.3.4.3.3.2.3.4.3.3.4.3.2.3.3.2.3.3.4.3.2.2.3.3.3.3.4.4.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.2.3.3.2.2.3.4.2.3.2.3.3.2.3.4.3.3.2.3.3.3.3.4.3.1.2.3.4.2.3.4.2.3.2.3.2.3.3.4.3.2.3.3.3.2.3.4.3.2.2.3.2.2.3.4.3.3.3.3.4.2.3.4.4.3.3.3.2.3.3.4.2.2.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.2.3.4.3.3.4.3.3.2.3.3.2.3.4.2.3.2.3.3.3.3.4.4.3.3.3.3.2.3.4.3.2.2.3.4.2.3.4.3.3.3.3.3.2.3.4.2.2.3.3.3.3.3.4.1.2.2.3.2.3.3.4.3.2.2.3.4.2.3.4.2.2.3.3.2.3.3.4.3.2.2.3.3.3.3.4.3.3.3.3.2.2.3.4.3.3.3.3.4.2.3.4.3.2.2.3.3.2.3.4.2.3.3.3.3.3.3.4.2.2.3.3.3.3.3.4.3.2.3.3.4.2.3.4.3.2.3.3.3.3.3.4.2.3.2.3.3.3.3.4.4.2.2.3.2.2.3.4.3.3.2.3.4.2.3.4.2.3.3.3.2.3.3.4.3.1.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.2.3.2.3.2.3.3.4.3.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.2.2.3.4.3.3.4.3.3.2.3.3.3.3.4.3.2.3.3.3.2.3.4.3.2.3.3.2.2.3.4.3.3.2.3.4.2.3.4.3.2.3.3.2.3.3.4.2.3.3.3.3.2.3.4.4.2.2.3.3.3.3.4.3.2.3.3.4.3.3.4.4.3.2.3.1.2.3.4.2.3.3.3.3.2.3.4.2.3.3.3.2.3.3.4.3.2.2.3.4.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.2.2.3.3.2.3.4.3.2.2.3.4.3.3.4.2.3.3.3.2.3.3.4.3.3.3.3.3.2.3.4.2.3.2.3.2.2.3.4.3.2.3.3.4.3.3.4.3.3.3.3.2.3.3.4.2.3.2.3.3.3.3.4.4.3.3.3.3.3.3.4.3.2.3.3.4.2.3.4.3.1.2.3.3.2.3.4.3.2.2.3.3.3.3.4.3.2.2.3.2.2.3.4.3.3.2.3.4.3.3.4.2.2.3.3.3.2.3.4.3.3.2.3.3.2.3.4.3.3.2.3.3.2.3.4.3.3.3.3.4.3.3.4.4.2.2.3.2.3.3.4.2.2.3.3.3.2.3.4.3.2.2.3.2.3.3.4.3.2.2.3.4.3.3.4.3.3.3.3.2.2.3.4.2.2.3.3.3.3.3.4.4.3.2.3.2.3.3.4.3.3.2.3.4.2.3.4.1.2.3.3.2.3.3.4.3.2.2.3.3.3.3.4.2.2.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.2.3.3.2.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.2.2.3.4.3.2.3.3.4.2.3.4.2.3.2.3.3.2.3.4.2.3.3.3.3.3.3.4.2.2.2.3.3.2.3.4.3.3.3.3.4.3.3.4.3.3.2.3.2.3.3.4.3.2.3.3.3.2.3.4.4.3.2.3.2.3.3.4.3.2.3.3.4.3.3.4.3.1.2.3.3.2.3.4.2.3.2.3.3.3.3.4.2.2.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.2.2.3.2.3.3.4.3.3.2.3.4.2.3.4.3.2.3.3.2.2.3.4.3.2.3.3.3.3.3.4.2.3.2.3.3.3.3.4.3.3.3.3.4.3.3.4.3.2.2.3.3.2.3.4.2.2.2.3.3.3.3.4.4.2.2.3.3.3.3.4.3.3.2.3.4.2.3.4.2.3.3.3.1.2.3.4.2.2.3.3.3.2.3.4.3.2.3.3.2.2.3.4.3.3.3.3.4.2.3.4.2.2.3.3.2.3.3.4.2.3.2.3.3.2.3.4.3.3.3.3.3.2.3.4.3.2.2.3.4.3.3.4.3.3.2.3.2.2.3.4.3.3.2.3.3.3.3.4.2.3.3.3.2.2.3.4.3.2.2.3.4.3.3.4.3.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.4.3.3.3.2.2.3.4.3.3.2.3.4.2.3.4.3.2.3.3.3.3.3.4.3.1.2.3.3.2.3.4.2.3.2.3.2.3.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.2.3.4.2.3.3.3.3.2.3.4.3.3.3.3.3.3.3.4.3.2.2.3.4.3.3.4.4.2.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.2.2.3.3.3.3.4.3.3.2.3.4.2.3.4.3.3.3.3.2.2.3.4.3.3.2.3.3.2.3.4.4.3.2.3.3.2.3.4.3.3.3.3.4.3.3.4.2.3.2.3.2.3.3.4.2.3.2.3.3.2.3.4.1.2.2.3.2.3.3.4.3.2.3.3.4.2.3.4.2.3.3.3.3.2.3.4.3.2.3.3.3.3.3.4.3.2.2.3.2.3.3.4.3.3.2.3.4.3.3.4.2.2.3.3.3.3.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.2.3.4.3.3.2.3.4.3.3.4.3.2.2.3.3.2.3.4.3.3.2.3.3.2.3.4.4.2.3.3.2.3.3.4.3.2.3.3.4.2.3.4.2.3.3.3.3.3.3.4.2.2.3.3.3.3.3.4.3.2.2.3.2.3.3.4.3.1.2.3.4.2.3.4.2.3.2.3.2.3.3.4.3.2.2.3.3.3.3.4.3.3.2.3.3.2.3.4.3.2.3.3.4.2.3.4.3.2.2.3.2.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.2.3.3.4.3.3.4.3.3.2.3.3.3.3.4.2.3.2.3.3.3.3.4.4.2.2.3.2.3.3.4.3.3.3.3.4.2.3.4.3.3.3.3.2.2.3.4.3.3.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.2.3.3.3.1.2.3.4.2.2.3.3.3.2.3.4.3.2.3.3.2.3.3.4.3.3.3.3.4.2.3.4.3.3.2.3.2.2.3.4.2.2.3.3.3.2.3.4.3.3.2.3.2.2.3.4.3.3.2.3.4.2.3.4.3.2.3.3.2.3.3.4.3.2.3.3.3.2.3.4.4.3.3.3.3.2.3.4.3.2.2.3.4.3.3.4.3.2.3.3.2.3.3.4.2.3.2.3.3.3.3.4.2.2.3.3.3.2.3.4.3.2.2.3.4.2.3.4.2.3.3.3.3.3.3.4.2.3.3.3.3.3.3.4.3.1.2.3.2.2.3.4.3.3.2.3.4.3.3.4.4.2.2.3.3.3.3.4.3.2.2.3.3.2.3.4.2.3.3.3.3.2.3.4.3.2.3.3.4.2.3.4.3.3.2.3.3.3.3.4.2.3.2.3.3.2.3.4.4.2.3.3.2.3.3.4.3.2.2.3.4.3.3.4.2.2.2.3.3.2.3.4.2.3.3.3.3.3.3.4.3.3.3.3.2.2.3.4.3.3.3.3.4.3.3.4.3.2.3.3.2.3.3.4.3.2.2.3.3.2.3.4.3.3.3.3.3.3.3.4.3.3.3.3.4.3.3.4.1.2.2.3.2.2.3.4.3.2.2.3.3.2.3.4.2.3.2.3.2.3.3.4.3.2.2.3.4.2.3.4.3.3.2.3.2.3.3.4.2.3.3.3.3.3.3.4.4.2.2.3.3.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.3.3.4.2.3.3.3.3.2.3.4.3.2.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.2.3.3.2.3.3.4.2.3.2.3.3.3.3.4.3.2.3.3.2.3.3.4.3.2.3.3.4.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.3.3.3.4.2.1.2.3.3.2.3.4.3.2.2.3.4.2.3.4.3.2.3.3.3.3.3.4.3.2.2.3.3.3.3.4.4.3.3.3.2.2.3.4.3.3.3.3.4.3.3.4.3.3.2.3.2.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.3.2.3.4.3.3.4.2.2.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.3.2.3.3.2.3.4.3.3.3.3.4.2.3.4.2.2.3.3.2.2.3.4.3.2.2.3.3.3.3.4.3.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.3.2.3.3.1.2.3.4.2.3.2.3.3.2.3.4.4.3.2.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.2.3.2.3.3.4.2.2.3.3.3.2.3.4.3.2.3.3.2.2.3.4.3.3.3.3.4.3.3.4.2.2.3.3.2.3.3.4.3.2.3.3.3.3.3.4.3.2.2.3.3.2.3.4.3.3.3.3.4.3.3.4.4.2.2.3.3.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.3.2.3.4.2.3.4.3.3.2.3.3.3.3.4.2.3.3.3.3.3.3.4.4.2.2.3.2.3.3.4.3.1.2.3.4.2.3.4.3.3.2.3.2.3.3.4.3.2.3.3.3.2.3.4.2.3.2.3.2.2.3.4.3.2.3.3.4.2.3.4.3.3.2.3.2.2.3.4.2.3.2.3.3.3.3.4.3.3.3.3.2.3.3.4.3.2.2.3.4.2.3.4.2.3.3.3.3.2.3.4.3.3.2.3.3.3.3.4.3.2.2.3.2.2.3.4.3.3.2.3.4.2.3.4.3.2.3.3.2.2.3.4.3.2.3.3.3.2.3.4.4.3.2.3.3.2.3.4.3.3.3.3.4.3.3.4.2.3.3.3.3.2.3.4.3.2.2.3.3.3.3.4.1.2.3.3.2.3.3.4.3.2.3.3.4.3.3.4.2.3.2.3.3.3.3.4.2.2.3.3.3.3.3.4.3.2.3.3.2.2.3.4.3.3.2.3.4.2.3.4.3.2.3.3.3.3.3.4.2.3.2.3.3.2.3.4.2.3.3.3.3.3.3.4.3.2.2.3.4.3.3.4.3.2.2.3.2.2.3.4.2.3.3.3.3.2.3.4.4.3.3.3.2.2.3.4.3.2.2.3.4.3.3.4.4.3.3.3.3.3.3.4.3.2.3.3.3.3.3.4.2.2.2.3.3.3.3.4.3.2.2.3.4.2.3.4.2.3.3.3.2.3.3.4.3.1.2.3.3.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.4.2.3.4.3.2.2.3.2.3.3.4.2.3.3.3.3.2.3.4.2.3.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.2.3.3.2.3.4.3.2.2.3.3.3.3.4.4.2.2.3.3.2.3.4.3.3.2.3.4.3.3.4.3.3.3.3.3.3.3.4.3.2.3.3.3.2.3.4.2.3.3.3.3.2.3.4.3.3.3.3.4.3.3.4.3.3.2.3.2.2.3.4.2.2.2.3.3.3.3.4.3.2.2.3.2.3.3.4.3.2.2.3.4.3.3.4.4.3.2.3.1.2.3.4.2.2.3.3.3.2.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.2.3.4.3.2.3.3.3.3.3.4.2.2.2.3.3.2.3.4.4.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.2.3.3.2.3.3.4.2.3.2.3.3.3.3.4.3.2.3.3.3.2.3.4.3.3.2.3.4.2.3.4.2.3.2.3.3.3.3.4.2.2.3.3.3.3.3.4.3.3.3.3.2.2.3.4.3.2.3.3.4.2.3.4.2.3.3.3.2.3.3.4.3.2.2.3.3.2.3.4.2.3.3.3.2.2.3.4.3.3.3.3.4.3.3.4.3.1.2.3.3.2.3.4.3.3.2.3.3.2.3.4.4.2.3.3.2.3.3.4.3.3.2.3.4.2.3.4.2.2.2.3.3.2.3.4.2.3.2.3.3.3.3.4.3.3.2.3.2.3.3.4.3.3.3.3.4.2.3.4.2.2.3.3.3.2.3.4.3.3.3.3.3.2.3.4.3.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.2.3.4.2.3.3.3.3.3.3.4.2.2.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.3.2.3.3.2.3.4.2.3.3.3.3.2.3.4.4.2.3.3.2.2.3.4.3.3.3.3.4.2.3.4.1.2.3.3.2.3.3.4.2.2.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.3.2.3.2.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.3.2.3.4.3.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.2.2.3.3.2.2.3.4.3.3.3.3.4.3.3.4.3.2.2.3.2.3.3.4.3.2.2.3.3.3.3.4.4.3.2.3.2.3.3.4.3.2.3.3.4.2.3.4.3.2.2.3.3.3.3.4.3.3.3.3.3.3.3.4.2.3.3.3.2.3.3.4.3.2.2.3.4.3.3.4.2.1.2.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.3.3.3.2.3.4.3.3.2.3.4.3.3.4.4.3.3.3.2.2.3.4.3.3.2.3.3.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.3.3.4.2.3.3.3.3.2.3.4.4.2.2.3.3.3.3.4.3.2.3.3.4.2.3.4.2.3.2.3.2.2.3.4.2.3.3.3.3.3.3.4.3.2.3.3.2.3.3.4.3.3.2.3.4.3.3.4.3.2.3.3.3.3.3.4.3.2.2.3.3.2.3.4.3.2.3.3.3.2.3.4.3.2.2.3.4.3.3.4.3.3.2.3.1.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.3.3.3.2.3.4.2.2.3.3.3.3.3.4.4.3.2.3.2.2.3.4.3.3.2.3.4.2.3.4.2.3.2.3.2.3.3.4.3.2.3.3.3.3.3.4.2.3.3.3.3.2.3.4.3.3.3.3.4.2.3.4.3.2.3.3.3.3.3.4.2.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.2.3.3.4.2.3.4.3.2.2.3.3.3.3.4.2.2.3.3.3.3.3.4.3.2.2.3.2.2.3.4.3.3.3.3.4.2.3.4.3.3.3.3.2.2.3.4.3.1.2.3.3.2.3.4.4.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.3.3.2.3.3.2.3.4.2.2.2.3.3.2.3.4.2.2.3.3.2.3.3.4.3.3.2.3.4.3.3.4.3.3.3.3.2.2.3.4.3.2.3.3.3.2.3.4.3.2.2.3.2.3.3.4.3.3.2.3.4.3.3.4.2.2.3.3.2.3.3.4.2.3.3.3.3.2.3.4.3.3.2.3.3.2.3.4.3.2.2.3.4.3.3.4.3.3.2.3.2.2.3.4.2.3.2.3.3.3.3.4.4.2.3.3.3.3.3.4.3.2.2.3.4.3.3.4.3.3.3.3.3.2.3.4.2.3.3.3.3.3.3.4.1.2.2.3.2.3.3.4.3.2.2.3.4.2.3.4.2.3.3.3.2.3.3.4.3.2.2.3.3.2.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.3.3.4.4.2.3.3.2.2.3.4.3.3.2.3.3.3.3.4.2.2.3.3.2.3.3.4.3.2.3.3.4.3.3.4.3.2.3.3.3.2.3.4.3.2.2.3.3.3.3.4.4.3.2.3.2.2.3.4.3.3.2.3.4.2.3.4.4.3.3.3.3.2.3.4.3.2.2.3.3.3.3.4.2.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.2.3.2.3.2.3.3.4.2.2.3.3.3.2.3.4.3.3.2.3.2.3.3.4.3.1.2.3.4.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.2.3.4.3.2.3.3.3.3.3.4.2.3.2.3.3.3.3.4.4.2.3.3.3.3.3.4.3.2.2.3.4.3.3.4.3.2.2.3.2.2.3.4.3.3.2.3.3.2.3.4.2.3.3.3.3.3.3.4.3.2.3.3.4.2.3.4.2.3.2.3.3.2.3.4.3.3.3.3.3.3.3.4.3.2.2.3.3.2.3.4.3.3.2.3.4.3.3.4.3.2.2.3.3.3.3.4.3.2.3.3.3.2.3.4.2.3.3.3.2.2.3.4.3.3.3.3.4.2.3.4.3.2.2.3.1.2.3.4.2.3.2.3.3.2.3.4.4.3.3.3.2.3.3.4.3.2.2.3.4.2.3.4.2.3.3.3.3.3.3.4.2.2.3.3.3.3.3.4.3.3.2.3.2.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.2.3.4.3.2.2.3.3.3.3.4.3.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.2.2.3.3.2.3.3.4.2.2.3.3.3.2.3.4.3.3.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.2.3.3.3.3.4.2.2.3.3.3.3.3.4.4.2.2.3.2.2.3.4.3.3.3.3.4.2.3.4.3.3.3.3.2.3.3.4.3.2.3.3.3.2.3.4.3.1.2.3.3.2.3.4.3.2.2.3.4.3.3.4.3.2.2.3.3.2.3.4.2.3.2.3.3.3.3.4.3.3.3.3.2.2.3.4.3.3.2.3.4.3.3.4.4.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.2.2.3.3.3.3.3.4.3.3.2.3.4.3.3.4.3.2.2.3.2.3.3.4.3.3.3.3.3.3.3.4.4.3.2.3.3.2.3.4.3.2.3.3.4.2.3.4.3.2.3.3.2.2.3.4.2.3.2.3.3.2.3.4.2.3.3.3.3.3.3.4.3.3.2.3.4.2.3.4.2.2.3.3.3.2.3.4.2.3.3.3.3.3.3.4.3.3.2.3.2.3.3.4.3.3.2.3.4.2.3.4.1.2.3.3.2.3.3.4.3.2.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.3.3.4.3.3.2.3.2.3.3.4.3.2.2.3.3.2.3.4.4.2.2.3.2.3.3.4.3.2.3.3.4.3.3.4.2.3.3.3.3.2.3.4.2.2.3.3.3.3.3.4.3.2.3.3.3.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.3.3.4.2.3.2.3.3.2.3.4.3.2.2.3.3.3.3.4.3.2.3.3.4.3.3.4.3.2.3.3.3.2.3.4.2.3.3.3.3.3.3.4.2.3.3.3.2.2.3.4.3.2.3.3.4.2.3.4.3.3.3.3.3.3.3.4.3.2.3.3.3.3.3.4.4.1.2.3.3.2.3.4.3.2.2.3.4.2.3.4.4.2.2.3.2.3.3.4.3.3.2.3.3.2.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.3.3.4.3.2.2.3.2.3.3.4.2.3.2.3.3.3.3.4.3.2.3.3.2.3.3.4.3.2.3.3.4.3.3.4.2.3.2.3.3.2.3.4.3.2.2.3.3.3.3.4.3.2.3.3.2.2.3.4.3.3.2.3.4.3.3.4.3.2.3.3.2.3.3.4.3.3.2.3.3.2.3.4.4.3.3.3.3.2.3.4.3.3.3.3.4.3.3.4.3.2.2.3.2.2.3.4.2.3.3.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.2.3.4.2.3.4.3.3.2.3.1.2.3.4.2.2.3.3.3.2.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.2.3.4.4.3.3.3.3.3.3.4.2.3.2.3.3.3.3.4.2.2.2.3.3.2.3.4.3.3.3.3.4.3.3.4.3.2.3.3.2.3.3.4.2.3.3.3.3.3.3.4.4.2.3.3.2.2.3.4.3.2.2.3.4.3.3.4.2.3.2.3.3.3.3.4.2.3.3.3.3.3.3.4.3.2.2.3.2.3.3.4.3.3.3.3.4.2.3.4.2.3.2.3.2.3.3.4.3.2.3.3.3.2.3.4.3.3.2.3.2.2.3.4.3.2.3.3.4.3.3.4.3.3.2.3.3.3.3.4.2.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.1.2.3.4.2.3.4.3.3.2.3.3.2.3.4.2.2.2.3.3.3.3.4.4.3.2.3.3.3.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.2.3.4.3.2.2.3.3.2.3.4.2.3.3.3.3.3.3.4.3.2.3.3.4.3.3.4.2.2.2.3.2.2.3.4.3.2.2.3.3.3.3.4.3.2.3.3.3.3.3.4.3.2.3.3.4.2.3.4.3.3.3.3.2.2.3.4.2.3.3.3.3.3.3.4.3.3.2.3.3.2.3.4.3.3.2.3.4.3.3.4.3.3.3.3.2.3.3.4.2.2.3.3.3.2.3.4.4.2.2.3.3.3.3.4.3.3.3.3.4.3.3.4.3.3.2.3.2.3.3.4.3.3.2.3.3.2.3.4.1.2.3.3.2.2.3.4.3.2.3.3.4.2.3.4.2.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.2.3.3.2.2.3.4.3.3.2.3.4.3.3.4.3.2.3.3.2.3.3.4.3.2.2.3.3.3.3.4.2.3.2.3.3.3.3.4.3.2.3.3.4.2.3.4.3.2.2.3.2.3.3.4.2.3.3.3.3.3.3.4.4.3.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.2.2.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.2.3.3.2.3.4.3.3.3.3.4.2.3.4.2.2.3.3.2.3.3.4.3.3.3.3.3.2.3.4.3.3.3.3.3.2.3.4.3.2.3.3.4.3.3.4.4.2.2.3.2.3.3.4.3.1.2.3.3.2.3.4.2.3.2.3.2.3.3.4.3.2.3.3.4.2.3.4.3.3.2.3.2.2.3.4.3.2.3.3.3.2.3.4.4.2.3.3.2.2.3.4.3.3.2.3.4.3.3.4.2.2.3.3.3.3.3.4.2.2.2.3.3.3.3.4.2.3.2.3.3.2.3.4.3.3.2.3.4.3.3.4.3.2.2.3.3.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.3.3.3.4.3.2.2.3.4.2.3.4.2.3.2.3.3.3.3.4.2.3.3.3.3.3.3.4.2.3.3.3.2.3.3.4.3.2.2.3.4.3.3.4.3.2.3.3.3.3.3.4.3.3.2.3.3.3.3.4.4.3.2.3.2.2.3.4.3.2.3.3.4.2.3.4.3.2.3.3.1.2.3.4.2.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.2.3.3.4.2.3.4.2.2.3.3.3.2.3.4.2.3.2.3.3.3.3.4.3.3.2.3.2.2.3.4.3.3.3.3.4.2.3.4.3.3.3.3.2.3.3.4.3.2.2.3.3.3.3.4.2.3.2.3.3.2.3.4.3.3.3.3.4.3.3.4.3.2.3.3.3.2.3.4.2.3.2.3.3.2.3.4.4.2.3.3.2.3.3.4.3.3.2.3.4.2.3.4.3.3.2.3.3.3.3.4.3.2.3.3.3.2.3.4.3.3.2.3.2.3.3.4.3.3.2.3.4.2.3.4.2.2.3.3.2.3.3.4.2.2.3.3.3.2.3.4.3.3.2.3.3.2.3.4.3.3.3.3.4.3.3.4.3.1.2.3.2.2.3.4.2.3.2.3.3.3.3.4.2.2.3.3.3.3.3.4.3.2.2.3.4.3.3.4.3.3.3.3.3.2.3.4.3.2.3.3.3.3.3.4.4.3.2.3.2.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.3.3.4.3.3.2.3.3.3.3.4.2.3.2.3.3.2.3.4.3.2.3.3.4.2.3.4.3.3.2.3.2.2.3.4.3.3.3.3.3.2.3.4.3.2.3.3.2.3.3.4.3.3.2.3.4.3.3.4.4.2.3.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.3.3.2.2.3.4.3.3.2.3.4.2.3.4.3.3.3.3.2.2.3.4.3.2.2.3.3.2.3.4.4.3.3.3.3.3.3.4.3.2.3.3.4.3.3.4.1.2.3.3.2.2.3.4.2.2.3.3.3.3.3.4.2.3.3.3.2.3.3.4.3.2.2.3.4.2.3.4.2.3.2.3.2.3.3.4.2.2.3.3.3.3.3.4.3.2.2.3.3.3.3.4.3.3.2.3.4.2.3.4.2.2.3.3.3.3.3.4.3.3.2.3.3.2.3.4.3.2.2.3.3.3.3.4.3.2.3.3.4.3.3.4.3.3.2.3.2.3.3.4.2.3.3.3.3.2.3.4.4.3.3.3.2.2.3.4.3.2.3.3.4.2.3.4.2.3.2.3.3.2.3.4.3.3.3.3.3.3.3.4.2.3.3.3.2.2.3.4.3.3.2.3.4.3.3.4.2.2.2.3.3.3.3.4.3.2.2.3.3.2.3.4.3.3.3.3.2.2.3.4.3.3.3.3.4.3.3.4.3.1.2.3.2.2.3.4.3.3.2.3.3.2.3.4.3.2.3.3.2.3.3.4.3.2.2.3.4.2.3.4.3.2.2.3.3.2.3.4.2.3.3.3.3.3.3.4.4.2.2.3.3.2.3.4.3.3.2.3.4.2.3.4.2.2.3.3.3.2.3.4.3.3.3.3.3.3.3.4.2.3.2.3.3.3.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.2.3.4.2.3.3.3.3.3.3.4.3.2.2.3.2.3.3.4.3.2.2.3.4.2.3.4.2.3.3.3.2.3.3.4.2.3.3.3.3.2.3.4.3.2.2.3.2.3.3.4.3.3.3.3.4.2.3.4.3.3.3.3.2.3.3.4.3.2.2.3.3.3.3.4.4.3.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.2.2.3.1.2.3.4.2.3.2.3.3.2.3.4.2.3.3.3.2.2.3.4.3.3.2.3.4.2.3.4.3.3.2.3.3.3.3.4.2.3.3.3.3.3.3.4.3.2.2.3.3.2.3.4.3.2.3.3.4.2.3.4.4.2.3.3.2.3.3.4.3.2.3.3.3.2.3.4.2.3.3.3.2.2.3.4.3.2.3.3.4.3.3.4.3.2.2.3.2.2.3.4.2.3.3.3.3.3.3.4.4.3.3.3.3.3.3.4.3.2.2.3.4.2.3.4.3.3.3.3.3.2.3.4.2.3.2.3.3.3.3.4.3.2.3.3.2.2.3.4.3.3.2.3.4.3.3.4.2.3.3.3.2.3.3.4.3.2.2.3.3.2.3.4.3.3.2.3.3.2.3.4.3.3.3.3.4.3.3.4.2.3.3.3.3.2.3.4.2.1.2.3.3.2.3.4.2.2.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.3.2.3.3.2.3.4.2.2.3.3.3.2.3.4.4.2.3.3.3.3.3.4.3.3.2.3.4.3.3.4.3.2.3.3.2.3.3.4.2.2.2.3.3.3.3.4.2.2.2.3.3.3.3.4.3.2.2.3.4.3.3.4.3.3.3.3.2.2.3.4.2.3.2.3.3.2.3.4.3.3.3.3.2.3.3.4.3.3.2.3.4.3.3.4.3.3.2.3.3.2.3.4.2.2.3.3.3.3.3.4.3.3.2.3.3.2.3.4.3.2.2.3.4.2.3.4.3.2.3.3.3.3.3.4.3.3.2.3.3.2.3.4.4.3.2.3.2.2.3.4.3.3.3.3.4.2.3.4.4.2.2.3.3.3.3.4.2.3.3.3.3.2.3.4.1};
        returndp[n]; }};Copy the code

It doesn’t look like much code without line breaks, and an array of 40,000 elements looks like a lot after the automatic line break display.

One of the following questions per day

1673. Find the most competitive subsequence

A) 402 b) 402 C) 402 D) 402 Remove the K digits

Look at the solution of 402, there are many methods, and there are many similar problems are put together. This kind of problem should be able to test many kinds of algorithms, and then according to the time requirements and space requirements stuck in some of the algorithms. I’m going to have to do more problems to figure it out, but I’ll leave a little bit of a hole here, and I’ll figure out the different solutions and the complexity of these problems.

If you do it with a monotonic queue, the idea is to get the smallest number in order, get rid of the ones you don’t need, get rid of at most the original length minus the target length, how many more elements do you need to get rid of in one variable.

If you’re done iterating through the array, and you find that you still need to throw away some numbers, you start at the end, that’s why you’re monoqueuing, it’s easy to do things at the end of the queue.


class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        int n = nums.size(a); vector<int> mono_inc_stk;
        int max_del_cnt = n - k;
        for (int i = 0; i < n; i++) {
            while(! mono_inc_stk.empty() && mono_inc_stk.back() > nums[i] && max_del_cnt > 0) {
                mono_inc_stk.pop_back(a); max_del_cnt -=1;
            }
            mono_inc_stk.push_back(nums[i]);
        }
        while (mono_inc_stk.size() > k) {
            mono_inc_stk.pop_back(a); }returnmono_inc_stk; }};Copy the code

summary

Item infinite knapsack problem, mathematical solution dimension reduction blow, number table solution dimension reduction blow, monotonous queue crack delete element problem

Refer to the link

Remove K digits