Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 483d19f

Browse filesBrowse files
nature1995nature1995
committed
Update to 066
Update to 066
1 parent 70e5e31 commit 483d19f
Copy full SHA for 483d19f

5 files changed

+230
-0
lines changed

‎Python3/049_Group_Anagrams.py

Copy file name to clipboard
+40Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Given an array of strings, group anagrams together.
5+
6+
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
7+
Return:
8+
9+
[
10+
["ate", "eat","tea"],
11+
["nat","tan"],
12+
["bat"]
13+
]
14+
Note:
15+
For the return value, each inner list's elements must follow the lexicographic order.
16+
All inputs will be in lower-case.
17+
'''
18+
19+
20+
class Solution(object):
21+
def groupAnagrams(self, strs):
22+
"""
23+
:type strs: List[str]
24+
:rtype: List[List[str]]
25+
"""
26+
map = {}
27+
for i, v in enumerate(strs):
28+
target = "".join(sorted(v))
29+
if target not in map:
30+
map[target] = [v]
31+
else:
32+
map[target].append(v)
33+
result = []
34+
for value in map.values():
35+
result += [sorted(value)]
36+
return result
37+
38+
39+
if __name__ == "__main__":
40+
assert Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) == [['ate', 'eat', 'tea'], ['nat', 'tan'], ['bat'],]

‎Python3/053_Maximum_Subarray_Method1.py

Copy file name to clipboard
+51Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
5+
6+
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
7+
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
8+
'''
9+
# 思路一：
10+
# 遍历法，On:
11+
# 算法过程：遍历数组，用onesum去维护当前元素加起来的和。当onesum出现小于0的情况时，我们把它设为0。然后每次都更新全局最大值。
12+
13+
# 算法证明：一开始思考数组是个空的，把我们每次选一个nums[i]加入onesum看成当前数组新增了一个元素，也就是用动态的眼光去思考。
14+
# 过程很简单，代码很短，但为什么这样就能达到效果呢？我们进行的加和是按顺序来的，从数组第一个开始加。
15+
# 当我们的i选出来后，加入onesum。这时有2种情况
16+
17+
# 1）假设我们这个onesum一直大于0，从未被<0过。那也就是说我们计算的每一次的onesum都大于0，而每一次计算的onesum都是包括开头元
18+
# 素的一段子序列（尾部一直随i变化）。看似我们没有考虑所有可能序列，但实际上所有可能的序列都已经被考虑过了。这里简单讲一下，
19+
# 待会po原文。
20+
#    a)以当前子序列开头为开头，中间任一处结尾的序列。这种情况是一直在扫描的，也有一直保存更新，所以不用怕丢失信息。
21+
#    b)以当前子序列结尾为结尾，中间任一处开头的序列。这种情况一定的和小于以当前子序列开头为开头，结尾为结尾的序列。因为前
22+
# 面缺失的那一段经过我们的前提，它也是加和大于0的。
23+
#    c)以中间元素为开头和结尾的序列。和小于以当前子序列开头为开头，此分序列结尾为结尾的序列。因为前面缺失的那一段经过我们
24+
# 的前提，它也是加和大于0的。
25+
26+
# 2）出现小于0的情况，就说明我们当前形成的这个子序是第一次出现小于0的情况。现在至少我们要新形成的连续数组不能在整个的包括之前
27+
# 的连续子序了，因为我们在之前的那个连续子序里加出了<0的情况。但问题是我们需不需要保留一些呢？是不是所有以当前子序结尾为结尾的
28+
# 任意开头的子序都要被舍弃呢？答案是是的，因为那一段也一定小于0，因为那一段的加和会小于以当前子序开头为开头，当前子序结尾为结
29+
# 尾的序列（见前面证明）。于是抛弃掉它们，重新开始新的子序。
30+
31+
32+
class Solution(object):
33+
def maxSubArray(self, nums):
34+
"""
35+
:type nums: List[int]
36+
:rtype: int
37+
"""
38+
# onesum维护当前的和
39+
onesum = 0
40+
maxsum = nums[0]
41+
for i in range(len(nums)):
42+
onesum += nums[i]
43+
maxsum = max(maxsum, onesum)
44+
# 出现onesum<0的情况，就设为0，重新累积和
45+
if onesum < 0:
46+
onesum = 0
47+
return maxsum
48+
49+
50+
if __name__ == "__main__":
51+
assert Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6

‎Python3/053_Maximum_Subarray_Method2.py

