695.岛屿的最大面积

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

题目链接

思路

1. 深度优先搜索（DFS）
   利用深度优先搜索（DFS）对每个岛屿进行遍历，找出最大值
   （1）从每个陆地出发，遍历该陆地所在的岛屿
   （2）在遍历某一岛屿的时候：
   1）从隶属于该岛屿的某一块陆地出发，向四个方向递归地DFS
   2）每次递归对下标进行判断，以区域的边界作为递归边界
   3）为保证每块陆地只访问一次，将已访问过的陆地置0
   4）递归地返回整块岛屿的面积
   （3）找出所有岛屿的最大值，即为答案

邻接矩阵和邻接表表示的图的DFS和BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214

package test;

import java.util.LinkedList;
import java.util.Scanner;

class MGraph{
	private static final int MAXVEX = 100;
	private static final int INFINITY = 65535;
	
	int[] vexs = new int[MAXVEX];
	int[][] arc = new int[MAXVEX][MAXVEX];
	int numVertexes;
	int numEdges;
	boolean[] visited = new boolean[MAXVEX];
	
	public void createMGraph() {
		System.out.println("输入顶点数和边数：\n");
		Scanner scanner = new Scanner(System.in);
		numVertexes = scanner.nextInt();
		numEdges = scanner.nextInt();
		
		for(int i = 0; i < numVertexes; i++) {
			vexs[i] = scanner.nextInt();
		}
		
		for(int i = 0; i < numVertexes; i++) {
			for(int j = 0; j < numVertexes; j++) {
				arc[i][j] = INFINITY;
			}
		}
		
		for(int k = 0; k < numEdges; k++) {
			System.out.println("输入边（vi,vj）上的下标i,j和权w：\n");
			int i = scanner.nextInt();
			int j = scanner.nextInt();
			int w = scanner.nextInt();
			arc[i][j] = w;
			arc[j][i] = arc[i][j];
		}
	}
	
	public void DFS(int i) {
		 visited[i] = true;
		 System.out.println(vexs[i] + " ");
		 for(int j = 0; j < numVertexes; j++) {
			 if(arc[i][j] == 1 && !visited[j]) {
				 DFS(j);
			 }
		 }
	}
	
	public void DFSTraverse() {
		for(int i = 0; i < numVertexes; i++) {
			visited[i] = false;
		}
		
		for(int i = 0; i < numVertexes; i++) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}
	
	public void BFSTraverse() {
		LinkedList<Integer> queue = new LinkedList<Integer>();
		
		for(int i = 0; i < this.numVertexes; i++) {
			this.visited[i] = false;
		}
		
		for(int i = 0; i < this.numVertexes; i++) {//对每一个顶点做循环
			if(!visited[i]) {//若是未访问过就处理
				visited[i] = true;//设置当前顶点访问过
				System.out.println(this.vexs[i]);//打印顶点，也可以其他操作
				queue.addLast(i);//将此顶点入队列
				while(!queue.isEmpty()) {
					queue.pop();
					for(int j = 0; j < this.numVertexes; j++) {
						if(this.arc[i][j] == 1 && !this.visited[j]) {
							visited[j] = true;
							System.out.println(this.vexs[j]);
							queue.addLast(j);
						}
					}
				}
			}
		}
	}
}

class EdgeNode{
	int adjvex;
	EdgeNode next;
}

class VertexNode{
	int data;
	EdgeNode firstedge;
}

class GraphAdjList{
	private static final int MAXVEX = 100;
	VertexNode[] adjList= new VertexNode[MAXVEX];
	int numVertexes;
	int numEdges;
	boolean[] visited = new boolean[MAXVEX];
	
	public void createALGraph() {
		Scanner scanner = new Scanner(System.in);
		System.out.println("输入顶点数和边数：");
		this.numVertexes = scanner.nextInt();
		this.numEdges = scanner.nextInt();
		for(int i = 0 ; i < this.numVertexes; i++) {
			VertexNode node = new VertexNode();
			node.data = scanner.nextInt();
			node.firstedge = null;
			this.adjList[i] = node;
		}
		for(int k = 0; k < this.numEdges; k++) {
			System.out.println("输入边（vi,vj）上的顶点序号：\n");
			int i = scanner.nextInt();
			int j = scanner.nextInt();
			EdgeNode e = new EdgeNode();
			e.adjvex = j;
			e.next = this.adjList[i].firstedge;
			this.adjList[i].firstedge = e;
			
			EdgeNode e2 = new EdgeNode();
			e2.adjvex = i;
			e2.next = this.adjList[j].firstedge;
			this.adjList[j].firstedge = e2;
		}
	}
	
	public void DFS(int i) {
		visited[i] = true;
		System.out.println(this.adjList[i].data + " ");
		EdgeNode p = new EdgeNode();
		p = this.adjList[i].firstedge;
		while(p != null) {
			if(!visited[p.adjvex]) {
				DFS(p.adjvex);
			}
			p = p.next;
		}
	}
	
