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 = Noneclass 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