文章目錄
- 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)