【周赛复盘】LeetCode第298场单周赛 一时失言乱红尘 2023-09-28 11:10 141阅读 0赞 #### 目录 #### * 1、兼具大小写的最好英文字母 * * 1)题目描述 * 2)原题链接 * 3)思路解析 * 4)模板代码 * 5)算法与时间复杂度 * 2、个位数字为 K 的整数之和 * * 1)题目描述 * 2)原题链接 * 3)思路解析 * 4)模板代码 * 5)算法与时间复杂度 * 3、小于等于 K 的最长二进制子序列 * * 1)题目描述 * 2)原题链接 * 3)思路解析 * 4)模板代码 * 5)算法与时间复杂度 * 4、卖木头块 * * 1)题目描述 * 2)原题链接 * 3)思路解析 * 4)模板代码 * 5)算法与时间复杂度 * 5、周赛总结 ## 1、兼具大小写的最好英文字母 ## ### 1)题目描述 ### > 给你一个由英文字母组成的字符串 `s` ,请你找出并返回 `s`中的 **最好** 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母,则返回一个空字符串。 > **最好** 英文字母的大写和小写形式必须 **都** 在 `s` 中出现。 > 英文字母 `b` 比另一个英文字母 `a` **更好** 的前提是:英文字母表中,`b` 在 `a` 之 **后** 出现。 ### 2)原题链接 ### > [LeetCode.5242:兼具大小写的最好英文字母 > ][LeetCode.5242_] ### 3)思路解析 ### * ( 1 ) (1) (1)简单的模拟题,判断某个字母的大小写是否同时出现在字符串中即可,字典序越大的优先级越高。考虑使用字符映射去记录即可。下面我使用的是`int`数组去记录,题目只要求是否存在,使用`boolean`数组也可。 ### 4)模板代码 ### class Solution { int[] a=new int[26]; int[] b=new int[26]; public String greatestLetter(String s) { char[] str=s.toCharArray(); for (int i = 0; i < str.length; i++) { char c=str[i]; if('a'<=c&&c<='z') a[c-'a']++; else if ('A'<=c&&c<='Z') b[c-'A']++; } String ans=""; for (int i = 0; i < 26; i++) { if (a[i]!=0&&b[i]!=0){ ans=(char)(i+'A')+""; } } return ans; } } ### 5)算法与时间复杂度 ### 算法:**模拟** 时间复杂度:遍历一次字符串,复杂度为 O ( n ) O(n) O(n)。 ## 2、个位数字为 K 的整数之和 ## ### 1)题目描述 ### > 给你两个整数 `num`和 `k` ,考虑具有以下属性的正整数多重集: > > * 每个整数个位数字都是 `k`。 > * 所有整数之和是 `num` 。 > 返回该多重集的最小大小,如果不存在这样的多重集,返回 `-1` 。 > **注意:** > * 多重集与集合类似,但多重集可以包含多个同一整数,空多重集的和为 0 。 > * **个位数字** 是数字最右边的数位。 ![在这里插入图片描述][e3cef73cef0b4b2e8df569add62374ea.png] ### 2)原题链接 ### > [LeetCode.5218:个位数字为 K 的整数之和 > ][LeetCode.5218_ K _] ### 3)思路解析 ### * ( 1 ) (1) (1)可以很明显发现,假设我们数组中放了 n n n个数,这 n n n个数的和为 n u m num num,且每个数的个位数都为 k k k,那么我们很明显发现需要满足下面这个等式: n u m % 10 = ( n ∗ k ) % 10 num\\%10=(n\*k)\\%10 num%10=(n∗k)%10 * ( 2 ) (2) (2)这是因为 n u m num num的个位只由这 n n n个数的个位之和的个位数决定,而 n n n个数的个位数都是已知 k k k,所以我们需要去枚举到最小的 n n n,使得满足上述的等式,此时 n n n即为答案。 * ( 3 ) (3) (3)对于 n u m num num为 0 0 0需要特判一下,当相乘的数进入循环后说明没有找到答案直接返回`-1`。比如 `2`无论和谁相乘,答案的个位数永远都是`02468`,判断到重复说明不可能组成题意要求的。当然的过程中也需要保证 k ∗ n < = n u m k\*n<=num k∗n<=num ### 4)模板代码 ### class Solution { public int minimumNumbers(int num, int k) { //特判 if(num==0) return 0; if(k>num) return -1; //s是我们需要找的数字 int s=num%10; Set<Integer> set=new HashSet<>(); //区间足够大即可 for (int i = 1; i <3000; i++) { int g=k*i; //不能超过num if(g>num) return -1; //找到答案 if (g%10==s) return i; //找完了,没找到答案返回-1 if (!set.add(g%10)) return -1; } //无法到达的步骤 return -1; } } class Solution { public int minimumNumbers(int num, int k) { if (num == 0) { return 0; } for (int i = 1, j = num - k; i <= 10 && j >= 0; i++, j -= k) { if (j % 10 == 0) { return i; } } return -1; } } ### 5)算法与时间复杂度 ### 算法:**数学** 时间复杂度:结论题,不需要多少时间,视为 O ( 1 ) 。 O(1)。 O(1)。 ## 3、小于等于 K 的最长二进制子序列 ## ### 1)题目描述 ### > 给你一个二进制字符串 `s` 和一个正整数 `k` 。 > 请你返回 s 的 **最长** 子序列,且该子序列对应的 **二进制** 数字小于等于 `k` 。 > 注意: > > * 子序列可以有 **前导 0 。** > * 空字符串视为 `0` 。 > * **子序列** 是指从一个字符串中删除零个或者多个字符后,不改变顺序得到的剩余字符序列。 ### 2)原题链接 ### > [LeetCode.5218:小于等于 K 的最长二进制子序列 > ][LeetCode.5218_ K _ 1] ### 3)思路解析 ### * ( 1 ) (1) (1)考虑一个二进制字符串,如`1000110`,它的十进制应该是: ( 1000110 ) 2 = 2 1 + 2 2 + 2 6 (1000110)\_2=2^1+2^2+2^6 (1000110)2=21\+22\+26 从右往左的每个 1 1 1所代表的值分别是 2 1 2^1 21、 2 2 2^2 22、 2 6 2^6 26,幂数为它们从右往左数的下标(从`0`开始)。 * ( 2 ) (2) (2)由于题意说可以包含前导`0`,我们可知它并不会影响我们`1`的位置让我们的二进制数变大,但后面的`0`会导致`1`的位置向左移动导致值变大。比如`0000001000110`并不大,`1000011000000`却非常大。 * ( 3 ) (3) (3)从贪心的角度出发,为了选出更多的前导`0`以及让每个`1`的价值尽可能小,我们从末尾开始选择,对于每个`0`我们直接计入答案,对于每个`1`我们去判断加上它当前的价值和是否超出`k`,如果不超则加上否则不加。 * ( 4 ) (4) (4)注意精度问题, 2 30 2^\{30\} 230就已经接近超出`int`,所以需要判断,`k`的最大值也仅达到 1 0 9 10^9 109。 ### 4)模板代码 ### class Solution { public int longestSubsequence(String s, int k) { char[] c=s.toCharArray(); int ans=0; int res=0; int pre=0; for (int i = c.length-1; i >=0; i--) { if (c[i]=='1'&&pre<=30){ int h=(int)Math.pow(2,pre); if (ans+h<=k){ ans+=h; res++; } }else if(c[i]=='0') res++; pre++; } return res; } } ### 5)算法与时间复杂度 ### 算法:**贪心** 时间复杂度:遍历了一遍字符串,复杂度为 O ( n ) O(n) O(n)。 ## 4、卖木头块 ## ### 1)题目描述 ### > 给你两个整数 `m` 和 `n` ,分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 `prices` ,其中 `prices[i] = [hi, wi, pricei]` 表示你可以以 `pricei` 元的价格卖一块高为 `hi` 宽为 `wi` 的矩形木块。 > 每一次操作中,你必须按下述方式之一执行切割操作,以得到两块更小的矩形木块: * 沿垂直方向按高度 **完全** 切割木块,或 * 沿水平方向按宽度 **完全** 切割木块 > 在将一块木块切成若干小木块后,你可以根据 `prices` 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 **不能** 旋转切好后木块的高和宽。 > 请你返回切割一块大小为 `m x n` 的木块后,能得到的 最多 钱数。 > 注意你可以切割木块任意次。 > ![在这里插入图片描述][8aca313cb4184094bd512295e90a614e.png] ### 2)原题链接 ### > [LeetCode.5254:卖木头块 > ][LeetCode.5254_] ### 3)思路解析 ### * ( 1 ) (1) (1)不难发现,每个木块都是矩阵,且每个木块的价值只与高和宽有关,与位置无关,且矩阵切割后仍然为矩阵。从 d p dp dp角度出发。 * ( 2 ) (2) (2)定义 d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\]的含义为高为 i i i,宽为 j j j的木块可卖出的最大价值。对于任意一块高为 i i i宽为 j j j矩形木块我们可以枚举切割位置,我们可以按位置 \[ 1 , i − 1 \] \[1,i-1\] \[1,i−1\]切割为两块矩阵,也可以按宽 \[ 1 , j − 1 \] \[1,j-1\] \[1,j−1\]切割为两块矩阵。还需要考虑是否可以不切割直接进行售卖,三者取最大值。所以转移方程为 f \[ i \] \[ j \] = max k = 1 i − 1 f \[ k \] \[ j \] + f \[ i − k \] \[ j \] f\[i\]\[j\]=\\max \_\{k=1\}^\{i-1\} f\[k\]\[j\]+f\[i-k\]\[j\] f\[i\]\[j\]=k=1maxi−1f\[k\]\[j\]\+f\[i−k\]\[j\] f \[ i \] \[ j \] = max k = 1 j − 1 f \[ i \] \[ k \] + f \[ i \] \[ j − k \] f\[i\]\[j\]=\\max \_\{k=1\}^\{j-1\} f\[i\]\[k\]+f\[i\]\[j-k\] f\[i\]\[j\]=k=1maxj−1f\[i\]\[k\]\+f\[i\]\[j−k\] ### 4)模板代码 ### class Solution { int N=210; long[][] f=new long[N][N]; long[][] map=new long[N][N]; public long sellingWood(int m, int n, int[][] prices) { for (int[] p:prices){ map[p[0]][p[1]]=p[2]; } for (int i = 1; i <=m; i++) { for (int j = 1; j <=n; j++) { f[i][j]=map[i][j]; for (int k = 1; k <i; k++) { f[i][j]=Math.max(f[i][j],f[k][j]+f[i-k][j]); } for (int k = 1; k <j; k++) { f[i][j]=Math.max(f[i][j],f[i][k]+f[i][j-k]); } } } return f[m][n]; } } ### 5)算法与时间复杂度 ### 算法:**dp** 时间复杂度: O ( m n ( n + m ) ) O(mn(n+m)) O(mn(n\+m)) ## 5、周赛总结 ## 第四题没动脑,我是 s b sb sb。 [LeetCode.5242_]: https://leetcode.cn/problems/greatest-english-letter-in-upper-and-lower-case/ [e3cef73cef0b4b2e8df569add62374ea.png]: https://img-blog.csdnimg.cn/e3cef73cef0b4b2e8df569add62374ea.png [LeetCode.5218_ K _]: https://leetcode.cn/problems/sum-of-numbers-with-units-digit-k/ [LeetCode.5218_ K _ 1]: https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k/ [8aca313cb4184094bd512295e90a614e.png]: https://img-blog.csdnimg.cn/8aca313cb4184094bd512295e90a614e.png [LeetCode.5254_]: https://leetcode.cn/problems/selling-pieces-of-wood/
相关 【周赛复盘】LeetCode第80场双周赛 目录 1、强密码检验器 II 1)题目描述 2)原题链接 3)思路解析 4)模板代码 5)算法与 太过爱你忘了你带给我的痛/ 2023年10月01日 22:07/ 0 赞/ 19 阅读
相关 【周赛复盘】LeetCode第296场单周赛 目录 1、极大极小游戏 1)题目描述 2)原题链接 3)思路解析 4)模板代码 5)算法与时间复 悠悠/ 2023年10月01日 22:04/ 0 赞/ 26 阅读
相关 【周赛复盘】力扣第 312 场单周赛 1.按身高排序 1)题目描述 给你一个字符串数组 `names` ,和一个由 互不相同 的正整数组成的数组 `heights` 。两个数组的长度均为 `n` 。 偏执的太偏执、/ 2023年09月28日 23:11/ 0 赞/ 11 阅读
相关 【周赛复盘】力扣第 85 场双周赛 目录 1. 得到 K 个黑块的最少涂色次数 1)题目描述 2)原题链接 3)思路解析 4)模板代码 ╰+哭是因爲堅強的太久メ/ 2023年09月28日 21:26/ 0 赞/ 44 阅读
相关 【周赛复盘】力扣第 305 场单周赛 目录 1.算术三元组的数目 1)题目描述 2)原题链接 3)思路解析 4)模板代码 5)算法与时 忘是亡心i/ 2023年09月28日 18:58/ 0 赞/ 9 阅读
相关 【周赛复盘】LeetCode第304场单周赛 目录 1.使数组中所有元素都等于零 1)题目描述 2)原题链接 3)思路解析 4)模板代码 5) ゝ一世哀愁。/ 2023年09月28日 17:44/ 0 赞/ 43 阅读
相关 【周赛复盘】LeetCode第81场双周赛 目录 1、统计星号 1)题目描述 2)原题链接 3)思路解析 4)模板代码 5)算法与时间复杂度 悠悠/ 2023年09月28日 12:12/ 0 赞/ 31 阅读
相关 【周赛复盘】LeetCode第298场单周赛 目录 1、兼具大小写的最好英文字母 1)题目描述 2)原题链接 3)思路解析 4)模板代码 5) 一时失言乱红尘/ 2023年09月28日 11:10/ 0 赞/ 142 阅读
还没有评论,来说两句吧...