LeetCode out-of-order | personal record. To solve the problem

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
Copy the code

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
Copy the code

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)
Copy the code

Reverse a linked list

# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
    # returns 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
Copy the code

Check whether the list has rings

If next has ==head, it must be connected to the previous node, indicating that there must be a loop.

# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

#
# 
# @param head ListNode class
# @return bool 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
Copy the code

Check the brackets

#
# 
# @param s string String
# @return bool 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()
                ifcorrect ! = pop:return False
        if len(my_list) > 0:
            return False
            
        return True
                
Copy the code

Stock, Max in array (back – front)

Dynamic programming

#
# 
# @param prices int One dimensional array of integers
# @return int Specifies an integer
#
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
        
Copy the code

Binary search

#
The class name, method name, and parameter name have been specified, do not modify, directly return method specified value can be
#
If the target value exists, -1 is returned otherwise
# @param nums int One-dimensional array of integers
# @param target int Specifies an integer
# @return int Specifies an integer
#
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
Copy the code

Mirrored binary tree

recursive

# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
The class name, method name, and parameter name have been specified, do not modify, directly return method specified value can be
#
# 
# param pRoot TreeNode class
# @ return TreeNode class
#
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
Copy the code

Longest non-repeating substring

#
# 
# @param arr int The array
# @return int Specifies an integer
#
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
        
Copy the code

The missing number

If sum is zero, the last element in the list +1; if sum is zero, the last element in the list +1. If the result is not zero, the last element of the list – the result

#
# Find missing numbers
# @param a int Specifies a string of numbers in a one-dimensional array
# @return int Specifies an integer
#
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)
Copy the code

Three Sum finds all non-repeating triples that Sum to zero

If the first element is greater than 0, start from the left. If the first element is greater than 0, start from the left. If the first element is greater than 0, start from the left. If the sum is <0, it is too negative and the left pointer moves to the right. Duplicate_list = 0; duplicate_list = 0; duplicate_list = 0; duplicate_list = 0; duplicate_list = 0; duplicate_list = 0

#
# 
# @param num int One-dimensional array of integers
# @return int Two-dimensional array of integers
#
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
Copy the code