P1004 [NOIP 2000 提高组] 方格取数

#走两次dp
如果只走一次,这题是非常经典的DP。但是要走两次,就变得非常有难度。
首先,可以简单地推广:要走两次,dp就存四个下标:

int[][][][] dp = new int[N][N][N][N];

我们只需要遍历所有可能,并且比较四种走法(同下、同右、一下一右),取最大值就可以了。
注意,一个数只能取一次,需要一个判断防止重复取数。

for (int i1 = 1; i1 < N; i1 += 1) {
for (int i2 = 1; i2 < N; i2 += 1) {
for (int j1 = 1; j1 < N; j1 += 1) {
for (int j2 = 1; j2 < N; j2 += 1) {
int step = map[i1][j1];
if (i2 != i1 && j2 != j1) step += map[i2][j2];

dp[i1][j1][i2][j2] =
Math.max(dp[i1-1][j1][i2-1][j2],
Math.max(dp[i1-1][j1][i2][j2-1],
Math.max(dp[i1][j1-1][i2-1][j2],
dp[i1][j1-1][i2][j2-1]))) + step;
}
}
}
}
System.out.println(dp[N-1][N-1][N-1][N-1]);

当然,4个循环时间复杂度太高了。我们可以用一个k == i1 + j1 == i2 + j2来减少一重循环。
这个k利用得很巧妙,因为每次要么向下走,要么向右走,所以k-1 == i-1 + j == i + j-1,全程使用k-1就能代表所有情况。

阅读全文 »

0.0 PTA实录

0.1.1 最大子列和plus

  • 如何利用语句先后顺序记录上一条信息pre_start_tag
void sum_max_sequence(void)
{
long long int this_sum, max_sum;
int start_tag, end_tag, pre_start_tag, neg_tag;

start_tag = pre_start_tag = end_tag = 0;
this_sum = max_sum = 0;
neg_tag = 1;

for (int i = 0; i < num; i++)
{
if (list[i] >= 0) {
neg_tag = 0;
}
this_sum += list[i];
if (this_sum > max_sum)
{
max_sum = this_sum;
end_tag = i;
pre_start_tag = start_tag; // 我没有想到的代码!
}
if (this_sum < 0)
{
this_sum = 0;
start_tag = i+1;
}
}


if(neg_tag) // 输出0,第一个和最后一个数
printf("%lld %d %d\n", max_sum, list[0], list[num-1]);
else if (max_sum == 0)
{
printf("0 0 0\n");
}

else
printf("%lld %d %d\n", max_sum, list[pre_start_tag], list[end_tag]);
}
阅读全文 »

51 和的逆运算

#全排列
这题在给定的和不重复的情况下很简单:

  1. 首先升序排序好数组sums,生成答案数组nums[n]
  2. nums[0] + nums[1] 必然等于sums[0](最小值),nums[0] + nums[2] 必然等于sums[1](次小值), … , nums[n-2] + nums[n-1] 必然等于sums[lastIndex](最大值)。
  3. 可以反向推测出nums[0] = (sums[0] + sums[1] - sums[n-1]) / 2,论证看下方:
nums[n] = {a, b, c, d, e} 从小到大排列
a + b = sums[0] (1) // 最小
a + c = sums[1] (2)
a + d = sums[2]
a + e = sums[3]
b + c = sums[4] (3)
...
(1) + (2) = 2a + (3)
2a = sums[0] + sums[1] - sums[n-1] = (1) + (2) - (3)
  1. 得出了nums[0],其他数字都可以用nums[i] = sums[i-1] - nums[0]推出来

但是给定的和重复的情况下,上面的第2条就不成立了。例如测试用例3:

阅读全文 »

Tomcat

JRE报错

一般教程会让我们配置JAVA_HOMEJRE_HOME,然后启动Tomcat;
然而,在JDK9以后,就不默认包含JRE了。
此时,我们使用命令

jlink --module-path jmods --add-modules java.desktop --output jre

生成一个JRE后,启动Tomcat,就会报错:

