Algorithm

Record the learning algorithm experience.

reference

  1. 背包问题

Math

Reverse Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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