力扣第234场周赛

题一 字符串中不同整数的数目

描述

给你一个字符串 word ，该字符串由数字和小写英文字母组成。

请你用空格替换每个不是数字的字符。例如，"a123bc34d8ef34" 将会变成 " 123 34 8 34" 。注意，剩下的这些整数间至少要用一个空格隔开："123"、"34"、"8" 和 "34" 。

返回对 word 完成替换后形成的 不同 整数的数目。

如果两个整数的 不含前导零 的十进制表示不同，则认为这两个整数也不同。

 

思路

一次遍历，将数字存入Set中，注意前导零。

代码

import java.util.HashSet;
import java.util.Set;

/**
 * author: fangjie
 * email: syfangjie@live.cn
 * date: 2021/3/28 10:16 上午
 */
public class N1 {
    public int numDifferentIntegers(String word) {
        int idx=0;
        char[] strs=word.toCharArray();
        Set<String> set = new HashSet<>();
        while (idx<word.length())
        {
            while (idx<word.length()&&!Character.isDigit(strs[idx]))idx++;
            StringBuilder sb=new StringBuilder();
            while (idx<word.length()&&strs[idx]=='0')idx++;
            while (idx<word.length()&&Character.isDigit(strs[idx]))
            {
                sb.append(strs[idx]);
                idx++;
            }
            if(sb.length()==0&&idx>=1&&strs[idx-1]=='0')sb.append("0");
            if(sb.length()!=0)set.add(sb.toString());
        }
        return set.size();
    }
}

题二 还原排列的最少操作步数

描述

给你一个偶数 n ，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i（下标 从 0 开始 计数）。

一步操作中，你将创建一个新数组 arr ，对于每个 i ：

如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2] 如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2] 然后将 arr 赋值给 perm 。

要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。

思路

直接按题目要求模拟。

代码

public class N2 {
    public static void main(String[] args) {
        System.out.println(new N2().reinitializePermutation(4));
    }
    public int reinitializePermutation(int n) {
        int[] arr=new int[n];
        int[] tmp=new int[n];
        for (int i=0;i<n;i++)arr[i]=i;
        for (int res=1;res<4;res++)
        {
            //System.out.println(Arrays.toString(arr));
            for (int i=0;i<n;i++)
            {
                if(i%2==0) tmp[i]=arr[i/2];
                else if(i%2==1) tmp[i]=arr[n/2+(i-1)/2];
            }
            System.arraycopy(tmp, 0, arr, 0, n);
            boolean flag=true;
            for (int i=0;i<n;i++)
            {
                if(arr[i]!=i){
                    flag=false;
                    break;
                }
            }
            if(flag)return res;
        }
        return -1;
    }
}

题三 替换字符串中的括号内容

描述

给你一个字符串 s ，它包含一些括号对，每个括号中包含一个 非空 的键。

比方说，字符串 "(name)is(age)yearsold" 中，有 两个 括号对，分别包含键 "name" 和 "age" 。 你知道许多键对应的值，这些关系由二维字符串数组 knowledge 表示，其中 knowledge[i] = [keyi, valuei] ，表示键 keyi 对应的值为 valuei 。

你需要替换 所有 的括号对。当你替换一个括号对，且它包含的键为 keyi 时，你需要：

将 keyi 和括号用对应的值 valuei 替换。 如果从 knowledge 中无法得知某个键对应的值，你需要将 keyi 和括号用问号 "?" 替换（不需要引号）。 knowledge 中每个键最多只会出现一次。s 中不会有嵌套的括号。

请你返回替换 所有 括号对后的结果字符串。

思路

• 将knowledge变为map方便使用
• 一次遍历，解析出括号内的key

代码

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * author: fangjie
 * email: syfangjie@live.cn
 * date: 2021/3/28 10:17 上午
 */
public class N3 {

    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String,String> map=new HashMap<>(knowledge.size()*2+5);
        for (List<String> know:knowledge)map.put(know.get(0),know.get(1));
        StringBuilder res=new StringBuilder();
        char[] strs=s.toCharArray();
        int idx=0;
        while (idx<strs.length)
        {
            while (idx<strs.length&&strs[idx]!='(') res.append(strs[idx++]);
            StringBuilder key=new StringBuilder();
            idx++;
            while (idx<strs.length&&strs[idx]!=')') key.append(strs[idx++]);
            idx++;
            if(key.length()>0)res.append(map.getOrDefault(key.toString(),"?"));
        }
        return res.toString();
    }
}

题四 好因子的最大数目

描述

给你一个正整数 primeFactors 。你需要构造一个正整数 n ，它满足以下条件：

n 质因数（质因数需要考虑重复的情况）的数目 不超过 primeFactors 个。 n 好因子的数目最大化。如果 n 的一个因子可以被 n 的每一个质因数整除，我们称这个因子是 好因子 。比方说，如果 n = 12 ，那么它的质因数为 [2,2,3] ，那么 6 和 12 是好因子，但 3 和 4 不是。 请你返回 n 的好因子的数目。由于答案可能会很大，请返回答案对 109 + 7 取余 的结果。

请注意，一个质数的定义是大于 1 ，且不能被分解为两个小于该数的自然数相乘。一个数 n 的质因子是将 n 分解为若干个质因子，且它们的乘积为 n 。

思路

这题一开始想复杂了，总想着把这个正整数找出来。其实这题不需要把这个正整数找出来。

对num进行质因数分解

num=a1^k1*a2^k2.....

按题目要求可得

k1+k2+.....<=primeFactors

好因子必须包含有

a1*a2*....

这个因数。

题目是求好因子数目的最大化的，也就是求

k1*k2*...

的最大值

如何拆才能尽可能最大，尽可能拆成3。

选择3的理由如下：

依据均值不等式可得拆分成想等的值的时候乘积最大。

如果对n进行x份等值拆分可得y=(n/x)^x

可得x=e时，y最大。

最接近e的整数为3。

代码

public class N4 {

    private final static int MOD=(int) (1e9+7);

    public int maxNiceDivisors(int primeFactors) {
        if (primeFactors<=3) return primeFactors;
        if (primeFactors%3==1) return (int) (powMod(3, (primeFactors-4)/3, MOD)*4%MOD);
        if (primeFactors%3==2) return (int) (powMod(3, primeFactors/3, MOD)*2%MOD);
        return (int) (powMod(3, primeFactors/3, MOD));
    }
    //快速幂
    long powMod(long a, long b, final long mod) {
        if (b==0) return 1L;
        long res=powMod(a, b/2, mod)%mod;
        if (b%2==0) return res*res%mod;
        return res*res*a%mod;
    }

}