資訊專欄INFORMATION COLUMN
摘要：字母區(qū)分大小寫，因此和是不同類型的石頭。輸入輸出暴力解法將寶石中的每個元素在石頭中的數(shù)量相加的時間復(fù)雜度為石頭中的每個元素此元素在寶石中則官方解法哈希表將搜索的時間復(fù)雜度變?yōu)?/p>
本文章基于Datewhale第30期組隊學(xué)習(xí)
2021.11.15
# 1 兩數(shù)之和# 給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target，# 請你在該數(shù)組中找出和為目標(biāo)值 target 的那兩個整數(shù)，并返回它們的數(shù)組下標(biāo)。# 你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)
# 1.兩層 for 循環(huán) 暴解 O(n^2)class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: length = len(nums) for i in range(length): for j in range(i+1, length): # 從i+1 開始查找，因為i+1 之前的已經(jīng)查找匹配過了 if nums[i] + nums[j] == target: return [i, j]# 時間太長了（大概2800左右） 嘗試O(n)的方法# 2. 哈希表 O(n)class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: mp = {} for i in range(len(nums)): mp[nums[i]] = i # 因為每種輸入只對應(yīng)一個答案，所以只存儲最后一個 值 的下標(biāo) for i in range(len(nums)): if target - nums[i] in mp.keys() and mp[target - nums[i]] != i: # 防止返回兩次自身的下標(biāo) return [i, mp[target - nums[i]]]# 1929. 數(shù)組串聯(lián)# 給你一個長度為 n 的整數(shù)數(shù)組 nums 。請你構(gòu)建一個長度為 2n 的答案數(shù)組 ans ，# 數(shù)組下標(biāo) 從 0 開始計數(shù) ，對于所有 0 <= i < n 的 i ，滿足下述所有要求：# ans[i] == nums[i]# ans[i + n] == nums[i]# 具體而言，ans 由兩個 nums 數(shù)組 串聯(lián) 形成。
"""例：輸入：nums = [1,2,1] 輸出：[1,2,1,1,2,1] 解釋：數(shù)組 ans 按下述方式形成： - ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]] - ans = [1,2,1,1,2,1]"""# 如題所述class Solution: def getConcatenation(self, nums: List[int]) -> List[int]: length = len(nums) ans = [0] * 2 * length length = len(nums) for i in range(length): ans[i] = nums[i] ans[i + length ] = nums[i] return ans# 但實際上只需要將 nums * 2 或者 用 extend 即可class Solution: def getConcatenation(self, nums: List[int]) -> List[int]: # return nums * 2 # return nums + nums nums.extend(nums) return nums# 771. 寶石與石頭# 給你一個字符串 jewels 代表石頭中寶石的類型，另有一個字符串 stones 代表你擁有的石頭。# stones 中每個字符代表了一種你擁有的石頭的類型，你想知道你擁有的石頭中有多少是寶石。# 字母區(qū)分大小寫，因此 "a" 和 "A" 是不同類型的石頭。
""""輸入：jewels = "aA", stones = "aAAbbbb"輸出：3"""# 暴力解法 O(mn)class Solution: def numJewelsInStones(self, jewels: str, stones: str) -> int: # return sum(stones.count(i) for i in jewels) # 將 寶石中 的每個元素在 石頭中的數(shù)量相加 num = 0 # string.count的時間復(fù)雜度為 O(n) for i in stones: # 石頭中的每個元素 if i in jewels: # 此元素在 寶石 中 則 num++ num += 1 return num# O(m+n) 官方解法class Solution: def numJewelsInStones(self, jewels: str, stones: str) -> int: jewelsSet = set(jewels) # 哈希表 將搜索的時間復(fù)雜度變?yōu)镺(1) return sum(s in jewelsSet for s in stones)?
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/123495.html
摘要：正式地講，提莫在發(fā)起發(fā)起攻擊意味著艾希在時間區(qū)間含和處于中毒狀態(tài)。示例輸入輸出解釋提莫攻擊對艾希的影響如下第秒，提莫攻擊艾希并使其立即中毒。第秒，提莫再次攻擊艾希，艾希中毒狀態(tài)又持續(xù)秒，即第秒和第秒。 ...
摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數(shù)組知識點?；蛘呃奖疚淖钕旅?，添加的微信等會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
前端LeetCode刷題 下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關(guān)注。 數(shù)組類 26 刪除排序數(shù)組中的重復(fù)項 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數(shù)組中的重復(fù)項2 88 合并兩個有序數(shù)組 167 兩數(shù)之和II - 輸入有序數(shù)組 118 楊輝三角 169 easy 求眾數(shù) 1...
??前面的話?? 大家好！這是Java基礎(chǔ)知識與數(shù)據(jù)結(jié)構(gòu)博文的導(dǎo)航帖，收藏我！學(xué)習(xí)Java不迷路！ ?博客主頁：未見花聞的博客主頁 ?歡迎關(guān)注?點贊?收藏??留言? ?本文由未見花聞原創(chuàng)，CSDN首發(fā)！ ?首發(fā)時間：?2021年11月11日? ??堅持和努力一定能換來詩與遠(yuǎn)方！ ?參考書籍：?《Java核心技術(shù)卷1》，?《Java核心技術(shù)卷2》，?《Java編程思想》 ?參考在線編程網(wǎng)站：?牛...
閱讀 1867·2021-11-18 10:02
閱讀 3587·2021-11-16 11:45
閱讀 1884·2021-09-10 10:51
閱讀 2194·2019-08-30 15:43
閱讀 1432·2019-08-30 11:23
閱讀 1544·2019-08-29 11:07
閱讀 1961·2019-08-23 17:05
閱讀 1564·2019-08-23 16:14
