Home - JAVA 牛牛

一、参数校验

在开发中经常需要写一些字段校验的代码，比如字段非空，字段长度限制，邮箱格式验证等等，写这些与业务逻辑关系不大的代码个人感觉有两个麻烦：

验证代码繁琐，重复劳动
方法内代码显得冗长
每次要看哪些参数验证是否完整，需要去翻阅验证逻辑代码 hibernate validator （官方文档）提供了一套比较完善、便捷的验证实现方式。

spring-boot-starter-web包里面有hibernate-validator包，不需要引用hibernate validator依赖。

二、hibernate validator校验demo

先来看一个简单的demo，添加了Validator的注解：

import org.hibernate.validator.constraints.NotBlank;

import javax.validation.constraints.AssertFalse;
import javax.validation.constraints.Pattern;
复制代码
@Getter
@Setter
@NoArgsConstructor
public class DemoModel {
    @NotBlank(message="用户名不能为空")
    private String userName;

    @NotBlank(message="年龄不能为空")
    @Pattern(regexp="^[0-9]{1,2}$",message="年龄不正确")
    private String age;

    @AssertFalse(message = "必须为false")
    private Boolean isFalse;
    /**
     * 如果是空，则不校验，如果不为空，则校验
     */
    @Pattern(regexp="^[0-9]{4}-[0-9]{2}-[0-9]{2}$",message="出生日期格式不正确")
    private String birthday;
}

POST接口验证，BindingResult是验证不通过的结果集合：

    @RequestMapping("/demo2")
    public void demo2(@RequestBody @Valid DemoModel demo, BindingResult result){
        if(result.hasErrors()){
            for (ObjectError error : result.getAllErrors()) {
                System.out.println(error.getDefaultMessage());
            }
        }
    }

POST请求传入的参数：{“userName”:”dd”,”age”:120,”isFalse”:true,”birthday”:”21010-21-12”}

输出结果：

出生日期格式不正确
必须为false
年龄不正确

参数验证非常方便，字段上注解+验证不通过提示信息即可代替手写一大堆的非空和字段限制验证代码。下面深入了解下参数校验的玩法。

三、hibernate的校验模式

细心的读者肯定发现了：上面例子中一次性返回了所有验证不通过的集合，通常按顺序验证到第一个字段不符合验证要求时，就可以直接拒绝请求了。Hibernate Validator有以下两种验证模式：

返回目录

1、普通模式（默认是这个模式）

普通模式(会校验完所有的属性，然后返回所有的验证失败信息)

2、快速失败返回模式

快速失败返回模式(只要有一个验证失败，则返回)

两种验证模式配置方式：（参考官方文档）

failFast：true 快速失败返回模式 false 普通模式

ValidatorFactory validatorFactory = Validation.byProvider( HibernateValidator.class )
        .configure()
        .failFast( true )
        .buildValidatorFactory();
Validator validator = validatorFactory.getValidator();

和（hibernate.validator.fail_fast：true 快速失败返回模式 false 普通模式）

ValidatorFactory validatorFactory = Validation.byProvider( HibernateValidator.class )
        .configure()
        .addProperty( "hibernate.validator.fail_fast", "true" )
        .buildValidatorFactory();
Validator validator = validatorFactory.getValidator();

四、hibernate的两种校验

配置hibernate Validator为快速失败返回模式：

@Configuration
public class ValidatorConfiguration {
    @Bean
    public Validator validator(){
        ValidatorFactory validatorFactory = Validation.byProvider( HibernateValidator.class )
                .configure()
                .addProperty( "hibernate.validator.fail_fast", "true" )
                .buildValidatorFactory();
        Validator validator = validatorFactory.getValidator();

        return validator;
    }
}

1、请求参数校验

如demo里示例的，验证请求参数时，在@RequestBody DemoModel demo之间加注解 @Valid，然后后面加BindindResult即可；多个参数的，可以加多个@Valid和BindingResult，如：

public void test()(@RequestBody @Valid DemoModel demo, BindingResult result)

public void test()(@RequestBody @Valid DemoModel demo, BindingResult result,@RequestBody @Valid DemoModel demo2, BindingResult result2)

    @RequestMapping("/demo2")
    public void demo2(@RequestBody @Valid DemoModel demo, BindingResult result){
        if(result.hasErrors()){
            for (ObjectError error : result.getAllErrors()) {
                System.out.println(error.getDefaultMessage());
            }
        }
    }

2、GET参数校验(@RequestParam参数校验)

