Leetcode Contest 30 | 叶某人的碎碎念

今晚参加了一个朋友的婚前庆祝party。看着朋友幸福也是一种幸福的享受。希望我的幸福来得更早一些 😆

今晚的比赛也一次没WA地过了。前面三题是用 C++ 写的，最后一题实在觉得 C++ 麻烦，还是换了用python写。

第一题Reshape the Matrix

题目大意：给定一个矩阵，将其变成r行c列的矩阵。如果不能转换，则返回原矩阵。

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int n = nums.size();
        if (n==0) return nums;
        int m = nums[0].size();
        if (m==0) return nums;
        if (n*m != r*c) return nums;
        vector<vector<int>> ans(r, vector<int>(c, 0));
        int a = 0, b = 0;
        for (auto row: nums)
            for (auto n: row) {
                ans[a][b] = n;
                b ++;
                if (b == c) {
                    b = 0;
                    a ++;
                }
            }
        return ans;
    }
};

第二题Subarray Sum Equals K

题目大意：给定一个数组nums和k，找出和为k的连续子数组的个数。

假设nums的前缀和为s，也就令s[-1]=0，并且对i>=0，

s[i] = nums[0]+...+nums[i]
那么我们要找的下面这个集合元素的个数。
{(i, j): 0 &lt=i &lt=j &lt nums.size(), s[j]-s[i-1]=k}
我们现在可以在O(n²)的时间内暴力枚举，其中n为nums的长度，最大为20000。C++的话应该会过的。

如果我们换个角度看的话，其实可以在O(n)时间内求解。对于s[j]，我们关心的是s[j]-k在s[-1], s[0], ..., s[j]中出现的次数，所以我们可以用一个哈希表统计它们出现的次数。这样对于固定的j，我们就可以在O(1)的时间内求出满足条件的(i, j)的个数。实现如下。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int s = 0, ans = 0;
        cnt[0] = 1;
        for (int n: nums) {
            s += n;
            ans += cnt[s-k];
            cnt[s] ++;
        }
        return ans;
    }
};

第三题Permutation in String

题目大意：给定两个字符串s1和s2，问s1是不是s2某个子字符串的一个置换。

关键的想法是两个字符串是互为置换当且仅当它们有相同的字符集。所以我们只要看s2中有没有一个与s1长度一样的子字符串，使得它与s1有同样的字符集。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<char> v1(26, 0), v2(26, 0);
        int n = s1.length(), m = s2.length();
        if (n>m) return false;
        for (auto c: s1) v1[c-'a'] ++;
        for (int i=0; i<n; i++)
            v2[s2[i]-'a'] ++;
        if (v1==v2) return true;
        for (int i=n; i<m; i++)
        {
            v2[s2[i]-'a'] ++;
            v2[s2[i-n]-'a'] --;
            if (v1==v2) return true;
        }
        return false;
    }
};

第四题Maximum Vacation Days

题目大意：给定一个有N个顶点：顶点0, ..., 顶点N-1的图。这个图用01矩阵flights来表示。days是一个N*K的矩阵，其中days[i][j]表示第j步来到第i个顶点获得的值。现在我们从顶点0出发走K步（允许停留），求能获得的值的最大之和。

这是图上的动态规划。假设dp(i, j)表示第j步到达顶点i的最优值，需要注意的是我使用的j是从0到K－1的。

转移方程：

dp(i, j) = max(dp(i, j+1)+days[i][j+1]; dp(x, j+1)+days[x][j+1])
其中x要遍历所有满足flight[i][x]=1的顶点。

边界条件：对于任意的顶点i，dp(i, K-1) = 0

对于第0步，我们可以选择留在顶点0，也可以选择走到跟顶点0相邻的顶点。在考虑所有这些有可能的选择，我们求出每种选择的最优解，然后在这些最优解中找到最大值就行。

下面是我比较喜欢的递归实现。循环迭代的实现应该更优，因为递归的层数限制在数据比较大时很容易超出，而用循环可以避免这个问题。

class Solution(object):
    def maxVacationDays(self, flights, days):
        """
        :type flights: List[List[int]]
        :type days: List[List[int]]
        :rtype: int
        """
        n = len(flights)
        k = len(days[0])

        def dp(i, j, mf):
            if j==k-1:
                return 0;
            if (i, j) in mf:
                return mf[i, j]
            ans = dp(i, j+1, mf) + days[i][j+1]
            for x, b in enumerate(flights[i]):
                if b==1:
                    ans = max(ans, dp(x, j+1, mf)+days[x][j+1])
            mf[i, j] = ans
            return ans

        mf = {}
        ans = dp(0, 0, mf) + days[0][0]
        for x, b in enumerate(flights[0]):
            if b==1:
                ans = max(ans, dp(x, 0, mf)+days[x][0])
        return ans

leetcode contest