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

Writing in the front

This is the sixth day of my participation in the More text Challenge. For 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!

Okay, no more nonsense, let’s start the first two questions of the sixth day!

2021.6.6 One question daily

474. One and zero

This problem a look at the problem is the backpack problem, nothing to say. In addition, it is not said that this month is a prefix and month and list month, how every day the idea is different?

The classic backpack problem, a capacity a value, to get the maximum value in a limited capacity. This is a very similar problem, where you have two capacities and you have a value, and you want to get the maximum number of strings without having more than zero capacity and less than one capacity, to maximize the size of the subset. The state transition equation of one capacity and one value is DP [I][j], and the state transition equation of two capacities and one value is DP [I][J][k]. This can be obtained by analogy. The three arguments I, j, and k represent the ith string that you are looking at, and j zeros and K ones have been used. The maximum number of strings that can be retrieved in this case. Here j and k have to be 0 <= j <= m, 0 <= k <= n. We are currently looking at the ith string, can this string be taken up, to see the capacity of the remaining 0 and the capacity of the 1 can be held down. If zeros > m-j or ones > n-k, then the i-th string you are looking at cannot be picked up. The present state is the same as the previous state, which is written dp[i-1][j][k]. Now, if it’s possible for this string to be taken up, there are two cases, the sum is taken up and the sum is not taken up, depending on which one makes the current string more numerous. Written formula is dp [I] [j] [k] = Max {dp [I – 1) [j] [k], [dp] [I – 1 [j – zeros) – ones] [k + 1)}, the formulas for the first time see may feel a little meng, I wonder if you notice that the states in my state transition equation are moving forward, so does that make sense? When we push forward to a boundary point where I = 0, we don’t see any strings at that point, so the number of strings is 0, and the “value” is 0. When you push back to the boundary point, where I is the number of strings in the original large string, there is no way to know whether the capacity of 0 and 1 has been used up, and there is no way to know what their value is now, only the recursion of the previous state. So this is a problem where you’re moving back to where you started, and some of the backpack problems are moving back to where you ended up, and this is a little bit different from the other problems.

And then you write your code, and you’re going to follow that state.

class Solution {
public:
    vector<int> get_zeros_ones(string& str) {
        vector<int> zeros_ones(2);
        int length = str.length(a);for (int i = 0; i < length; i++) {
            zeros_ones[str[i] - '0'] + +; }return zeros_ones;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        int length = strs.size(a); vector<vector<vector<int>>> dp(length + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
        for (int i = 1; i <= length; i++) {
            vector<int>&& zeros_ones = get_zeros_ones(strs[i - 1]);
            int zeros = zeros_ones[0], ones = zeros_ones[1];
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= zeros && k >= ones) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1); }}}}returndp[length][m][n]; }};Copy the code

It is the same as in the official problem solving after writing, the screenshot is the efficiency of the official problem solving, and my code will be some again.

Then look at the official problem there is a solution to optimize the complexity of space, here before did not learn how to accumulate.

Emmm, this solution I will not explain, this writing method is very like the information science Orsaishu above those writing method, this writing can be no brain to set, understand the word look at many times to understand, but not very good to speak out. I’m going to paste the code here, so you can see what’s the difference

class Solution {
public:
    vector<int> getZerosOnes(string& str) {
        vector<int> zerosOnes(2);
        int length = str.length(a);for (int i = 0; i < length; i++) {
            zerosOnes[str[i] - '0'] + +; }return zerosOnes;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        int length = strs.size(a); vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i < length; i++) {
            vector<int>&& zerosOnes = getZerosOnes(strs[i]);
            int zeros = zerosOnes[0], ones = zerosOnes[1];
            for (int j = m; j >= zeros; j--) {
                for (int k = n; k >= ones; k--) {
                    dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1); }}}returndp[m][n]; }}; Author: Leetcode-Solution//leetcode-cn.com/problems/ones-and-zeroes/solution/yi-he-ling-by-leetcode-solution-u2z2/Copyright belongs to the author. Commercial reprint please contact the author to obtain authorization, non-commercial reprint please indicate the source.Copy the code

This writing method eliminates one dimension in space, because it must be the previous state transition, so there is no need to record the state variable, which corresponds to the previous “two capacities and one value”, and the transition equation does not include other variables. Another difference is that in the previous triple loop, the state variables are incremented, and then the two capacities are decrement (in normal order), and the processing within the loop is based on the previous state (controlled by the state variables). The latter type of space-saving writing method is triple loop, state variables increase, two capacity increase (reverse traversal), loop processing on the previous state (by reverse traversal control). No matter how I explain it, it feels like I’m pulling myself…

This feeling is familiar without aftereffect.

Dynamic programming problem is a kind of typical problems in operations research. The common scenario of this problem is “no aftereffect”, that is to say, the future situation of this problem is only related to the current decision and the future decision, and the past decision has nothing to do with the past decision, the past decision has no influence. Doesn’t that sound a little bit like Bayesian probability and Markov chains? Yeah, no aftereffect is also called Markov. The past history of a process can only affect its future development through its present state. It reads philosophic, but it is. (But there are all kinds of situations in daily life, and there are some things in the past that still affect us in the present.)

No more philosophy. Let’s do the next question.

2021.6.6 One question per day

Design browser history

This question writing method is strange, I think to improve the words can write a double pointer with array bidirectional queue, or bidirectional queue with array, so that the design of the code there is a certain extensibility, what export browsing records in accordance with xx sort to get the court to do evidence such requirements can meet.

class BrowserHistory {
public:
    BrowserHistory(string homepage) {
        history.push_back(homepage);
    }

    void visit(string url) {
        history.resize(++cur);
        history.push_back(move(url));
    }

    string back(int steps) {
        return history[cur = max(0, cur - steps)];
    }

    string forward(int steps) {
        cur = min((int)history.size() - 1, cur + steps);
        return history[cur];
    }

private:
    vector<string> history;
    int cur = 0;
};

/** * Your BrowserHistory object will be instantiated and called as such: * BrowserHistory* obj = new BrowserHistory(homepage); * obj->visit(url); * string param_2 = obj->back(steps); * string param_3 = obj->forward(steps); * /

Copy the code

summary

0-1 backpack problem, no aftereffect, backpack problem space optimization, array simulation stack of a variety of gameplay

Refer to the link

Analysis of dynamic programming — 0-1 knapsack problem