使用校验bean的方式，没有办法校验RequestParam的内容，一般在处理Get请求(或参数比较少)的时候，会使用下面这样的代码：

    @RequestMapping(value = "/demo3", method = RequestMethod.GET)
    public void demo3(@RequestParam(name = "grade", required = true) int grade,@RequestParam(name = "classroom", required = true) int classroom) {
        System.out.println(grade + "," + classroom);
    }

使用@Valid注解，对RequestParam对应的参数进行注解，是无效的，需要使用@Validated注解来使得验证生效。如下所示：

a.此时需要使用MethodValidationPostProcessor 的Bean：

    @Bean
    public MethodValidationPostProcessor methodValidationPostProcessor() {
　　　　  /**默认是普通模式，会返回所有的验证不通过信息集合*/
        return new MethodValidationPostProcessor();
    }

或可对MethodValidationPostProcessor 进行设置Validator（因为此时不是用的Validator进行验证，Validator的配置不起作用）

    @Bean
    public MethodValidationPostProcessor methodValidationPostProcessor() {
        MethodValidationPostProcessor postProcessor = new MethodValidationPostProcessor();
　　　　　/**设置validator模式为快速失败返回*/
        postProcessor.setValidator(validator());
        return postProcessor;
    }

    @Bean
    public Validator validator(){
        ValidatorFactory validatorFactory = Validation.byProvider( HibernateValidator.class )
                .configure()
                .addProperty( "hibernate.validator.fail_fast", "true" )
                .buildValidatorFactory();
        Validator validator = validatorFactory.getValidator();

        return validator;
    }

b.方法所在的Controller上加注解@Validated

@RequestMapping("/validation")
@RestController
@Validated
public class ValidationController {
    /**如果只有少数对象，直接把参数写到Controller层，然后在Controller层进行验证就可以了。*/
    @RequestMapping(value = "/demo3", method = RequestMethod.GET)
    public void demo3(@Range(min = 1, max = 9, message = "年级只能从1-9")
                      @RequestParam(name = "grade", required = true)
                      int grade,
                      @Min(value = 1, message = "班级最小只能1")
                      @Max(value = 99, message = "班级最大只能99")
                      @RequestParam(name = "classroom", required = true)
                      int classroom) {
        System.out.println(grade + "," + classroom);
    }
}

c.返回验证信息提示

可以看到：验证不通过时，抛出了ConstraintViolationException异常，使用同一捕获异常处理：

@ControllerAdvice
@Component
public class GlobalExceptionHandler {

    @ExceptionHandler
    @ResponseBody
    @ResponseStatus(HttpStatus.BAD_REQUEST)
    public String handle(ValidationException exception) {
        if(exception instanceof ConstraintViolationException){
            ConstraintViolationException exs = (ConstraintViolationException) exception;

            Set<ConstraintViolation<?>> violations = exs.getConstraintViolations();
            for (ConstraintViolation<?> item : violations) {
　　　　　　　　　　/**打印验证不通过的信息*/
                System.out.println(item.getMessage());
            }
        }
        return "bad request, " ;
    }
}

d.验证

浏览器服务请求地址：http://localhost:8080/validation/demo3?grade=18&classroom=888

没有配置快速失败返回的MethodValidationPostProcessor 时输出信息如下：

年级只能从1-9
班级最大只能99

配置了快速失败返回的MethodValidationPostProcessor 时输出信息如下：

年级只能从1-9

浏览器服务请求地址：http://localhost:8080/validation/demo3?grade=0&classroom=0

没有配置快速失败返回的MethodValidationPostProcessor 时输出信息如下：

年级只能从1-9
班级最小只能1

配置了快速失败返回的MethodValidationPostProcessor 时输出信息如下：

年级只能从1-9

3、model校验

待校验的model：

@Data
public class Demo2 {
    @Length(min = 5, max = 17, message = "length长度在[5,17]之间")
    private String length;

    /**@Size不能验证Integer，适用于String, Collection, Map and arrays*/
    @Size(min = 1, max = 3, message = "size在[1,3]之间")
    private String age;

    @Range(min = 150, max = 250, message = "range在[150,250]之间")
    private int high;

    @Size(min = 3,max = 5,message = "list的Size在[3,5]")
    private List<String> list;
}

验证model，以下全部验证通过：

    @Autowired
    private Validator validator;

    @RequestMapping("/demo3")
    public void demo3(){
        Demo2 demo2 = new Demo2();
        demo2.setAge("111");
        demo2.setHigh(150);
        demo2.setLength("ABCDE");
        demo2.setList(new ArrayList<String>()\{\{add("111");add("222");add("333");}});
        Set<ConstraintViolation<Demo2>> violationSet = validator.validate(demo2);
        for (ConstraintViolation<Demo2> model : violationSet) {
            System.out.println(model.getMessage());
        }
    }

