1. 代码段小站首页
  2. 算法

leetcode1071-字符串的最大公因子

彭晨涛 • • 算法 • 阅读 24

原题

对于字符串 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. 1 <= str1.length <= 1000
  2. 1 <= str2.length <= 1000
  3. str1[i] 和 str2[i] 为大写英文字母

解法

思想

这道题我之前想得很复杂！结果一看题解：卧槽还能这样。给大佬们跪了。

确实好久没接触这样的数学知识了：辗转相除法。

首先如果str1和str2有最大公因子，那么str1+str2就会等于str2+str1。

然后就是考虑怎么把最大公因子子字符串取出来，说实话辗转相除法我是没想到的，百度百科：

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

这样求出两个字符串的长度的最大公因数，就是子字符串的长度，然后用substring取出来。

代码

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if(!(str1+str2).equals(str2+str1)) return "";
        return str1.substring(0,gcd(str1.length(),str2.length()));
    }
    public int gcd(int x,int y){
        return x%y==0?y:gcd(y,x%y);
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode1071-%e5%ad%97%e7%ac%a6%e4%b8%b2%e7%9a%84%e6%9c%80%e5%a4%a7%e5%85%ac%e5%9b%a0%e5%ad%90/

赞 (1)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年3月11日 23:40
下一篇 2020年3月12日 16:38

相关推荐

  • 剑指offer57-和为s的连续正数序列

    原题（来源Leetcode） 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到...

    彭晨涛 彭晨涛
    算法 2020年3月6日
    050

  • leetcode876-链表的中间结点

    原题 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1: 输入： [1,2,3,4,5] 输出： 此列表中的结...

    彭晨涛 彭晨涛
    算法 2020年3月23日
    080
  • leetcode380-常数时间插入、删除和获取随机元素 算法

    leetcode380-常数时间插入、删除和获取随机元素

    原题 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。 insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 v...

    彭晨涛 彭晨涛
    2019年12月28日
    080
  • leetcode11-盛最多水的容器 算法

    leetcode11-盛最多水的容器

    原题 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i,...

    彭晨涛 彭晨涛
    2020年2月27日
    0220

  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...

    彭晨涛 彭晨涛
    算法 2019年12月18日
    0110

  • leetcode387-字符串中的第一个唯一字符

    原题 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"...

    彭晨涛 彭晨涛
    算法 2019年12月22日
    0110

  • leetcode1103-分糖果II

    原题 排排坐，分糖果。 我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类...

    彭晨涛 彭晨涛
    算法 2020年3月5日
    0130

  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...

    彭晨涛 彭晨涛
    算法 2019年12月18日
    0130

  • leetcode100-相同的树

    原题 给定两个二叉树，编写一个函数来检验它们是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 ...

    彭晨涛 彭晨涛
    算法 2020年5月7日
    0180

  • leetcode289-生命游戏

    原题 根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞...

    彭晨涛 彭晨涛
    算法 2020年4月2日
    0250

发表回复

登录后才能评论