Skip to content

cheungYX/algorithm

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

161 Commits
cheung
cheung
 
 
go
go
 
 
java
java
 
 
ruby
ruby
 
 
tmp
tmp
 
 
travel
travel
 
 
README.md
README.md
 
 
menu.md
menu.md
 
 

Repository files navigation

LintCode Ladder

level 1 BackTracking

level 2 Binary Search

level 3 Binary Tree & Divide Coquer

level 4 Breadth First Search

level 5 Depth First Search

level 6 Linked List & Array

level 7 Two Pointers

level 8 Data Structure

level 9 Dynamic Programming

LintCode Ladder advance

level 1 Windows Moving

level 2 UnionFind & Trie

level 3 Heap & Stack

level 4 Binary Search + Sweep Line

level 5 Dynamic Problem I

level 6 Dynamic Problem II

level 7 Follow Up

Leet Code

Algorithm

Binary Search

Robin-Karp

Topological sorting

External Sorting

Binary Index Tree

Divide Coquer

Breadth First Search

Depth First Search

Backtracking

  • 深搜中出栈的那一步

Two Pointers

  • window 同向双指针
  • 数据流

Dynamic Programming

  • 记忆化搜索
  • 子问题有交集
  • 状态定义 => 初始化 => 循环递推求解 => 求结果:起点
  • 题型: 最值，判断可行性，统计方案个数
  • 2^n n! => n^2 n^3

Moving window

for (int i = 0; i < n; i++) {
    while(j < n) {
        if(满足条件) {
            j++;
            更新j状态
        } else(不满足条件) {
            break;
        }
        更新i状态
    }
}

Scan-line algorithm

Quick Sort

Data Structure

Stack

  • LIFO
public class Stack {
    private int[] data;
    private int size;
    private int top = 0; // 指向栈的顶部

    public Stack(int size) {
        this.size = size;
        this.data = new int[size];
    }
}

Queue

  • FIFO

Linked List

class LinkNode {
    public int data;
    public LinkNode next;

    public LinkNode(int data) {
        this.data = data;
        this.next = null;
    }
}
class ListNode
	attr_accessor :val, :next
	def initialize(val)
		@val = val
		@next = nil
	end
end

head = ListNode.new(1)
head.next = ListNode.new(2)
head.next.next = ListNode.new(3)
head.next.next.next = ListNode.new(4)
head.next.next.next.next = ListNode.new(5)

Array

Hash Table

  • O(size of key)

  • 用来查重

  • 替代: BBST => TreeSet，trie，BloomFilter

  • LFU

  • LRU

Binary Tree

class Node {
    public Object data;
    public Node left;
    public Node right;
}

Heap

  • vs PriorityQueue
TreeMap Heap PriorityQueue
1. Insert() logn logn logn
2. Delete() logn logn O(n) / X
3. Pop() logn logn logn
4. Find() logn logn X
5. Modify() logn logn X
6. Min / Max logn O(1) O(1)
7. upper / lower logn X X

Union Find

class UnionFind{
    HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
    UnionFind(int n){
        for(int i = 0 ; i < n; i++) {
            father.put(i, i);
        }
    }
    int compressed_find(int x){
        int parent =  father.get(x);
        while(parent!=father.get(parent)) {
            parent = father.get(parent);
        }
        int temp = -1;
        int fa = father.get(x);
        while(fa!=father.get(fa)) {
            temp = father.get(fa);
            father.put(fa, parent) ;
            fa = temp;
        }
        return parent;
    }

    void union(int x, int y){
        int fa_x = compressed_find(x);
        int fa_y = compressed_find(y);
        if(fa_x != fa_y)
            father.put(fa_x, fa_y);
    }
}

public class UnionFind {
    private int[] father = null;

    public int find(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find(father[x]);
    }

    public void union(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father[root_a] = root_b;
        }
    }
}

Trie

ex

class TrieNode {
    public TrieNode[] children;
    public boolean isWord;

    public TrieNode() {
        children = new TrieNode[26];
        for (int i = 0; i < 26; ++i) {
            children[i] = null;
        }
        isWord = false;
    }
}

private TrieNode root;

public WordDictionary(){
    root = new TrieNode();
}

public void addWord(String word) {
    // write your code here
    TrieNode current = root;
    for(int i = 0; i < word.length(); i++) {
        Character c = word.charAt(i);
        if (current.children[c - 'a'] == null) {
            current.children[c - 'a'] = new TrieNode();
        }
        current = current.children[c - 'a'];
    }
    current.isWord = true;
}

boolean find(String word, int index, TrieNode now) {
    if(index == word.length()) {
        return now.isWord;
    }

    Character c = word.charAt(index);
    if (c == '.') {
        for(int i = 0; i < 26; ++i)
        if (now.children[i] != null) {
            if (find(word, index+1, now.children[i]))
                return true;
        }
        return false;
    } else if (now.children[c - 'a'] != null) {
        return find(word, index+1, now.children[c - 'a']);
    } else {
        return false;
    }
}
  • 和Hash比更加节约空间
  • 可用来优化某些dfs

Graph

DP

  • state, function, intialization, result
  • 记忆化搜索来达到减枝的目的
  • 矩阵
  • 记忆化搜索
  • 状态转移特别麻烦，不是顺序性
  • 初始化状态不好找
  • 从大到小
  • 博弈类
  • 画出搜索树，只考虑先手策略
  • 空间类

other

  • crack and code inetrview

About

solution of leetcode/lintcode/

Resources

Readme
Activity

Stars

12 stars

Watchers

1 watching

Forks

3 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages