[LeetCode周赛]第 278 场周赛

一.介绍

  周赛链接: LeetCode第278场周赛
  最终结果这样:

  晚起了十分钟,最后A了三题,还算OK吧,但是四次罚时……,无话可说,最后一题暴力过不了,可惜.

二.分析

2.1 将找到的值乘以2(Easy)

  题目链接: LeetCode-2154

题目内容:
    给你一个整数数组 nums ,另给你一个整数 original ,这是需要在 nums 中搜索的第一个数字。
    接下来,你需要按下述步骤操作:
        如果在 nums 中找到 original ,将 original乘以 2 ,得到新 original(即,令 original = 2 * original)。
        否则,停止这一过程。
        只要能在数组中找到新 original ,就对新 original 继续 重复 这一过程。
    返回 original 的 最终 值。

示例:
	输入:nums = [5,3,6,1,12], original = 3
    输出:24
    解释: 
        - 3 能在 nums 中找到。3 * 2 = 6 。
        - 6 能在 nums 中找到。6 * 2 = 12 。
        - 12 能在 nums 中找到。12 * 2 = 24 。
        - 24 不能在 nums 中找到。因此,返回 24 。

提示:
	1 <= nums.length <= 1000
    1 <= nums[i], original <= 1000

  我的解答如下:

class Solution {
    public int findFinalValue(int[] nums, int original) {
        Set<Integer>set=new HashSet<>();
        for(int num:nums) set.add(num);
        while(set.contains(original)) original=original*2;
        return original;
    }
}

  简单题没啥好说的,利用set可以很简单判断元素是否存在
  时间复杂度为O(n),空间复杂度为O(n)(不计算答案所用空间)
  本题也可以使用排序去做,若后一个元素超过2*前元素,返回即可,时间复杂度为O(nlogn),空间复杂度为O(1)(不计算答案所用空间)

2.2 分组得分最高的所有下标(Medium)

  题目链接: LeetCode-2155

题目内容:
	给你一个下标从 0 开始的二进制数组 nums ,数组长度为 n 。nums 可以按下标 i( 0 <= i <= n )拆分成两个数组(可能为空):numsleft 和 numsright 。
        numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素(包括 0 和 i - 1 ),
        而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素(包括 i 和 n - 1 )。
        如果 i == 0 ,numsleft 为 空 ,而 numsright 将包含 nums 中的所有元素。
        如果 i == n ,numsleft 将包含 nums 中的所有元素,而 numsright 为 空 。
    下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。

    返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。

示例:
	输入:nums = [0,0,1,0]
    输出:[2,4]
    解释:按下标分组
        - 0 :numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。
        - 1 :numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。
        - 2 :numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。
        - 3 :numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
        - 4 :numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
    下标 2 和 4 都可以得到最高的分组得分 3 。
    注意,答案 [4,2] 也被视为正确答案。

提示:
	n == nums.length
    1 <= n <= 10^5
    nums[i] 为 0 或 1

  我的解答如下:

class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        List<Integer>list=new ArrayList<>();
        int len=nums.length,num0=0,num1=0;
        for(int num:nums)
        {
            if(num==0) num0++;
            else num1++;
        }
        //获得0和1的数量
        int resmax=Math.max(num0,num1),n0=0,n1=num1;
        for(int i=1;i<=len;i++){
            if(nums[i-1]==0) n0++;
            else n1--;
            //动态变换n0和n1数量,并更改答案
            resmax=Math.max(resmax,n0+n1);
        }
        int ns0=0,ns1=num1;
        for(int i=1;i<=len;i++){
            if(nums[i-1]==0) ns0++;
            else ns1--;
            //获得对应的下标
            if(resmax==ns0+ns1) list.add(i);
        }
        if(resmax==num1) list.add(0);
        return list;
    }
}

  这个题难度也不高,分别统计0和1的数量,然后从左往右遍历获得最大结果,再遍历一次获得对应下标即可   时间复杂度为O(n),空间复杂度为O(1)(不计算答案所用空间)
  罚时的原因是添加下标时把len忘了,非常的可惜
  本题官解利用前缀和的思想,将遍历的次数减少到了一次,非常的厉害

  这种方法竞赛的时候确实很难想起来,不过还是有一定学习价值的
class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int n = nums.length;
        // best 为历史最大值
        int presum = 0, best = 0;
        // ans 为历史最大值的下标
        List<Integer> ans = new ArrayList<>();
        ans.add(0);
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                ++presum;
                if (presum > best) {
                    best = presum;
                    ans = new ArrayList<>();
                    ans.add(i+1);
                }
                else if (presum == best) {
                    ans.add(i + 1);
                }
            }
            else {
                --presum;
            }
        }
        return ans;
    }
} 

  时间复杂度为O(n),空间复杂度为O(1)(不计算答案所用空间)

