ARTS_第3周

Algorithm

Review

Tip

  1. 注册退出进程时的回调
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <stdlib.h>

void exit1(void);
void exit2(void);

int main(int argc, char* argv[]) {
    if (atexit(exit1) != 0) {
        printf("attext exit1 error\n");
        return 1;
    }

    if (atexit(exit1) != 0) {
        printf("attext exit1 error\n");
        return 1;
    }

    if (atexit(exit2) != 0) {
        printf("attext exit2 error\n");
        return 1;
    }

    printf("main return\n");

    return 0;
}

void exit1() {
    printf("call exit1\n");
}

void exit2() {
    printf("call exit2\n");
}
  1. 设置和获取环境变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>

void print_env(char*);

int main(int argc, char* argv[]) {
    if (putenv("MING=9988") != 0) {
        printf("putenv error\n");
        return 1;
    }
    print_env("MING");

    if (unsetenv("MING") < 0) {
        printf("unsetenv error\n");
        return 1;
    }
    print_env("MING");

    return 0;
}

void print_env(char* name) {
    char* path = getenv(name);
    if (path) {
        printf("%s\n", path);
    } else {
        printf("not found\n");
    }
}
  1. 异常控制setjmp/longjmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <setjmp.h>

jmp_buf jmpbuffer;

void func1();
void func2();

int main(int argc, char* argv[]) {
    int val = setjmp(jmpbuffer);
    if (val == 0) {
        printf("000 setjmp val=%d\n", val);
    } else {
        printf("setjmp val=%d\n", val);
        return 1;
    }

    func1();
    printf("main return\n");
    return 0;
}

void func1() {
    printf("call func1 start\n");
    func2();
    printf("call func1 end\n");
}

void func2() {
    printf("call func2 start\n");
    longjmp(jmpbuffer, 10);
    printf("call func2 end\n");
}
  1. fork
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <unistd.h>

int main(int argc, char const *argv[])
{
    //setbuf(stdout, NULL);
    printf("start...\n");
    fflush(stdout);
    printf("nani...\n");

    int a = 0;
    pid_t pid = fork();
    if (pid == 0) {
        a = 10;
    } else {
        a--;
        sleep(2);
    }

    printf("pid=%d, a=%d\n", getpid(), a);
    return 0;
}
  1. vfork
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int main(int argc, char const *argv[])
{
    printf("vfork begin");

    int a = 0;
    pid_t pid = vfork();
    if (pid < 0) {
        printf("vfork error\n");
    }

    if (pid == 0) {
        a = 10;
        //sleep(2);
        exit(0);
    }

    printf("pid=%d, a=%d\n", getpid(), a);
    return 0;
}

6.wait

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <sys/wait.h>
#include <stdlib.h>
#include <unistd.h>

void pr_exit(int status);

int main(int argc, char const *argv[])
{
    int status;
    pid_t pid = fork();    
    if (pid < 0) {
        printf("fork error\n");
    } else if (pid == 0) {
        printf("child work pid=%d\n", pid);
        //exit(4);
        //abort();
        status /= 0;
    }

    if (wait(&status) != pid) {
        printf("wait error\n");
    }

    pr_exit(status);
    return 0;
}

void pr_exit(int status) {
    if (WIFEXITED(status)) {
        printf("WIFEXITED\n");

    } else if (WIFSIGNALED(status)) {
        printf("WIFSIGNALED\n");

    } else if (WIFSTOPPED(status)) {
        printf("WIFSTOPPED\n");
        
    } else if (WIFCONTINUED(status)) {
        printf("WIFCONTINUED\n");
    }
}
  1. waitpid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdlib.h>

int main(int argc, char const *argv[])
{
    pid_t pid = fork();
    if (pid < 0) {
        printf("fork error\n");
    } else if (pid == 0) {
        printf("child proc start\n");
        sleep(4);
        printf("child proc end\n");
        // if ((pid = fork()) > 0) {
        //     exit(0);
        // } else {
        //     printf("child 2 proc start ppid=%d\n", getppid());
        //     sleep(3);
        // }
        exit(0);
    }

    int status;
    if (waitpid(pid, &status, 0) == 0) {
        printf("waitpid error\n");
    }

    printf("waitpid end ppid=%d\n", getppid());
    return 0;
}
  1. exec
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// show_argc
#include <stdio.h>
#include <unistd.h>

