Only played one LeetCode game of the week this week

Let’s start with the record: 1 question. / (ã„’ o ã„’) / ~ ~

The first question 2 minutes to write, and then has been stuck in the second question, card to the end of the game 😓

I don’t even see questions three and four

When the back carries on the note collation, to those did not see the question, is oneself try to do first, do not come out to see the question solution again, the result third question oneself did come, had the opportunity to pass 2 QAQ

It seems that the need to adjust the dead head when doing a problem, a problem card is too long to see the back of the first have a chance.

The title

1952

Three divisor

I give you an integer n. Returns true if n has exactly three positive divisor numbers; Otherwise, return false. If there is an integer k such that n = k * m, then the integer m is a divisor of n.

C + + code

class Solution {
public:
    bool isThree(int n) {
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0) {
                returni == n / i; }}return false; }};Copy the code

I’ll skip the check-in question.

1953

Maximum number of weeks you can work

I give you n items, numbered from 0 to n-1. Also give you an integer array named Renamed [I]; each of these lists lists the number of stage tasks in the i-th project.

You can work on a project by following two rules:

  • Each week, you will complete exactly one phase of a project. You have to work every week.
  • You cannot participate in and complete two phases of the same project in two consecutive weeks. Once all phase tasks in all projects have been completed, or only one phase task left will cause you to violate the above rule, then you will stop working. Note that you may not be able to complete all stages due to these conditions.

Returns the maximum number of weeks you can work without violating the above rules.

Example 1:

1. The first possible case was renamed as: 1,2,3:1;

  • In week 1, you participated in and completed one of the phase tasks in Project 0.
  • In week 2, you participated in and completed a phase task in Project 2.
  • In week 3, you participated in and completed a phase task in Project 1.
  • In week 4, you participated in and completed a phase task in Project 2.
  • In week 5, you participated in and completed a phase task in Project 1.
  • In week 6, you participated in and completed a phase task in Project 2. The total number of weeks is 6.

Show it by item number

,2,1,2,1,2 [0]

Example 2:

Renamed = [5, 3, 6]

Output: 14

Explanation:

One possible arrangement, indicated by item numbers, is

,0,1,2,0,1,2,0,1,2,0,2,0,2 [2]

Answer key:

In fact, this is a biased mathematical derivation and find rules of the puzzle. You can only complete one task per week, and can’t do two tasks on the same project in two adjacent weeks. Let’s think about it another way.

Think of each project as a ball of a certain color, and each phase of the project as a ball. Suppose a project has three phased tasks, then there are three balls of that color.

Then the question becomes, given a certain number of balls of different colors, how do you arrange the balls so that any two adjacent balls have different colors? How many balls can you arrange at most if this condition is satisfied?

To simplify the description, we will directly use the item number to indicate the color of the ball.

By trying multiple test cases, it is easy to see that the key is to find the most colored balls. (That is, find the project with the most phased tasks)

And then we compare the number of balls of that color with the number of other balls that are left. To arrange by means of space.

Let’s say that the color that has the largest number of balls is longest, and the sum of all the remaining balls is rest.

First, arrange the largest number of balls of this color in a row, and then try to insert the remaining balls into the empty space.

For example, the largest number is the color ball 0, for example, there are 9 balls (longest=9), then we will first arrange them in a row

0, 0, 0, 0, 0, 0

Then consider the size of rest, consider inserting other colored balls into it, and we’ll discuss this case by case.

Assuming that 9 0 balls can all be separated, we need at least 9-1=8 balls of other colors (the other colors are denoted by x), i.e

0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0

If REST < 8 (rest < longest -1), then the remaining balls are not enough to separate no. 0 ball. At this time, under the condition that the conditions are met, the maximum number of balls that can be placed is REST * 2 + 1, such as REST = 6. The maximum number of balls that can be placed is 2 * 6 + 1 = 13, as follows

0 x 0 x 0 x 0 x 0 x 0 x 0

So, in the first case, if rest is greater than longest-1, we can put all rest balls into it (and all rest balls can be separated by whatever color the largest number of rest balls is, in our case, ball 0), but for rest, if rest is greater than longest-1, we can put all REST balls into it (and rest balls can be separated by whatever color the largest number of rest balls is, in our case, ball 0), You can only put as many rest + 1 balls as you want, so you can put a maximum of REST * 2 + 1 balls. So,

  • whenrest < longest - 1“, the answer is2 * rest + 1.

And then let’s think about the case where rest >= longest-1, where we can put all the longest balls.

For example, if rest is equal to the longest, then rest is equal to the longest. If rest is equal to the longest, then rest is equal to the longest. If rest is equal to the longest, then rest is equal to the longest.

Let’s say rest > longest-1, where the rest is going to be able to separate all the longest balls, and then we have the rest. Let’s think about it this way. Let’s take the second largest number of balls (let’s say it’s a color number 1) and insert them.

