LeetCode初級演算法練習——陣列篇

NO IMAGE

陣列篇

26. 從排序陣列中刪除重複項

給定一個有序陣列,你需要原地刪除其中的重複內容,使每個元素只出現一次,並返回新的長度。

不要另外定義一個陣列,您必須通過用 O(1) 額外記憶體原地修改輸入的陣列來做到這一點。

示例:

給定陣列: nums = [1,1,2],
你的函式應該返回新長度 2, 並且原陣列nums的前兩個元素必須是1和2
不需要理會新的陣列長度後面的元素

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
前提是已排序
判斷nums[j]與nums[i-1]元素,相等j 1繼續判斷下一元素;不相等,nums[j]賦值給nums[i],
返回i與size的最小值(size為0時返回size,沒有不相同的時候           size==i,有相同的i<size)
"""
i = 1 
j = 1
size = len(nums)
while j < size:
if nums[j] == nums[i-1]:
j  = 1
else: 
nums[i] = nums[j]
i  = 1
j  = 1
return min(i,size)

122.買賣股票的最佳時機 II—— best time to buy and shell stock II 

    假設有一個陣列,它的第 i 個元素是一個給定的股票在第 i 天的價格。

    設計一個演算法來找到最大的利潤。你可以完成儘可能多的交易(多次買賣股票)。然而,你不能同時參與多個交易(你必須在再次購買前出售股票)。

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
total = 0
#當len(prices)==0時,不進行for迴圈,直接ruturn total
for i in range(1,len(prices)):
total  = max(0,prices[i]-prices[i-1])
return total

189. 旋轉陣列rotate array

將包含 n 個元素的陣列向右旋轉 步。

例如,如果  n = 7 ,  k = 3,給定陣列  [1,2,3,4,5,6,7]  ,向右旋轉後的結果為 [5,6,7,1,2,3,4]

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.
"""
if k%len(nums)!=0:#整除則旋轉一輪不變
l=len(nums)
k=k%l#取餘知旋轉幾次
nums[:k],nums[k:]=nums[l-k:],nums[:l-k]

217. 存在重複

給定一個整數陣列,判斷是否存在重複元素。

如果任何值在陣列中出現至少兩次,函式應該返回 true。如果每個元素都不相同,則返回 false。

class Solution:
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""      
#>>> s = set([1, 1, 2, 2, 3, 3])  
#>>> s  
#{1, 2, 3}  在se()中沒有重複的key
return len(nums) != len(set(nums))
"""利用hash table,別忘了判斷空陣列的情況.其實更麻煩"""
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums:
return False
dic = dict() #用list(),append新增會超時
for num in nums:
if num in dic:
return True
dic[num] = 1
return False

136. 只出現一次的數字

給定一個整數陣列,除了某個元素外其餘元素均出現兩次。請找出這個只出現一次的元素。 

備註:

你的演算法應該是一個線性時間複雜度。 你可以不用額外空間來實現它嗎?

class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#由於整數陣列只有一個元素出現一次,利用異或(兩個相同的數的異或為0)運算所有陣列元素
        #出現兩次的元素不管順序如何最後都會異或為0,最後只會剩下出現一次的某元素     
a = 0
for i in nums:
a ^= i
return a

350. 兩個陣列的交集 II

給定兩個陣列,寫一個方法來計算它們的交集。

例如:
給定 nums1 = [1, 2, 2, 1]nums2 = [2, 2], 返回 [2, 2].

注意:

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

跟進:

  • 如果給定的陣列已經排好序呢?你將如何優化你的演算法?
  • 如果 nums1 的大小比 nums2 小很多,哪種方法更優?
  • 如果nums2的元素儲存在磁碟上,記憶體是有限的,你不能一次載入所有的元素到記憶體中,你該怎麼辦?