int main(int argc, char const *argv[])
{
    for (int i=0; i<argc; i++) {
        printf("argv[%d]=%s\n", i, argv[i]);
    }

    for (char** p=__environ; *p != 0; p++) {
        printf("%s\n", *p);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char const *argv[])
{
    char* env[] = {
        "MING=333000",
        "PATH=.",
        NULL
    };
    pid_t pid = fork();
    if (pid < 0) {
        printf("fork error\n");
    } else if (pid == 0) {
        //if (execle("/home/ming/_work/apue/chapter8/show_argc", "aaaa", "bbbb", (char*)0, env) < 0) {
        if (execle("show_argc", "aaaa", "bbbb", (char*)0, env) < 0) {
            printf("execle error\n");
        }
    }

    if (waitpid(pid, NULL, 0) == 0) {
        printf("waitpid error\n");
    }

    printf("main end\n");
    return 0;
}

Share

  • 经济状态

  1. 难知如阴，最近黄金冲破1800美金，感觉经济越来越动荡了。

  • linux文件系统

  1. 文件系统是什么？

  2. 文件系统为什么存在？
    因为unix系统把所有东西当作IO的目标，一切皆可IO，因为IO操作的目标分很多类，所以unix抽象了不同的类型的文件。文件太多了，查找和修改就会不方便，因此，要有一个管理系统，这就是文件系统。

  3. 文件系统的数据结构是怎样的？
    文件系统的的数据结构，主要分三部分：

    • 文件描述符表
    • 文件状态表
    • 文件inode表

  • 很多时候，你觉得你是在写代码，但其实，你并不知道自己在干什么。

ARTS_第2周

Algorithm

Review

Exceptions in Java

  1. java异常和错误的区别:

    • 错误是严重的，不能被try catch的
    • 异常可用被try catch, 然后继续执行的

  2. jvm怎样处理异常:

    1. 递归搜索调用栈的代码，找到匹配异常的处理代码
    2. 如果找到，就执行对应的handle
    3. 如果没找到，就执行默认的handle，默认就是在标准输出打印异常信息(异常对象里包含了异常的信息)

  3. 程序员怎样处理异常
    bala bala…一些基础的废话

Tip

  1. 拷贝文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <unistd.h> 
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>

#define FILE_MODE   (S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)
#define BUFFER_SIZE 4096

int main(int argc, char* argv[]) {
    int srcfd = open(argv[1], O_RDONLY);
    int destfd = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, FILE_MODE);
    printf("srcfd=%d\n", srcfd);
    printf("destfd=%d\n", destfd);

    int n;
    char buf[BUFFER_SIZE];
    while ((n = read(srcfd, buf, BUFFER_SIZE)) > 0) {
        if (write(destfd, buf, n) != n) {
            printf("write error\n");
            exit(1);
        }
    }

    if (n < 0) {
        printf("read error\n");
    }

    if (close(srcfd) == -1 || close(destfd) == -1) {
        printf("close file error\n");
    }

    exit(0);
}

  1. 以字符查看文件

    1
    2
    3
    4
    ming@ming_server:~/_work/apue/chapter3$ od -c 11 
    0000000   n   e   w   f   d   =   1  \n   1   2   3   4   5   6   7   8
    0000020   9  \n
    0000022

  2. 文件描述符重定向，demo是把标准输出重定向到argv[1]的文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include <unistd.h>
    #include <stdio.h>
    #include <fcntl.h>
    #include <stdlib.h>

    #define BUFFER_SIZE 4096

    int main(int argc, char* argv[]) {
        int fd = open(argv[1], O_RDWR);
        if (fd == -1) {
            printf("open error\n");
            exit(1);
        }

        int newfd = dup2(fd, STDOUT_FILENO);
        if (newfd == -1) {
            printf("dup2 error\n");
            exit(2);
        }

        printf("newfd=%d\n", newfd);

        int n;
        char buf[BUFFER_SIZE];
        while ((n = read(STDIN_FILENO, buf, BUFFER_SIZE)) > 0) {
            printf("%s", buf);
        } 

        if (n < 0) {
            printf("read error\n");
        }

        return 0;
    }

  3. 查看进程的虚拟内存

    1
    2
    3
    4
    5
    6
    7
    8
    #include <stdio.h>

    int main() {
        printf("pid=%ld\n", getpid());
        getchar();
        printf("exit");
        return 0;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    ming@ming_server:~/_work$ cat /proc/29858/maps 
    561c252dc000-561c252dd000 r-xp 00000000 08:02 424368                     /home/ming/_work/apue/chapter3/a.out
    561c254dc000-561c254dd000 r--p 00000000 08:02 424368                     /home/ming/_work/apue/chapter3/a.out
    561c254dd000-561c254de000 rw-p 00001000 08:02 424368                     /home/ming/_work/apue/chapter3/a.out
    561c267fd000-561c2681e000 rw-p 00000000 00:00 0                          [heap]
    7f4f196a3000-7f4f1988a000 r-xp 00000000 08:02 136752                     /lib/x86_64-linux-gnu/libc-2.27.so
    7f4f1988a000-7f4f19a8a000 ---p 001e7000 08:02 136752                     /lib/x86_64-linux-gnu/libc-2.27.so
    7f4f19a8a000-7f4f19a8e000 r--p 001e7000 08:02 136752                     /lib/x86_64-linux-gnu/libc-2.27.so
    7f4f19a8e000-7f4f19a90000 rw-p 001eb000 08:02 136752                     /lib/x86_64-linux-gnu/libc-2.27.so
    7f4f19a90000-7f4f19a94000 rw-p 00000000 00:00 0 
    7f4f19a94000-7f4f19abb000 r-xp 00000000 08:02 131706                     /lib/x86_64-linux-gnu/ld-2.27.so
    7f4f19cb2000-7f4f19cb4000 rw-p 00000000 00:00 0 
    7f4f19cbb000-7f4f19cbc000 r--p 00027000 08:02 131706                     /lib/x86_64-linux-gnu/ld-2.27.so
    7f4f19cbc000-7f4f19cbd000 rw-p 00028000 08:02 131706                     /lib/x86_64-linux-gnu/ld-2.27.so
    7f4f19cbd000-7f4f19cbe000 rw-p 00000000 00:00 0 
    7fff83fcb000-7fff83fec000 rw-p 00000000 00:00 0                          [stack]
    7fff83ff9000-7fff83ffc000 r--p 00000000 00:00 0                          [vvar]
    7fff83ffc000-7fff83ffe000 r-xp 00000000 00:00 0                          [vdso]
    ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

  4. fcntl, 获取文件状态标志

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include <stdio.h>
     #include <fcntl.h>

     int main(int argc, char* argv[]) {
         int val = fcntl(atoi(argv[1]), F_GETFL);
         if (val == -1) {
             printf("fcntl error");
             return 1;
         }

         switch (val & O_ACCMODE) {
             case O_RDONLY:
                 printf("O_RDONLY");
                 break;
             case O_WRONLY:
                 printf("O_WRONLY");
                 break;
             case O_RDWR:
                 printf("O_RDWR");
                 break;
             default:
                 break;
         }
         printf("\n");
         getchar();
         return 0;
     }

  5. fcntl, 设置文件状态标志

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <stdio.h>
    #include <fcntl.h>

    int main(int argc, char* argv[]) {
        int fd = open(argv[1], O_RDWR);
        if (fd == -1) {
            printf("open error");
            return 0;
        }

        set_fl(fd, O_APPEND);

        int res = dprintf(fd, "aaaaa\n");
        printf("res=%d\n", res);
        return 0;
    }

    void set_fl(int fd, int flags) {
        int val = fcntl(fd, F_GETFL);
        printf("get=%d\n", val);
        if (val == -1) {
            printf("get error");
            return 0;
        }

        val |= flags; 
        printf("val=%d\n", val);
        int res = fcntl(fd, F_SETFL, val);
        if (res == -1) {
            printf("set error");
        }
    }

  6. 如果以O_APPEND打开文件，lseek只对读生效，每次写，会自动seek到文件末尾

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include <stdio.h>
    #include <fcntl.h>
    #include <unistd.h>

    #define BUFFERSIZE 4096

    int main(int argc, char* argv[]) {
        int fd;
        if ((fd = open(argv[1], O_RDWR | O_APPEND)) == -1) {
            printf("open error\n");
            return 1;
        }

        char buf[BUFFERSIZE];
        int n = read(fd, buf, BUFFERSIZE);
        if (n < 0) {
            printf("read error\n");
            return 2;
        }
        printf("pre seek: %s\n", buf);

        if (lseek(fd, 10, SEEK_SET) == -1) {
            printf("lseek error");
            return 3;
        } 

        n = read(fd, buf, BUFFERSIZE);
        if (n < 0) {
            printf("read error\n");
            return 2;
        }
        printf("after seek: %s\n", buf);

        dup2(fd, STDOUT_FILENO);

        printf("\nnani\n");

        return 0;
    }

  7. 获取文件类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <sys/stat.h>

int main(int argc, char* argv[]) {
    struct stat buf;
    for (int i=1; i<argc; i++) {
        printf("%s: ", argv[i]);
        if (stat(argv[i], &buf) < 0) {
            printf("lstat error");
            continue;
        }

        if (S_ISREG(buf.st_mode)) {
            printf("regular");
        } else if (S_ISDIR(buf.st_mode)) {
            printf("dir");
        } else if (S_ISCHR(buf.st_mode)) {
            printf("chr");
        } else if (S_ISBLK(buf.st_mode)) {
            printf("blk");
        } else if (S_ISFIFO(buf.st_mode)) {
            printf("fifo");
        } else if (S_ISLNK(buf.st_mode)) {
            printf("link");
        } else if (S_ISSOCK(buf.st_mode)) {
            printf("sock");
        } else {
            printf("other");
        }
        printf("\n");
    }
    return 0;
}
  1. 判断是否有访问权限
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>

int main(int argc, char* argv[]) {
    if (access(argv[1], R_OK) == 0) {
        printf("read ok\n");
    } else {
        printf("access error\n");
    }

    if (open(argv[1], O_RDONLY) < 0) {
        printf("open error\n");
    } else {
        printf("open ok\n");
    }
    return 0;
}
  1. 文件权限掩码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <fcntl.h>
#include <sys/stat.h>

#define RWRWRW (S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH | S_IWOTH)

int main(int argc, char* argv[]) {
    umask(0);
    if (creat("foo", RWRWRW) < 0) {
        printf("foo error");
    }

    umask(S_IRGRP | S_IROTH | S_IWOTH);
    if (creat("bar", RWRWRW) < 0) {
        printf("bar error");
    }

    return 0;
}

  1. 文件系统的数据结构
    主要分4个部分:

    1. 文件描述符表, 包括索引和文件表的指针
    2. 文件表, 字段包括文件状态标记，文件当前偏移，inode指针
    3. inode节点，包括文件权限，block指针，读写block的时间，修改inode的时间
    4. block节点，主要包含数据

  2. 标准库的io
    标准库的io主要是对系统调用的封装，之所以要封装，是为了效率，因为每次系统调用的开销太大。封装主要是加了缓冲，分为三种缓冲：

    • 全缓冲
    • 行缓冲
    • 不缓冲
      只有满足flush的条件或缓冲区满的时候，才调用系统调用，写入内核的缓冲。

  3. 内存其实也可用被当作文件，进行读写，定位等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <string.h>

#define BUFFER_SIZE 4096

int main(int argc, char* argv) {
    char buf[BUFFER_SIZE];
    memset(buf, '\0', BUFFER_SIZE);

    FILE* fp = fmemopen(buf, BUFFER_SIZE, "w+");
    if (!fp) {
        printf("fmemopen error");
        return 1;
    }

    printf("111->%s\n", buf);
    getchar();

    fprintf(fp, "hello world");
    fflush(fp);
    printf("222->%s\n", buf);

    getchar();

    return 0;
}

Share

  • 到目前为止(看完了前5章)，apue这本书中，主要讲了IO，包括文件操作，目录操作，内核中文件的数据结构，文件的权限和用户属性等，层次主要包括：系统调用和标准库的实现。
  • 其实对于一个unix进程来说，能干的事，全都包括在系统调用里，而IO是很重要的一部分，因为对于unix来说，所有跟读写相关的，全都被抽象成文件，比如：磁盘，内存，网卡等。之所以设计成这样，就是为了简化编程，统一成一类接口。其实，对于这种抽象也很好理解，就是把纷繁复杂的东西，做分类，然后，把自己要干的事，做成几个基本的原子操作。

ARTS_第1周

Algorithm

1.leecode300最长递增子序列

  • 标准的动态规划问题，也就是使用dp数组，保存了从[0,i]的最长递增子序列，避免了子问题的重复计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lengthOfLIS(int[] nums) {
    int size = nums.length;
    if (size == 0) return 0;

    int[] dp = new int[size];
    for (int i=0; i<size; i++) {
        dp[i] = 1;
    }

    for (int i=1; i<size; i++) {
        for (int j=0; j<i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
    }

    int max = 0;
    for (int i=0; i<size; i++) {
        max = Math.max(dp[i], max);
    }
    return max;
}
  • 对于这道题，如果想使用递归+备忘录的方式做，也可以，只不过有点别扭，因为无论是递归还是递推，都要把每个位置的最长上升子序列的长度求出来
  • 另外，这道题的递归，其实比较诡异，因为一般情况，递归是使用前一种状态，能够推导出下一种状态，但是这道题，是使用子问题中的多种状态，才能推导出当前状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int lengthOfLIS(int[] nums) {
    int size = nums.length;
    if (size == 0) return 0;

    int[] dp = new int[size];
    for (int i=0; i<size; i++) {
        dp[i] = 1;
    }

    for (int i=0; i<size; i++) {
        help(nums, i);
    }

    int max = 0;
    for (int i=0; i<size; i++) {
        max = Math.max(dp[i], max);
    }
    return max;
}

private int help(int[] nums, int index) {
    if (index == 0) return 1;
    if (mem[index] >= 1) return mem[index];
    int max = 0;
    for (int i=0; i<index; i++) {
        if (nums[i] < nums[index]) {
            max = Math.max(help(nums, i), max);
        }
    }
    mem[index] = max + 1;
    return mem[index]
}

2.最大连续子数组的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxSubArray(int[] nums) {
    if (nums.length == 0) return 0;

    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    for (int i=1; i<nums.length; i++) {
        if (dp[i-1] > 0) {
            dp[i] = dp[i-1] + nums[i];
        } else {
            dp[i] = Math.max(dp[i-1], nums[i]);
        }
    }

    int max = dp[0];
    for (int i=1; i<nums.length; i++) {
        if (dp[i] > max) {
            max = dp[i];
        }
    }
    return max;
}
  • 与上一题类似，差别就是递推公式，只用到了前一个dp状态

3. 01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private static int knapsack01(int n, int maxW, int[] w, int[] p) {
    int[][] dp = new int[n][maxW+1];
    for (int i=0; i<n; i++) {
        for (int j=0; j<maxW+1; j++) {
            dp[i][j] = -1;
        }
    }
    
    // 初始化第一行
    dp[0][0] = 0;
    if (w[0] <= maxW) dp[0][w[0]] = p[0]; 

    for (int i=1; i<n; i++) {
        // 不选i
        for (int j=0; j<=maxW; j++) {
            if (dp[i-1][j] < 0) continue;
            dp[i][j] = dp[i-1][j];
        }

        // 选i
        for (int j=0; j<=maxW; j++) {
            if (dp[i-1][j] < 0) continue;
            int x = j + w[i]; 
            if (x > maxW) break; 
            dp[i][x] = Math.max(dp[i-1][x], dp[i-1][j]+p[i]);
        }
    }

    int maxP = 0;
    for (int i=0; i<maxW+1; i++) {
        if (dp[n-1][i] > maxP) {
            maxP = dp[n-1][i];
        }
    }
    return maxP;
}

4.杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
    }
}

