mybatis03-复杂查询

mybatis-03学习复杂查询

讲到复杂查询,在mybatis中就要用到resultMap结果映射,之前用到单表简单查询,用一个resultType就可以满足了,但一旦是一些连接查询等复杂查询时候,resultMap作用就体现出来了。下面重点讲下这个MyBatis中最强大的元素。

resultMap介绍

显示resultMap的元素概念,下图是官网中的讲解图,重点讲下关联(association)和集合(collection)

image-20200518151113180

关联(association)

image-20200518212633184

关联(association)元素处理“有一个”类型的关系,同时MyBatis 有两种不同的方式加载关联:

  1. 嵌套的查询,和sql中的子查询类似
  2. 根据结果来映射

集合(collection)

实例使用resultMap的关联查询

正常的MySQL查询-连接查询,但是在mybatis怎么实现呢,接下来来讲下两种方式去实现。

image-20200518212358659

方式一 嵌套查询

StudentMapper.xml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<mapper namespace="com.yhy.dao.StudentMapper">

<select id="getStudent" resultMap="StudentTeacher">
select * from student;
</select>

<resultMap id="StudentTeacher" type="Student">
<result property="id" column="id" />
<result property="name" column="name" />

<!-- 有时需要处理一些复杂的数据查询,多表查询等,就需要用到assoction-->
<association property="teacher" column="tid" javaType="Teacher" select="getTeacher"/>
</resultMap>

<select id="getTeacher" resultType="Teacher">
select * from teacher where id = #{id};
</select>


</mapper>

结果,这个结果就类似sql中的子查询,一个结果中嵌套另一个结果

image-20200518151811158

方式二 按照结果处理

StudentMapper.xml修改成以下的形式,其实这样的形式更加容易理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
!--采用连接查询的方法-->
<select id="getStudent2" resultMap="StudentTeacher2">
select s.id sid,s.name sname, t.name tname
from student s , teacher t
where s.tid = t.id;
</select>

<resultMap id="StudentTeacher2" type="Student">
<result property="id" column="sid"/>
<result property="name" column="sname"/>
<association property="teacher" javaType="Teacher">
<result property="name" column="tname"/>
</association>
</resultMap>

结果也一样

image-20200518212227344

JavaType–用来指定实体类中的属性

ofType–用来指定映射到List或者集合中的pojo类型,泛型中的约束类型

最后

无论使用什么的方式,保持代码的可读性和效率是很关键的。

ssm小结

ssm框架学习

记录学习

SpringMVC框架

这是表现层-相当于之前的servlet层和一些视图

Spring

重点:控制反转(IOC)和AOP(面向切面编程)

MyBatis:持久层框架

数据访问层-相当于之前web项目中dao层,数据库的交互,包括增删改查;

持久化就是将数据在持久状态和瞬时状态转化的过程。内存是断电即失。所以需要数据的持久化。

JDBC技术:Connection、PrepareStatement、ResultSet.

为什么要使用框架代替jdbc呢?

​ 因为之前的jdbc的操作总是是重复单一的,在开发的时候要执行sql语句直接操作数据库,要经过加载驱动等操作,为了高效的开发,避免繁琐的操作,框架就诞生了。框架对jdbc进行封装,mybatis只需关注sql语句直接操作数据库,封装了操作的很多细节,这样可以将更多时间精力放在sql语句的编写上。

特点:灵活容易上手,用的多,封装jdbc

第一个程序

pojo的user类

映射数据库的user表

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
package com.yhy.pojo;

/**
* @Author: yhy
* @Date: 2020/5/12
* @Time: 10:58
* 用户表的pojo层
*/
public class User {
private int id;
private String name;
private String pwd;

public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}


public String getPwd() {
return pwd;
}

public void setPwd(String pwd) {
this.pwd = pwd;
}

}

pom.xml,

整个项目的maven管理文件。

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
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>com.yhy.learn</groupId>
<artifactId>mybatisDemo</artifactId>
<packaging>pom</packaging>
<version>1.0-SNAPSHOT</version>
<modules>
<module>mybatis-01</module>
</modules>

<dependencies>
<dependency>
<groupId>org.mybatis</groupId>
<artifactId>mybatis</artifactId>
<version>3.5.4</version>
</dependency>

<!-- https://mvnrepository.com/artifact/mysql/mysql-connector-java -->
<dependency>
<groupId>mysql</groupId>
<artifactId>mysql-connector-java</artifactId>
<version>8.0.15</version>
</dependency>

<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.12</version>
</dependency>

</dependencies>

<build>
<resources>
<resource>
<directory>src/main/resources</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>

<resource>
<directory>src/main/java</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>
</resources>
</build>



</project>

工具类

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
package com.yhy.utils;

import org.apache.ibatis.io.Resources;
import org.apache.ibatis.session.Configuration;
import org.apache.ibatis.session.SqlSession;
import org.apache.ibatis.session.SqlSessionFactory;
import org.apache.ibatis.session.SqlSessionFactoryBuilder;

import java.io.IOException;
import java.io.InputStream;

