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

Writing in the front

This is the 12th 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 to say start 12 days of the first two questions!

2021.6.12 One question of the day

1449. Digital cost and maximum number for target value

You don’t understand the problem, but you get the idea from the first example… I think it’s a backpack problem, and it’s not that simple. If you could write down the transition equation, you wouldn’t be able to define it all of a sudden. It’s listed? Good. This problem is done using the full backpack and the multiple backpack method. It’s not listed. Well, it’s really not a knapsack problem, it’s a knapsack problem, it’s a knapsack problem, it’s a monotone stack problem, it’s a knapsack problem, it’s a memorization problem. This prompt does not know can reflect, this problem has two sub-problems, first to get the maximum number of digits to find out, and then the cost of digit permutation combination to find the largest number of digit permutation. The first question must be the backpack problem, the back of this arbitrary, depending on personal interests, don’t overtime.

Full knapsack approach

A complete backpack is an infinite number of items, and I’m not going to do it in terms of optimizing spatial complexity a few days ago, because one less dimension is too difficult to understand.

Dp [I][j] represents the maximum integer that can be formed in the case that the total cost of the first I element types is j (the integer is a string and requires an invalid state, as in ‘#’). Did you notice that I didn’t define an array like “how many I elements are selected”? It’s too cumbersome to define such a dimension for state transitions. You can try it yourself. Therefore, the general complete backpack problem state transfer will only be transferred from two states, the first is “see but do not take, is to play”, the second is “see take, we see the follow-up”. I mentioned this idea on day 10, and you can check out the notes on day 10, which are in the reference link at the end. So I can write the state transition equation, where I starts at 1.

[\ texttt \ texttt {dp} {I}] [\ texttt {j}] = {Max} \ left \ {\ texttt {dp} [\ texttt {I} – 1] [\ texttt {j}]. \texttt{dp}[\texttt{i}][\texttt{j} – \texttt{cost}[\texttt{i}]] + \texttt{value}[\texttt{i}] \right \}

Dp [I][j] = dp[I][j] = dp[I][j] = dp[I][j] = dp[I][j] = dp[I] = dp[I] Cost [I] and value[I] are both the total cost and total value of the ith element type.

Dp [0][j] is not meaningful. Dp [0][j] is not meaningful. These states are assigned ‘#’. Then we traverse the I here is the serial number of element types, the number is increasing, so the back before the new digital must add to get the maximum value at the beginning of, here with string is easy, just the number is likely to be very big, here is a topic in give us lower the difficulty of the questions on not big integer also can use the string to save, If not, a bunch of people are going to do it with arrays, and a bunch of people are going to concatenate strings. And also, because the numbers are so big, I’m going to have to do it myself, so strings, or arrays, or queues, it’s pretty much the same idea. If the number of digits is the same as the number of digits, the size of a certain digit relationship appears, the size of the whole number relationship is determined.

The code is as follows:


class Solution {
public:
   int cost[9 + 5];
   string dp[9 + 5] [5000 + 5];
   // Return the larger of the two
   string string_max(const string &lhs, const string &rhs) {
       if (lhs.size() > rhs.size()) return lhs;
       if (rhs.size() > lhs.size()) return rhs;
       // When two strings are equal in length
       if (lhs > rhs) return lhs;
       else return rhs;
   }
   string largestNumber(vector<int>& c, int target) {
       int len = c.size(a);for (int i = 0; i < len; ++i) {
           cost[i + 1] = c[i];
       }
       // dp[I][j] represents the first I elements, which constitute the largest integer when the cost is j (integer is a string).
       // Invalid status is represented by '#'
       for (int j = 0; j <= target; ++j) {
           dp[0][j] = The '#';
       }
       dp[0] [0] = "";
       for (int i = 1; i <= 9; ++i) {
           for (int j = 0; j <= target; ++j) {
               string a, b;
               // do not select the I
               a = dp[i - 1][j];
               // Select one
               if (j - cost[i] >= 0&& dp[i][j - cost[i]] ! ="#")
                   b = std::to_string(i) + dp[i][j - cost[i]];
               dp[i][j] = string_max(a, b); }}if (dp[9][target] == "#") return "0";
       else return dp[9][target]; }}; Author: OfShare//leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/solution/xiang-xi-jiang-jie-wan-quan-b ei-bao-zhuang-tai-de-/Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.Copy the code

I don’t have a good grasp of full knapsack, so I’ll use OFShare’s problem solving code here.

In his comments section, another big guy, Sholmes9091, offered the idea that if the cost of several digits is the same, only the largest digit will be the same.


class Solution {
private:
    string MyStrCmp(const string& lhs, const string& rhs)
    {
        if (lhs.size() > rhs.size())
            return lhs; 
        else if (rhs.size() > lhs.size())
            return rhs; 
        else 
        {
            returnlhs > rhs ? lhs : rhs; }}public:
    string largestNumber(vector<int>& cost, int target) {
        // only keep the bigger digit with same cost 
        map<int.int> mp; 
        for (int i = cost.size() - 1; i >= 0; --i)
        {
            if (find_if(mp.begin(), mp.end(), 
                [&cost, i](auto& x)
                {
                    return x.second == cost[i];
                }
            ) == mp.end())
            {
                mp[i+1] = cost[i]; 
            }
        }
        
        string dp[mp.size() +1][target + 1]; 

        dp[0] [0] = ""; 
        for (int j = 1; j <= target; ++j)
        {
            dp[0][j] = "#"; 
        }

        for (auto it = mp.begin(a); it ! = mp.end(a); ++it) {int i = distance(mp.begin(), it) + 1; 
            int digit = it->first; 
            int c = it->second; 
            for (int j = 0; j <= target; ++j)
            {
                string a, b; 
                // do not pick ith digit 
                a = dp[i - 1][j]; 
                // pick one more ith digit 
                if (j - c >= 0&& dp[i][j - c] ! ="#")
                {
                    b = to_string(digit) + dp[i][j - c];
                }
                dp[i][j] = MyStrCmp(a, b); }}if (dp[mp.size()][target] == "#")
            return "0";
        else 
            return dp[mp.size()][target]; }};Copy the code

This idea is also very good, and LATER I plan to use hash table to do the same cost with the largest digit according to this idea, and test the result of this month’s brush problem.

Backpack problem step by step

All right, so I’ve given you a solution that doesn’t involve step by step, so here’s a step by step solution.

Count the number of digits of the final answer

So, let’s deal with the first subproblem. Now the state transition equation is written like this, where I starts at 0.

\texttt{dp}[\texttt{i + 1}][\texttt{j}] = {max} \left \{ \texttt{dp}[\texttt{i}][\texttt{j}], \texttt{dp}[\texttt{i + 1}][\texttt{j} – \texttt{cost}[\texttt{i}]] + 1 \right \}

This state transition equation can only be used if j≥cost[I]\texttt{j} \ge \texttt{cost}[\texttt{I}]j≥cost[I]. Failure to meet this condition is equivalent to a “see it, don’t take it, play with it” transition. I know what I know. I’m done. Now, the difference between the equation of state and the equation before is that the value becomes the number of digits in the final answer. In addition, you can’t just put something that didn’t make sense in the first place, and now the value is the number of digits in the answer, and to keep something that didn’t make sense in the first place, you just have to make it a very small negative number, and the +1 operation makes it a very small negative number.

Write the code for this section:


class Solution {
public:
    string largestNumber(vector<int> &cost, int target) {
        vector<vector<int>> dp(10, vector<int>(target + 1, INT_MIN));
        
        dp[0] [0] = 0;
        for (int i = 0; i < 9; i++) {
            int c = cost[i];
            for (int j = 0; j <= target; j++) {
                if (j < c) {
                    dp[i + 1][j] = dp[i][j];
                    
                } else {
                    if (dp[i][j] > dp[i + 1][j - c] + 1) {
                        dp[i + 1][j] = dp[i][j];
                        
                    } else {
                        dp[i + 1][j] = dp[i + 1][j - c] + 1; }}}}}};Copy the code

There’s some empty space, right? And then there’s no return value, the code hasn’t been written yet, and the empty space is what we need for the next subproblem.

Calculate the final answer

To compute the final answer, this step uses another two-dimensional array from[I + 1][j] to store where the current state came from, and this is the state transition equation again.

\texttt{from}[\texttt{i + 1}][\texttt{j}] = {\left \{ \begin{array}{ll} \texttt{j}, & \texttt{i} < \texttt{cost}[\texttt{i}] \\ \texttt{j}, & \\ \texttt{dp}[\texttt{i}][\texttt{j}] > \texttt{dp}[\texttt{i + 1}][\texttt{j} – \texttt{cost}[\texttt{i}]] + 1 \\ \texttt{j} – \texttt{cost}[\texttt{i}], & otherwise \end{array} \right.}

From [I + 1][j] == j, if yes, then it is from I, not from I + 1.

From [I + 1][j] from[I + 1][j] from[I + 1][j] from[I + 1][j] from[I + 1][j]

If you do it backwards, you have to use the first number, the first number is bigger. So when dp[I][j] == dp[I + 1][j – cos [I]], you must choose the latter one to move to the present state.

I said I was going to find a sort, but now this idea of going backwards and just adding the order to the end of the string is the biggest order.


class Solution {
public:
    string largestNumber(vector<int> &cost, int target) {
        vector<vector<int>> dp(10, vector<int>(target + 1, INT_MIN));
        vector<vector<int>> from(10, vector<int>(target + 1));
        dp[0] [0] = 0;
        for (int i = 0; i < 9; i++) {
            int c = cost[i];
            for (int j = 0; j <= target; j++) {
                if (j < c) {
                    dp[i + 1][j] = dp[i][j];
                    from[i + 1][j] = j;
                } else {
                    if (dp[i][j] > dp[i + 1][j - c] + 1) {
                        dp[i + 1][j] = dp[i][j];
                        from[i + 1][j] = j;
                    } else {
                        dp[i + 1][j] = dp[i + 1][j - c] + 1;
                        from[i + 1][j] = j - c; }}}}if (dp[9][target] < 0) {
            return "0";
        }
        string ans;
        int i = 9, j = target;
        while (i > 0) {
            if (j == from[i][j]) {
                i--;
            } else {
                ans += '0'+ i; j = from[i][j]; }}returnans; }};Copy the code

This method is easy to understand, the forward and backward to separate storage, speaking is not twisted.

But, according to my notes the other day, there must be a way to reduce space complexity, and reduce space complexity by eliminating the current I digit. Each step is to find its own source, the case that dp[j] == dp[j-cost [I]] is true is directly transferred from dp[j-cost [I]].


class Solution {
public:
    string largestNumber(vector<int> &cost, int target) {
        vector<int> dp(target + 1, INT_MIN);
        dp[0] = 0;
        for (int c : cost) {
            for (int j = c; j <= target; j++) {
                dp[j] = max(dp[j], dp[j - c] + 1); }}if (dp[target] < 0) {
            return "0";
        }
        string ans;
        for (int i = 8, j = target; i >= 0; i--) {
            for (int c = cost[i]; j >= c && dp[j] == dp[j - c] + 1; j -= c) {
                ans += '1'+ i; }}returnans; }};Copy the code

Again, leave a hole for yourself to fill in, save space but not step by step solution that I’ll add to the full backpack in front of you later.

One of the following questions per day

I feel like I’ve done three or four problems… I’m having a little brain twitch right now.

The flow of people in the stadium

Force buckle gave me a random plug a MYSQL question, ah can’t, if the interview is also so do not know if I interview is not a play, feel I switch between languages before shake a little long ah.

I still refer to the big guy’s idea to do this problem, the official problem solution is not universal, after reading the comment section found this idea:


with t1 as (
select
    id,
    visit_date,
    people,
Select * from 'rank'; select * from 'rank'
    id-rank(a)over(order by id) rk
from stadium
where people >= 100
)
select
    id,
    visit_date,
    people
from t1
# where filter if the number of entries is greater than 3
where rk in (
select rk from t1 group by rk having count(1) > =3);

# 作者：bryce-28
# link: https://leetcode-cn.com/problems/human-traffic-of-stadium/solution/da-shu-ju-fang-xiang-xia-ci-ti-jie-ti-si-lu-by-bry/
# Source: LeetCode
# Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Copy the code

In the direction of big data, the first time to solve the problem of continuity is to open a window to calculate the difference. Select * from people > 100; select * from people > 100; select * from people > 100; If it’s continuous then the difference must be the same. Filter out the number of bars greater than or equal to 3, and finish the problem.

The big guy’s code runs terrifyingly fast.

summary

Complete knapsack problem or step by step to solve the knapsack problem, after the window to find the difference

Refer to the link

🍭 🍭 🍭

I really should generalize like they did, but I didn’t do enough.

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

Mysql implements functions similar to windowing functions

12.21 the Window Functions provides

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

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

Writing in the front

2021.6.12 One question of the day

Full knapsack approach

Backpack problem step by step

Count the number of digits of the final answer

Calculate the final answer

One of the following questions per day

summary

Refer to the link

Related Posts

What? Don’t you know about these free and useful MySQL clients?

Interpreting the Service Grid 2021: Farewell to architecture “Great Leap Forward” and a hundred schools of Thought contend for technology ecology

The index of MySQL