// 极客时间，从顶到底的最短路径
private int minLen(Node root, Map<Node, Integer> mem) {
    if (root == null) return 0;
    if (mem.containsKey(root)) return mem.get(root);
    int res = root.val + Math.min(minLen(root.left, mem), minLen(root.right, mem));
    mem.put(root, res);
    return res;
}

参考1
dp问题分类

Review

Difference between Java IO and Java NIO

这篇文章介绍java IO和NIO的区别，主要包含如下差别

  1. 分别在java.io包和java.nio包
  2. io面向流, nio面向缓冲区
  3. io是阻塞的，nio非阻塞
  4. Channels, io不可用，nio可用
  5. io处理字节，nio处理数据块
  6. Selectors, io没有多路复用的概念，nio可以多路复用

Tip

  • 开始读apue，先下了apue的source code，编译，然后拷贝apue.h和error.c到/usr/include/。

  • 跑了三个demo：

  1. 简单实现ls命令

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <apue.h>
    #include <error.c>
    #include <dirent.h> 

    int main(int argc, char* argv[]) {
        DIR* dp;
        struct dirent* dirp;

        if (argc != 2) {
            err_quit("usage: ls dir_name");
        }

        if ((dp = opendir(argv[1])) == NULL) {
            err_sys("can't open %s", argv[1]);
        }

        while ((dirp = readdir(dp)) != NULL) {
            printf("%s\n", dirp->d_name);
        }

        closedir(dp);
        exit(0);
    }

  2. 用POSIX接口，read/write标准输入输出, ./in_out < infile > outfile

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    #include <apue.h>
    #include <error.c>

    #define BUF_SIZE 100

    int main(void) {
        int n;
        char buf[BUF_SIZE];

        while ((n = read(STDIN_FILENO, buf, BUF_SIZE)) > 0) {
            int count = write(STDOUT_FILENO, buf, n);
            if (count != n) {
                err_sys("write error!");
            }
        }

        if (n < 0) {
            err_sys("read error");
        } 
        exit(0);
    }

  3. 使用标准库函数getc/putc（stdio.h), 做标准输入输出, 与2的区别就是，库函数中自带了缓冲，最终也是调用read／write 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include <apue.h> 
    #include <error.c>

    int main() {
        int c;
        while ((c = getc(stdin)) != EOF) {
            if (EOF == putc(c, stdout)) {
                err_sys("putc EOF");
            }
        }

        if (ferror(stdin)) {
            err_sys("stdin EOF");
        }
        exit(0);
    }

  4. 进程相关，fork，execlp，getpid/getppid。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include <apue.h>
    #include <error.c>

    #define BUFFER_SIZE 100

    int main() {
        long pid;
        char buf[BUFFER_SIZE];
        int status;

        printf("%% ");
        while ((fgets(buf, BUFFER_SIZE, stdin)) != NULL) {
            int len = strlen(buf);
            if (buf[len-1] == '\n') {
                buf[len-1] = 0;
            }

            pid = fork();
            if (pid == 0) {
                execlp(buf, buf, (char*)0);
                err_ret("could'nt execute: %s", buf);
                exit(127);
            } else if (pid < 0) {
                err_sys("fork error!");
            }

            if ((pid = waitpid(pid, &status, 0)) < 0) {
                err_sys("waitpid error");
            }
            printf("%% ");
        }

        exit(0);
    }

  5. 出错处理，strerr, perror

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <stdio.h>
    #include <string.h>
    #include <error.c>
    #include <errno.h>

    int main(int argc, char* argv[]) {
        fprintf(stderr, "EACCES: %s\n", strerror(EACCES));
        errno = ENOENT;
        perror(argv[0]);
        exit(0);
    }

  6. 用户id和组id

    1
    2
    3
    4
    5
    6
    #include <apue.h>

    int main() {
        printf("uid is %d, gid is %d\n", getuid(), getgid());
        exit(0);
    }

  7. 信号处理

    1
    2
    3
    4
    5
    6
    7
    if (signal(SIGINT, sig_int) == SIG_ERR) {
        err_sys("signal error");
    }

    void sig_int(int sig) {
        printf("\nsig_int-->%d\n", sig);
    }

