问题
有效单词
有效单词需要满足以下几个条件：
至少包含3个字符。
由数字0-9和英文大小写字母组成。（不必包含所有这类字符。）
至少包含一个元音字母。
至少包含一个辅音字母。
给你一个字符串word。如果word是一个有效单词，则返回true，否则返回false。
注意：
‘a’、‘e’、‘i’、‘o’、'u’及其大写形式都属于元音字母。
英文中的辅音字母是指那些除元音字母之外的字母。
示例 1：
输入：word = “234Adas”
输出：true
解释：
这个单词满足所有条件。
解题思路
用两个变量 f0和 f1记录字符串中是否有辅音或元音，必须都为 true才返回 true
如果字符串长度不足 333 或者包含除了数字或字母以外的字符，返回 false。
class Solution {
public boolean isValid(String word) {
if (word.length() < 3) {
return false;
}
boolean[] f = new boolean[2];
Arrays.fill(f, false);
for (char c : word.toCharArray()) {
if (Character.isAlphabetic(c)) {
c = Character.toLowerCase(c);
f[c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ? 1 : 0] = true;
} else if (!Character.isDigit(c)) {
return false;
}
}
return f[0] && f[1];
}
}
K 周期字符串需要的最少操作次数
给你一个长度为n的字符串word和一个整数k，其中k是n的因数。
在一次操作中，你可以选择任意两个下标i和j，其中0<=i,j<n，且这两个下标都可以被k整除，然后用从j开始的长度为k的子串替换从i开始的长度为k的子串。也就是说，将子串word[i…i+k-1]替换为子串word[j…j+k-1]。
返回使word成为K周期字符串所需的最少操作次数。
如果存在某个长度为k的字符串s，使得word可以表示为任意次数连接s，则称字符串word是K周期字符串。例如，如果word==“ababab”，那么word就是s="ab"时的2周期字符串。
示例1：
输入：word=“leetcodeleet”,k=4
输出：1
解释：可以选择i=4和j=0获得一个4周期字符串。这次操作后，word变为"leetleetleet"。
解题思路
1、分段统计。使用哈希表记录各段出现次数，并记录相同段的最大次数。
2、使用贪心策略。求最少操作次数，以相同段最多的作为替换基准
class Solution {
public int minimumOperationsToMakeKPeriodic(String word, int k) {
int len = word.length();
// 1、分段统计。使用哈希表记录各段出现次数，并记录相同段的最大次数
HashMap<String, Integer> segmentCntMap = new HashMap<>();
int maxSegmentCnt = 0;
for (int i = 0; i < len; ) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < k; i++, j++) {
sb.append(word.charAt(i));
}
String segment = sb.toString();
int cnt = segmentCntMap.getOrDefault(segment, 0) + 1;
segmentCntMap.put(segment, cnt);
maxSegmentCnt = Math.max(cnt, maxSegmentCnt);
}
// 2、贪心策略。求最少操作次数，以相同段最多的作为替换基准
int totalSegment = len / k;
return totalSegment - maxSegmentCnt;
}
}
同位字符串连接的最小长度
给你一个字符串s，它由某个字符串t和若干t的同位字符串连接而成。
请你返回字符串t的最小可能长度。
同位字符串指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。
示例1：
输入：s=“abba”
输出：2
解释：
一个可能的字符串t为"ba"。
解题思路
1.len的因子作为 一段段字符串的截取长度。
2.都是小写字母，长度为26的数组判断是否相同就行。
class Solution {
public static int minAnagramLength(String s) {
char[] ch = s.toCharArray();
int len = s.length();
for (int i = 1; i <= len; i++) {
if (len % i != 0) continue;
if (minCheck(ch, i)) return i;
}
return len;
}
//不是滑窗 是一个个相同长度的字符串 截取。
public static boolean minCheck(char[] ch, int m) {
int len = ch.length;
if (len % m != 0) return false;
//比较的母体。
int[] arr = new int[26];
for (int i = 0; i < m; i++) {
arr[ch[i] - 'a']++;
}
int[] nowArr = new int[26];
//要跟母体比较的字符串从下标m开始。为了不错过最后一段，i能取到len
for (int i = m; i <= len; i++) {
if (i != m && i % m == 0) {
//当下标不是m 且 是m的倍数时。
// 那就是一段长度为m的字符串了，就可以跟母体比较了
if (!Arrays.equals(nowArr, arr)) return false;
nowArr = new int[26]; //比较完 清空长度为26的数组
}
if (i == len) break; //到底了 就要跳出了，不然要越界。
nowArr[ch[i] - 'a']++; //计数
}
return true;
}
}
使数组中所有元素相等的最小开销
给你一个整数数组nums和两个整数cost1和cost2。你可以执行以下任一操作任意次：
从nums中选择下标i并且将nums[i]增加1，开销为cost1。
选择nums中两个不同下标i和j，并且将nums[i]和nums[j]都增加1，开销为cost2。
你的目标是使数组中所有元素都相等，请你返回需要的最小开销之和。
由于答案可能会很大，请你将它对109+7取余后返回。
示例1：
输入：nums=[4,1],cost1=5,cost2=2
输出：15
解释：
执行以下操作可以使数组中所有元素相等：
将nums[1]增加1，开销为5，nums变为[4,2]。
将nums[1]增加1，开销为5，nums变为[4,3]。
将nums[1]增加1，开销为5，nums变为[4,4]。
总开销为15。
解题思路
贪心解题
class Solution {
int r = 1000000007;
public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) {
int n = nums.length;
long ans = 0;
long sum = 0,res=0;
// System.out.println(maxn);
Arrays.sort(nums);
int maxn = nums[n - 1];
for(int i=0;i<n;i++){
nums[i]=maxn-nums[i];
}Arrays.sort(nums);
maxn=nums[n-1];
System.out.println(sum+"a"+maxn);
if (n == 2) {
long a=nums[1],b=nums[0];
return (int)(( a-b ) * cost1%r);
}
for (int num : nums)
sum += num;
if (cost1 * 2 <= cost2) {
return (int) (sum*cost1%r);
}
if(maxn*2>sum){
//res=sum-2*(sum-maxn);
ans=(ans+(sum-maxn)*cost2)%r;
res=2*maxn-sum;
}
else{
ans=(ans+sum/2*cost2)%r;
if(sum%2==1)
res=1;
}
System.out.println(ans+" "+res);
//如果存在多个n-2-2k正好构成res
if(n%2==0&&res%2==1){
ans=(ans+cost1)%r;
res--;
if(res==0)
return (int) ans % r;
}
// long a1=cost1*res;
// long a2=cost2*
// ans+=Math.min();
for(int k=0;k*2+2<n&&res>0;k++){
long x=n-2-2*k;
long u=res/x;
ans=(ans+Math.min(u*(x+1+k)*cost2,x*u*cost1))%r;
res=res-x*u;
}
return (int) ans % r;
}
}
