JVM

1.JVM(Java Virtual Machine)

1.1 虚拟机(二进制字节码运行环境)

1. 系统虚拟机(完全是对物理计算机的仿真)
    提供了可运行完整操作系统的软件平台

2. 程序虚拟机(专门为执行单个计算机程序)
    典型代表就是java虚拟机,java虚拟机中执行的指令我们称为Java字节码指令

3. 作用
    3.1 一次编译,到处运行(java语言的可移植性)
    3.2 自动内存管理
    3.3 自动垃圾回收功能

1.2 jvm位置

1.3 jvm整体结构(背)

1.4 java代码执行流程

1.5 jvm架构模型(栈/寄存器指令集架构)

1. 栈的指令集架构
2. 寄存器的指令集架构

1.6 jvm生命周期(三个状态)

1. 启动
    通过引导类加载器创建一个初始类完成

2. 执行
    执行java程序(程序执行时jvm执行,程序结束时jvm结束)

3. 退出
    1. 程序正常执行结束
    2. 程序执行中遇到异常/错误而异常终止
    3. 由于操作系统出现错误/java虚拟机进程终止 
    4. 某线程调用Runtime类/System类的exit()方法/Runtime类的halt()方法

2.内存结构

类加载器子系统+虚拟机栈+执行引擎


3.类加载器子系统

3.1 类加载过程(3步)

  • ①加载:根据查找路径找到相应的class文件,然后放入堆

  • ②验证:检查加载的class文件的正确性

    四种验证:【①文件格式验证;②元数据验证;③字节码验证;④符号引用验证】

  • ③准备:给类中的静态变量分配内存空间

    三种情况:【①static int b=10;②static final int c=20[基本类型];③static final string d=’b’[引用类型]】

  • ④解析:虚拟机将常量池中的符号引用替换为直接引用的过程。符号引用就理解为一个标示,而在直接引用直接指向内存中的地址

  • ⑤初始化:对静态变量和静态代码块执行初始化工作

4.双亲委派机制(类加载器机制)

举例(Car类)

引用在栈,具体存在堆

加载器分类(4个)

1. 虚拟机自带的加载器
2. 启动类(根)加载器
3. 扩展类加载器
4. 应用程序(系统类)加载器

//注意:
    如果方法.getParent()返回null有以下两种情况:
        1. 不存在
        2. java程序获取不到(是其他语言写的 需要native修饰符修饰)

双亲委派机制(保证安全)

1. 类加载器收到类加载请求    

2. 向上委托给父类加载器去完成,一直向上委托,直到启动类加载器
    APP(应用类) --> EXC(扩展类) --> BOOT(最终执行)    

3. 启动加载器检查是否能够加载当前类
    3.1 能加载  --> 结束
    3.2 不能加载 --> 抛出异常,通知子加载器进行加载

4. 可能会弹出class not found

5.沙箱(sandbox)安全机制

基本组件(字节码校验器/类加载器)

1. 字节码校验器
    确保java类文件遵守java语言规范(核心类[java javax开头]的类文件不会经过)

2. 类加载器
    2.1 防止恶意代码干涉善意代码 (双亲委派机制)
    2.2 守护被信任的类库边界  (双亲委派机制)
    2.3 将代码归入保护域  (双亲委派机制)

6.Native关键字(底层c语言的库)

Java的作用范围达不到,要去找C语言的库—底层是C/C++语言编写

1. 进入本地方法栈
2. 调动本地方法接口 JNI(Java native interface) --扩展java的使用(融合不同编程语言为java所用)

7.PC寄存器(Program Counter Register)

每个线程都有一个程序计数器,是线程私有的一个指针


8.方法区(Method Area)

所有线程共享(共享区间)

1. 方法区: 静态变量(Static)  常量(Final)  类信息(构造方法,接口定义)  运行时的常量池
2. 堆内存: 实例变量

9.栈(Stack - 先进后出)

喝多了吐就是栈,吃多了拉就是队列(FIFO)


10.HotSpot

三种JVM

1. Sun公司的HotSpot
2. BEA JRockit
3. IBM J9 VM

HotSpot虚拟机的查看:


11.堆(Heap)

一个JVM只有一个堆内存

image-20241115104934776

11.1 堆内存三个区域

1. 新生区(伊甸园区Ed )  Young/New
2. 养老区  old
3. 永久区(Jdk8之后叫元空间)  Perm  

GC主要在新生区和养老区

1.新生区—类诞生、成长、死亡

1. 伊甸园区   --所有对象都在这new
2. 幸存区(幸存区0,幸存区1) 

2.养老区

新生区没有被淘汰清除的活下来了

3.永久区—常驻内存,存放java运行时环境/class信息

不存在垃圾回收!关闭JVM虚拟机就会释放区域内存

jdk1.6前    永久代 常量池在方法区
jdk1.7      永久化 常量池在堆 (慢慢的退化 -- 去永久代)
jdk1.8      无永久代 常量池在元空间

12.GC(垃圾回收)

12.1 复制算法(新生代使用)

谁空了谁就是to区域

从一个区域复制到另外一个(from和to的交换)

12.2 标记清除算法(标记-清除)

先标记,然后没有标记的进行清除,最后会造成内存碎片

12.3 标记压缩算法(标记-清除-压缩)

1. 标记 - 清除 - 压缩(重复步骤好几次,但是消耗大)
2. 标记清除几次 - 压缩(一次性将碎片整理)

12.4 分代收集算法(分代不同的解决方案)

1. 年轻代 : 存活率低 -> 复制算法
2. 老年代 : 存活率大 -> 标记清除(内存碎片不多) + 标记压缩混合 

算法总结

1. 内存效率    
    复制算法 > 标记清除算法 > 标记压缩算法(时间复杂度)

2. 内存整齐度
    复制算法(没有内存碎片) = 标记压缩算法(没有内存碎片) > 标记清除算法(有内存碎片)

3. 内存利用率
    标记清除算法 = 标记压缩算法 > 复制算法(有to区域浪费)

JVM后续

参考视频:

https://www.bilibili.com/video/BV1iJ411d7jS

Mysql复习

1.SQL基础知识

1.1 select执行顺序

顺序 说明 是否必须使用
select all(默认)/distinct(找不同) 要返回的列/表达式
from 检索数据的表 仅仅在从表中选择数据时使用
where 行级别过滤
group by 分组说明 仅仅在按照组计算聚集时使用
having 组级别过滤(选分组)
order by asc(默认)/desc(降序) 输出排序顺序
*limit * 输出行数(limit x,y 就是从x行输出到y行)

image-20231121192527482

1.2 选择数据库(USE指令)

输入 : USE crashcourse 
输出 : Database changed

1.3 展示数据库和表(SHOW指令)

1. 数据库、表、列、用户、权限等信息被存储在数据库和表中(一般内部表不让直接访问)
2. 展示数据库: show databases;
3. 展示数据库内表: show tables; (返回当前选择的数据库内可用表的列表)
4. 展示表列: show columns from XXX;
5. 展示服务器状态信息: show status
6. 展示特定数据库mysql语句: show create database
7. 展示特定表mysql语句: show create table
8. 展示授予用户安全权限: show grants
9. 展示服务器错误/警告信息: show errors / show warnings 

1.4 数据模型

1.4.1 关系型数据库(RDBMS)

image-20231116220225940

1.5 Mysql客户端启动方式

image-20231117212521219

1.6 SQL通用语法和分类

1.6.1 语法

image-20231117212650151

1.6.2 分类

image-20231117212751196

2.SQL四大语法

2.1 DDL 数据定义语言

image-20231119211435655

2.2 DML 数据操作语言

image-20231119215028254

2.3 DQL 数据查询语言

image-20231121192527482

2.4 DCL 数据控制语言

image-20231122162805124


3.检索数据(select语句)

3.1 检索单列

//检索user表中name列
    select name 
    from user      

3.2 检索多列(逗号分隔)

//检索user表中name还有id和price列
    select name,id,price 
    from user

3.3 检索所有列(通配符[*])

//检索user表中所有列
    select * 
    from user

3.4 检索不同行的值(distinct关键字)

//检索user表中不同的name列
    select distinct name 
    from user

满足条件

1. 必须放在列名前面  ---   distinct 列名    
2. 只能返回不同的值(唯一)
3. 应用于所有列

3.5 检索前n行(limit子句)

//检索user表中name列的前五行
    select name
    from user
    limit 5  //不多于5行

//为得出下一个5行,可以指定要检索的开始行和行数
    select name 
    from user
    limit 5,5  //从第五行开始检索5行 

注意事项

1. 行0  ---  检索出来的第一行是行0 (limit 1,1将检索出第二行)
2. 行数不够  ---   有多少输出多少
3. 替换语句:  limit 4 offset 3 <--> limit 3,4 (从行3开始取4行)

3.6 检索特定表的列

//检索user表内的name列
    select user.name
    from user

排序检索数据(order by子句)

单列排序

//从user表中查name列(根据字母顺序排序)
    select name
    from user
    order by name; //order by子句

多列排序(逗号分隔)

//先对三个列查询出来之后对name和price列进行排序
    select name,id,price
    from user
    order by name,price  //首先根据名字name  然后根据价格price

//注意:
    对于上述例子输出:仅在多个行具有相同的name值时才对price值进行排序(name列中所有值都是唯一,就不会按照price排序)

指定排序方向(desc/asc关键字)

//desc按照Z到A降序   --  
//asc按照A到Z升序(默认)

//根据价格降序排序产品(最贵的排在前面)
    select price,id,name
    from user
    order by price desc; //根据price排序 desc说明是降序

//多个列排序
    select price,id,name
    from user
    order by price desc,id; //只有price降序!!!

//找到列中某几个行
    select price,id,name
    from user
    order by price desc  //desc是降序(从高到低)
    limit 1;  //找到最贵的!!!

过滤数据(where子句)

举例

//语句顺序: select -- from -- where -- order by -- limit 
    select distinct name //找到不同的name
    from user
    where name='宋亚翔'  //限定找name是宋亚翔
    order by name desc  //根据name降序排序
    limit 5,5; //从第五行开始输出五行

where子句操作符

检查单值

//检测出name叫宋亚翔的一行
    select name,price
    from user
    where name='宋亚翔';

不匹配检查(不等于操作符)

//在user表中找id不是1003的结果
    select id,name
    from user
    where id<>1003; //where id!=1003

范围值检查(between)

//在user标准中找price在5-10的信息 展示名字和对应价格
    select name,price
    from user
    where price between 5 and 10;

空值检查(is null)

//检查有没有人的价格是null
    select name
    from user
    where price is null;

数据过滤(组合where子句)

多个子句就需要用and/or方式使用

and操作符

//找到名字为宋亚翔并且购买物品价格小于10的所有产品的名字和价格
    select name,id
    from user
    where id='宋亚翔' and price<=10;

or操作符

//检索名字由任一个指定叫宋亚翔或者刘伟的产品name和id
    select name,id
    from user
    where id='宋亚翔' or id='刘伟';

or和and优先级

优先级: and > or (适当给与()区分)

//两者共同使用必须用括号()区分
    select name,price
    from user
    where (id='宋亚翔' or id='刘伟') and price>=10;

in操作符(功能和or一样)

//检索名字是宋亚翔或者刘伟的信息根据name升序排序出name和price
    select name,price
    from user
    where id in('宋亚翔','刘伟')
    order by name;

//in操作符优点:
    1. 使用长的合法选项清单时,in操作符的语法更清楚而且直观
    2. 使用in操作符,计算次序更容易管理
    3. in操作符速度执行更快
    4. in能动态建立where子句

not操作符

//检索名字除宋亚翔和刘伟之外的所有信息根据name升序排序出name和price
    select name,price
    from user
    where id not in('宋亚翔','刘伟')
    order by name;

通配符过滤(like操作符)

%(0-n个字符)

百分号%可以匹配0/1/n个字符(不能匹配null)

//找到jet起头的产品
    select id,name
    from user
    where name like 'jet%'; //找到 jetxxxx 形式

//找到jet在中间的产品
    select id,name
    from user
    where name like '%jet%'; //找到 XXXjetxXX 形式

_(单个字符)

下划线_总能匹配一个字符(不能多也不能少)

//找到jet前面有一个字符的结果  (1jet 2jet等等)
    select id,name
    from user
    where name like '_jet'; //找到 Xjet形式

正则表达式搜索(regexp)

正则表达式用来匹配文本特殊的串(字符集合)

基本字符匹配(‘X’)

//检索列name包含文本1000的所有行
    select name 
    from user
    where name regexp '1000'  //regexp替换了like位置
   //where name regexp '.1000' //匹配任意一个字符(1000S 2000)
    order by name;

//总结
    1. 使用关键字regexp --> like
    2. 匹配不区分大小写:  可以使用binary区分大小写(默认不区分)
    3.  . 用于匹配单个字符

进行or匹配( | )

//匹配1000或者2000的结果
    select name
    from user
    where name regexp '1000|2000'
    order by name;

匹配单个字符([])

[] 等价于 | 等价于 or (三者都是)

//匹配1或者2或者3 
    select name
    from user
    where name regexp '[123]Ton' //[123]Ton是[1|2|3]Ton缩写
    order by name;

匹配一个/多个字符( - )

//匹配0到9 [0123456789]等价于[0-9]
    select name
    from user
    where name regexp '[1-9]Ton' //匹配数字0到9
    order by name;

匹配特殊字符( \\前导 )

//  \\-表示查找-
    select name
    from user
    where name regexp '\\-'
    order by name;   

找特殊字符必须要\转义(表示后面的字符当做普通字符被识别)

匹配字符类

匹配多个实例

// 第一个\\引导匹配特殊字符 
// [0-9]就是匹配任意数字 
// sticks?就是匹配stick或者sticks (?是匹配前面任何字符的0/1次)        

    select name
    from user
    where name regexp '\\([0-9] sticks?\\)'
    order by name; 

定位符(匹配一个串中任意位置文本)

//匹配以一个数(包括小数点开始的数字)开始的所有产品
//简单搜索[0-9\\.]不行  必须要用^定位符
// where name regexp '^[0-9\\.]'

计算字段

运行时在select语句内创建

1. 字段(field) 基本上和列意思相同
2. 数据库可以区分哪些列是实际的表列,哪些是计算字段
3. 客户机(应用程序)计算字段的数据和其他列数据相同方式返回

拼接字段(Concat()函数)

将值联结到一起构成单个值

//多数DBMS使用 + 或者 || 实现拼接
//使用拼接从user表根据name升序排序 输出格式是 name(price)
    select Concat(name,'(',price,')')
    from user
    order by name;

//例如:  
        宋亚翔(1200)
        张三(230)

删除数据右侧多余空格(RTrim()函数)

//拼接基础上删除右侧多余空格
    select Concat(RTrim(name),'(',RTrim(price),')')
    from user
    order by name;

别名/导出列(AS关键字)

一个字段/值的替换名

//拼接之后删除多余空格的字段  给个songyaxiang的别名就可以引用
    select Concat(RTrim(name),'(',RTrim(price),')') AS songyaxiang
    from user 
    order by name;

算术计算

//输出price和num乘积
    select price*num
    from user
    where name='宋亚翔';

数据处理函数

文本处理函数

//Soundex()函数就是匹配发音相似的函数
//现在user表里面有个人叫宋亚翔 其联络名叫laekkkkkkk(如果输入错误,实际应该是larkkkkkkk)
    select name,lianluoming
    from user
    where Soundex(lianluoming)=Soundex(larkkkkkkk);
//因为larkkkkkkk和laekkkkkkk发音相似,所以Soundex值匹配

日期和时间处理函数

数值处理函数


汇总数据

聚集函数(5个)

运行在行组上,计算和返回单值

avg()某列平均值

通过对表中行数计数并计算特定列值之和,求该列平均值

//从user表中找到价格price列的平均值 结果起个jiage的别名
    select avg(price) as jiage
    from user;

//计算特定列/行的平均值(where语句确定)
//从user表中找到名字叫宋亚翔的所有价格price列的平均值 结果叫jiage别名
    select avg(price) as jiage
    from user
    where id='宋亚翔';

count()某列行数和

1. 使用count(*)对表中行的数目进行计数(不管列中包含的是null还是非空值)
2. 使用count(column)对特定列中具有值得行进行计数(忽略null值)

//从user表中记录所有用户总数 结果给zongshu这个别名
    select count(*) as zongshu
    from user;

max()某列最大值

//从user表中找到最大价格price行 结果给max这个别名
    select max(price) as max
    from user;

min()某列最小值

//从user表中找到最小价格price行 结果给min这个别名
    select min(price) as min
    from user;

sum()某列总和

//从user表计算price总和 结果给sum这个别名
    select sum(price) as sum
    from user;

聚集不同值(distinct/all)

1. all(默认)  所有的行执行计算
2. distinct() 只包含不同的值   必须用于列名

组合聚集函数(select子句)

//使用四个函数
    //从user表中算出行总数 最大最小和平均价格并且给与别名
        select count(*) as count,
                min(price) as min,
                max(price) as max,
                avg(price) as avg
        from user;

分组数据(group by和having子句)

创建分组(group by子句)

分组在select语句的group by子句中建立

//计算每个id对应的产品个数
//例如:  宋亚翔有7个产品 刘伟有3个产品
    select id,count(*) as count
    from user
    group by id  //根据id分组
    order by id; //根据id升序

// 书写顺序:
     group by
    having
    order by
    limit

过滤分组(having子句)

//where过滤行,having子句过滤分组

//从orders表中查找每个id和总数 然后按照id升序排序 给结果的每行给别名orders 
//主要是我们只要count大于等于2的结果
    select id,count(*) as orders
    from orders
    group by id
    having count(*)>=2;

分组(group by)和排序(order by)区别

//检索总计订单价格大于等于50的订单的订单号和总计订单价格
    select id,sum(quantity*price) as jiage
    from user
    group by num   //根据num分组
    having sum(quantity*price)>=50  //过滤分组
    order by price;  //根据价格升序排序

子查询(嵌套在其他查询中的查询)

//说明情况:
    orders表: 每个订单(订单号,客户ID,订单日期)
    customers表: 实际的客户信息
    orderitems表:各订单的物品存储

//子查询执行顺序:
    从内向外处理

利用子查询过滤

两个以上select语句嵌套

作为计算字段使用子查询

//问题:
    需要显示customers表中每个客户的订单总数
    (订单和相应的客户ID存储在orders表)

//1. 从customers表中检索客户列表
//2. 对于检索出来的客户,统计其在orders表中订单的数目

//1.对客户10001的订单进行计数
    select count(*) as orders
    from orders
    where id=10001;

//2.为了对每个客户执行count(*)计算,应该作为一个子查询
    select name,state,(select count(*) 
                       from orders 
                       where orders.id=customers.id)   as orders
    from customers
    order by name;

相关子查询(涉及外部查询的子查询)


联结表(多表联系)

关系表

主键(primary key) : 唯一的标识
外键(foreign key) : 外键为某个表中的一列,它包含另一个表的主键值,定义了两个表之前的关系

笛卡尔积(乘积)

由没有联结条件的表关系返回的结果(h表1*h表2)

表别名

1. 列起名(select子句) + 表别名(from子句)

    //列别名
        select count(*) as jia  //结果起别名叫jia
        from user
        where id='宋亚翔';

    //表别名
        select name,price
        from customers as c,orders as o,orderitems as oi  //给三个表起别名
        where c.id=o.id and oi.num=c.num;  //where子句直接就用了别名

不同类型的联结(四种联结)

1. 内部联结/等值联结(简单联结)
2. 自联结
3. 自然联结
4. 外部联结 
    4.1 左外部联结
    4.2 右外部联结 

组合查询(union操作符)

并(union)/复合查询

//使用组合查询条件:
    1. 在单个查询中从不同的表返回类似结构的数据
    2. 对单个表执行多个查询,按单个查询返回数据

创建组合查询(union操作符)

只是给出每条select语句,在各条语句之间放入关键字union

//价格<=5的所有物品的一个列表 + 包括供应商1001和1002生产的所有物品(不考虑价格)

//分开写select语句
//1. 找到价格<=5的所有物品的一个列表
    select id,price
    from products    
    where price<=5;

//2. 找到供应商1001和1002生产的所有物品
    select id,price
    from products
    where id in(1001,1002);

//3. 组合两条语句
    select id,price
    from products    
    where price<=5;
    union
    select id,price
    from products
    where id in(1001,1002);

//4. 使用多条where子句
    select id,price
    from products    
    where price<=5 or id in(1001,1002);

union规则

1. 必须两条以上的select语句组成
2. union中的每个查询必须包含相同的列,表达式或者聚集函数
3. 列数据类型必须兼容(不必完全相同,DBMS可以隐含转换的类型)

包含重复行(union all)

查询结果集中自动去除重复行(和多个where子句组合一样)

组合查询结果排序(必须在最后一条select语句之后)

只能使用一条order by子句(但是排序却在所有select语句中起作用)


全文本搜索(比like和正则表达式更好!)

全文本搜索(建表时启用)

并非所有引擎都支持全文本搜索

1. MyISAM(5.5以前)
    支持全文本搜索(√)

2. 和InnoDB(5.5以后)
    不支持全文本搜索(×)

启用全文本搜索支持(fulltext子句)

创建表的时候使用fulltext子句

