Algorithm

Record the learning algorithm experience.

reference

1. 背包问题

Math

Reverse Integer

func reverse(x int) int {
    //math.MinInt32 = -2147483648
    //math.MaxInt32 = 2147483647
    var result int
    for x!=0{
        result=result*10+x%10
        if result > 2147483647  || result < -2147483648{
            return 0
        }
        x/=10
    }
    return result
}

Evolving Difficulty

# brute force O(n2)
import time

test = int(input())

for _ in range(test):
    n = int(input())
    a = [int(i) for i in input().split()]
    begin = time.time()
    result = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            result += (a[i]*a[j]*sum(a[j+1:]))

    end = time.time()
    print(result)
    print("time is {}".format(end - begin))

# -------------------
1
8
1 2 3 4 5 6 7 8
4536
time is 3.0994415283203125e-05

# arithmetic O(n)
import time 

test = int(input())

for _ in range(test):
    n = int(input())
    a = [int(i) for i in input().split()]
    begin = time.time()
    result = 0
    sumai = a[0] + a[1]
    sumai2 = a[0]**2 + a[1]**2

    for k in range(2,n):
        aiaj = (sumai**2 - sumai2) // 2
        result += aiaj*a[k]
        sumai += a[k]
        sumai2 += a[k]**2
    end = time.time()
    print(result)
    print("time is {}".format(end - begin))

# --------------------
1
8
1 2 3 4 5 6 7 8
4536
time is 2.1219253540039062e-05

quickSort

Based on recursive

package main

import "fmt"

func quickSort(arr []int, startIndex, endIndex int )  {

	if startIndex >= endIndex {
		return
	}
	pivotIndex:= partition(arr,startIndex,endIndex)
	quickSort(arr,startIndex,pivotIndex-1)
	quickSort(arr,pivotIndex+1,endIndex)
}

func partition(arr []int, startIndex, endIndex int )  int {

	pivot:=arr[startIndex]
	mark:=startIndex

	for i:=startIndex+1; i<= endIndex; i++{
		if arr[i]<pivot {
			mark++    //  numbers that smaller pivot ++
			arr[i],arr[mark] = arr[mark], arr[i]
		}
	}
	arr[startIndex] = arr [mark]
	arr[mark] = pivot
	return mark
}

func main() {

	var arr = []int{4,4,6,5,3,2,8,1}
	quickSort(arr,0, len(arr)-1)
	fmt.Print(arr)
}

Use stack

package main

import "fmt"
import "github.com/golang-collections/collections/stack"

func quickSort(arr []int, startIndex, endIndex int )  {

	quickSortStack := stack.New()
	rootParam := make(map[string]int)
	rootParam["startIndex"] = startIndex
	rootParam["endIndex"] = endIndex
	quickSortStack.Push(rootParam)

	for quickSortStack.Len() > 0 {

		param := quickSortStack.Pop().(map[string]int)
		pivotIndex := partition(arr, param["startIndex"], param["endIndex"] )

		if param["startIndex"] < pivotIndex-1 {
			leftParam := make(map[string]int)
			leftParam["startIndex"] = param["startIndex"]
			leftParam["endIndex"] = pivotIndex-1
			quickSortStack.Push(leftParam)
		}
		if pivotIndex+1 < param["endIndex"] {

			rightParam := make(map[string]int)
			rightParam["startIndex"] = pivotIndex+1
			rightParam["endIndex"] = param["endIndex"]
			quickSortStack.Push(rightParam)
		}
	}
}

func partition(arr []int, startIndex, endIndex int )  int {

	pivot:=arr[startIndex]
	mark:=startIndex

	for i:=startIndex+1; i<= endIndex; i++{
		if arr[i]<pivot {
			mark++    //  smaller pivot numbers ++
			arr[i],arr[mark] = arr[mark], arr[i]
		}
	}
	arr[startIndex] = arr [mark]
	arr[mark] = pivot
	return mark
}

func main() {

	var arr = []int{4,4,6,5,3,2,8,1}
	quickSort(arr,0, len(arr)-1)
	fmt.Print(arr)
}

Hash Table

Two Sum

func twoSum(nums []int, target int) []int {
    
    dic := make(map[int]int)
    for i, v := range nums {
        
        k,ok := dic[target-v]
        
        if ok {
            return []int{k, i}
        }
        dic[v]=i     
    }
    return nil  
}

