Leetcode daily question and next question of the day brush notes 10/30

Writing in the front

This is the 10th day of my participation in the More text Challenge. For more details, see more text Challenge

About to graduate, just find oneself by the algorithm problem in the interview hanging up hammer. No way can only be based on zero identity and classmates to join the force buckle brush problem army. My classmates are very good, they usually just modest, verbally said that they can’t, but I really can’t… As the Nuggets encourage their new players to blog every day, I joined in by recording the first two questions of the day, which I worked on carefully. I plan to brush five questions every day, and the other questions can only be forcibly memorized, not posted in the blog.

I really just a vegetable chicken, solution ideas what don’t reference from me here, coding habits also need to improve, if you want to find brush problem master consult questions I think to find the palace water three leaf brush problem diary this big guy is better. I try not to look at the problem before the problem to work out, so as not to crash with the content of the big guy.

In addition, I also hope that there are idle big guy to provide some more intelligent solution ideas to me, welcome to discuss ha!

All right, no more nonsense, let’s start the first two questions of the tenth day!

2021.6.10 One question per day

518. Change for II

This problem compares the standard item infinite backpack problem, which can be solved quickly. The capacity is the total value of the current coin price, and the value is the number of combinations to get the total value of the current price. The minimum amount is the price of a coin of the current denomination, and the maximum amount is the amount. Let me write down the equation of state.


dp [ i ] = dp [ i ] + dp [ i – cur_coin ] \texttt{dp}[\texttt{i}] = \texttt{dp}[\texttt{i}] + \texttt{dp}[\texttt{i} – \texttt{cur\_coin}]

I don’t think I need to explain, but the transfer equation is the number of combinations minus the currently selected coin plus the number of combinations without the currently selected coin.

The following code


class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int& cur_coin : coins) {
            for (inti = cur_coin; i <= amount; i++) { dp[i] += dp[i - cur_coin]; }}returndp[amount]; }};Copy the code

Sure enough, this month is a dynamic programming month, not a prefix and month…

2021.6.10 The following is the question of the day

Make the xOR result of all intervals zero

We’re using the xor property, the same thing xor is 0. You can make your own truth table and try it out.

And then you put it in this problem, you take any array that’s been adjusted, and xor is 0 for k numbers starting with I, and 0 for k numbers starting with I plus 1, so what do you get directly xor or? The repeated elements in the middle cancel out, just like the derivation of the geometric sequence, the dislocations cancel out, leaving only the heads and tails, Then got the nums [I] the radius nums [I] + k = 0 \ texttt {nums} [\ texttt {I}] \ oplus \ texttt {nums} [\ texttt {I} + \ texttt {k}] = 0 nums [I] the radius nums [I] + k = 0, Or nums = nums [I] [I] + k \ texttt {nums} [\ texttt {I}] = \ texttt {nums} [\ texttt {I} + \ texttt {k}] nums = [I] nums [I] + k

I’m not very good at this, but I think it’s going to be dynamic programming, and I’m going to use this relationship to find state transitions, but I can’t find them. And then I see the problem. So this is a hash table, so it makes a little bit of sense, because the number of occurrences of each element in the hash table depends on where it first occurred and the size of the array. Then began to consider the problem of state transition equation, state transition to the adjusted array as a comb with many wrong teeth, comb elements subscript k congruent (that is, a total of K comb), comb teeth periodically appear, a lot of comb teeth according to the law inserted into the gap of other combs. Set the current processing to the ith, take a tooth from each comb in the current array, and the XOR result is mask, then modify all teeth on comb I, set the modified value to x, then the modified XOR result is mask XOR x, so the state transition equation is slowly written out. In the state transition equation, size(I) is the number of teeth on the comb of the ith handle, and count[I][x] is the number of teeth whose value on the comb of the ith handle is equal to x. = = = = = = = = = = = = = = = = = = = = = = = = = =


dp [ i ] [ mask ] = m i n x { dp [ i – 1 ] [ mask The radius x ] + size [ i ] – count [ i ] [ x ] } = size [ i ] + m i n x { dp [ i – 1 ] [ mask The radius x ] – count [ i ] [ x ] } [\ texttt \ texttt {dp} {I}] [\ texttt {mask}] = \ underset {\ texttt {x}} {min} \ left \ {\ texttt {dp} [\ texttt {I} – 1] [\ texttt {mask} + \ \ oplus \ texttt {x}] texttt {size} [\ texttt {I}] – \ texttt {count} [\ texttt {I}] [\ texttt {x}] \} \ \ \ \ right quad, quad, quad , quad, quad = \ texttt {size} [\ texttt {I}] + \ underset {\ texttt {x}} {min} \ left \ {\ texttt {dp} [\ texttt {I} – 1] [\ texttt {mask} – \ \ oplus \ texttt {x}] texttt {count} [\ texttt {I}] [\ texttt {x}] \ right \}

