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能取到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;
    }
}