---

前言

????算法小白初入leetcode。本文主要記錄個人在leetcode上使用python解題的思路和過程，如果有更好、更巧妙的解題方法，歡迎大家在評論區給出代碼或思路。🚀

---

尋找兩個正序數組的中位數

• 題目描述

• 實際上就是對數組排序的問題

1?? 雙指針快速排序

• 定義兩個指針$i$和$j$，初始時分別指向兩個列表的開頭。然后，比較指針所指的元素，將較小的元素添加到結果列表中，并將對應指針向后移動一位。重復這個過程，直到其中一個列表的所有元素都被添加到結果列表中。最后，將另一個列表中剩余的元素添加到結果列表的末尾。具體代碼和執行過程可以如下所示：

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:num_12 = []i   = 0j   = 0while i<len(nums1) and j <len(nums2):if    nums1[i] < nums2[j]:num_12.append(nums1[i]) i += 1elif  nums1[i] > nums2[j]:num_12.append(nums2[j])j += 1else:   # 如果兩個指針指向的數值相同，重復添加該元素，同時移動兩個指針num_12 += [nums1[i],nums2[j]]i += 1j += 1# 若其中一個數組遍歷完成了，則將另外一個數組中的剩余元素添加到num_12中 while i<len(nums1):num_12.append(nums1[i])i += 1while j<len(nums2):num_12.append(nums2[j])j += 1if len(num_12)%2 == 0:return (num_12[len(num_12)//2] + num_12[len(num_12)//2 - 1]) / 2else :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) / 2def 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 sline1       = ''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_linereturn 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 = [''] * numRowsn = len(s)for i in range(n):res[temp[i%len(temp)]] += s[i]return ''.join(res)

思路清晰，代碼簡潔，確實很巧妙！

3??巧妙解法2

• 使用變量 $i$ 表示當前字符的行索引，初始值為 $0$；使用變量 $flag$ 表示行索引的變化方向，初始值為 $?1$。然后遍歷原字符串中的每個字符$c$：將當前字符 $c$ 添加到 $res[i]$ 對應的行中。如果當前行索引 i 到達首行或末行，則改變 $flag$ 的方向。最后根據 $flag$ 的方向更新行索引 $i$，這樣一來就實現了“Z”字形的邏輯。

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

字符串轉換整數 (atoi)

• 題目描述：

1?? 常規方法

• 按照題目，思路如下：
  • 第一步去掉字符串前面的所有空格；
  • 分類討論，只保留符合條件的字符：
    • 首字符是-或者+的情況：從第二個字符遍歷到最后一個字符，滿足條件的字符留下。對于是否保留$0$這個字符，可以通過最終拼接的字符串re的長度來判斷，如果等于$0$說明是前置零，直接舍棄，其余情況則保留。對于非數字字符的判斷，可以通過$Ascall$碼來進行判斷。
    • 其他情況：同上處理，只不過從開頭遍歷到結尾。
  • 將最后拼接的字符串轉換成整數并輸出。

class Solution:def myAtoi(self, s: str) -> int:s = s.strip()re  = ''if s == '':return 0elif s[0] == '-' or s[0] == '+':i = 1while i <= len(s)-1:if ord(s[i]) < 48 or ord(s[i]) > 57:breakif len(re) == 0  and s[i] == 0:continueelse:re += s[i]i += 1if len(re) == 0:return 0elif s[0] == '-':return max(-int(re),-2**31)else:return min(int(re),2**31-1)else:i = 0while i <= len(s)-1:if ord(s[i]) < 48 or ord(s[i]) > 57:breakif len(re) == 0  and s[i] == 0:continueelse:re += s[i]i += 1if len(re) == 0:return 0else: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 0elif s[0] == '-' or s[0] == '+':i = 1while i <= len(s)-1:if ord(s[i]) < 48 or ord(s[i]) > 57:breakif len(re) == 0  and s[i] == 0:continueelse:re += s[i]i += 1if len(re) == 0:return 0elif s[0] == '-':return max(-int(re),-2**31)else:return min(int(re),2**31-1)else:i = 0while i <= len(s)-1:if ord(s[i]) < 48 or ord(s[i]) > 57:breakif len(re) == 0  and s[i] == 0:continueelse:re += s[i]i += 1if len(re) == 0:return 0else: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 -= 1000elif 900 <= num < 1000:re += char_num[900]num -= 900elif 500 <= num < 900:re += char_num[500]num -= 500  elif 400 <= num < 500:re += char_num[400] num -= 400elif 100 <= num < 400:re += char_num[100]num -= 100elif 90 <= num < 100:re += char_num[90]num -= 90elif 50 <= num < 90:re += char_num[50]num -= 50elif 40 <= num < 50:re += char_num[40]num -= 40elif 10 <= num < 40:re += char_num[10]num -= 10elif 9 <= num < 10:re += char_num[9]num -= 9elif 5 <= num < 9:re += char_num[5]num -= 5elif 4 <= num < 5:re += char_num[4]num -= 4elif 1 <= num < 4:re += char_num[1]num -= 1return 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 = 0for 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 = 0while 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   

總結

算法小白初入leetcode，期待給出更精妙的算法🚀🚀🚀