Quicksort
class Sort:
def quickSort(self, arr):
self.quicksort_helper(arr, 0, len(arr)-1)
return arr
def quicksort_helper(self, arr, left, right):
if left < right:
pivot_final_resting_position = self.partition(arr, left, right)
self.quicksort_helper(arr, left, pivot_final_resting_position-1)
self.quicksort_helper(arr, pivot_final_resting_position+1, right)
def partition(self, arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
self.swap(arr, i, j)
self.swap(arr, i+1, right)
return i+1
def swap(self, arr, first, second):
temp = arr[first]
arr[first] = arr[second]
arr[second] = tempBubble Sort
class Sort:
def bubbleSort(self, nums):
for i in range(len(nums)-1, 0, -1):
for j in range(i):
if nums[j] > nums[i]:
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
return numsMerge Sort
class Sort:
def merge(self, left, right):
result = []
while len(left)>0 and len(right)>0:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result.extend(left)
if right:
result.extend(right)
return result
def mergeSort(self, arr):
num = len(arr)
if num < 2:
return arr
middle = num // 2
left = arr[:middle]
right = arr[middle:]
left_sort = mergeSort(left)
right_sort = mergeSort(right)
return self.merge(left_sort, right_sort)反转链表
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回 ListNode
def ReverseList(self, pHead):
# write code here
current = pHead
previous = None
while current:
temp = current.next
current.next = previous
previous = current
current = temp
return previous
判断链表是否有环
用 current.next 遍历，但凡遍历过的 node 都丢入 head 这一地址，若遍历过程中中 next 有 ==head 的，阐明肯定连贯到先前 node，阐明肯定有环。
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
#
# @param head ListNode 类
# @return bool 布尔型
#
class Solution:
def hasCycle(self , head):
# write code here
current = head
while current:
after = current.next
if after == head:
return True
current.next = head
current = after
return False查看括号
#
#
# @param s string 字符串
# @return bool 布尔型
#
class Solution:
def isValid(self , s):
# write code here
length = len(s)
if length % 2 != 0:
return False
my_dict = {"]":"[",
"}":"{",
")":"("}
my_list = []
for i in s:
if i not in my_dict:
my_list.append(i)
if i in my_dict:
if len(my_list) == 0:
return False
correct = my_dict[i]
pop = my_list.pop()
if correct != pop:
return False
if len(my_list) > 0:
return False
return True
股票，数组中的 max(后 - 前)
动静布局
#
#
# @param prices int 整型一维数组
# @return int 整型
#
class Solution:
def maxProfit(self , prices):
# write code here
profit = 0
min_start = prices[0]
for i in range(1,len(prices)):
if prices[i] < min_start:
min_start = prices[i]
profit = max(profit, prices[i]-min_start)
return profit
二分搜寻
#
# 代码中的类名、办法名、参数名曾经指定，请勿批改，间接返回办法规定的值即可
#
# 如果目标值存在返回下标，否则返回 -1
# @param nums int 整型一维数组
# @param target int 整型
# @return int 整型
#
class Solution:
def search(self , nums , target):
# write code here
low = 0
high = len(nums) - 1
while (low<=high):
middle = low + (high-low)//2
if nums[middle] == target:
while(middle>0 and nums[middle-1] == nums[middle]):
middle-=1
return middle
elif nums[middle]>target:
high = middle - 1
else:
low = middle+1
return -1镜像二叉树
递归
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、办法名、参数名曾经指定，请勿批改，间接返回办法规定的值即可
#
#
# @param pRoot TreeNode 类
# @return TreeNode 类
#
class Solution:
def Mirror(self , pRoot):
# write code here
if pRoot == None:
return pRoot
temp = pRoot.left
pRoot.left = pRoot.right
pRoot.right = temp
self.Mirror(pRoot.left)
self.Mirror(pRoot.right)
return pRoot最长无反复子串
#
#
# @param arr int 整型一维数组 the array
# @return int 整型
#
class Solution:
def maxLength(self , arr):
# write code here
my_dict = {}
max_len = 0
length = 0
start_ptr = 0
arr_len = len(arr)
if arr_len<=1:
return arr_len
for i in range(arr_len):
if arr[i] not in my_dict:
my_dict[arr[i]] = i
length += 1
else:
re_pos = my_dict[arr[i]]
max_len = max(max_len,length)
next_pos = re_pos+1
for j in range(start_ptr, next_pos):
my_dict.pop(arr[j])
my_dict[arr[i]] = i
start_ptr = next_pos
length = i-re_pos
max_len = max(length, max_len)
return max_len
缺失数字
依据题目意思，肯定从 0 开始，则用 sum 和 -index 和，若后果为零，list 的最初一个元素 +1；若后果不为零，list 的最初一个元素 - 后果
#
# 找缺失数字
# @param a int 整型一维数组 给定的数字串
# @return int 整型
#
class Solution:
def solve(self , a):
length = len(a)
sum1 = (0+len(a)-1)*length/2
sum2 = 0
for i in a:
sum2 = sum2+i
result = sum2-sum1
if result == 0:
return a[-1]+1
return (a[-1]-result)Three Sum 找出所有不反复的和为零的三元数组
快排
排完后造成有序数组，左小右大，右边肯定为正数开始【否则不可能和为 0】
间接排除：小于三个元素，sort 后第一个元素大于 0
基准从左开始，在正数范畴中搜寻
双指针，左指针指向基准后一个数，右指针指向最右数。若相加和 <0，阐明过负，左指针向右挪动；若相加和 >0，阐明过正，右指针向左挪动
如何确保不反复：建设 duplicate_list，将有序的和为零的三元组转为 string，每次 append 时先比拟是否 in duplicate_list 中
#
#
# @param num int 整型一维数组
# @return int 整型二维数组
#
class Solution:
def threeSum(self , num):
# write code here
num = self.quickSort(num)
length = len(num)
if length < 3 or num[0]>0:
return []
i = 0
dup = []
my_result = []
while i<length:
left = i+1
right = length-1
while (left<right):
result = num[i]+num[left]+num[right]
if result == 0:
string = str(num[i])+str(num[left])+str(num[right])
if (string not in dup):
dup.append(string)
my_result.append([num[i],num[left],num[right]])
left += 1
right -= 1
if (result<0):
left += 1
if (result>0):
right -= 1
i += 1
return my_result
def quickSort(self, arr):
self.quicksort_helper(arr, 0, len(arr)-1)
return arr
def quicksort_helper(self, arr, left, right):
if left < right:
pivot_pos = self.partition(arr, left, right)
self.quicksort_helper(arr, left, pivot_pos-1)
self.quicksort_helper(arr, pivot_pos+1, right)
def swap(self, arr, first, second):
temp = arr[first]
arr[first] = arr[second]
arr[second] = temp
def partition(self, arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
self.swap(arr, i, j)
self.swap(arr, i+1, right)
return i+1