	public void DFSTraverse() {
		for(int i = 0; i < this.numVertexes; i++) {
			this.visited[i] = false;
		}
		
		for(int i = 0; i < this.numVertexes; i++) {
			if(!visited[i]) {
				this.DFS(i);
			}
		}
	}
	
	public void BFSTraverse() {
		LinkedList<Integer> queue = new LinkedList<Integer>();
		EdgeNode p = new EdgeNode();
		for(int i = 0; i < this.numVertexes; i++) {
			this.visited[i] = false;
		}
		for(int i = 0; i < this.numVertexes; i++) {
			if(!this.visited[i]) {
				this.visited[i] = true;
				System.out.println(this.adjList[i].data);//打印顶点
				queue.addLast(i);
				while(!queue.isEmpty()) {
					queue.pop();
					p = this.adjList[i].firstedge;
					while(p != null) {
						if(!this.visited[p.adjvex]) {
							this.visited[p.adjvex] = true;
							System.out.println(this.adjList[p.adjvex].data);
							queue.add(p.adjvex);
						}
						p = p.next;
					}
				}
			}
			
		}
	}
}

public class DFSAndBFS {
	public static void main(String[] args) {
		//邻接矩阵
		MGraph graph = new MGraph();
		graph.createMGraph();
		System.out.println("邻接矩阵：\n");
		for(int i = 0; i < graph.numVertexes; i++) {
			for(int j = 0; j < graph.numVertexes; j++) {
				System.out.print(graph.arc[i][j]+"\t");
			}
			System.out.println();
		}
		System.out.println("深度优先搜索遍历图（邻接矩阵）：\n");
		graph.DFSTraverse();
		System.out.println("广度优先搜索遍历图（邻接矩阵）：\n");
		graph.BFSTraverse();
		
		//邻接表
		GraphAdjList GL = new GraphAdjList();
		GL.createALGraph();
		System.out.println("深度优先搜索遍历图（邻接表）：\n");
		GL.DFSTraverse();
		System.out.println("广度优先搜索遍历图（邻接表）：\n");
		GL.BFSTraverse();
	}
}

代码

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

class Solution:
	def island_dfs(self, grid, i, j):
		if len(grid) > i >= 0 and len(grid[0]) > j >= 0:
			if grid[i][j] == 0:
				return 0
			else:
				grid[i][j] = 0
				return 1 + self.island_dfs(grid, i - 1, j) + self.island_dfs(grid, i + 1, j) + \
				       self.island_dfs(grid, i, j - 1) + self.island_dfs(grid, i, j + 1)
		else:
			return 0
	
	def max_area_of_island(self, grid):
		ans = 0
		
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				ans = max(ans, self.island_dfs(grid, i, j))
		
		return ans


