dfs和多线程

算法

连接奶牛

利用全排列来代替爆搜，因为每个走法只能对应一个全排列，简化了搜索。只需要判断每次全排列是否能从第一个点走到第二个点，以及在连续的三个点中方向是否改变，以及能否从最后一个点回到原点。get函数来判断两个点的方向。

利用pair数对

来存储奶牛的坐标。

get函数
    int get(PII a, PII b) {
    if(a.first != b.first && a.second != b.second)  return -1;
    if(a.first == b.first) {
        if(b.second > a.second)
            return 0;
        else
            return 2;
    }
    if(b.first > a.first)
        return 1;
    return 3;
}
	// 0，1，2，3分别表示上右下左四个方向
	

	int res = 0;
    do {
        int last = get(p[0], p[q[1]]);
        if(last == -1)  continue;
        for(int i = 1; i <= n; i ++) {
            int d = get(p[q[i]], p[q[i + 1]]);
            if(d == -1 || d == last) {
                last = -1;
                break;
            }
            last = d;
        }
        if(last != -1)  res ++;
        
    }while(next_permutation(q + 1, q + 1 + n));

三条线

普通枚举：

枚举四种情况，三条横线，三条竖线，两横一竖，两竖一横。三条横线只要枚举所有点的横坐标是否超过了三种；三条竖线同理；两横一竖枚举一竖的那种情况，将在同一竖的点去掉之后，在枚举剩下的点是否能用两条横线包括；两竖一横同理。

$dfs$ 枚举：

最多枚举八种情况，所以时间复杂度只有$O(8N)$ ，从任意一个点开始枚举，每个点只有两种情况，分别枚举横线和竖线的情况，只要枚举超过三条还没有将所有的点包括就是不成功；另外用哈希表来存储横线和竖线。

int dfs(int u, int cnt) {
    if(cnt > 3)     return 0;
    if(u == n)      return 1;
    
    if(row.count(p[u].y) || col.count(p[u].x))
        return dfs(u + 1, cnt);
        
    row.insert(p[u].y);
    if(dfs(u + 1, cnt + 1))     return 1;  // 如果有解返回1
    row.erase(p[u].y);
    
    col.insert(p[u].x);
    if(dfs(u + 1, cnt + 1))     return 1; // 如果有解返回1
    col.erase(p[u].x);
    
    return 0; // 如果无解返回1
}

java

线程

1.线程通常都有五种状态，创建、就绪、运行、阻塞和死亡。

2.调用start（）方法后，线程的状态是“就绪”状态，而不是“运行”状态；线程要等待CPU调度，不同的JVM有不同的调度算法，线程何时被调度是未知的。因此，start（）方法的被调用顺序不能决定线程的执行顺序。

3.run（）方法的执行是不是需要线程调用start（）方法。

龟兔赛跑

public class Race implements Runnable{

    private static String winner;

    @Override
    public void run() {
        for(int i = 0; i <= 100; i ++) {

            if(Thread.currentThread().getName().equals("兔子") && i % 10 == 0) {
                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

            }

            boolean flag = gameOver(i);
            if(flag) {
                break;
            }

            System.out.println(Thread.currentThread().getName() + "-->跑了" + i);
        }
    }

    private boolean gameOver(int steps) {
        if(winner != null) {
            return true;
        }
        if(steps >= 100) {
            winner = Thread.currentThread().getName();
            System.out.println("winner is" + winner);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Race race = new Race();
        new Thread(race, "兔子").start();
        new Thread(race, "乌龟").start();
    }

}

多线程实现callable接口

实现callable接口
    public class TestCallable implements Callable<Boolean> {
        public Boolean call() throws Exception {
            WebDownLoad webdownload = new WebDownLoad();
            webdownload.download(url, name);
            System.out.println("下载了文件名为：" + name);
        // 有个返回值
            return true; 
        }
    }
    
    
    多线程的使用方式
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        TestCallable t1 = new TestCallable("https://img.alicdn.com/imgextra/i4/1015368528/O1CN01pAlQgg2CrsOImdwzJ_!!1015368528.jpg","1.jpg");
        TestCallable t2 = new TestCallable("https://img.alicdn.com/imgextra/i4/1015368528/O1CN01pAlQgg2CrsOImdwzJ_!!1015368528.jpg","2.jpg");
        TestCallable t3 = new TestCallable("https://img.alicdn.com/imgextra/i4/1015368528/O1CN01pAlQgg2CrsOImdwzJ_!!1015368528.jpg","3.jpg");

    	// 创建执行服务
        ExecutorService ser = Executors.newFixedThreadPool(3);

    	// 提交执行
        Future<Boolean> r1 = ser.submit(t1);
        Future<Boolean> r2 = ser.submit(t2);
        Future<Boolean> r3 = ser.submit(t3);

    	// 获取结果
        Boolean rs1 = r1.get();
        Boolean rs2 = r2.get();
        Boolean rs3 = r3.get();

    	// 关闭服务
        ser.shutdownNow();
    }

`Lambda`

Lambda表达式只能有一行代码的情况下才能简化成为一行（将花括号去掉），如果有多行，那么就用代码快包裹；前提是接口为函数式接口；多个参数也可以去掉参数类型，要去掉就都去掉，必须加上括号。

public class TestLambda {

    public static void main(String[] args) {
        ILike like = new Like();
        like.like();

        like = () ->{
            System.out.println("i like you2");
        };

        like.like();

        // 如果有参数
       /* like = (int a) -> {
            System.out.println("i like you3");
        };*/
        
        // 有参数可以简化1
        /* like = (a) -> {
            System.out.println("i like you3");
        };*/
        
        // 有参数可以简化2
        /* like = a -> {
            System.out.println("i like you3");
        };*/

        	
    }
}

//定义一个函数式接口（任何接口，如果只包含唯一一个抽象方法，那么它就是一个函数式接口）
interface ILike {
    void like();
}

// 实现类
class Like implements ILike {
    @Override
    public void like() {
        System.out.println("I like you forever");
    }
}

输出结果为：
    I like you forever
	i like you2

线程停止

建议使用一个标志位进行终止变量，当flag=false，则终止线程运行。

public class TestStop implements Runnable{

    private Boolean flag = true;

    @Override
    public void run() {
        int i = 0;
        while(flag) {
            System.out.println("run ----- Thread" + i ++);
        }
    }

    public void stop() {
        this.flag = false;
    }

    public static void main(String[] args) {
        TestStop testStop = new TestStop();

        new Thread(testStop).start();

        for (int i = 0; i < 100; i++) {
            System.out.println("main---run---" + i);
            if(i == 90) {
                testStop.stop();
                System.out.println("线程已停止----");
            }
        }
    }
}

礼让线程

让当前正在执行的线程暂定，但不阻塞，用yield（）方法，Thread.yield();

join线程插队

join合并线程，待此线程执行完成后，在执行其他线程，其他线程阻塞，可以看成是插队。

线程优先级

线程的优先级用数字表示，范围从1~10；默认是5，数字越大优先级越高；可以用setPriority()和getPriority()分别修改和获取线程优先级。

优先级的设定建议在start()调度前。

Thread.MIN_PRIORITY= 1;

Thread.MAX_PRIORITY= 1;

Thread.NORM_PRIORITY= 1;