LeetCode 第 298 场周赛

前言

        随缘复盘各种比赛，主要是 leetcode，CodeForces，AtCode 等等的一些比赛。菜鸡一个，基本只能过签到题，剩余的题目会尽可能的理解然后再些出来。
       比赛场次：LeetCode 第 298 场周赛
        

一、题目

二、算法思路

1、兼具大小写的最好英文字母

        题目理解：对于每一个大写的字母，如果其小写字母也出现在字符串中，那么认为它是一个 美好英文字母 ，返回较大的一个，如果不存在返回 ""。
        （1）建一个哈希表，记录字符串中出现的字母。
        （2）从 Z-A 遍历答案，查询哈希表中是否同时存在 大小写 字母，是则返回当前的字母。
        时间复杂度：$O(n)$

class Solution {
public:
    string greatestLetter(string s) {
        set<char> st;
        for (auto& x: s)
            st.insert(x);
        for (char i = 'Z'; i >= 'A'; i --) {
            if (st.count(i) && st.count(i + 32))
                return string(1, i);
        }
        return "";
    }
};

2、个位数字为 K 的整数之和

        题目理解：选取最小个个位数是 k 的和为 num 的个数。假设 n 个以 k 结尾的数 $k_i$ 的和为 num，那么 ${\sum }_1^n{k}_i=num$，即 $(n\ast k-num)\%10=0$。（单独将 个位数 拎出来考虑，其他位数看情况添加，只要保证个位数的合理性，那么就可以找到答案。由于是 10 进制的，所以 n 的可能最大值为 10）
        （1）因为每个数都是正整数，如果 num 为 0，那么最小答案为0，因为空集的和为 0；
        （2）遍历 1-10，如果 i*k 和 num 同余，那么返回答案，如果 $num-i\ast k<0$，说明没有解。
        时间复杂度：$O(n)$

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        for (int i = 1; i <= 10; i++) {
            if (num - i * k < 0) break;
            if ((num - i * k) % 10 == 0)
                return i;
        }
        return -1;
    }
};

3、小于等于 K 的最长二进制子序列

        题目理解：求子序列对应二进制数字小于等于 k 的最大长度，沃的建议是直接贪。
        （1）首先将数字 k 转换成对应的二进制序列 t。
        （2）对于两个字符串s，t：
                1、如果 t 的长度小于 s 的长度，那么字符串 s 对应的二进制数字严格小于 k，直接返回 s 的长度。
                2、对于字符串 s 前 n-m 个字符串的序列（n 为 s 的长度，m 为 t 的长度），其可加到答案中的最大长度是 字符为 0 的个数；
                3、对于字符串 s 后 m 个字符串，如果比 t 大，那么取长度 m - 1，否则取 m；
                4、返回答案为步骤 2、3 的和。
        时间复杂度：$O(n)$

class Solution {
public:
    int longestSubsequence(string s, int k) {
        string t;
        while (k) t += to_string(k % 2), k /= 2;
        reverse(t.begin(), t.end());
        int n = s.size(), m = t.size();
        if (n < m) return n;
        int ans = m;
        if (s.substr(n - m) > t) ans --;
        for (int i = n - m - 1; i >= 0; i --)
            if (s[i] == '0') ans ++;
        return ans;
    }
};

4、卖木头块

        题目理解：经典棋盘分割问题的简化问题。

• 集合表示：$f[i,j]$
  • 集合描述：所有高为 i ，宽为 j 的板子的分割集合。
  • 集合属性：最大值。
• 状态转移：$f[i,j]=max(f[k][j]+f[i-k][j],f[i][k]+f[i][m-k])$
          （1）对于切割高为 i ，宽为 j 的板子，集合的切割方案为行从 1~n，列从 1~m，从中挑选最大的板子分割。由于行列分割互不干扰，所以需要对两个方案求最大值。
          时间复杂度：$O(n^3)$

typedef long long LL;

class Solution {
public:
    long long sellingWood(int n, int m, vector<vector<int>>& prices) {
        vector<vector<LL>> f(n + 1, vector<LL>(m + 1));
        for (auto& p:prices) {
            int h = p[0], w = p[1], v = p[2];
            f[h][w] = v;
        }

        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                for (int k = 1; k < i; k ++) {
                    f[i][j] = max(f[i][j], f[k][j] + f[i - k][j]);
                }
                for (int k = 1; k < j; k ++) {
                    f[i][j] = max(f[i][j], f[i][k] + f[i][j - k]);
                }
            }
        }
        return f[n][m];
    }
};

结语

        经过这么多场的比赛，沃有被自己给蠢到，最近几天都是只出 1~2 道题，有的甚至不能出题。总结一下，发现最近出的题图论跟数学原理相关的题目相对多，leetcode，cf，atcoder。一看到是图论，我就脑阔疼，数学原理相关通常想不出来解决方法。接下来的目标，把图论相关的题感刷上来，然后就是要开始复习，每天都要学习点新的东西，最后是逼迫自己自律，最近作息有点混。