4、对象级联校验

对象内部包含另一个对象作为属性，属性上加@Valid，可以验证作为属性的对象内部的验证：（验证Demo2示例时，可以验证Demo2的字段）

@Data
public class Demo2 {
    @Size(min = 3,max = 5,message = "list的Size在[3,5]")
    private List<String> list;

    @NotNull
    @Valid
    private Demo3 demo3;
}

@Data
public class Demo3 {
    @Length(min = 5, max = 17, message = "length长度在[5,17]之间")
    private String extField;
}

级联校验：

    /**前面配置了快速失败返回的Bean*/
    @Autowired
    private Validator validator;

    @RequestMapping("/demo3")
    public void demo3(){
        Demo2 demo2 = new Demo2();
        demo2.setList(new ArrayList<String>()\{\{add("111");add("222");add("333");}});

        Demo3 demo3 = new Demo3();
        demo3.setExtField("22");
        demo2.setDemo3(demo3);
        Set<ConstraintViolation<Demo2>> violationSet = validator.validate(demo2);
        for (ConstraintViolation<Demo2> model : violationSet) {
            System.out.println(model.getMessage());
        }
    }

可以校验Demo3的extField字段。

5、分组校验

结论：分组顺序校验时，按指定的分组先后顺序进行验证，前面的验证不通过，后面的分组就不行验证。

有这样一种场景，新增用户信息的时候，不需要验证userId（因为系统生成）；修改的时候需要验证userId，这时候可用用户到validator的分组验证功能。

设置validator为普通验证模式（”hibernate.validator.fail_fast”, “false”），用到的验证GroupA、GroupB和model：

GroupA、GroupB：

public interface GroupA {
}

public interface GroupB {
}

验证model：Person

@Data
public class Person {
    @NotBlank
    @Range(min = 1,max = Integer.MAX_VALUE,message = "必须大于0",groups = {GroupA.class})
    /**用户id*/
    private Integer userId;
    @NotBlank
    @Length(min = 4,max = 20,message = "必须在[4,20]",groups = {GroupB.class})
    /**用户名*/
    private String userName;
    @NotBlank
    @Range(min = 0,max = 100,message = "年龄必须在[0,100]",groups={Default.class})
    /**年龄*/
    private Integer age;
    @Range(min = 0,max = 2,message = "性别必须在[0,2]",groups = {GroupB.class})
    /**性别 0：未知；1：男；2：女*/
    private Integer sex;
}

如上Person所示，3个分组分别验证字段如下：

GroupA验证字段userId；
GroupB验证字段userName、sex；
Default验证字段age(Default是Validator自带的默认分组)

a、分组

只验证GroupA、GroupB标记的分组：

@RequestMapping("/demo5")
public void demo5(){
    Person p = new Person();
    /**GroupA验证不通过*/
    p.setUserId(-12);
    /**GroupA验证通过*/
    //p.setUserId(12);
    p.setUserName("a");
    p.setAge(110);
    p.setSex(5);
    Set<ConstraintViolation<Person>> validate = validator.validate(p, GroupA.class, GroupB.class);
    for (ConstraintViolation<Person> item : validate) {
        System.out.println(item);
    }
}

或

    @RequestMapping("/demo6")
    public void demo6(@Validated({GroupA.class, GroupB.class}) Person p, BindingResult result){
        if(result.hasErrors()){
            List<ObjectError> allErrors = result.getAllErrors();
            for (ObjectError error : allErrors) {
                System.out.println(error);
            }
        }
    }

GroupA、GroupB、Default都验证不通过的情况：

验证信息如下所示：

ConstraintViolationImpl{interpolatedMessage='必须在[4,20]', propertyPath=userName, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='必须在[4,20]'}
ConstraintViolationImpl{interpolatedMessage='必须大于0', propertyPath=userId, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='必须大于0'}
ConstraintViolationImpl{interpolatedMessage='性别必须在[0,2]', propertyPath=sex, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='性别必须在[0,2]'}

GroupA验证通过、GroupB、Default验证不通过的情况：

验证信息如下所示：

ConstraintViolationImpl{interpolatedMessage='必须在[4,20]', propertyPath=userName, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='必须在[4,20]'}
ConstraintViolationImpl{interpolatedMessage='性别必须在[0,2]', propertyPath=sex, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='性别必须在[0,2]'}

b、组序列

