（2019.7.26）不斷更新中……
【python】Leetcode（Data Structure / Algorithm）
【python】Leetcode（Dynamic Programming）
【python】Leetcode（Map）
【python】Leetcode（String）
【python】Leetcode（Tree）
【python】Coding（Interview）
文章目錄
- 數字
- 260. 只出現一次的數字 III（字典 / 位運算）
- 136. 只出現一次的數字（字典）
- 137. 只出現一次的數字 II（字典）
- 169. 求眾數（字典）
- 229. 求眾數 II（字典）
- 977. 有序數組的平方
- 728. 自除數
- 507. 完美數
- 908. 最小差值 I
- 504. 七進制數（進制轉換）
- 461. 漢明距離（進制轉換 / 異或）
- 462. 最少移動次數使數組元素相等 II（中位數）
- 88. 合并兩個有序數組（雙指針）
- 167. 兩數之和 II - 輸入有序數組（雙指針）
- 1. 兩數之和（無序用Hash）
- 75. 顏色分類（荷蘭國旗）
- 78. 子集（集合的所有子集）
- 90. 子集 II（集合的所有子集）
- 944. 刪列造序（zip（*list））
- 867. 轉置矩陣（zip（*list））
- 999. 車的可用捕獲量（上下左右遍歷）
數字
260. 只出現一次的數字 III（字典 / 位運算）
給定一個整數數組 nums，其中恰好有兩個元素只出現一次，其余所有元素均出現兩次。 找出只出現一次的那兩個元素。
-
示例 :
輸入: [1,2,1,3,2,5]
輸出: [3,5] -
注意：
結果輸出的順序并不重要，對于上面的例子， [5, 3] 也是正確答案。
你的算法應該具有線性時間復雜度。你能否僅使用常數空間復雜度來實現？
思路1：用字典，key 是數字，value 是頻數，出現了兩次，就刪掉，最后輸出字典中有的元素
class
Solution
(
object
)
:
def
singleNumber
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: List[int]
"""
dict1
=
{
}
for
i
in
nums
:
if
i
in
dict1
:
del
dict1
[
i
]
else
:
dict1
[
i
]
=
1
list1
=
[
]
for
i
in
dict1
:
list1
.
append
(
i
)
return
list1
還有一種用二進制與操作的方法，很懵！（bryant）
LeetCode Medium 260 找單獨的數III Python
136. 只出現一次的數字（字典）
給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。
-
說明：
你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎？ -
示例 1:
輸入: [2,2,1]
輸出: 1 -
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
可以用
260. 只出現一次的數字 III（字典）
的方法！
class
Solution
(
object
)
:
def
singleNumber
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: int
"""
dict1
=
{
}
for
i
in
nums
:
if
i
in
dict1
:
del
dict1
[
i
]
else
:
dict1
[
i
]
=
1
for
i
in
dict1
:
return
i
137. 只出現一次的數字 II（字典）
給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現了三次。找出那個只出現了一次的元素。
-
說明：
你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎？ -
示例 1:
輸入: [2,2,3,2]
輸出: 3 -
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
這個出現了三次，不能像
260. 只出現一次的數字 III（字典）
那樣，出現第二次的時候刪掉字典鍵值對，所以我們中規中矩，把數字和頻數存在字典中，然后，遍歷字典，輸出頻數為 1 的數
class
Solution
(
object
)
:
def
singleNumber
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: int
"""
dict1
=
{
}
for
i
in
nums
:
if
i
not
in
dict1
:
dict1
[
i
]
=
0
dict1
[
i
]
+=
1
else
:
dict1
[
i
]
+=
1
for
i
in
dict1
:
if
dict1
[
i
]
==
1
:
return
i
169. 求眾數（字典）
給定一個大小為 n 的數組，找到其中的眾數。眾數是指在數組中出現次數大于 ? n/2 ? 的元素。
你可以假設數組是非空的，并且給定的數組總是存在眾數。
-
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2: -
輸入: [2,2,1,1,1,2,2]
輸出: 2
還是可以用
137. 只出現一次的數字 II
的思路，存在字典中，keys 是數字，values 是頻數，然后根據頻數篩選出最終答案！
class
Solution
(
object
)
:
def
majorityElement
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: int
"""
dict1
=
{
}
for
i
in
nums
:
if
i
not
in
dict1
:
dict1
[
i
]
=
1
else
:
dict1
[
i
]
+=
1
for
i
in
dict1
:
if
dict1
[
i
]
>
len
(
nums
)
/
2
:
return
i
還可以，直接排序，然后輸出后半段的數字就可以了！反正眾數一定存在，而且不管是比其他數大還是小，都占了一半以上！
class
Solution
(
object
)
:
def
majorityElement
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: int
"""
sort_nums
=
sorted
(
nums
)
return
sort_nums
[
len
(
nums
)
//
2
]
229. 求眾數 II（字典）
給定一個大小為 n 的數組，找出其中所有出現超過 ? n/3 ? 次的元素。
-
說明: 要求算法的時間復雜度為 O(n)，空間復雜度為 O(1)。
-
示例 1:
輸入: [3,2,3]
輸出: [3] -
示例 2:
輸入: [1,1,1,3,3,2,2,2]
輸出: [1,2]
還是可以用字典
class
Solution
(
object
)
:
def
majorityElement
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: List[int]
"""
dict1
=
{
}
list1
=
[
]
for
i
in
nums
:
if
i
not
in
dict1
:
dict1
[
i
]
=
1
else
:
dict1
[
i
]
+=
1
for
i
in
dict1
:
if
dict1
[
i
]
>
len
(
nums
)
/
3
:
list1
.
append
(
i
)
return
list1
977. 有序數組的平方
給定一個按非遞減順序排序的整數數組 A，返回每個數字的平方組成的新數組，要求也按非遞減順序排序。
-
示例 1：
輸入：[-4,-1,0,3,10]
輸出：[0,1,9,16,100] -
示例 2：
輸入：[-7,-3,2,3,11]
輸出：[4,9,9,49,121] -
提示：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非遞減順序排序。
先忽略掉順序，用最暴力的方法，遍歷，平方， 排序
class
Solution
(
object
)
:
def
sortedSquares
(
self
,
A
)
:
"""
:type A: List[int]
:rtype: List[int]
"""
return
sorted
(
[
i
**
2
for
i
in
A
]
)
還有可以用歸并排序，兩個指針（bryant）
728. 自除數
自除數 是指可以被它包含的每一位數除盡的數。
例如，128 是一個自除數，因為 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
還有，自除數不允許包含 0 。
給定上邊界和下邊界數字，輸出一個列表，列表的元素是邊界（含邊界）內所有的自除數。
-
示例 1：
輸入：
上邊界left = 1, 下邊界right = 22
輸出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
注意：
每個輸入參數的邊界滿足 1 <= left <= right <= 10000。
class
Solution
(
object
)
:
def
selfDividingNumbers
(
self
,
left
,
right
)
:
"""
:type left: int
:type right: int
:rtype: List[int]
"""
list1
=
[
]
for
num
in
range
(
left
,
right
+
1
)
:
# 遍歷區間的每一個數字
sum1
=
0
# 記錄是否每個數都除的盡
if
'0'
in
str
(
num
)
:
# 跳過包含 0 的項
continue
for
item
in
str
(
num
)
:
# 遍歷每一個數字的每一位
if
num
%
int
(
item
)
==
0
:
#自除數
sum1
+=
1
if
sum1
==
len
(
str
(
num
)
)
:
#if 每個數都除的盡
list1
.
append
(
num
)
return
list1
507. 完美數
對于一個 正整數，如果它和除了它自身以外的所有正因子之和相等，我們稱它為“完美數”。
給定一個 整數 n， 如果他是完美數，返回 True，否則返回 False
-
示例：
輸入: 28
輸出: True
解釋: 28 = 1 + 2 + 4 + 7 + 14 -
提示：
輸入的數字 n 不會超過 100,000,000. (1e8)
思路：要注意，1不符合條件，不過貌似測試樣例會給負數，因為負數的小數次冪得到的是復數，一直報錯！我們只用遍歷 2到 sqrt(num) 即可
class
Solution
(
object
)
:
def
checkPerfectNumber
(
self
,
num
)
:
"""
:type num: int
:rtype: bool
"""
if
num
<=
1
:
# 這個限制很關鍵
return
False
sum1
=
1
for
i
in
range
(
2
,
int
(
num
**
0.5
)
+
1
)
:
if
num
%
i
==
0
:
sum1
+=
i
sum1
+=
num
//
i
if
num
==
sum1
:
return
True
else
:
return
False
908. 最小差值 I
給定一個整數數組 A，對于每個整數 A[i]，我們可以選擇任意 x 滿足 -K <= x <= K，并將 x 加到 A[i] 中。
在此過程之后，我們得到一些數組 B。
返回 B 的最大值和 B 的最小值之間可能存在的最小差值。
-
示例 1：
輸入：A = [1], K = 0
輸出：0
解釋：B = [1] -
示例 2：
輸入：A = [0,10], K = 2
輸出：6
解釋：B = [2,8] -
示例 3：
輸入：A = [1,3,6], K = 3
輸出：0
解釋：B = [3,3,3] 或 B = [4,4,4] -
提示：
1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000
思路：相當于 A 中的每個數字在 [-K,K] 的范圍內波動，求波動后 B 中最大元素與最小元素差值的最小值！我們先計算出原來 A 中的差值，然后比較差值與 2K 的大小，如果小于 2K，那么最小差值能被波動抹平，自然是0，如果大于 2K，波動最多只能縮小 2K 的差距，也即 max - K and min+K
class
Solution
(
object
)
:
def
smallestRangeI
(
self
,
A
,
K
)
:
"""
:type A: List[int]
:type K: int
:rtype: int
"""
A_min
=
min
(
A
)
A_max
=
max
(
A
)
result
=
A_max
-
A_min
-
2
*
K
if
result
>
0
:
return
result
else
:
return
0
504. 七進制數（進制轉換）
給定一個整數，將其轉化為7進制，并以字符串形式輸出。
-
示例 1:
輸入: 100
輸出: “202”
示例 2: -
輸入: -7
輸出: “-10” -
注意: 輸入范圍是 [-1e7, 1e7] 。
class
Solution
(
object
)
:
def
convertToBase7
(
self
,
num
)
:
"""
:type num: int
:rtype: str
"""
nums
=
abs
(
num
)
s
=
''
# 這里只對大于0的數算 7 進制
while
(
nums
)
:
a
=
nums
%
7
nums
=
nums
//
7
s
=
s
+
str
(
a
)
if
num
>
0
:
return
s
[
:
:
-
1
]
# 倒序輸出計算結果
elif
num
<
0
:
return
'-'
+
s
[
:
:
-
1
]
# 負數添加一個負號
else
:
return
'0'
# 0 的話直接返回 0
461. 漢明距離（進制轉換 / 異或）
兩個整數之間的漢明距離指的是這兩個數字對應二進制位不同的位置的數目。
給出兩個整數 x 和 y，計算它們之間的漢明距離。
注意：
0 ≤ x, y < 231.
-
示例:
輸入: x = 1, y = 4
輸出: 2
解釋:
1
(
0
0
0
1
)
4
(
0
1
0
0
)
↑ ↑
上面的箭頭指出了對應二進制位不同的位置。
思路，計算二進制，然后比不同的位置
class
Solution
(
object
)
:
def
hammingDistance
(
self
,
x
,
y
)
:
"""
:type x: int
:type y: int
:rtype: int
"""
# 計算二進制逆序（方便后面的高位補0），結果存在列表中，
def
bin_num
(
x
)
:
list1
=
[
]
while
(
x
)
:
list1
.
append
(
x
%
2
)
x
=
x
//
2
return
list1
bin_x
=
bin_num
(
x
)
bin_y
=
bin_num
(
y
)
len_x
=
len
(
bin_x
)
len_y
=
len
(
bin_y
)
# 把兩個二進制的長度補成一樣的
if
len_x
<
len_y
:
bin_x
.
extend
(
[
0
]
*
(
len_y
-
len_x
)
)
else
:
bin_y
.
extend
(
[
0
]
*
(
len_x
-
len_y
)
)
# 統計不一樣的個數
num
=
0
for
i
in
range
(
len
(
bin_x
)
)
:
if
bin_x
[
i
]
!=
bin_y
[
i
]
:
num
+=
1
return
num
還有一種比較快的方法是直接計算異或（相同為1，不同為0）
class
Solution
(
object
)
:
def
hammingDistance
(
self
,
x
,
y
)
:
"""
:type x: int
:type y: int
:rtype: int
"""
return
bin
(
x
^
y
)
.
count
(
'1'
)
462. 最少移動次數使數組元素相等 II（中位數）
給定一個非空整數數組，找到使所有數組元素相等所需的最小移動數，其中每次移動可將選定的一個元素加1或減1。 您可以假設數組的長度最多為10000。
-
例如:
輸入:
[1,2,3]
輸出:
2 -
說明：
只有兩個動作是必要的（記得每一步僅可使其中一個元素加1或減1）：
[1,2,3] => [2,2,3] => [2,2,2]
思路，排序后找到中位數，到中位數的移動次數最少（其實我也沒有能完全 get，為什么到中位數移動次數最少，最好是能證明一下，哈哈哈）！
class
Solution
(
object
)
:
def
minMoves2
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: int
"""
nums
=
sorted
(
nums
)
l
=
len
(
nums
)
if
l
%
2
==
0
:
mid
=
(
nums
[
l
/
2
]
+
nums
[
(
l
-
1
)
/
2
]
)
//
2
else
:
mid
=
nums
[
l
//
2
]
sum1
=
0
for
i
in
nums
:
sum1
+=
abs
(
mid
-
i
)
return
sum1
還有解題思路是相遇！（bryant）
88. 合并兩個有序數組（雙指針）
給定兩個有序整數數組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序數組。
-
說明:
初始化 nums1 和 nums2 的元素數量分別為 m 和 n。
你可以假設 nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素。 -
示例:
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]
思路：題目中不能用別的數組來存排序后的結果，方法是采用兩個指針，倒序遍歷兩個數組，比較大小，把較大的數字從后面依次放在數組1中，最后把數組2剩下的數字全部復制到數組1中！
class
Solution
(
object
)
:
def
merge
(
self
,
nums1
,
m
,
nums2
,
n
)
:
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
p1
=
m
-
1
p2
=
n
-
1
p12
=
m
+
n
-
1
while
p1
>=
0
and
p2
>=
0
:
if
nums1
[
p1
]
>=
nums2
[
p2
]
:
nums1
[
p12
]
=
nums1
[
p1
]
p1
-=
1
p12
-=
1
else
:
nums1
[
p12
]
=
nums2
[
p2
]
p2
-=
1
p12
-=
1
nums1
[
:
p2
+
1
]
=
nums2
[
:
p2
+
1
]
167. 兩數之和 II - 輸入有序數組（雙指針）
給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等于目標數。
函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。
-
說明:
返回的下標值（index1 和 index2）不是從零開始的。
你可以假設每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。 -
示例:
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標數 9 。因此 index1 = 1, index2 = 2 。
1）暴力法
class
Solution
(
object
)
:
def
twoSum
(
self
,
numbers
,
target
)
:
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
list1
=
[
]
l
=
len
(
numbers
)
for
i
in
range
(
l
)
:
for
j
in
range
(
i
+
1
,
l
)
:
if
numbers
[
i
]
+
numbers
[
j
]
==
target
:
list1
.
append
(
i
+
1
)
list1
.
append
(
j
+
1
)
return
list1
2）雙指針
參考 https://blog.csdn.net/qq_17550379/article/details/80512745
我們可以這樣想，我們首先判斷首尾兩項的和是不是 target，如果比 target 小，那么我們左邊+1位置的數（比左邊位置的數大）再和右相相加，繼續判斷。如果比 target 大，那么我們右邊-1位置的數（比右邊位置的數小）再和左相相加，繼續判斷。我們通過這樣不斷放縮的過程，就可以在 O(n) 的時間復雜度內找到對應的坐標位置。（這和快速排序的思路很相似）
class
Solution
(
object
)
:
def
twoSum
(
self
,
numbers
,
target
)
:
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
l
=
len
(
numbers
)
left
=
0
right
=
l
-
1
#for i in range(l):
while
left
<
right
:
if
numbers
[
left
]
+
numbers
[
right
]
==
target
:
return
[
left
+
1
,
right
+
1
]
elif
numbers
[
left
]
+
numbers
[
right
]
>
target
:
right
-=
1
else
:
left
+=
1
return
[
]
1. 兩數之和
無序用Hash
1. 兩數之和（無序用Hash）
給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那兩個整數，并返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。
-
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1）暴力法
兩層循環嘛
class
Solution
(
object
)
:
def
twoSum
(
self
,
nums
,
target
)
:
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for
i
in
range
(
len
(
nums
)
-
1
)
:
# 0-倒數第二個
for
j
in
range
(
i
+
1
,
len
(
nums
)
)
:
# i的下一個到最后一個
if
nums
[
i
]
+
nums
[
j
]
==
target
:
return
[
i
,
j
]
2）Hash 表
思路
建立一個字典，keys 存當前元素達到 target 所需要的數值，values 存的是當前元素的下標！（也就是說第 values 個元素需要找 keys 才能匹配成功！）
遍歷數組元素，判斷元素是否在字典的 keys 中
如果在
，匹配成功，返回元素下標和字典的 values（也即自己另一半在數組中的下標）！
如果不在
，新增一個字典 item，將該元素達到 target 所需的數字存為 keys，該元素下標存為 values！參考 [LeetCode]1.TwoSum（Python實現）
class
Solution
(
object
)
:
def
twoSum
(
self
,
nums
,
target
)
:
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dict1
=
{
}
for
i
,
num
in
enumerate
(
nums
)
:
if
nums
[
i
]
in
dict1
:
return
[
i
,
dict1
[
nums
[
i
]
]
]
else
:
dict1
[
target
-
nums
[
i
]
]
=
i
167. 兩數之和 II - 輸入有序數組（雙指針）
有序的話用雙指針就可以
75. 顏色分類（荷蘭國旗）
給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。
此題中，我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。
-
注意:
不能使用代碼庫中的排序函數來解決這道題。 -
示例:
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2] -
進階：
一個直觀的解決方案是使用計數排序的兩趟掃描算法。
首先，迭代計算出0、1 和 2 元素的個數，然后按照0、1、2的排序，重寫當前數組。
你能想出一個僅使用常數空間的一趟掃描算法嗎？
1）桶排序
第一個想法當然是桶排序，參考本博客
347. 前 K 個高頻元素
中對桶排序的描述！
class
Solution
(
object
)
:
def
sortColors
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
buckets
=
[
0
]
*
3
for
i
in
nums
:
buckets
[
i
]
+=
1
del
nums
[
:
]
# 哈哈很精髓，注釋中說了不要改
for
i
in
range
(
len
(
buckets
)
)
:
if
buckets
[
i
]
:
nums
.
extend
(
[
i
]
*
buckets
[
i
]
)
不過題目要求原地算法，所以有瑕疵！
在計算機科學中，一個 原地算法 （in-place algorithm）是一種使用小的，固定數量的額外之空間來轉換資料的算法。當算法執行時，輸入的資料通常會被要輸出的部份覆蓋掉。不是原地算法有時候稱為非原地（not-in-place）或不得其所（out-of-place）——百度百科
2）利用快排序的思想
這個問題我們可以將這個問題視為一個數組排序問題，這個數組分為前部，中部和后部（0，1，2）三個部分！
思路如下：將前部和后部各排在數組的前邊和后邊，中部自然就排好了。具體的：
設置兩個標志位 begin 和 end 分別指向這個數組的開始和末尾，然后用一個標志位 current 從頭開始進行遍歷：
- 若遍歷到的位置為 0，則說明它一定屬于前部，于是就和 begin 位置進行交換，然后 current 向前進，begin 也向前進（表示前邊的已經都排好了）。
- 若遍歷到的位置為 1，則說明它一定屬于中部，根據總思路，中部的我們都不動，然后 current 向前進。
- 若遍歷到的位置為 2，則說明它一定屬于后部，于是就和 end 位置進行交換，由于交換完畢后 current 指向的可能是屬于前部的，若此時 current 前進則會導致該位置不能被交換到前部， 所以此時 current 不前進 ），end 向后退1。
參考
- 快速排序深入之荷蘭國旗問題
- Leetcode 75 python
class
Solution
(
object
)
:
def
sortColors
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
start
=
0
end
=
len
(
nums
)
-
1
current
=
0
while
current
<=
end
:
if
nums
[
current
]
==
2
:
# 這里沒有 current++ 小心這個坑
nums
[
current
]
,
nums
[
end
]
=
nums
[
end
]
,
nums
[
current
]
end
-=
1
elif
nums
[
current
]
==
0
:
nums
[
current
]
,
nums
[
start
]
=
nums
[
start
]
,
nums
[
current
]
current
+=
1
start
+=
1
else
:
current
+=
1
78. 子集（集合的所有子集）
給定一組不含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。
說明：解集不能包含重復的子集
思路：可以迭代，可以回溯，
算 1 的子集的時候，新增 1 結合 空集；
算 2 的子集的時候，2 結合 1 的所有子集；
算 3 的子集的時候，3 結合 2 的所有子集
…
class
Solution
(
object
)
:
def
subsets
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result
=
[
[
]
]
for
i
in
nums
:
result
.
extend
(
[
j
+
[
i
]
for
j
in
result
]
)
return
result
90. 子集 II（集合的所有子集）
給定一個可能包含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。
說明：解集不能包含重復的子集。
思路：和 78 唯一不同的是 nums 可能包含一樣的元素，這個時候就會存在 [1,2] 和 [2,1] 或者更難一點的 [1,2,2] 和 [2,1,2] 的情況，78 的解法這兩個都會保留（78中元素不一樣），但是這題只能保留其中一種！
簡單的 set 好像排除不了，我用的是 sorted
class
Solution
(
object
)
:
def
subsetsWithDup
(
self
,
nums
)
:
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result
=
[
[
]
]
for
i
in
nums
:
result
.
extend
(
[
j
+
[
i
]
for
j
in
result
]
)
set1
=
set
(
tuple
(
sorted
(
item
)
)
for
item
in
result
)
# tuple 才能 hash——set，sorted 配合set來去重
list1
=
list
(
list
(
item
)
for
item
in
set1
)
# 轉化成輸出的格式
return
list1
944. 刪列造序（zip（*list））
給定由 N 個小寫字母字符串組成的數組 A，其中每個字符串長度相等。
刪除 操作的定義是：選出一組要刪掉的列，刪去 A 中對應列中的所有字符，形式上，第 n 列為 [A[0][n], A[1][n], …, A[A.length-1][n]]）。
比如，有 A = [“abcdef”, “uvwxyz”]，
思路：列表中的的行的組合變成列的組合，然后判斷是否升序
class
Solution
(
object
)
:
def
minDeletionSize
(
self
,
A
)
:
"""
:type A: List[str]
:rtype: int
"""
B
=
[
]
# 交換行列
for
i
in
range
(
len
(
A
[
0
]
)
)
:
#遍歷列
s
=
""
for
j
in
range
(
len
(
A
)
)
:
#遍歷行
s
+=
A
[
j
]
[
i
]
B
.
append
(
s
)
count
=
0
# 比較大小
for
i
in
range
(
len
(
B
)
)
:
for
j
in
range
(
len
(
B
[
0
]
)
-
1
)
:
#第i組的第j個元素
if
B
[
i
]
[
j
]
>
B
[
i
]
[
j
+
1
]
:
#比較大小
count
+=
1
break
return
count
這么做太暴力了，需要柔美一點的，是否非降序可以用排序前后的對比，行列的互換可以用
zip(*list)
class
Solution
(
object
)
:
def
minDeletionSize
(
self
,
A
)
:
"""
:type A: List[str]
:rtype: int
"""
count
=
0
for
item
in
zip
(
*
A
)
:
if
sorted
(
item
)
!=
list
(
item
)
:
#這里注意 item 是元組，排序完是list
count
+=
1
return
count
867. 轉置矩陣（zip（*list））
給定一個矩陣 A， 返回 A 的轉置矩陣。
矩陣的轉置是指將矩陣的主對角線翻轉，交換矩陣的行索引與列索引。
示例 1：
輸入：[[1,2,3],[4,5,6],[7,8,9]]
輸出：[[1,4,7],[2,5,8],[3,6,9]]
思路：可以l兩層便利 a,b = b,a，也可以利用
zip（*list）
class
Solution
(
object
)
:
def
transpose
(
self
,
A
)
:
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
list1
=
[
]
for
i
in
zip
(
*
A
)
:
list1
.
append
(
list
(
i
)
)
return
list1
999. 車的可用捕獲量（上下左右遍歷）
在一個 8 x 8 的棋盤上，有一個白色車（rook）。也可能有空方塊，白色的象（bishop）和黑色的卒（pawn）。它們分別以字符 “R”，“.”，“B” 和 “p” 給出。大寫字符表示白棋，小寫字符表示黑棋。
車按國際象棋中的規則移動：它選擇四個基本方向中的一個（北，東，西和南），然后朝那個方向移動，直到它選擇停止、到達棋盤的邊緣或移動到同一方格來捕獲該方格上顏色相反的卒。另外，車不能與其他友方（白色）象進入同一個方格。
返回車能夠在一次移動中捕獲到的卒的數量。
思路：定位到車的位置，然后以車為原點，上下左右四條路出發，if 遇到象就直接break，else 遇到兵，結果+1，也 break（注意：因為不可能是肉彈戰車，橫掃千軍）
class
Solution
(
object
)
:
def
numRookCaptures
(
self
,
board
)
:
"""
:type board: List[List[str]]
:rtype: int
"""
# 定位
flag
=
False
for
row
in
range
(
len
(
board
)
)
:
for
col
in
range
(
len
(
board
[
0
]
)
)
:
if
board
[
row
]
[
col
]
==
"R"
:
flag
=
True
break
if
flag
==
True
:
break
count
=
0
# 上
for
i
in
reversed
(
range
(
row
)
)
:
if
board
[
i
]
[
col
]
==
"B"
:
break
elif
board
[
i
]
[
col
]
==
"p"
:
count
+=
1
break
# 下
for
i
in
range
(
row
+
1
,
len
(
board
[
0
]
)
)
:
if
board
[
i
]
[
col
]
==
"B"
:
break
elif
board
[
i
]
[
col
]
==
"p"
:
count
+=
1
break
# 左
for
j
in
reversed
(
range
(
col
)
)
:
if
board
[
row
]
[
j
]
==
"B"
:
break
elif
board
[
row
]
[
j
]
==
"p"
:
count
+=
1
break
# 右
for
j
in
range
(
col
+
1
,
len
(
board
)
)
:
if
board
[
row
]
[
j
]
==
"B"
:
break
elif
board
[
row
]
[
j
]
==
"p"
:
count
+=
1
break
return
count
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
