必会的10个经典算法题(附解析答案代码Java/C/Python看这一篇就够)（二）-阿里云开发者社区

续：必会的10个经典算法题(附解析答案代码Java/C/Python看这一篇就够)（一）：https://developer.aliyun.com/article/1529650

对称二叉树（LeetCode 101,Easy）

标签：二叉树递归、对称性判断

题目

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3] 输出：true 示例 2：

输入：root = [1,2,2,null,3,null,3] 输出：false

提示：

树中节点数目在范围 [1, 1000] 内

-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

原题： LeetCode 101

思路及实现

方式一：递归（推荐）

思路

乍一看无从下手，但用递归其实很好解决。

根据题目的描述，镜像对称，就是左右两边相等，也就是左子树和右子树是相当的。

注意这句话，左子树和右子相等，也就是说要递归的比较左子树和右子树。

我们将根节点的左子树记做 left，右子树记做 right。比较 left 是否等于 right，不等的话直接返回就可以了。

如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点

比如看下面这两个子树(他们分别是根节点的左子树和右子树)，能观察到这么一个规律：

左子树 2 的左孩子 == 右子树 2 的右孩子

左子树 2 的右孩子 == 右子树 2 的左孩子

根据上面信息可以总结出递归函数的两个终止条件：

left 和 right 不等，或者 left 和 right 都为空

递归的比较 left，left 和 right.right，递归比较
left，right 和 right.left

代码实现

Java版本

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;  // 如果根节点为null，即空树，视为对称二叉树，返回true
        }
        return isMirror(root.left, root.right);  // 调用isMirror方法判断左子树和右子树是否对称
    }
    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;  // 如果左子树和右子树都为null，也视为对称，返回true
        }
        if (left == null || right == null) {
            return false;  // 如果左子树和右子树只有一个为null，视为不对称，返回false
        }
        return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left);
        // 如果左子树和右子树的值相等，且同时满足左子树的左子树和右子树的右子树对称，
        // 以及左子树的右子树和右子树的左子树对称，则视为对称，返回true；否则，返回false
    }
}

说明：

isSymmetric方法是该函数的入口，接收一个二叉树的根节点作为参数。首先判断根节点是否为null，如果是，即空树，视为对称二叉树，返回true。否则，调用isMirror 方法来判断左子树和右子树是否对称。

isMirror方法是递归判断左右子树是否对称的函数。首先判断左子树和右子树是否都为null，如果是，即均为空树，视为对称，返回true。然后判断左子树和右子树中只有一个为null的情况，即一个为空树一个不为空树，视为不对称，返回false。最后，判断左子树的值和右子树的值是否相等，并且同时递归判断左子树的左子树和右子树的右子树是否对称，以及递归判断左子树的右子树和右子树的左子树是否对称。只有全部满足才视为对称，返回true；否则，返回false。

C语言版本

#include <stdbool.h>
/*struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
*/
bool isMirror(struct TreeNode *left, struct TreeNode *right);
bool isSymmetric(struct TreeNode *root) {
    if (root == NULL) {
        return true;   // 如果根节点为NULL，即空树，视为对称二叉树，返回true
    }
    return isMirror(root->left, root->right);   // 调用isMirror函数判断左子树和右子树是否对称
}
bool isMirror(struct TreeNode *left, struct TreeNode *right) {
    if (left == NULL && right == NULL) {
        return true;    // 如果左子树和右子树都为NULL，也视为对称，返回true
    }
    if (left == NULL || right == NULL) {
        return false;   // 如果左子树和右子树只有一个为NULL，视为不对称，返回false
    }
    return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left);
    // 如果左子树和右子树的值相等，并且同时满足左子树的左子树和右子树的右子树对称，
    // 以及左子树的右子树和右子树的左子树对称，则视为对称，返回true；否则，返回false
}

Python3版本

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True  # 如果根节点为空，返回True，空树被认为是对称的
        return self.isMirror(root.left, root.right)
    def isMirror(self, left: TreeNode, right: TreeNode) -> bool:
        if left is None and right is None:
            return True  # 如果左子树和右子树都为空，认为是对称的
        if left is None or right is None:
            return False  # 如果左子树和右子树只有一个为空，不对称
        return left.val == right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)
        # 比较左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树，满足条件才认为是对称的
# 假设定义了TreeNode类，包含val、left和right属性
class TreeNode:
    def __init__(self, val: int = 0, left: TreeNode = None, right: TreeNode = None):
        self.val = val
        self.left = left
        self.right = right

说明：代码中使用了 TreeNode 类来定义树节点，包含 val、left 和 right 属性。其中 val 存储节点的值，left 和

right 存储左子树和右子树的引用。

复杂度分析

时间复杂度：O(n)，其中 n 表示树的节点数。
空间复杂度：O(n)，递归调用的栈空间最多为树的高度。

方式二：队列（迭代）

思路

回想下递归的实现：

当两个子树的根节点相等时，就比较:

左子树的 left 和右子树的 right，这个比较是用递归实现的。

现在我们改用队列来实现，思路如下：

首先从队列中拿出两个节点(left 和 right)比较：

将 left 的 left 节点和 right 的 right 节点放入队列

将 left 的 right 节点和 right 的 left 节点放入队列

代码实现

Java版本