/**
* @Author: yhy
* @Date: 2020/5/12
* @Time: 11:45
* 工具类
* 获取sqlsession工厂
*/
public class MybatisUtils {
private static SqlSessionFactory sqlSessionFactory;
static {
try {
// 利用mybatis在一开始就获得了sqlsessionfactory
String resource = "mybatis-config.xml";
InputStream inputStream = Resources.getResourceAsStream(resource);
sqlSessionFactory = new SqlSessionFactoryBuilder().build(inputStream);
} catch (IOException e) {
e.printStackTrace();
}

}
// 有了工厂就可以获得实例来使用,sqlsession就可以面向数据库操作jdbc
public static SqlSession getSqlSession(){
return sqlSessionFactory.openSession();
}



}

dao的接口实现xml

用这个文件代替了之前dao层中的接口实现类,之前的话需要编写jdbc的全部,查询编写sql,获取结果集,遍历结果集,关闭连接。现在的话就是简化了步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE mapper
PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN"
"http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<!--namespace=绑定一个对应的Dao/Mapper接口 原本是写接口,但是现在不用怎么做-->
<mapper namespace="com.yhy.dao.UserDao">

<!--select查询语句-->
<select id="getUserList" resultType="com.yhy.pojo.User">
select * from mybatis.user
</select>

</mapper>

测试

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
package com.yhy.dao;

import com.yhy.pojo.User;
import com.yhy.utils.MybatisUtils;
import org.apache.ibatis.session.SqlSession;
import org.junit.Test;

import java.util.List;

/**
* @Author: yhy
* @Date: 2020/5/12
* @Time: 12:15
*/
public class UserDaoTest {
//借调工具类来使用测试
@Test
public void test(){
SqlSession sqlSession = MybatisUtils.getSqlSession();

UserDao mapper = sqlSession.getMapper(UserDao.class);
List<User> userList = mapper.getUserList();

for (User u: userList){
System.out.println(u);

}

sqlSession.close();


}


}

mybatis-config.xml

这个是关键的配置文件,决定了连接的对象以及设定了作用域

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
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE configuration
PUBLIC "-//mybatis.org//DTD Config 3.0//EN"
"http://mybatis.org/dtd/mybatis-3-config.dtd">
<configuration>
<typeAliases>
<package name="com.yhy.pojo"/>
</typeAliases>
<environments default="development">
<environment id="development">
//事务管理
<transactionManager type="JDBC"/>
<dataSource type="POOLED">
<property name="driver" value="com.mysql.cj.jdbc.Driver"/>
<property name="url" value="jdbc:mysql://localhost:3306/mybatis?characterEncoding=UTF-8"/>
<property name="username" value="root"/>
<property name="password" value="root"/>
</dataSource>
</environment>
</environments>
//作用域,删掉就是全局
//这里的配置可以是直接放在resource文件下,就直接写上xml名称就行,放在dao层的话就需要写全路径
<mappers>
<mapper resource="com/yhy/dao/UserMapper.xml"/>
</mappers>
</configuration>

演示两种mappers作用效果

  • 1.将UserMapper.xml放在dao层下,跟着userdao

配置就和我上面写的一样。最后效果如下,但是前提是你得在你项目的pom.xml设置好有效的作用域,要不然就疯狂报错,说找不到这个UserMapper.xml文件。

image-20200512143352609

pom.xml需要配置如下,这里是配置能够得读取到src下的有效配置文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<build>
<resources>
<resource>
<directory>src/main/resources</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>

<resource>
<directory>src/main/java</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>
</resources>
</build>
  • 2.是直接将UserMapper.xml放在src下的resource文件下,和总的mybatis-config.xml配置文件放置在一起。这样在mybatis-config.xml里面就直接如下这样写文件名就行了。
1
<mapper resource="UserMapper.xml"/>

image-20200512143952637

最后效果和第一种方法是一样的,都能够读取到数据。

  • 个人觉得这两种方法来说,第一种可以对项目的整体设计管理更加方便一点,就像接口和实现类都是靠近的,方便进一步的审查和优化,第二种在做小的demo的时候是很方便的,但是一旦多个配置文件时候就可以有点难找。

记录错误

  1. maven创建项目一开始经常会有的错误,就是设定的jdk版本问题,一开始我都是手动去修改project的setting,比较麻烦。默认的版本一般是jdk1.4或者是jdk1.5,但大家往往不是这个版本,所以会报错不支持发行版本5什么的。

解决:现在记录下,永久得起配置好。到自己maven下载文件夹下找到配置文件,并在里面修改settings.xml

image-20200512151703715

image-20200512151630090

修改:如下,我的是jdk11。所以可以根据自己的版本来修改。

image-20200512151902737

初步学习

解决idea错误

记录解决Intellij IDEA Tomcat启动项目加载页面的时候报错:java.lang.ClassNotFoundException-mysql数据库驱动问题

一个javaweb项目,在编写登录页面跳转的时候,因为借助了mysql中的数据,所以调用了数据库驱动。

下面的是一开始的错误,登录无法跳转界面,通过debug,里面传到user是null对象,无法走到正确页面。

image-20200504164413808

image-20200504163919368

一开始我以为测试正确就可以使用mysql数据库的驱动,后面才知道是不一样的。

image-20200504164336536

解决

首先是File-project structure-Artifacts,这里是为了解决这是由于pom.xml中下载的jar包未被部署,也就是我的问题所在。

image-20200504164706845

一开始我的左边是没有lib文件夹的,右边的依赖也没有加过来,所以要将右边的全部移动过来就可以解决了。

image-20200504164943384

最后成功登录

image-20200504165012470

最后