WARNING: Unknown module: java.rmi specified to --add-opens
Exception in thread "main" java.lang.NoClassDefFoundError: java/util/logging/Logger
at org.apache.juli.logging.DirectJDKLog.<init>(DirectJDKLog.java:61)
at org.apache.juli.logging.DirectJDKLog.getInstance(DirectJDKLog.java:181)
at org.apache.juli.logging.LogFactory.getInstance(LogFactory.java:133)
at org.apache.juli.logging.LogFactory.getInstance(LogFactory.java:156)
at org.apache.juli.logging.LogFactory.getLog(LogFactory.java:211)
at org.apache.catalina.startup.Bootstrap.<clinit>(Bootstrap.java:49)
Caused by: java.lang.ClassNotFoundException: java.util.logging.Logger
at java.base/jdk.internal.loader.BuiltinClassLoader.loadClass(BuiltinClassLoader.java:641)
at java.base/jdk.internal.loader.ClassLoaders$AppClassLoader.loadClass(ClassLoaders.java:188)
at java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:525)
... 6 more

这时候,只需要把jre文件和JRE_HOME环境变量删除,Tomcat就能正常启动

阅读全文 »

mybatis-config.xml

<?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>
<environments default="development">
<environment id="development"> <!-- 设置环境 -->
<transactionManager type="JDBC"/>
<dataSource type="POOLED">
<property name="driver" value="${驱动类(含包名)}"/>
<property name="url" value="${数据库连接URL}"/>
<property name="username" value="${用户名}"/>
<property name="password" value="${密码}"/>
</dataSource>
</environment>
</environments>
</configuration>

Util

一般只需要创建一次,所以创建一个工具类

