关于leetcode:LeetCode乱序-个人做题记录

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] = temp

Bubble 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 nums

Merge 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