# Python3刷题系列（七）

1，Leetcode-241

2，Leetcode-69

3，Leetcode-1

4，Leetcode-347

5，Leetcode-455

6，Leetcode-215

7，Leetcode-75

8，Leetcode-167

1，Leetcode-241：

```# leetcode-241:分治思想
class Solution:  # 使用递归实现分治思想，战胜了 63.59%
def diffWaysToCompute(self, input: str) -> List[int]:
return_list = []
for i in range(len(input)):
c = input[i]
if c in ['+','-','*']:
left = self.diffWaysToCompute(input[:i])
right = self.diffWaysToCompute(input[i+1:])
for l in left:
for r in right:
if c == '+':
return_list.append(l+r)
elif c == '-':
return_list.append(l-r)
elif c == '*':
return_list.append(l*r)
if not return_list:
return_list.append(int(input))  # return_list为空时，显然input只有一个整数

return return_list```

2，Leetcode-69：

https://leetcode.com/problems/sqrtx/

```# leetcode-69: 二分查找, O(lgn), 战胜了 84.44%
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0

l = 1
r = x

while l <= x:
res = (l + r) // 2
s = res ** 2

if s <= x < (res + 1)**2:
return res
if s < x:
l = res
if s > x:
r = res

class Solution(object):  # 同样是二分查找，这种写法超时
def mySqrt(self, x):
if x <= 1:
return x  # 考虑到0,1的情况
l = 0
h = x
while l <= h:
m = l + (h - 1) / 2  # 中值：防止溢出，等于（l + h） / 2,后者容易溢出
if x > m**2:
l = m+1
elif x < m**2:
h = m-1
elif x == m**2:
return int(m)
return int(h)```

3，Leetcode-1：

https://leetcode.com/problems/two-sum/

```# keetcode-1：哈希表
class Solution:   # 战胜了87.27%
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {}
for i in range(len(nums)):
if nums[i] in dict:
return [dict[nums[i]], i]
dict[target - nums[i]] = i

# 和上面阶梯思想一致，细节不同而已
class Solution:   # 战胜了87.27%
def twoSum(self, nums: List[int], target: int) -> List[int]:
my_dict = {}
for i in range(len(nums)):
if target - nums[i] in my_dict:
return [my_dict[target - nums[i]], i]
my_dict[nums[i]] = i```

4，Leetcode-347：

https://leetcode.com/problems/top-k-frequent-elements/

```# leetcode-347：桶排序
class Solution:  # 战胜了32.06%
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
di = {}
for num in nums:
if num not in di:
di[num] = 1
else:
di[num] += 1
bucket = [[] for _ in range(len(nums) + 1)]
for key, value in di.items():
bucket[value].append(key)
ans = []
for i in range(len(nums), -1, -1):
if bucket[i]:
ans.extend(bucket[i])
if len(ans) >= k:
break
return ans[:k]

class Solution:  # 战胜了24.62%
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
frequent_of_number = {}
for num in nums:
frequent_of_number[num] = frequent_of_number.get(num, 0) + 1
buckets = [[] for i in range(len(nums) + 1)]
for key, value in frequent_of_number.items():
buckets[value].append(key)
print(buckets)
result = []
for x in range(len(nums), -1, -1):
if k > 0 and buckets[x]:
result += buckets[x]
k -= len(buckets[x])
if k == 0:
return result```

5，Leetcode-455：

```# leetcode-455：贪心算法
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g = sorted(g)
s = sorted(s)
cnt_g = 0
cnt_s = 0
while cnt_g < len(g) and cnt_s < len(s):
if g[cnt_g] <= s[cnt_s]:
cnt_g += 1
cnt_s += 1
return cnt_g

class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
child = 0

while len(g) > child and len(s) > cookies:
child += 1
return child```

6，Leetcode-215：

https://leetcode.com/problems/kth-largest-element-in-an-array/

```# leetcode-215：快排：时间复杂度-O(N), 空间复杂度-O(1).
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return self.quick_sort(nums, k)

def quick_sort(self, nums, k):
k = len(nums) -k
left = 0
right = len(nums) - 1
while left < right:
j = self.partition(nums, left, right)
if j == k:
break
elif j < k:
left = j + 1
else:
right = j -1
return nums[k]

def partition(self, nums, left, right):
while True:
while nums[left] < nums[right]:
right -= 1
else:
nums[left], nums[right] = nums[right], nums[left]
if left >= right:
break
left += 1

while nums[left] < nums[right]:
left += 1
else:
nums[left], nums[right] = nums[right], nums[left]
if left >= right:
break
right -= 1
return left

# 堆排：时间复杂度-O(NlogK), 空间复杂度-O(K).
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return self.heap_sort(nums, k)

def heap_sort(self, nums, k):
for i in range(len(nums)//2 - 1, -1, -1):

cnt = 0
for i in range(len(nums) - 1, 0, -1):
self.heap_swap(nums, 0, i)
cnt += 1
if cnt == k:
return nums[i]
return nums[0]

tmp = nums[start]
k = start * 2 + 1
while k < length:
left = start * 2 + 1
right = left + 1

if right < length and nums[right] > nums[left]:
k = right

if nums[k] > tmp:
nums[start] = nums[k]
start = k
else:
break
k = k*2 + 1
nums[start] = tmp

def heap_swap(self, nums, i, j):
nums[i], nums[j] = nums[j], nums[i]
return nums

# 递归解法：
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if len(nums) == 0:
return
nums = self.quicksort(nums)
return nums[-k]

def quicksort(self, nums):
if len(nums) == 0:
return []
pivot = nums[0]
left = self.quicksort([x for x in nums[1:] if x < pivot])
right = self.quicksort([x for x in nums[1:] if x >= pivot])
return left + [pivot] + right

# 暴力解法：
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums)[-k]```

7，Leetcode-75：

https://leetcode.com/problems/sort-colors/

```# 三向切分快速排序思想：
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
head, now, tail = 0, 0, len(nums) - 1
while now <= tail:
if nums[now] == 0:
now += 1
elif nums[now] == 2:
nums[now], nums[tail] = nums[tail], nums[now]
tail -= 1
else:
now += 1

class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
zero, two = -1, len(nums)
i = 0
while i < two:
if nums[i] == 1:
i += 1
elif nums[i] == 2:
two -= 1
nums[two], nums[i] = nums[i], nums[two]
else:
zero += 1
nums[zero], nums[i] = nums[i], nums[zero]
i += 1

# 暴力解法：
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort()```

8，Leetcode-167：

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

```# 双指针：
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] > target:
j -= 1
elif numbers[i] + numbers[j] < target:
i += 1
else:
return [i+1, j+1]

class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
a = 0
b = len(numbers) -1

while a < b:
if numbers[a] + numbers[b] < target:
a += 1
elif numbers[a] + numbers[b] > target:
b -= 1
elif numbers[a] + numbers[b] == target:
return [a+1, b+1]
else:
return None

class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
for i in range(0, length-1):
for j in range(i+1, length):
a = numbers[i]
b = numbers[j]
sum = a +b
if sum == target:
break
if sum == target:
break
return i+1, j+1```

0 条评论

## 相关文章

30830

6710

24320

16160

### 002.NFS相关配置项

<输出目录> [客户端1 选项（访问权限,用户映射,其他）] [客户端2 选项（访问权限,用户映射,其他）]

7420

17720

13730

8220

### 002.DNS-BIND简介

Bind是Berkeley Internet Name Domain Service的简写，它是一款实现DNS服务器的开放源码软件。已经成为世界上使用最为广泛的...

12830

8530