[数据结构与算法]代码小白刷leetcode的总结回顾（2）

一、时间和题目名称

今天是2021年8月20日，是我刷LeetCode的第二天，由于刚刚开始学习python，很多基础知识掌握不清楚，刷题很慢，目前保持一天两题的速度刷入门题，坚持下去，加油！！！

今天刷的题目是：“罗马数字转整数”和“最长的公共前缀”。

二、题目分析

这两个题目没有太多的内在联系，两个题目分别考察了字典的索引操作和字符串的相关操作，这两个题考验一些基础的知识。

今天这第一个题目有一点自己的想法，在程序结构上与解答相类似；第二个题目开始就理解错了，困惑了好久，最后分析了别人的答案，理解了两种解题思路。

三、题目实操

罗马数字翻转的题目要求：

罗马数字包含以下七种字符:?I，?V，?X，?L，C，D?和?M。

字符 ? ? ? ? ?数值
I ? ? ? ? ? ? 1
V ? ? ? ? ? ? 5
X ? ? ? ? ? ? 10
L ? ? ? ? ? ? 50
C ? ? ? ? ? ? 100
D ? ? ? ? ? ? 500
M ? ? ? ? ? ? 1000
例如， 罗马数字 2 写做?II?，即为两个并列的 1。12 写做?XII?，即为?X?+?II?。 27 写做??XXVII, 即为?XX?+?V?+?II?。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做?IIII，而是?IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为?IX。这个特殊的规则只适用于以下六种情况：

I?可以放在?V?(5) 和?X?(10) 的左边，来表示 4 和 9。
X?可以放在?L?(50) 和?C?(100) 的左边，来表示 40 和?90。?
C?可以放在?D?(500) 和?M?(1000) 的左边，来表示?400 和?900。
给定一个罗马数字，将其转换成整数。输入确保在 1?到 3999 的范围内。

处理思路：1.根据题目要求分析，题目中的罗马数字和阿拉伯数字属于一一对应的关系，这正好符? ? ? ? ? ? ? ? ? ? ? ?合字典数据的要求，因而首先定义了一一对应的字典。

? ? ? ? ? ? ? ? ? ?2.输入的数据类型为字符串，首先取出字符串中的第一个数据便于后期的索引（开始? ? ? ? ? ? ? ? ? ? ? ? ? 没有这样处理，导致在字符串索引时导致超出了范围，在查看别人操作后模仿的）。

? ? ? ? ? ? ? ? ? ?3.由于罗马数字的特殊性质，有时候较小的数字放在前面，有时候较大的数字放在前? ? ? ? ? ? ? ? ? ? ? ? ? 面（罗马数字4和罗马数字6），此题的难点就在这里需要考虑不同的情况。将第一? ? ? ? ? ? ? ? ? ? ? ? ? 个字符数据对应的值与第二个值进行对比，若第一个值较小则在num减去对应的第? ? ? ? ? ? ? ? ? ? ? ? ? 一个值，若第一个值较大则num加上第一个值，以此类推再用第二个值和第三个值? ? ? ? ? ? ? ? ? ? ? ? ? 进行比较然后相加，以此类推。

? ? ? ? ? ? ? ? ? 4.由于最后的返回值，没有加上最后一次的pre值没有加上处理后的num值，因而需? ? ? ? ? ? ? ? ? ? ? ? ? ? 要相加。

代码的关键是在for循环里面以及初始的pre值设置，这两点设置的非常巧妙，值得反复思考研究！！

个人感觉在编程过程中经常会出现两个值遍历比较的时候经常会出现超出索引范围的情况，使用本题之中的操作可以解决这个问题，有很大的参考价值。

class Solution:
    def romanToInt(self, s: str) -> int:

        dic = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}

        num = 0
        pre = dic[s[0]]

        for i in range(1,len(s)):
            #第一个值
            if pre < dic[s[i]]:
                num -= pre
            else:
                num += pre
            
            #第0个值，二者始终差一个
            pre = dic[s[i]]

        return pre + num

最长的公共前缀题目要求：

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串?""。

输入：strs = ["flower","flow","flight"]

输出："fl"

方法一的处理思路：1.首先判断输入的数据类型是否符合要求，不符合要求则返回""。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2.将输入的列表数据进行排序，排序后的字符串数据会按照字母的相应的顺? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?序进行排序。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3.取出第一个字符串和最后一个字符串进行比较，若两者之间存在相同的前? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 缀，则该前缀就是最大的公共前缀。排序之后字母字符串，其中每一个对? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 应位置的字母都是符合相应的排序原则，这时候只要保证第一个字符串和? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 最后一个字符串存在着相同的前缀，则该组就一定存在最大公共前缀。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4.遍历第一个字符串，设置判断条件若当前的字符串索引大于最后一个字符? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?串的长度或者第一个和最后一个字符串对应的值不相等时，跳出for循环，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?否则拼接对应的字符串。

个人感觉这个方法最难理解的是为什么排序之后只考虑第一个字符串和最后一个字符串，我在写文章的时候还是有点懵，需要后续好好理解一下。这个题也解决了我一个困惑很久的问题for循环里面的break，有点尴尬。

#思路一
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        strs.sort()
        start=strs[0]
        end=strs[-1]
        res=""
        for i in range(len(start)):
            if i > len(end) or start[i] != end[i]:
                break
            res += start[i]
        return res

方法二的处理思路：1.首先所有输入字符串的每一个字母进行zip操作，将每个对应的位置的字母? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?组成一个元组，超出最短字符串的长度的字母全部被舍弃。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.遍历生成的元组，对每个元组进行序列操作（删除其中重复的元素并进行排? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 序），若生成的序列中只剩下一个字母则说明该字母是公共前缀进行拼? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 接，否则跳出循环。

个人感觉这个方法很巧妙，充分利用了python的内部函数zip和set操作，这两个函数在进行配对以及删除重复元素中经常使用，学习python基础课的时候不太容易见到这两个操作指令。

每一种语言都有自己的语言特色，我们既要掌握通用方法也要知道每种语言的特色方法，我感觉这样是没毛病的。

#非常巧妙的思路
class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        res = ""
        for tmp in zip(*strs):
            tmp_set = set(tmp)
            if len(tmp_set) == 1:
                res += tmp[0]
            else:
                break
        return res