//create table语句接受fulltext子句(给出被索引列的一个逗号分隔的列表)

create table user
(
    note_id int     not null 
    pro_id char(20)  not null,
    note_date datetime not null,
    note_text text null,
    primary key(note_id),
    fulltext(note_text)   //mysql根据fulltext子句指示给它进行索引,进行全文本搜索(索引会根据数据改变重新索引)
)ENGINE=MyISAM;  //myisam引擎支持全文本搜索

执行全文本搜索(Match()和Against()函数)

select的时候使用match()和against()函数

1. Match()指定被搜索的列 
2. Against()指定要使用的搜索表达式     

//检索单列
    select note_text 
    from productnotes
    where match(note_text) against('rabbit');    

//match(note_text)表明mysql针对note_text列进行搜索
//against('rabbit')表明对制定此rabbit作为搜索文本搜索

注意:
    match()里面的值必须和fulltext()里面的值相同(指定多列必须列出多列次序也要正确)

like匹配和全文本搜索对比

1. 全文本搜索可以对结果进行排序(较高等级的行先返回)
2. 全文本搜索中数据是索引的,速度v更快

查询扩展(搜索相关结果 with query expansion)

能找到可能相关的结果,即使他们并不精确包含所查找的词

//检索note_text列里面和rabbit相关的
    select note_text 
    from productnotes
    where match(note_text) against('anvils' with query expansion);

布尔文本搜索(in boolean mode)

不需要全文本搜索需要建立fulltext索引

1. 要匹配的词
2. 要排斥的词(如果某行包含这个词,则不返回该行,即使它包含其他指定的词也是如此)
3. 排列提示(更重要的词等级更高)
4. 表达式分组
5. 另外一些内容

全文本布尔操作符

//匹配包含heavy但不包含任意以rope开始的词 
    // -排除一个词(词必须不出现!) *是截断操作符
    select note_text
    from productnotes
    where match(note_text) against('heavy -rope*' in boolean mode)

全文本搜索使用说明

1. 许多次出现评率很高,搜索他们没有用处(返回太多结果)
    1.1 所以规定一条50%规则(不用于in boolean mode): 如果一个词出现在50%以上的行,将它作为一个非用词忽略。