least recently used

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# leetcode 146

class DoubleNode(object):
    def __init__(self, key, val, pre=None, next=None):
        self.key = key
        self.val = val
        self.pre = pre
        self.next = next


class LRUCache:
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._index = {}
        self._head = DoubleNode(-1, -1, None, None)
        
        cur = self._head
        for i in range(1, capacity):
            cur.next = DoubleNode(-1, -1, cur)
            cur = cur.next
        cur.next = self._head
        self._head.pre = cur
        
        
    def move_to_head(self, cur):
        if cur == self._head:
            self._head = self._head.pre
            return
        
        cur.pre.next = cur.next
        cur.next.pre = cur.pre
        # attach to head pointer
        cur.next = self._head.next
        cur.next.pre = cur
        self._head.next = cur
        cur.pre = self._head
        return
        
        
    def get(self, key: int) -> int:
        cur = self._index.get(key, None)
        if not cur:
            return -1
        else:
            self.move_to_head(cur)
            return cur.val


    def put(self, key: int, value: int) -> None:
        if self._index.get(key, None):
            cur = self._index[key]
            cur.val = value
            self.move_to_head(cur)
        else:
            if self._head.val != -1:
                del(self._index[self._head.key])
            
            self. _head.key = key
            self._head.val = value
            self._index[key] = self._head
            self._head = self._head.pre

Leetcode

Longest Palindromic Substring

# leetcode 5  Longest Palindromic Substring

class Solution:
    def _expand(self, s: str, left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right] :
            left -= 1
            right += 1
        
        return right - left - 1
    
    def longestPalindrome(self, s: str) -> str:
        if  s is None or len(s) == 0:
            return ""
        
        start = 0
        maxLen = 0
        for i in range(len(s)):
            len1 = self._expand(s, i, i)
            len2 = self._expand(s, i, i+1)
            length = max(len1, len2)
            if length > maxLen:
                start = i - (length-1)//2
                maxLen = length
            
        return s[start:start+maxLen]

Palindrome Linked List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        length = 0
        p = head
        while p != None:
            length += 1
            p = p.next
        
        # get length of link
        
        cur = head
        pre = None
        for i in range(length//2):
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        
        # even need goback 1 seat
        if length % 2 == 1:
            cur = cur.next
        
        while pre != None and cur != None:
            if pre.val != cur.val:
                return False
            
            pre = pre.next
            cur = cur.next
        
        return True

Median of Two Sorted Arrays

class Solution:
    # 分奇 偶情况来找到第 K 小的数字
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total = len(nums1) + len(nums2)
        if total & 1 == 1: # 按位与来判断奇偶性
            return self.find(nums1, nums2, total//2 + 1)
        else:
            a = self.find(nums1, nums2, total//2)
            b = self.find(nums1, nums2, total//2 + 1)
            return (a+b) / 2
        
    
    def find(self, nums1: List[int], nums2: List[int], k: int) -> float:
        len1 = len(nums1)
        len2 = len(nums2)
        base1 = 0 # 用 base 来增加偏移量，避免重复创建新的数组，节约空间
        base2 = 0
        
        while True:
            if len1 == 0: return nums2[base2 + k - 1]
            if len2 == 0: return nums1[base1 + k - 1]
            if k == 1: return min(nums1[base1], nums2[base2])
            
            i = min(k//2, len1)
            j = min(k-i, len2)
            a = nums1[base1 + i - 1]
            b = nums2[base2 + j - 1]
            
            if i+j == k and a == b: return a

# 这里 a == b 判断了两次，是因为 i+j<k, 第 k 小的数不在这两个部分，都可以排除
            if a <=b:
                base1 += i
                len1 -= i
                k -= i
            if a >= b:
                base2 += j
                len2 -= j
                k -= j
                

Longest Substring Without Repeating Characters

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int abcabcbb
        """
        if len(s) == 0:
            return 0
        seen = {}
        left, right = 0, 0
        longest = 1
        while right < len(s):
            if s[right] in seen:
                left = max(left,seen[s[right]]+1)
            longest = max(longest, right - left + 1)
            seen[s[right]] = right
            right += 1

        return longest

Regular Expression Matching