//leetcode submit region begin(Prohibit modification and deletion)
import java.util.LinkedList;
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return false;  // 根节点为空，不算对称
        }
        if (root.left == null && root.right == null) {
            return true;  // 左右子树都为空，算对称
        }
        
        LinkedList<TreeNode> queue = new LinkedList();  // 使用队列来保存待比较的节点
        queue.add(root.left);
        queue.add(root.right);
        
        while (queue.size() > 0) {
            TreeNode left = queue.removeFirst();
            TreeNode right = queue.removeFirst();
            
            // 只要两个节点都为空，继续循环；两者有一个为空，返回false
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            
            // 判断两个节点的值是否相等
            if (left.val != right.val) {
                return false;
            }
            
            // 将左节点的左子节点和右节点的右子节点放入队列
            queue.add(left.left);
            queue.add(right.right);
            
            // 将左节点的右子节点和右节点的左子节点放入队列
            queue.add(left.right);
            queue.add(right.left);
        }
        
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

说明：

这段代码使用迭代方法判断二叉树是否对称。

在 isSymmetric 方法中，首先判断根节点是否为空，如果为空，返回 false，表示不对称。然后，如果根节点的左右子树都为空，返回 true，表示对称（只有一个元素的case）。

接下来，创建一个队列 queue，并将根节点的左子节点和右子节点加入队列。然后进入循环，每次从队列中取出两个节点进行比较。在比较过程中，只要两个节点均为空，继续循环；如果只有一个节点为空，返回

false，表示不对称。然后，比较两个节点的值是否相等，如果不相等，返回 false。

将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。

当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回 true，表示对称。

这段代码使用了迭代方法，利用队列存储待比较的节点，逐层按顺序比较，避免了递归方法的额外栈空间开销。

C语言版本

// leetcode submit region begin(Prohibit modification and deletion)
#include <stdbool.h>
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
bool isSymmetric(struct TreeNode* root) {
    if (root == NULL) {
        return false;  // 根节点为空，不算对称
    }
    
    struct TreeNode* queue[10000];  // 使用队列来保存待比较的节点
    int front = 0, rear = 0;
    
    queue[rear++] = root->left;
    queue[rear++] = root->right;
    
    while (rear != front) {
        struct TreeNode* left = queue[front++];
        struct TreeNode* right = queue[front++];
        
        // 只要两个节点都为空，继续循环；两者有一个为空，返回false
        if (left == NULL && right == NULL) {
            continue;
        }
        if (left == NULL || right == NULL) {
            return false;
        }
        
        // 判断两个节点的值是否相等
        if (left->val != right->val) {
            return false;
        }
        
        // 将左节点的左子节点和右节点的右子节点放入队列
        queue[rear++] = left->left;
        queue[rear++] = right->right;
        
        // 将左节点的右子节点和右节点的左子节点放入队列
        queue[rear++] = left->right;
        queue[rear++] = right->left;
    }
    
    return true;
}
//leetcode submit region end(Prohibit modification and deletion)

说明：

这段代码使用C语言实现了迭代方法来判断二叉树是否对称。

在 isSymmetric 函数中，首先判断根节点是否为空，如果为空，返回 false，表示不对称。

创建一个队列 queue，使用数组来保存待比较的节点。使用 front 和 rear 变量分别表示队首和队尾的索引。

将根节点的左子节点和右子节点依次加入队列 queue。

然后进入循环，每次从队列中取出两个节点进行比较。

在比较过程中，只要两个节点均为空，继续循环；如果只有一个节点为空，返回

false，表示不对称。然后，比较两个节点的值是否相等，如果不相等，返回 false。

将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。

当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回 true，表示对称。

这段代码使用了迭代方法，利用数组队列方式存储待比较的节点，逐个按序比较，避免了递归方法的额外栈空间开销。

Python3版本

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return False  # 根节点为空，不算对称
        
        queue = []
        queue.append(root.left)
        queue.append(root.right)
        
        while queue:
            left = queue.pop(0)
            right = queue.pop(0)
            
            if left is None and right is None:
                continue  # 只要两个节点都为空，继续循环
            
            if left is None or right is None:
                return False  # 两者有一个为空，返回False，不对称
            
            if left.val != right.val:
                return False  # 节点值不相等，不对称
            
            queue.append(left.left)  # 左节点的左子节点入队列
            queue.append(right.right)  # 右节点的右子节点入队列
            queue.append(left.right)  # 左节点的右子节点入队列
            queue.append(right.left)  # 右节点的左子节点入队列
        
        return True  # 队列为空，所有节点比较完毕，对称

说明：（基础说明可查看java或者c的实现）

在函数参数的类型注解中，使用了 TreeNode 类型来标注 root 参数的类型。

使用了 is 运算符来判断节点是否为 None。is 运算符比较的是对象的身份标识，用于判断对象是否是同一个对象。这里用它来判断节点是否为None。

使用了列表 queue 来实现队列的功能，通过 append() 方法将节点加入队列的尾部，通过 pop(0)
方法来从队列的头部取出节点。Python的列表可以很方便地实现队列的功能。

复杂度分析

时间复杂度：O(n)，其中 n 表示树的节点数。在最坏情况下，需要遍历树的所有节点。
空间复杂度：O(n)，最坏情况下，队列中需要存储树的一层节点，所以空间复杂度与树的高度有关。在最坏情况下，树的高度为 n/2，因此空间复杂度为 O(n)。
综合来看，这个算法的时间复杂度和空间复杂度都是 O(n)，其中 n 表示树的节点数。算法的性能随着节点数的增加而线性增长。