class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
        #遍歷nums1,用字典對應元素及出現次數
        dic = dict()
        for num in nums1:
            if num in dic:
                dic[num]  = 1
            else:
                dic[num] = 1
        #遍歷nums2,判斷是否在字典中,存在value-1,並加入到list中
        n = list()
        for num in nums2:
            if num in dic.keys() and dic[num] != 0:
                    dic[num] -= 1
                    n.append(num)
        return n
"""但是python內建了Counter型別陣列,可以方便實現計數功能"""
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
from collections import Counter
c1 = Counter(nums1)
c2 = Counter(nums2)
return list((c1&c2).elements())

66. 加一

給定一個非負整陣列成的非空陣列,在該數的基礎上加一,返回一個新的陣列。

最高位數字存放在陣列的首位, 陣列中每個元素只儲存一個數字。

可以假設整數不包含任何前導零,除了數字0本身。

示例 1:

輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入陣列表示數字 123。

示例 2:

輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入陣列表示數字 4321。

class Solution:
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
#str和int的相互轉換
sum = 0
for i in digits:
sum = sum * 10   i
return [int(x) for x in str(sum 1)]

class Solution:
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
n = len(digits) 
i = n-1
while i > -1:#從列表末尾開始加1計算,並判斷是否進位,迴圈至最高位
if digits[i] != 9:#第i個元素不為9,元素直接 1,並返回列表,首輪判定的是列表末尾元素
digits[i] = digits[i]   1
return digits
elif i > 0: #如果為9,且不是最高位元素,該位元素=0,i-1(上一位元素要進位加1,重新判斷i-1位的元素是否為9)
digits[i] = 0
i = i - 1
continue
else:#如果為9,且i=0(此時為最高位,如999 1=1000,第0位元素=0,在列表首位新增數字元素1)
digits[i] = 0
digits =[1]   digits
i = i - 1#跳出迴圈條件
return digits

283. 移動零

給定一個陣列 nums, 編寫一個函式將所有 0 移動到它的末尾,同時保持非零元素的相對順序。

例如, 定義 nums = [0, 1, 0, 3, 12],呼叫函式之後, nums 應為 [1, 3, 12, 0, 0]