Since the argument for the minimum value is x, we can take out size[I], which is independent of x.

To optimize this formula later, I don’t understand the space complexity here… I did run out of time writing code along these lines…

I really need more research on this one. I’m stuck…

2021/6/11 update

Some problems to let it ferment in the brain for a period of time, and then out to do may be a little better. I’m not going to go into complexity here, but I’m going to go into complexity just to remind myself where we’re going. I’ve instructed myself to run out of time, so I really need to optimize here.

So they give us an array that has an upper limit on the value of each element, which is a 10 bit binary number, and that’s important because we want to minimize the number of changes to the element, so try to find the number that’s already there, and make it the same, and that’s the way to minimize the number of changes. Wouldn’t it be rude and understandable if I changed all the elements to zero without limiting the number of times I could change them? So, x actually has an upper bound, the same upper bound as the value of each element in the array, which is a 10-bit binary number. In this way, we can estimate the time complexity in the worst case (netherworld test case). In the worst case, the tooth of each comb has to be changed, then the tooth value is a 10 bit binary number, and all the possible x’s have to be tried out, so that the complexity of O(220k)O(2^{20} \texttt{k})O(220k)… That’s why we ran out of time.

This optimization idea is very clever, after the reaction found that they can think of. Because it’s minimizing, there’s already a minimum in the original set, so if I add something bigger than the minimum, it won’t affect me finding the minimum. So let’s break up the expression that we had here. Count [I][x] = 0; count[I][x] = 0; In this case, the minimum modification is the length of the comb, which is size[I]. If this is added to the set of minimum values, it will not affect finding the original minimum value (in fact, there is no new element, only to save the work of finding count[I][x]), so the time complexity is reduced.

The second part is to take one of the numbers where X still appears on the comb teeth. In this way, like the original state transition, nothing new will be introduced into the set of finding minimum values. The complexity should not be reduced here, and I do not know how many times X appears on the comb teeth before.

So, again, you can change the state transition equation, and the key idea is to take the numbers in the minimum set and calculate them in sections.


dp [ i ] [ mask ] = size [ i ] + m i n x { dp [ i – 1 ] [ mask The radius x ] . dp [ i – 1 ] [ mask The radius x ] – count [ i ] [ x ] } \texttt{dp}[\texttt{i}][\texttt{mask}] = \texttt{size}[\texttt{i}] + \underset{\texttt{x}}{min} \left \{ [\ texttt \ texttt {dp} {I} – 1] [\ texttt {mask} \ oplus \ texttt {x}]. [\ texttt \ texttt {dp} {I} – 1] [\ texttt {mask} \ oplus \ texttt {x}] – \ texttt {count} [\ texttt {I}] [\ texttt {x}] \ right \}

Now the state transition equation has an internal flavor, with “see but don’t take, just play” before “see and take, let’s see what happens”.

Here’s a quick look at the worst case, “Just to play,” where the complexity is O(210)O(2^{10})O(210), O(size[I])O(\texttt{size}[\texttt{I}])O(size[I]), O(210+size[I])O(2^{10} + \texttt{size}[\texttt{I}])O(210+size[I]) We get the total complexity is O(210k+n)O(2^{10}\texttt{k} +n)O(210k+n), and the last n is the length of the entire array. In this way, the final dp[k-1][0] is the required result (the comb number starts from the subscript 0, and the xOR result in the final state is 0).

To save space, we need one less variable in the state transition equation, which is the comb subscript we’re looking at. Then replace the two-dimensional array with two one-dimensional arrays of size O(210)O(2^{10})O(210).

The initial condition dp[-1][0] = 0, other dp[-1][] = infinity is meaningless.

The following code, go to see the official problem, my original code east to west to change and that is about the same, and then to complete a variety of non-standard writing, comments a plus, and the official problem of the code is very, very similar. Below is the screenshot of the official problem solved, is the passing rate of this question really so high? It’s all the same as in this screenshot

It’s not easy.

summary

For the infinite item knapsack problem, the state transition equation reduces the complexity by calculating the optimal value separately

Refer to the link

The solution of the second problem, I see this is ok, I did not understand.

Leetcode-cn.com/problems/ma…