[TOC]
1. 操作系统
1.1 进程-线程
进程:所有的应用程序都需要进入内存中执行。点击应用程序,程序进入内存,进入内存的程序叫进程。
线程:线程属于进程,是进程中的一个执行单元,负责程的执行。是通往cpu的通道。效率高,多个线程之间互不影响。
-
进程只是一个容器
image.png -
计算机真实的运行是 一条条线程
image.png
程序是完成某个特定功能的一系列程序语句的集合,只要不被破坏,他就永远存在。程序是一个静态的概念,而进程是一个动态的概念,它由创建而产生,完成任务后应撤销而消亡;进程是系统进行资源分配和调度的独立单位,而程序不是。
- 进程的状态
1.1.1 同步与互斥
同步 | 互斥 |
---|---|
直接制约关系 | 间接制约关系 |
两个人相约去什么地方;速度有差异,一定情况下等待 | 千军万马过独木桥 |
1.1.2 线程调度
- 分时调度
所有线程轮流使用CPU的使用权,平均分配每个线程占用CPU的时间。 - 抢占式调度
优先让优先级高的线程使用CPU,如果线程的优先级相同,呢么就会随机选择一个来执行(线程随机性),java为抢占式调度。
1.1.3 死锁
image.png1.2 存储
image.png1.2.1 页式存储组织
image.png1.2.2 段式存储组织
段式存储:按用户作业中的自然段来划分逻辑空间,然后调入内存a 存,段的长度可以不一样
image.png
1.2.3 段页式存储组织
image.png1.5 寻址
寻址空间
- 32位→4G
- 64位→264→1019Bytes
- 64位JVM→可以使用更大的内存,但是需要重新编译
1.6 列题
image.png2. 网络基础
image.pngimage.png
2.1 网络传输
- 丢包,重复包
- 出错
- 乱序不安全
- 中间人攻击
- 窃取
- 篡改
2.2 滑动窗口协议
image.pngimage.png
2.3 三次握手,四次挥手
image.png image.png2.4 列题
image.png3. 数据库
image.png image.pngimage.png
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的范围 -231~232-1
浮点数
浮点数比较
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.png5. 编码技巧
数学归纳法
用于证明断言对所以自然数成立
1. 证明对于N=1成立
2. 证明N>1时:如果对于N-1成立,那么对N成立
3.
5.1 递归
递归的书写方法:
○ 严格定义递归函数的作用,包括参数,返回值,Side-effect(全局状态)
○ 先一般,后特殊
○ 每次调用必须缩小问题规模
○ 每次问题规模缩小程度必须为1
5.1.1 将list转换为链表
image.png5.1.2 链表反转
image.png5.1.3 列出所有组合
image.png5.2 循环控制
- 定义循环不变式,斌仔循环体每次结束后保持循环不变式
- 先一般,后特殊
- 每次必须向前推进循环不变式中涉及的变量值
- 每次推进的规模必须为1
5.2.1 链表反转
image.png5.2.2 删除链表
image.png5.2.3 二分查找
image.png6. 数据结构
6.1 列表
数组:查询快,插入和删除慢
链表:删除快,查询慢
队列,栈
6.2 树
二叉查找树,左子树一定比节点小,右节点一定比节点大
二叉树
搜索树
堆/优先队列
6.2.1 二叉树的遍历
二叉树的遍历:
• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历
前序遍历: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;
}
6.3 栈,队列,优先队列
• pusb(1);push(3);push(2);pop();pop();pop();
栈:2;3;1;
队列:1;3;2;
优先队列:1;2;3
• Map<K,V>/Set<K>
HashMap/HashSet →基于 k.hashCode()
TreeMap/TreeMap→基于 k implements Comparable
6.4 图
无向图
有向图
有向无环图
图的算法
深度优先遍历
广度优先遍历
拓扑排序
最短路径、最小生成树
6.4 列题
image.png7. 算法复杂度
image.pngimage.png
8. 面向对象
image.pngimage.png
image.png
image.png
image.png image.png
9. 设计模式
image.pngimage.png
网友评论