两个数组的交集 II（LeetCode 350,Easy）

标签：哈希表、数组

题目

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，
应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

思路及实现

方式一：哈希表

思路

由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

代码实现

Java版本

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> numMap = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        
        // 遍历 nums1 数组，将元素及其出现次数存储在哈希表中
        for (int num : nums1) {
            numMap.put(num, numMap.getOrDefault(num, 0) + 1);
        }
        // 遍历 nums2 数组，检查每个元素是否在哈希表中出现
        // 如果出现，将该元素添加到结果集中，并将哈希表中的对应出现次数减1
        for (int num : nums2) {
            if (numMap.containsKey(num) && numMap.get(num) > 0) {
                res.add(num);
                numMap.put(num, numMap.get(num) - 1);
            }
        }
        
        // 将结果集转换为数组输出
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        
        return result;
    }
}

说明：

使用哈希表来求解两个数组的交集，并将结果集转换为数组输出。

首先创建一个哈希表 numMap 来存储第一个数组 nums1 中每个元素及其出现的次数。创建一个列表 res 来存储交集结果。遍历

nums2 数组，对于每个元素 num，检查其是否在哈希表 numMap 中出现且出现次数大于 0。如果满足条件，则将该元素加入结果集res 中，并将哈希表中对应出现次数减 1。将结果集 res 转换为数组输出。返回最终的结果数组。

tips优化空间：

哈希表 numMap 只用来存储 nums1 中的元素及其出现次数，而不是存储两个数组的交集。可以减少额外空间的使用。

结果集 res 使用列表存储交集结果，并在最后将其转换为数组输出。优化空间后的复杂度分析与之前相同，时间复杂度为 O(m +

n)，空间复杂度为 O(min(m, n))。其中 m 和 n 分别表示两个输入数组的长度。

C语言版本

#include <stdio.h>
#include <stdlib.h>
/**
 * 返回两个整数中的较小值
 */
int min(int a, int b) {
    return a < b ? a : b;
}
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    // 使用哈希表来存储nums1中每个元素及其出现的次数
    int* numMap = (int*) malloc(sizeof(int) * 1001);
    for (int i = 0; i < nums1Size; i++) {
        numMap[nums1[i]]++;
    }
    int* res = (int*) malloc(sizeof(int) * min(nums1Size, nums2Size));  // 结果集使用动态分配的数组来存储
    int resSize = 0;  // 结果集的大小
    // 遍历nums2数组，检查每个元素在哈希表中是否存在
    // 如果存在且对应出现次数大于0，则加入结果集，并将对应出现次数减1
    for (int i = 0; i < nums2Size; i++) {
        if (numMap[nums2[i]] > 0) {
            res[resSize++] = nums2[i];
            numMap[nums2[i]]--;
        }
    }
    *returnSize = resSize;  // 将结果集的大小赋给返回值
    free(numMap);  // 释放动态分配的内存
    return res;  // 返回结果集数组的指针
}

说明：

使用数组 numMap 来存储 nums1 数组中每个元素及其出现的次数，数组下标表示元素值。遍历 nums2 数组，对于每个元素nums2[i]，如果 numMap[nums2[i]] 大于 0，则将 nums2[i] 添加到结果集 res 中，并将

numMap[nums2[i]] 减 1。使用动态分配的数组 res 来存储交集结果，动态分配的内存大小为较小的数组大小

min(nums1Size, nums2Size)。将结果集的大小 resSize 赋给

returnSize，即将结果集的大小返回给调用函数。使用 free() 函数释放动态分配的内存。

Python3版本

class Solution:
    def intersect(self, nums1, nums2):
        # 使用哈希表来存储nums1中每个元素及其出现的次数
        numMap = {}
        for num in nums1:
            numMap[num] = numMap.get(num, 0) + 1
        res = []
        # 遍历nums2数组，检查每个元素在哈希表中是否存在
        # 如果存在且对应出现次数大于0，则加入结果集，并将对应出现次数减1
        for num in nums2:
            if num in numMap and numMap[num] > 0:
                res.append(num)
                numMap[num] -= 1
        return res

说明：

使用字典 numMap 来存储 nums1 数组中每个元素及其出现的次数。遍历 nums2 数组，对于每个元素 num，如果num 在 numMap 中存在且对应出现次数大于 0，则将 num 添加到结果集 res 中，并将 numMap[num] 减 1。返回结果集 res。

复杂度分析

时间复杂度：O(max(m, n))，其中 m 和 n 分别表示两个输入数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。
空间复杂度：O(min(m, n))，表示两个输入数组中较小的那个数组的长度

方式二：排序 + 双指针

思路

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

代码实现