2. 如果表中行数<3:全文本搜索不返回结果
3. 忽略词中的单引号(don't索引为dont)
4. 不具有词分隔符(包括日语和汉语)的语言不能恰当地返回全文本搜索结果
5. mysql带有一个内建的非用词(stopword)列表,这些词在索引时候被忽略(出现次数50%以上) 如果想用就覆盖这个列表
6. 在索引全文本数据时,短词被忽略而且要从索引中排除(短语是具有<=3个字符的词)

插入数据(insert语句)

提高整体性能(low_priority)

插入单行

//不安全(高度依赖于列定义次序)
    insert into customers
    values(null,'123','15009272737',null);

//安全但是麻烦(说明自定义的次序和对应值)
    insert into customers(id,glass,num,country)
    values(null,'123','15009272737',null);

插入多行

1. 第一个insert语句;第二个insert语句;
    insert into user()
    values();
    insert into user()
    values();

2. values语句(),();   -- 单条insert语句处理多个插入性能更好!!
    insert into user()
    values(),();

插入检索出的数据(insert select)

一条insert语句和一条select语句组成

从另一表中合并客户列表到你的customers表,将它用insert插入
    insert into customers(id,contact,email,name,address,city,state,zip,country)
    select id,contact,email,name,address,city,state,zip,country
    from custnew;

更新数据(update语句)

1. 更新表中特定行(update set where)
2. 更新表中所有行(update set )

更新特定行(where子句要有)

更新单列信息

//客户10005现在有了电子邮件地址,因此它的记录需要更新
    update customers
    set email='134506293@qq.com'
    where id=10005;

更新多列信息:(逗号分隔)

igonre关键字:保证就算发生错误,也继续更新!!!

//客户10005不仅有了电子邮件地址,而且有了班级信息
    update ignore customers  //ignore保证就算发生错误,也继续更新!!!
    set email='134506293@qq.com',class='软件工程';
    where id=10005;

更新所有行(where子句没有)

//将所有人的邮箱都改成134506293@qq.com
    update customers
    set email='134506293@qq.com'

删除某个列的值(set设置null)

//将10005客户的邮箱一栏删除 就是删除列的信息
    update customers    
    set email=null
    where id=10005;

删除数据(delete)

delete从表中删除行(不删除表本身)

1. 从表中删除特定行()
2. 从表中删除所有行()

删除特定行

//删除customers表中客户10005的信息
    delete 
    from customers
    where id=10005;  //删除的是行(删除列是update中set设置null)

删除所有行()

//删除customers表中所有行信息
    delete 
    from customers

更快删除所有行(truncate table)

删除原来表并且重新创建一个表

输入: truncate table
    速度比delete语句删除所有行速度更快

创建表(create table)

创建表方式(2种)

1. 使用具有交互式创建和管理表的工具(navicat)
2. 使用mysql语句操纵(create table语句)

null值(建表默认null)

null值是没有值,不是空串

//创建orders表
    create table orders
    (
        order_num   int       not null,
        order_date  datetime  not null,
        cust_id     int       not null,
        primary key(order_num)
    )ENGINE=InnoDB;

auto_increment(自动增量)

一个表只允许一个auto_increment列,而且它必须索引(主键)

指定默认值(default关键字)

如果在插入行时没有给出值,mysql会使用默认值(不是null值)

引擎类型(engine)

引擎具体创建表,隐藏在DBMS中

1. MyISAM (5.5以前)  --性能极高引擎
    支持全文本搜索 
    不支持事务处理

2. InnoDB (5.5以后)  --可靠的事务处理引擎
    不支持全文本搜索

更新表(alter table)

给表添加一个列

alter table user
add id char(50);

定义外键

alter table user
add constraint orders foreign key(order_num) references orders(order_num)

删除表(drop table)

//删除表(删除的不是内容)    
    drop table user;

重命名表(rename table)

多个表重命名用逗号隔开

//给user表换成usertwo名
    rename table user to usertwo;

视图(MYSQL5出现)

视图规则和限制

1. 试图必须唯一命名(不能和其他试图/表相同名字)
2. 试图数目没有限制
3. 创建视图必须由足够访问权限(数据库管理人员授予)
4. 试图可以嵌套(从其他试图中检索数据的查询来构建)
5. 试图可以使用order by排序
6. 试图不能索引/触发器/默认值
7. 试图可以和表一起使用

视图SQL语句(create view)

1. 创建视图: create view 
2. 查看创建视图的语句:show create view name
3. 删除视图: drop view name
4. 更新视图: 先drop然后再create / create or replace view 

简化联结(查询可从视图找)

//创建一个名为productcustomers的视图
//联结三个表,返回已订购任意产品的所有客户的列表
    create view productcustomers as
    select cust_name,cust_contact,prod_id
    from customers,orders,orderitems
    where customers.cust_id=orders.cust_id and orderitems.order_num=orders.order_num;

//建立了视图(虚表),可以使用select语句查询任意产品的客户
    select *
    from productcustomers //从视图中查询

存储检索结果方便查找

//单个组合计算列中返回供应商名和位置
    //Concat是拼接函数  RTrim删除右边多余空格
    select Concat(RTrim(name),'(',RTrim(country),')') as hhh  //拼接结果起别名为hhh
    from vendors  //从vendors表
    order by name; //根据名字name升序排序

//假设经常需要这个格式的结果,不必每次需要时候执行联结,可以创建一个视图,需要使用的视图即可
    create view shitu as  //添加视图名shitu
    select Concat(RTrim(name),'(',RTrim(country),')') as hhh  //拼接结果起别名为hhh
    from vendors  //从vendors表
    order by name; //根据名字name升序排序

//之后使用就select查找shitu即可
    select *
    from shitu;

过滤数据

应用于普通的where子句也很有用
//过滤没有电子邮件地址的客户
    create view noemail as
    select id,name,email
    from customers
    where email is not null; //where限定找到没有eamil的用户

简化计算字段使用

之前的所有操作得到的结果赋给一个视图,然后每次查找去找视图即可(简化数据处理)

更新视图(一般用于select语句)

视图可以更新,更新视图将更新其基表

更新视图条件

1. 由于视图本身是虚表(没有数据)所以还是对基表进行增删查改
2. 有以下操作则不能更新:
    1. 分组(group by和having)
    2. 联结
    3. 子查询(嵌套select语句)
    4. 并(union)
    5. 聚集函数(min()/max()/count()/avg()/sum())
    6. distinct(保证唯一)
    7. 计算列(select语句有计算)

存储过程(MySQL5出现)

为以后使用而保存的一条/多条Mysql语句的集合

创建存储过程(create procedure语句)

//一个返回产品平均价格的存储过程
    create procedure productpricing()  //创建存储过程名字为productpricing
    begin
        select avg(price) as priceaverage  //起别名为priceaverage
        from products;
    end;

参数

存储过程并不显示结果,只是把结果返回给你指定的变量

变量(variable)

//in    传递给存储过程
//out   从存储过程传出给调用者
//inout 对存储过程传入和传出

//创建有参数的存储过程
    create procedure productpricing(
        out p1 decimal(8,2),  //out用来从存储过程传出一个值(返回给调用者)
        out ph decimal(8,2),
        out pa decimal(8,2),
    )
    begin
        select min(price)  //p1存储产品最低价格
        into p1            //into插入
        from products;

        select max(price)  //ph存储产品最高价格
        into ph
        from products;

        select avg(price)  //pa存储产品平均价格
        into pa
        from products;
    end;

//调用productpricing存储过程(必须制定三个变量名)
    //变量必须以@开始!!!!!!!!!!!!
    call productpricing(@pricelow,@pricehigh,@priceaverage);

使用存储过程(call语句)

//执行刚创建的存储过程并显示返回的结果(存储过程实际上是一种函数,所以调用要有()符号)
    call productpricing();

执行存储过程(call语句)

//执行名字叫productpricing的存储过程,并且返回产品的最低、最高和平均价格
    call productipricing(@pricelow,@pricehigh,@priceaverage);

删除存储过程(drop procedure语句)

创建之后被保存在服务器上以供使用,直到被删除

//删除刚创建的存储过程
    drop procedure productpricing (if exists);

建立智能存储过程

目前使用的所有存储过程基本上是封装mysql简单的select语句

检查存储过程(show create procedure语句)

//展示ordertotal存储过程
    show create procedure ordertotal;

//展示存储过程何时、谁创建等详细信息的存储过程列表
    show procedure status (like 'xxx');  //like制定过滤模式

游标(cursor)

存储在mysql服务器上的数据库查询,是select语句检索出来的结果集

游标适用范围

1. mysql游标只能用于存储过程(上章讲解)和函数
2. mysql游标主要用于交互式应用,可以根据需要滚动/浏览其中的数据

游标使用步骤

1. 使用前必须定义要使用的select语句
2. 一旦定义,必须打开游标以供使用(用定义好的select语句把数据实际检索出来)
3. 对于填有数据的游标,根据需要取出索引各行
4. 游标使用结束之后,必须关闭游标

创建游标(declare)

//定义名为ordernumbers的游标,使用检索所有订单的select语句
    create procedure processorders()  //创建processorders存储过程
    begin
        declare ordernumbers cursor  //创建游标
        for
        select order_num  //select语句
        from orders;
    end;

打开/关闭游标(open cursor语句)

//打开ordernumbers游标
    open ordernumbers;
//关闭ordernumbers游标        
    close ordernumbers;  //释放游标使用的所有内部内存和资源

使用游标数据(fetch语句)

//从游标中检索单行(第一行)
    create procedure processorders()  //创建存储过程
        begin
            declare o int;  //局部声明的变量
            declare ordernumbers cursor //创建游标
            for
                select order_num  //书写的select语句
                from orders;
            open ordernumbers;  //打开游标
            fetch ordernumbers //检索当前行的order_num列到一个名为0的局部声明的变量中 
            into o;   //插入o游标
            close ordernumbers;  //关闭游标
        end;

//循环检索数据(从第一行到最后一行)
    create procedure processorders()  //创建存储过程
        begin
            declare done boolean default 0;
            declare o int;
            declare ordernumbers cursor  //定义游标
            for
                select order_num
                from orders
            declare cotinue handler for sqlstate '02000' set done=1;
            open ordernumbers;    //打开游标
            repeat
                fetch ordernumbers 
                into o;
            until done end repeat;  //反复执行到done为真
            close ordernumbers;   //关闭游标
        end;    

触发器(MYSQL5支持)

响应增删改三种语句而自动执行的一条mysql语句

触发器定义条件

1. 只能按照每个表每个事件每次地定义(每次只能有一个)
2. 每个表最多支持6个触发器(增删改的之前和之后)
3. 如果需要对一个insert和update操作执行,就必须要定义两个
4. 触发器不能识别执行存储过程的call语句(需要的存储过程代码需要复制到触发器内)

创建触发器(create trigger)

只有表支持触发器(视图和临时表也不可以)

//创建newproduct的新触发器
    create trigger newproduct //创建触发器名
    after insert on products  //定义是插入语句成功执行后执行 
    for each row  //定义每个插入行执行
    select 'chenggong'; //对每个成功的插入显示成功的消息

删除触发器(drop trigger)

//删除刚才的newproduct触发器
    drop trigger new product;

使用触发器(三类六种)

insert触发器(NEW虚拟表)

1. insert触发器代码中,可引用一个名字叫NEW的虚拟表(访问被插入的行)
2. 在before insert触发器中,new的值可以被更新
3. 对于auto_increment列,new在insert执行之前包含0,insert执行之后包含新的自动生成值

//创建一个名叫neworder的触发器 按照after insert on orders执行
    create trigger neworder 
    after insert on orders  //插入一个新订单到orders表
    for each row
    select new.order_num;  //mysql生成一个新订单号保存到order_num

delete触发器(OLD虚拟表)

1. delete触发器代码中,可引用一个名字叫OLD的虚拟表(访问被删除的行)
2. OLD中的值全是只读,不能更新

//创建一个名叫deleteorder的触发器
    create trigger deleteorder
    before delete on orders  //插入一个新订单到orders表
    for each row
    begin
        insert into achive_orders(num,data,id)
        values(OLD.num,OLD.data,OLD.id)
    end;

//用一条insert将要删除的订单保存到achive_orders表

update触发器(OLD虚拟表)

1. update触发器代码中,可引用一个名字叫OLD的虚拟表访问更新的值
2. before update触发器中,new的值可能会被更新
3. OLD中的值全是只读,不能更新

管理事务处理(commit和rollback语句)

MYSQL5.5以后支持的InnoDB引擎支持事务管理

事务知识点

事务(transaction) : 一组sql语句
回退(rollback) : 撤销指定sql语句的过程
提交(commit) : 将未存储的sql语句结果写入数据库表
保留点(savepoint) : 事务处理中设置的临时占位符,你可以对它发布回退

事务开始

会在commit/rollback语句执行后,事务自动关闭

start transaction

rollback命令回退

只能增删改语句(create/drop不能回滚)

//举例

select *
from ordertotals;  //展示ordertotals表内信息

start transaction;  //打开事务

delete
from ordertotals;  //删除ordertotals表中所有行

select *
from ordertotals;  //检验是否为空

rollback;  //回滚打开事务之后的所有语言

select *
from ordertotals;  //显示该表不是空(回滚成功!)

commit语句

//事务处理块中,必须明确提交(使用commit语句)

start transaction; //事务开始

delete
from order        //从order表中删除订单20010  
where num=20010;

delete   
from orders       //从orders表中删除订单20010
where num=20010;

commit; //提交

保留点(savepoint)

设置保留点进行部分提交/回滚

//设置保留点
    savepoint d1;

//回滚到d1点
    rollback to d1;

保留点越多越好:
    更加灵活地进行回退

释放保留点(事务处理完成后自动释放)
    release savepoint(mysql5之后)

更改默认的提交行为(autocommit自动提交)

//mysql默认是自动提交所有更改

//为了让mysql不自动提交更改
    set autocommit=0;

全球化和本地化

字符集(character)和校对顺序(collation)

//重要术语:
    字符集: 为字母和符号的集合
    编码: 为某个字符集成员的内部表示
    校对    : 为规定字符如何比较的指令(影响排序和搜索)

//决定级别:
    服务器/数据库/表级进行

字符集和校对顺序(sql语句)

//显示所有可用的字符集和每个字符集的描述和默认校对
    show character set;

//查看所支持校对的完整列表
    show collation;

//修改所用的字符集和校对
    show variables like 'character%';
    show variables like 'collation%';

//建表时设置字符集和校对
    create table user
    (
        id int,
        name varchar(10)
    )default character set hebrew
     collate hebrew_general_ci;

    //以下三种情况:
        1. 如果两个都设置,就使用这些设置
        2. 只设置字符集,则使用字符集默认的校对
        3. 如果两个都没设置,则使用数据库默认

安全管理

管理用户(存储在名mysql数据库中)

//需要获取所有用户账号列表
    use mysql;  //进入mysql数据库
    selet user
    from user;  //从user数据库中查找user(结果是root)

创建用户账号(create user)

//创建用户名为song
    create uesr song (identified by 'p@$$w0rd');

//identified by 'p@$$w0rd' 纯文本指定口令

//identified by password 散列值指定口令

重命名用户账号(rename user)

//将上面的song用户改名为ya
    rename user song to ya;

删除用户账号(drop user)

//删除上面的ya用户(5以后也删除相关权限)
    drop user ya;

//5之前只能删除用户账号
    1. 先用revoke删除相关权限
    2. 然后使用drop user删除账号

设置访问权限(grants)

//查看赋予用户账号的权限
    show grants for ya;

//设置权限(允许ya用户在user所有表上可以使用select语句)
    grant select on user to ya;

撤销访问权限(revoke)

//撤销上面设置的权限
    revoke select on user from ya;

控制访问权限(层次)

更改口令(set password)

set password for ya=password('自己的口令');

set password (不指定用户名,就更新当前登录用户口令)

数据库维护

备份数据(flush tables之后备份)

刷新未写数据(保证所有数据被写到磁盘)
    1. 先flush tables语句
    2. 然后备份

数据库维护(SQL语句)

//1. 检查表键是否正确
    analyze table user;  //返回状态信息

//2. check table 检查许多有问题的表并且修改
    (MyISAM(5.5以前)表还对索引进行检查)

//3. changed 检查自最后一次检查以来改动过的表

//4. extended 执行最彻底的检查

//5. fast 只检查未正常关闭的表

//6. medium 检查所有被删除的联结并且进行键检查

//7. quick 只进行快速扫描

MyISAM表访问不一致(repair table语句修复)

可能需要使用repair table来修复相应的表(不能经常使用,否则会有更大问题需要解决)

表中删除大量数据(optimize table回收空间)

诊断启动问题(mysqld命令行)

查看日志文件


改善性能(遵守规则)

1. 遵守硬件建议(学习和研究mysql)
2. 关键的生产DBMS应该放在自己的专用服务器上
3. Mysql是一系列默认设置预先配置的,过一段时间就需要调整内存大小等
4. Mysql是一个多用户多线程的DBMS,经常同时执行多个任务,如果出现性能不良等可以使用show processlist 展示所有活动进程/kill命令终结某个进程
5. 尽量找到最优sql语句
6. 一般来说,存储过程 > 一条一条执行其中的各条mysql语句
7. 使用正确的数据类型
8. 要检索多少就检索多少(不要select *)
9. 导入数据时,应该关闭自动提交
10. 必须索引数据库表(提高检索性能)
11. or条件 ---> 多条select语句和union语句
12. 索引尽量使用在常用表上

参考用书

参考《MySQL必知必会》


设计模式总结

1.参考网址

学习参考的网址:

http://c.biancheng.net/view/1351.html


2.设计模式分类(三大类二十三种)

  • 创建型模式用于描述怎么创建对象
  • 结构型模式用于描述如何将类/对象按某种布局组成更大的结构
  • 行为型模式用于描述类/对象之间如何相互协作共同完成单个对象都无法单独完成的任务,如何分配职责

image-20231009170032870


3.统一建模语言(UML)

1. 类图(9类):用例图、类图、对象图、状态图、活动图、时序图、协作图、构件图、部署图
2. 类
3. 接口
4. 类之间关系

3.1 类(类名、属性和操作之间有分割线的矩形)

具有相同属性、方法、关系的对象抽象,封装了数据和行为。

1. 类名(字符串)
    举例: Student

2. 属性([可见性]属性名:类型[=默认值])
    举例: -name:String
    可见性取值:
        + 公有 public
        - 私有 private
        # 受保护 protected
        ~ 朋友 friendly

3.操作([可见性]函数名称(函数参数列表)[:返回类型])
    举例: +display():void
  • 学生类的UML图举例

3.2 接口(带名称的小圆圈)

3.3 类图(静态模型)

1. 类图中的类可以通过某种编程 语言直接实现。
2. 类图在软件系统开发的整个生命周期都是有效的。
3. 它是面向对象系统的建模中最常见的图。
  • 举例:(计算长方形和圆形的周长与面积)

3.4 类之间的关系(六个)

1. 依赖关系  - - - -> (带虚线的箭头)

2. 关联关系   
    2.1 双向关联:  <一一> / 一一
    2.2 单向关联:  一一>
    2.3 关联分为一般关联 聚合 组合

3. 聚合关系(强关联)   部分一一◇整体
    整体和部分之间的关系 -- has a的关系
    部分离开整体也可以存在

4. 组合关系(更强烈的聚合关系) 部分部分一一◆整体
    整体和部分之间的关系 -- cxmtains-a的关系
    组合关系中增加整体对象可以控制部分对象的生命周期(整体死了部分也就死了)

5. 泛化关系(耦合度最大)  一一▷
    表示一般与特殊的关系 -- is a的关系(继承)

6. 实现关系  - - - ▷
    表示接口与实现类的关系

3.5 参考文章

http://c.biancheng.net/view/1319.html


4.UML设计七大原则

1. 开闭原则 : 是总纲,它告诉我们要对扩展开放,对修改关闭。 {多态参考的就是这个原则]
2. 里氏替换原则 : 告诉我们不要破坏继承体系
3. 依赖倒置原则 : 告诉我们要面向接口编程
4. 单一职责原则 : 告诉我们实现类要职责单一
5. 接口隔离原则 : 告诉我们在设计接口的时候要精简单一
6. 迪米特法则 : 告诉我们要降低耦合度
7. 合成复用原则 : 告诉我们要优先使用组合或者聚合关系复用,少用继承关系复用。

5.创建型模式(怎样创建对象)

将对象的创建和使用分离,降低系统耦合度,我们不需要关注创建细节,对象的创建由相关的工厂来完成

5.1 创建型模式分类(五个)

1. 单例模式(Singleton)            --对象创建型模式
    1.1 某个类只能生成一个实例,该类提供一个全局访问点供外部获取 (相当于城里面有一个店铺 你要访问店铺必须要通过城门检查)
    1.2 扩展是有限多例模式

2. 原型模式(Prototype)            --对象创建型模式
    2.1 将一个对象作为原型,然后通过复制而克隆出多个新实例

3. 工厂方法(FactoryMethod)          --类创建型模式
    3.1 定义一个创建产品的接口 由子类决定生产什么产品(相当于我定义一个模型样子,具体怎么搞看你子类生产啥)

4. 抽象方法(AbstractFactory)        --对象创建型模式
    4.1 提供一个创建产品族的接口 其每个子类可以生产一系列相关的产品(相关的接口们都给你了 怎么继承覆盖方法是子类决定的)

5. 建造者方式(Builder)              --对象创建型模式
    5.1 将复杂对象分解为多个相对简单的部分 然后根据需求分别创建它们然后构成复杂对象(乐高一样组装)

6.单例模式

6.1 定义和特点

1. 定义:
    采取一定的方法保证在整个的软件系统中,对某个类只能存在一个对象实例,并且该类只提供一个取得其对象实例的方法。
2. 特点:
    2.1 单例类只能有一个实例对象
    2.2 该单例对象必须由单例类自行创建[类的构造器访问权限为private,这样就不能用new创建]
    2.3 单例类对外提供一个访问该单例的全局访问点
3. 实现思路
    如果我们要让类在一个虚拟机中只能产生一个对象,我们首先必须将类的构造器的访问权限设置为private,[就不能用new操作符在类的外部产生类的对象],但在类内部仍可以产生该类的对象。因为在类的外部开始还无法得到类的对象,只能调用该类的某个静态方法用于返回类内部创建的对象,静态方法只能访问类中的静态成员变量,所以,指向类内部产生的该类对象的变量也必须定义成静态的。

6.2 懒汉式(每次访问都要同步 线程不安全 延迟加载)

类加载时不生成单例,第一次调用getInstance方法才会创建单例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LazySingleton
{
private static volatile LazySingleton instance=null; //保证 instance 在所有线程中同步
private LazySingleton(){
//private 避免类在外部被实例化
}

//编写多线程不删除关键字volatile和synchronized,否则将存在线程非安全的问题。
public static synchronized LazySingleton getInstance()
{
//getInstance 方法前加同步
if(instance==null)
{
instance=new LazySingleton();
}
return instance;
}

}

6.3 饿汉式(写死静态对象 线程安全 立即加载)

一旦加载就会创建一个单例,保证在调用getInstance方法之前单例就已经存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class HungrySingleton
{
//饿汉式单例在类创建的同时就已经创建好一个静态的对象供系统使用,以后不再改变
//所以是线程安全的,可以直接用于多线程而不会出现问题。
private static final HungrySingleton instance=new HungrySingleton();
private HungrySingleton(){

}

public static HungrySingleton getInstance()
{
return instance; //之前写死了一个instance
}

}

6.4 单例模式应用场景

1. 其类只需要生成一个对象 比如一个班的班长 每个人的身份证号
2. 当对象需要被共享的场合,由于只能创建一个对象,所以共享比较节省内存 比如web的配置对象,数据库连接池
3. 当某类需要频繁实例化,而创建的对象又频繁被销毁 如多线程的线程池、网络连接池
4. Windows 的回收站、操作系统中的文件系统、多线程中的线程池、显卡的驱动程序对象、打印机的后台处理服务、应用程序的日志对象    

7.原型模式(实现Cloneable接口的clone()方法)

7.1 定义和特点

1. 定义:
    1.1 在有些系统中,存在大量相同或相似对象的创建问题,如果用传统的构造函数来创建对象,会比较复杂且耗时耗资源,用原型模式生成对象就很高效
    1.2 用一个已经创建的实例作为原型,通过复制该原型对象来创建一个和原型相同或相似的新对象。

2. 特点:
    2.1 无需知道对象创建的细节

7.2 深克隆

浅克隆不会克隆原对象中的引用类型,仅仅拷贝了引用类型的指向。深克隆则拷贝了所有。也就是说深克隆能够做到原对象和新对象之间完全没有影响。

引用类型所在的类实现Cloneable接口,并使用public修饰符重写clone方法

7.3 浅克隆

具体原型类只要实现Cloneable接口就可实现对象的浅克隆(Cloneable接口是抽象原型类)

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

//具体原型类
class Realizetype implements Cloneable //实现Cloneable接口
{
Realizetype(){
System.out.println("具体原型创建成功!"); //构造函数
}
public Object clone() throws CloneNotSupportedException{ //重写clone方法
System.out.println("具体原型复制成功!");
return (Realizetype)super.clone();
}
}

//原型模式的测试类
public class PrototypeTest
{
public static void main(String[] args)throws CloneNotSupportedException{
Realizetype obj1=new Realizetype();
Realizetype obj2=(Realizetype)obj1.clone(); //obj2复制obj1
System.out.println(obj1==obj2);
}
}


//输出结果
具体原型创建成功!
具体原型复制成功!
false

7.4 原型模式应用场景

1. 对象之间相同/相似
2. 对象创建比较麻烦,但复制比较简单

8.工厂方法模式(满足开闭原则的可以拓展,不能修改)

8.1 定义和特点

1. 定义:
    一个创建产品对象的工厂接口,将产品对象的实际创建工作推迟到具体子工厂类中。
    (我定义一个模型样子,具体怎么搞看你子类生产了)
2. 产品: 被创建的对象
3. 工厂: 创建产品的对象

4. 特点:
    4.1 用户只需要知道具体工厂名称就可以得到产品(无须知道产品的具体创建过程)
    4.2 不需要对原厂进行修改,只需要在添加新产品的时候添加具体产品类和对应具体工厂类(符合开闭原则:可以拓展不可以修改)
    4.3 每增加一个产品就要增加一个具体产品类和一个对应的具体工厂类,这增加了系统的复杂度

8.2 结构

8.3 举例(设计畜牧场)

8.4 工厂方法模式应用场景

1. 客户只知道创建产品的工厂名(不知道具体的产品名)  如TCL电视工厂、海信电视工厂
2. 创建对象的任务由多个具体子工厂中的某一个完成
3. 抽象工厂只提供创建产品的接口
4. 客户只关心产品的名牌(细节无所谓)

9.抽象工厂模式(多等级产品的生产)

9.1 定义和特点

1. 定义
    1.1 为访问类提供一个创建一组相关或相互依赖对象的接口
    1.2 且访问类不需要指定所要产品具体类就能得到同族的不同等级的产品的模式结构。

2. 特点
    2.1 可生产多个等级的产品
    2.2 当增加一个新产品族时不需修改原代码(满足开闭原则)
    2.3 当产品族增加一个新产品时,所有工厂类都要修改

9.2 结构

9.3 举例(设计农场类)

9.4 抽象工厂模式应用场景

1. 当需要创建的对象是一系列相互关联或相互依赖的产品族时,如电器工厂中的电视机、洗衣机、空调等。
2. 系统有多个产品族,但每次只用一族(有人只穿某个品牌衣服鞋)
3. 系统中提供了产品的类库,且所有产品的接口相同,客户端不依赖产品实例的创建细节和内部结构。

10.建造者模式

10.1 定义和特点

1. 定义:
    将一个复杂对象的构造与它的表示分离,使同样的构建过程可以创建不同的表示

2. 特点:
    2.1 各建造者相互独立,有利于系统扩展
    2.2 客户端不需要知道产品内部组成细节,便于控制细节风险
    2.3 关注零部件的组装过程(工厂方法模式更关注零部件创建过程)

10.2 结构

Product产品类

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

class Product{
//三个参数
private String partA;
private String partB;
private String partC;
//三个set方法
public void setPartA(String partA)
{
this.partA=partA;
}
public void setPartB(String partB)
{
this.partB=partB;
}
public void setPartC(String partC)
{
this.partC=partC;
}
//show方法
public void show()
{
//显示产品的特性
}

}

Builder抽象建造者(接口)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

abstract class Builder
{
//创建产品对象
protected Product product=new Product();
public abstract void buildPartA();
public abstract void buildPartB();
public abstract void buildPartC();
//返回产品对象
public Product getResult(){
return product;
}

}

ConcreteBuilder具体建造类(实现抽象建造者接口)

1
2
3
4
5
6
7
8
9
10
11
12
13
 //继承Builder接口
public class ConcreteBuilder extends Builder
{
public void buildPartA(){
product.setPartA("建造 PartA");
}
public void buildPartB(){
product.setPartA("建造 PartB");
}
public void buildPartC(){
product.setPartA("建造 PartC");
}
}

Director指挥者(调用建造者方法完成复杂对象的创建)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Director
{
private Builder builder; //接口实例
public Director(Builder builder)
{
this.builder=builder; //构造函数
}
//产品构建与组装方法
public Product construct(){
builder.buildPartA();
builder.buildPartB();
builder.buildPartC();
return builder.getResult();
}

}

客户端Client

1
2
3
4
5
6
7
8
9

public class Client{
public static void main(String[] args){
Builder builder=new ConcreteBuilder();
Director director=new Director(builder);
Product product=director.construct();
product.show();
}
}

10.3 举例(客厅装修)

1. 客厅装修是复杂过程(墙体装修、电视选择、沙发购买)
2. 客户 --> 项目经理 --> 装修工人

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

//main方法类
public class ParlourDecorator
{
public static void main(String[] args)
{

Decorator d=(Decorator) ReadXML.getObject();
ProjectManager m=new ProjectManager(d); //指挥者
Parlour p=m.decorate(); //产品
p.show(); //调取结果
}
}

//产品:客厅
class Parlour
{
private String wall; //墙
private String TV; //电视
private String sofa; //沙发
public void setWall(String wall)
{
this.wall=wall;
}
public void setTV(String TV)
{
this.TV=TV;
}
public void setSofa(String sofa)
{
this.sofa=sofa;
}
public void show()
{
System.out.println(wall); //展示方法
System.out.println(tv);
System.out.println(sofa);
}

}

//抽象建造者:装修工人
abstract class Decorator
{
//创建产品对象
protected Parlour product=new Parlour();
public abstract void buildWall();
public abstract void buildTV();
public abstract void buildSofa();
//返回产品对象
public Parlour getResult()
{
return product;
}
}

//具体建造者: 具体装修工人1
class ConcreteDecorator1 extends Decorator{ //继承
public void buildWall()
{
product.setWall("w1"); //给属性赋值
}
public void buildTV()
{
product.setTV("TV1");
}
public void buildSofa()
{
product.setSofa("sf1");
}
}

//具体建造者: 具体装修工人2
class ConcreteDecorator2 extends Decorator{
public void buildWall()
{
product.setWall("w2"); //给属性赋值
}
public void buildTV()
{
product.setTV("TV2");
}
public void buildSofa()
{
product.setSofa("sf2");
}
}

//指挥者:项目经理
class ProjectManager{
private Decorator builder;
public ProjectManager(Decorator builder)
{
this.builder=builder; //构造函数
}
//产品构建与组装方法
public Parlour decorate(){
builder.buildWall(); //进行装修修饰(让具体工人去干活)
builder.buildTV();
builder.buildSofa();
return builder.getResult();
}
}

10.4 建造者模式应用场景

1. 对象较复杂 多个部件构成(部件间相对稳定)
2. 产品构建过程和最终表示是独立的

11.结构型模式(类和对象的布局结构)

11.1 分类(两大类七小类)

1. 类结构型模式  组织接口和类(继承的方式)
    1.1 适配器模式(Adapter) : 将一个类的接口A转换成客户希望的另外一个接口B,使得原来由于接口不兼容不能一起工作的类又能一起工作


2. 对象结构型模式 组合对象(组合/聚合的方式)
    2.1 代理模式(Proxy) : 为某对象提供一种代理用来控制对该对象的访问(修改对象的特性)
    2.2 适配器模式(Adapter) : 将一个类的接口A转换成客户希望的另外一个接口B,使得原来由于接口不兼容不能一起工作的类又能一起工作
    2.3 桥接模式(Bridge) : 抽象和现实分离(组合代替继承)
    2.4 装饰模式(Decorator) : 动态地给对象增加一些职能(增加额外功能) 
    2.5 外观模式(Facade) : 为多个复杂的子系统提供一个一致的接口(使子系统更容易被访问)
    2.6 享元模式(Flyweight) : 运用共享技术支持大量细粒度对象的复用
    2.7 组合模式(Composite) : 将对象组合成树状层次结构,让用户对单个对象和组合对象具有一致访问性

12.代理模式(中介)

12.1 定义和特点

1. 定义
    需要给某对象提供一个代理以控制对该对象的访问。
    访问对象不适合/不能直接引用目标对象(代理对象作为访问对象和目标对象的中介)

2. 特点
    2.1 代理模式在客户端与目标对象之间起到一个中介作用和保护目标对象的作用
    2.2 代理对象可以扩展目标对象的功能
    2.3 代理模式能将客户端与目标对象分离,在一定程度上降低了系统的耦合度
    2.4 但是,会增加系统的复杂度和请求处理速度变慢

12.2 结构

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
43
44
45

//客户类(执行main方法)
public class ProxyTest{
public static void main(String[] args){
Proxy p=new Proxy(); //代理类生成对象
P.Request(); //调用真实主题里存在的方法
}
}

//抽象主题
interface Subject{
void Request(); //接口只写方法
}

//真实主题
public class RealSubject implements Subject{
public void Request(){
System.out.println("这是访问真实主题方法!!");
}
}

//代理
public class Proxy implements Subject{
private RealSubject realSubject; //生成真实主题对象
public void Request(){
if(realSubject==null){
realSubject=new RealSubject(); //为空新建
}
preRequest(); //调用代理新加的功能
realSubject.Request(); //调用原有方法
postRequest(); //调用代理新加的功能
}
//新加的功能
public void preRequest(){
System.out.println("访问真实主题预处理");
}
public void postRequest(){
System.out.println("访问真实主题后续处理");
}
}

//执行结果
访问真实主题预处理
访问真实主题方法...
访问真实主题后续处理

12.3 举例(原有类上更新功能)

12.4 代理模式应用场景

1. 以前的功能在不修改基础上/不可看到接口内部 -- 代理模式进行扩展和修改
2. 远程代理 : 用户申请某些网盘空间时,会在用户的文件系统中建立一个虚拟的硬盘,用户访问虚拟硬盘时实际访问的是网盘空间。
3. 安全代理 : 控制不同种类客户对真实对象的访问权限。
4. 延迟加载 : 指为了提高系统的性能,延迟对目标的加载。

13.适配器模式(Adapter – 接口兼容)

13.1 定义和特点

1. 定义:
    将一个类的接口A转换成客户希望的另外一个接口B,这样使原来由于接口不兼容而不能一起工作的类能一起工作

2. 特点:
    2.1 分为类结构型模式(耦合度更高,使用较少)和对象结构性模式
    2.2 复用现存的类,不需要修改源代码而重用现有的适配者类

13.2 结构

1. 类适配器模式: 适配器类 implement 当前系统业务接口 + 适配器类 extends 组件
2. 对象适配器模式: 适配器类 implement 当前系统业务接口 + 组件引入到适配器类(聚合)
3. 两种类型的区别:
    只是客户端和适配器类代码不同!!!    

类适配器模式

对象适配器模式

13.3 举例(模拟新能源汽车发动机)

13.4 适配器模式应用场景

1. 以前开发的系统存在满足新系统功能需求的类,但是其接口和新系统接口不一致
2. 使用第三方提供的组件,但是组件接口定义和自己要求定义不同

14.桥接模式(组合替换继承)

14.1 定义和特点

1. 定义:
    将抽象和显示分离,使他们可以独立变化(组合代替继承)        
2. 特点:
    2.1 抽象和实现分离,扩展能力强
    2.2 实现细节可以对客户透明

14.2 结构

14.3 举例(模拟女士皮包选购)

14.4 桥接模式应用场景

1. 当一个类存在两个独立变化的维度,且这两个维度都需要进行扩展时。
2. 当一个系统不希望使用继承或因为多层次继承导致系统类的个数急剧增加时。
1. 当一个系统需要在构件的抽象化角色和具体化角色之间增加更多的灵活性时。

15.装饰模式(Decorator动态增加职能)

15.1 定义和特点

1. 定义:
    1.1 不改变现有对象结构的情况下,动态地给该对象增加一些职责(即增加其额外功能
    1.2 相当于在左边具体构件实现抽象构件的这条路基础上,增加右边这条线(抽象装饰类调用实现原来的具体构件的方法完成基础工作,然后具体装饰类可以新增功能)        

2. 特点:
    2.1 采用装饰模式扩展对象的功能比采用继承更加灵活
    2.2 可以设计多个不同的具体装饰类,创造出多个不同行为的组合

15.2 结构

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

//具体装饰类
public class DecoratorPattern{
public static void main(String[] args){
Component p=new ConcreteComponent();
p.operation();
Component d=new ConcreteDecorator(p);
d.operation();
}
}

//抽象构件角色
interface Component{
public void operation();
}

//具体构件角色
class ConcreteComponent implements Component{
public ConcreteComponent(){
System.out.println("创建具体构件角色");
}
public void operation(){
System.out.println("调用具体构件角色的方法operation()");
}
}

//抽象装饰角色
class Decorator implements Component{
private Component component;
public Decorator(Component component){
this.component=component;
}
public void operation(){
component.operation();
}
}

//具体装饰角色
class ConcreteDecorator extends Decorator
{
public ConcreteDecorator(Component component){
super(component);
}
public void operation(){
super.operation();
addedFunction();
}
//新增加的功能
public void addedFunction(){
System.out.println("为具体构件角色增加额外的功能addedFunction()");
}
}

//运行结果

创建具体构件角色
调用具体构件角色的方法operation()
调用具体构件角色的方法operation() //完成前面的功能
为具体构件角色增加额外的功能addedFunction() //新增功能

15.3 举例(美少女变身)

1. 其实本来就是茉莉卡原身实现茉莉卡接口进行display()方法展示
2. 但是现在我想变更多的样子我不想生成子类我就想使用装饰模式
3. 所以我新建changer变形类实现茉莉卡接口展示茉莉卡原身,然后生成新子类女巫和少女类不仅实现了茉莉卡方法展示茉莉卡原身,并且可以换新的setchanger()装备样子;

15.4 装饰模式应用场景

1. 需要给一个现有类添加附加只能,而且不能采用生成子类的方法扩充时候
2. 当对象的功能要求可以动态添加和删除

16.外观模式(提供统一接口)

16.1 定义和特点

1. 定义:
    通过为多个复杂子系统提供一致的接口

2. 特点:
    2.1 降低各子系统之间的耦合度
    2.2 降低了大型软件系统编译依赖性

16.2 结构

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
43
44
45
46
47
48

//客户类
public class FacadePattern{
public static void main(String[] args){
Facade f=new Facade();
f.method(); //调用方法
}
}

//外观角色
class Facade{
private SubSystem01 obj1=new SubSystem01();
private SubSystem02 obj2=new SubSystem02();
private SubSystem03 obj3=new SubSystem03();
public void method(){ //调用三个子类
obj1.method1();
obj2.method2();
obj3.method3();
}
}

//子系统角色
class SubSystem01{
public void method1(){
System.out.println("子系统01的method1()被调用!");
}
}

//子系统角色
class SubSystem02{
public void method2(){
System.out.println("子系统02的method2()被调用!");
}
}

//子系统角色
class SubSystem03{
public void method3(){
System.out.println("子系统03的method3()被调用!");
}
}


//运行结果(客户来不会一个一个子系统调用,只会去找外观角色facade)

子系统01的method1()被调用!
子系统02的method2()被调用!
子系统03的method3()被调用!

16.3 举例(办理业务)

16.4 外观模式应用场景

1. 子系统很多,需要外观模式为系统设计一个简单的接口供外界访问。

17.享元模式(flyweight)

17.1 定义和特点

1. 定义:
    运用共享技术有效地支持大量细粒度对象的复用

2. 特点:
    2.1 为了使对象可以共享,需要将一些不能共享的状态外部化
    2.2 相同的对象只需要保存一份,降低系统中对象的数量

17.2 结构

17.3 举例(五子棋)

五子棋同围棋一样,包含多个“黑”或“白”颜色的棋子,
所以用享元模式比较好。

17.4 享元模式应用场景

1. 系统中存在大量相同或相似的对象,这些对象耗费大量的内存资源。
2. 大部分的对象可以按照内部状态进行分组,且可将不同部分外部化,这样每一个组只需保存一个内部状态。
3. 由于享元模式需要额外维护一个保存享元的数据结构,所以应当在有足够多的享元实例时才值得使用享元模式。

18.组合模式(部分-整体模式)

18.1 定义和特点

1. 定义:
    将对象组合成树状的层次结构,使用户对每个对象和组合对象具有一致的访问性

2. 特点:
    2.1 客户端代码可以一致地处理单个对象和组合对象
    2.2 更容易在组合体内加入新对象

18.2 结构

透明式

安全式

18.3 举例(购物显示各个商品)

18.4 组合模式应用场景

1. 需要表示一个对象整体与部分的层次结构场合

19.行为型模式(类/对象协同工作)

19.1 行为型模式分类(11个)

1. 模板方法模式(Template Method) 定义一个操作中的算法骨架,将算法的一些步骤延迟到子类中,使得子类在可以不改变该算法结构的情况下重定义该算法的某些特定步骤。

2. 策略模式(Strategy) 定义一系列算法,并且将算法封装起来,相互替换。

3. 命令模式(Command) 将一个请求封装为一个对象,使发出请求和执行分开

4. 职责链模式(Chain of Responsibility) 将请求从链中的一个对象传到下一个对象,直到请求被响应为止

5. 状态模式(State) 允许一个对象在其内部状态发生改变时改变行为能力

6. 观察者模式(Observer) 多个对象间存在一对多关系,当一个对象改变,把这种改变通知给其他多个观察者,从而影响其他对象行为

7. 中介者模式(Mediator) 定义一个中介对象来简化原有对象之间的交互关系

8. 迭代器模式(Iterator) 提供一种方法来顺序访问聚合对象中的数据,而不暴露内部

9. 访问者模式(Visitor) 为一个集合中的每个元素提供多种访问方式

10. 备忘录模式(Memento) 不破坏封装,获取保存一个对象的内部状态,以便后面恢复

11. 解释器模式(Interpreter) 提供如何定义语言文法,以及对语言句子的解释方法

12. 模板方法模式和解释器模式是类行为型模式,其他的全部属于对象行为型模式

20.观察者模式/发布订阅/模型视图(Observer模式连带改变)

20.1 定义和特点

1. 定义:(对象行为型模式)
    多个对象间存在一对多依赖,一个对象状态改变,所有依赖它的对象都得到通知并自动更新

2. 特点:    
    2.1 降低了目标与观察者之间的耦合关系,两者之间是抽象耦合关系。
    2.2 目标与观察者之间建立了一套触发机制。
    2.3 观察者对象很多,通知的发布会花费很多时间,影响程序的效率。

20.2 结构

20.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
	//其实就是汇率抽象类让人民币汇率具体时间实现change()方法
//如果人民币汇率变化会通过company接口通知给实现接口的进出口公司

//人民币汇率执行类(main方法)
public class RMBrateTest{
public static void main(String[] args){
Rate rate=new RMBrate(); //新建汇率类
//新建两个实体公司
Company watcher1=new ImportCompany();
Company watcher2=new ExportCompany();
//汇率集合list添加两个公司和汇率改变
rate.add(watcher1);
rate.add(watcher2);
rate.change(10);
rate.change(-9);
}
}

//抽象目标:汇率
abstract class Rate{
protected List<Company> companys=new ArrayList<Company>();

//增加观察者方法
public void add(Company company){
companys.add(company); //添加公司(观察者)
}

//删除观察者方法
public void remove(Company company){
companys.remove(company);
}
//改变的方法 需要实现
public abstract void change(int number);

}

//具体目标:人民币汇率
class RMBrate extends Rate
{
public void change(int number){ //实现汇率类
for(Company obs:companys){
((Company)obs).response(number); //公司类改变汇率 (通知!!)
}
}
}

//抽象观察者:公司
interface Company{
void response(int number);
}

//具体观察者1:进口公司
class ImportCompany implements Company
{
public void response(int number){
if(number>0){
System.out.println("人民币汇率升值"+number+"个基点,降低了进口产品成本,提升了进口公司利润率。");
}
else if(number<0){
System.out.println("人民币汇率贬值"+(-number)+"个基点,提升了进口产品成本,降低了进口公司利润率。");
}
}
}

//具体观察者2:出口公司
class ExportCompany implements Company {
public void response(int number){
if(number>0){
System.out.println("人民币汇率升值"+number+"个基点,降低了出口产品收入,降低了出口公司的销售利润率。");
}
else if(number<0){
System.out.println("人民币汇率贬值"+(-number)+"个基点,提升了出口产品收入,提升了出口公司的销售利润率。");
}
}
}

20.4 应用场景

1. 对象间存在一对多关系,一个对象状态改变会影响其他对象
2. 当一个抽象模型有两个方面,其中一个方面依赖于另一方面时,可将这二者封装在独立的对象中以使它们可以各自独立地改变和复用

21.备忘录模式/快照模式(memento模式)

21.1 定义和特点

1. 定义:
    1.1 能记录一个对象的内部状态,当用户后悔时能撤销当前操作,使数据恢复到原先状态
    1.2 在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态,以便以后当需要时能将该对象恢复到原先保存的状态。该模式又叫快照模式。

2. 特点:    
    2.1 提供了一种可以恢复状态的机制。当用户需要时能够比较方便地数据恢复到某个历史的状态。
    2.2 实现了内部状态的封装。除了创建它的发起人之外,其他对象都不能够访问这些状态信息。
    2.3 简化了发起人类。发起人不需要管理和保存其内部状态的各个备份,所有状态信息都保存在备忘录中,并由管理者进行管理,这符合单一职责原则。

21.2 结构

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

//执行main方法类
public class MementoPattern{
public static void main(String[] args){
Originator or=new Originator(); //创建发起人
Caretaker cr=new Caretaker(); //创建管理者

or.setState("S0"); //发起人状态设置S0
System.out.println("初始状态:"+or.getState());

cr.setMemento(or.createMemento()); //管理者保存发起人状态
or.setState("S1"); //发起人更改状态为S1
System.out.println("新的状态:"+or.getState());

or.restoreMemento(cr.getMemento()); //发起人恢复状态为S0
System.out.println("恢复状态:"+or.getState());
}
}

//备忘录
class Memento{
private String state;
public Memento(String state){
this.state=state;
}
public void setState(String state){
this.state=state;
}
public String getState(){
return state; //获取状态state
}
}

//发起人
class Originator{
private String state;
public void setState(String state){
this.state=state;
}
public String getState(){
return state;
}
public Memento createMemento(){
return new Memento(state); //新建备忘录
}
public void restoreMemento(Memento m){
this.setState(m.getState()); //重新设置备忘录状态
}
}

//管理者
class Caretaker{
private Memento memento;
public void setMemento(Memento m){
memento=m; //设置备忘录
}
public Memento getMemento(){
return memento;
}
}

21.3 举例(相亲)

21.4 应用场景

1. 需要保存与恢复数据场景(玩游戏时存档功能)
2. 需要提供一个可回滚操作场景(Word、记事本、Photoshop,Eclipse软件Ctrl+Z、据库中事务操作)

22. 其余设计模式

其余设计模式均放入网站中可以浏览


京东2019校招笔试Java开发工程师笔试题

题目分析

这套题目考察的方面和深度我感觉都比较棒!!!但是答案错误太多了我吐了!!!


软件开发增量模型

题目

分析

AD就是互相矛盾
C适用于也是错误的,不应该是只需要客户化的工程项目    

知识点总结

瀑布模型(流程实施项目开发)+原型进化模型(系统按照功能分解为许多增量构建,然后不断地添加进系统直到交付给用户)


值类型和引用类型

题目

分析

1. 值类型变量赋值: 数据复制,创建一个同值得新对象
2. 引用类型变量赋值: 只是把对象引用的指针赋给变量,共用一个内存地址
3. 值类型一般是基本数据类型,不是封装的 C错误
4. 值类型没有实例 B错误
5. 值类型变量可以作为引用类型的成员变量存储在堆里面 D错误

知识点总结


操作系统避免死锁

题目

分析

说实话我感觉这道题有歧义,我觉得选D(傲娇不承认答案A)

知识点总结

  • 产生死锁

    1. 互斥 :存在一个资源每次只能被一个进程使用,若别的进程也要使用该资源,需要等待知道其占用者用完释放。
    2. 占有并等待 :部分分配,允许进程在不释放其已经分得的资源的情况下请求并等待分配的资源
    3. 不可抢占 :有些系统资源是不可抢占的,系即当某个进程已经获得这种资源后,只能由自身使用完释放。
    4. 循环等待 :若干个进程形成环形链,链中的每一个进程都在等待该链中下一个进程所占用的资源。
  • 避免死锁

    破坏四个条件其中一个就会避免死锁


奇数和算法

题目

分析

1. 计算是1+3+5+7+9+11+..+999
2. 所以i的计数肯定是i=i+2 然后s和i的变化要看顺序

知识点总结

其实最简单的就是自己写一个对比或者执行一遍即可

递归法

题目

分析

1. 递归法很容易崩 执行不出来所以执行效率肯定比递推法效率低

知识点总结

1. 递归就是一层一层调用 所以代码很简洁清晰
2. 递归会有很多次重复,然后递归调用占用大量内存空间,一旦执行次数过大就会无法执行
3. 递归法执行效率低

字符串比较

题目

分析

1. 这就跟c语言判断一样,一个一个字符对比。
2. 这道题对比A<D,还要结果是真 所以选择 <

知识点总结

比较的是ASCII码 从第一位开始判断

看代码判断结果

题目

分析

不管i取何值 (-1)*i永远是负数,所以ABC错误

知识点总结

取值测试

运算符优先级

题目

分析

知识点总结


如何确定一棵二叉树

题目

分析

我觉得AB都可以(不知道为啥是单选..)

知识点总结

只要告诉三种遍历其中之二即可

求小顶堆左子节点

题目

分析

知识点总结

小顶堆: 每个节点的值 <= 左右孩子节点的值


求子串

题目

分析

字符串有8个字符
非空子串数为8+7+...+2+1=8*9/2=36
加上一个空串,总共的子串数量为37

知识点总结

计算公式: n(n+1)/2+1  (等差数列求和) 

求二叉树总结点数

题目

分析

1. 叶子节点个数=度为2的节点个数+1
2. 所以n2=4 
3. 所以最终sum=n0+n1+n2=5+3+4=12

知识点总结

叶子节点值和度为2节点个数关系:n0=n2+1

排序算法

题目

分析

简单选择排序、快速排序、冒泡排序、堆排序

知识点总结


求哈夫曼树带权路径长度

题目

分析

根据构造哈夫曼树,然后计算权值

知识点总结

根据构造哈夫曼树(每次选最小的两个构成新的节点),然后计算权值(节点值*深度)

循环链表

题目

分析

关键字:依次  所以只能选循环链表

知识点总结

1. 双向链表: 从中间一个点,必须先往左一次再掉头往右一次才能遍历
2. 循环链表: 只要沿着一个方向一直走下遍历

TCP/IP各层及协议分布

题目

分析

ssh是应用层协议

知识点总结

1. SSH是secure shell缩写
2. 建立在应用层基础上的安全协议(比较可靠)

数据链路层设备

题目

分析

数据链路层是交换机

知识点总结

1. 应用层: 网关
2. 网络层: 路由器(分组交换)    
3. 数据链路层: 网桥 交换器
4. 物理层: 中继器(再生数字信号) 集线器(放大信号)

分组交换和电路交换

题目

分析

打电话有保证  电路交换
手机上网无保证 分组交换

知识点总结

1. 电路交换 有预留,且分配一定空间,提供专用的网络资源,提供有保证的服务,应用于电话网;
2. 分组交换 无预留,且不分配空间,存在网络资源争用,提供有无保证的服务。分组交换可用于数据报网络和虚电路网络。我们常用的Internet就是数据报网络,单位是Bit。

后退N帧协议

题目

分析

滑动窗口协议有
    1、停止等待协议,发送窗口=1,接受窗口=1;
    2、退后N帧协议,发送>1,接收=1;
    3、选择重传协议,发送>1,接收>1;

知识点总结

滑动窗口协议有
    1、停止等待协议,发送窗口=1,接受窗口=1;
    2、退后N帧协议,发送>1,接收=1;
    3、选择重传协议,发送>1,接收>1;

避免拥塞控制

题目

分析

慢开始
拥塞避免
快重传
快恢复

知识点总结

拥塞控制算法四种:
    慢开始
    拥塞避免
    快重传
    快恢复

TCP三次挥手ACK

题目

分析

知识点总结

每次都要发ack确定


预防Ddos方法

题目

分析

我感觉选A和B  
a减少重传次数 b减少半连接重传总时长

知识点总结

1. 半连接:服务器发送SYN-ACK之后,收到客户端的ACK之前的TCP连接称为半连接。
2. 攻击客户端通过发包器,在短时间内伪造大量不存在的IP地址,
3. 向服务器不断地发送SYN包,服务器回复确认包SYN/ACK,并等待客户的确认,由于源地址是不存在的,服务器需要不断的重发SYN/ACK直至超时,这些伪造的SYN包将长时间占用未连接队列,正常的SYN请求被丢弃,目标系统运行缓慢,严重者引起网络堵塞甚至系统瘫痪。
4. SYN攻击是一个典型的DDOS攻击。所以缩短超时时间和半连接数目都可以解决。

linux加载指令

题目

分析

1. -r: 将文件系统作为只读文件系统进行安装,而不考虑它先前在 /etc/file systems 文件中指定的内容或者先前的任何命令行选项。
2. ro : 将已安装的文件指定为只读文件,而不考虑它先前在 /etc/file systems 文件中指定的选项或者先前的任何命令行选项。缺省值是 rw。

知识点总结


软连接

题目

分析

我觉得答案选C 不接受反驳

知识点总结

1. 软连接知识点:
    1.1 可以有自己的文件属性和权限
    1.2 可以对不存在的文件/目录创建软连接
    1.3 软连接可以交叉文件系统
    1.4 创建软连接,连接计数i_nlink不会增加 

Ext3日志文件系统特点

题目

分析

我觉得四个选项都有 所以选ABCD

知识点总结

1、高可用性:系统使用了ext3文件系统后,即使在非正常关机后,系统也不需要检查文件系统。
 2、数据的完整性:避免了意外宕机对文件系统的破坏。
 3、文件系统的速度:因为ext3的日志功能对磁盘的驱动器读写头进行了优化。所以,文件系统的读写性能较之Ext2文件系统并来说,性能并没有降低。 
4、数据转换 :“由ext2文件系统转换成ext3文件系统非常容易。
 5、多种日志模式

DHCP协议作用

题目

分析

为网络中主机分配IP地址 

知识点总结

1. DHCP)是一个局域网的网络协议,使用UDP协议工作,
2. 主要有两个用途:
    1. 给内部网络或网络服务供应商自动分配IP地址给用户
    2. 内部网络管理员作为对所有计算机管理的手段。

获取本地ip地址

题目

分析

1. ipconfig 是win10系统
2. ifconfig 是linux系统

知识点总结

1. ipconfig 是win10系统
2. ifconfig 是linux系统

获取本地cpu使用率

题目

分析

1. top可以得到本地cpu使用情况

知识点总结

A ifconfig命令 : 被用于配置和显示Linux内核中网络接口的网络参数。
B uptime命令 : 打印系统总共运行了多长时间和系统的平均负载。
C top命令 : 可以实时动态地查看系统的整体运行情况,是一个综合了多方信息监测系统性能和运行信息的实用工具。
D netstat命令 : 用来打印Linux中网络系统的状态信息,可让你得知整个Linux系统的网络情况。

设置环境变量指令

题目

分析

1. export 设置环境变量
2. env 创建环境变量
3. cat 用于连接文件并打印到标准输出设备
4. echo 显示文字并且修改颜色

知识点总结

1. export 设置环境变量
2. env 创建环境变量
3. cat 用于连接文件并打印到标准输出设备
4. echo 显示文字并且修改颜色

第一范式(1NF)

题目

分析

1. 第一范式保证原子性
2. 第二范式不存在部分依赖 B错误
3. 第三范式不存在传递依赖 AD错误

知识点总结

1. 第一范式保证原子性 (不可拆分)
2. 第二范式不存在部分依赖
3. 第三范式不存在传递依赖 

Sql语句

题目

分析

由于结果里面有两个表而且要table1所以要left左连接 AB错误
而left semi join表示只打印出左边表的key C错误

知识点总结

1. 两个表要找一个表的完全内容只能是 left/right连接
2. 然后考虑是否是全部输出

Mysql数据库引擎MyISAM(以前默认的)

题目

分析

1. Innodb支持事务和行级锁 所以A错误    

知识点总结

1:不支持事务、不具备AICD特性(原子性、一致性、分离性、永久性);
2:表级别锁定形式(更新数据时锁定整个表、这样虽然可以让锁定的实现成本很小但是同时大大降低了其并发的性能);
3:读写相互阻塞(不仅会在写入的时候阻塞读取、还会在读取的时候阻塞写入、但是读取不会阻塞读取);
4:只会缓存索引(myisam通过key_buffer_size来设置缓存索引,提高访问性能较少磁盘IO的压力、但是只缓存索引、不缓存数据);
5:读取速度快、占用资源比较少;
6:不支持外键约束、只支持全文检索;
7:是MySQL5.5.5版本之前的默认存储引擎;

sql语句索引

题目

分析

b+树的数据项是复合的数据结构
    比如(name,age,sex)的时候,b+数是按照从左到右的顺序来建立搜索树的
    比如当(张三,20,F)这样的数据来检索的时候,
    b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据
所以C错误 -- 但当(20,F)这样的没有name的数据来的时候,b+树就不知道下一步该查哪个节点

知识点总结

索引的最左匹配特性


Delete和Truncate table区别

题目

分析

执行速度:  drop> truncate > delete  A对

知识点总结


根据描述写sql语句

题目

分析

1. 要查每个国家的用户人数肯定要有限制所以CD错误
2. B选项只能查到某个国家的人数 所以要用group by语句

知识点总结

考察select语句和分组语句

备忘录模式

题目

分析

1. 听着名字就感觉是备忘录模式存放

知识点总结

1. 备忘录模式: 适合恢复某个类的先前状态(类似于快照功能)

适配器模式

题目

分析

1. 建造者模式:将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。
2. 适配器模式:将一个类的接口转换成另外一个客户希望的接口。Adapter 模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
3. 桥接模式:将抽象部分与它的实现部分分离,使它们都可以独立地变化。

知识点总结

1. 建造者模式:将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。
2. 适配器模式:将一个类的接口转换成另外一个客户希望的接口。Adapter 模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
3. 桥接模式:将抽象部分与它的实现部分分离,使它们都可以独立地变化。

代码执行顺序

题目

分析

静态初始化代码块 > 初始化代码块 > 构造函数
1. 先加载static块 输出D
2. 然后执行main方法 输出A
3. 执行代码块 输出C
4. 执行Main方法 输出B
5. 有一次执行代码块 输出C
6. 执行Main方法 输出B
7. 最终结果为: DACBCB

知识点总结


Integer和int区别

题目

分析

1. Integer相当于string是写死的 所以值不会变
2. int值传递不会影响int的结果
3. 最终结果应该还是10 10

知识点总结

1. Integer范围是[-128,127]
2. Integer是写死的 所以值不会变

String实例问题

题目

分析

1. s1生成之后 s2生成的时候发现s1已经有了 所以指向了s1位置 所以 s1==s2为true
2. s3重新生成对象 所以s1==s3为false

知识点总结

考虑生成实例对象的问题

Java类加载1.0

题目

分析

1. static和final同时修饰的变量,类没初始化的时候就可以访问 所以没有输出OK
2. 最后直接输出JD

知识点总结

static和final同时修饰的变量,类没初始化的时候就可以访问

Java类加载2.0

题目

分析

1. 和上道题区别是JD这次是实例对象
2. 所以还是需要先打印OK然后打印JD    

知识点总结


Java类加载3.0

题目

分析

1. 和上道题区别就是实例在下面
2. 其实没啥区别所以还是OKJD

知识点总结


父子继承类1.0

题目

分析

和上面题一样 static和final修饰的变量不经过类初始化 所以只有C输出

知识点总结


父子继承类2.0

题目

分析

因为这道题c变量没有static和final共同修饰
所以先静态代码块输出A然后输出C

知识点总结


类加载器加载原理

题目

分析

其实就是先输出Test然后调用方法输出静态代码快的A

知识点总结


异常try catch 执行顺序

题目

分析

1. 先调用方法执行try语句输出A
2. 执行fun2()方法 执行之后输出C
3. 但是还是先不输出D 然后调回finally语句输出B
4. 最后输出D
5. 最后的顺序就是: ACBD

知识点总结

try中含有return时,如果return中调用了函数或者表达式,会先执行,如果还有finally的话,会继续执行完finally的内容再返回。

list集合扩容

题目

分析

10 15 22 33 49 73 109 所以是6次

知识点总结

初始值为10 只有增长幅度为1.5倍

Object类方法

题目

分析

1. 应该是equals()方法

知识点总结

1. clone方法
2. getClass方法
3. toString方法
4. finalize方法
5. equals方法
6. hashCode方法
7. wait方法
8. notify方法
9. notifyAll方法

线程池参数问题

题目

分析

前三个参数是 核心线程 最大线程池 保持时间
所以说一定会有5个线程不会被结束

知识点总结


线程执行

题目

分析

最终执行顺序是 Thread 1 Thread 2 main

知识点总结


linux文件权限问题

题目

分析

说实话我感觉BCD都对

知识点总结


算数运算符的指令形式

题目

分析

>= 就是 ge greater than or equal

知识点总结

EQ 就是 EQUAL等于 
NE就是 NOT EQUAL不等于 
GT 就是 GREATER THAN大于 
LT 就是 LESS THAN小于 
GE 就是 GREATER THAN OR EQUAL 大于等于 
LE 就是 LESS THAN OR EQUAL 小于等于

指令执行结果

题目

分析

echo就是更改输出颜色
expr是修改环境变量 应该输出的是0

知识点总结


修改权限(春招出过这道题目)

题目

分析

1. 4 2 1 / r w x 就是对应的读 写 执行
2. 所以应该是 0 5(4+1) 0 

知识点总结


bash脚本文件开头(#!)

题目

分析

1. 开头就是 #!

知识点总结


获取上一条命令的返回码($?)

题目

分析

$? 可以获取上一条命令的返回码

知识点总结


linux执行文件

题目

分析

先../返回到根目录 然后> 找到目录 最后 echo执行结果

知识点总结


标准输出和错误重定向

题目

分析

1. 错误重定向 2>
2. 标准输出 >
3. 同时的话就是 &>

知识点总结

1. 错误重定向 2>
2. 标准输出 >
3. 同时的话就是 &>

抽象工厂模式

题目

分析

1. 铁桌子和木桌子的例子印象深刻
2. 虽然图看不清但是大概看出样子就觉得是A

知识点总结


京东2019春招京东Java开发试卷

题目分析

说实话觉得京东的题目比较偏基础,我这种菜鸡大部分的题目没复习的情况下还能有点思路


解空间树搜索算法

题目

分析

其实解空间树搜索算法就是我们见过的树的遍历方法,其实就是dfs和bfs。
题目中意思是一个节点可能有多次机会那么肯定是深度优先遍历算法。
广度其实就是一层一层不会出现多次,只有深度是这次到底才往回返一次,就是使用回溯法进行。因此选择回溯法

知识点总结

参考大佬博客:

https://blog.csdn.net/ncepuzhuang/article/details/8944991

两种遍历总结:


算法基本要素

题目

分析

1. 错误点:
    其实就是当时对于D答案查看不仔细,没看出竟然是数据机构????
2. 正确选项:
    算法基本要素=对数据对象的运算和操作+算法的控制结构

知识点总结

1. 算法的基本要素:
    1.1 数据对象的运算和操作
    1.2 控制结构

选择排序

题目

分析

开始时:900,512,613,700,810
第一趟后:512,900,613,700,810  512要和900更换位置
第二趟后:512,613,900,700,810  613要和900更换位置
第三趟后:512,613,700,900,810  700要和900更换位置

知识点总结

选择排序:获取未排序部分数据中最小的数据放到数组的最前面,以此类推


递归次数

题目

分析

分析计算步骤:
    x(8) = x(6)+ x(4) +1 = 9
    x(6) = x(4)+ x(2) +1 = 5
    x(4) = x(2)+ x(0) +1 = 3
但是此题目有点歧义,x(8)=9之后还会进行调用就还会有9次,一共是18次

知识点总结

递归调用逻辑执行,一步一步进行即可


线性链表

题目

分析

D 线性链表中个元素位置不一定连续,存储顺序也是任意的 D对
AB 双向链表的表头元素不一定在其他元素前面 AB错
C 数组是连续的,线性链表不是必须连续

知识点总结

1. 分类:
    1.1 单向链表 
    1.2 双向循环链表 
    1.3 循环链表
2. 定义:    
    2.1 具有链接存储结构的线性表,用一组地址任意的存储单元存放线性表中的数据元素,逻辑上相邻的元素在物理上不要求也相邻,不能随机存取。
    2.2 结点描述:结点(表示数据元素) =数据域(数据元素的映象) + 指针域(指示后继元素存储位置)

朴素模式匹配算法时间复杂度

题目

分析

1. 最坏时间算法:每次都匹配字串最后一位
因此:
    2.1 匹配次数为m
    2.2 匹配到主串的尾部:匹配次数为n-m+1
    2.3 所以结果是m*(n-m+1)

知识点总结

KMP模式匹配算法


广义表(Lists)

题目

分析

题目中的广义表E((a,(a,b),((a,b),c)))

1. 广义表长度:
    最大括号里面是(a,(a,b),((a,b),c)) --> 长度=逗号数0+1=1

2. 广义表深度:
    (a,(a,b),((a,b),c)):4+1=5
    a:0+1=1
    (a,b):1+1=2
    ((a,b),c):2+1=3     --> 深度=max(5,1,2,3)=5

知识点总结

1. 长度:最大括号里面的逗号数+1
2. 深度:最大括号根据逗号拆开的每个部分的括号匹配数+1的最大值

TCP协议

题目

分析

1. 多播服务的是UDP (网上视频会议、网上视频点播特别适合采用多播方式)

知识点总结

1. TCP面向连接 可靠传输
2. TCP可靠交付
3. TCP报文头部长 传输开销大

bash shell环境

题目

分析

cz在bash shell环境下是将前台任务转入后台

知识点总结


Order by子句

题目

分析

order by子句默认是asc(升序)

知识点总结

1. order by子句是根据指定列对结果集进行排序
2. 有两种方法 asc(升序默认)和desc(降序)

看UML图识别设计模式

题目

分析

1. 最投机取巧的就是观察类和接口名判断是生成器模式
2. 生成器模式也叫建造者模式,功能就是使用简单的对象一步步构成复杂对象

知识点总结


看描述识别设计模式

题目

分析

观察者模式:一个对象修改,依赖对象也会被自动通知

知识点总结

  • 观察者模式
    对象间存在一对多的关系,如果一个对象被修改,会自动通知它的依赖对象

  • 建造者模式/生成器模式
    使用对各简单的对象一步一步构建出一个复杂对象


linux指令修改权限

题目

分析

1. 考点:就是linux指令和文件权限修改
2. 思路:
    2.1 使用chomd命令改变文件权限
    2.2 owner group others三种身份对应read write execute三种权限
    2.3 增加可读不可写所以第一组和第三组默认为0,第二组中添加r-x即可 chomd+050
    2.4 因为对于目录,要浏览r必须赋予进入x的权限

知识点总结


shell语句生成/test文件

题目

分析

1. >/test:输出重定向,没有文件就创建
2. 反引号(''):其中的命令执行后返回结果
3. touch指令: touch /test

知识点总结

1. 反引号 :将反引号其中的命令执行后返回结果
2. touch指令 :创建/xxx文件
3. > :输出重定向

shell头

题目

分析

1. A是执行
2. B是注释
3. C是错误的

知识点总结


shell脚本参数

题目

分析

1. $1 : 传递给脚本/函数的第一个参数
2. $? : 退出状态/函数返回值

知识点总结


Redis数据类型

题目

分析

1. 四个都是 主要是加了s之后迷惑人

知识点总结

redis一共包含5种数据类型
    ①字符串 String (最基本的类型,可包含任意数据)
    ②哈希 Hash (String类型的field、value映射表)
    ③列表 List (字符串列表,有序不唯一)
    ④集合 set (字符串集合,无序唯一)
    ⑤集合排序 zset (字符串集合,可以通过设置分数score进行排序)

Redis内容

题目

分析

Redis使用数据分片引入哈希槽(hash slot)来实现

知识点总结

1. 主要为了方便数据读取,所以redis主要消耗内存资源
2. redis集群之间是异步复制
3. 分区可以让redis管理更大内存

JVM新生代

题目

分析

1. 新生代区域分为: Eden from to 三个区域

知识点总结

1. Java堆是JVM管理最大的一块内存空间,主要存放各种类的实例对象。
2. Java堆
     2.1 新生代(Young) Eden / From Survivor / To Survivor
     2.2 老年代(Old)
3. 堆大小通过参数 -Xms -Xmx指定         
4. java每次只会使用eden和其中一块survivor区域来为对象服务,所以无论如何都有一块survivor区域是空闲的

示意图:


符号运算级

题目

分析

1. 优先级: ++/-- > 四则运算
2. 所以这道题就是先减b之后a-- 然后减b后a--

知识点总结

优先级


JVM内存部分

题目

分析

1. stacks栈 A对
2. PC寄存器就是程序计数器 B对
3. Heap堆  C对
4. Head Frame D错没出现    

知识点总结


JAVA数据类型大小

题目

分析

1. int是四个字节 所以A错
2. double是八个字节 所以C错
3. long是八个字节 所以D错

知识点总结

//8种基本类型:    
    1. byte : 1
    2. int : 4
    3. long : 8
    4. char : 2
    5. float : 4 
    6. double : 8
    7. boolean : 1

Integer包装类

题目

分析

Integer范围是[-128,127] 范围内是true 超过范围是false

知识点总结

1. Integer范围是 -128 - 127
2. 只要是在范围内就是被缓存了,每个对象的内存地址都是相同的。超过就新建一个Integer对象。

字符串方法(split()方法底层)

题目

分析

没找到分隔符会把字符串当一个长为1的字符串数组,所以选1

知识点总结

split方法默认是找不到就输出长度为1的字符串数组

前后端数据过程

题目

分析

ABC选项的数据都是不可信数据 D对

知识点总结

前后端数据采用信息安全部发布的XSSFilter做进行相应编码

开放定址法(解决哈希冲突)

题目

分析

1. HashMap 链地址法(链表方式连接)
2. ThreadLocal 开放地址法(纯数组连接)

知识点总结

1. HashMap 链地址法(链表方式连接)
2. ThreadLocal 开放地址法(纯数组连接)

线程同步问题

题目

分析

1. CountDownLatch:允许一个/多个线程等待特定情况,同步完成线程中其他任务

知识点总结

1. CountDownLatch:
    允许一个/多个线程等待特定情况,同步完成线程中其他任务.(例如:百米赛跑)
2. CyclicBarrier:
    让指定数量的线程等待期他所有的线程都满足某些条件之后才继续执行.(例如:坐车人齐了才可以走)

volatile和synchronized区别

题目

分析

synchronized:原子性 + 有序性 + 可见性
volatile:有序性 + 可见性(缺一个原子性)

知识点总结

1. volatile:
    1.1 线程同步的轻量级实现
    1.2 修饰变量

2. synchronized:
    2.1 为了减少获得锁和释放锁带来的性能消耗引入偏向锁和轻量级锁以及其它各种优化
    2.2 修饰方法和代码块

java参数传递

题目

分析

D中 集合和maps元素也是传递对象,所以和C一样应该是对的

知识点总结

1. 改变基础类型参数不会影响原始参数值
2. 改变对象参数引用只是修改形参保存的地址,但是不会影响原始引用
3. 修改一个对象的属性影响对象参数
4. 修改集合和Maps对象和第三条一样

spring代理配置

题目

分析

使用aop:aspectj-autoproxy标签
<aop:aspectj-autoproxy proxy-target-class="true"/>

知识点总结

1. jdk动态代理(默认)
2. cglib代理

拼多多2020校招部分编程题合集

多多的魔术盒子(二进制位数)

题目

分析

//根据规律可知,即算出该十进制的二进制表示的位数
//比如5,二进制表示为101,位数为3,则最少操作次数为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
27
28
29
30
31
32

public class Main {
public static void main(String[] args) {
//根据规律可知,即算出该数的二进制表示的位数
//比如5,二进制表示为101,位数为3,则最少操作次数为3
Scanner input=new Scanner(System.in);
int t=input.nextInt();
int[] a=new int[t];
//循环遍历输入
for (int i=0;i<t;i++) {
a[i]=input.nextInt();
}
int[] res=zhao(a); //调用方法得到结果
//循环遍历输出
for(int i=0;i<res.length;i++){
System.out.println(res[i]);
}
}

public static int[] zhao(int[] a){
int[] b=new int[a.length]; //新建数组接住结果
//遍历获取结果
for(int i=0;i<b.length;i++){
//数字转二进制字符串
String temp=Integer.toBinaryString(a[i]);
//获取每个数字的最少次数(字符串长度)
b[i]=temp.length();
}
return b;
}

}

结果


多多的排列函数(规律构造)

题目

分析

在{An}的所有排列中,能让F(N)取得的最大最小值为多少。
例如 5,6,7,8,我们把它们两两一组 |||8-6|-7|-5|=0,最小值是0;
猜测最小值的变化也是4个一组。看到min只有2种取值。0,1,最大值自然就是N-getmin(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
30
31

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int nums = sc.nextInt();
for (int i = 0; i<nums; i++){
int N = sc.nextInt();
maxandmin(N);
}
}

public static void maxandmin(int N){
if (N==1||N==2){
System.out.println("1 1"); //如果n是1或者2就输出 1 1
return;
}
//之后每4个一组 0011
int min = getmin(N);
int max = N-getmin(N-1);
System.out.println(min + " " + max);
}

public static int getmin(int N){
int temp = (N-2)%4; //temp临时值接住
if (temp==1 || temp==2){
return 0;
}
else return 1;
}

}

结果


多多的电子字典

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt(); //n个a
int m=input.nextInt(); //m个b
int k=input.nextInt(); //第k小的单词
System.out.println(dik(n,m,k));
}

