0615学习

agile Posted on Jun 20 2023

面试 leetcode学习

-    字符串的最大公因子-1071
对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

---

```C#
public string GcdOfStrings(string str1, string str2)
{
    var str1Length = str1.Length;
    var str2Length = str2.Length;

var gcd = __Gcd(str1Length, str2Length);
    var cdList = _Allcd(gcd);
    foreach (var l in cdList)
    {
        var gcdStr = str1.Substring(0, l);

if (__IsGcdString(str1, gcdStr, l, 1) && __IsGcdString(str2, gcdStr, l, 0))
        {
            return gcdStr;
        }
    }

return "";
}

private bool __IsGcdString(string str, string gcdStr, int l, int index)
{
    var strLength = str.Length;
    var gcdNum = strLength / l;
    for (var i = 0; i < l; i++)
    {
        var c = gcdStr[i];
        for (var j = index; j < gcdNum; j++)
        {
            var cs = str[j * l + i];
            if (cs != c)
            {
                return false;
            }
        }
    }

return true;
}

private int __Gcd(int a, int b)
{
    return b == 0 ? a : __Gcd(b, a % b);
}

将 1 ~ sqrt(n)的所有数枚举一遍，如果能被n整除，且这个数不等于 n 除以其本身，则将该数和n除以该数的值双双存入，否则，就仅存该数，另外，如果不能被n整除，就进入下一次循环
private List<int> _Allcd(int gcd)
{
    var res = new List<int> { gcd };
    if (gcd == 1)
    {
        return res;
    }

var sq = (int)Math.Sqrt(gcd);
    for (var i = sq; i >= 2; i--)
    {
        if (gcd % i == 0)
        {
            var other = gcd / i;
            if (other != i)
            {
                res.Add(other);
            }

res.Add(i);
        }
    }

res.Sort(delegate(int i, int i1)
    {
        if (i > i1)
        {
            return -1;
        }

return 1;
    });

return res;
}
```

---
最快的方法
需要知道一个性质：如果 str1 和 str2 拼接后等于 str2和 str1 拼接起来的字符串（注意拼接顺序不同），那么一定存在符合条件的字符串 X。

先证必要性，即如果存在符合条件的字符串 X ，则 str1 和 str2 拼接后等于 str2和 str1 拼接起来的字符串。

如果字符串 X 符合条件，那么 str1=X+X+...+X+X=n*X ，str2=X+X+..+X+X=m*X，n*X 表示 n 个字符串 X 拼接，m*X 同理，则 str1 与 str2 拼接后的字符串即为 (n+m)*X，而 str2 与 str1 拼接后的字符串即为 (m+n)*X，等于 (n+m)*X，所以必要性得证。

再看充分性，简单来说，我们可以如下图一样先将两个拼接后的字符串放在一起。不失一般性，我们假定 str1 的长度大于 str2，

---

```C#
public string GcdOfStrings2(string str1, string str2)
{
    if (str1 + str2 != str2 + str1)
    {
        return "";
    }

int gcd = __Gcd(str1.Length, str2.Length);

return str1.Substring(0, gcd);
}

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数

private int __Gcd(int a, int b)
{
    return b == 0 ? a : __Gcd(b, a % b);
}
```