[TOC]

1. 操作系统

1.1 进程-线程

进程：所有的应用程序都需要进入内存中执行。点击应用程序，程序进入内存，进入内存的程序叫进程。

线程：线程属于进程，是进程中的一个执行单元，负责程的执行。是通往cpu的通道。效率高，多个线程之间互不影响。

进程只是一个容器

image.png
计算机真实的运行是一条条线程

image.png

程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，他就永远存在。程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后应撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是。

进程的状态

进程的状态

1.1.1 同步与互斥

同步	互斥
直接制约关系	间接制约关系
两个人相约去什么地方；速度有差异，一定情况下等待	千军万马过独木桥

1.1.2 线程调度

分时调度
所有线程轮流使用CPU的使用权，平均分配每个线程占用CPU的时间。
抢占式调度
优先让优先级高的线程使用CPU，如果线程的优先级相同，呢么就会随机选择一个来执行（线程随机性），java为抢占式调度。

1.1.3 死锁

image.png

1.2 存储

image.png

1.2.1 页式存储组织

image.png

1.2.2 段式存储组织

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存a 存，段的长度可以不一样

image.png

1.2.3 段页式存储组织

image.png

1.5 寻址

寻址空间

32位→4G
64位→2^64→1019Bytes
64位JVM→可以使用更大的内存，但是需要重新编译

1.6 列题

image.png

2. 网络基础

image.png

2.1 网络传输

丢包，重复包
出错
乱序不安全
- 中间人攻击
- 窃取
- 篡改

2.2 滑动窗口协议

image.png

2.3 三次握手，四次挥手

image.png

2.4 列题

image.png

3. 数据库

image.png

4. 程序设计语言基础

4.1 语言的分类

1. 类型检查
·  编译时：C，C++，Java，Go…
·  运行时：Python，Perl，JavaScript，Ruby…

比如说：java中 int a 那么a就永远是一个int ，Python中 a 一开始可以是int 后来可能是String 所以只有他们只有在运行的时候才能知道是什么类型

4.2 运行/编译

· 编译为机器代码运行：C,C++，….
好处是编译快
· 编译为中间代码，在虚拟机运行：Java，C#，….
为什么在虚拟机中运行呢，因为为提高跨平台的能力
· 解释执行：Python，Perl，javaScript，….

有时候说java即使编译型也是解释型语言
因为java不将代码编译成 .class字节码文件就无法运行，所以是编译型语言。
但是java编译后不能直接运行，必须在JVM中才能解释运行，所以是解释型语言。

4.3 编程范式

· 面向过程： C， Visual， Basic，…. 现在已经不怎么使用了
· 面向对象：Java，C#，C++，Scala，…. 现在的主流，大型商业使用的系统还是面向对象比较容易胜任。
· 函数式：Haskell，Erlang，…. 具体的场合有比较容易的使用

4.4 数据类型

1. boolean，byte，char 
    java中char是两个字节，都是使用的Unicode
    C中的char是一个字节
2. short，int，long，float，double
    java中int是32位，long是64位的
3. String，Enum，Array
    他们是Object派生下来的，像String可以+ 在C++中可以自定义+号，但是在java中不可以
4. Object

32位int的范围 -2^31~232-1
浮点数

image.png

浮点数比较          
    a==b   是不可以的           
    Math.abs(a-b)<eps?          
    使用BigDecimal算钱          
    
    
Primitive type vs object 
原始类型VS对象类型

    Primitive type: int,long,float….
        值类型 
        用 a==b 判断相等
    Object : Integer,Long,Float,String…. 
        引用类型
        用a==b判断是否为同一个Object
        用a.equals(b)    java7出现了Object.equals(a,b) 解决了a为null的情况

4.5 列题

image.png

5. 编码技巧

数学归纳法
用于证明断言对所以自然数成立
1. 证明对于N=1成立
2. 证明N>1时：如果对于N-1成立，那么对N成立
3.

5.1 递归

递归的书写方法：        
    ○ 严格定义递归函数的作用，包括参数，返回值，Side-effect（全局状态）        
    ○ 先一般，后特殊        
    ○ 每次调用必须缩小问题规模      
    ○ 每次问题规模缩小程度必须为1

5.1.1 将list转换为链表

image.png

5.1.2 链表反转

image.png

5.1.3 列出所有组合

image.png

5.2 循环控制

定义循环不变式，斌仔循环体每次结束后保持循环不变式
先一般，后特殊
每次必须向前推进循环不变式中涉及的变量值
每次推进的规模必须为1

5.2.1 链表反转

image.png

5.2.2 删除链表

image.png

5.2.3 二分查找

image.png

6. 数据结构

6.1 列表

数组：查询快，插入和删除慢
链表：删除快，查询慢
队列，栈

6.2 树