0 1 0 1 0 1 0 1 0 1 0 x 0 x 0 x 0

The remaining positions that have not been inserted are represented by X. Since the number of no. 1 balls is smaller than that of No. 0 balls, it may not be possible to separate all no. 0 balls (if the number of no. 1 balls is exactly 1 smaller than that of No. 0 balls, it can be separated). With the insertion of the no.1 ball, there was more space. We can then insert the number of the third big ball (assuming the Numbers for 2), no. 2 ball can be inserted into any open (because the arrangement of ball no. 2, no. 2 ball in the case of adjacent), and no. 2 ball can all insert (space becomes a lot, and the number of no. 2 ball very few), insert the no. 2 ball all, in the same way, It is possible to insert all three balls in any position, and then all four balls in any space, so dependent that all balls can be inserted.

so

  • whenrest > longest - 1“, the answer is alsorest + longestThat is, all the balls can fit into the answer.

After the above analysis and discussion, there are only two cases

  • rest < longest - 1At this point torestPart of the ball, you can insert all of it, rightlongestPart of the ball that can be inserted as far as possible (rest + 1), the answer is2 * rest + 1
  • rest >= longest - 1I can insert all the balls. The answer isrest + longest

The C++ code is as follows

class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        int n = milestones.size();
        int longest = 0; / / the longest
        long long rest = 0;
        for (int i = 0; i < n; i++) {
            rest += milestones[i];
            longest = max(longest, milestones[i]);
        }
        rest -= longest;
        if (rest >= longest - 1) return longest + rest;
        else return rest * 2 + 1; }};Copy the code

1954

Collect enough apples for the minimum garden perimeter

You are given a garden represented by an infinite two-dimensional grid, with an apple tree at each integer coordinate. Integer coordinates (I, j) apple tree have | | | | + j I an apple.

You will buy a square of land with a central coordinate of (0, 0), and each edge is parallel to one of the two axes.

Given an integer neededApples, return the minimum circumference of the field so that there are at least neededApples in or at the edge of the field.

| | x value is defined as:

If x is greater than or equal to 0, it’s going to be x and if x is less than 0, it’s going to be minus x

Answer key:

This is a relatively simple to find the rule of the topic, as long as their own hands to draw, find the rule, induce a formula, can. (It is a pity that they do the topic is very stubborn, that night week game card in the second topic, has been stuck, did not see the back of the topic. Originally this problem can be done, alas

The derivation process of the formula is given below

Since we only have apple trees at integer coordinates, and we need a square of land centered at the origin (0,0), we can draw a two-dimensional coordinate axis. It is easy to know that the sides of a square can only be even. Here is the following

We call the length of the line segment in yellow in the figure above the radius of the square (r). Since there are only apple trees at integer coordinates, and we can only circle a square centered on the origin (0,0) when we circle the apples. So r can only be a positive integer from 1 to n.

So the first thing we can easily get is that the sides of the square are equal to 8 times r.

Next, we looked at all the apple trees that happened to be on the edge of the square.

First look at the side, the leftmost coordinate of the side is (-r, r), then move to the right of the side, the coordinates of integer points are (-(r-1), r), (-(r-2), r),… , (-1, r), (0, r); Then look at the right half of the edge, respectively (1, r), (2, r)… , (r, r), and found that the left and right sides are symmetric. The total number of apples on this side is: the number of apples on the left side times 2, plus the center (0, r). So let’s do the left-hand side first, as follows

[(r - 1) + r] + [(r - 2) + r] + .. + [1 + r] = r × r + (1 + 2 +... + r)

Result is r2 + (1 + r) x r2r ^ 2 + \ frac {(1 + r) \ times r} {2} r2 + 2 (1 + r) (r, The edge of the total number of apple is (r2 + (1 + r) (r2) * 2 + r = 3 r2 + 2 r (r ^ 2 + \ frac {(1 + r) \ times r} {2}) \ times 2 + r ^ 2 + 2 = 3 r r (r2 + (1 + r) (r) 2 x 2 + r = 3 r2 + 2 r

It’s easy to extrapolate. We’re going to have the same number of apples on all four sides, so we’re going to multiply it by 4, but we’re going to notice that we’ve added one more apple to the four top angles, so we’re going to subtract one more. The result is (3r2+2r)×4−2r×4=12r2(3r^2+2r) \times 4-2r \times 4=12r ^2(3R2 +2r)×4−2r×4=12r2

So, the number of apples on the edge of the square with radius R is 12r212r^ 212R2, and the circumference of the square is 8R8R8R

We simply start with r=1r=1r=1 and add up the number of apples until it exceeds neededApples.

The C++ code is as follows:

class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
        long long sum = 0;
        long long i = 0;
        while (sum < neededApples) {
            ++i;
            sum += 12 * i * i;
        }
        return 8* i; }};Copy the code

1955

Count the number of special subsequences

A special sequence is a sequence of positive integer zeros, followed by positive integer ones, and finally positive integer twos.

  • For example, [0,1,2] and [0,0,1,1, 2] are special sequences.

  • In contrast, [2,1,0], [1] and [0,1,2,0] are not special sequences.

Given an array nums (only integers 0,1, and 2), return the number of different special subsequences. Since the answer may be large, you can return it mod 10^9^ + 7.

A subsequence of an array is a sequence in which zero or more elements are removed without changing the order of the elements. Two subsequences are different if they have different sets of subscripts.

Example 1:

Input: nums =,1,2,2 [0] output: 3: special subsequence,1,2,2 [0], [0,1,2,2] and [0,1,2,2]Copy the code

Example 2:

Input: nums = [2,2,0,0] output: 0 explanation: there are no special subsequences in the array [2,2,0,0].Copy the code

Example 3:

Input: nums = [0,1,2,0,1,2] output: 7 explanation: special subsequences include: ,1,2,0,1,2,1,2,0,1,2 - [0] - [0] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] -,1,2,0,1,2 [0] - [0,1,2,0,1,2]Copy the code

Answer key:

By enumerating simple use cases, it is easy to see that when constructing a particular sequence, we need a subsequence like 000, a subsequence like 00111, and a subsequence like 00111222. Each of these subsequences may be preceded or followed by a number to form a special sequence such as 0011222.

So this problem is considered to be done with the idea of dynamic programming, as follows:

We call a subsequence of type 0, such as 000, consisting only of positive integer zeros; Such as 00111, only by the positive integer 0 followed by the positive integer 1 subsequence, called type 1 sequence; A subsequence such as 0011222, consisting of a positive integer 0 followed by a positive integer 1 followed by a positive integer 2, is called a type 2 sequence (that is, the special sequence described in the question).

So, we can use

  • f(i,0)To say fromnums[0]tonums[i],Type zero sequenceThe number of;
  • f(i,1)To say fromnums[0]tonums[i],Type 1 sequenceThe number of;
  • f(i,2)To say fromnums[0]tonums[i],Type 2 sequenceThe number of

And then we enumerate I,

  • When nums[I]=0, we can not use this 0, then no new sequence of type 0 is generated, then f(I,0) is at least equal to f(i-1,0); You can also use this 0, and append this 0 to all the type 0 sequences of f(i-1,0) to form a new type 0 sequence; This 0 can also be a type 0 sequence on its own (without using any type 0 sequence prior to I-1). This zero does nothing for the type 1 sequence represented by F (i-1,1), and it does nothing for the type 2 sequence represented by F (i-1,2). It is easy to obtain the state transition equation at this time:

    F (I,0)=2 times f(I -1,0) + 1,

    F (I, 1) = f (I – 1, 1),

    F (I, 2) = f (I - 1, 2)

  • When nums[I]=1, similarly, the 1 can be appended to all the type 1 sequences of f(i-1,1) to form a new type 1 sequence. For the type 0 sequence of F (i-1,0), we can append this 1 to form a new type 1 sequence. It has no effect on all type 2 sequences of F (i-1,2). Thus, the state transition equation is:

    F (I, 0) = f (I - 1, 0)

    F (I,1)=2 * f(I -1,1) + f(I -1,0)

    F (I, 2) = f (I - 1, 2)

  • When nums[I]=2, similarly, the 2 can be appended to all f(i-1,2) type 2 sequences to form a new type 2 sequence. For the type 1 sequence of F (i-1,1), this 2 can be added to form a new type 2 sequence; F of I minus 1,0, doesn’t work. Thus, the state transition equation is:

    F (I, 0) = f (I - 1, 0)

    F (I, 1) = f (I - 1, 1)

    F (I,2)=2 times f(i-1,2) + f(i-1,1)

And the answer we’re going to find is f of n minus 1,2.

To simplify the code, we just need to traverse the numS array, let the current traversal position is I, then

  • ifnums[i]=0To updateF of I,0 is equal to 2 times f of I minus 1,0, plus 1
  • ifnums[i]=1To updateF (I,1)=2 * f(I -1,1) + f(I -1,0)
  • ifnums[i]=2To updateF (I,2)=2 times f(i-1,2) + f(i-1,1)

Because each f(I,?) in the ith position. Depends only on f of the previous position I minus one. , so it can be compressed to one dimension for rolling updates

The C++ code is as follows

class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        int MOD = 1e9 + 7;
        long long f0 = 0, f1 = 0, f2 = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 0) f0 = (2 * f0 + 1) % MOD;
            if(nums[i] == 1) f1 = (2 * f1 + f0) % MOD;
            if(nums[i] == 2) f2 = (2 * f2 + f1) % MOD;
        }
        returnf2; }};Copy the code

(after)

Try again next week! I can’t believe there’s still one problem next week!

See you next week!