Java版本

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // 对两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        // 获取两个数组的长度
        int length1 = nums1.length, length2 = nums2.length;
        
        // 创建结果数组，长度为两个数组中较小的长度
        int[] intersection = new int[Math.min(length1, length2)];
        
        // 初始化指针和结果数组的索引
        int index1 = 0, index2 = 0, index = 0;
        
        // 双指针法求交集
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;  // nums1的元素较小，移动nums1的指针
            } else if (nums1[index1] > nums2[index2]) {
                index2++;  // nums2的元素较小，移动nums2的指针
            } else {
                // 相等，加入结果数组，同时移动两个指针和结果数组的索引
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        
        // 返回交集结果数组，利用Arrays.copyOfRange()截取结果数组的有效部分
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

说明：

首先，对两个输入的数组 nums1 和 nums2 进行排序，这里使用了 Arrays.sort() 方法。时间复杂度为

O(nlogn)，其中 n 分别表示两个数组的长度。初始化指针 index1 和 index2 分别指向数组 nums1 和 nums2

的起始位置，同时初始化结果数组的索引 index 为 0。创建结果数组 intersection，长度为两个数组长度较小的那个。

使用双指针法进行比较：如果 nums1[index1] 小于 nums2[index2]，说明 nums1 的元素较小，将 index1

向后移动。如果 nums1[index1] 大于 nums2[index2]，说明 nums2 的元素较小，将 index2 向后移动。

如果 nums1[index1] 等于 nums2[index2]，说明找到了一个交集元素，将该元素加入结果数组 intersection

中，并将两个指针和结果数组的索引都向后移动。当有一个指针越界时，表示已经遍历完其中一个数组，此时得到的结果数组即为两个数组的交集。

最后，利用 Arrays.copyOfRange() 方法截取结果数组 intersection 的有效部分（0 到

index-1），并返回新的数组作为输出。

C语言版本

#include <stdlib.h>
int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}
int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
    // 对两个数组进行排序
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);
    // 创建结果数组，长度为两个数组中较小的大小
    int *intersection = (int *)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));
    // 初始化指针和结果数组索引
    int index1 = 0, index2 = 0, index = 0;
    // 双指针法求交集
    while (index1 < nums1Size && index2 < nums2Size) {
        if (nums1[index1] < nums2[index2]) {
            index1++;  // nums1的元素较小，移动nums1的指针
        } else if (nums1[index1] > nums2[index2]) {
            index2++;  // nums2的元素较小，移动nums2的指针
        } else {
            // 相等，加入结果数组，同时移动两个指针和结果数组的索引
            intersection[index] = nums1[index1];
            index1++;
            index2++;
            index++;
        }
    }
    // 返回交集结果数组的大小
    *returnSize = index;
    return intersection;
}

说明：

使用qsort()函数对输入的两个数组nums1和nums2进行排序。这里使用了自定义的比较函数cmp()来指定排序规则。排序后，两个数组中的元素将按照从小到大的顺序排列。

创建一个结果数组intersection，长度为两个数组中较小的那个。使用动态内存分配函数malloc()来分配存储交集结果所需的内存空间。

初始化两个指针index1和index2，分别指向数组nums1和nums2的起始位置。同时，初始化结果数组的索引index为0。

使用双指针法进行比较遍历：如果nums1[index1]小于nums2[index2]，说明nums1的元素较小，将index1向后移动。

如果nums1[index1]大于nums2[index2]，说明nums2的元素较小，将index2向后移动。

如果nums1[index1]等于nums2[index2]，说明找到了一个交集元素，将该元素加入结果数组intersection中，并将两个指针和结果数组的索引都向后移动。

当有一个指针越界时，表示已经遍历完其中一个数组，此时得到的结果数组即为两个数组的交集。

使用指针returnSize来记录交集结果数组的大小。返回交集结果数组intersection的指针。

Python3版本

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 对两个数组进行排序
        nums1.sort()
        nums2.sort()
        # 获取两个数组的长度
        length1, length2 = len(nums1), len(nums2)
        # 创建一个空列表来存储交集结果
        intersection = list()
        # 初始化两个指针
        index1 = index2 = 0
        # 双指针法求交集
        while index1 < length1 and index2 < length2:
            if nums1[index1] < nums2[index2]:
                index1 += 1
            elif nums1[index1] > nums2[index2]:
                index2 += 1
            else:
                # 相等，加入结果列表，同时移动两个指针
                intersection.append(nums1[index1])
                index1 += 1
                index2 += 1
        
        # 返回交集结果列表
        return intersection

说明：

对输入的两个数组nums1和nums2进行排序，这里使用了Python内置的sort()方法，能在原地排序。

创建一个空列表intersection来存储交集结果。

使用双指针法进行比较，分别初始化index1和index2为0，它们分别指向数组nums1和nums2的起始位置。

遍历两个数组，比较当前指针位置上的元素大小。如果nums1[index1]小于nums2[index2]，则index1向右移动。

如果nums1[index1]大于nums2[index2]，则index2向右移动。

如果nums1[index1]等于nums2[index2]，则找到一个交集元素，加入结果列表intersection中，并同时移动两个指针。

当有一个指针越界时，表示已经遍历完其中一个数组，那么结果列表intersection中存储的就是两个数组的交集。

返回交集结果列表intersection。

复杂度分析

时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。
空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。不过在 C++ 中，我们可以直接创建一个 vector，不需要把答案临时存放在一个额外的数组中，所以这种实现的空间复杂度为 O(1)。

最长公共前缀（LeetCode 14,Easy）

标签：字符串处理、前缀判断

题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

原题：LeetCode 14

思路及实现

方式一：横向扫描

思路

代码实现

Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或者长度为0，则返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }
        // 将第一个字符串作为前缀进行初始化
        String prefix = strs[0];
        // 数组中字符串的数量
        int count = strs.length;
        // 遍历字符串数组，依次求取最长公共前缀
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            // 如果最长公共前缀为空，则可以提前结束循环
            if (prefix.length() == 0) {
                break;
            }
        }
        // 返回最长公共前缀
        return prefix;
    }
    // 求取两个字符串的最长公共前缀
    public String longestCommonPrefix(String str1, String str2) {
        // 获取两个字符串的最小长度
        int length = Math.min(str1.length(), str2.length());
        // 初始化索引
        int index = 0;
        // 遍历两个字符串，找到最长公共前缀的结束索引
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        // 返回最长公共前缀
        return str1.substring(0, index);
    }
}

