ds之并查集

发表于 2019-01-21 | 分类于 data structure | 阅读次数:

字数统计: 1.4k | 阅读时长 ≈ 6

六个关系网就能达到全世界


// quick_find.java

import java.io.File;
import java.util.Scanner;

public class UF {

    int count;   //连通分量数
    int[] id;    //每个数所属的连通分量

    public UF(int N) {   //初始化时，N个点有N个分量
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    //返回连通分量数
    public int getCount(){
        return count;
    }
    //查找x所属的连通分量
    public int find(int x){
        return id[x];
    }
    //连接p,q(将q的分量改为p所在的分量)
    public void union(int p,int q){
        int pID=find(p);
        int qID=find(q);
        for(int i=0;i<id.length;i++){
            if(find(i)==pID){
                id[i]=qID;
            }
        }
        count--;    //记得每进行一次连接，分量数减“1”
    }
    //判断p,q是否连接，即是否属于同一个分量
    public boolean connected(int p,int q){
        return find(p)==find(q);
    }

    public static void main(String[] args) throws Exception {

        //数据从外部文件读入，“data.txt”放在项目的根目录下
        Scanner input = new Scanner(new File("data.txt"));  
        int N=input.nextInt();
        UF uf = new UF(N);
        while(input.hasNext()){
            int p=input.nextInt();
            int q=input.nextInt();
            if(uf.connected(p, q)) continue;        //若p,q已属于同一连通分量不再连接，则故直接跳过
            uf.union(p, q);
            System.out.println(p+"-"+q);
        
        }
        System.out.println("总连通分量数："+uf.getCount());
    }

}

// quick_union.java

import java.io.File;
import java.util.Scanner;

public class UF {

    int count;   //连通分量数
    int[] id;    //每个数所属的连通分量

    public UF(int N) {   //初始化时，N个点有N个分量
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    //返回连通分量数
    public int getCount(){
        return count;
    }
    
    //查找x所属的连通分量
    public int find(int x){
        while(x!=id[x]) x = id[x];  //若找不到，则一直往根root回溯
        return x;
    }
    //连接p,q(将q的分量改为p所在的分量)
    public void union(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if(pID==qID) return ;
        id[qID]=pID;
        count--;
    }
    /*
    //查找x所属的连通分量
    public int find(int x){
        return id[x];
    }
    
    //连接p,q(将q的分量改为p所在的分量)
    public void union(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if(pID==qID) return ;
        for(int i=0;i<id.length;i++){
            if(find(i)==pID){
                id[i]=qID;
            }
        }
        count--;    //记得每进行一次连接，分量数减“1”
    }
    */
    //判断p,q是否连接，即是否属于同一个分量
    public boolean connected(int p,int q){
        return find(p)==find(q);
    }

    public static void main(String[] args) throws Exception {

        //数据从外部文件读入，“data.txt”放在项目的根目录下
        Scanner input = new Scanner(new File("data.txt"));  
        int N=input.nextInt();
        UF uf = new UF(N);
        while(input.hasNext()){
            int p=input.nextInt();
            int q=input.nextInt();
            if(uf.connected(p, q)) continue;        //若p,q已属于同一连通分量不再连接，则故直接跳过
            uf.union(p, q);
            System.out.println(p+"-"+q);
        
        }
        System.out.println("总连通分量数："+uf.getCount());
    }

}

// weighted_uf.java

import java.io.File;
import java.util.Scanner;

public class UF {

    int count; // 连通分量数
    int[] id; // 每个数所属的连通分量
    int[] sz;

    public UF(int N) { // 初始化时，N个点有N个分量
        count = N;
        sz = new int[N];
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;

        for (int i = 0; i < N; i++)
            sz[i] = 1;

    }

    // 返回连通分量数
    public int getCount() {
        return count;
    }