希望自己能够从错误中不断学习,也很感谢那个大哥花时间帮我,感谢!!

参考1

参考2

参考3

mybatis02-分页

mybatis学习系列第二篇

分页

在网页中常常用到,在查询数据库内容并想将其输出的时候,因为有时有多组数据,一页展示过于突兀,所以会用到分页操作。

sqllimit来分页。

首先是UserMapper.xml

1
2
3
4
5
6
7
<!-- 实现分页的接口 -->

<select id="getUserByLimit" parameterType="map" resultType="User">

select * from mybatis.user limit #{startIndex},#{pageSize};

</select>

然后是UserMapper.java

1
2
// 实现分页查询操作
List<User> getUserByLimit(Map<String,Integer> map);

再到测试类中的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void getUserByLimit() {
SqlSession sqlSession = MybatisUtils.getSqlSession();
UserDao mapper = sqlSession.getMapper(UserDao.class);

Map<String,Integer> map = new HashMap<>();
//通过map来传参来实现数据的交互绑定
map.put("startIndex", 1);
map.put("pageSize", 2);

List<User> userlist = mapper.getUserByLimit(map);
for (User user : userlist) {
System.out.println(user);

}

sqlSession.close();

}

还可以使用RowBounds来实现分页

UserMapper.java

1
2
// 实现分页的方法二
List<User> getUserByLimit2();

UserMapper.xml

1
2
3
4
<!-- 实现分页的方法二 -->
<select id="getUserByLimit2" resultType="User">
select * from mybatis.user ;
</select>

RowBounds构造方法,和limit相似。

image-20200517090058269

test代码

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

public void getUserByLimit2() {
SqlSession sqlSession = MybatisUtils.getSqlSession();


RowBounds rowBounds = new RowBounds(1,2);
// 使用java代码来实现分页操作
List<User> selectList = sqlSession.selectList("com.yhy.dao.UserDao.getUserByLimit2", null, rowBounds);

for (User user : selectList) {
System.out.println(user);
}

sqlSession.close();

}

输出结果

image-20200517090333835

pageHelper分页插件

了解

注解开发

本质是使用反射,还有动态代理模式

在工具类MybatisUtils中,打开自动提交事务,这样在后续的编写代码中就不要在使用commit

image-20200517150310456

1
2
3
4
5
//    有了工厂就可以获得实例来使用,sqlsession就可以面向数据库操作jdbc
// 打开自动提交事务
public static SqlSession getSqlSession(){
return sqlSessionFactory.openSession(true);
}

注解开发流程-实例

整体文件结构

image-20200517195217954

使用注解开发的时候,接口里面定义的方法就是使用注解的地方,实例如下

1
2
3
4
//使用注解的方法,之前是需要写xml文件进行配置,这里就直接使用注解的方法
//这个方法是查询所有用户信息
@Select("select * from user")
List<User> getUsers();

在主配置文件中,也是关键所在,绑定的有所不同。将文件资源标签改为class,并将所在的类位置标出。

image-20200517200001711

测试类-使用的步骤和之前的没有使用注解的方法一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
@Test
public void test() {
SqlSession sqlSession = MybatisUtils.getSqlSession();
UserMapper mapper = sqlSession.getMapper(UserMapper.class);

List<User> users = mapper.getUsers();
for (User user : users) {
System.out.println(user);
}

sqlSession.close();

}

总的来说,注解是分散的数据配置,而xml是集中的数据配置。

使用注解可以很多程度来简化工作,省去了很多配置文件的编写,但有时注解过于分散不利于管理和维护,在一些通用配置上,像数据库连接等,还是比较建议xml文件进行配置,因为XML方式比注解的可扩展性和复杂性维护上好的多。所以注解有利有弊,看什么场景去使用,用对了就是事半功倍的效果!

了解Lombok

Lombok是一个java开发插件,目的是简化代码,方便开发,通过注解省去了一些pojo中的getset方法和构造方法,还有一些其他的tostringequals等。有些介绍可以参考官网中的文档,当然对于这款插件,欢呼声和骂声一直都充斥在各个平台,各种分析文章网上也有很多,我就不再去记录太多了。但任何事情都有其两面性,理性看待,喜欢觉得有用大家就用,不喜欢就当了解一些也不为过。下面是记录使用的一些图片代码。

1、插件下载–setting里面的插件

image-20200518102201415

2、maven导包,在官网找到信息进行导包,选择自己所需要的版本进行使用

image-20200518103524190

我选择了最新的版本,有错再去解决

1
2
3
4
5
6
7
8
9
10
<dependencies>
<!-- https://mvnrepository.com/artifact/org.projectlombok/lombok -->
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<version>1.18.12</version>
<scope>provided</scope>
</dependency>

</dependencies>

3、使用实例

在插件管理查看信息里面就可以看到Lombok的一些介绍吗,下面是一些注解的介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Getter and @Setter //生成get和set方法
@FieldNameConstants
@ToString //tostring方法
@EqualsAndHashCode //equals和hashcode方法的生成
@AllArgsConstructor, @RequiredArgsConstructor and @NoArgsConstructor //全参构造和无参构造和一个自定义构造
@Log, @Log4j, @Log4j2, @Slf4j, @XSlf4j, @CommonsLog, @JBossLog, @Flogger, @CustomLog
@Data //这个最常见了,加一个可以默认生成了一系列的方法,可以见下图使用
@Builder
@SuperBuilder
@Singular
@Delegate
@Value
@Accessors
@Wither
@With
@SneakyThrows
@val
@var
experimental @var
@UtilityClass
Lombok config system
Code inspections
Refactoring actions (lombok and delombok)

