LeetCode面试必刷75题

🚲 🚗 ✈️ 🚀

🚀 交替合并字符串 - 简单

题目：

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。

如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回合并后的字符串。

示例 1：

输入：word1 = “abc”, word2 = “pqr”
输出：”apbqcr”
合并后： apbqcr

示例 2：

输入：word1 = “ab”, word2 = “pqrs”
输出：”apbqrs”
解释：注意，word2 比 word1 长，”rs” 需要追加到合并后字符串的末尾。
合并后：apbqrs

示例 3：

输入：word1 = “abcd”, word2 = “pq”
输出：”apbqcd”
解释：注意，word1 比 word2 长，”cd” 需要追加到合并后字符串的末尾。
合并后：apbqcd

题解 - 暴力求解

定义一个数组或列表，依次读取word1和word2的字符并存储在该数组上，最后返回该数组。

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        retstr = ''
        word1Len = len(word1)
        word2Len = len(word2)
        strLen   = word1Len + word2Len
        word1Index = 0
        word2Index = 0
        strIndex   = 0
        while strIndex < strLen:
            if word1Index < word1Len:
                retstr += word1[word1Index]
                word1Index += 1
                strIndex += 1
            if word2Index < word2Len:
                retstr += word2[word2Index]
                word2Index += 1
                strIndex += 1
        return retstr

# 测试
if __name__ == '__main__':
    word1List = ['abc', 'ab', 'abcd', '', 'abc', '', ' a  ']
    word2List = ['pqr', 'pqrs', 'pq', 'pqr', '', '', 'p q r']
    word3List = ['apbqcr', 'apbqrs', 'apbqcd', 'pqr', 'abc', '', ' pa  q  r']
    testNum = len(word1List)
    for i in range(testNum):
        word3 = Solution().mergeAlternately(word1List[i], word2List[i])
        if word3 != word3List[i]:
            print(f'Error: {word1List[i]} + {word2List[i]} = {word3}')

执行用时：48 ms, 在所有 Python3 提交中击败了20.64%的用户

内存消耗：16.2 MB, 在所有 Python3 提交中击败了5.28%的用户

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char * mergeAlternately(char * word1, char * word2){
    unsigned char word1Len = strlen(word1);
    unsigned char word2Len = strlen(word2);
    unsigned char lenSum   = word1Len + word2Len;
    char *retStr = (char *)malloc(lenSum+1);
    int i;
    unsigned char index1 = 0;
    unsigned char index2 = 0;

    if (lenSum == 0)
    {
        return "";
    }

    for (i = 0; i < lenSum;)
    {
        if (index1 < word1Len)
        {
            retStr[i] = word1[index1];
            i++;
            index1++;
        }
        if (index2 < word2Len)
        {
            retStr[i] = word2[index2];
            i++;
            index2++;
        }
    }

    retStr[i] = '\0';

    return retStr;
}

void main(void)
{
    char word1List[][8] = {"abc", "ab", "abcd", "", "abc", "", " a  "};
    char word2List[][8] = {"pqr", "pqrs", "pq", "pqr", "", "", "p q r"};
    char word3List[][16] = {"apbqcr", "apbqrs", "apbqcd", "pqr", "abc", "", " pa  q  r"};
    int testNum = sizeof(word1List) / 8;
    int i;
    char *pstr;

    for(i = 0; i < testNum; i++)
    {
        pstr = mergeAlternately(word1List[i], word2List[i]);
        if (strcmp(pstr, word3List[i]))
        {
            printf("num%d error: mergeAlternately(\"%s\", \"%s\") = \"%s\" \r\n", i, word1List[i], word2List[i], pstr);
        }
    }

}

执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户

内存消耗：5.9 MB, 在所有 C 提交中击败了5.46%的用户

优化

上面的解法用了一个变量来记录返回字符串的总长度，这个变量是可以被优化掉的，代码如下：

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        index = 0
        res = ''
        word1Len = len(word1)
        word2Len = len(word2)
        while index < word1Len or index < word2Len:
            if index < word1Len:
                res += word1[index]
            if index < word2Len:
                res += word2[index]
            index += 1
        return res

执行用时：36 ms, 在所有 Python3 提交中击败了82.96%的用户

内存消耗：16.1 MB, 在所有 Python3 提交中击败了13.34%的用户

char * mergeAlternately(char * word1, char * word2){
    unsigned char word1Len = strlen(word1);
    unsigned char word2Len = strlen(word2);
    unsigned char i, j = 0;
    char *retStr = (char *)malloc(word1Len + word2Len + 1);
    
    for (i = 0; (i < word1Len) || (i < word2Len); i++)
    {
        if (i < word1Len)
        {
            retStr[j++] = word1[i];
        }
        if (i < word2Len)
        {
            retStr[j++] = word2[i];
        }
    }
    retStr[j] = '\0';

    return retStr;
}

执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户

内存消耗：5.6 MB, 在所有 C 提交中击败了66.55%的用户

🚀 字符串的最大公因子 - 简单

题目：

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

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

示例 1：

输入：str1 = “ABCABC”, str2 = “ABC”
输出：”ABC”

示例 2：

输入：str1 = “ABABAB”, str2 = “ABAB”
输出：”AB”

示例 3：

输入：str1 = “LEET”, str2 = “CODE”
输出：””

题解

题目要求字符串 x 能除尽 str1 且 x 能除尽 str2，因此字符串 x 的长度必须为 str1 和 str2 的最大公因数。

以最大公因数对字符串 str1 进行切片，看看切片出来的字符串 str3 是否是 str1 和 str2 的子串。如果是，则str3 就是最大公因子。如果不是，则没有公因子。

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        str1Len = len(str1)
        str2Len = len(str2)
        divisor = gcd(str1Len, str2Len)	# 计算公因数
        
        retStr = ''
        if str1[0 : divisor] == str2[0 : divisor]:
            retStr = str1[0 : divisor]
            index = divisor
            while index + divisor <= str1Len:
                if retStr != str1[index : (index + divisor)]:
                    return ''
                index += divisor
            index = divisor
            while index + divisor <= str2Len:
                if retStr != str2[index : (index + divisor)]:
                    return ''
                index += divisor
        
        return retStr

if __name__ == '__main__':
    strList1 = ['ABCABC', 'ABABAB', 'LEET', 'ABCABCABCABC', 'ABCABCABCABC', 'ABCABCABCABD']
    strList2 = ['ABC', 'ABAB', 'CODE', 'ABCABCABCABC', 'ABCABC', 'ABCABC']
    strList3 = ['ABC', 'AB', '', 'ABCABCABCABC', 'ABCABC', '']
    listLen = len(strList1)
    for i in range(listLen):
        str1 = Solution().gcdOfStrings(strList1[i], strList2[i])
        if str1 != strList3[i]:
            print(f'Error: Solution().gcdOfStrings(strList1[i], strList2[i]) = \'{str1}\'')