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

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

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

"""
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])

189. 旋轉陣列rotate array

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. 存在重複

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 的大小比 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. 加一

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. 移動零

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. 兩數之和

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. 有效的數獨

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

[
["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"]
]

[
["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"]
]

• 一個有效的數獨（部分已被填充）不一定是可解的。
• 只需要根據以上規則，驗證已經填入的數字是否有效即可。
• 給定數獨序列只包含數字 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. 旋轉影象

[
[1,2,3],
[4,5,6],
[7,8,9]
],

[
[7,4,1],
[8,5,2],
[9,6,3]
]

[
[ 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