二叉查找树，左子树一定比节点小，右节点一定比节点大
二叉树
搜索树
堆/优先队列

6.2.1 二叉树的遍历

二叉树的遍历：
• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

image.png

前序遍历：ABDEGCF
中序遍历：DBGEACF
后序遍历：DGEBCFA
层次遍历：ABCDEFG

6.2.1 树对象结构

public class Tree {
    private final char value;
    private Tree left;
    private Tree right;

    public Tree(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public char getValue() {
        return value;
    }

    public Tree getLeft() {
        return left;
    }

    public void setLeft(Tree left) {
        this.left = left;
    }

    public Tree getRight() {
        return right;
    }

    public void setRight(Tree right) {
        this.right = right;
    }
}

6.2.2 初始化树

 public Tree create(){
        Tree tree = new Tree('A');
        tree.setRight(new Tree('C'));
        tree.getRight().setRight(new Tree('F'));

        tree.setLeft(new Tree('B'));
        tree.getLeft().setLeft(new Tree('D'));
        tree.getLeft().setRight(new Tree('E'));
        tree.getLeft().getRight().setLeft(new Tree('G'));

        return tree;
    }

6.2.3 test

 @Test
    public void test(){
        System.out.println("abcde".charAt(0));
        System.out.println("abcde".substring(0, 2));
        //ab
        System.out.println("abcde".indexOf('c'));
        //2
    }

6.2.4 遍历树

public class TreeShow {
    //先序遍历 Foreword
    public void foreword(Tree tree){
        if (tree==null){
            return;
        }
        System.out.print(tree.getValue());
        foreword(tree.getLeft());
        foreword(tree.getRight());
    }

    //中序遍历Medium
    public void medium(Tree tree){
        if (tree==null){
            return;
        }
        medium(tree.getLeft());
        System.out.print(tree.getValue());
        medium(tree.getRight());
    }

    //后序遍历Post
    public void post(Tree tree){
        if (tree==null){
            return;
        }
        post(tree.getLeft());
        post(tree.getRight());
        System.out.print(tree.getValue());
    }


    public static void main(String[] args){
        //初始化树
        Tree tree = new TreeCreate().create();

        TreeShow treeShow = new TreeShow();
        //先序遍历
        System.out.println("先序遍历");
        treeShow.foreword(tree);
        System.out.println();

        //中序遍历
        System.out.println("中序遍历");
        treeShow.medium(tree);
        System.out.println();

        //后序遍历
        System.out.println("后序遍历");
        treeShow.post(tree);
        System.out.println();

        //求后序遍历
        System.out.println("=============================");
        tree = new TreeCreate().getPost("ABDEGCF","DBGEACF");
        treeShow.post(tree);
        System.out.println();

        //求后序遍历
        System.out.println("=============================");
        String str = new TreeCreate().getPostString("ABDEGCF","DBGEACF");
        System.out.println(str);
        System.out.println();
    }
}

6.2.5 已知前序，中序求后序（生成树）

/**
     * 已知 前序遍历  中序遍历 求 后序遍历  方法一
     * 前序遍历：A BDEG CF
     * 中序遍历：DBGE A CF
     * 后序遍历：DGEBCFA
     * @Author chendpeng
     * @Description //TODO
     * @Date 17:01
     * @Param [foreword, medium]
     * @return com.looc.demo4.Tree
     **/
    public Tree getPost(String foreword,String medium){
        if (foreword.isEmpty()){
            return null;
        }
        //得到根节点
        char rootNode = (char) foreword.charAt(0);
        Tree tree = new Tree(rootNode);

        //拿到a的root节点的位置
        int rootIndex = medium.indexOf(rootNode);
        //左节点
        tree.setLeft(
                getPost(
                        foreword.substring(1,rootIndex+1),
                        medium.substring(0,rootIndex)));
        //右节点
        tree.setRight(
                getPost(
                        foreword.substring(rootIndex+1),
                        medium.substring(rootIndex+1)));
        return tree;
    }

6.2.6 已知前序，中序求后序（不生成树）


   /* * 前序遍历：A BDEG CF
     * 中序遍历：DBGE A CF
     * 后序遍历：DGEBCFA*/
    public String getPostString(String foreword, String medium){
        if (foreword.isEmpty()){
            return "";
        }
        //拿到根节点
        char rootChar = foreword.charAt(0);
        //拿到在中序遍历中的位置
        int rootIndex = medium.indexOf(rootChar);

        //左边
        String leftForeword = foreword.substring(1,rootIndex+1);
        String rightForeword = foreword.substring(rootIndex+1);

        //右边
        String leftMedium = medium.substring(0,rootIndex);
        String rightMedium = medium.substring(rootIndex+1);

        return getPostString(leftForeword,leftMedium)+
                getPostString(rightForeword,rightMedium)+
                rootChar;

    }