说明：

首先，通过判断字符串数组strs是否为空或长度为0，来确定是否存在最长公共前缀。如果数组为空或长度为0，则直接返回空字符串。

将字符串数组中的第一个字符串作为初始化的最长公共前缀prefix。

使用一个循环遍历剩余的字符串，依次计算最长公共前缀。在每次循环中，调用longestCommonPrefix()方法，将当前最长公共前缀prefix和当前遍历的字符串进行比较，更新最长公共前缀。

如果最长公共前缀为空字符串，则说明不存在公共前缀，无需继续循环，直接跳出。最后，返回最长公共前缀prefix。

longestCommonPrefix()方法是一个内部方法，用于找到两个字符串str1和str2的最长公共前缀。

首先，获取两个字符串的最小长度length。初始化索引index为0。

遍历两个字符串，比较对应位置的字符是否相等，直到遇到不相等的字符或到达较短字符串的末尾。

最后，返回前缀部分的字符串，即str1中的前index个字符。

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空或者长度为0，则返回空字符串
    if (strs == NULL || strsSize == 0)
        return "";
    // 将第一个字符串作为初始的最长公共前缀
    char* prefix = strs[0];
    // 遍历数组剩余的字符串，更新最长公共前缀
    for (int i = 1; i < strsSize; i++) {
        prefix = lcp(prefix, strs[i]);
        
        // 如果最长公共前缀为空，则跳出循环
        if (prefix[0] == '\0')
            break;
    }
    
    return prefix;
}

说明：

longestCommonPrefix() 函数用于找到字符串数组 strs 中的最长公共前缀。

首先，判断字符串数组是否为空或长度为0，如果是，则直接返回空字符串。将数组的第一个字符串作为初始的最长公共前缀 prefix。

遍历数组剩余的字符串，调用 lcp() 函数计算当前字符串与当前最长公共前缀的公共前缀，并更新最长公共前缀 prefix。

如果最长公共前缀为空字符串，则无需继续遍历，跳出循环。返回最长公共前缀 prefix。 lcp() 函数用于找到两个字符串 str1 和str2 的最长公共前缀。获取两个字符串的最小长度 length。初始化索引 index 为0。

遍历两个字符串，比较对应位置的字符是否相等，直到遇到不相等的字符或到达较短字符串的末尾。创建一个新的字符串来存储最长公共前缀commonPrefix。

使用 strncpy() 函数从 str1 复制 index 个字符到 commonPrefix 中。在

commonPrefix 的末尾添加字符串结束符 ‘\0’。返回最长公共前缀 commonPrefix。

Python3版本

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 如果字符串数组为空，则返回空字符串
        if not strs:
            return ""
        
        # 将数组的第一个字符串作为初始的最长公共前缀
        prefix, count = strs[0], len(strs)
        
        # 遍历数组剩余的字符串，更新最长公共前缀
        for i in range(1, count):
            prefix = self.lcp(prefix, strs[i])
            
            # 如果最长公共前缀为空，则跳出循环
            if not prefix:
                break
        
        return prefix
    
    # 求取两个字符串的最长公共前缀
    def lcp(self, str1, str2):
        # 获取两个字符串的最小长度
        length, index = min(len(str1), len(str2)), 0
        
        # 遍历两个字符串，找到最长公共前缀的结束索引
        while index < length and str1[index] == str2[index]:
            index += 1
        
        # 返回最长公共前缀
        return str1[:index]
•

说明：

longestCommonPrefix()方法是一个类方法，用于找到字符串数组strs中的最长公共前缀。

首先，判断字符串数组是否为空，如果为空，则直接返回空字符串。将数组的第一个字符串作为初始的最长公共前缀 prefix。

获取数组中的字符串数量 count。使用一个循环遍历剩余的字符串，调用 lcp()

方法来计算当前字符串与当前最长公共前缀的公共前缀，并更新最长公共前缀 prefix。如果最长公共前缀为空字符串，则无需继续遍历，跳出循环。

返回最长公共前缀 prefix。 lcp() 方法是一个类方法，用于找到两个字符串 str1 和 str2 的最长公共前缀。

获取两个字符串的最小长度 length。初始化索引 index 为0。

遍历两个字符串，比较对应位置的字符是否相等，直到遇到不相等的字符或到达较短字符串的末尾。返回前缀部分的字符串，即 str1 中的前

index 个字符。

复杂度分析

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。

方式二：纵向扫描

思路

方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

代码实现

Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或者长度为0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }
        // 获取第一个字符串的长度和数组的长度
        int length = strs[0].length();
        int count = strs.length;
        // 遍历第一个字符串的每个字符
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            // 遍历剩余的字符串进行比较
            for (int j = 1; j < count; j++) {
                // 如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，返回前缀部分
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        // 返回第一个字符串作为最长公共前缀
        return strs[0];
    }
}

说明：

longestCommonPrefix() 方法用于寻找字符串数组 strs 中的最长公共前缀。

如果字符串数组为空或长度为0，直接返回空字符串。获取第一个字符串的长度和字符串数组的长度。遍历第一个字符串的每个字符。获取当前字符