除了按组指定是否验证之外，还可以指定组的验证顺序，前面组验证不通过的，后面组不进行验证：

指定组的序列（GroupA》GroupB》Default）：

@GroupSequence({GroupA.class, GroupB.class, Default.class})
public interface GroupOrder {
}

测试demo：

    @RequestMapping("/demo7")
    public void demo7(){
        Person p = new Person();
        /**GroupA验证不通过*/
        //p.setUserId(-12);
        /**GroupA验证通过*/
        p.setUserId(12);
        p.setUserName("a");
        p.setAge(110);
        p.setSex(5);
        Set<ConstraintViolation<Person>> validate = validator.validate(p, GroupOrder.class);
        for (ConstraintViolation<Person> item : validate) {
            System.out.println(item);
        }
    }

或

    @RequestMapping("/demo8")
    public void demo8(@Validated({GroupOrder.class}) Person p, BindingResult result){
        if(result.hasErrors()){
            List<ObjectError> allErrors = result.getAllErrors();
            for (ObjectError error : allErrors) {
                System.out.println(error);
            }
        }
    }

GroupA、GroupB、Default都验证不通过的情况：

验证信息如下所示：

ConstraintViolationImpl{interpolatedMessage='必须大于0', propertyPath=userId, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='必须大于0'}

GroupA验证通过、GroupB、Default验证不通过的情况：

验证信息如下所示：

ConstraintViolationImpl{interpolatedMessage='必须在[4,20]', propertyPath=userName, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='必须在[4,20]'}
ConstraintViolationImpl{interpolatedMessage='性别必须在[0,2]', propertyPath=sex, rootBeanClass=class validator.demo.project.model.Person, messageTemplate='性别必须在[0,2]'}

结论：分组顺序校验时，按指定的分组先后顺序进行验证，前面的验证不通过，后面的分组就不行验证。

五、自定义验证器

一般情况，自定义验证可以解决很多问题。但也有无法满足情况的时候，此时，我们可以实现validator的接口，自定义自己需要的验证器。

如下所示，实现了一个自定义的大小写验证器：

public enum CaseMode {
    UPPER,
    LOWER;
}


@Target( { ElementType.METHOD, ElementType.FIELD, ElementType.ANNOTATION_TYPE })
@Retention(RetentionPolicy.RUNTIME)
@Constraint(validatedBy = CheckCaseValidator.class)
@Documented
public @interface CheckCase {
    String message() default "";

    Class<?>[] groups() default {};

    Class<? extends Payload>[] payload() default {};

    CaseMode value();
}


public class CheckCaseValidator implements ConstraintValidator<CheckCase, String> {
    private CaseMode caseMode;
    public void initialize(CheckCase checkCase) {
        this.caseMode = checkCase.value();
    }

    public boolean isValid(String s, ConstraintValidatorContext constraintValidatorContext) {
        if (s == null) {
            return true;
        }

        if (caseMode == CaseMode.UPPER) {
            return s.equals(s.toUpperCase());
        } else {
            return s.equals(s.toLowerCase());
        }
    }
}

要验证的Model：

    public class Demo{
        @CheckCase(value = CaseMode.LOWER,message = "userName必须是小写")
        private String userName;

        public String getUserName() {
            return userName;
        }

        public void setUserName(String userName) {
            this.userName = userName;
        }
    }

validator配置：

    @Bean
    public Validator validator(){
        ValidatorFactory validatorFactory = Validation.byProvider( HibernateValidator.class )
                .configure()
                .addProperty( "hibernate.validator.fail_fast", "true" )
                .buildValidatorFactory();
        Validator validator = validatorFactory.getValidator();

        return validator;
    }

验证测试：

    @RequestMapping("/demo4")
    public void demo4(){
        Demo demo = new Demo();
        demo.setUserName("userName");
        Set<ConstraintViolation<Demo>> validate = validator.validate(demo);
        for (ConstraintViolation<Demo> dem : validate) {
            System.out.println(dem.getMessage());
        }
    }

输出结果：

userName必须是小写

六、常见的注解

  Bean Validation 中内置的 constraint     