    // 查找x所属的连通分量
    public int find(int x) {
        while (x != id[x])
            x = id[x]; // 若找不到，则一直往根root回溯
        return x;
    }

    // 连接p,q(将q的分量改为p所在的分量)
    public void union(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID)
            return;

        if (sz[p] < sz[q]) {    //通过结点数量，判断树的大小并将小树并到大树下
            id[p] = qID;
            sz[q] += sz[p];
        } else {
            id[q] = pID;
            sz[p] += sz[q];
        }
        count--;
    }

    /*
     * //查找x所属的连通分量 public int find(int x){ return id[x]; }
     * 
     * //连接p,q(将q的分量改为p所在的分量) public void union(int p,int q){ int pID=find(p);
     * int qID=find(q); if(pID==qID) return ; for(int i=0;i<id.length;i++){
     * if(find(i)==pID){ id[i]=qID; } } count--; //记得每进行一次连接，分量数减“1” }
     */
    // 判断p,q是否连接，即是否属于同一个分量
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public static void main(String[] args) throws Exception {

        // 数据从外部文件读入，“data.txt”放在项目的根目录下
        Scanner input = new Scanner(new File("data.txt"));
        int N = input.nextInt();
        UF uf = new UF(N);
        while (input.hasNext()) {
            int p = input.nextInt();
            int q = input.nextInt();
            if (uf.connected(p, q))
                continue; // 若p,q已属于同一连通分量不再连接，则故直接跳过
            uf.union(p, q);
            System.out.println(p + "-" + q);

        }
        System.out.println("总连通分量数：" + uf.getCount());
    }

}

网络通信（比如：是否需要在通信点p,q建立通信连接）
媒体社交（比如：向通一个社交圈的朋友推荐商品）
数学集合（比如：判断元素p,q之后选择是否进行集合合并）

六度分隔理论，该理论认为世界上任何互不相识的两人，只需要很少的中间人就能够建立起联系。

哈佛大学心理学教授斯坦利·米尔格拉姆于1967年根据这个概念做过一次连锁信实验，尝试证明平均只需要6步就可以联系任何两个互不相识的美国人。

leetcode-714 含有手续费的买卖股票时机

发表于 2019-01-19 | 分类于 leetcode | 阅读次数:

字数统计: 75 | 阅读时长 ≈ 1

leetcode 含有手续费的买卖股票时机


class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        n = len(prices)
        if n < 2:
             return 0
        ans, minimum = 0, prices[0]
        for i in xrange(1, n):
            if prices[i] < minimum:
                minimum = prices[i]
            elif prices[i] > minimum + fee:
                ans += prices[i] - fee - minimum
                minimum = prices[i] - fee
        return ans

py连接mysql的条条大路

发表于 2019-01-19 | 阅读次数:

字数统计: 55 | 阅读时长 ≈ 1

1.mysqldb
最古老的 c api开发

2.mysqlclient
也不支持asyncio

3.pymysql

纯python开发的mysql连接库

4.aiomysql

需要异步访问数据库时就可以使用此库

5.mysql-connector-python

建议使用3和4

dl之15种回归

发表于 2019-01-10 | 阅读次数:

字数统计: 0 | 阅读时长 ≈ 1

es6总结

发表于 2019-01-10 | 分类于 frontend | 阅读次数:

字数统计: 1.2k | 阅读时长 ≈ 4

1.变量声明let和const

我们都是知道在ES6以前，var关键字声明变量。无论声明在何处，都会被视为声明在函数的最顶部(不在函数内即在全局作用域的最顶部)。这就是函数变量提升例如:

function aa() {
    if(bool) {
        var test = 'hello man'
    } else {
        console.log(test)
    }
  }

现在的情况下则是
我们通常用let和const来声明，let表示变量、const表示常量。let和const都是块级作用域。怎么理解这个块级作用域？

在一个函数内部
在一个代码块内部

function aa() {
    if(bool) {
       let test = 'hello man'
    } else {
        //test 在此处访问不到
        console.log(test)
    }
  }

let的作用域是在它所在当前代码块，但不会被提升到当前函数的最顶部。

2.模版字符串


const name = 'lux'
console.log(`hello ${name}`) //hello lux 基本的字符串格式化。将表达式嵌入字符串中进行拼接。用${}来界定。

多行字符串或者字符串一行行拼接。ES6反引号(``)直接搞定。
// es5
var msg = "Hi \
man!
"
// es6
const template = `<div>
    <span>hello world</span>
</div>`
    
    
    
// es5
var msg = "Hi \
man!
"
// es6
const template = `<div>
    <span>hello world</span>
</div>`

3.函数

为函数提供默认值

function action(num = 200) {
        console.log(num)
    }
    
action() //200
action(300) //300

箭头函数

箭头函数最直观的三个特点。

不需要function关键字来创建函数
省略return关键字
继承当前上下文的 this 关键字

4.拓展的对象功能

键值对简写
省掉function关键字

5.更方便的数据访问解构

6.展开运算符

const number = [1,2,3,4,5]
    const [first, ...rest] = number
    console.log(rest) //2,3,4,5
    //对象
    const user = {
        username: 'lux',
        gender: 'female',
        age: 19,
        address: 'peking'
    }
    const { username, ...rest } = user
    console.log(rest) //{"address": "peking", "age": 19, "gender": "female"
}