注意事項:

  1. 必須在原陣列上操作,不要為一個新陣列分配額外空間。
  2. 儘量減少操作總數。
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
m = len(nums)
i = 0
while i<m:
if nums[i] == 0: #元素為0時,元素索引i不變,元素通過pop和append函式新增在列表末尾,此時為避免無限迴圈m-1
t = nums.pop(i)
nums.append(t)
m -= 1 
else: #元素不為0,遍歷下一元素
i  = 1

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]
"""
dic = dict()
for index,value in enumerate(nums):
sub = target - value
if sub in dic:
return [dic[sub],index]
else:
dic[value] = index

36. 有效的數獨

判斷一個 9×9 的數獨是否有效。只需要根據以下規則,驗證已經填入的數字是否有效即可。

  1. 數字 1-9 在每一行只能出現一次。
  2. 數字 1-9 在每一列只能出現一次。
  3. 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

上圖是一個部分填充的有效的數獨。

數獨部分空格內已填入了數字,空白格用 '.' 表示。

示例 1:

輸入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
輸出: true

示例 2:

輸入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
輸出: false
解釋: 除了第一行的第一個數字從 5 改為 8 以外,空格內其他數字均與 示例1 相同。
但由於位於左上角的 3x3 宮內有兩個 8 存在, 因此這個數獨是無效的。

說明:

  • 一個有效的數獨(部分已被填充)不一定是可解的。
  • 只需要根據以上規則,驗證已經填入的數字是否有效即可。
  • 給定數獨序列只包含數字 1-9 和字元 '.' 。
  • 給定數獨永遠是 9x9 形式的。
class Solution:  
# @param board, a 9x9 2D array  
# @return a boolean  
def valid(self,x,y,tmp,board): 
#tem元素位於x行,y列
for i in range(9):  #判斷第y列元素是否有等於tmp元素的
if board[i][y]==tmp:  
return False  
for j in range(9):  #判斷第x行元素是否有等於tmp元素的
if board[x][j]==tmp:  
return False  
for i in range(3):  #判斷3*3宮內是否有等於tmp元素的
for j in range(3):  
if board[(x//3)*3 i][(y//3)*3 j]==tmp:  #根據x,y計算出3*3宮的元素下標範圍,x//3得到的是整數部分
return False  
return True  
def isValidSudoku(self, board):  
for i in range(9):  #遍歷 行
for j in range(9): #在行不變的情況下,遍歷一整列 
if board[i][j]=='.':   #在為時'.',繼續遍歷
continue  
tmp=board[i][j]  #當為數字時,賦值給tmp
board[i][j]='D'  #將該位元素修改為不相關元素
if self.valid(i,j,tmp,board)==False:  #判斷tmp與陣列所有元素(包括board[i][j],所以修改了board[i][j])是否相同
return False  
else:  #不相同則將board[i][j]修改回來
board[i][j]=tmp  
return True  
class Solution:
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
return (self.is_row_valid(board) and
self.is_col_valid(board) and
self.is_square_valid(board))
def is_row_valid(self, board):
for row in board:#遍歷每一行
if not self.is_unit_valid(row): #is_unit_valid(row)返回的是False,說明行中有相同元素,則return False
return False
return True
'''
zip() 函式用於將可迭代的物件作為引數,將物件中對應的元素打包成一個個元組,然後返回由這些元組組成的列表。
如果各個迭代器的元素個數不一致,則返回列表長度與最短的物件相同,利用 * 號操作符,可以將元組解壓為列表。
>>>a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b)     # 打包為元組的列表
[(1, 4), (2, 5), (3, 6)]
>>> zip(a,c)              # 元素個數與最短的列表一致
[(1, 4), (2, 5), (3, 6)]
>>> zip(*zipped)          # 與 zip 相反,可理解為解壓,返回二維矩陣式
[(1, 2, 3), (4, 5, 6)]
'''
def is_col_valid(self, board):
for col in zip(*board):#zip(*board)將board中對應列的元素以列表形式打包成一個個元祖
if not self.is_unit_valid(col):#判斷是否有相同元素
return False
return True
def is_square_valid(self, board):
for i in (0, 3, 6):
for j in (0, 3, 6):
square = [board[x][y] for x in range(i, i   3) for y in range(j, j   3)] #將3*3宮的元素以列表形式儲存在square中
if not self.is_unit_valid(square):
return False
return True
def is_unit_valid(self, unit):
unit = [i for i in unit if i != '.'] #遍歷引數unit將不為.的元素以列表形式儲存到變數unit
return len(set(unit)) == len(unit) #利用set的性質,如果有重複元素則兩邊不相等,返回False

48. 旋轉影象

給定一個 × n 的二維矩陣表示一個影象。

將影象順時針旋轉 90 度。

說明:

你必須在原地旋轉影象,這意味著你需要直接修改輸入的二維矩陣。請不要使用另一個矩陣來旋轉影象。

示例 1:

給定 matrix = 
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋轉輸入矩陣,使其變為:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:

給定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
], 
原地旋轉輸入矩陣,使其變為:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

class Solution:
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
"""使用兩次旋轉
The idea was firstly transpose the matrix and then flip it symmetrically. For instance,
1  2  3             
4  5  6
7  8  9
after transpose, it will be swap(matrix[i][j], matrix[j][i])
1  4  7
2  5  8
3  6  9
Then flip the matrix horizontally. (swap(matrix[i][j], matrix[i][matrix.length-1-j])
7  4  1
8  5  2
9  6  3
"""
n = len(matrix)
#對角線元素交換
for i in range(n):
for j in range(i):
matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
#同一行前後對應位置的元素互換
left = 0
right = n - 1
while left < right:
for i in range(n):
matrix[i][left],matrix[i][right] = matrix[i][right],matrix[i][left]
left = left   1
right = right - 1