Leetcode复盘|LeetCode 第 298 场周赛算法|职场和发展|leetcode

前言 【Leetcode复盘|LeetCode 第 298 场周赛】随缘复盘各种比赛，主要是 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 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 ∑1n?ki?=num，即( n ? k ? n u m ) % 10 = 0 (n*k-num)\%10=0 (n?k?num)%10=0。（单独将个位数拎出来考虑，其他位数看情况添加，只要保证个位数的合理性，那么就可以找到答案。由于是 10 进制的，所以 n 的可能最大值为 10）
（1）因为每个数都是正整数，如果 num 为 0，那么最小答案为0，因为空集的和为 0；
（2）遍历 1-10，如果 i*k 和 num 同余，那么返回答案，如果n u m ? i ? k < 0 num-i*k<0 num?i?k<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[i?k][j],f[i][k]+f[i][m?k])
（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>& prices) { vector> f(n + 1, vector(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。一看到是图论，我就脑阔疼，数学原理相关通常想不出来解决方法。接下来的目标，把图论相关的题感刷上来，然后就是要开始复习，每天都要学习点新的东西，最后是逼迫自己自律，最近作息有点混。