将变量定义留着,其他方法注释掉,就可以自动生成了

image-20200518104820601

默认是生成了无参的构造器,加入AllArgsConstructor就可以了

image-20200518105023599

最后留下的代码就剩得这么干净。自己看的确实很舒服,当用的多了,不懂的人可能够呛哈哈哈。

image-20200518105157269

最后

这是第二篇mybatis文章,谢谢阅读。有错误请多多指教,谅解!跟随b站狂神的视频记录的学习笔记

mybatis03-复杂查询

MyBatis:持久层框架

前言

之前有看过和学习一些mybatis的文章和内容,但是没有去写过文章记录下,现在借鉴b站的狂神视频和官方文档看来重新撸一遍入门。有错误请多指教。

内容

数据访问层-相当于之前web项目中dao层,数据库的交互,包括增删改查;

持久化就是将数据在持久状态和瞬时状态转化的过程。内存是断电即失。所以需要数据的持久化。

JDBC技术:Connection、PrepareStatement、ResultSet.

为什么要使用框架代替jdbc呢?

​ 因为之前的jdbc的操作总是是重复单一的,在开发的时候要执行sql语句直接操作数据库,要经过加载驱动等操作,为了高效的开发,避免繁琐的操作,框架就诞生了。框架对jdbc进行封装,mybatis只需关注sql语句直接操作数据库,封装了操作的很多细节,这样可以将更多时间精力放在sql语句的编写上。

特点:灵活容易上手,用的多,封装jdbc;MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集。

演示使用

现在演示mybatis的一个helloworld程序,看看是怎么样去使用。

pom.xml,

整个项目的maven管理文件。

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
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>com.yhy.learn</groupId>
<artifactId>mybatisDemo</artifactId>
<packaging>pom</packaging>
<version>1.0-SNAPSHOT</version>
<modules>
<module>mybatis-01</module>
</modules>

<dependencies>
<dependency>
<groupId>org.mybatis</groupId>
<artifactId>mybatis</artifactId>
<version>3.5.4</version>
</dependency>

<!-- https://mvnrepository.com/artifact/mysql/mysql-connector-java -->
<dependency>
<groupId>mysql</groupId>
<artifactId>mysql-connector-java</artifactId>
<version>8.0.15</version>
</dependency>

<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.12</version>
</dependency>

</dependencies>

<build>
<resources>
<resource>
<directory>src/main/resources</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>

<resource>
<directory>src/main/java</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>
</resources>
</build>



</project>

工具类

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
package com.yhy.utils;

import org.apache.ibatis.io.Resources;
import org.apache.ibatis.session.Configuration;
import org.apache.ibatis.session.SqlSession;
import org.apache.ibatis.session.SqlSessionFactory;
import org.apache.ibatis.session.SqlSessionFactoryBuilder;

import java.io.IOException;
import java.io.InputStream;

/**
* @Author: yhy
* @Date: 2020/5/12
* @Time: 11:45
* 工具类
* 获取sqlsession工厂
*/
public class MybatisUtils {
private static SqlSessionFactory sqlSessionFactory;
static {
try {
// 利用mybatis在一开始就获得了sqlsessionfactory
String resource = "mybatis-config.xml";
InputStream inputStream = Resources.getResourceAsStream(resource);
sqlSessionFactory = new SqlSessionFactoryBuilder().build(inputStream);
} catch (IOException e) {
e.printStackTrace();
}

}
// 有了工厂就可以获得实例来使用,sqlsession就可以面向数据库操作jdbc
public static SqlSession getSqlSession(){
return sqlSessionFactory.openSession();
}



}

pojo的user类

映射数据库的user表

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
package com.yhy.pojo;

/**
* @Author: yhy
* @Date: 2020/5/12
* @Time: 10:58
* 用户表的pojo层
*/
public class User {
private int id;
private String name;
private String pwd;

public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}


public String getPwd() {
return pwd;
}

public void setPwd(String pwd) {
this.pwd = pwd;
}

}

dao层的UserDao接口

1
2
3
4
5
6
7
8
9
package com.yhy.dao;

import com.yhy.pojo.User;

import java.util.List;

public interface UserDao {
List<User> getUserList();
}

dao的接口实现xml

用这个文件代替了之前dao层中的接口实现类,之前的话需要编写jdbc的全部,查询编写sql,获取结果集,遍历结果集,关闭连接。现在的话就是简化了步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE mapper
PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN"
"http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<!--namespace=绑定一个对应的Dao/Mapper接口 原本是写接口,但是现在不用怎么做-->
<mapper namespace="com.yhy.dao.UserDao">

<!--select查询语句-->
<select id="getUserList" resultType="com.yhy.pojo.User">
select * from mybatis.user
</select>

</mapper>

mybatis-config.xml