Share

并发是他妈什么鬼

  • 站在单核的cpu的汇编指令层，是不存在并发的，指令永远是一条一条执行的，不可能同时执行两条指令。
  • 站在操作系统的层面，因为cpu的速度太快，不想等其他速度慢的设备（比如IO），所以操作系统制造了进程和线程的概念。
  • 站在应用层，操作系统提供了进程，为了方便的共享内存，在进程内，OS提供了线程。
  • 因为同一个进程内，多线程共享虚拟内存，由于并发的不确定性，所以太容易导致多个线程读写了同一块内存，出现意料之外的错误。因此，出现了锁的概念。
  • 锁按照从严格到宽松的顺序，互斥锁，信号量，临界区，读写锁，CAS。

NIO是他妈什么鬼

参考1
参考2
参考3

树相关leecode题目分类

遍历

  1. 树的深度优先遍历，前中后序（DFS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void dfs(TreeNode root) {
    if (root == null) return;
    list.add(root.val);
    dfs(root.left);
    dfs(root.right);
}

private void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    list.add(root.val);
    dfs(root.right);
}

private void dfs(List<Integer> list, TreeNode root) {
    if (root == null) return;
    dfs(list, root.left);
    dfs(list, root.right);
    list.add(root.val);
}
  1. 树的广度遍历（BFS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (queue.size() > 0) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        while (queue.size() > 0) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue1.offer(node.left);
            }  
            if (node.right != null) {
                queue1.offer(node.right);
            }  
        }
        result.add(list);
        queue = queue1;
    }
    return result;
}
  1. 树的最大深度
