Combinations

Combinations
import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Solution solution = new Solution();
    char[][] input = {
      {'1','?','0','?','?'}      
    };
    for(int i=0;i<input.length;i++) {
      System.out.println(Arrays.toString(input[0]) + "\n");
      solution.combinations(input[i]);
    }
  }
  
  public void combinations(char[] input){
    if(input == null || input.length < 1) return;
    combinations(input, 0);
  }
       
  private void combinations(char[] input, int i) {
    if(i >= input.length) {
       System.out.println(input);
       return;
    }
    if(input[i] == '?'){
      for(char ch = '0'; ch <='1'; ch++ ){
        input[i] = ch;
        combinations(input, i+1);
        input[i] = '?';
      }
      return;
    }
    combinations(input, i+1);
  }
}

PYTHON SQLITE

1. create_new_db.py 2. create_table.py 3. insert_example.py 4. insert_example2.py 5. db_example.py 6. validate_check.py 7. SQL examples
# -*- coding: utf-8 -*-



import os
import sys
import sqlite3



log_file = open("log_db_file.txt", "a")


db_name = sys.argv[1]

print(str(db_name))


def validatedbname(db_name):
    filename, file_extension = os.path.splitext(db_name)
    if file_extension != '.db':
        print("Incorrent naming. File needs to suffix .db. Terminating")
        sys.exit(1)
    else:
        print("File provided in correct format. Proceeding with script")
        
def checkifexists(db_name):        
    if os.path.isfile(db_name):
        response = input("The file {0} already exists, do you wish to recreate it? (y/n)".format(db_name))
        if response == 'y' or response == 'Y':
            return True
        else:
            print("Terminating script.")
            sys.exit(1)
    else:
        print("File not located. New {0} file will be created".format(db_name))
        return True


def createdb(db_name):
    with sqlite3.connect(db_name) as db:
        try:
            cursor = db.cursor()
        except:
            print("Cannot establish cursor at {0}".format(db_name))
            return False
        else:
            print("Database {0} created succesfully.".format(db_name))
            return True


############################################################
# # Create new db
# # Notes:
# # Will create a new db file if one doesnt exist.
# # If it doesnt exist it will connect to existing db.
# # No conflict problems.
# with sqlite3.connect(db_name) as db:
    # cursor = db.cursor()

# # or
# db_name2 = "oeo.db"
# db2 = sqlite3.connect(db_name2)
# cursor2 = db2.cursor()

# # with try/except
# with sqlite3.connect(db_name) as db:
    # try:
        # cursor = db.cursor()    
    # except:
        # print("Could not establish connection to {0}".format(db_name))
        
    
    
# # or
# db_name2 = "oeo.db"
# try:
    # db2 = sqlite3.connect(db_name2)
    # cursor2 = db2.cursor()   
# except:
    # print("Could not establish connection to {0}".format(db_name))
    
    
validatedbname(db_name)
checkifexists(db_name)
createdb(db_name)

PYTHON ARGPARSER

Basic module for argument parsing. 1. 2. 3. 4. 5. 6. 7. 8.
# -*- coding: utf-8 -*-



# - h or --help are included default

import argparse
parser = argparse.ArgumentParser()
parser.parse_args()

aaaa.md

```java
public void foo()
{
    int a= 0;
}
```

Test snippet

This is a test snippet.
<div></div>

This is a test Gist

This is a test Gist
public class {
}

Mysql_Role_Back

START TRANSACTION;

ALTER TABLE applicant DROP COLUMN type;
/* if you need Role back run(ROLLBACK)*/
ROLLBACK;
/*or*/
COMMIT ;

compose function

Compose n functions with a value
const compose = (...fns) => (val) => fns.reduce((acc, current) => current(acc), val);

const addTen = val => val + 10;
const multiplyByTen = val => val * 10;


const res = compose(
    addTen,
    multiplyByTen,
    multiplyByTen,
    multiplyByTen,
    addTen,
)(2);

console.log(res);

Environment PhpStorm

## Fix watchers
- `cat /proc/sys/fs/inotify/max_user_watches`
- `sudo nano /etc/sysctl.conf`

```txt
fs.inotify.max_user_watches = 524288
```

- `sudo sysctl -p`

Discretization(Two ways)

rt
/**
 *  离散化a数组
 *  lower_bound 函数在前闭后开区间上寻找第一个大于等于val的位置
 *  相同元素离散化后仍然相同 
 * 
 */

const int maxn=1e5+10;
int a[maxn], t[maxn];
int n;

scanf("%d",&n);
for(int i=1; i<=n; i++)
    scanf("%d",a[i]),t[i]=a[i];
sort(t+1,t+n+1);
m=unique(t+1,t+1+n)-t-1; //m为不重复的元素的个数
for(int i=1; i<=n; i++)
    a[i]=lower_bound(t+1,t+1+m,a[i])-t;

flatten dictionary

Write a function to flatten a nested dictionary by joining the keys with a dot
def flatten(init, lkey=''):
    ret = {}
    for rkey,val in init.items():
        key = lkey+rkey
        if isinstance(val, dict):
            ret.update(flatten(val, key + '.'))
        else:
            ret[key] = val
    return ret