public static String dik(int n,int m,int k){
String res="123";

return res;
}

}

结果


Git复习

Git复习目录

1. 版本控制
2. Git和SVN区别
3. Git历史
4. Git安装和环境配置
5. 常用Linux命令
6. Git的必要配置
7. Git的工作原理
8. Git项目创建和克隆
9. Git基本操作命令
10. 码云的注册和使用
11. 配置SSH公钥以及创建远程仓库
12. IDEA中集成Git操作
13. Git分支说明

版本控制(Revision control)

含义

开发过程中用于管理我们对文件/目录/工程等内容的修改历史,方便更改历史记录,备份以便恢复以前的版本的软件工程技术。

  • 实现跨区域多人协同开发
  • 追踪和记载一个/多个文件的历史记录
  • 组织和保护你的源代码和文档
  • 统计工作量
  • 并行开发、提高开发效率
  • 跟踪记录整个软件开发过程
  • 减少开发人员负担,节省时间

主流版本控制器

  • Git(主流)
  • SVN(主流)
  • CVS
  • VSS
  • TFS
  • visual Studio Online

版本控制分类

本地版本控制 RCS

集中版本控制 SVN

1. 所有的版本数据都存在服务器上
2. 用户的本地只有自己以前所同步的版本
3. 如果不连网的话,用户就看不到历史版本,也无法切换版本验证问题,或在不同分支工作。
4. 所有数据都保存在单一的服务器上,有很大的风险这个服务器会损坏,这样就会丢失所有的数据
5. 当然可以定期备份。代表产品:SVN、CVS、VSS

