# Python3刷题系列（三）

1，leetcode-69：Sqrt(x) （x 的平方根）

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

2，leetcode-167：双指针

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]

3，leetcode-215：练习排序方法：快排、堆排

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

# 快排：时间复杂度-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

4，leetcode-347：桶排序

class Solution:
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.item():
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-75：三向切分快排

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

# 三向切分快速排序思想：
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

6，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

0 条评论

• ### c# 利用AForge.NET组件操作摄像头

private FilterInfoCollection videoDevices;

• ### 001.LVS简介及算法

LVS是linux virtual server的简写linux虚拟服务器，是一个虚拟的服务器集群系统，可以再unix/linux平台下实现负载均衡集群功能。

• ### JSONObject put,accumulate,element的区别

public Object put (Object key, Object value) 将value映射到key下。如果此JSONObject对象之前存在一个...

• ### jQuery 下拉查询筛选插件Combo Select

插件描述：Combo Select 是一款友好的 jQuery 下拉框插件，在 PC 浏览器上它能模拟一个简单漂亮的下拉框，在 iPad 等移动设备上又能回退到...

• ### linux应用之wget命令详解

wget是linux最常用的下载命令, 一般的使用方法是: wget + 空格 + 要下载文件的url路径

• ### Json（Json-lib）中使用JSONObject.toBean(JSONObject jsonObject, Class beanClass)日期保存了当前时间

1、问题：使用Json-lib，转换数据的方法JSONObject.toBean(JSONObject jsonObject, Class beanClass)...

• ### 【ionic+angularjs】angularjs ui-router路由简介（\$urlRouter、\$state、\$stateProvider、ui-sref....）

之前有写过一篇关于Angular自带的路由：ngRoute。今天来说说Angular的第三方路由：ui-router。那么有人就会问:为什么Ang...

• ### JSONObject.fromObject 转换JSON字符串Map及javabean时间处理的问题

这几天的项目开发过程中遇到一个比较棘手的问题，主要是通用导出类中，使用了一个javabean转换成json字符串的问题，javabean中一个日期格式是“yyy...