Leetcode brush the daily problem and the next problem of the daily problem notes 18/30

Writing in the front

This is the 18th 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!

Good nonsense not much to say the first two questions of the 18th day!

2021.6.18 One question of the day

483. Minimum good base

This problem is to find the sum of geometric sequence, the problem is said to be fanciful. There is a formula for the sum of geometric sequence, after entering the society, it is gradually forgotten (maybe people who buy funds and fry money are using it every day, they should not forget). The derivation of the summation formula is the transposition. So I’m going to embarrass you and derive the sum formula that we’re going to use.


n = S u m = 1 + k + k 2 + . . . + k m k x n = k x S u m = k + k 2 + k 3 + . . . + k m + 1 \begin{aligned} n &= Sum = 1 + k + k ^ 2 + … + k ^ m \\ k \times n &= k \times Sum = k + k ^ 2 + k ^ 3 + … + k ^ {m + 1} \end{aligned}

Subtract the top and bottom of these two things, and you get the sum


( k – 1 ) x n = ( k – 1 ) x S u m = – 1 + 0 + 0 + . . . + 0 + k m + 1 n = S u m = k m + 1 – 1 k – 1 . k indicates 1 (k – 1) \times n = (k – 1) \times Sum = -1 + 0 + 0 + … + 0 + k ^ {m + 1} \\ n = Sum = \frac{k ^ {m + 1} – 1}{k – 1}, k \ne 1

This formula works for all cases where the common ratio is not 1.

Now, back to the interview question, this formula has the original number N and its “good base” K in it, so if you transform the sum formula and scale it up, you get the new relationship


k m + 1 = 1 + n x k – n < k x n m < l o g k n k ^ {m + 1} = 1 + n \times k – n < k \times n \\ m < log_k n

They have the range of n, so we can approximate the range of m,


3 Or less n Or less 1 0 18 . k > = 2 . m < l o g 2 1 0 18 = 18 l o g 2 10 material 60 3 \le n \le 10^{18}, k >= 2, \\ m < log_2 10^{18} = 18 log_2 10 \approx 60

This is an important condition, so let me write it down.

And then I’m going to have to scale again, this time I’m going to scale the summation formula, and the summation formula has to have a lower bound, as long as the base K is greater than or equal to 2, the geometric sequence is monotonically increasing. So the sum of the first m term is definitely greater than the last term. And we have to find an upper bound. The upper bound is easy to determine, and each term in the geometric sequence has a coefficient of 1, and then the form of each term is the same as the form of each term in the binomial theorem, this time using the binomial theorem to scale, the whole summation formula is definitely less than the power of the binomial consisting of base K and 1.


n = 1 + k + k 2 + . . . + k m < ( m 0 ) + ( m 1 ) x k + ( m 2 ) x k 2 + . . . + ( m m ) x k m = ( k + 1 ) m . n < ( k + 1 ) m n = 1 + k + k ^ 2 + … + k ^ m < \binom{m}{0} + \binom{m}{1} \times k + \binom{m}{2} \times k ^ 2 + … + \binom{m}{m} \times k ^ m = {(k + 1)} ^ m, \\ n < {(k + 1)} ^ m

If you already have a job and can’t understand what I’m talking about, please take a look at the Yang Hui triangle below. I hope this will remind you of your school days.


1 m = 1 1 2 1 m = 2 1 3 3 1 m = 3 1 4 6 4 1 m = 4 . . . . . . ( m 0 ) ( m 1 ) . . . . . . ( m m – 1 ) ( m m ) m = m \begin{aligned} \begin{array}{} 1 & m = 1 \\ 1 \quad 2 \quad 1 & m = 2 \\ 1 \quad 3 \quad 3 \quad 1 & m = 3 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 & m = 4 \\ …… \\ \binom{m}{0} \quad \binom{m}{1} \quad …… \quad \binom{m}{m – 1} \quad \binom{m}{m} & m = m \end{array} \end{aligned}

The power of the binomial I said, its coefficients are only 1 for the highest and lowest degree terms on both sides, and the coefficients of the other terms are already greater than 1. It is inevitable that the sum of the geometric series will be greater than that of the sum of the geometric series. To sum up, the result of this scaling gives the range of the sum of both ends of the geometric series.


k m < n < ( k + 1 ) m . k < n m < k + 1 . ⌊ n m ⌋ = k . ⌈ n m ⌉ = k + 1 k ^ m < n < {(k + 1)} ^ m, \\ k < \sqrt[m]{n} < k + 1, \\ \lfloor \sqrt[m]{n} \rfloor = k, \lceil \sqrt[m]{n} \rceil = k + 1

So now we have another set of relationships, remember that, and we’re going to use them.

We already know n when we write the code, so we can just give any m, and we can figure out a k, and then verify that this k can figure out n.

When m is equal to 1, there are only two terms in the whole geometric series. The good base k is guaranteed and also the largest. We should start from 60 where M is the largest, so that the smallest good base will be encountered first.

Here is the end of the code train of thought, behind is the translation part.


class Solution {
public:
    string smallestGoodBase(string n) {
        long nVal = stol(n);
        int mMax = floor(log(nVal) / log(2));
        for (int m = mMax; m > 1; m--) {
            int k = pow(nVal, 1.0 / m);
            long mul = 1, sum = 1;
            for (int i = 0; i < m; i++) {
                mul *= k;
                sum += mul;
            }
            if (sum == nVal) {
                return to_string(k); }}return to_string(nVal - 1); }};Copy the code

This problem is to push if you don’t want to use the formula so around, can directly take binary estimate about how many 1, under a good hexadecimal number is 1, the largest is the good base n – 1, with binary try one by one down to go, probably is the most wonderful hexadecimal from binary and middle n – 1 the hexadecimal began to try, The length of all ones remains the same until a good base can be tried (if all ones are so long that no one can be tried, one less digit will be tried). Try out good base process is a process of binary, if now the midpoint hexadecimal sequence of all 1 to 10 hexadecimal than the original number is big, I am at the point of the middle and small point on continue to try, if turn decimal is smaller than the original number, I just at the point of the middle and large continue to try, try to two endpoints overlap haven’t the right into the system, So I’m going to have to subtract one from all ones. If you can’t do it with all 1s and length 3, then good base is the best base that can guarantee the bottom.

In fact, no matter what idea, is to narrow the search scope step by step, if the effect of zoom out is better, the search scope can be smaller faster, why not better zoom out?

One question per day below

47. Maximum value of a gift

There’s a path, you can’t go diagonally, that’s dynamic programming. This is a classic problem, to make it easier to write code, just add a line and a column in front of the starting point. Each cell is updated by adding the maximum value from its left and top sides to its own sum, so that the bottom right corner finally gets the maximum value. If you want to find the path, use backtracking.


class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(a); vector<vector<int>> dp(n + 1, vector<int>(m + 1.0));
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]; }}returndp[n][m]; }};Copy the code

I’m going to save a little bit more space by writing it this way, by saving space on one dimension, which must have been transferred from the previous one anyway.


class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(a);vector<int> dp(m + 1.0);
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                dp[j] = max(dp[j], dp[j - 1]) + grid[i - 1][j - 1]; }}returndp[m]; }};Copy the code

summary

Mathematical or mindless dichotomies are used to narrow the search area, and dynamic programming makes boundary condition processing code easier by opening one more column above and to the left of the starting point.

Refer to the link

There is no