bittib

import java.io.*;
public class Main{

    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static int N = 8; 
    static int cnt = 0;

    public static void main(String[] args){
        int[] array = new int[N];
        cnt = 0;

bittib

/**
 * 最简单的01背包
 * N个物品，装入重量大小为M的包，每个物品重w[i]，价值p[i], 求包内最大价值
 * 输入规模 ：1<=N<=3402, 1<=M<=12880
 * 
 * 设f[i][j]是前i个物品装入重量大小为j的包的最大值,
 * f[i][j] = max{f[i-1][j], f[i-1][j-w[i]] + p[i]}
 * 最终结果是f[n-1][m]
 * 
 * 时间复杂度为O(N*M),空间复杂度为O(N*M),空间复杂度可以优化到O(N)

bittib

// DP version, Time Complexity : O(n^2)
public int lis(int[] A){
    if (A == null || A.length == 0) return 0;
    int n = A.length;
    int[] f = new int[n];
    for (int i=0; i<n; i++){
        f[i] = 1;
        for (int j=0; j<i; j++){
            if (A[j] <= A[i] && f[j] + 1 > f[i])
                f[i] = f[j] + 1;

bittib

public String lcs(String a, String b){
    int m = a.length(), n = b.length();
    int[][] f = new int[m+1][n+1];
    for (int i=0; i<=n; i++)
        f[0][i] = 0;
    for (int i=0; i<=m; i++)
        f[i][0] = 0;
    for (int i=1; i<=m; i++){
        for (int j=1; j<=n; j++){
            if (a.charAt(i-1) == b.charAt(j-1))

bittib

/**
 * http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
 * O(lgm + lgn) Solution
 */

static final int MIN = Integer.MIN_VALUE;
static final int MAX = Integer.MAX_VALUE;

public static int kthSmallest(int[] A, int[] B, int k){
    if (A == null || B == null || k > A.length + B.length)

bittib

/**
 * Time Complexity: O(n)
 */
public int[] minOfSlidingWindow(int[] A, int k){
    int n = A.length;
    int[] B = new int[n - k + 1];
    int[] queue = new int[n];
    int head = 0, tail = 0;
    for (int i=0; i<n; i++){
        while (head < tail && A[i] <= A[queue[tail-1]])

bittib

/**
 * Time Complexity : Comparision time : 3 * n/2 + 1
 */
public int[] findMinMax(int[] A){
    int n = A.length;
    if (n == 0) return null;
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int i=0; i < n-1; i+=2){
        int smaller = A[i], bigger = A[i+1];
        if (A[i] > A[i+1){

bittib

/**
 * LeetCode Add Binary Probem

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

 */

bittib

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode(int val){
        this.val = val;
    }
}

public void flatten(TreeNode root){
    root = flatten(root, null);

bittib

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode(int val){
        this.val = val;
    }
}

public String serialize(TreeNode root){
    StringBuilder sb = new StringBuilder();