1、兩數之和
- 簡單
題目：
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，并返回它們的數組下標。你可以假設每種輸入只會對應一個答案，并且你不能使用兩次相同的元素。你可以按任意順序返回答案。
- 示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。- 示例 2： 輸入：nums = [3,2,4], target = 6 輸出：[1,2]
- 示例 3： 輸入：nums = [3,3], target = 6 輸出：[0,1]
- 題解：
class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""self.nums=numsself.target=targetfor i in range(0,len(self.nums)-1):for j in range(i+1,len(self.nums)):if self.nums[i]+self.nums[j]==self.target:return [i,j]2、字母異位詞分組
- 中等
給你一個字符串數組，請你將 字母異位詞 組合在一起。可以按任意順序返回結果列表。
字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。
示例
- 示例 1: 輸入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 輸出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
- 示例 2: 輸入: strs = [“”] 輸出: [[“”]]
- 示例 3: 輸入: strs = [“a”] 輸出: [[“a”]]
- 題解
class Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""if len(strs)==1:return [strs]dict = {}for i in strs:ss=str(sorted(i))if ss not in dict:dict[ss]=[i]else:dict[ss].append(i)return list(dict.values())
3、最長連續序列
- 中等
給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。
請你設計并實現時間復雜度為 O(n) 的算法解決此問題。
- 示例 1： 輸入：nums = [100,4,200,1,3,2] 輸出：4 解釋：最長數字連續序列是 [1, 2, 3, 4]。它的長度為 4。
- 示例 2： 輸入：nums = [0,3,7,2,5,8,4,6,0,1] 輸出：9
- 示例 3： 輸入：nums = [1,0,1,2] 輸出：3
class Solution(object):def longestConsecutive(self, nums):""":type nums: List[int]:rtype: int"""res=set(nums) # 將 nums 轉化為 set (去重,排序)rns=0 # 存儲最大長度 for n in res:if n-1 not in res:length=1while n+1 in res:length+=1n+=1rns=max(length,rns)return rns# res=0# dic={} # 鍵代表num,值代表它的長度# for i in nums:# if i not in dic:# left=dic.get(i-1,0)# right=dic.get(i+1,0)# cur=left+1+right# res=max(res,cur)# dic[i]=cur# dic[i-left]=cur# dic[i+right]=cur# return res# class Solution:
# # def longestConsecutive(self, nums: List[int]) -> int:
# def longestConsecutive(self, nums):
# longest_streak = 0
# num_set = set(nums)# for num in num_set:
# if num - 1 not in num_set:
# current_num = num
# current_streak = 1# while current_num + 1 in num_set:
# current_num += 1
# current_streak += 1# longest_streak = max(longest_streak, current_streak)# return longest_streak
)