1
2
3
4
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
  1. 判断树是否对称
1
2
3
4
5
6
7
8
9
10
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSame(root.left, root.right);
}

private boolean isSame(TreeNode root1, TreeNode root2) {
     if (root1 == null && root2 == null) return true;
     if (root1 == null || root2 == null) return false;
     return root1.val == root2.val && isSame(root1.left, root2.right) && isSame(root1.right, root2.left);
}
  1. 路径总和
1
2
3
4
5
6
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    int dx = sum - root.val;
    if (dx == 0 && root.left == null && root.right == null) return true;
    return hasPathSum(root.left, dx) || hasPathSum(root.right, dx);
}
  1. 树最近公共根节点
1
2
3
4
5
6
7
8
9
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) return root;
    TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
    TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
    if (leftNode != null && rightNode != null) return root;
    if (leftNode == null) return rightNode;
    return leftNode;
}
  1. 平衡二叉树
  2. 比较两棵树是否相同

重建

  1. 根据中序遍历和后序遍历，重建二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        List<Integer> inorderList = new ArrayList<>();
        for (int one : inorder) {
            inorderList.add(one);
        }
        List<Integer> postorderList = new ArrayList<>();
        for (int one : postorder) {
            postorderList.add(one);
        }
        return subBuildTree(inorderList, postorderList);
    }

    public TreeNode subBuildTree(List<Integer> inorder, List<Integer> postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return null;
        int val = postorder.get(postorder.size()-1);
        TreeNode root = new TreeNode(val);
        int index = inorder.indexOf(val);
        root.left = subBuildTree(inorder.subList(0, index), postorder.subList(0, index));
        root.right = subBuildTree(inorder.subList(index+1, inorder.size()), postorder.subList(index, postorder.size()-1));
        return root;
    }
}
  1. 根据前序遍历和中序遍历，重建二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null;
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return build(map, preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}

