Leetcode刷题2

文章目录

前言
寻找两个正序数组的中位数
- 1️⃣ 双指针快速排序
- 2️⃣ 第k小数解法
Z 字形变换
- 1️⃣ 个人解法
- 2️⃣巧妙解法1
- 3️⃣巧妙解法2
字符串转换整数 (atoi)
- 1️⃣ 常规方法
- 2️⃣ 作弊方法😫
整数转罗马数字
- 1️⃣ 常规方法：按照给定规则写出判断条件即可
- 2️⃣ 循环实现
罗马数字转整数
- 1️⃣ 常规处理
- 2️⃣ 改进
总结

前言

算法小白初入leetcode。本文主要记录个人在leetcode上使用python解题的思路和过程，如果有更好、更巧妙的解题方法，欢迎大家在评论区给出代码或思路。🚀
在这里插入图片描述

寻找两个正序数组的中位数

题目描述

实际上就是对数组排序的问题

1️⃣ 双指针快速排序

定义两个指针 $i$ 和 $j$ ，初始时分别指向两个列表的开头。然后，比较指针所指的元素，将较小的元素添加到结果列表中，并将对应指针向后移动一位。重复这个过程，直到其中一个列表的所有元素都被添加到结果列表中。最后，将另一个列表中剩余的元素添加到结果列表的末尾。具体代码和执行过程可以如下所示：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        num_12 = []
        i   = 0
        j   = 0

        while i<len(nums1) and j <len(nums2):
            if    nums1[i] < nums2[j]:
                num_12.append(nums1[i]) 
                i += 1
            elif  nums1[i] > nums2[j]:
                num_12.append(nums2[j])
                j += 1
            else:   # 如果两个指针指向的数值相同，重复添加该元素，同时移动两个指针
                num_12 += [nums1[i],nums2[j]]
                i += 1
                j += 1
        
        # 若其中一个数组遍历完成了，则将另外一个数组中的剩余元素添加到num_12中 
        while i<len(nums1):
            num_12.append(nums1[i])
            i += 1
        
        while j<len(nums2):
            num_12.append(nums2[j])
            j += 1
        if len(num_12)%2 == 0:
            return (num_12[len(num_12)//2] + num_12[len(num_12)//2 - 1]) / 2
        else :
            return num_12[len(num_12)//2]

2️⃣ 第k小数解法

这个解法是众多题解中非常巧妙的一个，具体原理和算法可以直接看这里：第k小数解法视频详解
算法实现：知道原理后，其实本质就是在不断排除比中位数还要小的那些数，直到找到中位数，所以可以利用递归的方式去实现它。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total_length = len(nums1) + len(nums2)
        
        if total_length % 2 == 1:
            # 如果总长度为奇数，则中位数为第 (total_length // 2 + 1) 小的元素
            return self.findKthElement(nums1, nums2, total_length // 2 + 1)
        else:
            # 如果总长度为偶数，则中位数为第 total_length // 2 和第 total_length // 2 + 1 小的元素的平均值
            left = self.findKthElement(nums1, nums2, total_length // 2)
            right = self.findKthElement(nums1, nums2, total_length // 2 + 1)
            return (left + right) / 2
            
    def findKthElement(self,nums1, nums2, k):
        """
        nums1: 第一个有序数组
        nums2: 第二个有序数组
        k    : 要查找的第 k 小的元素（1-indexed）
        返回值: 第 k 小的元素
        """
        len1, len2 = len(nums1), len(nums2)
        
        # 确保 nums1 是较短的数组
        if len1 > len2:
            return self.findKthElement(nums2, nums1, k)
        
        # 如果较短数组为空，则直接返回 nums2 中的第 k 个元素
        if len1 == 0:
            return nums2[k-1]
        
        # 如果 k == 1，则返回两个数组中第一个元素的最小值
        if k == 1:
            return min(nums1[0], nums2[0])
        
        # 选择 nums1 和 nums2 中的 k//2 个元素，比较这两个元素
        i = min(len1, k // 2)
        j = min(len2, k // 2)
        
        if nums1[i-1] > nums2[j-1]:
            # 如果 nums1 中第 i 个元素较大，则说明 nums2 中的前 j 个元素不可能是第 k 小的元素
            return self.findKthElement(nums1, nums2[j:], k - j)
        else:
            # 如果 nums2 中第 j 个元素较大，则说明 nums1 中的前 i 个元素不可能是第 k 小的元素
            return self.findKthElement(nums1[i:], nums2, k - i)

确实是又快了一些，可惜才击败三十多，想知道更快的解法💡

Z 字形变换

题目描述

1️⃣ 个人解法

可以发现每一行的字符都与第一行的字符存在关联的，所以只要先确定第一行的元素，后面几行的元素就能确定了。如题目描述中的示例2，第二行字符ALSIG可以认为是第一行字符PIN中每个元素在 $s$ 中的索引位置向左和右各移动 $1$ 次得到（超出索引位置就舍弃掉），第二行字符YAHR可以认为是第一行字符PIN中每个元素在 $s$ 中的索引位置向左和右各移动 $2$ 次得到（超出索引位置就舍弃掉），依次类推…
但是要注意两点：1）：最后一行的字符按照这样的处理会导致出现重复，所以需要单独处理；2）：如果是下面这种情况，按照这样的处理就会导致末尾RI这两个字符遗漏，所以由第一行字符中最后一个字符确定其他行字符时，需要单独处理。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        '''
        思路：先确定第一行和最后一行的元素，后面几行的元素顺序与第一行有关
        '''
        if numRows == 1:
            return s
        line1       = ''
        line1_index = []
        length      = len(s)
        for i in range(0,length,2*(numRows-1)):
            line1 += s[i]
            line1_index.append(i)

        for i in range(numRows-1):
            next_line = ''
            index = []
            for j in line1_index:
                if i == numRows-2:    #最后一行作特殊处理
                    if j+numRows-1 < length:
                        next_line += s[j+numRows-1]
                else:
                    if j-i-1 > 0:
                        next_line += s[j-i-1]
                    if j+i+1 < length:
                        next_line += s[j+i+1]
                    if j == line1_index[-1] and j+2*numRows-3-i < length:
                        next_line += s[j+2*numRows-3-i]
            line1 += next_line
        return line1

不过时间效率并不高，有待优化🤦‍♂️

2️⃣巧妙解法1

参考leetcode-wuji3


class Solution:
    def convert(self, s: str, numRows: int) -> str:
        temp = [i for i in range(numRows)]
        temp += temp[1:-1][::-1]

        res = [''] * numRows
        n = len(s)

        for i in range(n):
            res[temp[i%len(temp)]] += s[i]

        return ''.join(res)

思路清晰，代码简洁，确实很巧妙！

3️⃣巧妙解法2

使用变量 $i$ 表示当前字符的行索引，初始值为 $0$ ；使用变量 $f l a g$ 表示行索引的变化方向，初始值为 $- 1$ 。然后遍历原字符串中的每个字符 $c$ ：将当前字符 $c$ 添加到 $res [i]$ 对应的行中。如果当前行索引 i 到达首行或末行，则改变 $f l a g$ 的方向。最后根据 $f l a g$ 的方向更新行索引 $i$ ，这样一来就实现了“Z”字形的逻辑。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2:
            return s
        res = ['' for i in range(numRows)]
        i , flag = 0,-1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1:
                flag = -flag
            i = i + flag
        return ''.join(res)

字符串转换整数 (atoi)

题目描述：

1️⃣ 常规方法

按照题目，思路如下：
- 第一步去掉字符串前面的所有空格；
- 分类讨论，只保留符合条件的字符：
  - 首字符是-或者+的情况：从第二个字符遍历到最后一个字符，满足条件的字符留下。对于是否保留 $0$ 这个字符，可以通过最终拼接的字符串re的长度来判断，如果等于 $0$ 说明是前置零，直接舍弃，其余情况则保留。对于非数字字符的判断，可以通过 $A sc a ll$ 码来进行判断。
  - 其他情况：同上处理，只不过从开头遍历到结尾。
- 将最后拼接的字符串转换成整数并输出。

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

        s = s.strip()
        re  = ''

        if s == '':
            return 0
        elif s[0] == '-' or s[0] == '+':
            i = 1
            while i <= len(s)-1:
                if ord(s[i]) < 48 or ord(s[i]) > 57:
                    break
                if len(re) == 0  and s[i] == 0:
                    continue
                else:
                    re += s[i]
                i += 1
            if len(re) == 0:
                return 0
            elif s[0] == '-':
                return max(-int(re),-2**31)
            else:
                return min(int(re),2**31-1)
        else:
            i = 0
            while i <= len(s)-1:
                if ord(s[i]) < 48 or ord(s[i]) > 57:
                    break
                if len(re) == 0  and s[i] == 0:
                    continue
                else:
                    re += s[i]
                i += 1
            
            if len(re) == 0:
                return 0
            else:
                return min(int(re) , 2**31-1)

2️⃣ 作弊方法😫

其实Python中的内置函数int可以直接实现这个题目的大部分情况，我们直接拿来使用，然后对于使用不了的情况就用try ... except进行捕捉，然后再使用上面的常规方法。

class Solution:
    def myAtoi(self, s: str) -> int:
        try:
            return max(int(s),-2**31) if '-' in s else min(int(s),2**31-1) 
        except Exception as e:
            s = s.strip()
            re  = ''

            if s == '':
                return 0
            elif s[0] == '-' or s[0] == '+':
                i = 1
                while i <= len(s)-1:
                    if ord(s[i]) < 48 or ord(s[i]) > 57:
                        break
                    if len(re) == 0  and s[i] == 0:
                        continue
                    else:
                        re += s[i]
                    i += 1
                if len(re) == 0:
                    return 0
                elif s[0] == '-':
                    return max(-int(re),-2**31)
                else:
                    return min(int(re),2**31-1)
            else:
                i = 0
                while i <= len(s)-1:
                    if ord(s[i]) < 48 or ord(s[i]) > 57:
                        break
                    if len(re) == 0  and s[i] == 0:
                        continue
                    else:
                        re += s[i]
                    i += 1
                
                if len(re) == 0:
                    return 0
                else:
                    return min(int(re) , 2**31-1)

确实提速了一些hhh

整数转罗马数字

题目描述

1️⃣ 常规方法：按照给定规则写出判断条件即可

class Solution:
    def intToRoman(self, num: int) -> str:
        char_num = {1:'I',5:'V',10:'X',50:'L',100:'C',500:'D',1000:'M',4:'IV',9:'IX',40:'XL',90:'XC',400:'CD',900:'CM'}
        re = ''
        while num > 0:
            if 1000 <= num:
                re += char_num[1000]
                num -= 1000
            elif 900 <= num < 1000:
                re += char_num[900]
                num -= 900
            elif 500 <= num < 900:
                re += char_num[500]
                num -= 500  
            elif 400 <= num < 500:
                re += char_num[400] 
                num -= 400
            elif 100 <= num < 400:
                re += char_num[100]
                num -= 100
            elif 90 <= num < 100:
                re += char_num[90]
                num -= 90
            elif 50 <= num < 90:
                re += char_num[50]
                num -= 50
            elif 40 <= num < 50:
                re += char_num[40]
                num -= 40
            elif 10 <= num < 40:
                re += char_num[10]
                num -= 10
            elif 9 <= num < 10:
                re += char_num[9]
                num -= 9
            elif 5 <= num < 9:
                re += char_num[5]
                num -= 5
            elif 4 <= num < 5:
                re += char_num[4]
                num -= 4
            elif 1 <= num < 4:
                re += char_num[1]
                num -= 1

        return re

2️⃣ 循环实现

将上面判断改成循环的方式实现

class Solution:
    def intToRoman(self, num: int) -> str:
        char_num = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
        re = ''
        for i in char_num.keys():
            if num // i != 0:
                re += char_num[i] * (num//i)
                num = num % i 
        return re

不过速度变慢了一些

罗马数字转整数

题目描述（上面一题的相反处理）

1️⃣ 常规处理

先将字符串中特殊的 $6$ 种罗马数字挑选出来转换成整数，然后再将剩下的罗马单个字符一一转换成数字即可。

class Solution:
    def romanToInt(self, s: str) -> int:
        dict1 = {'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000}
        dict2 = {'IV': 4,'IX': 9,'XL': 40,'XC': 90,'CD': 400,'CM': 900}
        result = 0
        for i in dict2.keys():
            if i in s:
                result += dict2[i]
                s       = s.replace(i,'')
        for i in s:
            result += dict1[i]
        return result

2️⃣ 改进

上面算法需要遍历两次字符串，时间复杂度为 $\mathcal{O(2n)}$ ，其实只需要遍历一次就行，时间复杂度变成 $\mathcal{O(n)}$ 。

class Solution:
    def romanToInt(self, s: str) -> int:
        dict1 = {'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000}
        dict2 = {'IV': 4,'IX': 9,'XL': 40,'XC': 90,'CD': 400,'CM': 900}
        result = 0

        while len(s) >= 1:
            if len(s) == 1:
                result += dict1[s[0]]
                s = ''
            elif dict1[s[0]] < dict1[s[1]]:
                result += dict2[s[0:2]]
                s = s[2:]
            else:
                result += dict1[s[0]]
                s = s[1:]
        return result