分布式版本控制 Git

1. 每个人都拥有全部的代码!安全隐患!
2.    所有版本信息仓库全部同步到本地的每个用户,这样就可以在本地查看所有版本历史,可以离线在本地提交,
3.    只需在连网时push到相应的服务器或其他用户那里。
4.    由于每个用户那里保存的都是所有的版本数据,只要有一个用户的设备没有问题就可以恢复所有的数据,
5.    缺点就是增加了本地存储空间的占用。

不会因为服务器损坏或者网络问题,造成不能工作的情况!


Git和SVN区别

Git(分布式版本控制系统)

1. 没有中央服务器。每个人的电脑就是一个完整的版本库,
2. 工作的时候不需要联网了,因为版本都在自己电脑上。
3. 协同的方法:比如说自己在电脑上改了文件A,其他人也在电脑上改了文件A,这时,你们两之间只需把各自的修改推送给对方,就可以互相看到对方的修改了。
4. Git可以直接看到更新了哪些代码和文件!

SVN(集中式版本控制系统)

1. 版本库是集中放在中央服务器的,
2. 而工作的时候,用的都是自己的电脑,
3. 所以首先要从中央服务器得到最新的版本,然后工作,完成工作后,需要把自己做完的活推送到中央服务器。
4. 集中式版本控制系统是必须联网才能工作,对网络带宽要求较高。

Git历史

Git是免费、开源的,最初Git是为辅助 Linux 内核开发的,来替代 BitKeeper!


Git安装和配置

下载

1. 官网 : https://git-scm.com/
2. 淘宝镜像 : http://npm.taobao.org/mirrors/git-for-windows/

安装

1. 无脑下一步即可(换安装路径)

启动

分为Bash/CMD/GUI三种图标

  • Git Bash:Unix与Linux风格的命令行,使用最多,推荐最多

  • Git CMD:Windows风格的命令行

  • Git GUI:图形界面的Git,不建议初学者使用,尽量先熟悉常用命令


常用的Linux命令

具体的可以参考我的linux博客篇


Git配置

查看所有配置

git config -l

查看系统级(system)配置

指令:git config –system –list

配置文件存在位置:一般是Git安装目录下的gitconfig文件

文件内容和指令框对比

查看当前用户级(global)配置

指令:git config –global –list

配置文件存在位置:一般是当前用户的目录下的.gitconfig文件

文件内容和指令框对比


Git设置用户名和邮箱(必须!!!)

1. 安装Git后首先要做的事情是设置你的用户名称和e-mail地址。
2. Git提交都会使用该信息。它被永远的嵌入到了你的提交中:
3. 指令格式:
    git config --global user.name "XXX"  //名称
    git config --global user.email XXX@qq.com  //邮箱

Git基本理论(imp)

四个区域介绍

1. 工作目录(Working Directory):平时放代码的地方

2. 暂存区(Stage/Index):临时存放代码改动的一个文件,保存即将提交到文件列表信息

3. 资源库(Repository/Git Directory):安全存放数据的位置(HEAD指向最新的仓库版本)

4. 远程的git仓库(Remote Directory):托管代码的服务器

5. 四个区域指令操作图示:

工作流程

1. git add . : 在文件目录中添加/修改文件
2. git commit : 将需要进行版本管理的文件放入暂存区域
3. git push  : 将暂存区域的文件提交到git仓库


Git项目搭建

创建工作目录与常用指令

本地仓库搭建(上传项目)

参考别人的步骤(亲测有用!!)

https://www.cnblogs.com/jf-67/p/7086659.html?utm_source=itdadao&utm_medium=referral

克隆远程仓库(下载别人项目)

1. 随便位置新建一个文件夹 -- 右键git bash输入git init初始化 -- 输入git clone XXXX  //xxx就是人家项目的路径(项目右上角绿色框)
2. 去gitee/github克隆一个测试

Git文件操作(四种状态)

四种状态

查看文件状态(git status)

忽略文件(主目录新建.gitignore文件)


码云

U1S1其实就是中国版的github(不需要翻墙)

具体如何使用参考以下链接(百度也有方法)

https://mp.weixin.qq.com/s/Bf7uVhGiu47uOELjmC5uXQ


IDEA集成Git

这里展示的是和码云配套:

1. idea新建项目,绑定git(远程的git文件目录拷贝到项目中即可)
2. 修改文件(使用Idea操作git)
    1. 添加到暂存区
    2. commit提交
    3. push到远程仓库
3. 提交测试

Git分支

git分支指令:

可能出现的问题:

1. 同文件合并分支都被修改会引起冲突:
    解决方法:我们可以修改冲突文件后重新提交!选择要保留他的代码还是你的代码
2. master主分支用来发布新版本
3. 新建dev分支上工作:dev分支代码稳定后可以合并到主分支master上

参考文档

当时学习时候看的B站狂神的视频:

https://mp.weixin.qq.com/s/Bf7uVhGiu47uOELjmC5uXQ


leetcode剑指offer

数组中重复的数字(哈希表/排序遍历/二分)

题目

分析

1. 哈希表:使用hashset.contains方法选重复的弹出
2. 排序遍历:数组排序之后遍历如果前后有相同的就弹出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static int findRepeatNumber(int[] nums) {
int res=0;
Set<Integer> set=new HashSet<>();
Arrays.sort(nums); //排序
for(int i=0;i<nums.length;i++){
if(set.contains(nums[i])){
return nums[i]; /如果出现过就弹出这个值
}else{
set.add(nums[i]); //没出现过就添加到set里面
}
}
return 0;
}

结果


二维数组中的查找(双指针/暴力法)