@Null   被注释的元素必须为 null     
@NotNull    被注释的元素必须不为 null     
@AssertTrue     被注释的元素必须为 true     
@AssertFalse    被注释的元素必须为 false     
@Min(value)     被注释的元素必须是一个数字，其值必须大于等于指定的最小值     
@Max(value)     被注释的元素必须是一个数字，其值必须小于等于指定的最大值     
@DecimalMin(value)  被注释的元素必须是一个数字，其值必须大于等于指定的最小值     
@DecimalMax(value)  被注释的元素必须是一个数字，其值必须小于等于指定的最大值     
@Size(max=, min=)   被注释的元素的大小必须在指定的范围内     
@Digits (integer, fraction)     被注释的元素必须是一个数字，其值必须在可接受的范围内     
@Past   被注释的元素必须是一个过去的日期     
@Future     被注释的元素必须是一个将来的日期     
@Pattern(regex=,flag=)  被注释的元素必须符合指定的正则表达式     
Hibernate Validator 附加的 constraint     
@NotBlank(message =)   验证字符串非null，且长度必须大于0     
@Email  被注释的元素必须是电子邮箱地址     
@Length(min=,max=)  被注释的字符串的大小必须在指定的范围内     
@NotEmpty   被注释的字符串的必须非空     
@Range(min=,max=,message=)  被注释的元素必须在合适的范围内

//大于0.01，不包含0.01
@NotNull
@DecimalMin(value = "0.01", inclusive = false)
private Integer greaterThan;

//大于等于0.01
@NotNull
@DecimalMin(value = "0.01", inclusive = true)
private BigDecimal greatOrEqualThan;

@Length(min = 1, max = 20, message = "message不能为空")
//不能将Length错用成Range
//@Range(min = 1, max = 20, message = "message不能为空")
private String message;

难度：简单
本题涉及算法： 排序 哈希表 摩尔投票法思路
思路： 排序 哈希表 摩尔投票法思路
类似题型:
- 229. 求众数 II

题目 169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ` n/2 ` 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

方法一

解题思路

一定会出现多数元素，则说明，在排序后，中间位置一定是该元素
时间复杂度 $O(logn)$ 空间复杂度 $O(nlogn)$

代码

python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

java

public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

方法二哈希表

通过使用哈希表保存所有元素出现的次
在哈希表中找出出现大于 n/2 的数
时间复杂度 $O(n)$ 空间复杂度 $O(n)$

java

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> cmap = new HashMap<>();
        for(int i:nums){
            if (cmap.containsKey(i)) {
               int v=  cmap.get(i)+1;
               cmap.put(i,v);
            }else {
                cmap.put(i,1);
            }
        }
        for(Map.Entry entry:cmap.entrySet()) {
            if((int)entry.getValue()>nums.length/2){
                return (int)entry.getKey();
            }
        }
        return 0;
    }
}

python

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
        for i in nums:
            if dic.get(i):
                v = dic.values()
                dic[i]+=1
            else:
                dic[i]=1
        for di in dic:
            if dic.get(di)>(len(nums)/2):
                return di

方法三摩尔投票法思路 (投票法)

候选人(cand_num)初始化为 nums[0]，票数 count 初始化为1。
当遇到与 cand_num 相同的数，则票数 count = count + 1 ，否则票数 count = count - 1。
当票数 count 为0时，更换候选人，并将票数 count 重置为1。
遍历完数组后，cand_num 即为最终答案。

为何这行得通呢？

投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。
因此“多数元素”的个数 - 其余元素的个数总和的结果肯定 >= 1。
这就相当于每个“多数元素”和其他元素两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。

无论数组是 1 2 1 2 1，亦或是 1 2 2 1 1，总能得到正确的候选人。

java

class Solution {
    public int majorityElement(int[] nums) {
        int cand_num = nums[0], count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i])
                ++count;
            else if (--count == 0) { // 很鸡贼的一段代码 --count 是不是等于 0， 先减1 在说
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
}

难度：简单
本题涉及算法： 动态规划 递归
思路： 动态规划 递归
类似题型:

题目面试题 17.16. 按摩师

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

示例

示例 1：

输入： [1,2,3,1]   
输出： 4   
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

输入： [2,7,9,3,1]   
输出： 12    
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。   

示例 3：

输入： [2,1,4,5,3,1,1,3]   
输出： 12    
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。   

解题思路

根据条件可知只能找不相邻的两个数
假设 opt[i] 表示到下标为 i 的最佳方案
选择下标为 i 的方案 opt[i-2] + arr[i]
不选择下标为 i 的方案 opt[i]
再比较这两个的大小
找出口 - 当数组 arr 只有一个数字的时候最大数 opt[0] = arr[0] - 当数组 arr 有两个数字的时候最大数 opt[1] = max(arr[0],arr[1])

根据思路可推到出公式

\[opt(i)=\begin{cases} arr[0] & i = 0 \\ max(arr[0],arr[1]) & i = 1 \\ \end{cases}\] \[opt(i)=max=\begin{cases} opt[i-2]+ arr[i] & 选择 \\ opt[i-1] & 不选 \\ \end{cases}\]

