Leetcode python 數組問題

兩個數組的交集

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]輸出: [2,2]

示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]輸出: [4,9]

說明：

• 輸出結果中每個元素出現的次數，應與元素在兩個數組中出現的次數一致。
• 我們可以不考慮輸出結果的順序。

進階:

• 如果給定的數組已經排好序呢？你將如何優化你的演算法？
• 如果 nums1 的大小比 nums2 小很多，哪種方法更優？
• 如果 nums2 的元素存儲在磁碟上，磁碟內存是有限的，並且你不能一次載入所有的元素到內存中，你該怎麼辦？

class Solution: def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ dic={} output=[] for i in nums1: if i in dic: dic[i]=dic[i]+1 else: dic[i]=1 for i in nums2: if i in dic: if dic[i] >= 1: dic[i]-=1 output.append(i) return output

從排序數組中刪除重複項

給定一個排序數組，你需要在原地刪除重複出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。

不要使用額外的數組空間，你必須在原地修改輸入數組並在使用 O(1) 額外空間的條件下完成。

示例 1:

給定數組 nums = [1,1,2], 函數應該返回新的長度 2, 並且原數組 nums 的前兩個元素被修改為 1, 2。 你不需要考慮數組中超出新長度後面的元素

示例 2:

給定 nums = [0,0,1,1,1,2,2,3,3,4],函數應該返回新的長度 5, 並且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。你不需要考慮數組中超出新長度後面的元素。

方法一：class Solution: def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int 執行時間為900ms """ i = 0 while i < len(nums)-1: if nums[i] == nums[i+1]: nums.remove(nums[i]) else: i+=1 return len(nums)方法二：class Solution: def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int 執行時間為120ms """ i = 1 while i < len(nums): if nums[i] == nums[i-1]: nums.pop(i) else: i+=1 return len(nums)

買賣股票的最佳時機

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。

設計一個演算法來計算你所能獲取的最大利潤。你可以儘可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）

示例 1:

輸入: [7,1,5,3,6,4]輸出: 7解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。 隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

示例 2:

輸入: [1,2,3,4,5]輸出: 4解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。 因為這樣屬於同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。

class Solution: def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ flag = 0 buy = 0 sale = 0 profit = 0 for i in range(0, len(prices) - 1): if flag == 0 and prices[i] < prices[i + 1]: buy = prices[i] flag = 1 continue if flag == 1 and prices[i] > prices[i + 1]: sale = prices[i] flag = 0 profit = profit + (sale - buy) if flag == 1: sale = prices[len(prices) - 1] profit = profit + (sale - buy) return profit

旋轉數組

給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數

示例 1:

輸入: [1,2,3,4,5,6,7] 和 k = 3輸出: [5,6,7,1,2,3,4]解釋:向右旋轉 1 步: [7,1,2,3,4,5,6]向右旋轉 2 步: [6,7,1,2,3,4,5]向右旋轉 3 步: [5,6,7,1,2,3,4]

示例 2:

輸入: [-1,-100,3,99] 和 k = 2輸出: [3,99,-1,-100]解釋: 向右旋轉 1 步: [99,-1,-100,3]向右旋轉 2 步: [3,99,-1,-100]

class Solution: def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ nums_length=len(nums) nums[:] = nums[nums_length-k:]+nums[:nums_length-k] return nums

存在重複

給定一個整數數組，判斷是否存在重複元素。

如果任何值在數組中出現至少兩次，函數返回 true。如果數組中每個元素都不相同，則返回 false。

class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ if len(set(nums)) == len(nums): return False else: return True

class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ dic=collections.Counter(nums) for value in dic.values(): if value>=2: return True return False

只出現一次的數字

給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

說明：

你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎？

class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ dic=collections.Counter(nums) for (key,value) in dic.items(): if value<2: return key

加一

給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。

最高位數字存放在數組的首位， 數組中每個元素只存儲一個數字。

你可以假設除了整數 0 之外，這個整數不會以零開頭。

class Solution(object): def plusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ size = len(digits) if size == 0: return [1] carry = 0 digits[size - 1] += 1 while size > 0: digits[size - 1] += carry if digits[size - 1] > 9: digits[size - 1],carry = 0,1 else: carry = 0;break size -= 1 if carry == 0: return digits digits.insert(0,1) return digits

移動零

給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序

說明:

1. 必須在原數組上操作，不能拷貝額外的數組。
2. 盡量減少操作次數。

class Solution: def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ # 思路一： 0 個數多的時候效率低下# for i in nums:# if i == 0:# nums.remove(i)# nums.append(0) # 思路二： 逆向循環避免多餘操作（操作次數是，0個數的兩倍） # for i in range(len(nums)-1,-1,-1): # if nums[i] == 0: # del nums[i] # nums.append(0) # 思路三： 移動非零元素（操作次數就是非零元素的個數） j = 0 # 記錄非零元素應該換到第幾個位置 for i in range(len(nums)): if nums[i] != 0: nums[j], nums[i] = nums[i], nums[j] j += 1

兩數之和

給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。

你可以假設每個輸入只對應一種答案，且同樣的元素不能被重複利用。

示例:

給定 nums = [2, 7, 11, 15], target = 9因為 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ length=len(nums) dic={} for i in range(length): a = target - nums[i] if nums[i] in dic: return dic[nums[i]],i else: dic[a]=i

推薦閱讀：