private TreeNode build(HashMap<Integer, Integer> map, int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
    if (preLeft > preRight) return null;
    int val = preorder[preLeft];
    TreeNode node = new TreeNode(val);
    if (preLeft == preRight) return node; 

    int index = map.get(val);
    int leftSize = index - inLeft;
    int rightSize = inRight - index;
    node.left = build(map, preorder, preLeft+1, preLeft+leftSize, inorder, inLeft, inLeft+leftSize-1);
    node.right = build(map, preorder, preLeft+1+leftSize, preLeft+leftSize+rightSize, inorder, index+1, index+rightSize);
    return node;
}

修剪

  1. 同层连接所有节点
1
2
3
4
5
6
7
8
9
10
11
12
13
public Node connect(Node root) {
    if (root == null) return null;
    conn(root.left, root.right);
    return root;
}

private void conn(Node root1, Node root2) {
    if (root1 == null || root2 == null) return;
    root1.next = root2;
    conn(root1.left, root1.right);
    conn(root1.right, root2.left);
    conn(root2.left, root2.right);
}
  1. 连接同层所以节点，非完全二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Node connect(Node root) {
    if (root == null) return null;

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (queue.size() > 0) {
        Node pre = null;
        Queue<Node> tmp = new LinkedList<>();
        while (queue.size() > 0) {
            Node node = queue.poll();
            if (pre != null) pre.next = node;
            pre = node;
            if (node.left != null) tmp.offer(node.left);
            if (node.right != null) tmp.offer(node.right);
        }
        queue = tmp;
    }
    return root;
}