代码一维数组

递归的时间复杂度是 $O(n)$

python

class Solution:
  def massage(self, nums: List[int]) -> int:

      lenNums = len(nums)
      if nums == None or lenNums ==0:
          return 0
      opt = [0] * lenNums
      if lenNums == 1:
          return nums[0]
      if lenNums == 2:
          return max(nums[0],nums[1])
      opt[0] = nums[0]
      opt[1] = max(nums[0],nums[1])
      for i in range(2,lenNums):
          a = opt[i-2] + nums[i]
          b = opt[i-1]
          opt[i] = max(a,b)
      return opt[lenNums-1]

java

public class Solution {

  public int massage(int[] nums) {
      int len = nums.length;
      if (len == 0) {
          return 0;
      }
      if (len == 1) {
          return nums[0];
      }
      int[] opt = new int[len];
      opt[0] = nums[0];
      opt[1] = Math.max(nums[0],nums[1]);
      for(int i = 2;i<len;i++) {
          int a = opt[i-2] + nums[i];
          int b = opt[i-1];
          opt[i] = Math.max(a,b);
      }
      return opt[len-1];
  }
}

方法二递归

递归的时间复杂度是 $O(n^2)$
(该方法会超时，只是多提供一个思路)

class Solution:
    def massage(self, nums: List[int]) -> int:
        lenNums = len(nums)
        if nums == None or lenNums ==0:
            return 0
        return self.opt(nums,lenNums-1)

    def opt(self,nums,lenNums):
        if lenNums == 0 :
            return nums[0]
        elif lenNums == 1 :
            return max(nums[0],nums[1])
        else:
            a = self.opt(nums,lenNums-2) + nums[lenNums] # 选择nums[i]
            b = self.opt(nums,lenNums-1) # 不选nums[i]
            return max(a,b)

ArrayList 和 ArrayList 是Java集合框架中经常使用的类。如果你只知道从基本性能比较 ArrayList 和 ArrayList ，那么请仔细阅读这篇文章。 ArrayList 应该在需要更多搜索操作的地方使用，并且 ArrayList 应该在需要更多插入和删除操作的地方使用。

ArrayList 使用 Array 数据结构， ArrayList 使用 DoublyArrayList 数据结构。在这里，我们要讨论基础数据结构如何影响插入，搜索的性能，以及删除操作 ArrayList 和 ArrayList 。下面是使用 ArrayList 和 LinkedList 不同操作的示例:下面我们将比较 ArrayList 和 LinkedList 的操作，看哪一个在性能方面更有效。

在最后索引处插入值（块1和2）

当我们在最后一个索引处插入一个值时， ArrayList 必须：

检查基础数组是否已满。
如果数组已满，则将数据从旧数组复制到新数组（大小比旧数组大两倍），
然后在最后一个索引处添加值。

另一方面， LinkedList 只是在底层 DoublyLinkedList 的尾部添加该值。

两者都具有时间复杂度O（1），但是由于在 ArrayList 中创建新数组的附加步骤，其最坏情况复杂度达到N的顺序，这就是为什么我们更喜欢使用 LinkedList .

在给定指数处插入值（第3和第4块）

当我们在给定索引处插入值时，ArrayList必须 :

检查基础数组是否已满。
如果数组已满，则将数据从旧数组复制到新数组（大小为旧数组的两倍）。
之后，从给定索引开始，将值移动一个索引以为新值创建空间。
然后在给定索引处添加值。

另一方面， LinkedList 只是通过重新排列底层 DoublyLinkedList 的指针来查找索引并在给定索引处添加该值。

两者都具有时间复杂度O（N），但是由于在 ArrayList 中创建新数组并将现有值复制到新索引的附加步骤，我们更喜欢使用LinkedList.

按值搜索（第5和第6块）

当我们在 ArrayList 或LinkedList中搜索任何值时，我们必须遍历所有元素。该操作具有O（N）时间复杂度。看起来像 ArrayList 和LinkedList都具有相同的性能。

这里我们需要注意的是，数组（ ArrayList 的底层数据结构）将所有值存储在连续的内存位置，但是 DoublyArrayList 将每个节点存储在一个随机的内存位置。迭代连续内存位置比随机内存位置更具性能效率，这就是为什么我们在按值搜索时更喜欢使用 ArrayList 而不是 ArrayList 。

按索引获取元素（第7和第8块）

当我们通过Index获得元素时， ArrayList 是一个明显效果更好。

