leetcode1071-字符串的最大公因子

原题

对于字符串 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)
彭晨涛彭晨涛管理者
上一篇 2020年3月11日 23:40
下一篇 2020年3月12日 16:38

相关推荐

  • leetcode974-和可被K整除的子数组

    原题 给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。 示例: 输入: A = [4,5,0,-2,-3,1], K = 5 输出: 7 解释: …

    算法 2020年5月27日
    0170
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    090
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0210
  • leetcode74-搜索二维矩阵

    原题 编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性: 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。   示例…

    算法 2020年4月29日
    0200
  • leetcode81-搜索旋转排序数组II

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定…

    算法 2020年5月30日
    060
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    070
  • leetcode374-猜数字大小

    原题 我们正在玩一个猜数字游戏。 游戏规则如下:我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了,我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接…

    算法 2019年12月31日
    0370
  • leetcode331-验证二叉树的前序序列化

    原题 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。 _9_ / \ 3 2…

    算法 2020年1月26日
    080
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0100
  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0150

发表回复

登录后才能评论