LeetCode75 Day1

1768.交替合并字符串

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

示例 1：

1
2
3
4
5
6
输入：word1 = "abc", word2 = "pqr"
输出："apbqcr"
解释：字符串合并情况如下所示：
word1：  a   b   c
word2：    p   q   r
合并后：  a p b q c r

示例 2：

1
2
3
4
5
6
输入：word1 = "ab", word2 = "pqrs"
输出："apbqrs"
解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1：  a   b 
word2：    p   q   r   s
合并后：  a p b q   r   s

示例 3：

1
2
3
4
5
6
输入：word1 = "abcd", word2 = "pq"
输出："apbqcd"
解释：注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。
word1：  a   b   c   d
word2：    p   q 
合并后：  a p b q c   d

提示：

  • 1 <= word1.length, word2.length <= 100
  • word1 和 word2 由小写英文字母组成

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
char * mergeAlternately(char * word1, char * word2){
    char *ans=(char*)malloc(sizeof(char)*(strlen(word1)+strlen(word2)+1));
    int i,j,k=0;
    for(i=0,j=0;i<strlen(word1)&&j<strlen(word2);i++,j++)//此处循环不结束条件为双指针都没有到尾端
    {
        ans[k++]=word1[i];
        ans[k++]=word2[j];
    }
    if(strlen(word1)>strlen(word2))//判断两个字符串的长度把后面的字符补上
    for(;i<strlen(word1);i++)
        ans[k++]=word1[i];
    else if(strlen(word1)<strlen(word2))
    for(;j<strlen(word2);j++)
        ans[k++]=word2[j];
    ans[k]='\0';//别忘了最后的\0
    return ans;    
}

作者：喜欢玩亚索
链接：https://leetcode.cn/problems/merge-strings-alternately/solutions/2577413/jian-dan-mo-ni-by-brave-napiernqn-y1bi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1. 首先，函数通过 malloc 动态分配了足够的内存来存储合并后的字符串，这个内存大小是两个输入字符串长度之和加上一个额外的字符用于存储字符串结束的空字符 '\0'。
  2. 接下来使用两个循环变量 i 和 j 来遍历两个输入字符串 word1 和 word2，同时将它们的字符逐个交替放入新字符串 ans 中。这个过程在循环中进行，直到其中一个字符串的字符遍历完毕。
  3. 如果其中一个字符串遍历完了而另一个字符串还有剩余字符，那么需要继续将剩余字符添加到 ans 中。这部分代码使用了两个 if 条件来判断哪个字符串有剩余字符，并将剩余字符逐个添加到 ans 中。
  4. 最后，确保 ans 字符串以空字符 '\0' 结尾，以符合 C 语言字符串的约定。
  5. 返回合并后的字符串 ans。

image-20240329232337147

leetcode给出代码运行后的执行时间已经消耗内存，这个时候发现还有一个更快的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char * mergeAlternately(char * word1, char * word2){
    int len1 = strlen(word1),len2 = strlen(word2);
    char *result = (char*)calloc(len1+len2+1,sizeof(char));
    for(int i = 0,j = 0,k = 0;i < len1+len2;){
        if(word1[j] != '\0'){
            result[i++] = word1[j++];
        }
        if(word2[k] != '\0'){
            result[i++] = word2[k++];
        }
    }
    result[len1+len2] = '\0';
    return result;
}

image-20240329232621730

  1. 首先，通过 strlen 函数获取了 word1 和 word2 的长度，并分别存储在 len1 和 len2 变量中。
  2. 然后，使用 calloc 函数分配了足够的内存来存储合并后的字符串。calloc 与 malloc 类似，都用于动态分配内存，但是 calloc 在分配内存的同时会将分配的内存块中的每个字节都初始化为零。在这里，分配的内存大小为 len1 + len2 + 1，即两个输入字符串的长度之和再加上一个额外的字符 \0，用于存储字符串结束的空字符。
  3. 接下来，使用 for 循环遍历合并后的字符串的每个位置。循环变量 i 用于表示合并后字符串的当前位置，而 j 和 k 则分别用于遍历 word1 和 word2。
  4. 在循环中，通过判断 word1 和 word2 的当前字符是否为 \0，即判断是否到达字符串的结束，来决定是否将字符添加到合并后的字符串中。如果 word1 或 word2 还有字符未处理，则将其添加到合并后的字符串中，并且 i 的值递增。
  5. 最后，确保合并后的字符串以空字符 \0 结尾，以符合 C 语言字符串的约定。
  6. 返回合并后的字符串 result。

这段代码与之前的代码相比，使用了 calloc 函数分配内存，并且使用了单个循环来遍历两个字符串并将其合并，代码逻辑更加简洁。