c，用来与其他字符串的对应位置字符进行比较。遍历剩余的字符串，依次比较当前字符和其他字符串对应位置的字符。

如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，返回前缀部分，即第一个字符串的从索引0到当前位置的子串。

返回第一个字符串作为最长公共前缀，因为该字符串是其他字符串的公共前缀。

C语言版本

在这里插入代码片

Python

在这里插入代码片

复杂度分析

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。

方式三：纵向扫描

思路

代码实现

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或者长度为0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        } else {
            return longestCommonPrefix(strs, 0, strs.length - 1);
        }
    }
    
    // 递归函数，用于求取指定范围内字符串数组的最长公共前缀
    public String longestCommonPrefix(String[] strs, int start, int end) {
        // 如果范围内只有一个字符串，则直接返回该字符串作为最长公共前缀
        if (start == end) {
            return strs[start];
        } else {
            // 计算范围中间索引
            int mid = (end - start) / 2 + start;
            // 求取左半部分和右半部分的最长公共前缀
            String lcpLeft = longestCommonPrefix(strs, start, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, end);
            // 返回左半部分和右半部分的最长公共前缀的公共前缀
            return commonPrefix(lcpLeft, lcpRight);
        }
    }
    
    // 求取两个字符串的最长公共前缀的公共前缀
    public String commonPrefix(String lcpLeft, String lcpRight) {
        // 获取最小长度
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        // 对比两个字符串的字符，找到不相等的位置，返回前缀部分
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        // 返回最小长度范围内的字符串，即最长公共前缀
        return lcpLeft.substring(0, minLength);
    }
}

说明：

longestCommonPrefix() 方法是递归函数，用于求取指定范围内字符串数组 strs 的最长公共前缀。

如果范围内只有一个字符串，则直接返回该字符串作为最长公共前缀。否则，计算范围中间索引 mid。调用递归函数

longestCommonPrefix() 分别求取左半部分和右半部分的最长公共前缀：lcpLeft 和 lcpRight。

返回左半部分和右半部分的最长公共前缀的公共前缀，即调用 commonPrefix() 函数。 commonPrefix()

方法用于求取两个字符串 lcpLeft 和 lcpRight 的最长公共前缀的公共前缀。获取两个字符串的长度的最小值作为最小长度minLength。逐个字符比较两个字符串的对应位置的字符，找到不相等的位置，返回当前位置前的子串作为最长公共前缀的公共前缀。

如果没有找到不相等的位置，返回最小长度范围内的字符串，即最长公共前缀。

C语言版本

#include <stdio.h>
#include <string.h>
// 函数声明
char* longestCommonPrefix(char** strs, int strsSize);
/*
 * 获取两个字符串的最长公共前缀
 * 参数: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最长公共前缀的指针
 */
char* commonPrefix(char* str1, char* str2);
/*
 * 获取字符串数组中的最长公共前缀
 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度
 * 返回值: 最长公共前缀的指针
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空或者长度为0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }
    // 将第一个字符串作为初始的最长公共前缀
    char* prefix = strs[0];
    // 遍历剩余的字符串
    for (int i = 1; i < strsSize; i++) {
        // 更新最长公共前缀为当前遍历的字符串与最长公共前缀的公共前缀
        prefix = commonPrefix(prefix, strs[i]);
        // 如果最长公共前缀为空，说明不存在公共前缀，直接跳出循环
        if (strlen(prefix) == 0) {
            break;
        }
    }
    return prefix;
}
/*
 * 获取两个字符串的最长公共前缀的公共前缀
 * 参数: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最长公共前缀的指针
 */
char* commonPrefix(char* str1, char* str2) {
    int length1 = strlen(str1);
    int length2 = strlen(str2);
    int index = 0;
    while (index < length1 && index < length2 && str1[index] == str2[index]) {
        index++;
    }
    // 创建新的字符串，存储公共前缀
    char* result = (char*)malloc((index + 1) * sizeof(char));
    strncpy(result, str1, index);
    result[index] = '\0';  // 末尾添加结束符
    return result;
}

说明：

longestCommonPrefix()函数用于找到字符串数组中的最长公共前缀。

在函数中，首先判断字符串数组是否为空或长度为0。如果是，则直接返回空字符串。将字符串数组的第一个字符串作为初始的最长公共前缀prefix。

使用一个循环遍历剩余的字符串，分别与当前最长公共前缀进行比较，更新最长公共前缀。如果最长公共前缀为空字符串，说明不存在公共前缀，跳出循环。

返回最长公共前缀prefix的指针。 commonPrefix()函数用于找到两个字符串的最长公共前缀的公共前缀。

在函数中，通过计算两个字符串的长度，初始化索引index为0。

使用一个循环比较两个字符串的对应位置字符，直到遇到不相等的字符或其中一个字符串的结尾。

创建一个新的字符数组result，用于存储公共前缀部分。使用strncpy()函数将公共前缀部分复制到result中。

在result末尾添加结束符\0。返回公共前缀result的指针。

请注意，使用malloc()动态分配了内存空间来存储结果字符串，因此在使用完毕后，记得使用free()函数释放它。