public class MybatisUtil {

//在类加载时就进行创建
private static SqlSessionFactory sqlSessionFactory;
static {
try {
sqlSessionFactory = new SqlSessionFactoryBuilder().build(new FileInputStream("mybatis-config.xml"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}

/**
* 获取一个新的会话
* @param autoCommit 是否开启自动提交(跟JDBC是一样的,如果不自动提交,则会变成事务操作)
* @return SqlSession对象
*/
public static SqlSession getSession(boolean autoCommit){
return sqlSessionFactory.openSession(autoCommit);
}
}
阅读全文 »

SpringBoot Mail 邮箱验证码

<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-mail</artifactId>
</dependency>
spring:
mail:
host: your.SMTP.host
username: your_server_email@email.com
password: your_passowrd
@Resource
JavaMailSender sender;

@PostMapping("/verification-email")
public String sendVerificationEmail(@RequestParam String targetEmail,
HttpSession session) {
SimpleMailMessage message = new SimpleMailMessage();
message.setSubject(EMAIL_TITLE);
int vCode = getVerificationCode();
session.setAttribute("vcode", vCode);
session.setAttribute("uemail", email);

message.setText(EMAIL_CONTEXT + code);
message.setTo(targetEmail);
message.setFrom(EMAIL_SERVEREMAIL); // 与配置文件中的保持一致

sender.send(message);
return "发送成功"; // 前端弹窗可以接受此参数
}

@PostMapping("/register")
public String register(@RequestParam String username,
@RequestParam String email,
@RequestParam String code,
@RequestParam String password,
HttpSession session) {
String sessionCode = session.getAttribute("vcode").toString;
String sessionEmail = session.getAttribute("uemail").toString;

if (sessionCode == null) {
return "验证码为空";
}
if (!sessionCode.equals(code)) {
return "验证码错误!";
}
if (!sessionEmail.equals(email)) {
return "请获取验证码";
}
}
阅读全文 »

Spring Security 初始化

  1. 导入依赖
<dependency>
<groupId>org.springframework.security</groupId>
<artifactId>spring-security-web</artifactId>
<version>6.1.1</version>
</dependency>
<dependency>
<groupId>org.springframework.security</groupId>
<artifactId>spring-security-config</artifactId>
<version>6.1.1</version>
</dependency>
  1. 创建SecurityInitializer
package com.example.init
public class SecurityInitializer extends AbstractSecurityWebApplicationInitializer {
//不用重写任何内容
//这里实际上会自动注册一个Filter,SpringSecurity底层就是依靠N个过滤器实现的,我们之后再探讨
}
  1. 创建配置类
package com.example.config
@Configuration
@EnableWebSecurity //开启WebSecurity相关功能
public class SecurityConfiguration {

}
  1. MainInitializer添加配置文件
@Override
protected Class<?>[] getRootConfigClasses() {
return new Class[]{MainConfiguration.class, SecurityConfiguration.class};
}

Post表单认证

在POST请求中需要携带页面中的csrfToken,否则一律进行拦截操作

<input type="text" th:id="${_csrf.getParameterName()}" th:value="${_csrf.token}" hidden>

密码加密

@Configuration
@EnableWebSecurity
public class SecurityConfiguration {

//将BCryptPasswordEncoder直接注册为Bean,Security会自动进行选择
@Bean
public PasswordEncoder passwordEncoder(){
return new BCryptPasswordEncoder();
}
}

使用

encoder.encode(yourPassword);

关闭CSFR

@Configuration
@EnableWebSecurity
public class SecurityConfiguration {

@Bean
public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
return http
.csfr(conf -> {
// 关闭CSFR
conf.disable();
})
}
}

自定义登录页

@Configuration
@EnableWebSecurity
public class SecurityConfiguration {

@Bean
public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
return http
// 验证请求拦截和放行配置
.authorizeHttpRequests(auth -> {
// 将所有请求全部拦截,一律需要验证
auth.anyRequest().authenticated();
})
// 表单登录相关配置
.formLogin(conf -> {
conf.loginPage("/login"); // 将登录页设置为我们自己的登录页面
conf.loginProcessingUrl("/doLogin"); // 登录表单提交的地址,可以自定义
conf.defaultSuccessUrl("/"); // 登录成功后跳转的页面
conf.permitAll(); // 将登录相关的地址放行,否则未登录的用户无法进入登录界面
// 用户名和密码的表单字段名称
conf.usernameParameter("username");
conf.passwordParameter("password");
})
// 退出登录
.logout(conf -> {
...
})
.build();
}
}

记住密码

@Configuration
@EnableWebSecurity
public class SecurityConfiguration {

@Bean
public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
return http
.rememberMe(conf -> {
conf.alwaysRemember(false);
})

MVC

<dependency>
<groupId>org.springframework</groupId>
<artifactId>spring-webmvc</artifactId>
<version>6.0.10</version>
</dependency>

Controller

页面

@Controller   //直接添加注解即可
public class HelloController {

@RequestMapping("/index") //直接填写访问路径
public ModelAndView index(){
ModelAndView modelAndView = new ModelAndView("index");
modelAndView.getModel().put("arg", "value"); //将name传递给Model
return modelAndView;
//返回后会经过视图解析器进行处理
}

@RequestMapping(value = "/index")
public String index(Model model){ //这里不仅仅可以是Model,还可以是Map、ModelMap
model.addAttribute("arg", "value");
return "index";
}
}

重定向

@RequestMapping("/index")
public String index(){
return "redirect:page";
}

请求转发

@RequestMapping("/index")
public String index(){
return "forward:home";
}

Bean的Web作用域

Bean的作用域:

