文章目录
- 6047. 移除指定数字得到的最大结果
- 6048. 必须拿起的最小连续卡牌数
- 6049. 含最多 K 个可整除元素的子数组
- 6050. 字符串的总引力
6047. 移除指定数字得到的最大结果
https://leetcode-cn.com/problems/remove-digit-from-number-to-maximize-result/
思路：先用一个集合记录字符串中字符等于digit的位置，然后遍历该集合，在原始字符串中删除该位置的字符得到一个新的字符串，比较这些新的字符串的大小即可（字符串比较）
class Solution {
public String removeDigit(String number, char digit) {
ArrayList<Integer> index=new ArrayList<>();
for(int i=0;i<number.length();i++){
if(number.charAt(i)==digit)
index.add(i);
}
String max="0000";//初始化1个较小值
for(int i:index) {
StringBuilder sb=new StringBuilder(number);
sb.deleteCharAt(i);
String s=sb.toString();
if(s.compareTo(max)>0)
max=s;
}
return max;
}
}
//O(n)
//O(n)
6048. 必须拿起的最小连续卡牌数
https://leetcode-cn.com/problems/minimum-consecutive-cards-to-pick-up/
思路：使用HashMap,卡片值->卡片位置,当某个卡片第一次出现时直接加入map， 第2次及以后出现时则更新相邻两次的距离，答案取最小距离，同时map中card出现的位置更新为最近出现的
class Solution {
public int minimumCardPickup(int[] cards) {
HashMap<Integer, Integer> map=new HashMap<>();
int ans=Integer.MAX_VALUE;
for(int i=0;i<cards.length;i++) {
int card=cards[i];
if(!map.containsKey(card))
map.put(card,i);//第一次出现
else{
ans=Math.min(ans,i-map.get(card)+1);//更新两次出现的位置距离
map.put(card,i);//更新card出现的位置
}
}
return ans==Integer.MAX_VALUE?-1:ans;
}
}
//O(n)
//O(n)
6049. 含最多 K 个可整除元素的子数组
https://leetcode-cn.com/problems/k-divisible-elements-subarrays/
思路：枚举从位置0到n-1的子数组，在满足条件的情况下加入各个子数组，采用set去重，最后set的大小就是满足的连续子数组的个数
class Solution {
public int countDistinct(int[] nums, int k, int p) {
HashMap<Integer, Integer> map=new HashMap<>();
HashSet<String> set=new HashSet<>();
int n=nums.length;
for(int i=0;i<n;i++) {
int cnt=0;
StringBuilder sb=new StringBuilder();
int j=i;
while(cnt<=k&&j<n) {
if(nums[j]%p==0)//遇到一个可以被p整除的元素
cnt++;
if(cnt>k)//已经超了 停止
break;
sb.append(nums[j]+"-");//注意这里要加上一个字符串符号 不然1 17 和11 7会被当成1个子数组
set.add(sb.toString());//加入到set集合
j++;
}
}
return set.size();
}
}
6050. 字符串的总引力
https://leetcode-cn.com/problems/total-appeal-of-a-string/
思路：假设有两组相邻的子字符串: 以
s[i-1]
结尾的子字符串，以
s[i]
结尾的子字符串
后者由前者增加一个字符
s[i]
得到，记
s[i]
在区间
[0,i-1]
内出现的位置是
j
,则对于子字符串
s[0..i-1]
s[1..i-1]
s[2..i-1]
s[j..i-1]
这些子字符串的引力值没有影响，因为s[i]已经出现过了，但是对于子字符串
s[j+1..i-1]
s[j+2..i-1]
s[j+3..i-1]
s[i-1..i-1]
有影响，s[i]没有出现过，对这些子字符串造成的引力值影响是(i-1)-(j+1)+1=i-j-1 , 再加上s[i]这一个字符(一个字符s[i]形成的子字符串也是以s[i]结尾)组成的字符串的引力值，即总的是i-j
class Solution {
public long appealSum(String s) {
long ans=0,sum=0;
int[] pos=new int[26];
Arrays.fill(pos,-1);//初始化为-1 当没有出现时 i-j=i+1 相当于给每个子字符串的引力值加一
for(int i=0;i<s.length();i++){
int ch=s.charAt(i)-'a';
sum+=i-pos[ch];//sum记录以s[i]结尾的字符串的引力值之和
ans+=sum;//ans记录所有的子字符串的引力值之和
pos[ch]=i;//更新字符ch出现的位置
}
return ans;
}
}
//O(n)
//O(1)