print(flatten({'a': 1, 'b': {'1': 2, '2': 3}, 'c': 4}))

Nowcoder 第五场 暑期多校训练2018

rt
// 概率+期望
// https://www.nowcoder.com/acm/contest/143#question

#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <stack>
#include <math.h>
#include <string>
#include <algorithm>
#include <time.h>

#define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) (x&-x)
#define foe(i, a, b) for(int i=a; i<=b; i++)
#define fo(i, a, b) for(int i=a; i<b; i++);
#pragma warning ( disable : 4996 )

using namespace std;
typedef long long LL;
inline LL LMax(LL a, LL b) { return a>b ? a : b; }
inline LL LMin(LL a, LL b) { return a>b ? b : a; }
inline LL lgcd(LL a, LL b) { return b == 0 ? a : lgcd(b, a%b); }
inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; }  //a*b = gcd*lcm
inline int Max(int a, int b) { return a>b ? a : b; }
inline int Min(int a, int b) { return a>b ? b : a; }
inline int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
inline int lcm(int a, int b) { return a / gcd(a, b)*b; }  //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = 998244353;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int maxk = 1e6 + 5;
const int maxn = 1e5+5;

int n;
LL inv;
LL sum[maxn];
struct node {
	int p, siz, id;
	bool operator<(const node& a)
	{ return siz > a.siz; }
}dia[maxn];

///a^b % m
LL getM(LL a, LL b, LL m)
{
	LL _sum = 1, base = a;
	
	while (b)
	{
		if (b&1)
			_sum = (_sum*base)%m;
		base = (base*base)%mod;
		b >>= 1;
	}
	return _sum;
}

void add(int x, int v)
{
	while (x <= maxn)
	{
		sum[x] = (sum[x]*v)%mod;
		x += lowbit(x);
	}
}

LL query(int x)
{
	LL _sum = 1;
	while (x)
	{
		_sum = (_sum*sum[x])%mod;
		x -= lowbit(x);
	}
	return _sum;
}

void init()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &dia[i].p, &dia[i].siz);
		dia[i].id = i;
		sum[i] = 1;
	}
	sum[0] = 1;
	sort(dia+1, dia+1+n);

	inv = getM(100, mod-2, mod);
}

int main()
{
	init();

	LL ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans = (ans + (query(dia[i].id-1) * ((dia[i].p*inv) % mod)) % mod) % mod;
		add(dia[i].id, inv*(100-dia[i].p)%mod);
		//cout << sum[1] << endl;
	}
	printf("%lld\n", ans);
	return 0;
}

Binary Indexed Tree

An incredible data structure to quickly caculate sum of array perfix (even postfix and even sum of product).
#define lowbit(x) (x&-x)

int sum( int x )
{
    int ret = 0;
    while( x > 0 )
        {    ret += bit[x]; x -= lowbit(x); }
    return ret;
}

void add( int x, int d )
{
    while( x <= N )
        { bit[x] += d; x += lowbit(x); }
}

QuickPow

caculate a^b% mod m with quickpow algorithm
/*return a^b % m*/

LL getM(LL a, LL b, LL m)
{
	LL _sum = 1, base = a;
	
	while (b)
	{
		if (b&1)
			_sum = (_sum*base)%m;
		base = (base*base)%mod;
		b >>= 1;
	}
	return _sum;
}

编辑距离

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。 总共三种操作方法:插入一个字符、删除一个字符、替换一个字符 样例: 给出 work1="mart" 和 work2="karma" 返回 3 定义一个dp[word1.length() + 1][word2.length() + 1],dp[i][j]表示word1前i个字符变成word2前j个字符的最少操作次数。 分三种情况讨论: (1)增加字符   dp[i][j] = dp[i][j - 1] + 1   dp[i][j - 1] -> dp[i][j] 只需要再增加一个word2[j]字符 (2)删除字符   dp[i][j] = dp[i - 1][j] + 1   dp[i - 1][j] -> dp[i][j] 直接删除第i个字符 (3)替换字符   分为两种情况:   word1[i] == word2[j]时,不需要做任何操作,dp[i][j] = dp[i - 1][j - 1]   word1[i] != word2[j]时,替换当前字符,dp[i][j] = dp[i - 1][j - 1] + 1
public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            // 从i个字符变成0个字符,需要i步(删除)
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            // 从0个字符变成i个字符,需要i步(增加)
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // word1[i] == word2[j]
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // word1[i] != word2[j]  求三种操作的最小值
                    dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("mart","karma"));
    }
}

01背包问题

有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和? 状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。 Pi表示第i件物品的价值。 决策:为了背包中物品总价值最大化,第i件物品应该放入背包中吗 ?
public class Bag {
    public static int maxValue(int[] P, int[] W, int packageW)  {
        int[][] dp = new int[P.length + 1][packageW + 1];
        for (int i = 0; i <= P.length; i++) {
            for (int j = 0; j <= packageW; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (j < W[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - W[i - 1]] + P[i - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[P.length][packageW];
    }

    public static void main(String[] args) {
        System.out.println(maxValue(new int[]{2,2,6,5,4},new int[]{6,3,5,4,6},10));
    }
}