  1. Singleton
  2. Prototype
  3. Request HTTP请求产生新实例,结束后Bean消失
  4. Session 每一个会话
  5. Global Session

RESTFul

一种设计风格。RESTful风格的设计允许将参数通过URL拼接传到服务端。

http://localhost:8080/mvc/index/13579
@RequestMapping("/index/{str}")
public String index(@PathVariable String str) {
System.out.println(str);
return "index";
}

文件上传

public class MainInitializer extends AbstractAnnotationConfigDispatcherServletInitializer {

...

@Override
protected void customizeRegistration(ServletRegistration.Dynamic registration) {
// 直接通过registration配置Multipart相关配置,必须配置临时上传路径,建议选择方便打开的
// 同样可以设置其他属性:maxFileSize, maxRequestSize, fileSizeThreshold
registration.setMultipartConfig(new MultipartConfigElement("/path/to/save"));
}
}

Controller模板

@RequestMapping(value = "/upload", method = RequestMethod.POST)
@ResponseBody
public String upload(@RequestParam MultipartFile file) throws IOException {
File fileObj = new File("filename.png");
file.transferTo(fileObj);
System.out.println("用户上传的文件已保存到:"+fileObj.getAbsolutePath());
return "文件上传成功!";
}

前端模板

<div>
<form action="upload" method="post" enctype="multipart/form-data">
<input type="file" name="file">
<input type="submit">
</form>
</div>

application.properties

Property形式

server.port=80 // 端口号
aruge.arugement=value
@Value("{argue.argument}")
String argu;

YAML形式

server:
port: 80

spring:
datasource:
url: jdbc:mysql://localhost:3306/db_name
username:
password:
driver-class-name: com.mysql.cj.Driver
mvc:
static-path-pattern: /static/**
security:
filter:
order: -100 # Spring Security Filter 优先级
user:
name: 'admin'
password: 'Abc123.'
roles:
- admin
- user
阅读全文 »

所有的Java云平台都能够使用基于JAR的打包方式,WAR文件只在一些云平台上能够运行。

Pom.xml 更换 Maven 源

<?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 https://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>org.springframework.quoters</groupId>
<artifactId>quoters-incorporated</artifactId>
<version>0.0.1-SNAPSHOT</version>
<packaging>jar</packaging>

<name>quoters-incorporated</name>
<description>REST service to support the guides</description>

<developers>
<developer>
<id>gturnquist</id>
<name>Greg Turnquist</name>
<email>gturnquist at vmware.com</email>
<organization>VMware, Inc.</organization>
<roles>
<role>Project Lead</role>
</roles>
</developer>
</developers>

<organization>
<name>VMware, Inc.</name>
<url>https://spring.io</url>
</organization>

<licenses>
<license>
<name>Apache License, Version 2.0</name>
<url>https://www.apache.org/licenses/LICENSE-2.0</url>
<comments>
Copyright 2011 the original author or authors.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
See the License for the specific language governing permissions and
limitations under the License.
</comments>
</license>
</licenses>

<parent>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-parent</artifactId>
<version>2.7.5</version>
<relativePath/> <!-- lookup parent from repository -->
</parent>

<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
<java.version>1.8</java.version>
</properties>

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

<dependency>
<groupId>com.h2database</groupId>
<artifactId>h2</artifactId>
<scope>runtime</scope>
</dependency>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-test</artifactId>
<scope>test</scope>
</dependency>
</dependencies>

<!-- 配置阿里云仓库 -->
<repositories>
<repository>
<id>aliyun-repos</id>
<url>https://maven.aliyun.com/repository/public</url>
<releases>
<enabled>true</enabled>
</releases>
<snapshots>
<enabled>false</enabled>
</snapshots>
</repository>
</repositories>
<pluginRepositories>
<pluginRepository>
<id>aliyun-repos</id>
<url>https://maven.aliyun.com/repository/public</url>
<releases>
<enabled>true</enabled>
</releases>
<snapshots>
<enabled>false</enabled>
</snapshots>
</pluginRepository>
</pluginRepositories>

<build>
<plugins>
<plugin>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-maven-plugin</artifactId>
</plugin>
</plugins>
</build>

</project>

Tight Coupling 紧耦合

在Spring框架以前,使用排序算法需要将算法实例化

public class ComplexBusinessService {
SortAlgorithm sortAlgorithm = new BubbleSortAlgorithm;
}
public class BubbleSortAlgorithm implements SortAlgorithm {...}

Good code has loose coupling.

移除依赖项的实例化可以移除紧耦合

public class ComplexBusinessService {
SortAlgorithm sortAlgorithm; // = new BubbleSortAlgorithm();

public ComplexBusinessService(SortAlgorithm sortAlgorithm) { // 创建构造函数
this.sortAlgorithm = sortAlgorithm;
}

public classBubbleSortAlgorithm implements SortAlgorithm {...}

Spring Framework instantiates objects and populates the dependencies.

阅读全文 »
0%