必会的10个经典算法题(附解析答案代码Java/C/Python看这一篇就够)(二)

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 必会的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 的左孩子

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

  1. left 和 right 不等,或者 left 和 right 都为空
  2. 递归的比较 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的实现)

  1. 在函数参数的类型注解中,使用了 TreeNode 类型来标注 root 参数的类型。
  2. 使用了 is 运算符来判断节点是否为 None。is 运算符比较的是对象的身份标识,用于判断对象是否是同一个对象。这里用它来判断节点是否为None。
  3. 使用了列表 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
在这里插入代码片
复杂度分析
  • 时间复杂度
  • 空间复杂度

结语

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

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

相关文章
|
3天前
|
存储 分布式计算 DataWorks
MaxCompute产品使用合集之如何在代码中解析File类型的文件内容
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
28 11
|
4天前
|
存储 Python
离散事件模拟(Discrete Event Simulation)详解与Python代码示例
离散事件模拟(Discrete Event Simulation)详解与Python代码示例
|
4天前
|
供应链 Python
供需匹配(Demand-Supply Matching)的详细解释与Python代码示例
供需匹配(Demand-Supply Matching)的详细解释与Python代码示例
|
4天前
|
供应链 Python
Demand Forecasting模型解释与Python代码示例
Demand Forecasting模型解释与Python代码示例
|
4天前
|
存储 Python
数据包络分析(Data Envelopment Analysis, DEA)详解与Python代码示例
数据包络分析(Data Envelopment Analysis, DEA)详解与Python代码示例
|
1天前
|
存储 Python
深度剖析:Python里字典树Trie的构建与查询,让你的代码更优雅!
【7月更文挑战第20天】Trie树(前缀树)是高效处理字符串搜索的 数据结构**。通过Python实现,每个节点含指向子节点的链接(字典)和结束标识。`TrieNode`和`Trie`类分别表示节点和树,支持插入、搜索和前缀检查。空间效率高,共享公共前缀,时间复杂度O(m)。适用于字符串集合的快速检索和灵活扩展,如自动补全。学习和应用Trie能提升代码效率和质量。
6 0
|
4天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真
|
6天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
13小时前
|
传感器 机器学习/深度学习 算法
基于GA遗传算法的WSN网络节点覆盖优化matlab仿真
本研究应用遗传优化算法于无线传感器网络(WSN),优化节点布局与数量,以最小化节点使用而最大化网络覆盖率。MATLAB2022a环境下,算法通过选择、交叉与变异操作,逐步改进节点配置,最终输出收敛曲线展现覆盖率、节点数及适应度值变化。无线传感器网络覆盖优化问题通过数学建模,结合遗传算法,实现目标区域有效覆盖与网络寿命延长。算法设计中,采用二进制编码表示节点状态,适应度函数考量覆盖率与连通性,通过选择、交叉和变异策略迭代优化,直至满足终止条件。

推荐镜像

更多