这个是关键的配置文件,决定了连接的对象以及设定了作用域

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
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE configuration
PUBLIC "-//mybatis.org//DTD Config 3.0//EN"
"http://mybatis.org/dtd/mybatis-3-config.dtd">
<configuration>
<typeAliases>
<package name="com.yhy.pojo"/>
</typeAliases>
<environments default="development">
<environment id="development">
//事务管理
<transactionManager type="JDBC"/>
<dataSource type="POOLED">
<property name="driver" value="com.mysql.cj.jdbc.Driver"/>
<property name="url" value="jdbc:mysql://localhost:3306/mybatis?characterEncoding=UTF-8"/>
<property name="username" value="root"/>
<property name="password" value="root"/>
</dataSource>
</environment>
</environments>
//作用域,删掉就是全局
//这里的配置可以是直接放在resource文件下,就直接写上xml名称就行,放在dao层的话就需要写全路径
<mappers>
<mapper resource="com/yhy/dao/UserMapper.xml"/>
</mappers>
</configuration>

测试

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
package com.yhy.dao;

import com.yhy.pojo.User;
import com.yhy.utils.MybatisUtils;
import org.apache.ibatis.session.SqlSession;
import org.junit.Test;

import java.util.List;

/**
* @Author: yhy
* @Date: 2020/5/12
* @Time: 12:15
*/
public class UserDaoTest {
//借调工具类来使用测试
@Test
public void test(){
SqlSession sqlSession = MybatisUtils.getSqlSession();

UserDao mapper = sqlSession.getMapper(UserDao.class);
List<User> userList = mapper.getUserList();

for (User u: userList){
System.out.println(u);

}

sqlSession.close();


}


}

结果如下

image-20200512143352609

演示两种mappers作用效果

  • 1.将UserMapper.xml放在dao层下,跟着userdao配置就和我上面写的一样。最后效果如下,但是前提是你得在你项目的pom.xml设置好有效的作用域,要不然就疯狂报错,说找不到这个UserMapper.xml文件。

    image-20200512162240033

pom.xml需要配置如下,这里是配置能够得读取到src下的有效配置文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<build>
<resources>
<resource>
<directory>src/main/resources</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>

<resource>
<directory>src/main/java</directory>
<includes>
<include>**/*.xml</include>
<include>**/*.properties</include>
</includes>
</resource>
</resources>
</build>
  • 2.是直接将UserMapper.xml放在src下的resource文件下,和总的mybatis-config.xml配置文件放置在一起。这样在mybatis-config.xml里面就直接如下这样写文件名就行了。
1
<mapper resource="UserMapper.xml"/>

image-20200512143952637

最后效果和第一种方法是一样的,都能够读取到数据。

  • 个人觉得这两种方法来说,第一种可以对项目的整体设计管理更加方便一点,就像接口和实现类都是靠近的,方便进一步的审查和优化,第二种在做小的demo的时候是很方便的,但是一旦多个配置文件时候就可以有点难找。

记录错误

  1. maven创建项目一开始经常会有的错误,就是设定的jdk版本问题,一开始我都是手动去修改project的setting,比较麻烦。默认的版本一般是jdk1.4或者是jdk1.5,但大家往往不是这个版本,所以会报错不支持发行版本5什么的。

解决:现在记录下,永久得起配置好。到自己maven下载文件夹下找到配置文件,并在里面修改settings.xml

image-20200512151703715

image-20200512151630090

修改:如下,我的是jdk11。所以可以根据自己的版本来修改。

image-20200512151902737

初步学习

测试代码中的几个关键类,三者的关系都是从上到下生成。

image-20200512155009281

SqlSessionFactoryBuilder这个类可以被实例化、使用和丢弃,一旦创建了 SqlSessionFactory,就不再需要它了。

SqlSessionFactory 一旦被创建就应该在应用的运行期间一直存在,没有任何理由丢弃它或重新创建另一个实例,这样也是开发的规范。

每个线程都应该有它自己的 SqlSession 实例。SqlSession 的实例不是线程安全的,因此是不能被共享的,所以它的最佳的作用域是请求或方法作用域,同时好的开发习惯,要在使用之后,将其关闭。SqlSession就相当于jdbc中的Connection对象

namespace:表示的作用的接口范围之类的,绑定的是包名。

resultType:sql语句执行的返回值

增删改查

  1. 编写接口
  2. 写mapper.xml中的sql语句
  3. 执行语句,获得结果(注意增删改提交事务)

处理结果集映射问题

resultmap

这个处理数据库中和实体类的变量名不一样,导致结果出错。使用在主要配置文件中,为了解决列名不匹配的另外一种方式。

使用:property是实体类中的,另一个是数据库中的数据列

1
2
3
4
5
6
写在mybatis_config.xml中
<resultMap id="userResultMap" type="User">
<id property="id" column="user_id" />
<result property="username" column="user_name"/>
<result property="password" column="hashed_password"/>
</resultMap>
1
2
3
4
5
<select id="selectUsers" resultMap="userResultMap">
select user_id, user_name, hashed_password
from some_table
where id = #{id}
</select>

mybatis中的日志

首先在setting中配置,在官网中有以下的选择。

image-20200514161137980

用键值对的方式去设置各种参数,下面是使用标准日志输出。

1
2
3
4
<settings> 
<!-- 配置了日志输出 -->
<setting name="logImpl" value="STDOUT_LOGGING" />
</settings>

选择了标准功能,开启日志功能之后,测试执行了一个方法,调用数据库查询某一个id的数据,输出如下

image-20200514162220813

log4j

使用步骤

  • 导包
  • 配置log4j的文件-properties
  • 实例化日志对象
  • 使用对象的方法-info debug error等

