Leetcode - 周赛396

一，3136. 有效单词

二，3137. K 周期字符串需要的最少操作次数

三，3138. 同位字符串连接的最小长度

四，3139. 使数组中所有元素相等的最小开销

一，3136. 有效单词

本题就是一道阅读理解题：

字符串长度小于3，返回false
字符串出现除了26个字母和数字以外的字符，返回false
字符串中必须出现至少一个元音字母，一个辅音字母

代码如下：

class Solution {public boolean isValid(String word) {if(word.length() < 3) return false;String t = "aeiouAEIOU";int a = 0, b = 0, c = 0;for(char ch : word.toCharArray()){if(ch>='a'&&ch<='z'||ch>='A'&&ch<='Z'){if(t.indexOf(ch)!=-1){a++;}else{b++;}}else if(ch>='0'&&ch<='9'){c++;}else{return false;}}return a>0&&b>0;}
}

二，3137. K 周期字符串需要的最少操作次数

本题求最少操作次数，正难则反，可以转换成最多保留多少个长度为k的字符串，可以使用HashMap来存储长度为k的子字符串出现次数，用总数 - 最多的出现次数就是答案。

代码如下：

class Solution {public int minimumOperationsToMakeKPeriodic(String word, int k) {Map<String,Integer> map = new HashMap<>();int mx = 0;for(int i=0; i<=word.length()-k; i+=k){String t = word.substring(i, i+k);map.merge(t, 1, Integer::sum);mx = Math.max(mx, map.get(t));}return word.length()/k - mx;}
}

三，3138. 同位字符串连接的最小长度

本题的题意：能否将字符串均匀分成 x 段，使得每一段字符串出现字符的种类和数目一样，返回最短的子字符串，可以直接暴力

代码如下：

class Solution {public int minAnagramLength(String s) {char[] ch = s.toCharArray();int n = s.length();for(int k=1; k<=n/2; k++){if(n%k != 0) continue;int[] cnt = new int[26];for(int j=0; j<k; j++){cnt[ch[j]-'a']++;}boolean flg = true;//判断后续分成的字段是否符合条件for(int i=k; i<=n-k; i+=k){int[] cnt0 = new int[26];for(int j=i; j<i+k; j++){cnt0[ch[j]-'a']++;}if(!Arrays.equals(cnt, cnt0)){flg = false;break;}}if(!flg) continue;return k;}return n;}
}

四，3139. 使数组中所有元素相等的最小开销

在写题之前，需要先解决一个问题，当数组中所有的元素相等时，这个相等的值（k）是否一定要等于原数组中的最大值？这是不一定的，比如 [1，14，14，15]，cost1=2，cost2=1，该样例的中，当它的所有元素等于21时，它的所有开销最小，所以需要从max(nums)开始枚举这个k，不断的求出其中的最小值。

分类讨论：

cost1 * 2 <= cost2 ，直接全部使用 cost1 来增加，返回 s * cost1 % MOD
接下来就是如何判断何时使用 cost1，cost2。易知，只有先使用cost2，再使用cost1，才能使得答案越小，这里讲一个结论，令 d = k - mn，s = 整个数组需要增加的1的次数：当 d <= s - d 时，res = s / 2 * cost2 + s % 2 * cost1；当 d > s - d 时，res = (s - d) * cost2 + (2*d - s) * cost1；

结论说明：上述选择同增(cost2)还是单增(cost1)的问题，可以转化成——给你一个字符串（只包含小写字母），让他重新排列，问你能否使得这个字符串相邻的字符不相同？

实在不明白可以去写一下这个题 重排字符串 (nowcoder.com)

class Solution {public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) {int MOD = (int)1e9 + 7;long mx = 0, mn = nums[0], sum = 0;int n = nums.length;for(int x : nums){mx = Math.max(mx, x);mn = Math.min(mn, x);sum += x;}long s = n*mx - sum;if(2*cost1 <= cost2) return (int)(s * cost1 % MOD);long ans = Long.MAX_VALUE;for(long i=mx; i<mx*2+1; i++){long d = i - mn;long res = 0;if(d <= s - d){res = s/2*cost2+s%2*cost1;}else{res = (s - d)*cost2+(d*2-s)*cost1;}s += n;ans = Math.min(ans, res);}return (int)(ans%MOD);}
}

优化：二分

class Solution {long base,n;long mn, mx, c1, c2;public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) {int MOD = (int)1e9 + 7;this.c1 = cost1;this.c2 = cost2;long mx = 0, mn = nums[0];long sum = 0;int n = nums.length;this.n = n;for(int x : nums){mx = Math.max(mx, x);mn = Math.min(mn, x);sum += x;}long base = n*mx - sum;this.base = base;this.mx = mx;this.mn = mn;if(2*cost1 <= cost2) return (int)(base * cost1 % MOD);long ans = Long.MAX_VALUE;if(mx%2==1){    ans = f(mx);mx += 1;base += n;}long l = mx/2, r = mx;//偶数while(l <= r){long k = (l + r)/2;if(f(k*2)<f((k+1)*2)){r = k - 1;}else{l = k + 1;}}long k0 = r + 1;l = mx/2;r = mx;while(l <= r){//奇数long k = (l + r)/2;if(f(k*2+1) < f((k+1)*2+1)){r = k - 1;}else{l = k + 1;}}long k1 = r + 1;ans = Math.min(ans, f(k0*2));ans = Math.min(ans, f(k1*2+1));return (int)(ans%MOD);}private long f(long i){long s = base + (i - mx)*n;long d = i - mn;if(d <= s - d){return s/2*c2 + s%2*c1;}return (s-d)*c2+(d*2-s)*c1;}
}