相较于第一段代码用了多个for循环，这段代码只需要一个for循环，通过判断字符串是否为’\0’结尾。

1071.字符串的最大公因子

对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。

给定两个字符串 str1 和 str2 。返回最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

示例 1：

1
2
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

示例 2：

1
2
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

示例 3：

1
2
输入：str1 = "LEET", str2 = "CODE"
输出：""

提示：

  • 1 <= str1.length, str2.length <= 1000
  • str1 和 str2 由大写英文字母组成

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
char* gcdOfStrings(char* str1, char* str2) {
    int n1 = strlen(str1), n2 = strlen(str2);
    while (true) 
        if      (n1 == n2 && strncmp(str1, str2, n1) == 0) return str1;
        else if (n1 >  n2 && strncmp(str1, str2, n2) == 0) str1 += n2, n1 -= n2;
        else if (n1 <  n2 && strncmp(str1, str2, n1) == 0) str2 += n1, n2 -= n1;
        else                                               return "";            
}

作者：_G_
链接：https://leetcode.cn/problems/greatest-common-divisor-of-strings/solutions/2550547/zhan-zhuan-chu-li-c100-by-admiring-menin-pt83/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1. 首先，通过 strlen 函数获取了 str1 和 str2 的长度，并分别存储在 n1 和 n2 变量中。
  2. 使用 while 循环进行迭代处理，直到找到最大公因子或者无法继续进行迭代为止。
  3. 在每次循环中，通过 strncmp 函数比较 str1 和 str2 的前 n1 或 n2 个字符是否相等，以判断它们是否是共有的前缀或后缀。
  4. 如果两个字符串的长度相等，并且它们的前 n1 个字符相等，则表示整个字符串都是共有的最大公因子，直接返回 str1。
  5. 如果 str1 的长度大于 str2 的长度，并且 str1 的前 n2 个字符与 str2 相等，则将 str1 的指针向后移动 n2 个字符，同时更新 n1 为原来的长度减去 n2。
  6. 如果 str1 的长度小于 str2 的长度，并且 str1 的前 n1 个字符与 str2 相等，则将 str2 的指针向后移动 n1 个字符，同时更新 n2 为原来的长度减去 n1。
  7. 如果以上情况都不满足，则表示没有找到公因子，直接返回空字符串 ""。
  8. 循环继续进行，直到找到最大公因子或者无法继续迭代。
  9. 返回找到的最大公因子或空字符串。

总的来说，这段代码利用了字符串的前缀和后缀的性质来寻找两个字符串的最大公因子，通过不断地比较和调整字符串的长度和指针位置来达到这个目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char* gcdOfStrings(char* str1, char* str2) {
    int len1=strlen(str1);
    int len2=strlen(str2);
    while(1){
        if(len1==len2&&strncmp(str1,str2,len1)==0){
            return str1;
        }else if(len1>len2&&strncmp(str1,str2,len2)==0){
            str1+=len2;
            len1-=len2;
        }else if(len1<len2&&strncmp(str1,str2,len1)==0){
            str2+=len1;
            len2-=len1;
        }else{
            return "";
        }
    }
}
  1. 首先，通过 strlen 函数获取了 str1 和 str2 的长度，并分别存储在 len1 和 len2 变量中。
  2. 使用 while(1) 循环进行迭代处理，直到找到最大公因子或者无法继续进行迭代为止。while(1) 是一个无限循环，表示会一直执行循环内的代码，直到遇到 return 语句或者 break 语句终止循环。
  3. 在每次循环中，通过 strncmp 函数比较 str1 和 str2 的前 len1 或 len2 个字符是否相等，以判断它们是否是共有的前缀或后缀。
  4. 如果两个字符串的长度相等，并且它们的前 len1 个字符相等，则表示整个字符串都是共有的最大公因子，直接返回 str1。
  5. 如果 str1 的长度大于 str2 的长度，并且 str1 的前 len2 个字符与 str2 相等，则将 str1 的指针向后移动 len2 个字符，同时更新 len1 为原来的长度减去 len2。
  6. 如果 str1 的长度小于 str2 的长度，并且 str1 的前 len1 个字符与 str2 相等，则将 str2 的指针向后移动 len1 个字符，同时更新 len2 为原来的长度减去 len1。
  7. 如果以上情况都不满足，则表示没有找到公因子，直接返回空字符串 ""。
  8. 循环继续进行，直到找到最大公因子或者无法继续迭代。
  9. 返回找到的最大公因子或空字符串。

这段代码与之前解释的代码逻辑相同，只是将 while 循环的终止条件改为了 while(1)，代表无限循环。