2.3 查找给定哈希值的子串(Medium)

  题目链接: LeetCode-2156

题目内容:
	给定整数 p和 m,一个长度为 k且下标从0开始的字符串s的哈希值按照如下函数计算:
        hash(s, p, m) = (val(s[0]) * p^0 + val(s[1]) * p^1 + ... + val(s[k-1]) * p^(k-1)) mod m.
        其中val(s[i])表示s[i]在字母表中的下标,从val('a') = 1 到val('z') = 26。

    给你一个字符串s和整数power,modulo,k和hashValue。请你返回 s中第一个长度为k的子串sub,满足hash(sub, power, modulo) == hashValue。

    测试数据保证一定存在至少一个这样的子串。
    子串定义为一个字符串中连续非空字符组成的序列。


示例:
	输入:s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
    输出:"fbx"
    解释:"fbx" 的哈希值为 hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 31^2) mod 100 = 23132 mod 100 = 32 。
         "bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 31^2) mod 100 = 25732 mod 100 = 32 。
    "fbx" 是长度为 3 的第一个哈希值为 32 的子串,所以我们返回 "fbx" 。
    注意,"bxz" 的哈希值也为 32 ,但是它在字符串中比 "fbx" 更晚出现。

提示:
	1 <= k <= s.length <= 2 * 10^4
    1 <= power, modulo <= 10^9
    0 <= hashValue < modulo
    s只包含小写英文字母。
    测试数据保证一定存在满足条件的子串。

  我的解答如下:

class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int len=s.length();
        long temp=0;
        long tempmode=1;
        char[]cs=s.toCharArray();
        for(int j=0;j<=len-k;j++){
            temp=0;
            tempmode=1;
            for(int i=0;i<k;i++)
            {
                temp+=(cs[j+i]-'a'+1)*(tempmode);
                tempmode*=power;
                tempmode=tempmode%modulo;
                temp=temp%modulo;   
            }
            if(temp==hashValue) return s.substring(j,j+k);
        }
        return s;

    }
}

  最开始用的滑窗去做的,各种各样的边界bug,因为数据范围只到104,于是就用暴力法测试了一下,没想到真的能AC。查看评论区后发现能用long的时候尽量不要用double,会由于精度问题导致越界问题
  时间复杂度为O(nk),空间复杂度为O(1)(不计算答案所用空间)
  显然本题的做法不应当是这样的,参考大佬做法,本题正确的思路应当是倒序滑窗:

class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] str = s.toCharArray();
        int n = str.length;
        long x = 0, b = 1;
        int index=0;
        //计算最后k个字符组成的字符串的哈希值
        for (int i = 0; i < k; i++) {
            char ch = str[n - 1 - i];
            x = (x * power + ch - 'a' + 1) % modulo;
        }
        for (int i = 0; i < k - 1; i++)
            b = b * power % modulo;
        
        //此处还可以用快速幂优化
        if (x == hashValue)
            index=n-k;
        for (int i = n - k - 1; i >= 0; i--) {
            x = (x + modulo - (b * (str[i + k] - 'a' + 1) % modulo)) % modulo;
            //减去滑窗中最右边字符
            char ch = str[i];
            x = (x * power + ch - 'a' + 1) % modulo;
            //其余哈希值×modulo,并加上第一个的哈希值
            if (x == hashValue)
                index = i;
        }
        return s.substring(index,index+k);
    }
}

  时间复杂度为O(n),空间复杂度为O(1),这道题如果从前往后枚举,通过前缀和的方式记录prefix[i](表示从0到i这段的字符串哈希值),这样我们可以通过(prefix[r] - prefix[l]) / pow(p, l)来求出任意一段子串([l,r])的哈希值,但是本题这样的计算方法是错误的。因为我们的字符串哈希值的计算时候是需要做取模预算的,这里的取余数对于除法来说是计算是会出错的,我们只能想办法去转换成乘法运算。我们可以通过反向枚举从后往前划窗求解:
  1)求出最后一段长度为k的子串的哈希值
  2)滑动窗口大小为k,不断的往前移动,每次移动时先取出尾部元素(离开窗口的元素)然后乘以pow(p, k - 1),最后再加上头部元素(进入窗口的元素),这里面计算的每一步都记得要取模
  3)找到符合要求的子串时记录下标,最后返回字符串截取的值即可