ArrayList 可以为您提供O（1）复杂度的任何元素，因为该数组具有随机访问属性。您可以直接访问任何索引而无需遍历整个数组。

ArrayList 具有顺序访问属性。它需要迭代每个元素以达到给定的索引，因此从 ArrayList 通过索引获取值的时间复杂度是O（N）。

按值删除（块9和10）

它类似于在给定索引处添加值。要在 ArrayList 和 ArrayList 中按值删除元素，我们需要迭代每个元素以到达该索引，然后删除该值。该操作具有O（N）复杂度。

不同的是，要从 ArrayList 中删除一个元素，我们只需要修改指针，但是在 ArrayList 中，我们需要在删除值的索引之后移动所有元素以填充创建的间隙。

由于移位是昂贵的操作然后修改指针，因此即使在相同的总体复杂度O（N）之后，我们更喜欢 ArrayList ，其中需要更多按值操作删除。

按索引删除（第11和12栏）

为了通过索引删除， ArrayList 使用O（1）复杂度中的随机访问来查找该索引，但是在移除元素之后，移位其余元素会导致整体O（N）时间复杂度。

另一方面， ArrayList 花费O（N）时间来使用顺序访问来查找索引，但是要删除元素，我们只需要修改指针。

由于移位是比迭代更昂贵的操作，因此如果我们想要逐个删除元素， ArrayList 会更有效。

难度：简单
本题涉及算法： 数组 快慢指针 单指针法
思路： 数组 快慢指针 单指针法
类似题型:
- 202. 快乐数

题目 876. 链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例

示例 1：

输入：[1,2,3,4,5]    
输出：此列表中的结点 3 (序列化形式：[3,4,5])    
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。   
注意，我们返回了一个 ListNode 类型的对象 ans，这样：   
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]    
输出：此列表中的结点 4 (序列化形式：[4,5,6])    
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。    

提示：

给定链表的结点数介于 1 和 100 之间。

方法一：数组

解题思路

根据题目所说的链表长度最长为100，则可以遍历入参的链表，从 0 开始记录当 head.next = null 是即是链表的长度，通过 A[N/2] 拿到中间数据
链表的缺点在于不能通过下标访问对应的元素。因此我们可以考虑对链表进行遍历，同时将遍历到的元素依次放入数组 A 中。如果我们遍历到了 N 个元素，那么链表以及数组的长度也为 N，对应的中间节点即为 A[N/2]。
这里想说的是，把数组放在空数组(空数组长度> 传入数组)里，再去拿到指定位置的数据，还是第一次看到
java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }
}

方法二快慢指针

思路：快指针q每次走2步，慢指针p每次走1步，当q走到末尾时p正好走到中间。

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) { // 对链表个数 奇偶的判断
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast  and fast.next :
            fast = fast.next.next
            slow = slow.next
        return slow

方法三单指针法

遍历获取链表的长度 n
在遍历直到 n/2 的位置
python

```python

class Solution: def middleNode(self, head: ListNode) -> ListNode: n, cur = 0, head while cur: n += 1 cur = cur.next k, cur = 0, head while k < n // 2: k += 1 cur = cur.next return cur ```

难度：简单
本题涉及算法： 数组
思路： 数组
类似题型:

题目按既定顺序创建目标数组

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：

目标数组 target 最初为空。
按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
重复上一步，直到在 nums 和 index 中都没有要读取的元素。请你返回目标数组。

题目保证数字插入位置总是存在。

示例

示例 1：

输入：nums = [0,1,2,3,4], index = [0,1,2,2,1]    
输出：[0,4,1,3,2]    
解释：   
nums       index     target   
0            0        [0]   
1            1        [0,1]   
2            2        [0,1,2]   
3            2        [0,1,3,2]   
4            1        [0,4,1,3,2]

示例 2：

输入：nums = [1,2,3,4,0], index = [0,1,2,3,0]    
输出：[0,1,2,3,4]    
解释：   
nums       index     target   
1            0        [1]   
2            1        [1,2]       
3            2        [1,2,3]   
4            3        [1,2,3,4]   
0            0        [0,1,2,3,4]   

示例 3：

输入：nums = [1], index = [0]    
输出：[1]    

方法一

解题思路

python 数组的 insert 方法可以指定位置插入数据，且元数据后移一位，在java中 listArray.add 同样的功能

代码

第一版需要另外开辟空间

1
2
3
4
5
6
class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        res = []
        for i in range(len(nums)):
            res.insert(index[i], nums.[i])
        return res

第二版需要另外开辟空间

1
2
3
4
class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums.insert(index[i], nums.pop(i))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public lass Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        // 用于在列表的指定位置插入指定元素，并将当前处于该位置的元素及其后续元素的索引加 1
        List<Integer> list = new ArrayList<>();
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i>=index.length) {
                break;
            }
            list.add(index[i],nums[i]);
        }
        for (int j=0;j<list.size();j++) {
            res[j]=list.get(j);
        }
        return res;

    }
}

