目录
- 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)题目描述
给你一个由英文字母组成的字符串2)原题链接s
,请你找出并返回s
中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母,则返回一个空字符串。
最好 英文字母的大写和小写形式必须 都 在s
中出现。
英文字母b
比另一个英文字母a
更好 的前提是:英文字母表中,b
在a
之 后 出现。
LeetCode.5242:兼具大小写的最好英文字母3)思路解析
- ( 1 ) (1) (1)简单的模拟题,判断某个字母的大小写是否同时出现在字符串中即可,字典序越大的优先级越高。考虑使用字符映射去记录即可。下面我使用的是
int
数组去记录,题目只要求是否存在,使用boolean
数组也可。
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 。
- 个位数字 是数字最右边的数位。
文章图片
2)原题链接
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
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 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)题目描述
给你一个二进制字符串2)原题链接s
和一个正整数k
。
请你返回 s 的 最长 子序列,且该子序列对应的 二进制 数字小于等于k
。
注意:
- 子序列可以有 前导 0 。
- 空字符串视为
0
。- 子序列 是指从一个字符串中删除零个或者多个字符后,不改变顺序得到的剩余字符序列。
LeetCode.5218:小于等于 K 的最长二进制子序列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。
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
的矩形木块。
每一次操作中,你必须按下述方式之一执行切割操作,以得到两块更小的矩形木块:
- 沿垂直方向按高度 完全 切割木块,或
- 沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后,你可以根据2)原题链接prices
卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。
请你返回切割一块大小为m x n
的木块后,能得到的 最多 钱数。
注意你可以切割木块任意次。
文章图片
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?1?f[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?1?f[i][k]+f[i][j?k]
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
5)算法与时间复杂度 ??算法:dp
??时间复杂度: O ( m n ( n + m ) ) O(mn(n+m)) O(mn(n+m))
5、周赛总结 【《力扣周赛题解》|【周赛复盘】LeetCode第298场单周赛】??第四题没动脑,我是 s b sb sb。
推荐阅读
- Leetcode复盘|LeetCode 第 298 场周赛
- 《力扣周赛题解》|【周赛复盘】LeetCode第80场双周赛
- 索引|《穿越 Java | 第三章 - 基础语法篇》
- 大厂面试题精华总结|SpringCloud面试百题集
- java|java 数组下标 变量_Java基础语法(数组)
- 大厂面试题精华总结|SpringBoot面试百题集
- 大厂面试题精华总结|Spring面试百题集
- Java|Java学习笔记01(Java概述_基础语法)
- JavaSE|JavaSE入门学习9(Java基础语法之数组)