5076-字符串的最大公因子

sourcenode 發布于2019-08-16 17:48 / 1963人閱讀

摘要：前言的字符串的最大公因子對于字符串和，只有在與自身連接次或多次時，我們才認定能除盡。返回字符串，要求滿足能除盡且能除盡。

前言

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

GPU云服務器云服務器最大公因子算法字符串最大子串c語言公對公轉賬密碼因子

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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