Python3版本

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 定义递归函数，用于求取字符串数组中指定范围内的最长公共前缀
        def lcp(start, end):
            # 如果范围中只有一个字符串，则直接返回该字符串作为最长公共前缀
            if start == end:
                return strs[start]
            # 分治法，将范围划分为两部分，分别求取左右两部分的最长公共前缀
            mid = (start + end) // 2
            lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
            # 找到左右两部分最长公共前缀的最小长度
            minLength = min(len(lcpLeft), len(lcpRight))
            # 在最小长度范围内逐个字符比较
            for i in range(minLength):
                if lcpLeft[i] != lcpRight[i]:
                    # 遇到第一个不相等的字符，返回前缀部分
                    return lcpLeft[:i]
            # 返回最小长度范围内的最长公共前缀
            return lcpLeft[:minLength]
        # 如果字符串数组为空，则返回空字符串
        return "" if not strs else lcp(0, len(strs) - 1)

说明：

使用分治法，将指定范围划分为左右两部分，分别求取它们的最长公共前缀。计算中间索引 mid。调用 lcp()

函数求取左半部分的最长公共前缀 lcpLeft。调用 lcp() 函数求取右半部分的最长公共前缀 lcpRight。

找到左右两部分最长公共前缀的最小长度。在最小长度范围内逐个字符比较左右两部分的对应位置字符。

如果遇到第一个不相等的字符，返回当前位置前的子串作为最长公共前缀。返回最小长度范围内的最长公共前缀。如果字符串数组为空，则返回空字符串。

否则，调用 lcp() 函数，传入起始索引0和结束索引 len(strs) - 1，求取整个字符串数组的最长公共前缀。

longestCommonPrefix() 方法是主函数，用于启动递归过程并处理边界情况。lcp() 函数是一个内部递归函数，用于求取字符串数组中指定范围内的最长公共前缀

复杂度分析

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。时间复杂度的递推式是 T(n)=2⋅T(2n )+O(m)，通过计算可得 T(n)=O(mn)。
空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 logn，每层需要 m 的空间存储返回结果。

方式四：二分查找

显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid，判断每个字符串的长度为 mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，如果不相同则最长公共前缀的长度一定小于 mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。

代码实现

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或长度为0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        // 获取字符串数组中最短字符串的长度
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        
        // 使用二分查找的思路来查找最长公共前缀
        int low = 0, high = minLength;
        while (low < high) {
            // 取中间位置
            int mid = (high - low + 1) / 2 + low;
            
            // 判断中间位置的前缀是否是公共前缀
            if (isCommonPrefix(strs, mid)) {
                // 如果是，更新 low，继续查找右半部分
                low = mid;
            } else {
                // 如果不是，更新 high，继续查找左半部分
                high = mid - 1;
            }
        }
        
        // 返回最长公共前缀
        return strs[0].substring(0, low);
    }
    
    // 判断指定长度前缀是否是字符串数组的公共前缀
    public boolean isCommonPrefix(String[] strs, int length) {
        // 获取第一个字符串的指定长度前缀
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        
        // 遍历剩余的字符串，逐个比较前缀字符
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        
        // 返回是否是公共前缀的结果
        return true;
    }
}

说明：

longestCommonPrefix() 方法用于求取字符串数组 strs 中的最长公共前缀。

首先判断字符串数组是否为空或长度为0，如果是，则直接返回空字符串。获取字符串数组中最短字符串的长度 minLength。

使用二分查找的思路来查找最长公共前缀。维持一个区间 [low, high]，初始为 [0, minLength]。

在每一次循环中，取区间的中间位置 mid。判断以mid长度作为前缀是否是字符串数组的公共前缀，通过调用 isCommonPrefix()

方法实现。如果是公共前缀，则更新 low = mid，继续查找右半部分。如果不是公共前缀，则更新 high = mid -

1，继续查找左半部分。当 low >= high 时，二分查找结束，得到最长公共前缀的长度。返回最长公共前缀，使用

strs[0].substring(0, low) 来截取对应长度的前缀。 isCommonPrefix()

方法用于判断指定长度的前缀是否是字符串数组 strs 的公共前缀。获取第一个字符串的指定长度前缀 str0。

遍历剩余的字符串，逐个比较前缀中的字符。如果存在不相等的字符，说明不是公共前缀，返回 false。

如果所有字符串的前缀字符都相等，说明是公共前缀，返回 true。

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 函数声明
char* longestCommonPrefix(char** strs, int strsSize);
int isCommonPrefix(char** strs, int strsSize, int len);
/**
int main() {
    // 测试数据
    char* strs[] = {"flower", "flow", "flight"};
    int strsSize = 3;
    // 调用函数并打印结果
    char* result = longestCommonPrefix(strs, strsSize);
    printf("Longest Common Prefix: %s\n", result);
    return 0;
}
**/
/*
 * 获取字符串数组中的最长公共前缀
 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度
 * 返回值: 最长公共前缀的指针
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空或长度为0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }
    // 找出最短字符串的长度
    int minLength = INT_MAX;
    for (int i = 0; i < strsSize; i++) {
        int len = strlen(strs[i]);
        if (len < minLength) {
            minLength = len;
        }
    }
    // 使用二分法查找最长公共前缀
    int low = 1;
    int high = minLength;
    int mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;
        if (isCommonPrefix(strs, strsSize, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    // 根据最长公共前缀的长度，创建并返回结果字符串
    char* result = (char*)malloc((mid + 1) * sizeof(char));
    strncpy(result, strs[0], mid);
    result[mid] = '\0';
    return result;
}
/*
 * 判断指定长度前缀是否是字符串数组的公共前缀
 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度, len - 前缀长度
 * 返回值: 是否是公共前缀的整数值，1为是，0为否
 */