题目

分析

1. 暴力法: 二重循环遍历查找
2. 双指针:定义hang和列两个指针,然后依次判断和target大小(因为行和列都是递增的)
    2.1 如果matrix[hang][lie]==target 输出true
        如果matrix[hang][lie]<target 这列上面都小 所以换下一行hang++
        如果matrix[hang][lie]>target 这行后面的都大 所以换上一列   

代码

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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int[][] a=new int[][]{
{1,4,7,11,15},
{2,5,8,12,19},
{3,6,9,16,22},
{10,13,14,17,24},
{18,21,23,26,30}
};
int target=input.nextInt();
System.out.println(findNumberIn2DArray(a,target));
}

public static boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int hang=0; //从第一行开始
int lie=matrix[0].length-1; //从最后一列开始
while(hang<matrix.length&&lie>=0){
if(matrix[hang][lie]==target){
return true; //找到了就返回true
}else if(matrix[hang][lie]>target){
lie--; //这行后面都大 所以换前一列lie--
}else if(matrix[hang][lie]<target){
hang++; //这列上面都小 所以换下一行hang++
}
}
return false; //默认找不到false
}

}

结果


替换空格(StringBuilder类)

题目

分析

1. StringBuilder类 : sb.append()方法添加,然后遇到空格就分别添加% 2 0
2. 新建char数组: 直接定义下标,然后遇到空格就按顺序填充% 2 0
3. 字符串替换 : s.replace(" ","%20"); 

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.nextLine(); //一定要用nextLine() 因为字符串有空格!!!!!!
System.out.println(replaceSpace(s)); //调用方法返回结果
}

public static String replaceSpace(String s) {
StringBuilder sb=new StringBuilder(); //新建sb对象
for(int i=0;i<s.length();i++){
char c=s.charAt(i); //获取字符串每个位置字符
if(c==' '){
sb.append('%'); //遇到空格就分别添加 % 2 0
sb.append('2');
sb.append('0');
}else{
sb.append(c); //不是空格就按序添加进去
}
}
return sb.toString(); //sb对象要转成字符串输出
}

}

结果


从尾到头打印链表(stack栈)

题目

分析

1. 新建栈存入所有链表元素
2. 然后依次出栈存入数组
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

//定义好的链表类
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}


//实现类
public class LianBiao {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
ListNode head=new ListNode(1);
ListNode l2=new ListNode(3);
head.next=l2; // 1 -> 3
ListNode l3=new ListNode(2);
l2.next=l3; // 1 -> 3 -> 2
System.out.println(Arrays.toString(reversePrint(head)));
}

public static int[] reversePrint(ListNode head) {
//栈存储链表所有元素
Stack<ListNode> stack=new Stack<ListNode>();
//按需存储压栈
while(head!=null){
stack.push(head); //不断地压入栈
head=head.next;
}
//结果返回到int数组
int size=stack.size(); //获取stack栈的长度
int[] a=new int[size]; //后面才能确定长度
for (int i = 0; i < size ; i++) {
a[i]=stack.pop().val; //依次弹出
}
return a; //返回数组元素
}

}

结果


重建二叉树

题目

分析

代码

1
2


结果


实现队列(双栈)

题目

分析

1. 思路:使用双栈(stack1添加元素/stack2删除元素)
2. 具体实现步骤:
    2.1 生成两个栈stack(stack1用来实现添加元素/stack2用来实现删除元素)
    2.2 stack1只需要push
    2.3 stack2先将stack1压栈 然后stack2再出栈

代码

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
class CQueue {
Deque<Integer> stack1; //创建两个stack栈
Deque<Integer> stack2;

public CQueue() {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}

public void appendTail(int value) {
stack1.push(value); //压栈
}

public int deleteHead() {
// 如果第二个栈为空
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop()); //把stack1压入stack2
}
}
if (stack2.isEmpty()) {
return -1; //stack2为空 返回-1
} else {
int deleteItem = stack2.pop();
return deleteItem; //stack2不为空 出栈
}
}
}

结果


斐波那契数列(动态规划/递归)

题目

分析

1. 递归: 从第二位开始都是fib(n)=fib(n-1)+fib(n-2)
2. 动态规划:
    2.1 每次都是abc三个数字不断替换迭代
    2.2 每次通过数组元素不断替换迭代 

代码

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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
System.out.println("递归:"+fib(n));
System.out.println("动态规划:"+fiber(n));
}

//递归
public static int fib(int n) {
if(n<=1){
return n; // 0 1
}
if(n==2){
return 1; // 0 1 1
}
return (fib(n-1)+fib(n-2))%1000000007;
}

//动态规划
public static int fiber(int n) {
int a=0; //第一个值
int b=1; //第二个值
int c=0; //第三个值
//不断迭代
for(int i=0;i<n;i++){
c=(a+b)%1000000007; //每次计算都要取余
a=b;
b=c;
}
return a;
}

}

结果


青蛙跳台阶(递归/动态规划)

题目

分析

1. 递归: 从第二位开始都是fib(n)=fib(n-1)+fib(n-2)
2. 动态规划:
    2.1 每次都是abc三个数字不断替换迭代
    2.2 每次通过数组元素不断替换迭代 

思路:

代码

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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
/*for (int i = 0; i < n; i++) {
a[i]=input.nextInt();
}*/
System.out.println("递归:"+numWays(n));
System.out.println("动态规划:"+numWayser(n));
}

public static int numWays(int n) {
if(n<=1){
return 1; // 1 1
}
if(n==2){
return 2; // 1 1 2
}
return (numWays(n-1)+numWays(n-2))%1000000007;
}

public static int numWayser(int n) {
int a=1; //跳1个台阶 1
int b=1; //跳1个台阶 1
int c=0; //跳2个台阶 2
//不断迭代
for(int i=0;i<n;i++){
c=(a+b)%1000000007; //每次计算都要取余
a=b;
b=c;
}
return a;
}

}

结果


旋转数组的最小数字(排序/二分法)

题目

分析

1. 排序:排序之后输出数组a[0]即可
2. 二分法:就是不断的缩小范围(通过确定缩小条件)

代码

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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for (int i = 0; i < n; i++) {
a[i]=input.nextInt();
}
System.out.println(minArray(a));
}

//排序输出
public static int minArray(int[] numbers) {
Arrays.sort(numbers); //排序
return numbers[0]; //输出最小的第一位
}

//二分法
public static int minArray(int[] numbers) {
int i=0; //左指针
int j=numbers.length-1; //右指针
while(i<j){
int z=(i+j)/2; //找中间位置
if(numbers[z]>numbers[j]){
i=z+1; //min值在右边出现
}else if(numbers[z]<numbers[j]){
j=z; //min值在左边出现
}else {
j--; //无法确定范围 缩小范围继续找
}
}
return numbers[i];
}

}

结果


矩阵中的路径(DFS+剪枝)

题目

分析

代码

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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
char[][] a= new char[][]{ //定义好要找的路径集
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}};
String word=input.next(); //输入要找的路径
System.out.println(exist(a,word)); //调用方法
}

public static boolean exist(char[][] board, String word) {
char[] words=word.toCharArray(); //字符串转字符数组
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(dfs(board, words, i, j, 0)) {
return true; //二重循环调用方法
}
}
}
return false; //默认失败
}

//board是要找的路径集合 words字符串转的字符数组 i和j是board下标 k是找到了几个
private static boolean dfs(char[][] board, char[] words, int i, int j, int k) {
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]){
return false; // i和j越界 / 找不到符合
}
if(k == words.length - 1) { //已经全部找到了!!!
return true;
}
char temp=board[i][j]; //中间值
board[i][j]='/'; //用过之后改成 ‘/’
//上下左右都找找
boolean res=dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i - 1, j, k + 1) ||
dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i , j - 1, k + 1);
board[i][j]=temp; //用完之后再回溯返回原值
return res;
}

}

结果


机器人的运动范围

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int m=input.nextInt();
int n=input.nextInt();
int k=input.nextInt();
System.out.println(movingCount(m,n,k));
}

public static int movingCount(int m, int n, int k) {
int res=123;
return res;
}

}

结果


剪绳子(动态规划/归类)

题目

分析

尽量都凑出来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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int m=input.nextInt();
System.out.println(cuttingRope(m));
}

public static int cuttingRope(int n) {
if(n<=3){
return n-1;
}
int a=n/3;
int b=n%3;
if(b==0){
return (int)Math.pow(3,a);
}
if(b==1){
return (int)Math.pow(3,a-1)*4;
}
return (int)Math.pow(3,a)*2;
}

}

结果


剪绳子II(贪心/快速幂)

题目

分析

1. 与上面的剪绳子1.0相比需要取余,我们选择贪心算法
2. 具体实现:
    2.1 摆出n<4的每一个可能结果
    2.2 摆出n>4的while循环
    2.3 相比于1.0的题目我们其实还是不断的乘3,然后取余即可(n<=4跳出来)
    2.4 因为跳出来的n可能是4 3 2三种可能(不可能n最后为1),但是这三种情况其实也是直接乘n之后取余即可

代码

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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int m=input.nextInt();
System.out.println(cuttingRope(m));
}

public static int cuttingRope(int n) {
//把其他特定条件列出
if(n==2){
return 1; //分为1 1
}
if(n==3){
return 2; //分为1 2
}
if(n==4){
return 4; //分为2 2
}
if(n<4){
return n-1; //如果长度<4 返回 1 3
}
long res=1; //最终结果
int mod=1000000007;
while(n>4){
res=res*3; //不停地乘3
res=res%mod; //然后取余 (防止溢出)
n=n-3; //每次使用完减去3
}
res=res*n; //乘上剩下的n (最后剩下的肯定是4 3 2 这三种情况就直接乘n即可)
res=res%mod; //不要忘记取余
return (int)res; //返回最后res
}

}

结果


二进制中1的个数(位运算/按位判断)

题目

分析

1. 按位判断:就相当于十进制按位拆开,判断每一位是1就计数器+1
2. 位运算: n&(n−1) 二进制最右边的1变为0,其余不变。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int m=input.nextInt();
System.out.println(hammingWeight(m));
}

public static int hammingWeight(int n) {
int res=0; //接最后结果
while(n!=0){
res++;
n=n&(n-1); //消除数字n最右边的1
}
return res;
}

}

结果


删除链表的节点(跳过要删除的节点连接)

题目

分析

1. 其实就是考虑两件事情:定位和删除
2. 定位:设置一个临时temp=head,然后去判断head.val和val的大小直到找到。
3. 删除:我们考虑提前找head.next.val和val去判断,这样的话我找到就可以head.next=head.next.next,不然一般的删除,我都遍历到要删除的节点了,但是不知道怎将前面的节点找到!!!

代码

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

public class DelJie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
ListNode head=new ListNode(4);
ListNode l2=new ListNode(5);
head.next=l2; // 4 -> 5
ListNode l3=new ListNode(1);
l2.next=l3; // 4 -> 5 -> 1
ListNode l4=new ListNode(2);
l3.next=l4; // 4 -> 5 -> 1 -> 9
int val=input.nextInt(); //输入要删除的节点
}

public static ListNode deleteNode(ListNode head, int val) {
if(head==null){ //如果链表为空返回null
return null;
}
if(head.val==val){ //如果当前节点就是要删除的
return head.next; //返回head.next就行
}
ListNode temp=head; //head节点给一个临时temp节点
while(temp.next!=null){
if(temp.next.val==val){ //如果下一个节点是要删除的节点
temp.next=temp.next.next; //直接这个节点的下一个节点连接下下一个节点(跳过要删除的节点)
}else{
temp=temp.next; //不是的话就继续下一个节点
}
}
return head; //返回原节点
}

}

结果


正则表达式匹配(动态规划)

题目

分析

主要是各种情况:

https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zhu-xing-xiang-xi-jiang-jie-you-qian-ru-shen-by-je/

代码

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
43
44
45
46

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.next(); //输入s
String p=input.next(); //输入p
System.out.println(isMatch(s,p)); //调用方法
}

public static boolean isMatch(String s, String p) {
int n=s.length(); //获取s的长度
int m=p.length(); //获取p的长度
boolean[][] f=new boolean[n+1][m+1]; //获取结果(多一位方便取)
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
//空正则
if (j==0){ //要判断的p字符串为空
f[i][j]=i==0;
}
//非空正则
else{
//分为 * 和 非*
if(p.charAt(j-1)!='*'){
//两个倒数第二位一样 p的倒数第二位还是.
if(i>0&&(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.')){
f[i][j]=f[i-1][j-1];
}
}
else{
//不看*之前的内容
if(j>=2){
f[i][j]|=f[i][j-2]; //直接砍掉p的后面两个
}
//看*之前的内容
if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
f[i][j] |= f[i - 1][j]; //s串前移一个
}
}
}

}
}
return f[n][m]; //返回当前位置结果
}

}

结果


表示数值的字符串/有效数字(分情况讨论)

题目

分析

1. 主要分为数字/./指数形式/+-开头/其他不符合条件情况
2. 具体实现:
    先设定numSeen,dotSeen和eSeen三种boolean变量,分别代表是否出现数字、点和E.然后遍历目标字符串
    1.判断是否属于数字的0~9区间
    2.遇到点的时候,判断前面是否有点或者E,都需要return false
    3.遇到E的时候,判断前面数字是否合理,是否有E,并把numSeen置为false,防止E后无数字
    4.遇到-+的时候,判断是否是第一个,如果不是第一个判断是否在E后面,都不满足则return false
    5.其他情况都为false
    6.最后返回numSeen的结果即可

代码

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
43
44
45
46
47
48
49

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.next();
System.out.println(isNumber(s));
}

public static boolean isNumber(String s) {
if(s==null||s.length()==0) {
return false; //字符串为空格
}
boolean numSeen=false; //出现数字
boolean dotSeen=false; //出现 .
boolean eSeen=false; //出现 e/E
char arr[]=s.trim().toCharArray(); //转字符数组(去除空格
for(int i=0; i<arr.length; i++){
if(arr[i]>='0'&&arr[i]<='9'){ //数字
numSeen=true; //更改为true
}
else
if(arr[i]=='.'){ // .
if(dotSeen||eSeen){ //在这个.之前有 . / e/E就false (举例: . . / e .)
return false; //在这个.之前有数字没啥影响( 举例:123. )
}
dotSeen=true; //更改为true
}
else
if(arr[i]=='E'||arr[i]=='e'){ // e/E
if(eSeen||!numSeen){
return false; //在这个之前没有数字 / . 就false
}
eSeen=true; //更改为true
numSeen=false; //设置成false防止e/E后面没有数字
}
else
if(arr[i]=='+'||arr[i]=='-'){ // + / -
if(i!=0&&arr[i-1]!='e'&&arr[i-1]!='E'){ // 不是第一位出现 / 前一个不是e/E
return false;
}
}
else{ //其他情况
return false; //其他情况都是false
}
}
return numSeen; //返回数字属性
}

}

结果


调整数组顺序奇数在偶数前面(二分法/分情况添加)

题目

分析

1. 二分法:定义两个指针,就是左边是偶数右边是奇数才可以交换,否则就左右指针靠近。
2. 分情况添加:新建数组或者stringbuilder然后奇数添加左边开始,偶数从最右边往左边添加。

代码

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 class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for (int i = 0; i < a.length; i++) {
a[i]=input.nextInt();
}
System.out.println(Arrays.toString(exchange(a)));
}

public static int[] exchange(int[] nums) {
int i=0; //左指针
int j=nums.length-1; //右指针
int temp=0; //临时交换用
while(i<j) {
while (i < j && ((nums[i] % 2) != 0)) {
i++; //奇数往后移动
}
while (i < j && ((nums[j] % 2) == 0)) {
j--; //偶数往前移动
}
//左边是偶数 右边是奇数的话就交换
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}

}

结果


链表中倒数第K个节点(两个链表)

题目

分析

1. 初始化两个指针former和latter指向头节点head
2. 然后先让前指针former前进k步(former在第k个位置,latter还在0的位置)
3. 两个指针然后继续走,直到former走结束,然后latter到了的位置就是我们要的位置,然后输出latter指针

代码

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

public class DaoShuK {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
ListNode head=new ListNode(4);
ListNode l2=new ListNode(5);
head.next=l2; // 4 -> 5
ListNode l3=new ListNode(1);
l2.next=l3; // 4 -> 5 -> 1
ListNode l4=new ListNode(2);
l3.next=l4; // 4 -> 5 -> 1 -> 9
int k=input.nextInt(); //输入要查看的倒数第k个节点
System.out.println(getKthFromEnd(head,k));
}

public static ListNode getKthFromEnd(ListNode head, int k) {
ListNode former = head, latter = head; //初始化两个指向头节点head的链表
// 假设5个数字 求倒数第二个(正数第四个) 5-2+1=4
for(int i = 0; i < k; i++) {
if(former == null) return null;
former = former.next; //先让former提前走k步
}
// former走了2步 现在在第二个数位置
while(former != null) {
former = former.next; //一起走了3步之后
latter = latter.next; //latter到了倒数第k个值得位置
}
return latter; //返回latter链表
}

}

结果


反转链表(栈/双指针)

题目

分析

1. 因为要反转我们可以使用先进后出的进行存储
2. 新建链表然后依次出栈即可

代码

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

public class DaoShuK {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
ListNode head=new ListNode(4);
ListNode l2=new ListNode(5);
head.next=l2; // 4 -> 5
ListNode l3=new ListNode(1);
l2.next=l3; // 4 -> 5 -> 1
ListNode l4=new ListNode(2);
l3.next=l4; // 4 -> 5 -> 1 -> 9
System.out.println(reverseList(head));
}

public static ListNode reverseList(ListNode head) {
//新建栈存链表元素
Stack<Integer> stack = new Stack<Integer>();
//新建tmp链表用来将head存入栈
ListNode tmp = head;
while(tmp!=null){
stack.push(tmp.val); //压栈
tmp = tmp.next; //链表往后移
}
//因为已经用完了所以重新指向head
tmp = head;
while(tmp!=null){
tmp.val = stack.pop(); //出栈
tmp = tmp.next; //链表往后移动
}
return head; //因为之前把head位置的值改了就从head输出即可
}

}

结果


合并两个排序的链表(新建链表)

题目

分析

1. 新建链表l3存放结果,一开始要自定义一个值当做假的开始,等我们算出答案后return l3.next即可
2. 新建cur链表指向l3,然后通过判断l1和l2的val值确定插入到cur链表的顺序。
3. 肯定会有l1和l2长度不相等的情况,while之后要判断是否还有后续的要添加

代码

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
43
44
45
46
47
48
49

public class DaoShuK {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
//第一个链表l1
ListNode l1=new ListNode(1);
ListNode l12=new ListNode(2);
l1.next=l12; // 1 -> 2
ListNode l13=new ListNode(4);
l12.next=l13; // 1 -> 2 -> 4
//第二个链表l2
ListNode l2=new ListNode(1);
ListNode l22=new ListNode(3);
l2.next=l22; // 1 -> 3
ListNode l23=new ListNode(4);
l22.next=l23; // 1 -> 3 -> 4
//调用方法返回结果
System.out.println(mergeTwoLists(l1,l2));
}

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null){ //l1链表为空
return l2; //直接返回l2链表
}
if(l2==null){ //l2链表为空
return l1; //直接返回l1链表
}
ListNode l3=new ListNode(0); //前置伪头节点(只是为了连起来)
ListNode cur=l3;
while(l1.next!=null&&l2.next!=null){
if(l1.val>l2.val){
cur.next=l2;
l2=l2.next;
}else{
cur.next=l1;
l1=l1.next;
}
cur=cur.next;
}
//跳出while肯定是有一个为空
if(l1.next!=null){
cur.next=l1.next;
}else{
cur.next=l2.next;
}
return l3.next; //第一个位置是伪头节点
}

}

结果


树的子结构(递归求子结构)

题目

分析

参考思路:

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/tao-wa-ta-lai-liao-jing-pin-tu-jie-by-orangex/

具体实现总结:
1. isSubStructure(TreeNode A,B)用来判断是不是这个节点,找的话找isPartSame方法判断是不是这个部分,如果找不到就找当前节点的左节点和右节点是否符合
2. isPartSame方法如果找到了这个值,判断它的左节点和右节点的是不是符合(递归)

代码

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