Copy file name to clipboard
+41Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
5+
6+
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
7+
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
8+
'''
9+
# 思路二：
10+
# 动态规划 On
11+
12+
# 算法过程：
13+
# 设sum[i]为以第i个元素结尾的最大的连续子数组的和。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以
14+
# 第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，
15+
# 即sum[i]
16+
# = max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。
17+
# 由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法
18+
# 的时间和空间复杂度都很小
19+
20+
# 算法证明：这道题的代码我直接使用了题目数据中的nums数组，因为只要遍历一遍。nums[i]表示的是以当前这第i号元素结尾（看清了一定
21+
# 要包含当前的这个i）的话，最大的值无非就是看以i-1结尾的最大和的子序能不能加上我这个nums[i]，如果nums[i]>0的话，则加上。注意
22+
# 我代码中没有显式地去这样判断，不过我的Max表达的就是这个意思，然后我们把nums[i]确定下来。
23+
24+
25+
class Solution(object):
26+
def maxSubArray(self, nums):
27+
"""
28+
:type nums: List[int]
29+
:rtype: int
30+
"""
31+
length = len(nums)
32+
for i in range(1, length):
33+
# 当前值的大小与前面的值之和比较，若当前值更大，则取当前值，舍弃前面的值之和
34+
subMaxSum = max(nums[i] + nums[i - 1], nums[i])
35+
nums[i] = subMaxSum # 将当前和最大的赋给nums[i]，新的nums存储的为和值
36+
return max(nums)
37+
38+
39+
if __name__ == "__main__":
40+
assert Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
41+

‎Python3/053_Maximum_Subarray_Method3.py

Copy file name to clipboard
+66Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
5+
6+
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
7+
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
8+
'''
9+
# 思路三：
10+
#
11+
# 分治递归
12+
# 算法过程：
13+
# 分治法，最大子序和要么在左半部分，要么在右半部分，要么就横跨两部分（即包括左半部分的最后一个元素，和右半部分的第一个元素）
14+
# 。返回这三种情况的最大值即可。第三种情况，其中包括左半部分最后一个元素的情形，需要挨个往前遍历，更新最大值。包含右半部分的
15+
# 第一个元素的情况类似。总的时间复杂度O(nlogn)
16+
17+
# 算法证明：
18+
# 总的来说还是超级巧妙的。不断的切不断的切数组，把一块数组看成左中右三个部分。实际上这有点像枚举，但我们在枚举时利用了二分
19+
# 的思路，优化了很多。所以枚举当然可以达到我们的目标了，因为我们不断在计算以一定包括中间节点的子序的最大和。
20+
21+
22+
class Solution(object):
23+
def maxSubArray(self, nums):
24+
# 主函数
25+
left = 0
26+
# 左右边界
27+
right = len(nums) - 1
28+
# 求最大和
29+
maxSum = self.divide(nums, left, right)
30+
return maxSum
31+
32+
def divide(self, nums, left, right):
33+
# 如果只有一个元素就返回
34+
if left == right:
35+
return nums[left]
36+
# 确立中心点
37+
center = (left + right) // 2
38+
# 求子序在中心点左边的和
39+
leftMaxSum = self.divide(nums, left, center)
40+
# 求子序在中心点右边的和
41+
rightMaxSum = self.divide(nums, center + 1, right)
42+
43+
# 求子序横跨2边的和，分成左边界和和右边界和
44+
leftBorderSum = nums[center]
45+
leftSum = nums[center]
46+
for i in range(center - 1, left - 1, -1):
47+
leftSum += nums[i]
48+
if leftSum > leftBorderSum:
49+
# 不断更新左区块的最大值
50+
leftBorderSum = leftSum
51+
52+
rightBorderSum = nums[center + 1]
53+
rightSum = nums[center + 1]
54+
for i in range(center + 2, right + 1):
55+
rightSum += nums[i]
56+
if rightSum > rightBorderSum:
57+
# 不断更新右区块的最大值
58+
rightBorderSum = rightSum
59+
# 左边界的和 + 右边那块的和
60+
BorderSum = leftBorderSum + rightBorderSum
61+
return max(leftMaxSum, rightMaxSum, BorderSum)
62+
63+
64+
if __name__ == "__main__":
65+
assert Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
66+

‎Python3/066_Plus_One.py

Copy file name to clipboard
+32Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Given a non-negative number represented as an array of digits, plus one to the number.
5+
6+
The digits are stored such that the most significant digit is at the head of the list.
7+
'''
8+
9+
10+
class Solution(object):
11+
def plusOne(self, digits):
12+
"""
13+
:type digits: List[int]
14+
:rtype: List[int]
15+
"""
16+
carry = 1
17+
for i in range(len(digits)-1, -1, -1):
18+
digits[i] += carry
19+
if digits[i] < 10:
20+
carry = 0
21+
break
22+
else:
23+
digits[i] -= 10
24+
if carry == 1:
25+
digits.insert(0,1)
26+
return digits
27+
28+
29+
if __name__ == "__main__":
30+
assert Solution().plusOne([1, 2, 3, 4, 9]) == [1, 2, 3, 5, 0]
31+
assert Solution().plusOne([9]) == [1, 0]
32+

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.