Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)

这篇具有很好参考价值的文章主要介绍了Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)例子:Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)

分析题目:

主要目的:求出各个字符串的公共前缀

思路(本人解法):

用所给实例来看,不难看出我们可以直接以竖着对应来查看是否是公共前缀 , 

这样就有了一定的思路 , 然后接着想如何让他找到最长的公共前缀后就 停止下来呢 

这样就能想到,从最短的字符串下手(因为公共前缀最长就只能是最短的字符串或者是最长字符串的前几个)

这样就有了大概的轮廓:

  1. 找到最短字符串(记录其长度)
  2. 通过比较的方法依次竖向比较,然后遍历(每个字符串和每个对应的前缀),找到公共前缀的最后(也就是不同/len的时候就能退出了)竖向比较:Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)

 

Cyy:

char * longestCommonPrefix(char ** strs, int strsSize){
    int i = 0;
    int j = 0;
//找到最短的字符串以及记录其最短的长度
    int len = strlen(strs[0]);
    for(int i = 1 ; i < strsSize ; i++)
    {
        if(strlen(strs[i]) < len)
        {
            len = strlen(strs[i]);
        }
    }
//竖向比较
//从下标为0处开始,到最短字符串的最后一个字符(len-1)
    for(i = 0; i < len ;i++)
    {
        for(j = 1; j < strsSize;j++)//比较每个字符串的下标i处的字符是否相等(此时进行竖向比较)
        {
            if(strs[j][i] != strs[j-1][i])//当有不同的时候就退出
                break;
        }
        if(j != strsSize)//到此处有两种可能,一是有不同中途退出的,二是全部相同后自然退出的
            break;//当不是自然退出的时候 j != strSize 、 此时就表示已经找到公共前缀的最后一个那就退出循环
    }
    strs[0][i] = '\0';//直接把下标i处换成\0,这里利用了字符串以\0结尾的特性
    return strs[0];
}

通过查看官方给的答案后进一步优化:

此时我们还能不再判断最短的字符串

而是直接在内部来查看,当竖向查找到了其中一个字符串的最后一个元素时就退出循环

char * longestCommonPrefix(char ** strs, int strsSize){
    int i = 0;
    int j = 0;
    int len = strlen(strs[0]);
    for(i = 0; i < len ;i++)
    {
        for(j = 1; j < strsSize;j++)
        {
            if(strs[j][i] != strs[j-1][i] || strlen(strs[j]) == i)//此处进行了优化
                break;
        }
        if(j != strsSize)
            break;
    }
    strs[0][i] = '\0';
    return strs[0];
}

C++:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int number = strs.size();
        int len = strs[0].size();
        for(int i = 0; i < len;i++)
        {int j;
            for(j = 1 ; j < number;j++)
            {
               if(strs[j][i] != strs[0][i] || strs[j].size() == i)
                    break;
            }
            if(j != number)
                return strs[0].substr(0,i);
        }
        return strs[0];
    }
};

总结学到什么:文章来源地址https://www.toymoban.com/news/detail-508577.html

  • 模拟法(模拟题目所给步骤来解决问题)
  • 用些地方可以进行优化
    • 优化后不用再查找最小字符串(因为后面有需要遍历的字符串所以可以再后面再进行 与i的进行判断看是否到某些字符串的结尾了)
  • 字符串以\0结尾可以把一个字符串的某个位置改成\0这样就修改了结尾

到了这里,关于Day.1 LeetCode刷题练习(最长公共前缀 C/C++两种解法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++面试宝典第19题:最长公共前缀

    题目         编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀,返回空字符串\\\"\\\"。说明:所有输入只包含小写字母a-z。         示例1:         示例2: 解析         最长公共前缀(Longest Common Prefix)是计算机科学中一个常见的问题,它

    2024年01月19日
    浏览(35)
  • 【python】求最长连续公共子序列长度的几种解法

      给定两个序列X和Y,返回最长连续的公共子序列长度。如果没有连续公共子序列,返回0. X和Y的元素都是整数。 示例: 输入: 1 5 7 3 4 5 7 3 4 4 5 7 -2 输出: 3  说明: 最长的连续公共子序列是[7,3,4] (X[2:4] 和Y[0:2]) 这道题在【leetcode1143】的基础上增加了公共子序列连续的限制。

    2024年02月10日
    浏览(47)
  • 探秘力扣之谜:如何轻松解决最长公共前缀问题?

    本篇博客我会讲解力扣中的“14. 最长公共前缀”这道题,这是题目链接。 先来审题: 以下是几个输出示例: 提示: 这道题的思路其实并不难,也是一些字符串的常规操作的结合。大家可以先思考一下,再来听我讲解。 思路是这样的:外层循环遍历第一个字符串的每一个字

    2024年02月03日
    浏览(55)
  • Leetcode1143. 最长公共子序列

    解题思路 求两个数组或者字符串的最长公共子序列问题,肯定是要用动态规划的。下面的题解并不难,你肯定能看懂。 首先,区分两个概念:子序列可以是不连续的;子数组(子字符串)需要是连续的; 另外,动态规划也是有套路的:单个数组或者字符串要用动态规划时,

    2024年01月25日
    浏览(45)
  • 【算法刷题day22】Leetcode:235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 50.删除二叉搜索树中的节点

    文档链接:[代码随想录] 题目链接:235. 二叉搜索树的最近公共祖先 题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深

    2024年04月13日
    浏览(40)
  • leetcode1143. 最长公共子序列-动态规划(java)

    leetcode1143. 最长公共子序列 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-common-subsequence 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串: 它是由原字

    2024年01月19日
    浏览(44)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • 刷题笔记之七(统计每个月兔子的总数+汽水瓶+查找两个字符串a,b中的最长公共子串+公共子串计算)

    目录 1. 数据库中,count不会返回null值,max和concat可能会返回null值 2. 数据库特点: 共享性高,冗余度小,安全性强,独立性强 3.  top是sql server中的,用于求前n条数据 4. 数据库使用函数进行全部扫描(数据遍历)最慢,并且函数执行本身也是需要耗时的 5.  使用%作为

    2023年04月09日
    浏览(44)
  • 【LeetCode】1143.最长公共子序列(闫氏dp可视化无分析)

      推荐一下这道题的可视化过程 最长公共子序列 - 动态规划 Lngest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili  

    2024年02月15日
    浏览(46)
  • 两种解法解决 LeetCode 27. 移除元素【C++】

    1. 暴力解法 😄 创作不易,你的点赞和关注都是对我莫大的鼓励,再次感谢您的观看😄

    2024年02月09日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包