7.import export

1.当用export default people导出时，就用 import people 导入（不带大括号）

2.一个文件里，有且只能有一个export default。但可以有多个export。

3.当用export name 时，就用import { name }导入（记得带上大括号）

4.当一个文件里，既有一个export default people, 又有多个export name 或者 export age时，导入就用 import people, { name, age } 

5.当一个文件里出现n多个 export 导出很多模块，导入时除了一个一个导入，也可以用import * as example

8.promise

在promise之前代码过多的回调或者嵌套，可读性差、耦合度高、扩展性低。通过Promise机制，扁平化的代码机构，大大提高了代码可读性；用同步编程的方式来编写异步代码，保存线性的代码逻辑，极大的降低了代码耦合性而提高了程序的可扩展性。

setTimeout(function() {
  console.log(1)
}, 0);
new Promise(function executor(resolve) {
  console.log(2);
  for( var i=0 ; i<10000 ; i++ ) {
    i == 9999 && resolve();
  }
  console.log(3);
}).then(function() {
  console.log(4);
});
console.log(5);

首先先碰到一个 setTimeout，于是会先设置一个定时，在定时结束后将传递这个函数放到任务队列里面，因此开始肯定不会输出 1 。

然后是一个 Promise，里面的函数是直接执行的，因此应该直接输出 2 3 。

然后，Promise 的 then 应当会放到当前 tick 的最后，但是还是在当前 tick 中。

因此，应当先输出 5，然后再输出 4 。

最后在到下一个 tick，就是 1 。

“2 3 5 4 1”

9.迭代器

生成器（ generator）是能返回一个迭代器的函数。生成器函数也是一种函数，最直观的表现就是比普通的function多了个星号*，在其函数体内可以使用yield关键字,有意思的是函数会在每个yield后暂停。

这里生活中有一个比较形象的例子。咱们到银行办理业务时候都得向大厅的机器取一张排队号。你拿到你的排队号，机器并不会自动为你再出下一张票。也就是说取票机“暂停”住了，直到下一个人再次唤起才会继续吐票。

OK。说说迭代器。当你调用一个generator时，它将返回一个迭代器对象。这个迭代器对象拥有一个叫做next的方法来帮助你重启generator函数并得到下一个值。next方法不仅返回值，它返回的对象具有两个属性：done和value。value是你获得的值，done用来表明你的generator是否已经停止提供值。继续用刚刚取票的例子，每张排队号就是这里的value，打印票的纸是否用完就这是这里的done。