二叉搜索树

  1. 验证二叉搜索树
1
2
3
4
5
6
7
8
9
boolean valid = true;
TreeNode pre;
private void dfs(TreeNode root) {
    if (!valid) return;
    if (root == null) return;
    dfs(root.left);
    if (pre != null && pre.val >= root.val) valid = false;
    pre = root;
    dfs(root.right);
  1. 二叉搜索树迭代器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class BSTIterator {

    Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        if (root == null) return;
        stack.push(root);
        TreeNode p = root.left;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        TreeNode p = node.right;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        return node.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.empty();
    }
}
  1. 搜索BST
1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode searchBST(TreeNode root, int val) {
    TreeNode p = root;
    while (p != null) {
        if (p.val > val) {
            p = p.left;
        } else if (p.val < val) {
            p = p.right;
        } else {
            return p;
        }
    }
    return null;
}
  1. BST插入节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    TreeNode p = root;
    while (p != null) {
        if (val > p.val) {
            if (p.right == null) {
                p.right = new TreeNode(val);
                break;
            }
            p = p.right;
        } else {
            if (p.left == null) {
                p.left = new TreeNode(val);
                break;
            }
            p = p.left;
        } 
    }
    return root;
}

RSA数学原理

计算出公钥和私钥

  • 随便找两个质数p和q