2.4 字符串分组(Hard)

  题目链接: LeetCode-2157

题目内容:
	给你一个下标从 0 开始的字符串数组words每个字符串都只包含小写英文字母。words中任意一个子串中,每个字母都至多只出现一次。

    如果通过以下操作之一,我们可以从 s1的字母集合得到 s2 的字母集合,那么我们称这两个字符串为关联的:
        往s1的字母集合中添加一个字母。
        从s1的字母集合中删去一个字母。
        将s1中的一个字母替换成另外任意一个字母(也可以替换为这个字母本身)。
    
    数组word 可以分为一个或者多个无交集的组。一个字符串与一个组如果满足以下任一条件,它就属于这个组:
        它与组内至少一个其他字符串关联。
        它是这个组中唯一的字符串。
    注意,你需要确保分好组后,一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下,分组方案是唯一的。

    请你返回一个长度为2的数组ans:
    ans[0]是 words分组后的总组数。
    ans[1]是字符串数目最多的组所包含的字符串数目。

示例:
	输入:words = ["a","ab","abc"]
    输出:[1,3] 
    解释:
        - words[0] 与 words[1] 关联。
        - words[1] 与 words[0] 和 words[2] 关联。
        - words[2] 与 words[1] 关联。
    由于所有字符串与其他字符串都关联,所以它们全部在同一个组内。
    所以最大的组大小为 3 。

提示:
	1 <= words.length <= 2 * 10^4
    1 <= words[i].length <= 26
    words[i]只包含小写英文字母。
    words[i]中每个字母最多只出现一次。

  我当时的解答如下:

class Solution {
    boolean []flag;
    public int[] groupStrings(String[] words) {
        int len=words.length;
        flag=new boolean[len];
        Map<Integer,List<String>>map=new HashMap<>();  //记录对应长度的字符串集合
        Map<String,List<Integer>>map1=new HashMap<>(); //记录字符串对应的下标集合
        for(int i=0;i<len;i++){
            String s=words[i];
            int n=s.length();
            if(map.containsKey(n)) map.get(n).add(s);
            else{
                List<String> temp=new ArrayList<>();
                temp.add(s);
                map.put(n,temp);
            }
            if(map1.containsKey(s)) map1.get(s).add(i);
            else{
                List<Integer> temp=new ArrayList<>();
                temp.add(i);
                map1.put(s,temp);
            }
        }
        int zushu=0,zumax=0;

        //暴力查找,若已访问过则跳过,否则bfs
        for(int j=0;j<len;j++){
            if(flag[j]) continue;
            else{
                int tempsize=1;
                Deque<String> deque=new LinkedList<>();
                deque.add(words[j]);
                flag[j]=true;
                while(!deque.isEmpty()){
                    int size=deque.size();
                    for(int i=0;i<size;i++){
                        String t=deque.pollFirst();

                        //长度相等时判断,置满足条件的下标为true,并将字符串加入队列中
                        for(String s:map.getOrDefault(t.length(),new ArrayList<String>())){
                            if(islikesamedeng(s,t)){
                                boolean isok=false;
                                for(Integer g:map1.get(s)){
                                    if(flag[g]) continue;
                                    else{
                                        isok=true;
                                        tempsize++;
                                        flag[g]=true;
                                    }
                                }
                                if(isok) deque.add(s);
                            }  
                        }
                        
                        //长度不等时
                        for(String s:map.getOrDefault(t.length()-1,new ArrayList<String>())){
                            if(islikesameda(t,s)){
                                boolean isok=false;     
                                for(Integer g:map1.get(s)){
                                    if(flag[g]) continue;
                                    else{            
                                        isok=true;
                                        tempsize++;
                                        flag[g]=true;
                                    }
                                }
                                 if(isok) deque.add(s);
                            }  
                        }
                        for(String s:map.getOrDefault(t.length()+1,new ArrayList<String>())){
                            if(islikesameda(s,t)){
                                boolean isok=false;
                                for(Integer g:map1.get(s)){
                                    if(flag[g]) continue;
                                    else{
                                        isok=true;
                                        tempsize++;
                                        flag[g]=true;
                                
                                    }
                                }
                                if(isok) deque.add(s);
                            }  
                        }
                    }
                }
                zumax=Math.max(zumax,tempsize); 
                zushu++;
                
            }
        }
        return new int[]{zushu,zumax};

    }