int isCommonPrefix(char** strs, int strsSize, int len) {
    for (int i = 0; i < len; i++) {
        char ch = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != ch) {
                return 0;
            }
        }
    }
    return 1;
}

说明：

longestCommonPrefix()函数用于找到字符串数组中的最长公共前缀。

在函数中，首先判断字符串数组是否为空或长度为0。如果是，则直接返回空字符串。找出字符串数组中最短字符串的长度minLength。

使用二分法来查找最长公共前缀。初始化low为1，high为最短字符串的长度minLength。循环遍历，直到找到最长公共前缀的长度。

设置mid为low和high的中间值。如果前缀长度为mid的前缀是字符串数组的公共前缀，则在[mid+1, high]范围继续查找。

如果前缀长度为mid的前缀不是字符串数组的公共前缀，则在[low, mid-1]范围继续查找。

根据最长公共前缀的长度mid，动态分配内存创建结果字符串result。

使用strncpy()函数将字符串数组的第一个字符串的前mid个字符复制到结果字符串中。在结果字符串的末尾添加结束符’\0’。

返回结果字符串的指针。请注意，在使用完结果字符串后，不要忘记使用free()函数释放分配的内存。

Python3版本

def longestCommonPrefix(strs):
    # 如果字符串数组为空或长度为0，直接返回空字符串
    if not strs:
        return ""
    # 找出最短字符串的长度
    minLength = min(len(s) for s in strs)
    # 使用二分法查找最长公共前缀
    low = 1
    high = minLength
    while low <= high:
        mid = (low + high) // 2
        if isCommonPrefix(strs, mid):
            low = mid + 1
        else:
            high = mid - 1
    # 根据最长公共前缀的长度，返回结果字符串
    return strs[0][:low]
def isCommonPrefix(strs, length):
    for i in range(length):
        ch = strs[0][i]
        for j in range(1, len(strs)):
            if strs[j][i] != ch:
                return False
    return True
# 调用函数并打印结果
#strs = ["flower", "flow", "flight"]
#result = longestCommonPrefix(strs)
#print("Longest Common Prefix:", result)

说明：

longestCommonPrefix() 函数用于找到字符串数组中的最长公共前缀。

首先判断字符串数组是否为空。如果为空，则直接返回空字符串。找出字符串数组中最短字符串的长度 minLength，使用 min()函数和生成器表达式来实现。使用二分法来查找最长公共前缀。初始化 low 为 1，high 为最短字符串的长度 minLength。

循环遍历，直到找到最长公共前缀的长度。设置 mid 为 low 和 high 的中间值。如果前缀长度为 mid

的前缀是字符串数组的公共前缀，则在 [mid+1, high] 范围继续查找。如果前缀长度为 mid 的前缀不是字符串数组的公共前缀，则在[low, mid-1] 范围继续查找。根据最长公共前缀的长度 low，返回结果字符串，使用切片操作实现。

isCommonPrefix() 函数用于判断指定长度的前缀是否是字符串数组的公共前缀。

使用嵌套循环遍历前缀的每个字符，逐个比较所有字符串的对应位置字符。如果存在不相等的字符，说明不是公共前缀，返回 False。

如果所有字符串的前缀字符都相等，说明是公共前缀，返回 True。调用函数并打印结果，使用示例字符串数组。

复杂度分析

时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是 O(logm)，每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。
空间复杂度：O(1)。使用的额外空间复杂度为常数。

克隆图（LeetCode 133,Medium）

标签：图的遍历、深拷贝

题目

在这里插入代码片

思路及实现

方式一：暴力解法（不推荐）

思路

代码实现

Java

在这里插入代码片

C

在这里插入代码片

Python

在这里插入代码片

复杂度分析

时间复杂度
空间复杂度

方式二：暴力解法（不推荐）

思路

代码实现

Java

在这里插入代码片

C

在这里插入代码片

Python

在这里插入代码片

复杂度分析

时间复杂度
空间复杂度

合并排序的数组（LeetCode 88,Easy）

标签：归并排序、数组操作

题目

在这里插入代码片

思路及实现

方式一：暴力解法（不推荐）

思路

代码实现

Java

在这里插入代码片

C

在这里插入代码片

Python

在这里插入代码片

复杂度分析

时间复杂度
空间复杂度

方式二：暴力解法（不推荐）

思路

代码实现

Java

在这里插入代码片

C

在这里插入代码片

Python

在这里插入代码片

复杂度分析

时间复杂度
空间复杂度

第 K 个数（LeetCode 215,Medium）

标签：快速选择、二分查找

题目

在这里插入代码片

思路及实现

方式一：暴力解法（不推荐）

思路

代码实现

Java

在这里插入代码片

C

在这里插入代码片

Python

在这里插入代码片

复杂度分析

时间复杂度
空间复杂度

方式二：暴力解法（不推荐）

思路

代码实现

Java

在这里插入代码片

C

在这里插入代码片

Python

在这里插入代码片

复杂度分析

时间复杂度
空间复杂度

结语

经典的数据结构与算法题目不仅考察我们的解题思路和编程能力，更重要的是让我们深入理解各种数据结构和算法的原理和应用。通过解题，我们可以不断提高自己的编程能力，锻炼思维的敏捷性。同时，也能够给我们带来一些乐趣和满足感。

希望这些有趣的题目能够给你带来启发和帮助，让你更加热爱并深入学习数据结构与算法。加油，继续挑战，我们一起做个优秀的开发者！