/**
* 定义树类:
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public static boolean isSubStructure(TreeNode A, TreeNode B) {
// A/B结束了还没找到
if(A == null || B == null){
return false;
}
//是一部分
if(isPartSame(A,B)){
return true;
}else{
//不是一部分 去找左节点或者右节点
return isSubStructure(A.left,B)||isSubStructure(A.right,B);
}
}

//判断是不是存在的一部分!
public static boolean isPartSame(TreeNode A, TreeNode B) {
if(B==null){
return true; //已经找完了
}
if(A==null){
return false; //还没找完A没了
}
if(A.val==B.val){ //当前节点找到了 找下面的节点(递归)
return isPartSame(A.left,B.left) && isPartSame(A.right,B.right);
}else{
return false; //节点都不相同
}
}
}

结果


二叉树的镜像(递归/辅助栈)

题目

分析

1. 思路:就是递归不断地往下找,然后交换左右节点值

代码

1
2
3
4
5
6
7
8
9
10
11
12

//1.递归
public static TreeNode mirrorTree(TreeNode root) {
if(root==null){
return null; //如果root为空 返回空
}
TreeNode leftRoot = mirrorTree(root.right); //递归交换当前节点的右节点
TreeNode rightRoot = mirrorTree(root.left); //递归交换当前节点的左节点
root.left = leftRoot; //两个交换
root.right = rightRoot;
return root;
}

结果


对称的二叉树(递归)

题目

分析

1. 通过递归判断左右子树的左左/左右/右左/右右的对比
2. 特殊情况:
    2.1 没有两个子节点 -- true
    2.2 只有一个子节点 -- 肯定false(不对称)
    2.3 拥有两个子节点 --值不同肯定false
    2.4 拥有两个子节点 --就要递归判断左右子树的节点是否满足(递归)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static boolean isSymmetric(TreeNode root) {
//方法调用
return isSymmetric(root,root);
}

public static boolean isSymmetric(TreeNode root1,TreeNode root2){
if(root1 == null && root2 == null){
return true; //空树
}
//只有一个子结点
if(root1 == null || root2 == null){
return false; //肯定不对称
}
//有两个子节点 但是值不相同
if(root1.val != root2.val){
return false;
}
//递归调用
return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right,root2.left);
}

结果


顺时针打印矩阵(四指针)

题目

分析

1. 如果数组为空 --返回为null
2. 如果数组不为空
     2.1 建立ArrayList集合
     2.2 建立四个坐标用于标识数组变化
     2.3 从左往右(行:top    列:left到right)
     2.4 从上到下(行:top+1到bottom  列:right) 
     2.5 从右到左(行:bottom  列:right-1到left)  --但要注意可能最后是一行就不需要进行这一步
     2.6 从下到上(行:bottom-1到top  列:left)    --但要注意可能最后是一列就不需要进行这一步

代码

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
43
44
45
46
47
48
49
50
51

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int[][] a=new int[][]{{1,2,3},{4,5,6},{7,8,9}};
System.out.println(Arrays.toString(spiralOrder(a)));
}

public static int[] spiralOrder(int [][] matrix) {
if(matrix.length == 0) {
return new int[0]; //数组空就弹出空数组
}
int row=matrix.length; //行
int col=matrix[0].length; //列
int left=0; //二维数组上面行的最左边
int right=col-1; //二维数组上面行的最右边
int top=0; //二维数组左边的最上边
int bottom=row-1; //二维数组左边的最下边
int[] a=new int[row*col];
int q=0; //控制结果数组下标
while(left<=right&&top<=bottom){
//从左到右
for(int i=left;i<=right;i++){
a[q++]=matrix[top][i]; //top行
}
//从上到下(从下一行开始向下走)
for(int i=top+1;i<=bottom;i++){
a[q++]=matrix[i][right]; //right列
}
//从右到左(从左边一列开始向左走)
if(top!=bottom) { //如果是一行的话就不需要返回去(已经左到右)
for (int i=right-1;i>=left;i--) {
a[q++]=matrix[bottom][i]; //bottom行
}
}
//从下到上(从上一行开始向上走)
if(left!=right) { //如果是一列的话就不需要返回去(已经上到下)
for (int i=bottom-1;i>top;i--) {
a[q++]=matrix[i][left]; //left列
}
}
//下一个正方形矩阵(往里缩小 -- 变换四个下标)
top++;
right--;
left++;
bottom--;
}
return a; //返回a数组
}

}

结果


包含main函数的栈(辅助栈)

题目

分析

1. 使用辅助栈然后调用方法进行解决

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class MinStack {
Stack<Integer> A, B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int x) {
A.add(x);
if(B.empty() || B.peek() >= x)
B.add(x);
}
public void pop() {
if(A.pop().equals(B.peek()))
B.pop();
}
public int top() {
return A.peek();
}
public int min() {
return B.peek();
}
}

结果


栈的压入、弹出序列(辅助栈)

题目

分析

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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int[] a=new int[]{1,2,3,4,5}; //压栈
int[] b=new int[]{4,5,3,2,1}; //压栈的一种出栈可能
System.out.println(validateStackSequences(a,b));
}

public static boolean validateStackSequences(int[] pushed, int[] popped) {
//生成新的栈(尝试模拟)
Stack<Integer> stack=new Stack<Integer>();
int count=0;
for(int i=0;i<pushed.length;i++){
stack.push(pushed[i]); //按照pushed数组入栈
while(!stack.isEmpty()&&stack.peek()==popped[count]){ //栈顶值==出栈的当前位置
stack.pop(); //出栈
count++; //后移(判断下一位出栈)
}
}
return stack.empty(); //是否所有都出栈(归0)
}

}

结果


从上到下打印二叉树(递归/bfs/辅助队列)

题目

分析

1. 队列queue: 每次用来存储树的节点(按照层次bfs的遍历方式)
2. 集合list: 每次存储当前节点的值
3. 数组res: 将list集合内容依次遍历

代码

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

public class ErChaShu {
public static void main(String[] args) {
TreeNode root=new TreeNode(3); //根节点3
TreeNode r1=new TreeNode(9);
root.left=r1;
TreeNode r2=new TreeNode(20);
root.right=r2;
TreeNode r21=new TreeNode(15);
r2.left=r21;
TreeNode r22=new TreeNode(7);
r2.right=r22;
System.out.println(Arrays.toString(levelOrder(root)));
}

public static int[] levelOrder(TreeNode root) {
//空树
if(root==null){
return new int[0]; //返回空
}
//新建队列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root); //先将root放入
//新建list集合(存放读取顺序)
List<Integer> list=new ArrayList<>();
while(!queue.isEmpty()){ //当queue为空就弹出 (所有节点都取出)
TreeNode temp=queue.poll(); //弹出当前节点
list.add(temp.val); //list集合接住当前节点的值
if(temp.left != null)
queue.add(temp.left); //队列添加左节点
if(temp.right != null)
queue.add(temp.right); //队列添加右节点
}
//新建res数组用于存储结果
int[] res=new int[list.size()] ;
for (int i = 0; i < res.length; i++) {
res[i]=list.get(i); //遍历放入数组
}
return res;
}

}

结果


从上到下打印二叉树II(递归/队列)

题目

分析

1. 与I对比:只是输出时候每次一行行输出
2. 队列queue: 每次用来存储树的节点(按照层次bfs的遍历方式)
3. 集合res: 每层结束之后把集合temp存入res
4. 集合temp: 每次存储当前节点的值

5. 难点(问题)
    5.1 怎么判断是一层: 从root之后都每次后面会添加两个节点,所以用for循环判断temp集合存储几个(for循环结束之后将temp存入res)
    5.2 输出的问题:list集合先转数组然后数组转字符串输出

代码

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
43
44
45

public class ErChaShu {
public static void main(String[] args) {
TreeNode root=new TreeNode(3); //根节点3
TreeNode r1=new TreeNode(9);
root.left=r1;
TreeNode r2=new TreeNode(20);
root.right=r2;
TreeNode r21=new TreeNode(15);
r2.left=r21;
TreeNode r22=new TreeNode(7);
r2.right=r22;
//返回list集合先转数组toArray() 然后Arrays.toString()转字符串输出
System.out.println(Arrays.toString(levelOrder(root).toArray()));
}

public static List<List<Integer>> levelOrder(TreeNode root) {
//空树
if(root==null){
return new ArrayList<>();
}
//新建队列存储每个节点(<>里面是treenode)
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root); //先存入root根节点
//存储最终结果res集合
List<List<Integer>> res=new ArrayList<>();
while(!queue.isEmpty()) { //最后队列是否为空(用完了)
List<Integer> temp = new ArrayList<>();
for (int i=queue.size();i>0;i--) {
TreeNode t = queue.poll(); //出队
temp.add(t.val); //将弹出的节点的值放入temp队列
if (t.left != null) {
queue.add(t.left); //刚才要弹出节点的左节点入队
}
if (t.right != null) {
queue.add(t.right); //刚才要弹出节点的左节点入队
}
}
res.add(temp); //每一层的temp加入到list最终集合
}

return res;
}

}

结果


从上到下打印二叉树III(递归/队列)

题目

分析

1. 与II的对比:奇数行从左到右输出,偶数行从右到左输出
2. 解法和II的对比不同只是在于最后temp存入到res时需要判断奇偶数
    //奇数行(第一行flag=1 第三行flag=3)
        if(flag%2==1){
           res.add(temp); //每行结果添加到res集合
        }
    //偶数行(第二行flag=2 第四行flag=4)
         if(flag%2==0){
           List<Integer> ou = new ArrayList<>(); //新建集合存储
           for(int i=temp.size()-1;i>=0;i--){
              ou.add(temp.get(i));  //倒序放入新集合
            }
              res.add(ou); //每行结果添加到res集合
         }

代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

public class ErChaShu {
public static void main(String[] args) {
TreeNode root=new TreeNode(3); //根节点3
TreeNode r1=new TreeNode(9);
root.left=r1;
TreeNode r2=new TreeNode(20);
root.right=r2;
TreeNode r21=new TreeNode(15);
r2.left=r21;
TreeNode r22=new TreeNode(7);
r2.right=r22;
//返回list集合先转数组toArray() 然后Arrays.toString()转字符串输出
System.out.println(Arrays.toString(levelOrder(root).toArray()));
}

public static List<List<Integer>> levelOrder(TreeNode root) {
//空树
if(root==null){
return new ArrayList<>();
}
//新建队列(存储节点)
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root); //先存入root根节点
//新建嵌套list集合存储最终结果
List<List<Integer>> res=new ArrayList<>();
//新建计数器(奇偶数)
int flag=0;
//直到队列queue为空结束
while(!queue.isEmpty()) {
List<Integer> temp = new ArrayList<>(); //存储每行的结果
//每次准备出队的时候+1(每次开始肯定是一行的内容进行循环)
flag++;
// 每次出队时候里面存的都是一行的节点
for (int i=queue.size();i>0;i--) {
TreeNode t = queue.poll(); //出队
temp.add(t.val); //存储出队结果值
if (t.left != null) {
queue.add(t.left); //队列添加左节点
}
if (t.right != null) {
queue.add(t.right); //队列添加右节点
}
}
//奇数行(第一行flag=1 第三行flag=3)
if(flag%2==1){
res.add(temp); //每行结果添加到res集合
}
//偶数行(第二行flag=2 第四行flag=4)
if(flag%2==0){
List<Integer> ou = new ArrayList<>();
for(int i=temp.size()-1;i>=0;i--){
ou.add(temp.get(i));
}
res.add(ou); //每行结果添加到res集合
}

}
return res;
}

}

结果


二叉搜索树的后序遍历序列(递归分治)

题目

分析

1. 二叉搜索树: 
    1.1 左子树中所有节点的值<根节点的值<右子树中所有节点的值
    1.2 左、右子树也分别为二叉搜索树

具体实现:

代码

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

public class ErChaShu {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for (int i = 0; i < n; i++) {
a[i]=input.nextInt();
}
System.out.println(verifyPostorder(a));
}

public static boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1); // 调用方法( 数组postorder i j )
}

public static boolean recur(int[] postorder, int i, int j) {
if(i >= j){
return true; //子树节点<=1 肯定true
}

//找左子树
int chang = i;
while(postorder[chang] < postorder[j]){ //左边肯定比根节点小(第一个大的数字就是右节点的开始位置)
chang++;
}

//找右子树
int zhong = chang; //找到第一个 > postorder[j]的值就是右子树的开始位置
while(postorder[chang] > postorder[j]) { //右边肯定都比根节点大
chang++;
}

//判断长度是否相等 而且左右子树也是二叉搜索树(递归)
return chang==j&&recur(postorder,i,zhong-1)&&recur(postorder,zhong,j-1); //j位置是左右根的根
}

}

结果


二叉树中和为某一值的路径(回溯/dfs深度优先遍历)

题目

分析

1. 定义path集合用来走路径,合适的话就加入到最终的res集合
2. 思路:
    2.1 path添加进入当前节点的值
    2.2 然后更新target目标值
    2.3 判断如果遍历到没有左右子节点而且target成功了就弹出
    2.4 左节点递归
    2.5 右节点递归
    2.6 回溯(最后一位移除)

代码

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

public class LuJing {
private ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
TreeNode root=new TreeNode(5); //根节点3
TreeNode r1=new TreeNode(4);
root.left=r1;
TreeNode r2=new TreeNode(8);
root.right=r2;
TreeNode r21=new TreeNode(11);
r2.left=r21;
TreeNode r22=new TreeNode(13);
r2.right=r22;
int sum=input.nextInt();
//返回list集合先转数组toArray() 然后Arrays.toString()转字符串输出
System.out.println(pathSum(root,sum));
}

private Stack<Integer> path = new Stack<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null){
return paths; //如果空树 返回默认空paths集合
}
path.push(root.val); //存入当前节点值
target = target -root.val; //更新剩下的target
if(target == 0 && root.left == null && root.right == null){ //如果target找到了 而且到最底层(叶子节点)
paths.add(new ArrayList<Integer>(path)); //path放入paths集合
}
FindPath(root.left, target); //左递归
FindPath(root.right, target); //右递归
path.pop(); //回溯 弹出最后一个点往上返
return paths; //返回paths集合
}

}

结果


复杂链表的复制(HashMap集合)

题目

分析

1. 首先,构造一个Map<Node,Node>,前一个是原链表的指针,后一个是新链表的指针
2. 将他们用HashMap关联起来
3. 接着遍历原链表,查找到关联的新链表节点,在对其赋值
4. 用原链表的next节点找到新链表的next节点
5. 用原链表的random找到新链表的random

代码

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

// 定义节点类
class Node {
int val;
Node next;
Node random;

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

//具体实现方法
public static Node copyRandomList(Node head) {
//创建HashMap集合
HashMap<Node,Node> map = new HashMap<>();
Node cur=head; //新建节点指向head
//复制节点值
while(cur!=null){
//存储put:<key,value1>
map.put(cur,new Node(cur.val)); //顺序遍历
cur=cur.next;
}
//复制节点指向
cur=head; //上面已经动过了重新指向head
while(cur!=null){
//得到get:<key>.value2,3
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
//返回复制的链表
return map.get(head);
}

结果


二叉搜索树与双向链表(中序遍历)

题目

分析

代码

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

class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
//判断空树
if(root == null) return null;
//中序遍历 左根右(递增)
dfs(root);
//处理头尾节点(相互指向)
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
//节点为空
if(cur == null) {
return;
}
//左子树
dfs(cur.left);
if(pre != null){
pre.right = cur; //不为空 前置节点的右节点指向当前节点
}else
head = cur; //为空 让头指针定位

cur.left = pre; //当前节点左边是前置节点
pre = cur; //往后移动

//右子树
dfs(cur.right);
}
}

结果


序列化二叉树

题目

分析

代码

1
2


结果


字符串的排列(回溯)

题目

分析

代码

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

public ArrayList<String> Permutation(String str) {
ArrayList<String> ans=new ArrayList<>();//所有排列的可能都在这
if(str!=null||str.length()>0){ //str真实存在
help(0,str.toCharArray(),ans);
Collections.sort(ans); //调用方法排序
}
return ans;
}

public static void help(int i,char[] cha,ArrayList<String> ans){
if(i==cha.length-1){ //找到最后位置
String val=String.valueOf(cha); //转字符串
if(!ans.contains(val)){
ans.add(val); //答案里面没有就添加到ans
}
}else{
for(int j=i;j<cha.length;j++){
swap(i,j,cha);//依次选一个数固定住
help(i+1,cha,ans);//让后面的进行全排列
swap(i,j,cha);//恢复原来的模样,回溯关键

}
}
}

//两者交换
public static void swap(int i,int j,char[] cha){
char temp=cha[i];
cha[i]=cha[j];
cha[j]=temp;
}

}

结果


数组中出现次数超过一半的数字(摩尔投票法/数组排序/map集合)

题目

分析

摩尔投票法分析:

核心:一定会有sum>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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

//1.摩尔投票法
public static int majorityElement(int[] nums) {
int votes=0; //投票和
int x=0; //众数
for(int i=0;i<nums.length;i++){
if(votes==0){
x=nums[i]; //如果当前位置votes=0 众数换当前值
}
//判断当前值是不是众数
if(nums[i]==x){
votes++; //是众数,投票数加一
}else{
votes--; //不是众数,投票数减一
}
}
return x; //返回众数
}


//2.排序之后取中位数
public int majorityElement(int[] nums) {
Arrays.sort(nums); //对数组排序
return nums[nums.length/2]; //其他数字只出现一次 所以超过一半的数字肯定是中间位置开始
}

//3.map集合存储次数 然后找长度超过一半的数组值
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length==0){
return 0;
}
int flag=0;
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<array.length;i++){
int c=array[i];
map.put(c,map.containsKey(c)?map.get(c)+1:1);
}
for(int i=0;i<array.length;i++){
int c=array[i];
if(map.get(c).intValue()>=array.length/2+1){
flag=c;
}
}
return flag;
}

结果


最小的k个数(排序法)

题目

分析

1. 使用排序之后将前k个值赋给新的数组即可

代码

1
2
3
4
5
6
7
8
9
10

//1.排序之后将前k个值赋给新的数组
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
int[] a=new int[k];
for(int i=0;i<k;i++){
a[i]=arr[i];
}
return a;
}

结果


数据流中的中位数

题目

分析

代码

1
2


结果


连续子数组的最大和(动态规划)

题目

分析

1. 新建dp数组存放每个nums[i]值时候的最大和
2. 新建res每次dp[i]确定值之后进行比较,不断取出dp里面最大值(或者可以dp最后排序取出最后一位即可)
3. 思路:
    3.1 res和dp[0]都必须先默认是第一位(不然报错)
    3.2从第二位开始遍历
    3.3 如果dp[i-1]<0说明对于后面的和没有作用,不如dp[i]=nums[i];
    3.4 反之有加强作用,因此dp[i]=dp[i-1]+nums[i];
    3.5 每次循环结束前进行res和dp[i]取最大

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//动态规划
public static int maxSubArray(int[] nums) {
//接答案(默认第一个值就是最大的和)
int res=nums[0];
//记录每个位置能取得最大值
int[] dp=new int[nums.length];
dp[0]=nums[0]; //初始最大值是第一个值
//依次遍历
for (int i=1;i<nums.length;i++) { //从第二个位置开始
if(dp[i-1]>0){ //如果前面的和大于0
dp[i]=dp[i-1]+nums[i]; //就加上当前值更大
}else{ //前面的和小于0 那我还不如当前值为和
dp[i]=nums[i]; //更换为当前值
}
res=Math.max(res,dp[i]); //每次把当前值的dp[i]和最大值比较更新res
}
return res; //res最后就是dp数组最大值
}

结果


1-n中整数中1出现的次数(拆除法)

题目

分析

1. 按位拆除判断(超时):for循环让每个数组判断,进入方法拆除每一位判断是否为1计数,最终求和
2. 数学归纳法:
    1. 对于百位数>=2和百位数字==0这两种情况即(a+8)/10*100
    2. 对于百位数字==1情况可以用(a+8)10*100+(b+1)

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/xiang-jie-gui-lu-yong-shi-0ms-by-sircarol/

代码

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

//1. 按位拆除判断(超时)
public static int countDigitOne(int n) {
int res=1;
if(n==0){ //0的话出现0次
res=0;
}
if(n==1){ //1的话出现1次
res=1;
}
for(int i=2;i<=n;i++){ //从2开始
res+=jige(i);
}
return res;
}
//统计1的次数
public static int jige(int i){
int sum=0;
while(i!=0){ //缩小范围到0
if(i%10==1){
sum++; //出现1的时候计数器+1
}
i=i/10; //不断缩小
}
return sum;
}


//2. 数学归纳法
public int countDigitOne(int n) {
int res = 0;
for (long m = 1; m <= n; m *= 10) {
long a = n / m;
long b = n % m;
res += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
}
return res;
}

结果


数字序列中某一位的数字(数学归纳)

题目

分析

1. 第一个while用来判断多少个
2. 用char数组存放结果,然后不断地取出到哪一位

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static int findNthDigit(int n) {
int res=0;
if(n<10){
return n; //前10位是按照顺序0123456789
}
int i=1;
while(n>i*(Math.pow(10,i-1)*9)){ // 9(10个) 99(90个) 999(900个)
n-=i*Math.pow(10,i-1)*9;
i++;
}
char[] result=String.valueOf((int)Math.pow(10,i-1)+(n-1)/i).toCharArray();//我们用字符串来接收值,方便找位数 result结果为我们要的那个数的
int value=result[(n-1)%i]-'0'; //(n-1)%位数 得出我们要的第x位的数
return value;
}

结果


把数字翻译成字符串(动态规划)

题目

分析

代码

1
2


结果


礼物的最大价值(回溯)

题目

分析

1.思路:其实就是典型的回溯算法解决。    

代码

1
2


结果


最长不含重复字符的子字符串(动态规划)

题目

分析

1. 动态规划法:循环遍历确定start和end两个位置,就可以确定最终的长度由ans接住。
2. 具体实现:
    2.1 新建map集合存放字符和数字出现几率
    2.2 如果map里面有当前位置的字符就让start取当前位置字符出现次数+1的最大值,然后更新ans
    2.3 循环结束前更新当前位置字符和出现位置end

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
Map<Character, Integer> map = new HashMap<>();//key出现的字符,value对应的最新的位置
// try to extend the range [i, j]
int start=0;
for (int end = 0; end < n; end++) {
if (map.containsKey(s.charAt(end))) {
start = Math.max(map.get(s.charAt(end)) + 1, start);//由于重复的坐标不知道在start的前方还是后方,所以要取个最大值
}
ans = Math.max(ans, end - start + 1); //更新最大长度
map.put(s.charAt(end), end); //存放的字符对应位置更新
}
return ans;
}
}

结果


丑数(三指针)

题目

分析

1. 分析丑数:从第一位1之后都是2 4 6 8 10加上3 6 9 12以及5 10 15 20等等
2. 解决方案:通过dp数组存放结果,然后不断求2和3和5之间倍数和交叉和的结果。
3. 举例:
    求第二位的丑数: p2 p3 p5都为0   dp[1]=min(2*dp[0] 3**dp[0] 5*dp[0])=2 p2=1(递增)
    求第三位的丑数: p2=1 p3=0 p5=0  dp[2]=min(2*dp[1] 3**dp[0] 5*dp[0])=3 p3=1(递增)
    求第四位的丑数: p2=1 p3=1 p5=0  dp[3]=min(2*dp[1] 3**dp[1] 5*dp[0])=5 p5=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

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
System.out.println(nthUglyNumber(n)); //调用方法
}

public static int nthUglyNumber(int n) {
int p2=0; //只乘2
int p3=0; //只乘3
int p5=0; //只乘5
int[] dp=new int[n]; //存放所有的丑数
dp[0]=1; //第一个丑数是1
for(int i=1;i<n;i++){
dp[i]=Math.min(dp[p2]*2,Math.min(dp[p3]*3,dp[p5]*5)); //从第二位开始求当前位置丑数
//看是哪个指针走了就跳后面
if(dp[i]==dp[p2]*2){
p2++;
}
if(dp[i]==dp[p3]*3){
p3++;
}
if(dp[i]==dp[p5]*5){
p5++;
}
}
return dp[n-1]; //最后返回n-1结果
}

}

结果


第一个只出现一次的字符(计数遍历/hashmap存储出现次数)

题目

分析

//第一种计数遍历
    1. 第一次遍历将所有字符的出现次数记录
    2. 第二次遍历找到只出现1次的字符然后就弹出即可(找第一个只出现一次的)

//第二种hashmap存储
    1. 遍历存储每个字符出现次数
    2. 第二次遍历找到次数res.get(str.charAt(i)).intvalue()是1的就返回然后break停止遍历

代码

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
43
44
45
46
47
48
49
50
51
52
53

public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.next();
System.out.println(firstUniqChar(s));
}

//第一种:计数遍历
public static char firstUniqChar(String s) {
//定义计数器 记录26个字母出现次数
int[] count=new int[26];
//存取最终结果
char c=' '; //默认找不到返回空字符

//遍历数组 计数
for(int i=0;i<s.length();i++){
count[s.charAt(i)-97]++; //字符数组存的ascii码
}

//遍历数组找到出现了一次的字符
for(int i=0;i<s.length();i++){
if(count[s.charAt(i)-97]==1){ //出现了一次
c=s.charAt(i); //结果赋给c
break; //弹出(第一次出现)
}
}
return c;
}


//第二种:hashmap集合存储
public int FirstNotRepeatingChar(String str) {
if(str.length()==0){
return -1; //如果字符串为0 返回-1找不到
}
int flag=-1; //接住最后结果
Map<Character,Integer> res=new HashMap<>(); //记录每个字符出现次数
for(int i=0;i<str.length();i++){
char c=str.charAt(i); //获取每个位置的字符
res.put(c,res.containsKey(c)?res.get(c)+1:1); //map集合存储次数
}
for(int i=0;i<str.length();i++){
char c=str.charAt(i);
if(res.get(c).intValue()==1){ //第一个出现次数是1的字符就输出 break结束
flag=i;
break ;
}
}
return flag; //返回flag结果
}

}

结果


数组中的逆序列

题目

分析

代码

1
2


结果


两个链表的第一个公共节点(双指针)

题目

分析

参考图即可:

https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/shuang-zhi-zhen-fa-lang-man-xiang-yu-by-ml-zimingm/

1. 其实就是两个节点不断往后推,然后两个到最后的时候交换然后遍历,直到两个节点到同一个节点上输出即可(pA==pB)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null; //两个不存在
}
ListNode pA = headA; //pA指向headA节点
ListNode pB = headB; //pB指向headB节点
//循环判断
while(pA != pB){
if (pA == null) {
pA=headB;
}else{
pA=pA.next; //没空就一直往后推
}
if (pB == null) {
pB=headA;
}else{
pB=pB.next; //没空就一直往后推
}
}
return pA;
}

结果


二叉搜索树的第k大节点(后序遍历递减)

题目

分析

1. 二叉搜索树中序遍历递增 所以选择递减的后序遍历
2. 然后递归一次计数器加一次当等于k时候就是到了,然后返回当前节点的值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int count=0,num=0; //全局变量

public int kthLargest(TreeNode root, int k) {
helper(root,k); //调用方法
return num;
}

public void helper(TreeNode root,int k){
if(root==null){ //如果为空返回空
return;
}
helper(root.right,k); //右
count++; //计数器增加
if(count==k){ //如果计数器的和k位置一样了赋值节点值给num
num=root.val; //根
return;
}
helper(root.left,k); //左
}

结果


二叉搜索树的深度(递归DFS)

题目

分析

1. 树深度=Math.max(左子树深度,右子树深)+1
2. 所以我们使用递归不断求每个子树的深度,然后取最大值+1

代码

1
2
3
4
5
6
7
8

public int maxDepth(TreeNode root) {
if(root==null){
return 0; //左右节点为空 所以长度是0
}
//返回当前节点的深度就是 max(左深度,右深度)+1
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}

结果


平衡二叉树(求深度题目基础上增加判断)

题目

分析

1. 树深度=Math.max(左子树深度,右子树深)+1
2. 所以我们使用递归不断求每个子树的深度,然后取最大值+1
3. 在第二步基础上如果不符合<=1的话就方法赋-1 然后主方法输出false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public boolean isBalanced(TreeNode root) {
return recur(root) != -1; //判断是不是-1
}

//求二叉搜索树的深度
private int recur(TreeNode root) {
if (root == null) { // 左/右子树为空
return 0;
}
int left = recur(root.left); //获取左子树长度
if(left == -1) return -1;
int right = recur(root.right); //获取右子树长度
if(right == -1) return -1;
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1; //如果异常就-1
}

结果


数组中数字出现的次数I(哈希表)

题目

分析

1. 使用hashset不能存放重复的机制
2. 如果第二次出现了就让set移除出去,然后
3. 剩下的就是只出现一次

代码

1
2
3
4
5
6
7
8
9
10
11

public static Object[] singleNumberser(int[] nums) {
int[] a=new int[nums.length];
Set<Integer> set=new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if(!set.add(nums[i])){
set.remove(nums[i]); //出现第二次的就挪出去
}
}
return set.toArray(); //转数组
}

结果


数组中数字出现的次数II(哈希表)

题目

分析

1. 使用hashmap存放每个数字出现次数,然后遍历找value==1的key即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public static int singleNumber(int[] nums) {
int res=0; //最终结果
//记录每个数字出现次数
HashMap<Integer,Integer> map=new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])){
map.put(nums[i], map.get(nums[i]) + 1); //递增value
}else{
map.put(nums[i],1); //没出现过value为1
}
}
for(int i=0;i<nums.length;i++){
if(map.get(nums[i]).intValue()==1){ //找value是1的key
res=nums[i]; //res接住
}
}
return res; //接住结果
}

结果


和为s的两个数字(双指针)

题目

分析

代码

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 class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int[] a = new int[]{10,26,30,31,47,60};
int target=input.nextInt();
System.out.println(Arrays.toString(twoSum(a,target)));
}

public static int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1; //定义两个指针
while(i < j) {
int s = nums[i] + nums[j]; //求和
if(s < target){
i++; //太小了往后挪
}
else if(s > target){
j--; //太大了往前挪
}
else return new int[]{nums[i], nums[j]}; //找到了就返回这两个值
}
return new int[0]; //默认返回空
}

}

结果


和为s的连续正数序列(滑动窗口)

题目

分析

不断地使用滑动窗口取结果集

代码

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

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int target=input.nextInt();
System.out.println(findContinuousSequence(target));
}

public static int[][] findContinuousSequence(int target) {
int i = 1; // 滑动窗口的左边界
int j = 1; // 滑动窗口的右边界
int sum = 0; // 滑动窗口中数字的和
//res集合接收结果
List<int[]> res = new ArrayList<>();
while(i<=target/2){ //只能到一半的位置
if(sum<target){
sum+=j; //太小了 往右移动找新的
j++;
}else if(sum>target){
sum-=i; //太大了 往右移动把最左边的删除
i++;
}else{ //找到了结果集
int[] arr=new int[j-i]; //长度是j-i
for(int k=i;k<j;k++){
arr[k-i]=k; //要把i和j开始遍历放入数组
}
//将每一个结果数组放入res集合
res.add(arr);
//左边界限向右移动(找到了i就要往后挪动)
sum-=i; //sum要减去i
i++;
}
}
return res.toArray(new int[res.size()][]); //集合转数组
}

}

结果


翻转单词顺序(空格分开)

题目

分析

1. 将s去掉两边空格然后以空格隔开得到单词集合strs数组[s.trim().split(" ")]
2. 新建res对象接住结果
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
27

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s=input.nextLine(); //nextLine()输入格式
System.out.println(reverseWords(s));
}

public static String reverseWords(String s) {
if(s.length()==0){
return ""; //输入空字符串
}
String[] strs = s.trim().split(" "); // 删除首尾空格,分割字符串
if(strs.length==1){ //输入两个空格 数组长度就是1
return str;
}
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
if(strs[i].equals("")){
continue; // 遇到空单词则跳过
}
res.append(strs[i]+" "); // 将单词拼接至 StringBuilder
}
return res.toString().trim(); // 转化为字符串,删除尾部空格,并返回
}

}

结果


左旋转字符串(遍历)

题目

分析

1. 新建stringbuilder对象然后将n之后的添加然后添加n之前的
2. 可以考虑substring()方法添加

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s=input.next();
int n=input.nextInt();
System.out.println(reverseLeftWords(s,n));
}

public static String reverseLeftWords(String s, int n) {
StringBuilder res=new StringBuilder();
//将n后面的遍历加入
for(int i=n;i<s.length();i++){
res.append(s.charAt(i));
}
//将n之前的遍历加入
for(int i=0;i<n;i++){
res.append(s.charAt(i));
}
return res.toString(); //转字符串
}

}

结果


滑动窗口的最大值(双指针移动)

题目

分析

1. 其实就是不断的挪动窗口取每次的最大值
2. 实现步骤:
    2.1 判断特殊情况:窗口为0就返回0  窗口为1就返回原数组(每一位就是最大值)
    2.2 判断一般情况:
        2.2.1 定义数组a接住结果
        2.2.2 定义每次滑动窗口的left和right指针
        2.2.3 每次都调用maxer方法去找到最大值(maxer方法要有左右指针位置和nums数组)
        2.2.4 每次结束之后将left和right往后移动一位
        2.2.5 最后输出结果        

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public ArrayList<Integer> maxInWindows(int [] num, int size)
{
int len = num.length - size + 1; //假如数组长度6 要找框为3 只需要4次
ArrayList<Integer> res = new ArrayList<>();
if(size == 0){
return res; //框为0就返回res集合
}
for(int i = 0; i < len; i++)
{
int max = num[i];
for(int j=i; j<i+size;j++)
{
if(num[j]>max)
max = num[j];
}
res.add(max);
}
return res;
}

结果


队列的最大值(链表)

题目

分析

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-ii-javashi-xian-yuan-li-he-mian-shi/

代码

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

public class MaxQueue {

Queue<Integer> queue;
LinkedList<Integer> max;
public MaxQueue() {
queue = new LinkedList<>();
max = new LinkedList<>();//LinkedList是双端链表
}

public int max_value() {
return max.size()==0?-1:max.getFirst();
}

public void push_back(int value) {
queue.add(value);
while(max.size()!=0&&max.getLast()<value){//注意:这里第二个判断条件不能带等号,即max中对于当前queue中的具有相同值的元素会全部存储,而不是存储最近的那个。
max.removeLast();
}
max.add(value);
}

public int pop_front() {
if(max.size()!=0&&queue.peek().equals(max.getFirst()))//Integer类型的值的比较不能直接使用==
max.removeFirst();
return queue.size()==0?-1:queue.poll();
}

}

结果


n个骰子的点数(动态规划)

题目

分析

代码

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

public static double[] twoSum(int n) {
if(n==0) {
return new double[0]; //n个筛子
}
double[] dp=new double[6*n+1];
double[] ans=new double[5*n+1];
double all=Math.pow(6,n);
for(int i=1;i<=6;i++){
dp[i]=1;
ans[i-1]=1.0/6;
}
for(int i=2;i<=n;i++){
for(int j=6*n;j>=1;j--){
int temp=0;
for(int k=1;k<=6;k++){
temp+=(j>=k)?dp[j-k]:0;
}
dp[j]=temp;
if(i==n && j>=n){
ans[j-i]=dp[j]/all;
}
}
}
return ans;
}

结果


扑克牌中的顺子(Set集合)

题目

分析

1. 除大小王外,所有牌没有重复
2. 最大和最小的牌:max-min<5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) {
return false; // 若有重复,提前返回 false
}
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}

结果


圆圈中最后剩下的数字(约瑟夫杀人环list集合)

题目

分析

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

代码

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

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
System.out.println(lastRemaining(n,m));
}

public static int lastRemaining(int n, int m) {
//新建list集合
ArrayList<Integer> list = new ArrayList<>();
//将所有元素都加入list集合
for (int i=0;i<n;i++){
list.add(i);
}
//定义下标--确定每次删除的位置
int i=0;
//循环删除
while(n>1){
i=(i+m-1)%n;
list.remove(i); //list删除
n--; //总数减少1个
}
return list.get(0); //剩下的唯一一个数字
}

}

结果


股票的最大利润(动态规划)

题目

分析

1. 新建dp数组存放每个位置的利润
2. 不断的找min最小值,然后取当前位置的利润

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int[] a=new int[]{7,1,5,3,6,4};
System.out.println(maxProfit(a));
}

public static int maxProfit(int[] prices) {
if(prices.length==0){
return 0; //数组长为0
}
int min=prices[0]; //购买的日子
int[] dp=new int[prices.length]; //存每个位置的利润
for (int i=1;i<prices.length;i++) {
min=Math.min(min,prices[i-1]); //找最小值
dp[i]=Math.max(dp[i-1],prices[i]-min); //每个位置的利润
}
return dp[prices.length-1];
}

}

结果


求1+2+..+n的和(归纳)

题目

分析

1. 递归
2. 迭代
3. 数学归纳法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt();
System.out.println(sumNums(n));
}

public static int sumNums(int n) {
int res=0;
res=((n+1)*n)/2;
return res;
}

}

结果


不用加减乘除做加法(位运算)

题目

分析

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/jin-zhi-tao-wa-ru-he-yong-wei-yun-suan-wan-cheng-j/

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
System.out.println(add(n,m));
}

public static int add(int a, int b) {
while(b!=0){
int tempSum=a^b; //求不考虑进位的相加和
int carrySum=(a&b)<<1; //进位的和
//不断循环迭代 直到没有进位(b==0)
a=tempSum;
b=carrySum;
}
return a;
}

}

结果


构建乘积数组(不用除法就分区)

题目

分析

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

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int[] a=new int[]{1,2,3,4,5};
System.out.println(Arrays.toString(constructArr(a)));
}

public static int[] constructArr(int[] a) {
if(a.length==0){
return new int[0]; //返回0
}
int[] b=new int[a.length];
b[0]=1;
int temp=1;
//计算左下角
for(int i=1;i<a.length;i++){ //从上到下
b[i]=b[i-1]*a[i-1];
}
//计算右上角
for(int i=a.length-2;i>=0;i--){ //从下往上
temp=temp*a[i+1];
b[i]=b[i]*temp;
}

return b;
}

}

结果


字符串转整数(考虑成分)

题目

分析

1. 组成四个部分:  空格+正负号+数字+非数字部分
2. 空格: 直接跳过(i下标++)
3. 正负号:使用布尔变量标识(i下标++)
4. 数字部分:进行10进制的位数增加(注意有越界情况) 
5. 非数字部分:跳过不管
6. 最后记得是负数要添加负号(*-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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s=input.next();
System.out.println(strToInt(s));
}

public static int strToInt(String str) {
if(str==null) {
return 0; //字符串为空 返回0
}
int n=str.length(); //获取字符串长度
int i=0;
int res=0; //接最后结果
boolean is_negative=false; //判断正负数
// 第一步,跳过前面若干个空格
while(i<n&&str.charAt(i)==' '){
++i; //i往后调
}
//如果字符串全是空格直接返回
if(i==n) {
return 0;
}
//第二步,判断正负号
if(str.charAt(i)=='-') {
is_negative = true;
}
//如果是正负号,还需要将指针i,跳过一位
if(str.charAt(i)=='-' || str.charAt(i)=='+') {
++i;
}
//第三步,循环判断字符是否在 0~9之间
while(i<n && Character.isDigit(str.charAt(i))) {
//'0'的ASCII码是48,'1'的是49,这么一减就从就可以得到真正的整数值
int tmp = str.charAt(i)-48;
//判断是否大于 最大32位整数
if(!is_negative &&(res>214748364 ||(res==214748364 && tmp>=7))) {
return 2147483647;
}
//判断是否小于 最小32位整数
if(is_negative &&(-res<-214748364 || (-res==-214748364 && tmp>=8))) {
return -2147483648;
}
//将字符串转为整数(10进制)
res = res*10 + tmp;
++i;
}
//如果有负号标记则返回负数
if(is_negative) {
return -res;
}
return res;
}

}

结果


二叉搜索树的最近公共祖先(迭代/递归)

题目

分析

1. 由于是二叉搜索树所以有以下三种情况:
    1.1 root.val < p.val 则p在root右子树中
    1.2 root.val > p.val 则p在root左子树中
    1.3 root.val = p.val 则p和root指向同一节点        
2. 递归法思路:
    当p和q都在root右子树中,递归root.right并返回
    当p和q都在root左子树中,递归root.left并返回

代码

1
2
3
4
5
6
7
8
9
10
11

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//p q都在右子树 右子树里面找
if(root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
//p q都在左子树 左子树里面找
if(root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
//公共节点既不在左子树也不再右子树上 只能是顶端的公共节点
return root;
}

结果


二叉树的最近公共祖先(后序遍历DFS)

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) {
return null; // 1. 左右子树都不包含p和q
}
if(left == null) {
return right; // 3.不在左子树 直接返回right
}
if(right == null) {
return left; // 4.不在右子树 直接返回left
}
return root; // 2.不同时为空 p和q分在两侧
}

结果


Hexo博客重装系统重新部署

前提(博客文件夹还在!!!)

我写这篇博客想记录重装系统之后如何重新部署hexo博客!!


1.完整步骤

1.1安装git和node.js文件

两个软件路径百度就可以找到(如果你有幸看到这篇文章,可以联系我发给你)

1.2配置git信息,生成新的ssh密钥

//每次输入一行就执行一次(按回车)
    git config --global user.name "你自己的github用户名"
    git config --global user.email "Xxxxx@qq.com"

//你需要把邮件地址和用户名换成你自己的,然后一路回车,使用默认值即可。    
    ssh-keygen -t rsa -C "Xxxx@qq.com"

1.3更新ssh密钥

打开id_rsa.pub文件并且复制里面的内容

生成的ssh公钥(刚复制的内容)复制到github的settings里面的ssh选项中(参考github讲ssh密钥添加到github账户)

http://https://docs.github.com/cn/github/authenticating-to-github/adding-a-new-ssh-key-to-your-github-account

1.4安装hexo

npm install hexo-cli -g

1.5打开原来的hexo博客所在文件夹

只需保留_config.yml,theme/,source/,scaffolds/,package.json,.gitignore 这些项目,删除其他的文件。

git bush运行命令npm install

git bush运行命令npm install hexo-deployer-git –save

最后执行hexo g和hexo d试试就行


2.重新部署参考文章

参考别人的思路!!!

http://http://fenghub.top/2017/02/25/hexo-rebuilding/


3.hexo博客更改域名

3.1 购买域名

3.2 域名解析

前提:

​ 先找到自己能够跑通的github网站: larkkkkkkk.github.io

​ 然后电脑cmd打开输入ipconfig进行ping一下: 得到ip地址xxx.xxx.xxx.xxx

image-20231009160826890

3.2.1 一键解析

image-20231009160418731

3.2.2 自己解析

创建一条A记录,创建一条CNAME记录。

image-20231009160942760

3.3 Hexo目录下创建CNAME文件

创建一个文件里面存放你的域名: www.xxx.xxx
image-20231009161109713

3.4 访问

这样的话就不用xxx.github.io,直接访问你的新域名就行

image-20231009161211550

,