1
假设：p=3，q=11
  • 求出n
1
n = p * q = 33
  • 求欧拉函数
1
y = (p-1)*(q-1)=20
  • 公钥e的约束(例如：e可以取7，满足条件1和2）
    1. 1<e<y
    2. e与y互为质数
  • 私钥d的约束（例如：d可以取3，满足条件1）
    1. (e*d)%y = 1

加密的方法

已知：e，n，m（明文），计算密文c
m的e次幂%n=c

解密的方法

已知：d,n,c(密文），计算m
c的d次幂%n=m

为什么RSA是安全的

e,n,c==>d==>y==>p,q==>则需要对n质因数分解

http1.1是怎样升级到http2.0的？

**** 背景知识1：****

  1. http协议是是基于tcp之上的协议。
  2. http2.0之前的版本是http1.1

*** 目标：***

  • 让client与server用http2.0通信

*** 问题推演：***

*** 在不知道server端的http版本的情况下，想要使用http2.0，需要什么手段？***

  • 因为通信之前，server和client都彼此不知道对方的http的协议版本，所以client只能先使用http1.1尝试通信
  • 因为client想要升级到http2.0，所以需要与server端协商使用http的版本，目前有两种协商协议：NPN和ALPN

*** NPN和ALPN的区别是什么？***

  • NPN 是服务端发送所支持的 HTTP 协议列表，由客户端选择；而 ALPN 是客户端发送所支持的 HTTP 协议列表，由服务端选择；
  • NPN 的协商结果是在 Change Cipher Spec 之后加密发送给服务端；而 ALPN 的协商结果是通过 Server Hello 明文发给客户端；

*** 用wireshark抓包（ALPN）发现，app中okhttp的请求，已经是http2.0了，为什么log中还显示http1.1？***

  • 因为添加拦截器（HttpLoggingInterceptor）的层级不对。
  1. addInterceptor添加的拦截器，打印请求行log时，长链接还没连上。
  2. addNetworkInterceptor是在协商之后才打印日志。
git

修改git log中的author邮箱 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/bin/sh
git filter-branch --env-filter '
OLD_EMAIL="ming.liu@dfs168.com"
CORRECT_NAME="liumingmad"
CORRECT_EMAIL="liumingmad@gmail.com"
if [ "$GIT_COMMITTER_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_COMMITTER_NAME="$CORRECT_NAME"
    export GIT_COMMITTER_EMAIL="$CORRECT_EMAIL"
fi
if [ "$GIT_AUTHOR_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_AUTHOR_NAME="$CORRECT_NAME"
    export GIT_AUTHOR_EMAIL="$CORRECT_EMAIL"
fi
' --tag-name-filter cat -- --branches --tags