- 设原始数据规模为n，需要采样的数量为k
- 先选取数据流中的前k个元素，保存在集合A中；
- 从第j（k + 1 <= j <= n）个元素开始，每次先以概率p = k/j选择是否让第j个元素留下。若j被选中，则从A中随机选择一个元素并用该元素j替换它；否则直接淘汰该元素；
- 重复步骤3直到结束，最后集合A中剩下的就是保证随机抽取的k个元素。
算法
-
[1,2,3,4,5,6,7,8,9] 输出 [64,36,16,4]，逆序输出偶数的平方（Reverse String） 344 2
func reverseArray(s[] byte){ lastIndex := len(s) - 1 for i:=0; i<len(s); i++{ if s[i] % 2 != 0{ s = append(a[:i], a[i+1:]...) } } for i:=0; i<len(s)/2; i++{ tmp := s[lastIndex - i] s[lastIndex - i] = s[i] s[i] = tmp } } -
层序遍历二叉树（Binary Tree Level Order Traversal）102
func levelOrderDFS(root *TreeNode) [][]int { result := [][] int{} levelOrderHelper(root, 0, &result) return result } func levelOrderHelper(node *TreeNode, level int, result *[][]int) { if node == nil { return } if level == len(*result) { *result = append(*result, []int{}) } (*result)[level] = append((*result)[level], node.Val) levelOrderHelper(node.Left, level+1, result) levelOrderHelper(node.Right, level+1, result) } -
链表求和（Add Two Numbers）2
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { carry := 0 head := new(ListNode) cur := head for l1 != nil || l2 != nil || carry != 0 { n1, n2 := 0, 0 if l1 != nil { n1, l1 = l1.Val, l1.Next } if l2 != nil { n2, l2 = l2.Val, l2.Next } num := n1 + n2 + carry carry = num / 10 cur.Next = &ListNode{Val: num % 10, Next: nil} cur = cur.Next } return head.Next } -
给定一个 0-4 随机数生成器生成 0-6 随机数（Implement Rand10() Using Rand7()）470 2
func rand10() int { index := int(^uint(0) >> 1) for index >= 40 { index = 7 * (rand7() - 1) + (rand7() - 1) } return index % 10 + 1 } -
二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）236 2
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil || root == p || root == q { return root } left := lowestCommonAncestor(root.Left, p, q) right := lowestCommonAncestor(root.Right, p, q) if left != nil && right != nil { return root } if left != nil { return left } return right } -
二叉树最大路径和（Binary Tree Maximum Path Sum）124 2
func maxPathSum(root *TreeNode) int { maxSum := math.MinInt32 maxPathSumHelper(root, &maxSum) return maxSum } func maxPathSumHelper(node *TreeNode, maxSum *int) int { if node == nil { return 0 } left, right := maxPathSumHelper(node.Left, maxSum), maxPathSumHelper(node.Right, maxSum) maxSumEndingAtNode := max(node.Val, node.Val + max(left, right)) *maxSum = max(*maxSum, max(node.Val + left + right, maxSumEndingAtNode)) return maxSumEndingAtNode } func max(x, y int) int { if x > y { return x }; return y } -
链表转二叉树（Convert Sorted List to Binary Search Tree）109
func sortedListToBST(head *ListNode) *TreeNode { return helper(head, nil) } func helper(head *ListNode, end *ListNode)*TreeNode{ if head == end{ return nil } if head.Next == end{ return &TreeNode{Val: head.Val} } mid := findMid(head, end) return &TreeNode{ Val: mid.Val, Left: helper(head, mid), Right: helper(mid.Next, end), } } func findMid(head *ListNode, end *ListNode) *ListNode{ fast := head slow := head for fast != end && fast.Next != end{ fast = fast.Next.Next slow = slow.Next } return slow } -
二叉树删除节点（Delete Node in a BST）450
func FindMin(root *TreeNode) *TreeNode{ for root.Left != nil{ root = root.Left } return root } func deleteNode(root *TreeNode, key int) *TreeNode { if root == nil{ return nil } if key < root.Val{ root.Left = deleteNode(root.Left, key) } else if key > root.Val{ root.Right = deleteNode(root.Right, key) } else{ if root.Right == nil{ return root.Left } else if root.Left == nil{ return root.Right } minNode:= FindMin(root.Right) root.Val = minNode.Val root.Right = deleteNode(root.Right, minNode.Val) } return root } -
奇偶链表（Odd Even Linked List）328
func oddEvenList(head *ListNode) *ListNode { if head == nil { return head } odd := head even := head.Next evenHead := even for even != nil && even.Next != nil { odd.Next = odd.Next.Next even.Next = even.Next.Next odd = odd.Next even = even.Next } odd.Next = evenHead return head }单向链表，奇数位是升序，偶数位是降序，重新排列是降序，时间复杂度O(n)，空间复杂度O(1)。
-
反转链表（Reverse Linked List）206 3
func reverseList(head *ListNode) *ListNode { var prev *ListNode for head != nil { head.Next, prev, head = prev, head, head.Next } return prev } -
合并两个有序链表（Merge Two Sorted Lists）21
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { var dummy ListNode tail := &dummy for l1 != nil && l2 != nil { if l1.Val < l2.Val { tail.Next = l1 l1 = l1.Next } else { tail.Next = l2 l2 = l2.Next } tail = tail.Next } if l1 != nil { tail.Next = l1 } if l2 != nil { tail.Next = l2 } return dummy.Next } -
组成N位的数字去掉K位保证数字最小（Remove K Digits）402
func removeKdigits(num string, k int) string { stack := make([]byte, 0) for i := range num { for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] { k-- stack = stack[:len(stack)-1] } stack = append(stack, num[i]) } stack = stack[:len(stack)-k] // Calculate leading zeros var zeros int for i := range stack { if stack[i] != '0' { break } zeros++ } if len(stack) == 0 || zeros == len(stack) { return "0" } return string(stack[zeros:]) } -
下一个更大元素(单调栈)（Next Greater Element II）503
type node struct { index int value int } func nextGreaterElements(nums []int) []int { length := len(nums) nums = append(nums, nums...) var stack []node for i := 0; i < len(nums); i++ { for len(stack) > 0 && stack[len(stack)-1].value < nums[i] { node := stack[len(stack)-1] stack = stack[:len(stack)-1] nums[node.index] = nums[i] } stack = append(stack, node{i, nums[i]}) nums[i] = -1 } return nums[:length] } -
链表环（Linked List Cycle）142 3
func detectCycle(head *ListNode) *ListNode { if head == nil || head.Next == nil { return nil } fast := head slow := head cycle := false for fast.Next != nil && fast.Next.Next != nil { fast = fast.Next.Next slow = slow.Next if fast == slow { cycle = true break } } if !cycle { return nil } for head != slow { head = head.Next slow = slow.Next } return head } -
相交链表（Intersection of Two Linked Lists ）160 3
func getIntersectionNode(headA, headB *ListNode) *ListNode { n1, n2 := headA, headB if headA == nil || headB == nil { return nil } for n1 != n2 { if n1 != nil { n1 = n1.Next } else { n1 = headB } if n2 != nil { n2 = n2.Next } else { n2 = headA } } return n1 } -
二叉树非递归后序遍历（Binary Tree Postorder Traversal ）145
func postorderTraversal(root *TreeNode) []int { if root == nil { return []int{} } traversal := make([]int, 0) stack := make([]*TreeNode, 0) current := root for current != nil || len(stack) > 0 { for current != nil { traversal = append(traversal, current.Val) stack = append(stack, current) current = current.Right } current = stack[len(stack)-1] stack = stack[:len(stack)-1] current = current.Left } reverse(traversal) return traversal } func reverse(nums []int) { for i := 0; i < len(nums)/2; i++ { nums[i], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[i] } } -
LRU Cache（146） 2
func Constructor(capacity int) LRUCache { m := make(map[int]*CacheNode) c := LRUCache{Cap: capacity, Map: m} return c } func (this *LRUCache) Get(key int) int { found, ok := this.Map[key] if !ok { return -1 } if this.Head == found { return found.Val } if this.Tail == found { this.Tail = found.Prev } if found.Next != nil { found.Next.Prev = found.Prev } if found.Prev != nil { found.Prev.Next = found.Next } this.Head.Prev, found.Next = found, this.Head return found.Val } func (this *LRUCache) Put(key int, value int) { found, ok := this.Map[key] if ok { found.Val = value _ = this.Get(found.Key) return } n := &CacheNode{Key: key, Val: value} if len(this.Map) == 0 { this.Tail = n } else { this.Head.Prev, n.Next = n, this.Head } this.Map[key], this.Head = n, n if this.Cap == this.Len { delete(this.Map, this.Tail.Key) this.Len, this.Tail = this.Len+1, this.Tail.Prev } this.Len++ } type LRUCache struct { Cap int Len int Head *CacheNode Tail *CacheNode Map map[int]*CacheNode } type CacheNode struct { Next *CacheNode Prev *CacheNode Key int Val int } -
Design HashMap（706） 5
type MyHashMap struct { val [1010]list } type list struct { values []node } type node struct { key int value int } func Constructor() MyHashMap { return MyHashMap{val: [1010]list{}} } func (this *MyHashMap) Put(key int, value int) { r := key % 1009 // 如果存在 l := this.val[r].values for i := 0; i < len(l); i++ { if l[i].key == key { l[i].value = value // 如果存在就修改值 return } } this.val[r].values = append(l, node{key: key, value: value}) // 如果不存在加在末尾 } func (this *MyHashMap) Get(key int) int { r := key % 1009 l := this.val[r].values for i := 0; i < len(l); i++ { if l[i].key == key { return l[i].value } } return -1 } func (this *MyHashMap) Remove(key int) { r := key % 1009 l := this.val[r].values for i := 0; i < len(l); i++ { if l[i].key == key { this.val[r].values = append(l[:i], l[i+1:]...) } } } -
快速排序 Quick Sort 4
func QuickSort(values []int) { length := len(values) if length <= 1 { return } // 取第一个元素作为分水岭，i下标初始为1，即分水岭右侧的第一个元素的下标 mid, i := values[0], 1 head, tail := 0, length-1 // 头尾的下标 for head < tail { // 如果头和尾没有相遇，就会一直触发交换 if values[i] > mid { // 如果分水岭右侧的元素大于分水岭，就将右侧的尾部元素和分水岭右侧元素交换 values[i], values[tail] = values[tail], values[i] tail-- // 尾下标左移一位 } else { // 如果分水岭右侧的元素小于等于分水岭，就将分水岭右移一位 values[i], values[head] = values[head], values[i] head++ // 头下标右移一位 i++ // i下标右移一位 } } // 分水岭左右的元素递归做同样处理 QuickSort(values[:head]) QuickSort(values[head+1:]) } -
最长公共子序列（ Longest Common Subsequence）1143
func longestCommonSubsequence(text1 string, text2 string) int { if len(text1) * len(text2) == 0 { return 0 } dp := make([][]int, len(text1)+1) for i := range dp { dp[i] = make([]int, len(text2)+1) } for i, v1 := range text1 { for j, v2 := range text2 { dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]) if v1 == v2 { dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j+1]) } } } return dp[len(text1)][len(text2)] } func max(i, j int) int { if i > j { return i } return j } -
判断BST（Validate Binary Search Tree）98
func isValidBST(root *TreeNode) bool { if root != nil{ for i, v := range []*TreeNode{root.Left, root.Right}{ var q []*TreeNode if v != nil{ q =append(q, v) for len(q) > 0{ v := q[0] q = q[1:] if i==0&&v.Val>=root.Val||i==1&&v.Val<=root.Val{ return false } for _, t :=range []*TreeNode{v.Left, v.Right}{ if t != nil{ q = append(q, t) } } } } } return isValidBST(root.Left)&&isValidBST(root.Right) } return true } -
斐波那且数列，空间复杂度o(1)（Fibonacci Number）509
func fib(N int) int { if N == 0 { return 0 } if N == 1 { return 1 } var a = 0 var b = 1 for i := 2; i <= N; i++ { a, b = b, a+b } return b } -
k个有序链表归并（ Merge k Sorted Lists）23
type minHeap []*ListNode func (h minHeap) Less(i, j int) bool { return h[i].Val < h[j].Val} func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h minHeap) Len() int { return len(h) } func (h *minHeap) Push(v interface{}) { *h = append(*h, v.(*ListNode))} func (h *minHeap) Pop() interface{} { min := (*h)[len(*h) - 1] *h := (*h)[:len(*h) - 1] return min } func mergeKLists(lists []*ListNode) *ListNode { tmp := minHeap(lists) h := &tmp heap.Init(h) var head, last *ListNode for h.Len() > 0 { v := heap.Pop(h).(*ListNode) if v == nil { continue } if last != nil { last.Next = v } if head == nil { head = v } last = v if v.Next != nil { heap.Push(h, v.Next) } } return head } -
用队列实现栈（Implement Stack using Queues）225
type MyStack struct { enque [] int deque [] int } func Constructor() MyStack { return MyStack{[]int{}, []int{}} } func (this *MyStack) Push(x int) { this.enque = append(this.enque, x) } func (this *MyStack) Pop() int { length := len(this.enque) for i := 0; i < length - 1; i++{ this.deque = append(this.deque, this.enque[0]) this.enque = this.enque[1:] } topEle := this.enque[0] this.enque = this.deque this.deque = nil return topEle } func (this *MyStack) Top() int { topEle := this.Pop() this.enque = append(this.enque, topEle) return topEle } func (this *MyStack) Empty() bool { if len(this.enque) == 0 { return true } return false } -
二叉树路径总和定长（Path Sum III ）437
func pathSum(root *TreeNode, sum int) int { if root == nil { return 0 } return helper(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum) } func helper(root *TreeNode, sum int) int { count := 0 if root == nil { return 0 } if root.Val == sum { count++ } return count + helper(root.Left, sum - root.Val) + helper(root.Right, sum - root.Val) } -
二叉树路径总和定长（Path Sum II ）113
func pathSum(root *TreeNode, sum int) [][]int { var slice [][]int slice = findPath(root, sum, slice, []int(nil)) return slice } func findPath(n *TreeNode, sum int, slice [][]int, stack []int) [][] int { if n == nil { return slice } sum -= n.Val stack = append(stack, n.Val) if sum == 0 && n.Left == nil && n.Right == nil { slice = append(slice, append([]int(nil), stack...)) } slice = findPath(n.Left, sum, slice, stack) slice = findPath(n.Right, sum, slice, stack) return slice } -
二叉树转双向链表（Convert Binary Search Tree to Sorted Doubly Linked List）426 2
func Tree2DoublyList(root *TreeNode) *TreeNode{ if root == nil{ return nill } head, pre := ListNode{}, ListNode{} inOrder(root, pre, head) pre.Right = head head.Left = pre return head } func inOrder(root, pre, head *TreeNode){ if root == nil {return nil} inOrder(root.Left, pre, head) if head == nil{ head = root pre = root }else{ pre.Right = root root.Left = pre pre = root } inOrder(root.Right, pre, head) } -
岛屿的最大面积（Max Area of Island）695 2
func maxAreaOfIsland(grid [][]int) int { var maxArea int for i := 0; i < len(grid); i++ { for j := 0; j < len(grid[0]); j++ { if grid[i][j] == 0 { continue } area := 0 helper(i, j, grid, &area) if area > maxArea { maxArea = area } } } return maxArea } func helper(i, j int, grid [][]int, area *int) { if i < 0 || i == len(grid) || j < 0 || j == len(grid[0]) || grid[i][j] == 0 { return } *area++ grid[i][j] = 0 helper(i+1, j, grid, area) helper(i-1, j, grid, area) helper(i, j+1, grid, area) helper(i, j-1, grid, area) } -
栈排序（Sort Stack By Stack）
func sortStackByStack(s []int) res []int{ while s != nil{ top := s[len(s)-1] s := s[:len(s)-2] while res != nil && res[len(s)-1] > top{ s = append(s, res[len(s)-1]) res = res[:len(s)-2] } res = append(res, top) } } -
Min栈（Min Stack）155
type MinStack struct { stack []int min []int } /** initialize your data structure here. */ func Constructor() MinStack { return MinStack{ stack: make([]int, 0), min: make([]int, 0), } } func (this *MinStack) Push(x int) { this.stack = append(this.stack, x) if len(this.min) == 0 || x <= this.GetMin() { this.min = append(this.min, x) } } func (this *MinStack) Pop() { if this.Top() == this.GetMin() { this.min = this.min[:len(this.min)-1] } this.stack = this.stack[:len(this.stack)-1] } func (this *MinStack) Top() int { return this.stack[len(this.stack)-1] } func (this *MinStack) GetMin() int { return this.min[len(this.min)-1] } -
最大子数组的和（Maximum Subarray）53
func maxSubArray(nums []int) int { var cursum, maxsum int maxsum = math.MinInt32 for _, value := range nums{ cursum += value if cursum > maxsum{ maxsum = cursum } if cursum < 0{ cursum = 0 } } return maxsum } -
交换数字得最大整数（Maximum Swap）670
func maximumSwap(num int) int { var digits []int for num > 0 { digits = append(digits, num%10) num /= 10 } var maxDigit, maxIndex int index1, index2 := -1, -1 for i, digit := range digits { if digit > maxDigit { maxDigit = digit maxIndex = i } else if digit < maxDigit { index1 = i index2 = maxIndex } } if index1 >= 0 { digits[index1], digits[index2] = digits[index2], digits[index1] } var res int for i := len(digits) - 1; i >= 0; i-- { res = res*10 + digits[i] } return res } -
打家劫舍 II（House Robber II）213 3
func rob(nums []int) int { l := len(nums) if l == 0 { return 0 } if l == 1 { return nums[0] } return max(helper(nums[:l-1]), helper(nums[1:])) } func helper(nums []int) int { if len(nums) == 1 { return nums[0] } dp := make([]int, len(nums)) dp[0], dp[1] = nums[0], max(nums[0], nums[1]) for i := 2; i < len(nums); i++ { dp[i] = max(dp[i-2] + nums[i], dp[i-1]) } return dp[len(dp)-1] } func max(a int, b int) int { if a > b { return a } return b } -
LFU Cache 460
type CacheNode struct { key int value int prev *CacheNode next *CacheNode parent *FreqNode } func (n *CacheNode) moveAddOneFreq(key int, value int) *CacheNode { var newFreqNode *FreqNode curFreqNode := n.parent if curFreqNode.next != nil && curFreqNode.next.freq == (curFreqNode.freq + 1) { newFreqNode = curFreqNode.next } else { newFreqNode = NewFreqNode(curFreqNode.freq + 1, curFreqNode, curFreqNode.next) } newCacheNode := &CacheNode{ key: key, value: value, prev: nil, next: newFreqNode.head, parent: newFreqNode, } if newFreqNode.head == nil { newFreqNode.tail = newCacheNode } else { newFreqNode.head.prev = newCacheNode } newFreqNode.head = newCacheNode n.evictNode() return newCacheNode } type FreqNode struct { freq int head *CacheNode tail *CacheNode prev *FreqNode next *FreqNode } func (node *FreqNode) removeFreqNode() { if node.freq == 0 { panic("should not remove the head") } node.prev.next = node.next if node.next != nil { node.next.prev = node.prev } } func NewFreqNode(freq int, prev *FreqNode, next *FreqNode) *FreqNode { nn := &FreqNode{ freq: freq, prev: prev, next: next, } if prev != nil { prev.next = nn } if next != nil { next.prev = nn } return nn } type LFUCache struct { size int capacity int cache map[int]*CacheNode lfuHead *FreqNode } func Constructor(capacity int) LFUCache { zeroFreqHead := &FreqNode{ freq: 0, // head freq is true } return LFUCache{ capacity: capacity, cache: make(map[int]*CacheNode, capacity), lfuHead:zeroFreqHead, } } func (this *LFUCache) Get(key int) int { if found, ok := this.cache[key]; ok { newCacheNode := found.moveAddOneFreq(key, found.value) this.cache[key] = newCacheNode return found.value } else { return -1 } } func (this *LFUCache) Put(key int, value int) { if this.capacity == 0 { return } if found, ok := this.cache[key]; ok { newCacheNode := found.moveAddOneFreq(key, value) this.cache[key] = newCacheNode } else { if this.size >= this.capacity { lfuNode := this.lfuHead.next.tail delete(this.cache, lfuNode.key) lfuNode.evictNode() } else { this.size++ } var oneFreqNode *FreqNode if this.lfuHead.next != nil && this.lfuHead.next.freq == 1 { oneFreqNode = this.lfuHead.next } else { oneFreqNode = NewFreqNode(1, this.lfuHead, this.lfuHead.next) } newCacheNode := &CacheNode{ key: key, value: value, prev: nil, next: oneFreqNode.head, parent: oneFreqNode, } this.cache[key] = newCacheNode if oneFreqNode.head == nil { oneFreqNode.tail = newCacheNode } else { oneFreqNode.head.prev = newCacheNode } oneFreqNode.head = newCacheNode } } func (node *CacheNode) evictNode() { // remove the cache node from the linkedList // remove the freqNode(parent) if it is empty // do nothing to the map curFreqNode := node.parent if node.prev != nil { node.prev.next = node.next } else { curFreqNode.head = node.next } if node.next != nil { node.next.prev = node.prev } else { curFreqNode.tail = node.prev } if curFreqNode.head == nil { curFreqNode.removeFreqNode() } } -
链表排序（Sort List）148
func sortList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } slow, fast := head, head.Next for fast.Next != nil && fast.Next.Next != nil { slow = slow.Next fast = fast.Next.Next } rightHead := slow.Next slow.Next = nil return merge(sortList(head), sortList(rightHead)) } func merge(list1 *ListNode, list2 *ListNode) *ListNode { result := &ListNode{Val: 0} current := result for list1 != nil && list2 != nil { if list1.Val < list2.Val { current.Next = list1 list1 = list1.Next } else { current.Next = list2 list2 = list2.Next } current = current.Next } if list1 != nil { current.Next = list1 } if list2 != nil { current.Next = list2 } return result.Next } -
数组中超过一半的数字（Majority Element）169 3
func majorityElement(nums []int) int { m := make(map[int] int) for _, v := range nums{ m[v]++ if m[v] > len(nums) / 2 { return v } } return 0 } -
每K个一组反转列表（Reverse Nodes in k-Group）25 2
func reverseKGroup(head *ListNode, k int) *ListNode { if head == nil || head.Next == nil || k < 2 { return head } curr := head count := 0 for curr != nil && count != k { curr = curr.Next count++ } if count == k { curr = reverseKGroup(curr, k) for count > 0 { tmp := head.Next head.Next = curr curr = head head = tmp count-- } head = curr } return head } -
对称二叉树（Symmetric Tree）101
func isSymmetric(root *TreeNode) bool { if root == nil{ return true } return ish(root.Left, root.Right) } func ish(l, r *TreeNode) bool{ if l == nil || r == nil{ return l == r } if l.Val != r.Val { return false } return ish(l.Left, r.Right) && ish(l.Right, r.Left) } -
字符串解码（Decode String）394 2
func decodeString(s string) string { stackNums := make([]int, 0) stackStr := make([]string, 0) var res string var num int for i := 0; i < len(s); i++ { switch { case s[i] >= '0' && s[i] <= '9': num = 10*num + int(s[i]) - '0' case s[i] == '[': stackNums = append(stackNums, num) num = 0 stackStr = append(stackStr, res) res = "" case s[i] == ']': tmp := stackStr[len(stackStr)-1] stackStr = stackStr[:len(stackStr)-1] count := stackNums[len(stackNums)-1] stackNums = stackNums[:len(stackNums)-1] res = tmp + strings.Repeat(res, count) default: res += string(s[i]) } } return res } -
区间合并（Merge Intervals）2
func merge(intervals [][]int) [][]int { if len(intervals) == 0 { return [][]int{} } merged := make([][]int, 0, len(intervals)) sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) current := intervals[0] for i := 1; i < len(intervals); i++ { if intervals[i][0] > current[1] { merged = append(merged, current) current = intervals[i] } else if intervals[i][1] > current[1] { current[1] = intervals[i][1] } } merged = append(merged, current) return merged } -
数组序号转换（Rank Transform of an Array）1331
type Ints []int func (arr Ints) Len() int { return len(arr) } func (arr Ints) Swap(i, j int) { arr[i], arr[j] = arr[j], arr[i] } func (arr Ints) Less(i, j int) bool { return arr[i] < arr[j] } func arrayRankTransform(arr []int) []int { var m map[int][]int = make(map[int][]int) for i, v := range arr { m[v] = append(m[v], i) } sort.Sort(Ints(arr)) // fmt.Println("after sorted", arr) var res []int = make([]int, len(arr)) var seq int = 1 for _, v := range arr { if _, ok := m[v]; ok == true { for _, v1 := range m[v] { res[v1] = seq } seq++ delete(m, v) } } return res } -
数组中第K个大的元素（Kth Largest Element in an Array）215 2
func findKthLargest(nums []int, k int) int { nlen := len(nums) targetPos := nlen - k start, end := 0, nlen-1 for { pivotIndex := partition(nums, start, end) if pivotIndex == targetPos { return nums[pivotIndex] } else if pivotIndex < targetPos { start = pivotIndex + 1 } else { end = pivotIndex - 1 } } } func partition(nums []int, start, end int) int { pivot := nums[start] left, right := start+1, end for left <= right { for left <= right && nums[left] <= pivot { left++ } for left <= right && nums[right] > pivot { right-- } if left <= right { nums[left], nums[right] = nums[right], nums[left] } } nums[start], nums[right] = nums[right], nums[start] return right } -
反转数组中的最小值（Find Minimum in Rotated Sorted Array）153 3
func findMin(nums []int) int { left, right := 0, len(nums)-1 for left < right { mid := (left + right) / 2 if nums[mid] > nums[right] { left = mid + 1 } else { right = mid } } return nums[left] } -
平衡二叉树（Balanced Binary Tree）110 2
func isBalanced(root *TreeNode) bool { return maxDepth(root) != -1 } func maxDepth(root *TreeNode) int { if root == nil { return 0 } left := maxDepth(root.Left) right := maxDepth(root.Right) if left == -1 || right == -1 || left-right > 1 || right-left > 1 { return -1 } return max(left, right) + 1 } func max(a, b int) int { if a > b { return a } return b } -
括号匹配（Longest Valid Parentheses）32
func longestValidParentheses(s string) int { var result int stack := []int{-1} for i := range s { if len(stack) > 1 && s[i] == ')' && s[stack[len(stack)-1]] == '(' { stack = stack[:len(stack)-1] if i-stack[len(stack)-1] > result { result = i - stack[len(stack)-1] } } else { stack = append(stack, i) } } return result } -
二叉树右视图（Binary Tree Right Side View）199
func rightSideView(root *TreeNode) []int { result := make([] int, 0) rightView(root, &result, 0) return result } func rightView(cur *TreeNode, result *[]int, curDepth int) { if cur == nil { return } if curDepth == len(*result) { *result = append(*result, cur.Val) } rightView(cur.Right, result, curDepth+1) rightView(cur.Left, result, curDepth+1) } -
首个缺失正数（First Missing Positive）41
func firstMissingPositive(nums []int) int { length := len(nums) for i := 0; i < length; i++ { if nums[i] <= 0 || nums[i] > length { nums[i] = 0 } else if nums[i] == i+1 { continue } else if nums[i] == nums[nums[i]-1] { nums[i] = 0 } else if nums[i] != nums[nums[i]-1] { nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] i-- } } for i, v := range nums { if v == 0 { return i+1 } } return length+1 } -
只出现一次的数字（Single Number）136
func singleNumber(nums []int) int { var result int for i := range nums { result ^= nums[i] } return result } -
最长无重复子串（Longest Substring Without Repeating Characters）3
func maxInt(a, b int) int { if a > b { return a } return b } func lengthOfLongestSubstring(s string) int { maxLen, start := 0, 0 table := [128]int{} for i, _ := range table { table[i] = -1 } for i, c := range s { if table[c] >= start { start = table[c] + 1 } table[c] = i maxLen = maxInt(maxLen, i - start + 1) } return maxLen } -
组合之和（Combination Sum）39
func combinationSum(candidates []int, target int) [][]int { result := make([][]int, 0) backtracking([]int{}, candidates, 0, target, &result) return result } func backtracking(subset, candidates []int, sum, target int, result *[][]int) { if sum == target { *result = append(*result, subset) return } else if sum > target { return } for i := range candidates { subsetCopy := make([]int, 0, len(subset)+1) subsetCopy = append(subsetCopy, subset...) backtracking(append(subsetCopy, candidates[i]), candidates[i:], sum+candidates[i], target, result) } } -
顺时针打印矩阵（Spiral Matrix）54
func spiralOrder(matrix [][]int) []int { if len(matrix) == 0 || len(matrix[0]) == 0 { return []int{} } var res []int top, bottom, left, right := 0, len(matrix) - 1, 0, len(matrix[0]) - 1 point := []int{0, 0} for { for i := point[1]; i <= right; i++{ res = append(res, matrix[point[0]][i]) } if point[0] >= bottom { break } top, point[0], point[1] = top + 1, point[0] + 1, right for i := point[0]; i <= bottom; i++{ res = append(res, matrix[i][point[1]]) } if point[1] <= left { break } right, point[0], point[1] = right - 1, bottom, point[1] -1 for i := point[1]; i >= left; i--{ res = append(res, matrix[point[0]][i]) } if point[0] <= top { break } bottom, point[0], point[1] = bottom - 1, point[0] - 1, left for i := point[0]; i >= top; i--{ res = append(res, matrix[i][point[1]]) } if point[1] >= right{ break } left, point[0], point[1] = left + 1, top, point[1] + 1 } return res } -
36进制加法
func Add(str1 string, str2 string) string { List36 := []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"} i := len(str1) - 1 j := len(str2) - 1 var sum string var tem int //进位 for i >= 0 && j >= 0 { s := GetInt(str1[i]) + GetInt(str2[j]) + tem if s >= 36 { tem = 1 sum = List36[s%36]+sum } else { tem = 0 sum = List36[s]+sum } i-- j-- } for i >= 0 { s:= GetInt(str1[i])+tem if s>=36{ tem = 1 sum = List36[s%36]+sum }else { tem = 0 sum = List36[s]+sum } i-- } for j >= 0 { s:= GetInt(str2[i])+tem if s>=36{ tem = 1 sum = List36[s%36]+sum }else { tem = 0 sum = List36[s]+sum } j-- } if tem!=0{ sum="1"+sum } return sum } //将'0'-'9'映射到数字0-9，将'a'-'z'映射到数字10-35 func GetInt(a uint8) int { if a-'0' > 0 && a <= '9' { return int(a - '0') } else { return int(a-'A') + 10 } } -
Sqrt(x) 69
func mySqrt(x int) int { for left, right := 0, x; ; { mid := left + (right-left)/2 if mid*mid > x { right = mid - 1 } else if (mid+1)*(mid+1) > x { return mid } else { left = mid + 1 } } } -
快速幂（Pow(x, n)）50
func myPow(x float64, n int) float64 { if n < 0 { x, n = 1/x, -n } result := 1.0 for n > 0 { if n&1 == 1 { result *= x } x, n = x*x, n>>1 } return result } -
抛掷硬币（Toss Strange Coins）1230
func probabilityOfHeads(prob []float64, target int) float64 { dp := make([]float64, len(prob) + 1) dp[0] = 1.0 for i := 0; i < len(prob); i++ { for k := target; k >= 0; k-- { if k > 0 { dp[k] = dp[k - 1] * prob[i] + dp[k] * (1 - prob[i]) } else { dp[k] = dp[k] * (1 - prob[i]) } } } return dp[target] } -
按奇偶排序数组（Sort Array By Parity）922
func sortArrayByParityII(A []int) []int { i := 1 for j:=0;j<len(A);j+=2{ if A[j] % 2 == 1{ for A[i] % 2 == 1{ i += 2 } A[i],A[j] = A[j], A[i] } } return A } -
N叉树层序遍历（N-ary Tree Level Order Traversal）429
func levelOrder(root *Node) [][]int { res := [][]int{} helper(root, 0, &res) return res } func helper(root *Node, level int, res *[][]int){ if root == nil{ return } for _, v := range root.Children{ helper(v, level+1, res) } for len(*res) <= level{ *res = append(*res, []int{}) } (*res)[level] = append((*res)[level], root.Val) } -
最小覆盖子串（Minimum Window Substring ）76
func minWindow(s string, t string) string { requirements := make(map[byte]int) for i := range t { requirements[t[i]]++ } apperances := make(map[byte]int) counter := len(t) minLen := len(s) + 1 resLeft, resRight := 0, 0 for left, right := 0, 0; right < len(s); { lch, rch := s[left], s[right] if _, ok := requirements[rch]; ok { apperances[rch]++ if apperances[rch] <= requirements[rch] && counter != 0 { counter-- } } if counter == 0 { for { if _, ok := apperances[lch]; !ok || apperances[lch] > requirements[lch] { if apperances[lch] > requirements[lch] { apperances[lch]-- } left++ lch = s[left] } else { break } } if right-left+1 < minLen { resLeft, resRight = left, right+1 minLen = right - left + 1 } } right++ } if resLeft == 0 && resRight == 0 { return "" } return s[resLeft:resRight] } -
数组中最长的山（Longest Mountain in Array）845
type direction int const ( UP direction = iota DOWN FLAT ) func max(a, b int) int { if a > b { return a } return b } func longestMountain(A []int) int { N := len(A) if N < 3 { return 0 } longest := 0 i := 1 for ; i < N && A[i] <= A[i - 1]; i++ {;} direc, upStep, downStep := UP, 1, 0 for i++; i < N; i++ { if direc == UP { if A[i] > A[i - 1] { upStep++ } else if A[i] < A[i - 1] { direc, upStep, downStep = DOWN, upStep + 1, 1 } else { direc, upStep, downStep = FLAT, 0, 0 } } else if direc == FLAT { for ; i < N && A[i] <= A[i - 1]; i++ {;} direc, upStep, downStep = UP, 1, 0 } else { if A[i] > A[i - 1] { longest = max(longest, upStep + downStep) direc, upStep, downStep = UP, 1, 0 } else if A[i] < A[i - 1] { downStep++ } else { longest = max(longest, upStep + downStep) direc, upStep, downStep = FLAT, 0, 0 } } } if direc == DOWN { longest = max(longest, upStep + downStep) } return longest } -
删除数组中相邻重复数（Remove All Adjacent Duplicates in String）1047
func removeDuplicates(S string) string { stack := []byte{} for i := 0; i < len(S); i++ { if len(stack) != 0 && stack[len(stack)-1] == S[i] { stack = stack[:len(stack)-1] } else { stack = append(stack, S[i]) } } return string(stack) } -
给表达式添加运算符（Expression Add Operators）282
func addOperators(num string, target int) []string { ans := make([]string, 0) currStr := "" backTrack(num, 0, target, currStr, &ans) return ans } func backTrack(num string, idx ,target int, currStr string, ans *[]string) { if idx == len(num) { if len(currStr) > 0 && isNumeric(currStr[len(currStr)-1]) { if isEquationCorrect(currStr, target) { *ans = append(*ans, currStr) } } return } if len(currStr) >0 && isNumeric(currStr[len(currStr)-1]) { backTrack(num, idx, target, currStr+"*", ans) backTrack(num, idx, target, currStr+"+", ans) backTrack(num, idx, target, currStr+"-", ans) } backTrack(num, idx+1, target, currStr+string(num[idx]), ans) } func isNumeric(b byte) bool { if b >= 48 && b <= 57 { return true} return false } func isEquationCorrect(eq string, target int) bool { stack := make([]string, 0) idx := 0 for idx < len(eq) { if eq[idx] == '-' || eq[idx] == '+' { stack = append(stack, string(eq[idx])) idx++ continue } else if eq[idx] >= 48 && eq[idx] <= 57 { prev := idx for idx < len(eq) && eq[idx] >= 48 && eq[idx] <= 57 { idx++ } if len(string(eq[prev:idx])) > 1 && string(eq[prev:idx])[0] == 48 { return false } stack = append(stack, string(eq[prev:idx])) continue } else if eq[idx] == '*' { prevNum, _ := strconv.Atoi(stack[len(stack)-1]) stack = stack[:len(stack)-1] idx++ prev := idx for idx < len(eq) && eq[idx] >= 48 && eq[idx] <= 57 { idx++ } if len(string(eq[prev:idx])) > 1 && string(eq[prev:idx])[0] == 48 { return false } num,_ := strconv.Atoi(eq[prev:idx]) newNum := num*prevNum stack = append(stack, strconv.Itoa(newNum)) } } ans := 0 sign := 1 for _, val := range stack { if val == "-" { sign = -1 } else if val != "+" && val != "-" { num,_ := strconv.Atoi(val) ans += sign*num sign = 1 } } return ans == target } -
过桥
func bridge(v []int){ length := len(v) sort.Ints(v) dp := make([]int, length) dp[0], dp[1] = v[0], v[1] for i:=2; i<len; i++{ dp[i] = min(dp[i-1]+v[0]+v[i], dp[i-2]+2*v[1]+v[0]+v[i]) } return dp[len-1] } -
删除注释（Remove Comments）722
func removeComments(source []string) []string { inblock := false var result []string var arr []string for i:=0;i<len(source);i++ { word := source[i] if !inblock { arr = nil } j := 0 for j < len(word) { if !(inblock) &&j+1 < len(word) && word[j] == '/' && word[j+1] == '*' { inblock = true j++ }else if inblock && j+1 < len(word) && word[j] == '*' && word[j+1] == '/' { inblock = false j++ }else if !(inblock) && j+1 < len(word) && word[j] == '/' && word[j+1] == '/' { break } else if !(inblock) { arr = append(arr,string(word[j])) } j++ } if !inblock && len(arr) > 0 { result = append(result,strings.Join(arr,"")) } } return result } -
买卖股票的最佳时机（Best Time to Buy and Sell Stock） 121
func maxProfit(prices []int) int { if len(prices) < 2 { return 0 } var profit int min := prices[0] for i := 1; i < len(prices); i++ { if prices[i]-min > profit { profit = prices[i] - min } if prices[i] < min { min = prices[i] } } return profit } -
搜索二维矩阵（Search a 2D Matrix II）240
func searchMatrix(matrix [][]int, target int) bool { if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 { return false } row, col := 0, len(matrix[0])-1 for row < len(matrix) && col >= 0 { val := matrix[row][col] if val > target { col-- } else if val < target { row++ } else { return true } } return false } -
爱吃香蕉的珂珂（Koko Eating Bananas） 875
func minEatingSpeed(piles []int, H int) int { left, right := 1, math.MaxInt32 for left <= right { mid := left + (right-left)/2 if minEatingSpeedHelper(piles, H, mid) { right = mid - 1 } else { left = mid + 1 } } return left } func minEatingSpeedHelper(piles []int, H int, K int) bool { for i := 0; i < len(piles); i++ { H -= ((piles[i]-1)/K + 1) if H < 0 { return false } } return true } -
字符串实现减法（ Subtract two integers）
func subtract(num1, num2 string)int{ if len(num1) < len(num2){ subtract(num2, num1) return } if len(num1) == len(num2){ for i:=0; i<len(num1); i++{ if num1[i] < num2[i]{ subtract(num2, num1) return } } } point1, point2 := len(num1)-1, len(num2)-1 while point1 >= 0 && point2 >=0{ digit1 := num1[point1--] digit2 := num2[point2--] diff := 0 if digit1 < digit2{ diff = digit1+10-digit2 num1[point1] = -1 }else{ diff = digit1 - digit2 } num1[point+1] = diff } num := 0 for i:=0;i<len(num1); i++{ num = num*10 + num1[1] } return num } -
压平二维向量（Flatten 2D Vector）251
type Vector2D struct { v [][]int r, c int } func Constructor(v [][]int) Vector2D { return Vector2D{v, 0, 0 } func (this *Vector2D) Next() int { this.HasNext() v := this.v[this.r][this.c] this.c++ return v } func (this *Vector2D) HasNext() bool { for this.r < len(this.v) { if this.r < len(this.v) && this.c < len(this.v[this.r]) { return true } if this.c == len(this.v[this.r]) { this.r++ this.c = 0 } else { this.c++ } } return false } -
硬币找零（Coin Change）322
func coinChange(coins []int, amount int) int { dp := make([]int, amount+1) for i := 1; i <= amount; i++ { min := -1 for _, coin := range coins { if i < coin || dp[i-coin] == -1 { continue } if min == -1 || dp[i-coin]+1 < min { min = dp[i-coin] + 1 } } dp[i] = min } return dp[amount] } -
取子游戏（Nim Game）292
func canWinNim(n int) bool { return n%4 != 0 } -
下一个排列（Next Permutation）31
func nextPermutation(nums []int) { if len(nums) < 2 { return } var idx = len(nums) - 1 for idx > 0 { if nums[idx-1] < nums[idx] { break } idx-- } reverseSort(nums, idx, len(nums)-1) if idx == 0 { return } for i := idx; i < len(nums); i++ { if nums[i] > nums[idx-1] { nums[idx-1], nums[i] = nums[i], nums[idx-1] return } } } func reverseSort(nums []int, start int, end int) { for i, j := start, end; i < end+(start-end)/2; i, j = i+1, j-1 { nums[i], nums[j] = nums[j], nums[i] } }
海量数据
- 分而治之/hash映射 + hash统计 + 堆/快速/归并排序
- 双层桶划分
- Bloom filter/Bitmap
- Trie树/数据库/倒排索引
- 外排序
- 分布式处理之Hadoop/Mapreduce
-
10亿个数字，取最小的100个数 heapSort、partition、（时间、空间复杂度）5
-
数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间。
-
局部淘汰法，用一个容器保存前10000个数，然后将剩余的所有数字——与容器内的最小数字相比，如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。
-
分治法，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的100*10000个数据里面找出最大的10000个。
-
Hash法。如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。
-
最小堆。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）该算法的时间复杂度为O（nmlogm），空间复杂度是10000（常数）。
func heapSort(data []int) { for i := (len(data) - 1) / 2; i >= 0; i-- { // create heap siftDown(data, i, len(data)) } for i := len(data) - 1; i >= 0; i-- { // sort data[0], data[i] = data[i], data[0] siftDown(data, 0, i) } } func siftDown(data []int, low, high int) { root := low for { child := 2*root + 1 if child >= high { break } if child+1 < high && data[child] < data[child+1] { child++ } if data[root] >= data[child] { break } data[root], data[child] = data[child], data[root] root = child } } -
网友评论