    //判断同样长度的字符串是否符合要求
    public boolean islikesamedeng(String s,String t){
        int[]cal1=new int[26];
        int[]cal2=new int[26];
        int len=s.length();
        for(int i=0;i<len;i++){
            cal1[s.charAt(i)-'a']++;
            cal2[t.charAt(i)-'a']++;
        }
        int dir=0;
        for(int i=0;i<26;i++){
            if(cal1[i]!=cal2[i]){
                dir++;
                if(dir>=3) return false;
            }
        }
        return true;  
    }

    //判断长度差一的字符串是否符合要求
    public boolean islikesameda(String s,String t){
        int[]cal1=new int[26];
        int[]cal2=new int[26];
        int len=t.length();
        for(int i=0;i<len;i++){
            cal1[s.charAt(i)-'a']++;
            cal2[t.charAt(i)-'a']++;
        }
        cal1[s.charAt(len)-'a']++;
        boolean dir=false;
        for(int i=0;i<26;i++){
            if(cal1[i]!=cal2[i]){
                if(!dir) dir=true;
                else return false;
            }
        }
        return true;  
    }
}

  其实这是一个正确的解,但注意到2 <= n <= 104,该解的时间复杂度为O(n2)logn,所以无法通过全部案例
  显然本题可以使用位运算标记字符串降时间复杂度,但经过测试后,极端案例超过1000ms,还是无法通过:
  本题可以通过并查集+暴力遍历26个字母的方式求解

class Solution {
    public int[] groupStrings(String[] words) {
        // 记录二进制的下表 Entry<Key, Value>  Key: 二进制表示 Value: 下标
        Map<Integer, Integer> map = new HashMap();
        // 并查集数组
        int[] fa = new int[words.length];
        // 初始化
        for(int i = 0;i < words.length;i ++){
            fa[i] = i;
        }

        for(int i = 0;i < words.length;i ++){
            int hash = getHash(words[i]);
            int aa = getFa(fa, i);
            for(int j = 0;j < 26;j ++){
                    // 添加或删去字母 直接异或即可 0变为1 1变为0
                    int nx = hash ^ (1 << j);
                    int ny=map.getOrDefault(nx,-1);
                    if(ny!=-1){
                        int bb = getFa(fa, ny);
                        union(fa, aa, bb);
                    }
                
            }
            // 将已有字母替换成另一个字母
            for(int j = 0;j < 26;j ++){
                //原先为1 变为0
                if((hash & (1 << j)) != 0){
                    for(int z = 0; z < 26;z ++){
                        //原先为0 变为1
                        if((hash & (1 << z)) == 0){
                            int nx = hash ^ (1 << j) | (1 << z);
                            int ny=map.getOrDefault(nx,-1);
                            if(ny!=-1){
                                int bb = getFa(fa, ny);
                                union(fa, aa, bb);
                            }
                        }
                    }
                }
            }
            // 若之前不存在,则记录
            int nhash=map.getOrDefault(hash,-1);
            if(nhash==-1){
                map.put(hash, i);
            }else{  // 之前存在与当前字符串集相同的串, 合并
                int bb = getFa(fa, nhash);
                union(fa, aa, bb);
            }
        }

        //统计各个分组的个数
        Map<Integer, Integer> ans = new HashMap();
        int[] res = new int[2];
        for(int i = 0;i < words.length;i ++){
            int pos = getFa(fa, i);
            //自成一组
            int nx=ans.getOrDefault(pos,0);
            if(nx==0){
                ans.put(pos, 1);
                res[0] ++;
            }
            //否则组员数+1
            else ans.put(pos, nx + 1);
            res[1] = Math.max(res[1],nx+1);
        }
        return res;
    }

    // 获取字符串的二进制表示
    public int getHash(String word){
        int ans = 0,len=word.length();
        for(int i = 0;i < len;i ++){
            ans |= (1 << (word.charAt(i) - 'a'));
        }
        return ans;
    }

    // 并查集合并
    public void union(int[] fa, int faa, int fbb){
        fa[fbb] = faa;
    }

    // 获取并查集的父顶端节点
    public int getFa(int[] fa, int now){
        if(fa[now] == now){
            return now;
        }
        fa[now] = getFa(fa, fa[now]);
        return fa[now];
    }
}

  并查集的模板题,在变换字母的时候灵活运用位运算即可,0与1的变换可以通过异或实现,新增字母可以通过暴力二次循环实现,先找到1,再依次把每个0变为1,判断是否存在即可
  本方法时间复杂度为 O(n*(m + m2)), m=26,空间复杂度为O(n)

end
  • 作者:Yuan(联系作者)
  • 发表时间:2022-08-23 16:49
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载博主转载的文章,请附上原文链接
  • 公众号转载:请联系作者
  • 评论