Leetcode 每日一题和每日一题的下一题刷题笔记 6/30

写在前面

这是我参与更文挑战的第6天，活动详情查看：更文挑战

快要毕业了，才发现自己被面试里的算法题吊起来锤。没办法只能以零基础的身份和同窗们共同加入了力扣刷题大军。我的同学们都非常厉害，他们平时只是谦虚，口头上说着自己不会，而我是真的不会。。。乘掘金鼓励新人每天写博客，我也凑个热闹，记录一下每天刷的前两道题，这两道题我精做。我打算每天刷五道题，其他的题目嘛，也只能强行背套路了，就不发在博客里了。

本人真的只是一个菜鸡，解题思路什么的就不要从我这里参考了，编码习惯也需要改进，各位如果想找刷题高手请教问题我觉得去找宫水三叶的刷题日记这位大佬比较好。我在把题目做出来之前尽量不去看题解，以免和大佬的内容撞车。

另外我也希望有得闲的大佬提供一些更高明的解题思路给我，欢迎讨论哈！

好了废话不多说开始第六天的前两道题吧！

2021.6.6 每日一题

474. 一和零

这道题一看题面就是背包问题了，没什么好说的。另外，不是说这个月是前缀和月和链表月吗，怎么每天的题思路都不一样了？

经典的背包问题，一个容量一个价值，要在有限的容量里拿到最大价值的东西。这道题很类似，这里有两个容量一个价值，要在不超过 0 的容量且不超过 1 的容量的前提下拿到最多的字符串，让子集的大小最大。一个容量一个价值的状态转移方程是 dp[i][j]，两个容量一个价值的状态转移方程是 dp[i][j][k]，这个类比一下就能得到。三个参数 i, j, k 分别代表当前正在看第 i 个字符串，当前已经使用了 j 个 0 和 k 个 1，这种情况下能取到最多字符串的数量。这里的 j 和 k 要满足 0 <= j <= m, 0 <= k <= n。当前正在看第 i 个字符串，这个字符串能不能被取上，要看剩下 0 的容量和 1 的容量能不能盛的下。设当前字符串的 0 数量为 zeros，1 的数量为 ones，如果 zeros > m - j 或 ones > n - k，那现在正在看的第 i 个字符串就不能被取上。现在的状态就和前一个状态是一样的，前一个状态写作 dp[i - 1][j][k]。如果现在这个字符串有可能被取上，那就分两种情况，取上了和没取上，具体是哪一种，要看哪一种能让当前字符串数量更多。写成公式就是 dp[i][j][k] = max{dp[i - 1][j][k], (dp[i - 1][j - zeros][k - ones] + 1)}，这个式子第一次看可能觉得有点懵，不知道有没有发现我这个状态转移方程里的状态一直在往前推，这样是不是好理解一些呢？当往前推推到一个边界点，也就是 i = 0 的时候，这个位置上没有看到字符串，字符串数量也就是 0，也就是前面说的“价值”是 0。往后推推到边界点的时候，i 是原本那个大字符串的里字符串的数量，这个时候没有办法知道 0 和 1 的容量是不是已经用完了，也没法知道现在的价值，只有往前一个状态的递推式。所以说这个题状态转移一直在往最开始那个状态走，有些背包问题状态是往结束那个位置上走，这里要和其他的题目区分开。

然后写代码，就按照这个状态转移来。


class Solution {
public:
    vector<int> get_zeros_ones(string& str) {
        vector<int> zeros_ones(2);
        int length = str.length();
        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();
        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);
                    }
                }
            }
        }
        return dp[length][m][n];
    }
};

复制代码

写完精简一下和官方题解里是一样的，截图里是官方题解的效率，我的代码还要再次一些。

后来看官方题解里面还有一个优化空间复杂度的解法，这里之前没怎么学过，积累一下。

emmm，这个解法我不太会解释，这种写法就很像信息学奥赛书上面那些写法，这样写可以无脑往上套，理解的话看好多遍就看懂了，但是不太好讲出来。我把代码粘贴到这里，你们可以看一下有什么不同


class Solution {
public:
    vector<int> getZerosOnes(string& str) {
        vector<int> zerosOnes(2);
        int length = str.length();
        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();
        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);
                }
            }
        }
        return dp[m][n];
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/ones-and-zeroes/solution/yi-he-ling-by-leetcode-solution-u2z2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

这种写法空间上省去了一个维度，因为肯定是往前一个状态转移的，所以不用记录状态这个变量了，这就和前面的“两个容量一个价值”对上了，转移方程不要写其他的变量进去。然后还有一个区别是前面的三重循环，状态变量是自增的，然后两个容量自减（正常顺序），循环内的处理是往前一个状态上看（靠状态变量控制）。后一种省空间的写法三重循环，状态变量自增，两个容量自增（倒序遍历），循环内处理往前一个状态上看（靠倒序遍历控制）。不管我怎么解释，总感觉在自我拉扯。。。

这种感觉，是熟悉的无后效性。

动态规划问题是运筹学里面的一类典型问题，这种问题共同的场景就是“无后效性”，也就是说这个问题未来的情况只和当前的决策以及未来的决策有关，和过去的决策没关系了，过去的决策影响不到了。这样一说是不是有点贝叶斯概率和马尔可夫链这些玩意的感觉了？没错，无后效性也叫马尔可夫性。过程的过去历史只能通过当前的状态去影响它未来的发展。乍一读很有哲理，其实就是很有哲理。（不过日常生活中各种情况都有，有些过去的事情不也一直影响着现在的我们嘛）

不哲理了，下一道题吧。

2021.6.6 每日一题下面的题

1472. 设计浏览器历史记录

这个题写法千奇百怪，我觉得要提高的话可以写一个双指针配合数组实现双向队列的，或者双向队列配合数组，这样这个设计题的代码就还有一定的扩展性，什么导出浏览记录按照xx排序拿到法院做证据这样的要求都能满足。


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);
 */

复制代码