（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