难度：简单
本题涉及算法： 暴力 二分查找
思路： 暴力 二分查找
类似题型:

题目两个数组间的距离值

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的距离值。

「距离值」定义为符合此描述的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 \|arr1[i]-arr2[j]\| <= d 。

示例

示例 1：

输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2   
输出：2    
解释：   
对于 arr1[0]=4 我们有：   
|4-10|=6 > d=2    
|4-9|=5 > d=2   
|4-1|=3 > d=2   
|4-8|=4 > d=2   
对于 arr1[1]=5 我们有：   
|5-10|=5 > d=2    
|5-9|=4 > d=2   
|5-1|=4 > d=2   
|5-8|=3 > d=2   
对于 arr1[2]=8 我们有：   
|8-10|=2 <= d=2   
|8-9|=1 <= d=2    
|8-1|=7 > d=2   
|8-8|=0 <= d=2   

示例 2：

输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3   
输出：2  

示例 3：

输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6    
输出：1  

方法一暴力循环

java

public class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int res = 0;
        a: for (int i=0;i<arr1.length;i++) {
            for (int j=0;j<arr2.length;j++) {
                if (Math.abs(arr1[i] -arr2[j])<=d) {
                    continue a;
                }
            }
            res++;
        }

        return res;
    }
}

python

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        res = 0
        for num in arr1:
            if all([abs(num - num2) > d for num2 in arr2]):
                res +=1
        return res

方法二二分查找

在上一种方法中，要知道是否每一个 $y_j$ 是不是满足 $|x_i - y_j| > d$ ，我们枚举了所有 $y_j$ 。实际上我们只要找到大于等于 $x_i$ 的第一个 $y_j$ 和小于 $x$ 的第一个 $y_j$，看看它们满不满足这个性质就可以了。

我们可以对 arr2 进行排序，然后对于 arr1 中的每个元素 $x_i$ 在 arr2 中二分寻找上述的两个 $y_j$ 如果这两个元素满足性质，则所有元素都满足性质，将答案增加 11。

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        cnt = 0
        for x in arr1:
            p = bisect.bisect_left(arr2, x)
            if p == len(arr2) or abs(x - arr2[p]) > d:
                if p == 0 or abs(x - arr2[p - 1]) > d:
                    cnt += 1
        return cnt

webstorm项目运行到apache服务器

339 post articles, 43 pages.

一、参数校验

二、hibernate validator校验demo

三、hibernate的校验模式

1、普通模式（默认是这个模式）

2、快速失败返回模式

四、hibernate的两种校验

1、请求参数校验

2、GET参数校验(@RequestParam参数校验)

a.此时需要使用MethodValidationPostProcessor 的Bean：

b.方法所在的Controller上加注解@Validated

c.返回验证信息提示

d.验证

3、model校验

4、对象级联校验

5、分组校验

a、分组

b、组序列

五、自定义验证器

六、常见的注解

题目 169. 多数元素

示例

示例 1:

示例 2:

方法一

解题思路

代码

python

java

方法二 哈希表

java

python

方法三 摩尔投票法思路 (投票法)

为何这行得通呢？

java

题目 面试题 17.16. 按摩师

示例

示例 1：

示例 2：

示例 3：

解题思路

代码 一维数组

python

java

方法二 递归

在最后索引处插入值（块1和2）

在给定指数处插入值（第3和第4块）

按值搜索（第5和第6块）

按索引获取元素（第7和第8块）

按值删除（块9和10）

按索引删除（第11和12栏）

题目 876. 链表的中间结点

示例

示例 1：

示例 2：

提示：

方法一：数组

解题思路

java

方法二 快慢指针

java

python

方法三 单指针法

python

题目 按既定顺序创建目标数组

示例

示例 1：

示例 2：

示例 3：

方法一

解题思路

代码

题目 两个数组间的距离值

示例

示例 1：

示例 2：

示例 3：

方法一 暴力循环

java

python

方法二 二分查找

方法二哈希表

方法三摩尔投票法思路 (投票法)

题目面试题 17.16. 按摩师

代码一维数组

方法二递归

方法二快慢指针

方法三单指针法

题目按既定顺序创建目标数组

题目两个数组间的距离值

方法一暴力循环

方法二二分查找