5076-字符串的最大公因子

sourcenode 发布于2019-08-16 17:48 / 1817人阅读

摘要：前言的字符串的最大公因子对于字符串和，只有在与自身连接次或多次时，我们才认定能除尽。返回字符串，要求满足能除尽且能除尽。

前言

Weekly Contest 139的字符串的最大公因子：

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
示例2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
示例3：
输入：str1 = "LEET", str2 = "CODE"
输出：""
提示：

1 <= str1.length <= 1000
1 <= str2.length <= 1000

str1[i] 和 str2[i] 为大写英文字母

解题思路

本题需要注意，如果字符串S和T本身不是有特定字符串循环组成的，那么其实字符串S和T直接也不存在一个最大公因子。我的解题思路是将问题进行分解，分解为以下3步：

提取循环因子：判断字符串是否由特定字符循环组成，并找出所有可以组成字符串的循环字符串

提取公因子：字符串S和T的循环因子结果进行并集计算

提取最大公因子：从公因子集合中找出长度最大的字符串

实现代码

    /**
     * 5076. 字符串的最大公因子
     * @param str1
     * @param str2
     * @return
     */
    public String gcdOfStrings(String str1, String str2) {
        List loopStr1=findLoopStrings(str1);
        List loopStr2=findLoopStrings(str2);
        List union=new ArrayList<>();
        if(!loopStr1.isEmpty() && !loopStr2.isEmpty()){// 不存在循环因子
            for(String l1:loopStr1){// 进行并集运算，提取公因子
                for (String l2: loopStr2) {
                    if(l1.equals(l2)){
                        union.add(l1);
                    }
                }
            }
            if(union.isEmpty()){// 无公因子，直接返回空字符
                return "";
            }
            // 找出长度最大的字符串
            return union.stream().collect(Collectors.maxBy(Comparator.comparing(String::length))).get();
        }
        return "";
    }

    /**
     * 获取组成循环字符串的子串
     * @param str
     * @return
     */
    private List findLoopStrings(String str){
        List result=new ArrayList<>();
        for(int i=0;i

海外云主机服务器托管最大公因子算法字符串最大子串c语言公对公转账密码因子

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74746.html

开发零成本：En-Tan-Mo黄皮书解读之开发者篇

摘要：项目黄皮书一经发布，区块链垂直媒体星球日报就对这本书作了专题式的解读。在接受星球日报采访中，开发者们表示，担心节点集中化带来的安全风险。本文，星球日报将通过解读黄皮书，解答开发者关心的问题。 showImg(https://segmentfault.com/img/bVbt2EX?w=800&h=534); 由ETM科学院历时半年打磨的黄皮书，从科学和技术两方面全方位解读了ETM的理论...

pakolagij 2019-08-19 11:45 评论0 收藏0
开发零成本：En-Tan-Mo黄皮书解读之开发者篇

摘要：项目黄皮书一经发布，区块链垂直媒体星球日报就对这本书作了专题式的解读。在接受星球日报采访中，开发者们表示，担心节点集中化带来的安全风险。本文，星球日报将通过解读黄皮书，解答开发者关心的问题。 showImg(https://segmentfault.com/img/bVbt2EX?w=800&h=534); 由ETM科学院历时半年打磨的黄皮书，从科学和技术两方面全方位解读了ETM的理论...

plus2047 2019-07-01 14:01 评论0 收藏0
干货！亮相 Staking 生态大会的ETM都透露了啥进展？

摘要：月日，由星球日报主办的大型线下活动生态大会在北京隆重举行。第一个是投票率不高，核心的原因是因为投票者是在等待超级节点在等待收益利润，这个链除了发布挖矿收益以外，这两部分是割裂的。的超级节点，始终集中在少数节点是容易被攻击的。 7月10日，由星球日报主办的大型线下活动Staking 生态大会在北京隆重举行。作为公链3.0项目的代表之一，En-Tan-Mo首席科学家、创始人Aaron Yu...

keithyau 2019-08-16 18:33 评论0 收藏0
12因子应用文档(一)

摘要：因子是一种构建应用的方法用声明式的格式设置自动化，最小化新开发者加入项目的时间和成本。代码库一份被版本控制追踪的代码，多份部署因子应用会一直放在版本控制中，如，或者。每个分布式系统中的组件是一个应用，每一个都可以独立遵守因子。原文地址： https://12factor.net/12factor... 介绍现在软件通常交付为一个服务：可以叫web应用，或软件即服务(SaaS)。1...

浠ラ箍 2019-08-16 12:38 评论0 收藏0