if __name__ == "__main__":
	s = Solution()
	grid = [[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
	        [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
	        [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
	        [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
	        [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
	        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
	        [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
	        [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]]
	max_area = s.max_area_of_island(grid)
	print(max_area)

字符串常量池

首先来看下面一段代码：

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

public class Test {
    public static void main(String[] args){
        String a = "abc";
        String b = "abc";
        String c = "ab" + "c";
        String d = "a" + "bc";
        String e = "a" + "b" + "c";
        String f = new String("abc");

        System.out.println(a == b);//true
        System.out.println(a == c);//true
        System.out.println(a == d);//true
        System.out.println(a == e);//true
        System.out.println(a == f);//false
    }
}

• 在使用String a = “abc”创建字符串对象时，JVM会使用常量池来管理字符串直接量。在执行该语句时，JVM会先检查常量池中是否已经存有”abc”，
  若没有则将”abc”存入常量池，否则就复用常量池中已有的”abc”，将其引用赋值给变量a。
• 在使用new String(“abc”)创建字符串对象时，JVM会先使用常量池来管理字符串直接量，即将”abc”存入常量池。然后再创建一个新的String对象，
  这个对象会被保存在堆内存中。并且，堆中对象的数据会指向常量池中的直接量。

Java整数常量池

首先来看一段示例代码，我们会发现这样的现象 127 = 127,128 != 128。

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

public class Test {
    public static void main(String[] args) {
        Integer a = 127;
        Integer b = 127;
        Integer c = 128;
        Integer d = 128;
        System.out.println(a == b);//true
        System.out.print(c == d);//false

        Integer e = 1;
        int f = 1;
        System.out.println(e == f); //Integer和int进行比较时，Integer会自动拆箱为int，然后比较两个值是否相等。
    }
}

为什么会出现这样的现象，我们来看以下Integer类的源码：

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

/**
 * Cache to support the object identity semantics of autoboxing for values between
 * -128 and 127 (inclusive) as required by JLS(Java Language Specification).
 *
 * The cache is initialized on first usage.  The size of the cache
 * may be controlled by the {@code -XX:AutoBoxCacheMax=<size>} option.
 * During VM initialization, java.lang.Integer.IntegerCache.high property
 * may be set and saved in the private system properties in the
 * sun.misc.VM class.
 */

private static class IntegerCache {
    static final int low = -128;
    static final int high;
    static final Integer cache[];

    static {
        // high value may be configured by property
        int h = 127;
        String integerCacheHighPropValue =
            sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
        if (integerCacheHighPropValue != null) {
            try {
                int i = parseInt(integerCacheHighPropValue);
                i = Math.max(i, 127);
                // Maximum array size is Integer.MAX_VALUE
                h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
            } catch( NumberFormatException nfe) {
                // If the property cannot be parsed into an int, ignore it.
            }
        }
        high = h;

        cache = new Integer[(high - low) + 1];
        int j = low;
        for(int k = 0; k < cache.length; k++)
            cache[k] = new Integer(j++);

        // range [-128, 127] must be interned (JLS7 5.1.7)
        assert IntegerCache.high >= 127;
    }

    private IntegerCache() {}
}

以上这段代码是Integer类的一个内部类IntegerCache，它缓存了-128 ~ 127之间的整数值，缓存的最小值为low表示的值，缓存的最大值为high表示的值。
在创建这个范围内的整数对象时，可以在常量池中直接引用，而无需重新创建，因此 a == b 返回true。超出此范围的值，会通过new新的对象，因此 c == d返回false。

SpringBoot集成Druid

Java程序很大一部分要操作数据库，为了提高性能操作数据库的时候，又不得不使用数据库连接池。
Druid 是阿里巴巴开源平台上一个数据库连接池实现，结合了 C3P0、DBCP 等 DB 池的优点，同时加入了日志监控。
Druid 可以很好的监控 DB 池连接和 SQL 的执行情况，天生就是针对监控而生的 DB 连接池。
Druid已经在阿里巴巴部署了超过600个应用，经过一年多生产环境大规模部署的严苛考验。
Spring Boot 2.0 以上默认使用 Hikari 数据源，可以说 Hikari 与 Driud 都是当前 Java Web 上最优秀的数据源，我们来重点介绍 Spring Boot 如何集成 Druid 数据源，如何实现数据库监控。

Github地址

• 项目目录
  
• 添加Druid数据源依赖

  1 2 3 4 5

  <dependency> <groupId>com.alibaba</groupId> <artifactId>druid</artifactId> <version>1.2.11</version> </dependency>

• 切换数据源并配置数据源；之前已经说过 Spring Boot 2.0 以上默认使用 com.zaxxer.hikari.HikariDataSource 数据源，但可以 通过 spring.datasource.type 指定数据源

  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

  spring: datasource: username: root password: root url: jdbc:mysql://localhost:3306/test?serverTimezone=UTC&useUnicode=true&characterEncoding=utf-8 driver-class-name: com.mysql.jdbc.Driver type: com.alibaba.druid.pool.DruidDataSource #SpringBoot默认是不注入这些的，需要自己绑定 #druid数据源专有配置 initialSize: 5 minIdle: 5 maxActive: 20 maxWait: 60000 timeBetweenEvictionRunsMillis: 60000 minEvictableIdleTimeMillis: 300000 validationQuery: SELECT 1 FROM DUAL testWhileIdle: true testOnBorrow: false testOnReturn: false poolPreparedStatements: true #配置监控统计拦截的filters，stat：监控统计、log4j：日志记录、wall：防御sql注入 #如果允许报错，java.lang.ClassNotFoundException: org.apache.Log4j.Properity #则导入log4j 依赖就行 filters: stat,wall # ,log4j maxPoolPreparedStatementPerConnectionSize: 20 useGlobalDataSourceStat: true connectionoProperties: druid.stat.mergeSql=true;druid.stat.slowSqlMillis=500

• 现在需要程序员自己为 DruidDataSource 绑定全局配置文件中的参数，再添加到容器中，而不再使用 Spring Boot 的自动生成了；我们需要 自己添加 DruidDataSource 组件到容器中，并绑定属性；

  1 2 3 4 5 6 7 8 9 10 11

  @Configuration public class DruidConfig { //绑定全局配置文件中的参数 @ConfigurationProperties(prefix = "spring.datasource") @Bean public DataSource druidDataSource() { return new DruidDataSource(); } }

• 测试Druid数据源是否配置成功

  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

  package com.example; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import javax.sql.DataSource; import java.sql.Connection; import java.sql.SQLException; @SpringBootTest class SpringDataApplicationTests { @Autowired DataSource dataSource; @Test void contextLoads() throws SQLException { //查看默认的数据源 System.out.println(dataSource.getClass()); //获得数据库链接 Connection connection = dataSource.getConnection(); System.out.println(connection); //关闭 connection.close(); } }

• 配置Druid数据源监控
  Druid 数据源具有监控的功能，并提供了一个 web 界面方便用户查看，类似安装 路由器 时，人家也提供了一个默认的 web 页面。
  所以第一步需要设置 Druid 的后台管理页面，比如 登录账号、密码 等；配置后台管理；

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

  // 后台监控：相当于web.xml，配置ServletRegistrationBean //因为SprintBoot内置了servlet容器，所以没有web.xml，替代方法ServletRegistrationBean @Bean public ServletRegistrationBean statViewServlet() { ServletRegistrationBean<StatViewServlet> bean = new ServletRegistrationBean<>(new StatViewServlet(), "/druid/*"); // 后台登录进行账号密码配置 HashMap<String, String> initParameters = new HashMap<>(); // 增加配置，登录的key是固定的，loginUsername loginPassword initParameters.put("loginUsername", "admin"); initParameters.put("loginPassword", "123456"); // 允许谁可以访问，如果后面的参数为空代表谁都可以访问，指定参数只能指定的参数进行访问 initParameters.put("allow", ""); // 禁止谁可以访问 // initParameters.put("koko","192.168.43.21"); bean.setInitParameters(initParameters); // 设置初始化参数 return bean; }

• 配置完成后，就可以通过http://localhost:8080/druid/login.html访问监控页面
  
• 登录成功后显示的监控页面
  
• 配置 Druid web 监控 filter 过滤器

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

  //filter @Bean public FilterRegistrationBean webStatFileter(){ FilterRegistrationBean bean = new FilterRegistrationBean(); bean.setFilter(new WebStatFilter()); //可以过滤那些请求呢？ Map<String, String> initParameters = new HashMap<>(); //这些东西不进行统计 initParameters.put("exclusions", "*.js,*.css,/druid/*"); return bean; }

SpringBoot集成MyBatis

• 项目目录
  
• 导入MyBatis所需要的依赖

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

  <!--mybatis-springboot--> <dependency> <groupId>org.mybatis.spring.boot</groupId> <artifactId>mybatis-spring-boot-starter</artifactId> <version>1.3.2</version> </dependency> <!--lombok--> <dependency> <groupId>org.projectlombok</groupId> <artifactId>lombok</artifactId> </dependency>

• 数据库和表
  
• 配置数据库连接信息(application.yaml)、配置mybatis

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

  spring: datasource: username: root password: 123456 #?serverTimezone=UTC解决时区的报错 url: jdbc:mysql://localhost:3306/mybatis?serverTimezone=UTC&useUnicode=true&characterEncoding=utf-8 driver-class-name: com.mysql.cj.jdbc.Driver # 整合mybatis mybatis: type-aliases-package: com.example.pojo mapper-locations: classpath:mybatis/mapper/*.xml

• 创建实体类User.java（需要用到lombok）

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

  package com.example.pojo; import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor; @Data @AllArgsConstructor @NoArgsConstructor public class User { private int id; private String name; private String pwd; }

• 创建Mapper接口UserMapper.java

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

  package com.example.mapper; import com.example.pojo.User; import org.apache.ibatis.annotations.Mapper; import org.springframework.stereotype.Repository; import java.util.List; @Mapper @Repository public interface UserMapper { List<User> queryUserList(); User queryUserById(int id); int addUser(User user); int updateUser(User user); int deleteUser(int id); }

• 创建映射文件UserMapper.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 mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd"> <mapper namespace="com.example.mapper.UserMapper"> <!--resultType="User"和parameterType="User"只有配置了type-aliases-package后才能起作用--> <select id="queryUserList" resultType="User"> select * from user </select> <select id="queryUserById" resultType="User"> select * from user where id = #{id} </select> <insert id="addUser" parameterType="User"> insert into user (id, name, pwd) values (#{id}, #{name}, #{pwd}) </insert> <update id="updateUser" parameterType="User"> update user set name=#{name},pwd=#{pwd} where id = #{id} </update> <delete id="deleteUser" parameterType="int"> delete from user where id = #{id} </delete> </mapper>

• 编写UserController.java进行测试

  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

  package com.example.controller; import com.example.mapper.UserMapper; import com.example.pojo.User; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.PathVariable; import org.springframework.web.bind.annotation.RestController; import javax.websocket.server.PathParam; import java.util.List; @RestController public class UserController { @Autowired private UserMapper userMapper; @GetMapping("/queryUserList") public List<User> queryUserList(){ List<User> userList = userMapper.queryUserList(); return userList; } @GetMapping("/queryUserById/{id}") public User queryUserById(@PathVariable Integer id){ User user = userMapper.queryUserById(id); return user; } // @GetMapping("/addUser") //http://localhost:8080/addUser?id=4&name=wangmazi&pwd=91011 // public String addUser(@PathParam("id")Integer id, @PathParam("name")String name, @PathParam("pwd")String pwd){ // userMapper.addUser(new User(id, name, pwd)); // return "ok"; // } @GetMapping("/addUser/{id}/{name}/{pwd}") //http://localhost:8080/addUser/4/wangmazi/123 public String addUser(@PathVariable("id") Integer id, @PathVariable("name") String name, @PathVariable("pwd") String pwd){ userMapper.addUser(new User(id, name, pwd)); return "ok"; } @GetMapping("/updateUser") public String updateuser(){ userMapper.updateUser(new User(5, "liuba", "325")); return "ok"; } @GetMapping("/deleteUser/{id}") public String deleteUser(@PathVariable("id") Integer id){ userMapper.deleteUser(id); return "ok"; } }

SpringSecurity用户认证、授权、注销、权限控制、记住我、首页定制

• 实现功能：授权不同的用户角色访问不同的模块，如下图所示：
  

• 描述

  • 设置三个不同用户角色（victory,root,guest）
  • victory可以访问level2和leve3的内容，root可以访问页面的所有内容，guest只可以访问level1的内容，而且没有权限的模块在该用户登录时不显示。
  • 没有登录时，点击三个模块的内容会跳转到登录页面
  • 记住我功能
  • 首页定制（不使用SpringSecurity默认登录页面，使用自己写的登录页面）

• 页面
  

• 依赖导入

  • 导入thymeleaf依赖

    1 2 3 4 5 6 7 8

    <dependency> <groupId>org.thymeleaf</groupId> <artifactId>thymeleaf-spring5</artifactId> </dependency> <dependency> <groupId>org.thymeleaf.extras</groupId> <artifactId>thymeleaf-extras-java8time</artifactId> </dependency>

  • 导入Web依赖

    1 2 3 4

    <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web</artifactId> </dependency>

  • 导入security依赖

    1 2 3 4

    <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-security</artifactId> </dependency>

• 项目目录
  

• 编写RootController映射请求（跳转页面）

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

package com.example.controller;

import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestMapping;

@Controller
public class RootController {
    @RequestMapping({"/", "/index"})
    public String index(){
        return "index";
    }

    @RequestMapping("toLogin")
    public String toLogin(){
        return "views/login";
    }

    @RequestMapping("/level1/{id}")
    public String level1(@PathVariable("id") int id){
        return "views/level1/"+id;
    }

    @RequestMapping("/level2/{id}")
    public String level2(@PathVariable("id") int id){
        return "views/level2/"+id;
    }

    @RequestMapping("/level3/{id}")
    public String level3(@PathVariable("id") int id){
        return "views/level3/"+id;
    }
}

• 编写SecurityConfig配置SpringSecurity

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

package com.example.config;

import org.springframework.security.config.annotation.authentication.builders.AuthenticationManagerBuilder;
import org.springframework.security.config.annotation.web.builders.HttpSecurity;
import org.springframework.security.config.annotation.web.configuration.EnableWebSecurity;
import org.springframework.security.config.annotation.web.configuration.WebSecurityConfigurerAdapter;
import org.springframework.security.crypto.bcrypt.BCryptPasswordEncoder;

@EnableWebSecurity
public class SecurityConfig extends WebSecurityConfigurerAdapter {
    //授权
    @Override
    protected void configure(HttpSecurity http) throws Exception {
        //首页所有人可以访问，功能页只有对应有权限的人才能访问
        //请求授权的规则
        //链式编程
        http.authorizeHttpRequests()
                .antMatchers("/").permitAll()
                .antMatchers("/level1/**").hasRole("vip1")
                .antMatchers("/level2/**").hasRole("vip2")
                .antMatchers("/level3/**").hasRole("vip3");

        //没有权限默认会跳到登录页面
        http.formLogin();

        //防止网站攻击 get不安全，可以使用post springboot默认开启csrf(注销失败可能的原因)
        http.csrf().disable(); //关闭csrf功能

        //注销，跳到首页
        http.logout().logoutSuccessUrl("/");
    }

    //认证
    //密码编码：PasswordEncoder
    //在Spring Security 5.0+新增了很多加密方法
    //报错 500 密码没有加密
    @Override
    protected void configure(AuthenticationManagerBuilder auth) throws Exception {
        //这些数据正常应该从数据库中读
        auth.inMemoryAuthentication().passwordEncoder(new BCryptPasswordEncoder())
                .withUser("victory").password(new BCryptPasswordEncoder().encode("123")).roles("vip2", "vip3")
                .and()
                .withUser("root").password(new BCryptPasswordEncoder().encode("123")).roles("vip1", "vip2", "vip3")
                .and()
                .withUser("guest").password(new BCryptPasswordEncoder().encode("123")).roles("vip1");
    }
}

• 权限控制（没有权限的模块在该用户登录时不显示）
  • 导入依赖

    1 2 3 4 5

    <dependency> <groupId>org.thymeleaf.extras</groupId> <artifactId>thymeleaf-extras-springsecurity4</artifactId> <version>3.0.4.RELEASE</version> </dependency>

  • 在页面中导入命名空间

    1	<html lang="en" xmlns:th="http://www.thymeleaf.org" xmlns:sec="http://www.thymeleaf.org/thymeleaf-extras-springsecurity4">

  • 在页面中使用thymeleaf-security语法进行权限控制

    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

    <!DOCTYPE html> <html lang="en" xmlns:th="http://www.thymeleaf.org" xmlns:sec="http://www.thymeleaf.org/thymeleaf-extras-springsecurity4"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"> <title>首页</title> <!--semantic-ui--> <link href="https://cdn.bootcss.com/semantic-ui/2.4.1/semantic.min.css" rel="stylesheet"> <link th:href="@{/qinjiang/css/qinstyle.css}" rel="stylesheet"> </head> <body> <!--主容器--> <div class="ui container"> <div class="ui segment" id="index-header-nav" th:fragment="nav-menu"> <div class="ui secondary menu"> <a class="item" th:href="@{/index}">首页</a> <!--登录注销--> <div class="right menu"> <!--如果未登录--> <div sec:authorize="!isAuthenticated()"> <a class="item" th:href="@{/toLogin}"> <i class="address card icon"></i> 登录 </a> </div> <!--如果登录：用户名和注销--> <div sec:authorize="isAuthenticated()"> <a class="item"> 用户名：<span sec:authentication="name"></span> <!--角色：<span sec:authentication="principal.getUsername()"></span>--> </a> <a class="item" th:href="@{/logout}"> <i class="sign-out icon"></i> 注销 </a> </div> </div> </div> </div> <div class="ui segment" style="text-align: center"> <h3>Spring Security Study by 秦疆</h3> </div> <div> <br> <div class="ui three column stackable grid"> <!--根据用户的角色动态的实现--> <div class="column" sec:authorize="hasRole('vip1')"> <div class="ui raised segment"> <div class="ui"> <div class="content"> <h5 class="content">Level 1</h5> <hr> <div><a th:href="@{/level1/1}"><i class="bullhorn icon"></i> Level-1-1</a></div> <div><a th:href="@{/level1/2}"><i class="bullhorn icon"></i> Level-1-2</a></div> <div><a th:href="@{/level1/3}"><i class="bullhorn icon"></i> Level-1-3</a></div> </div> </div> </div> </div> <div class="column" sec:authorize="hasRole('vip2')"> <div class="ui raised segment"> <div class="ui"> <div class="content"> <h5 class="content">Level 2</h5> <hr> <div><a th:href="@{/level2/1}"><i class="bullhorn icon"></i> Level-2-1</a></div> <div><a th:href="@{/level2/2}"><i class="bullhorn icon"></i> Level-2-2</a></div> <div><a th:href="@{/level2/3}"><i class="bullhorn icon"></i> Level-2-3</a></div> </div> </div> </div> </div> <div class="column" sec:authorize="hasRole('vip3')"> <div class="ui raised segment"> <div class="ui"> <div class="content"> <h5 class="content">Level 3</h5> <hr> <div><a th:href="@{/level3/1}"><i class="bullhorn icon"></i> Level-3-1</a></div> <div><a th:href="@{/level3/2}"><i class="bullhorn icon"></i> Level-3-2</a></div> <div><a th:href="@{/level3/3}"><i class="bullhorn icon"></i> Level-3-3</a></div> </div> </div> </div> </div> </div> </div> </div> <script th:src="@{/qinjiang/js/jquery-3.1.1.min.js}"></script> <script th:src="@{/qinjiang/js/semantic.min.js}"></script> </body> </html>

  • thymeleaf security整合可能出现的错误
    • thymeleaf security不生效，可以将SpringBoot版本降低到2.0.7.RELEASE
    • 登录后出现WhiteLabel Error Page，Html文件中关于thymeleaf-security的代码有错误
• 记住我、首页定制
  • 首页定制、记住我
    在configure(HttpSecurity http)方法中添加以下代码即可定制首页

    1 2 3 4

    //formLogin() 默认到登录页面（SpringSecurity自带登录页面） //usernameParameter("user") 与自定义登录页面用户名文本框的name属性对应 //passwordParameter("pwd") 与自定义登录页面密码文本框的name属性对应 http.formLogin().loginPage("/toLogin").usernameParameter("user").passwordParameter("pwd").loginProcessingUrl("/login");

    在configure(HttpSecurity http)方法中添加以下代码即可实现记住我功能

    1 2	//开启记住我功能 cookie,默认保存两周 http.rememberMe().rememberMeParameter("remember");

  • 页面

    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

    <!DOCTYPE html> <html lang="en" xmlns:th="http://www.thymeleaf.org"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"> <title>登录</title> <!--semantic-ui--> <link href="https://cdn.bootcss.com/semantic-ui/2.4.1/semantic.min.css" rel="stylesheet"> </head> <body> <!--主容器--> <div class="ui container"> <div class="ui segment"> <div style="text-align: center"> <h1 class="header">登录</h1> </div> <div class="ui placeholder segment"> <div class="ui column very relaxed stackable grid"> <div class="column"> <div class="ui form"> <form th:action="@{/login}" method="post"> <div class="field"> <label>Username</label> <div class="ui left icon input"> <input type="text" placeholder="Username" name="user"> <i class="user icon"></i> </div> </div> <div class="field"> <label>Password</label> <div class="ui left icon input"> <input type="password" name="pwd"> <i class="lock icon"></i> </div> </div> <div class="field"> <input type="checkbox" name="remember">记住我 </div> <input type="submit" class="ui blue submit button"/> </form> </div> </div> </div> </div> <div style="text-align: center"> <div class="ui label"> </i>注册 </div> <br><br> <small>blog.kuangstudy.com</small> </div> <div class="ui segment" style="text-align: center"> <h3>Spring Security Study by 秦疆</h3> </div> </div> </div> <script th:src="@{/qinjiang/js/jquery-3.1.1.min.js}"></script> <script th:src="@{/qinjiang/js/semantic.min.js}"></script> </body> </html>

SpringBoot常用的请求映射方式注解

我们在处理web端应用的请求时，通常会使用如下几种方式进行请求映射，我们可以通过查看源码看到它们的真实面目。

• @RequestMapping

源码对注解的注释：Annotation for mapping web requests onto methods in request-handling classes with flexible method signatures.

翻译：用于将web请求映射到具有灵活方法签名的请求处理类中的方法的注释。

• @GetMapping

源码对注解的注释：Annotation for mapping HTTP GET requests onto specific handler methods.
Specifically, @GetMapping is a composed annotation that acts as a shortcut for @RequestMapping(method = RequestMethod.GET).

翻译：用于将HTTP GET请求映射到特定的请求处理方法的注释。具体来说，@GetMapping是一个组合注解，是@RequestMapping(method = RequestMethod.GET)的缩写。

• @PostMapping

源码对注解的注释：Annotation for mapping HTTP POST requests onto specific handler methods.
Specifically, @PostMapping is a composed annotation that acts as a shortcut for @RequestMapping(method = RequestMethod.POST).

翻译：用于将HTTP POST请求映射到特定的请求处理方法的注释。具体来说，@PostMapping是一个组合注解，是@RequestMapping(method = RequestMethod.POST)的缩写。

• @PutMapping

源码对注解的注释：Annotation for mapping HTTP PUT requests onto specific handler methods.
Specifically, @PutMapping is a composed annotation that acts as a shortcut for @RequestMapping(method = RequestMethod.PUT).

翻译：用于将HTTP PUT请求映射到特定的请求处理方法的注释。具体来说，@PutMapping是一个组合注解，是@RequestMapping(method = RequestMethod.PUT)的缩写。

• @DeleteMapping

源码对注解的注释：Annotation for mapping HTTP DELETE requests onto specific handler methods.
Specifically, @DeleteMapping is a composed annotation that acts as a shortcut for @RequestMapping(method = RequestMethod.DELETE).

翻译：用于将HTTP DELETE请求映射到特定的请求处理方法的注释。具体来说，@DeleteMapping是一个组合注解，是@RequestMapping(method = RequestMethod.DELETE)的缩写。

• @PatchMapping

源码对注解的注释：Annotation for mapping HTTP PATCH requests onto specific handler methods.
Specifically, @PatchMapping is a composed annotation that acts as a shortcut for @RequestMapping(method = RequestMethod.PATCH).

翻译：用于将HTTP PATCH请求映射到特定的请求处理方法的注释。具体来说，@PatchMapping是一个组合注解，是@RequestMapping(method = RequestMethod.PATCH)的缩写。

从源码注释和注解接口实现源代码可以得出以下结论：

• 可以使用@RequestMapping注解并指定method属性对所有HTTP进行映射。
• @XxxMapping注解是@RequestMapping(method=”XXX”)的缩写
  • @GetMapping是@RequestMapping(method = RequestMethod.GET)的缩写
  • @PostMapping是@RequestMapping(method = RequestMethod.POST)的缩写
  • @PutMapping是@RequestMapping(method = RequestMethod.PUT)的缩写
  • @DeleteMapping是@RequestMapping(method = RequestMethod.DELETE)的缩写
  • @PatchMapping是@RequestMapping(method = RequestMethod.PATCH)的缩写
• 推荐用法：在对特定的请求进行映射时，采用对应的注解。

414.第三大的数

题目描述

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

• 示例 1：
  输入：[3, 2, 1]
  输出：1
  解释：第三大的数是 1 。

• 示例 2：
  输入：[1, 2]
  输出：2
  解释：第三大的数不存在, 所以返回最大的数 2 。

• 示例 3：
  输入：[2, 2, 3, 1]
  输出：1
  解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
  此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

题目链接

思路

1. 排序
   将nums数组排序后，从数组末尾返回第三大的数。
2. 有序集合
   遍历数组，同时用一个有序集合来维护数组中前三大的数。具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 333，就删除集合中的最小元素。这样可以保证有序集合的大小至多为 333，且遍历结束后，若有序集合的大小为 333，其最小值就是数组中第三大的数；若有序集合的大小不足 333，那么就返回有序集合中的最大值。
3. 一次遍历
   遍历数组，并用三个变量a、b、c来维护数组中的最大值、次大值和第三大值，在遍历过程中更新这三个值即可。

   代码

   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

   class Solution(object): def thirdMax(self, nums): """ 排序（自己实现快速排序） :type nums: List[int] :rtype: int """ def quick_sort(arr, low, high): if low < high: pivot = partition(arr, low, high) quick_sort(arr, low, pivot - 1) quick_sort(arr, pivot + 1, high) def partition(arr, low, high): pivot_key = arr[low] while low < high: while low < high and arr[high] >= pivot_key: high -= 1 arr[low], arr[high] = arr[high], arr[low] while low < high and arr[low] <= pivot_key: low += 1 arr[low], arr[high] = arr[high], arr[low] return low quick_sort(nums, 0, len(nums) - 1) diff = 0 for i in range(len(nums) - 1, -1, -1): if nums[i] != nums[i - 1]: diff += 1 if diff == 2: return nums[i-1] return nums[-1] def thirdMax1(self, nums): """排序（直接调用排序方法）""" nums.sort(reverse=True) diff = 1 for i in range(1, len(nums)): if nums[i] != nums[i-1]: diff += 1 if diff == 3: return nums[i] return nums[0] def thirdMax2(self, nums): """有序集合""" from sortedcontainers import SortedList s = SortedList() for num in nums: if num not in s: s.add(num) if len(s) > 3: s.pop(0) return s[0] if len(s) == 3 else s[-1] def thirdMax3(self, nums): """一次遍历（用三个变量a,b,c来维护数组中的最大值、次大值和第三大值）""" a, b, c = float('-inf'), float('-inf'), float('-inf') for num in nums: if num > a: a, b, c = num, a, b elif a > num > b: b, c = num, b elif b > num > c: c = num return a if c == float('-inf') else c if __name__ == "__main__": slt = Solution() # third_max_num = slt.thirdMax([2, 2, 3, 1]) # third_max_num = slt.thirdMax1([2, 2, 3, 1]) # third_max_num = slt.thirdMax2([2, 2, 3, 1]) third_max_num = slt.thirdMax3([2, 2, 3, 1]) print(third_max_num)

python处理json数据

找出以下json数据中children键对应列表为空的data键的id值。
例如以下示例children键对应的列表为空时，返回data键的id值：

1
2
3
4

{
    "data": {"id": 1234},
    "children": []
}

• 方法：
  分析数据可知，该文本数组为字典类型的嵌套，故可以使用递归的方法解决。
  首先全部输入文本就是一个大字典，因此递归函数输入为一个大字典，然后判断字典中children键对应的列表是否为空，
  如果为空则将children键对应的data键的id加入结果列表，如果children键对应的列表（列表中的元素仍为字典）不为空，
  则遍历列表中的字典，继续使用该递归函数进行处理，依次类推。
• 重要的一步
  在处理json数据中极为重要的一步是将一个字符串表示的字典转换为python中的字典。
  我们可以使用python中的内置模块json中的loads方法将一个字符串表示的字典转换为json数据，既python中的字典。

  1	json_data = json.loads(string_dict)

349.两个数组的交集

题目描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

题目链接

思路

1. 集合求交集
2. 排序+双指针
   对nums1、nums2进行排序，设置两个指针index1、index2分别指向两个数组的头部，并按以下步骤进行：
   （1）如果元素相等则加入结果列表
   （2）如果index1指向的元素小于index2指向的元素，则index1指针后移，否则index2指针后移
   不断执行以上两个步骤，最后结果列表中的元素即为两个数字的交集。

   代码

   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

   """ 集合操作 1.求交集 set1.intersection(set2) 2.求差集 set1.difference(set2) 3.求并集 set1.union(set2) """ class Solution(object): def intersection(self, nums1, nums2): """ 集合求交集 :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ return list(set(nums1).intersection(set(nums2))) def intersection1(self, nums1, nums2): """排序+双指针""" nums1.sort() nums2.sort() index1 = 0 index2 = 0 intersection = list() while index1 < len(nums1) and index2 < len(nums2): if nums1[index1] == nums2[index2]: if not intersection or nums1[index1] != intersection[-1]: intersection.append(nums1[index1]) index1 += 1 index2 += 1 elif nums1[index1] < nums2[index2]: index1 += 1 else: index2 += 1 return intersection if __name__ == "__main__": slt = Solution() nums1 = [2, 1] nums2 = [1, 2] # inter = slt.intersection(nums1, nums2) inter = slt.intersection(nums1, nums2) print(inter)