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