leetcode-二进制

leetcode经典二进制运算题目

寻找只出现一次的两个数

输入:nums = [4,1,4,6]
输出:[1,6] 或 [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
class Solution {
public int[] singleNumbers(int[] nums) {
//用到了异或运算和与运算
int res = 0;
//遍历所有,最后的异或运算的结果就是这两个不同数的结果
for(int a : nums){
res ^= a;
}

//算出一个mask,二进制中的1的最低位
int flag = res & (-res);
int result[] = new int[2];
for(int a: nums){
//与运算等于0的分到一组,另一个分到另一组去
if((a&flag )== 0){
result[0] ^= a;
}else{
result[1] ^= a;
}
}
return result;

}
}

50. Pow(x, n) (快速幂,二进制)

用到

  • 向下整除 n // 2 等价于 右移一位 n >> 1 ;

  • 取余数 n % 2 等价于 判断二进制最右位 n & 1

题目:实现函数求幂

image-20200511110535592

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public double myPow(double x, int n) {
if(x == 0.0f) return 0.0d;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
}

这里需要注意的是int转为long,java中int类型的范围n∈[−2147483648,2147483647],如果n=−2147483648,执行-n就会出现越界,所以转为long来操作就安全了。一开始的报错。

image-20200511112239300

这道题最核心的部分在于下面这三行,从二进制来看,比如2的9次幂。

1
2
3
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;

那么上面的b就是9,我们需要转化为二进制为1001,又因为2的9次幂等于2的一次乘于2的八次;且由&运算可知,在1001中,也就是第一位1和第四位1会在if语句中生效,所以res就可以取得2^1*2^3=2^9;

leetcode-滑动窗口算法

leetcode刷题——总结字符串滑动窗口思想解法

做了一些字符串题目后,查看题解的时候看到了滑动窗口思想,之前都没有去了解过,看一些文章也比较模糊,想自己总结弄懂,然后能够讲接地气给你们看。

是什么

【滑动窗口算法】(sliding window algorithm)–想必大家都有在平常生活中遇到过滑动窗口的场景,这个算法浅白来讲就是这样的感觉,滑动窗口(满足了连续的位置),改变长度或者位置,去获得不同要求的结果,很明显的是这个窗口滑动距离满足不超过这个窗户整体长度,所以在处理一些字符/数组的子部分的问题时候,可能就派上用场了。

简单的数组滑动实例:

leetcode3-求无重复字符的最长子串长度

1
2
3
4
5
6
7
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串

image-20200523132319424

滑动窗口问题的解决一般都得设置好双指针

leetcode76-最小覆盖子串

image-20200523101638056

答案解析如下

image-20200523110555077

模板

在leetcode上有一位大佬总结出来了模板,可以参考下

大致逻辑如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left = 0, right = 0;

while (right < s.size()) {`
// 增大窗口
window.add(s[right]);
right++;

while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
//对应上面的例题,中间的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
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
int left = 0 , right = 0;
char[] needs = new char[128]; //相当于hashMap,用于记录每个字符的个数
char[] windows = new char[128];
for (int i = 0; i < p.length(); i++) {
needs[p.charAt(i)]++;
}
//统计符合要求字符个数
int count =0;
while(right < s.length()){

char ch = s.charAt(right);
windows[ch]++;
if (needs[ch] > 0 && needs[ch] >= windows[ch]){
count++;
}
//长度满足条件
while( count == p.length()){
//加入符合要求的结果
if (right + 1 - left == p.length()){
list.add(left);
}
//经过一轮的条件满足,要向下继续寻找,不符合下面要求,则滑动窗口,往右走
char ch1 = s.charAt(left);
//这一步是有点难理解的,一开始我是结合例子,步步过才掌握了。很巧妙
if (needs[ch1] > 0){
//这里是通过剔除已经满足的窗边位置,这样才可以往下走,重新往右搜索
windows[ch1]--;
if ( windows[ch1] < needs[ch1]){
count--;
}
}
left++;
}
right++;
}
return list;
}

作用

  • 滑动窗口算法可以解决字符串或者数组的一些子部分问题,比如一些要求连续的子部分
  • 同时可以提高效率,减低时间复杂度,将嵌套问题优化。
  • 在有些字符串情况下,比kmp算法还要高效

leetcode-动态规划

动态规划

1、前言

动态规划(Dynamic Programming)本身是属于运筹学的一个分支。是解决决策过程最优解的数学方法,

常常做到动态规划问题,想记录下做过的dp题,遇到简单的还可以想出来一些,但是常常都是有点难度,而且动态规划问题很常见,在一些大厂的笔试面试题中,今天来总结下动态规划。

2、介绍

动态规划有个很明显的特点就是可以解决重复的子问题,就是将多次重复计算的子部分省掉,只计算一次,将其记录起来,提高效率。还有一个很重要的特点是存在最优子结构-子部分中有个部分是符合题目的最优解。当然这个结果是在比较之后得出的。

3、分类

百度百科上有着详细的分类,遇到比较多的是背包问题,在下面的举例中的也大多是背包问题,背包问题就是简单来说,就一个背包,装东西,怎么装,在满足什么条件去装,从而得到不同的最优结果。

image-20200520120607437

4、使用场景以及怎么使用

使用场景

首先是什么时候会用到动态规划,一开始我也会模糊这个使用。但总的来说就是遇到一些求最值问题,或者是最优解,往往动态规划都是可以用的。

同时记住要使用动态规划的前提是必须满足最优化原理(简单说这个解一定是最屌的解,最优解)和无后效性(不受前面影响)。

最优化原理(最优子结构性质):一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

过程的历史只能通过当前的状态去影响它的未来的发展,不受之前的影响,当前的状态已经是之前的总结了,未来只能是通过现在去影响了。这个性质称为无后效性。

使用步骤

概念

动态规划中重要的三个概念有最优子结构、边界和状态转移方程。理解好这三个,任何动态规划问题就可以很好很容易解决的。

最优子结构-指的是不走最后一步或者走最后一步的最优子情况是怎么样的。

边界是每一个动态规划问题要想有解必须存在的,没有边界就没有答案,就是到某一个解的时候,其没有子解了,它自己已经是最小的了。

状态转移方程是最重要的,常常看到下面类似这种方程,就是状态转移方程。

image-20200520123555118

步骤(当确定了使用动态规划之后)

1、找到状态

(小规模问题的数学表示)状态表示阶段开始时的客观条件,当前处于什么的条件

2、最小状态是什么

这个也是指边界(最小规模的问题)也是逆推的终点。

3、列出状态转移方程

(大规模问题如何转化为更小的问题)确定过程由一个状态转移到另一个状态的演变过程。这个也是最重要的,最难的。

4、要求的返回值是什么

题目要求返回什么,就将结果解答出来。因为有时最后的最优状态不是所需的,可能需要输出其他的结果,所以要看清楚题目要求。

5、动态规划解题思维

有两种思维,简单的就是从头到尾,还有从尾到头。

自顶向下

基本会用递归,大范围开始推算到小范围(后面的最优到最前的最优),注意不断保存着中间结果,避免了重复计算。这里是和运筹学中的逆推解法大同小异。意思是从最终状态开始,逆着实际过程的进展方向逐段求解。直到第一个阶段为止。

下面举例是熟悉的走楼梯

一个人每次只能走一层楼梯或者两层楼梯,问走到第100层楼梯一共有多少种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
int[] dp= new int[100];/*用于保存中间结果否则会重复计算很多重复的子问题*/
int DP(int n)
{
//1和2是边界条件
if(n == 1)
return 1;
if(n == 2)
return 2;
//状态转移方程
dp[n] = DP(n-1) + DP(n-2);
//返回的结果
return dp[n];
}

自底向上

自小推到大,从小范围到大范围,运筹学中的顺推法,与上面只是方向不一样。

格式如下,常常伴随着for遍历

1
2
3
for(int i= 0; i < max; i++){
dp[i] = dp[i-1]+dp[i-2]
}

6、例题

题目有以下这些推荐—

image-20200521201817306

#背包问题

背包问题也分为了0-1背包和完全背包和多重背包问题

0-1背包问题

0-1背包就是每个物品只能用一次,重量价值都是一一对应,放的重量也是有限的。然后求出最大价值的放置方法

#416

image-20200521154608816

image-20200522095124725

image-20200521154729695

完全背包

完全背包问题是物品是无次数限制。其他和0-1一样

多重背包

多重背包是物品有次数限制,比如2、3、4这样的

#5

image-20200521095345466

image-20200522094922270

#983

image.png

image-20200522095328825

7、最后

动态规划就是解决冗余的。

借鉴了一些文章如下,感谢,有什么不对的地方大家多多指教,多多留言,觉得写的还可以点个赞hh

程序员小灰

知乎

leetcode of String

前言

记录和归纳leetcode上的字符串题目

题目

最长子回文串

给定一个字符串,返回子串中的最长回文串

回文应该大家知道,aba、aa、abccba这样的

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
//用的是中心扩散法
class Solution {
//往中间开始向周围找回文串
int lo;
int max;
public String longestPalindrome(String s) {
int length = s.length();
if(length < 2){
return s;
}
for(int i = 0; i < length-1; i++){
findMiddle(s,i,i);//处理奇数长度 aba
findMiddle(s,i,i+1);//处理偶数长度 abba
}
//截取
return s.substring(lo,lo+max);

}
public void findMiddle(String s,int left, int right){
//满足回文的条件,便开始循环
while(left >= 0&& right < s.length()&&left <= right && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
//每次更新的条件是满足大于之前的长度
if(max < right -left -1){
//这里的加一是因为在上面的while循环里面,假设条件是用到了left = 0了,执行完一次--,此时left会退到-1
lo = left +1;
max = right -left -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 String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int strLen = s.length();
int maxStart = 0; //最长回文串的起点
int maxEnd = 0; //最长回文串的终点
int maxLen = 1; //最长回文串的长度

boolean[][] dp = new boolean[strLen][strLen];

for (int r = 1; r < strLen; r++) {
for (int l = 0; l < r; l++) {
//判断中间是否是回文串
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
//符合回文
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
maxStart = l;
maxEnd = r;

}
}

}

}
return s.substring(maxStart, maxEnd + 1);

}

DFS和BFS

广度优先和深度优先搜索

前言

看着这两个搜索的前提的是读者具备图这一数据结构的基本知识,这些可以直接百度一波就了解了。图也像树一样,遍历具有很多的学问在里面,下面我将借用leetcode的题目讲解一下,虽然是图的遍历,但是借助树好像讲的更见浅白一点,不好的地方多指教。

广度优先搜索(BFS)

-对于树而言,就是一种层层遍历的感觉,在实现的过程中,常常借助的是辅助队列来实现,也就是借助先进先出的特性来实现的。下图来看。用BFS的话,就是3-9-20-15-7的结果。

整体实现来说,就是遍历root再来遍历左右子树,不过与DFS区别的是,这里是借助先进先出的特点,也就是要将前面的先排列出来,不用走到叶子结点才输出。一句话简单来说,BFS就是队列,入队列,出队列;

下面是借助leetcode的题目来巩固这个知识点,上面的图也是这个题的。题目要求层层从左往右遍历结点。

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
  class Solution {
public int[] levelOrder(TreeNode root) {
//特殊情况
if(root == null){
return new int[0];
}
//用队列来实现广度优先搜索
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
// 出列,这里的顺序就是先进先出,层层逐个遍历
TreeNode node = queue.poll();
list.add(node.val);
// 逐个入列,辅助队列也是BFS的关键点
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}

}
// 这样转换会慢一点
// int[] res = list.stream().mapToInt(Integer::valueOf).toArray();
int[] res = new int[list.size()];
for(int i = 0; i < list.size();i++){
res[i] = list.get(i);
}
//题目要求返回的是int[]
return res;



}
}


}

上面这道可以变形成输出结果不一样,也就是剑指offer中的后面两道-面试题31 - II. 从上到下打印二叉树和面试32题。

31题是要求输出的结果是不同数组的集合,每层的结点作为一个数组,解决代码如下

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
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return res;
}
//用队列来实现广度优先搜索
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<>();
//用队列的长度来做,这里在for循环中,长度一直在变,所以要先将其取出来
//关键点:主要思想在于用每次的队列长度来 判定这一层的结点有多少
//正如一开始只有一个根结点,所以长度等于一,只需执行一次添加list
int size = queue.size();
for(int i = 0; i < size; i++){
// 出列,这里的顺序就是先进先出,层层逐个遍历
TreeNode node = queue.poll();
//这道题要求每层出一个数组
list.add(node.val);
// 逐个入列,辅助队列也是BFS的关键点
if(node.left != null){ queue.add(node.left);}
if(node.right != null){queue.add(node.right);}
}
//每层加完就添加到结果里面
res.add(list);

}

//题目要求返回的是List<List<>>
return res;



}

}

32题有和上面不一样的地方在于,第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。就是奇数偶数层不一样的遍历方式。可以通过借助一个布尔常量来实现。

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
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return res;
}
//用队列来实现广度优先搜索
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean flag = true;
while(!queue.isEmpty()){
//这道题有实现头插法,为了高效,使用链表数组
List<Integer> list = new LinkedList<>();
//用队列的长度来做,这里在for循环中,长度一直在变,所以要先将其取出来
int size = queue.size();
for(int i = 0; i < size; i++){
// 出列,这里的顺序就是先进先出,层层逐个遍历
TreeNode node = queue.poll();
//关键点:这道题要求每层出一个数组,而且奇数行和偶数不一样
//奇数行是从左往右,偶数行是从右往左走
//借助一个布尔类型来完成
if(flag){
list.add(node.val);
}else{
//前面开始插
list.add(0,node.val);
}
// 逐个入列,辅助队列也是BFS的关键点
if(node.left != null){ queue.add(node.left);}
if(node.right != null){queue.add(node.right);}
}
//每次遍历完一行便开始更换布尔类型
flag = !flag;
//每层加完就添加到结果里面
res.add(list);

}

//题目要求返回的是List<List<>>a
return res;

}
}

深度优先搜索DFS

讲到DFS,很容易想到递归,没错它就是借助了递归的思想。在图中的描述是:深度优先搜索在搜索过程中访问某个顶点后,需要递归地访问此顶点的所有未访问过的相邻顶点

上面的图即是该题,题目要求输入一个目标sum,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

1
2
3
4
5
比如给出22,则返回下面
{
[5,4,11,2],
[5,8,4,5]
}
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
/**
leetcode 二叉树中和为某一值的路径(剑指offer34题)
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
// 有遍历 有递归
recur(root,sum);
//返回的是链表的链表结果
return res;
}

public void recur(TreeNode root,int sum){
// 递归的终止条件
if (root == null){
return;
}
path.add(root.val);
sum -= root.val;
//找到了最后叶子结点,且可以满足sum的和要求,便将该结果添加进去res
if (sum == 0&& root.left ==null&&root.right == null){
//这里需要添加新的对象
res.add(new LinkedList<>(path));
}
// 左子树递归
recur(root.left,sum);
// 右子树递归
recur(root.right,sum);
// 删掉上一个结点,这一步是比较难理解的,这一步有点回溯的感觉,就是你找到最后不符合要求的结点,你要返回到上一步,重新走下去。这一步是左右子树都递归完成后就会执行的
path.removeLast();

}
}

leetcode104-求深度

这个题是要求求树的深度,可以很好得对比BFS和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
   public int maxDepth(TreeNode root) {
// bfs
//时间复杂度也为O(n)
if(root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int num = 0;
while(!queue.isEmpty()){
num++;
//借助队列来完成
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
return num;

}


//Dfs 只有这两行。
// 时间复杂度为O(n),
if(root == null){
return 0;
}else{
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}