力扣題庫 - 簡單題 - 僅記錄學習

來源地址：?力扣 (LeetCode) 全球極客摯愛的技術成長平臺

1. 兩數之和

給定一個整數數組 nums?和一個整數目標值 target，請你在該數組中找出 和為目標值 target? 的那?兩個?整數，并返回它們的數組下標。

你可以假設每種輸入只會對應一個答案，并且你不能使用兩次相同的元素。

你可以按任意順序返回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9

輸出：[0,1]

解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 題解 1# for num in range(len(nums)):#     other = target - nums[num]#     if other in nums[num+1:]:#         return [num,nums[num+1:].index(other)+1+num]# 題解 2dict_val = {}for index,val in enumerate(nums):if target - val in dict_val:return [index,dict_val[target - val]]dict_val[val]=index

14. 最長公共前綴

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴，返回空字符串?""。

示例 1：

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

輸出："fl"

示例 2：

輸入：strs = ["dog","racecar","car"]

輸出：""

解釋：輸入不存在公共前綴。

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:data = ""for i in list(zip(*strs)):if len(set(i))  == 1:data +=i[0]else:breakreturn data

提示： zip(*strs)

strs = ['flower','floo','wwsds']

print(list(zip(*strs)))

# [('f', 'f', 'w'), ('l', 'l', 'w'), ('o', 'o', 's'), ('w', 'o', 'd')]

給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

示例 1：

輸入：s = "()"

輸出：true

示例 2：

輸入：s = "()[]{}"

輸出：true

class Solution:def isValid(self, s: str) -> bool:elist = ['?']dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}for val  in list(s):if val in dic:elist.append(val)else:if dic[elist.pop()] !=val:return Falsereturn len(elist) == 1

class Solution:def removeElement(self, nums: List[int], val: int) -> int:for num in range(nums.count(val)):nums.remove(val)return len(nums)

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 二分查找方法if target not in nums:l,r=0,len(nums)-1while l<=r:mid = (l+r)//2if nums[mid]<target:l=mid+1else:r=mid-1return lreturn nums.index(target)

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""# 方法1： 直接合并后排序# nums1[m:]=nums2# nums1.sort()# 方法二： 我們為兩個數組分別設置一個指針 p1? 與 p2? 來作為隊列的頭部指針elist=[]p1,p2=0,0while p1<m or p2<n:if p1==m:elist.append(nums2[p2])p2+=1elif p2==n:elist.append(nums1[p1])p1+=1elif nums1[p1]<nums2[p2]:elist.append(nums1[p1])p1+=1else:elist.append(nums2[p2])p2+=1nums1[:]=elist

121. 買賣股票的最佳時機

給定一個數組 prices ，它的第?i 個元素?prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

示例 1：

輸入：[7,1,5,3,6,4]

輸出：5

解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。 注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

class Solution:def maxProfit(self, prices: List[int]) -> int:cost,profit= float('inf'),0for p in prices:cost=min(cost,p)profit = max(profit,p-cost)return profit

205. 同構字符串

給定兩個字符串?s?和?t?，判斷它們是否是同構的。

如果?s?中的字符可以按某種映射關系替換得到?t?，那么這兩個字符串是同構的。

每個出現的字符都應當映射到另一個字符，同時不改變字符的順序。不同字符不能映射到同一個字符上，相同字符只能映射到同一個字符上，字符可以映射到自己本身。

示例 1:

輸入：s = "egg", t = "add"

輸出：true

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:# 方法1-索引標記for i in range(len(s)):if s.index(s[i]) != t.index(t[i]):return Falsereturn True

219. 存在重復元素 II

給你一個整數數組?nums 和一個整數?k ，判斷數組中是否存在兩個 不同的索引?i?和?j ，滿足 nums[i] == nums[j] 且 abs(i - j) 。如果存在，返回 true ；否則，返回 false 。

示例?1：

輸入：nums = [1,2,3,1], k = 3? 輸出：true

示例 2：

輸入：nums = [1,0,1,1], k = 1? 輸出：true

示例 3：

輸入：nums = [1,2,3,1,2,3], k = 2? 輸出：false

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:pos = {}# 方法一：哈希表for i, num in enumerate(nums):if num in pos and i - pos[num] <= k:return Truepos[num] = ireturn False

給定一個 ?無重復元素 的?有序 整數數組 nums 。

區間 [a,b] 是從 a 到 b（包含）的所有整數的集合。

返回 恰好覆蓋數組中所有數字 的 最小有序 區間范圍列表?。也就是說，nums 的每個元素都恰好被

某個區間范圍所覆蓋，并且不存在屬于某個區間但不屬于 nums 的數字 x 。

列表中的每個區間范圍 [a,b] 應該按如下格式輸出：

示例 1：

輸入：nums = [0,1,2,4,5,7]

輸出：["0->2","4->5","7"]

解釋：區間范圍是：[0,2] --> "0->2"[4,5] --> "4->5"[7,7] --> "7"

class Solution:def summaryRanges(self, nums: List[int]) -> List[str]:def fe(i:int,j:int):return str(nums[i]) if i==j else f'{nums[i]}->{nums[j]}'res = []i=0while i<len(nums):f=iwhile f+1<len(nums) and nums[f+1]== nums[f]+1:f+=1res.append(fe(i,f))i=f+1return res

class Solution:def addDigits(self, num: int) -> int:# 最直觀的方法是模擬各位相加的過程，直到剩下的數字是一位數。while num >= 10:sum = 0while num:sum += num % 10num //= 10num = sumreturn num

class Solution:def wordPattern(self, pattern: str, s: str) -> bool:# 判斷字符與字符串之間是否恰好一一對應。即任意一個字符都對應著唯一的字符串，任意一個字符串也只被唯一的一個字符對應。在集合論中，這種關系被稱為「雙射」。word_list=s.split()if len(word_list)!=len(pattern):return Falsemp1,mp2={},{}for a,b in zip(pattern,word_list):if a in mp1 and mp1[a]!=b or b in mp2 and mp2[b]!=a:return Falsemp1[a]=bmp2[b]=areturn True

from collections import Counter
class Solution:def canConstruct(self, ransomNote: str, magazine: str) -> bool:# 方法1  Counter 用法  cnt = Counter("aab")  # Counter({'a': 2, 'b': 1})# cnt = Counter(magazine) # # Counter({'d': 3, 'b': 2, 'c': 2, 'a': 1})# for c in ransomNote:#     cnt[c]-=1#     if cnt[c]<0:#         return False# return True# 方法2： 字符遍歷m,n=list(magazine),list(ransomNote)for i in range(len(m)):if m[i] in n:n.remove(m[i])if len(n)==0:return Trueelse:return False

class Solution:def isSubsequence(self, s: str, t: str) -> bool:# 方法一：雙指針n, m = len(s), len(t)i = j = 0while i < n and j < m:if s[i] == t[j]:i += 1j += 1return i == n