Hello, I’m Liang Tang.
As usual, let’s take a look at the LeetCode week, which ended yesterday morning. This article was originally posted on a personal public account: Coder Liang
This week’s competition is sponsored by Liufangyun, and the top 500 can get internal push codes, massage machines, custom cups and other prizes.
The quality of this competition is very good, the gradient is very obvious. There are no more niche algorithms, more attention to the understanding and thinking ability of conventional algorithms.
All right, let’s cut to the chase. Let’s see.
Find the difference between the two arrays
Difficulty: 0 stars
Nums1, nums2; nums1, nums2; nums1, nums2;
answer[0]是nums1All of theDon’tExists in thenums2In thedifferentA list of integers.answer[1]是nums2All of theDon’tExists in thenums1In thedifferentA list of integers.
Note: The integers in the list can be returned in any order.
solution
If you look at the range, two array elements are only 1000 at most, so you can play with it any way you want.
So I chose to use Python to water over…
However, there is a trick in the question, and the final result can only contain different elements, so we need to use set to duplicate before returning.
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) - >List[List[int]] :
st1, st2 = set(nums1), set(nums2)
rt1, rt2 = [], []
for x in nums1:
if x not in st2:
rt1.append(x)
for x in nums2:
if x not in st1:
rt2.append(x)
return [list(set(rt1)), list(set(rt2))]
Copy the codeI didn’t think that much during the contest. After the contest, I saw the big guy’s solution and found that this problem only needed three lines in Python:
class Solution:
def findDifference(self, s1: List[int], s2: List[int]) - >List[List[int]] :
return[[* (set(s1) - set(s2))], [*(set(s2) - set(s1))]]
Copy the codeI’m a little ashamed that I’m not familiar with Python yet…
The minimum number of deletions to beautify an array
Difficulty: 2 stars
Given an array of integers with indices starting at 0, nums is considered a beautiful array if:
nums.lengthFor the even- For all
i % 2 == 0The subscripti，nums[i] ! = nums[i + 1]All set up
Note that empty arrays are also considered beautiful arrays.
You can remove any number of elements from nums. When you delete an element, all elements to the right of the deleted element are moved one unit to the left to fill the gap, while elements to the left remain the same.
Returns the minimum number of elements to remove to make numS a beautiful array.
solution
First, let’s look at the data range. The array is at most 1e5, so we definitely can’t use greater than or equal to complexity
Once the range of complexity is determined, there are basically only two paths left: greedy or dynamic programming.
Let’s start with dynamic programming. There is only one conflict where nums[I] == nums[I +1] when I is even. As you can imagine, we can maintain each of these numbers in the odd and even digits. We use dp[I][0] to represent the least number of elements nums[I] should delete when nums[I] has even bits, and dp[I][1] to represent the least number of elements nums[I] should delete when nums[I] has odd bits.
How do we do state transitions?
First, there is only one case where a conflict occurs, and that is when nums[I] == nums[i-1]. At this point, depending on where I is, it’s going to be different.
For dp[I][0], it has two options. The first option is to follow dp[i-1][1], because the problem only requires that the even digit cannot be equal to the next odd digit, but it does not require that it cannot be equal to the previous digit, so this is a strategy. The second strategy is to replace the I -1 in even digits, which requires the I -1 to be deleted, so it incurs 1 overhead. So we in the two cases to choose the optimal: dp [I] [0] = min (dp [0] [I – 1] + 1, dp [I – 1] [1]).
For dp[I][1], it has only one choice, to replace I -1 in the odd digits. Because it can’t be followed by dp[i-1][0].
For nums [I]! In the case of = nums[i-1], this is easy. We have two options: 0 cost after the previous digit, or 1 cost to replace the previous digit. The code is as follows:
class Solution {
public:
int minDeletion(vector<int>& nums) {
int n = nums.size(a);int dp[n+2] [2];
memset(dp, 0.sizeof dp);
dp[0] [1] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] == nums[i- 1]) {
dp[i][0] = min(dp[i- 1] [1], dp[i- 1] [0] +1);
dp[i][1] = dp[i- 1] [1] +1;
}
else {
dp[i][0] = min(dp[i- 1] [1], dp[i- 1] [0] +1);
dp[i][1] = min(dp[i- 1] [0], dp[i- 1] [1] +1); }}return dp[n- 1] [1]; }};Copy the codeThis is not the only way of doing dynamic programming, but here’s another way of doing dynamic programming.
We can consider using DP [I] to store the minimum number of elements that need to be deleted for a substring starting with position I, traversing states from right to left for dynamic programming.
Obviously dp[n-1] = 1, because there is only one element left that does not satisfy the requirement and must be deleted.
When nums[I] == nums[I +1], there are two options, the first option is to replace the I +1 position at the cost of dp[I +1]+1, and the second option is to delete the position with the I +1 position at the cost of dp[I +2]+2.
If the nums [I]! Dp [I] = dp[I +2];
The code is as follows:
class Solution {
public:
int minDeletion(vector<int>& nums) {
int n = nums.size(a);int dp[n+2];
memset(dp, 0.sizeof dp);
dp[n- 1] = 1;
for (int i = n2 -; i > - 1; i--) {
if (nums[i] == nums[i+1]) {
dp[i] = min(dp[i+1] +1, dp[i+2] +2);
}else dp[i] = dp[i+2];
}
return dp[0]; }};Copy the codeIn fact, this problem can also be solved with greed…
Before we get to the algorithm, let’s just briefly prove why greed has a solution. We can think of an array as a concatenation of the same elements in m. Different elements can be spliced whether in odd or even digits, and the only thing to consider is how to combine the same elements to achieve the optimal combination.
Let’s assume that a fragment of the array looks like this: […, x, y, y,… y].
There are two possibilities. The first possibility is that x is in even digits, in which case you can put up to two y’s: [x, y, y].
The second possibility is that x is in odd digits, and only one y can be put down: [x, y]. In this case, we can choose to kill x and make the first y appear in the odd digit, so that we can put down two y: [y, y], but it is easy to find that the contribution to the whole is the same, both are contributing to the length 2.
After a simple proof, we can find that, in fact, no matter what we put in front of the greedy method can put in the results are the same. So you just need to maintain the last placed element and the total number of current placed elements:
class Solution {
public:
int minDeletion(vector<int>& nums) {
int ret = 0;
int n = nums.size(a);int last = nums[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
// Check whether the odd digit conflicts with last
if (cnt % 2) {
if(nums[i] ! = last) { last = nums[i]; cnt++; }// If it is in even digits, put it directly
}else{ last = nums[i]; cnt++; }}if (cnt % 2) cnt--;
returnn - cnt; }};Copy the codeIn the competition, I originally planned to push the dynamic programming algorithm carefully, but I felt that the representation and transfer between states were a little chaotic. After analyzing it, I found that greedy was feasible, so I gave up the derivation and solved it directly by greedy. The problem itself is not difficult, but the reasoning behind the various solutions is very interesting.
Finds the number of palindromes of specified length
Difficulty: 2.5 stars
Select * from ‘queries’ where’ queries’ = ‘intLength’; select * from ‘queries’ where’ queries’ = ‘intLength’; select * from ‘intLength’ where ‘queries’ =’ intLength ‘; It is 1.
Palindrome numbers are numbers that read exactly the same from front to back as from back to front. Palindromes cannot have a leading 0.
solution
As usual, let’s look at the data range. It is found that the maximum range of query is 1e9, that is, the maximum number of palindromes with range number 1e9. That’s a scary range to look at, but it also illustrates the impossibility of sequential generation. Big probability
Then analyze the size of the palindrome string arrangement, it is easy to find the trick.
There are 10 palindromes of length 1:0-9, and there are 10 palindromes of length 2:00-99. I guess some of you will say that not 00, not leading zero? Don’t worry, forget about the leading zero for the moment, just think of it as 10. So the question is, how many lengths are there of 3? 100. How do you count them?
It’s easy. There are 10 possibilities of length 1, so let’s pick one of them and there are 10 possibilities. Then we wrap 0-9 on the outer side of the palindrome string with length 1, so it is 10×10=100 kinds, among which there are 10 kinds of 00 packages, so there are 90 cases of removing leading zeros.
So, let me ask you again, how many palindromes are there of length K? It’s very simple, just to recurse: regardless of the leading zeros
Now let’s think about another problem, suppose we know that the length of a palindrome string is 5, and we want the x smallest palindrome string, how do we find it?
It’s actually quite simple. Let’s write out the smallest palindrome string. What is it? It’s 10001. What’s the second smallest? It’s 10101. Why this one? Because the first move the inside of the number can be as small as possible to ensure that the high position, so first move the inside of the number and then move the outer number. And what you see here is that the next digit of 10001 is 10101, and if we take away half of the numbers and just look at the left hand side, what is it? 100 becomes 101.
What’s the next number in 101? Of course it’s 102, so we want to know how to solve for x is small. It’s easy, 100+x, and then a little bit of palindrome is the answer, yeah, a lot of fancy stuff, it’s really that simple.
I didn’t turn my head during the game, it was ugly in C++…
class Solution {
public:
long long generate(vector<long long>& cnt, int lth, long long x) {
// Store the left part of the palindrome string
vector<int> bits;
for (int i = lth; i > 0; i -= 2) {
long long dec = (i > 1 ? cnt[i2 -] :1);
int b = x / dec + (i == lth);
if (b > 9) return - 1;
bits.push_back(b);
x = x % dec;
}
// Complete the palindrome string
if (lth % 2) {
for (int i = bits.size() - 2; i > - 1; i--) bits.push_back(bits[i]);
}else {
for (int i = bits.size() - 1; i > - 1; i--) bits.push_back(bits[i]);
}
long long ret = 0;
for (int i = bits.size(a)- 1; i > - 1; i--) {
ret = ret * 10 + bits[i];
}
return ret;
}
vector<long long> kthPalindrome(vector<int>& queries, int lth) {
vector<long long> cnt;
cnt.push_back(1);
cnt.push_back(10);
cnt.push_back(10);
// Count the number of LTH length palindromes
for (int i = 3; i <= lth; i++) {
cnt.push_back(10ll * cnt[i2 -]);
}
vector<long long> ret;
for (auto x: queries) {
ret.push_back(generate(cnt, lth, x- 1));
}
returnret; }};Copy the codeIt’s actually pretty easy to do in Python.
class Solution:
def kthPalindrome(self, queries: List[int], lth: int) - >List[int] :
base = 10 ** ((lth - 1) / /2)
maxi = 9 * base
ans = []
def func(x) :
if lth % 2= =0:
return str(x) + str(x)[::-1]
return str(x) + str(x)[-2: : -1]
for q in queries:
if q > maxi:
ans.append(-1)
else:
x = base + q - 1
ans.append(int(func(x)))
return ans
Copy the codeTake the largest denomination of K coins from the stack
Difficulty: 4 stars
There are n coin stacks on a table. Each stack has positive integer coins with face value.
In each operation, you can take 1 coin from the top of any stack, remove it from the stack, and put it in your wallet.
I give you a list piles where piles[I] are an array of integers representing the denominations of coins from top to bottom in stack I. Given a positive integer k, return the maximum value of the coins in your wallet given exactly k operations.
solution
As always, look at the scope first. N and K are not very wide, not very restrictive, not very suggestive.
We are going to take some coins from the n pile. Since each coin is worth more than zero and k is less than the total number of coins, k must be filled up. Secondly, the coins are listed, which means that the number of times we take the coins in the same column can be combined into one take.
So the problem can be simplified: there are n columns of coins, and how many coins can we take from any one of these columns at a time. What is the maximum value that we can take from a maximum of K coins?
If we turn coins into goods, it’s already obvious that this is a multiple backpack problem. It’s just that in multiple backpacks, the same item has the same value, but there’s a slight change here, so coins in the same row don’t have to have the same price. But it doesn’t matter if they’re one or the other, because they’re on the stack, and we can only take them from the top down, and there’s only one way to take x, and we just have to add up.
Familiar with backpack problems, should be able to cut in seconds.
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
int n = piles.size(a); vector<vector<int>> dp(n+1, vector<int>(k+2.0));
for (int i = 1; i <= n; i++) {
int m = piles[i- 1].size(a); vector<int> val;
val.push_back(0);
int tot = 0;
// select * from (1)
for (int j = 0; j < m; j++) {
tot += piles[i- 1][j];
val.push_back(tot);
}
// Skip this column
for (int l = 0; l <= k; l++) dp[i][l] = dp[i- 1][l];
for (int j = 1; j <= m; j++) {
for (int l = k-j; l > - 1; l--)
dp[i][l+j] = max(dp[i][l+j], dp[i- 1][l] + val[j]); }}returndp[n][k]; }};Copy the codeIn general, the difficulty of this competition is not very high, the gradient is good, and it is worth our pondering and thinking. It is very recommended that you personally start to practice, there will be a harvest.
Thank you for reading, and good luck.