LeetCode 第 298 场周赛

发布时间:2023-04-16 08:30

前言

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

一、题目

题目 难度
5242. 兼具大小写的最好英文字母 ⭐️
5218. 个位数字为 K 的整数之和 ⭐️⭐️
6099. 小于等于 K 的最长二进制子序列 ⭐️⭐️⭐️
5254. 卖木头块 ⭐️⭐️⭐️

二、算法思路

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

        题目理解:对于每一个大写的字母,如果其小写字母也出现在字符串中,那么认为它是一个 美好英文字母 ,返回较大的一个,如果不存在返回 ""
        (1)建一个哈希表,记录字符串中出现的字母。
        (2)从 Z-A 遍历答案,查询哈希表中是否同时存在 大小写 字母,是则返回当前的字母。
        时间复杂度: O ( n ) O(n) 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 k_i ki 的和为 num,那么 ∑ 1 n k i = n u m \sum^n_1{k_i}=num 1nki=num,即 ( n ∗ k − n u m ) % 10 = 0 (n*k-num)\%10=0 (nknum)%10=0。(单独将 个位数 拎出来考虑,其他位数看情况添加,只要保证个位数的合理性,那么就可以找到答案。由于是 10 进制的,所以 n 的可能最大值为 10
        (1)因为每个数都是正整数,如果 num 为 0,那么最小答案为0,因为空集的和为 0;
        (2)遍历 1-10,如果 i*knum 同余,那么返回答案,如果 n u m − i ∗ k < 0 num-i*k<0 numik<0,说明没有解。
        时间复杂度: O ( n ) O(n) 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 ) O(n) 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 ] f[i,j] f[i,j]
    • 集合描述:所有高为 i ,宽为 j 的板子的分割集合。
    • 集合属性:最大值。
  • 状态转移: f [ i , j ] = m a x ( f [ k ] [ j ] + f [ i − k ] [ j ] , f [ i ] [ k ] + f [ i ] [ m − k ] ) f[i,j]=max(f[k][j]+f[i-k][j],f[i][k]+f[i][m-k]) f[i,j]=max(f[k][j]+f[ik][j],f[i][k]+f[i][mk])
            (1)对于切割高为 i ,宽为 j 的板子,集合的切割方案为行从 1~n,列从 1~m,从中挑选最大的板子分割。由于行列分割互不干扰,所以需要对两个方案求最大值。
            时间复杂度: O ( n 3 ) O(n^3) O(n3)
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。一看到是图论,我就脑阔疼,数学原理相关通常想不出来解决方法。接下来的目标,把图论相关的题感刷上来,然后就是要开始复习,每天都要学习点新的东西,最后是逼迫自己自律,最近作息有点混。

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号