Leetcode 第396场周赛 问题和解法

问题

有效单词

有效单词需要满足以下几个条件：

至少包含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能取到lenfor (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正好构成resif(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;}
}

来源

LeetCode周赛