/algorithm

solution of leetcode/lintcode/

Primary LanguageJava

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