LC题解-重复的子字符串-KML算法

解题思路

  • KML算法，计算最长相当前后缀长度，字符串长度减最长相当前后缀长度即为最小的重复字符串，字符串长度余最小重复字符串长度为0则说明字符串为重复字符串
  • 将字符串相加，同时掐头去尾2个，如果新字符串包含原字符串，则说明字符串是重复字符串

KML 解题源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean repeatedSubstringPattern(String s) {
    if (s == null || s == "" || s.length() == 1) {
        return false;
    }
    int[] next = getNext(s);
    int preNextLen = next[next.length - 1];
    return preNextLen > 0 && next.length % (next.length - preNextLen) == 0;
}

private int[] getNext(String s) {
    char[] sc = s.toCharArray();
    int j = 0;

    int[] next = new int[s.length()];

    for (int i = 1; i < sc.length; i++) {
        while (j > 0 && sc[j] != sc[i]) {
            j = next[j - 1];
        }
        if (sc[j] == sc[i]) {
            j++;
        }
        next[i] = j;
    }

    return next;
}

相加解题源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

public boolean repeatedSubstringPattern(String s) {
    if(s == null || s.length() < 2) {
        return false;
    }
    String ns = s + s;
    return strStr(ns.substring(1, ns.length() - 1), s) >= 0;
}

private int strStr(String ns, String s) {
    int[] next = getNext(s);

    char[] nsc = ns.toCharArray();
    char[] sc = s.toCharArray();

    int j = 0;

    for(int i = 0; i < nsc.length; i++) {
        while(j > 0 && nsc[i] != sc[j]) {
            j = next[j - 1];
        }

        if(nsc[i] == sc[j]) {
            j++;
            if(j == sc.length){
                return i - (j - 1);
            }
        }
    }

    return -1;
}

private int[] getNext(String s) {
    int[] next = new int[s.length()];

    int j = 0;
    char[] cs = s.toCharArray();
    for(int i = 1; i < s.length(); i++) {
        while(j > 0 && cs[i] != cs[j]) {
            j = next[j - 1];
        }
        
        if(cs[j] == cs[i]) {
            j++;
        }

        next[i] = j;
    }

    return next;
}

字符串算法-KML算法详解

KML 算法用来处理字符串匹配的问题。核心思想是当出现字符串不匹配时，根据之前已经匹配的文本内容，避免从头再去做匹配。

举例：

字符串，原始字符串，模式串是否属于字符串的一部分；
模式串，字符串的子串，用来匹配的。
对应字符串与模式串如下：
字符串：aabaabaafa
模式串：aabaaf
暴力破解方式为2层循环，一个字符一个字符交替进行匹配，此时时间复杂度为 n * m。
使用KML算法匹配，从第一个开始匹配，匹配到b != f的时候，不是从头开始匹配，而是从模式串的b开始往后匹配，可以一直匹配的末尾，字符串匹配到最后一个的下标减模式串的长度（8-6=2），即是结果

概念

能更清晰说明白KML算法，需要厘清几个概念

  • 前缀：包含首字母，不包含尾字母的所有子串
  • 后缀：包含尾字母，不包含首字母的所有子串
  • 最长相当前后缀：字符串的前缀后缀相当的子串中，最长的子串
  • next数组：存放遇到冲突后，回退下标，计算方式为最长相当前后缀长度

next数组

  • 赋值内容：直接存最长相当前后缀长度，开头存负一整体右移，最长相当前后缀减一
  • 计算逻辑：
    • 从第一个子串开始逐个循环
    • 前一位子串的最长相当前后缀的基础上分析，当前子串的最后一位=前一个最长相当前后缀长度所在下标的字符，则当前子串的最长相当前后缀加一，因为前面的在上一步已经判断过了
    • 当前子串的最后一位 != 前一个最长相当前后缀长度所在下标的字符，因为上一个最长相当前后缀可知前面的比较结果已经知道了，所以不用全部回退，只需要找到前一个下标的next数组中的最长前档前后缀的长度，回退到那个位置继续比较，直到相当或到头，记录最长相当前后缀在next当前的下标
  • 方便理解的几个模式串例子：aabaaf-010120、afbafaf-0001212、afbafafbafcaf-0001212345012

实现示例

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
/**
 * 练习KML算法
 *
 * @param haystack
 * @param needle
 * @return
 */
public int strStr(String haystack, String needle) {
    if (needle.length() == 0 || needle.length() > haystack.length()) {
        return -1;
    }

    char[] cHaystack = haystack.toCharArray();
    char[] cNeedle = needle.toCharArray();

    // 计算next数组
    // next 数组是模式串的最长相当前后缀的长度组成的数组
    // 前缀表：包含首字母，不包含尾字母的所有子串
    // 后缀表：包含尾字母，不包含首字母的所有子串
    // 最长相当前后缀：字符串的前缀表中与后缀表相当的子串中，最长的那个子串
    int[] next = getNext(cNeedle);

    int i = 0;
    int j = 0;

    while (i < cHaystack.length) {
        while (i < cHaystack.length && cHaystack[i] == cNeedle[j]) {
            if (j == cNeedle.length - 1) {
                return i - j;
            }
            j++;
            i++;
        }
        if (j == 0) {
            i++;
        } else {
            int preNextLen = next[j - 1];
            j = preNextLen;
        }
    }

    return -1;
}

private int[] getNext(char[] neddle) {
    int[] next = new int[neddle.length];

    int j = 0;
    next[0] = j;

    for (int i = 1; i < neddle.length; i++) {
        while (j > 0 && neddle[j] != neddle[i]) {
            // 原则是，比较过的不比较
            // 最长公共前后缀值得是该串的前后缀相当，当前冲突，对于前面的串不需要回退到第一个，
            // 只需要回退到公共前缀的末尾，如果不冲突，就出来结果了，如果还是冲突，则继续回退
            j = next[j - 1];
        }
        if (j >= 0 && j != i && neddle[j] == neddle[i]) {
            j++;
        }
        next[i] = j;
    }

    return next;
}

SpringBoot与Mybatis下字段脱敏、加密解密非侵入性实现方式

&emsp;&emsp;系统开发中经常遇到保护用户敏感信息的需求，比如身份证、手机号码等，在页面显示需要脱敏，在数据库保存需要加密以防止脱库等。脱敏、加密解密属于与业务无关的公共逻辑，如果夹杂在业务代码里面，不仅会增加业务代码的复杂度，而且容易出错。将其抽象提取到业务代码以外，使脱敏、加密解密对业务代码无侵入将能简化业务代码，降低出BUG的概率。

一、前端接口敏感字段脱敏

前端页面需要脱敏字段特征：

  1. 内存状态：在内存中是明文

  2. 脱敏时刻：给到前端页面那一刻脱敏

  3. 脱敏后是否还会用到该对象：脱敏后方法结束，无需再使用，即内存中的对象会被回收，即脱敏后内存状态无需关注

    基于以上特点分析，可以借助spring mvc的 ResponseBodyAdvice实现。ResponseBodyAdvice接口会对加了@RestController(也就是@Controller+@ResponseBody)注解的处理器的返回值进行增强处理，底层基于AOP实现。

    ResponseBodyAdvice 有2个方法supports和beforeBodyWrite，supports判断当前返回值是否需要增强处理，beforeBodyWrite实现增强处理的具体逻辑。

    基于脱敏字段特征及ResponseBodyAdvice的实现方式，实现思路如下：

  4. 设计一个基类，基类包含一个字段，用以说明当前业务状态是否需要脱敏。需要脱敏的实体都继承自该基类；

  5. 设计一个注解，注解只有一个参数，说明脱敏算法类型（比如手机号码脱敏算法、邮箱脱敏算法等），需要脱敏的字段使用注解标注；

  6. 实现ResponseBodyAdvice接口的2个方法supports和beforeBodyWrite，supports通过返回值类型判断是否需要做增强处理；beforeBodyWrite根据反射获取父类判断是否需要脱敏，再通过反射获取脱敏注解的字段，将字段脱敏。

1
2
3
4
5
6
7
8
9
10
/**
* 脱敏基类
*/
@Data
public class UnSensitiveDto implements Serializable {
 /**
  * 是否脱敏
  */
 private boolean sensitiveFlag = false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 脱敏注解
*
* @author avinzhang
*/
@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
public @interface UnSensitive {
 /**
  * 标注不同的脱敏算法，比如邮箱脱敏算法、身份证号码脱敏算法、手机号码脱敏算法
  * @return
  */
 String 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
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
/**
* 接口返回字段脱敏拦截器
* 使用说明
* <p>
* 使用方法，返回结果的类继承 com.qw.desensitize.dto.UnSensitiveDto
* com.qw.desensitize.dto.UnSensitiveDto#sensitiveFlag，脱敏的标识，比如本人登录状态，则赋值为false，不脱敏，其他人登录查看则赋值为true脱敏
* <p>
* 需要脱敏的字段添加注解 com.qw.desensitize.common.sensitive.UnSensitive
* com.qw.desensitize.common.sensitive.UnSensitive#type() 为脱敏算法，目前实现了手机，身份证，邮箱三种脱敏算法，对应枚举定位位置 com.qw.desensitize.dto.UnSensitiveDto
*
* @author avinzhang
*/
@ControllerAdvice
@AllArgsConstructor
@Slf4j
public class UnSensitiveAdvice implements ResponseBodyAdvice<R> {

 @Override
 public boolean supports(MethodParameter returnType, Class<? extends HttpMessageConverter<?>> converterType) {
     Type type = returnType.getGenericParameterType();
     String typeName = type.getTypeName();
     return typeName.startsWith("com.qw.desensitize.common.R");
 }

 @Nullable
 @Override
 public R beforeBodyWrite(@Nullable R body, MethodParameter returnType, MediaType selectedContentType, Class<? extends HttpMessageConverter<?>> selectedConverterType, ServerHttpRequest request, ServerHttpResponse response) {
     if (body != null) {
         if (body.getData() != null) {
             if (body.getData() instanceof UnSensitiveDto) {
                 UnSensitiveDto sensitive = (UnSensitiveDto) body.getData();
                 if (sensitive.isSensitiveFlag()) {
                     Long start = System.currentTimeMillis();
                     body.setData(unSensitive(sensitive));
                     log.warn("脱敏耗时{}毫秒", System.currentTimeMillis() - start);
                     return body;
                 }
             } else if (body.getData() instanceof List) {
                 List<Object> list = (List<Object>) body.getData();
                 if (list != null && list.size() > 0) {
                     Object element = list.get(0);
                     if (element instanceof UnSensitiveDto) {
                         UnSensitiveDto sensitive = (UnSensitiveDto) element;
                         if (sensitive.isSensitiveFlag()) {
                             Long start = System.currentTimeMillis();
                             body.setData(unSensitive(list));
                             log.warn("脱敏耗时{}毫秒", System.currentTimeMillis() - start);
                             return body;
                         }
                     }
                 }
             }
         }
     }
     return body;
 }

 private Object unSensitive(Object data) {
     try {
         if (data instanceof List) {
             // 处理list
             List<Object> list = (List) data;
             for (Object o : list) {
                 unSensitive(o);
             }
         } else {
             // 处理类
             unSensitiveParam(data);
         }
     } catch (IllegalAccessException e) {
         throw new RuntimeException(e);
     }
     return data;
 }

 /**
  * 脱敏
  *
  * @param data
  * @throws IllegalAccessException
  */
 private void unSensitiveParam(Object data) throws IllegalAccessException {
     if (data == null) {
         return;
     }
     List<Field> fields = getFields(data.getClass());
     for (Field field : fields) {
         field.setAccessible(true);
         Class<?> classType = field.getType();
         if (classType.getName().startsWith("com.qw.desensitize.dto")) {
             // 如果属性是自定义类，递归处理
             unSensitiveParam(field.get(data));
         } else if (List.class.isAssignableFrom(classType)) {
             Object objList = field.get(data);
             if (objList != null) {
                 List<Object> dataList = (List<Object>) objList;
                 for (Object dataParam : dataList) {
                     unSensitiveParam(dataParam);
                 }
             }
         } else {
             UnSensitive annotation = field.getAnnotation(UnSensitive.class);
             if (annotation != null) {
                 String type = annotation.type();
                 if (UN_SENSITIVE_EMAIL.equals(type)) {
                     if (field.get(data) != null) {
                         field.set(data, email(String.valueOf(field.get(data))));
                     }
                 }
                 if (UN_SENSITIVE_PHONE.equals(type)) {
                     if (field.get(data) != null) {
                         field.set(data, phone(String.valueOf(field.get(data))));
                     }
                 }
                 if (UnSensitiveDto.UN_SENSITIVE_ID_NUM.equals(type)) {
                     if (field.get(data) != null) {
                         field.set(data, idNum(String.valueOf(field.get(data))));
                     }
                 }
             }
         }
     }
 }

 /**
  * 递归获取所有属性
  *
  * @param clazz
  * @return
  */
 private List<Field> getFields(Class<?> clazz) {
     List<Field> list = new ArrayList<>();
     Field[] declaredFields = clazz.getDeclaredFields();
     list.addAll(Arrays.asList(declaredFields));

     Class<?> superclass = clazz.getSuperclass();
     if (superclass.getName().startsWith("com.qw.desensitize.dto")) {
         list.addAll(getFields(superclass));
     }
     return list;
 }

 /**
  * 脱敏邮箱
  *
  * @param src
  * @return
  */
 private String email(String src) {
     if (src == null) {
         return null;
     }
     String email = src.toString();
     int index = StringUtils.indexOf(email, "@");
     if (index <= 1) {
         return email;
     } else {
         return StringUtils.rightPad(StringUtils.left(email, 0), index, "*").concat(StringUtils.mid(email, index, StringUtils.length(email)));
     }
 }

 /**
  * 脱敏手机号码
  *
  * @param phone
  * @return
  */
 private String phone(String phone) {
     if (StringUtils.isBlank(phone)) {
         return "";
     }
     return phone.replaceAll("(^\\d{0})\\d.*(\\d{4})", "$1****$2");
 }

 /**
  * 身份证脱敏
  *
  * @param idNumber
  * @return
  */
 private String idNum(String idNumber) {
     if (StringUtils.isBlank(idNumber)) {
         return "";
     }
     if (idNumber.length() == 15 || idNumber.length() == 18) {
         return idNumber.replaceAll("(\\w{4})\\w*(\\w{4})", "$1*********$2");
     }
     if (idNumber.length() > 4) {
         // 组织机构代码的方式脱敏****1111
         return idNumber.replaceAll("(\\w{0})\\w*(\\w{4})", "$1*********$2");
     }
     // 不足四位或者只有一位的都替代为*
     return "*********";
 }
}
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
/**
* 继承父类，需要做脱敏处理
*/
@Data
public class UserDto extends UnSensitiveDto {
    private String name;
    /**
    * 对手机号码做脱敏的主机，脱敏算法是手机号码
    */
    @UnSensitive(type = UN_SENSITIVE_PHONE)
    private String phoneNo;
    private String gender;
    private Encrypt idNo;
}
/**
* 控制器
*/
@GetMapping("info")
public R<UserDto> info(@RequestParam String userId) {
    // 获取数据库数据
    User user = mapper.selectById(userId);
    if (user == null) {
        return R.error();
    }
    // 转化为dto
    UserDto dto = new UserDto();
    BeanUtils.copyProperties(user, dto);

    // 标注需要脱敏
    dto.setSensitiveFlag(true);

    return R.success(dto);
}

脱敏效果 

二、数据库敏感字段加密解密

数据库字段加密解密特征：

  1. 加密时刻：入库的时候

  2. 解密时刻：出库的时候

  3. 内存状态要求：在内存中需是明文

  4. 解密后是否会用到对象：会，解密即读库，读库一定是为了使用，因此解密后内存需为明文

  5. 加密后是否会用到对象：可能会，某些业务入库即结束，有些用户入库后可能还有进一步的业务，因此加密后内存中仍需保持明文。

    基于以上特征分析，可以采用mybatis的Interceptor拦截器或新定义类型使用TypeHandler处理。

mybatis 拦截器

  1. 加密：预先对入参类通过继承基类或注解添加加密标识，拦截setParameters，获取入参对象，获取到标记为需要加密的字段，对字段内容进行加密

  2. 解密：预先对结果类通过继承基类或注解添加解密标识，拦截handleResultSets，获取查询结果对象，获取需要解密的字段，对字段进行解密

  3. 缺点：加密后会将入参对象字段改为密文，影响后续使用，需要在入库的同时再操作一次读库以保证内存中一直是明文

    mybatis拦截器解密存在瑕疵，加密后需特殊处理，不建议使用，因此不再罗列该方案demo代码。

新定义类型通过TypeHandler处理思路

  1. TypeHandler在mybatis中用于实现java类型和JDBC类型的相互转换。mybatis使用prepareStatement进行参数设置的时候，通过typeHandler将传入的java类型参数转换成对应的JDBC类型参数，这个过程是通过调用PrepareStatement不同的set方法实现的；在获取结果返回之后，需将返回的结果的JDBC类型转换成java类型，通过调用ResultSet对象不同类型的get方法实现；所以不同类型的typeHandler其实就是调用PrepareStatement和ResultSet的不同方法来进行类型的转换，因此可以在调用PrepareStatement和ResultSet的相关方法之前可以对传入的参数进行处理

  2. 继承BaseTypeHandler，实现setNonNullParameter方法实现加密逻辑，实现getNullableResult方法实现解密逻辑；

  3. 将与数据库交互的类中需要加密解密的字段类型用自定义的类代替；

  4. 如果需要对前端无感，可以统一对json工具做特殊处理，对加密对象的json序列化和反序列化按照字符串逻辑处理。

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
/**
 * 加密字段字符串
 *
 * @author avinzhang
 */
public class Encrypt {
    private String value;

    public Encrypt(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }


    @Override
    public int hashCode() {
        return value.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (obj instanceof Encrypt) {
            Encrypt objE = (Encrypt) obj;
            return value.equals(objE.getValue());
        }
        return false;
    }

    @Override
    public String toString() {
        return value;
    }
}

    如果使用jackson进行json序列化和反序列化，可以通过新的序列化反序列化逻辑，代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
        // jackson
ObjectMapper objectMapper = new ObjectMapper();

// 加密解密字段json序列化与反序列化，按照字符串逻辑处理
SimpleModule simpleModule = new SimpleModule();
simpleModule.addSerializer(Encrypt.class, new JsonSerializer<Encrypt>() {
    @Override
    public void serialize(Encrypt value, JsonGenerator g, SerializerProvider serializers) throws IOException {
        g.writeString(value.getValue());
    }
});
simpleModule.addDeserializer(Encrypt.class, new JsonDeserializer<Encrypt>() {
    @Override
    public Encrypt deserialize(JsonParser p, DeserializationContext ctxt) throws IOException {
        int currentTokenId = p.getCurrentTokenId();
        if (JsonTokenId.ID_STRING == currentTokenId) {
            String text = p.getText().trim();
            return new Encrypt(text);
        }
        throw new JacksonException("json 反序列化异常", "", Encrypt.class);
    }
});
objectMapper.registerModule(simpleModule);
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
import com.qw.desensitize.dto.Encrypt;
import com.qw.desensitize.kit.DesKit;
import org.apache.ibatis.type.BaseTypeHandler;
import org.apache.ibatis.type.JdbcType;
import org.apache.ibatis.type.MappedJdbcTypes;
import org.apache.ibatis.type.MappedTypes;

import java.sql.CallableStatement;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;

/**
 * 加密解密类型转换器
 *
 * @author avinzhang
 */
@MappedJdbcTypes(JdbcType.VARCHAR)
@MappedTypes(Encrypt.class)
public class EncryptTypeHandler extends BaseTypeHandler<Encrypt> {

    /**
     * 设置参数
     */
    @Override
    public void setNonNullParameter(PreparedStatement ps, int i, Encrypt parameter, JdbcType jdbcType) throws SQLException {
        if (parameter == null || parameter.getValue() == null) {
            ps.setString(i, null);
            return;
        }
        String encrypt = DesKit.encrypt(DesKit.KEY, parameter.getValue());
        ps.setString(i, encrypt);
    }

    /**
     * 获取值
     */
    @Override
    public Encrypt getNullableResult(ResultSet rs, String columnName) throws SQLException {
        return decrypt(rs.getString(columnName));
    }

    /**
     * 获取值
     */
    @Override
    public Encrypt getNullableResult(ResultSet rs, int columnIndex) throws SQLException {
        return decrypt(rs.getString(columnIndex));
    }

    /**
     * 获取值
     */
    @Override
    public Encrypt getNullableResult(CallableStatement cs, int columnIndex) throws SQLException {
        return decrypt(cs.getString(columnIndex));
    }

    /**
     * 解密
     *
     * @param value
     * @return
     */
    private Encrypt decrypt(String value) {
        if (null == value) {
            return null;
        }
        return new Encrypt(DesKit.decrypt(DesKit.KEY, value));
    }
}        

使用举例：

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
/**
 * 用户 entity
 */
@Data
@TableName("user")
@EncryptObj
public class User {
    @TableId(value = "id", type = IdType.ASSIGN_ID)
    private String id;
    @TableField("name")
    private String name;
    /**
     * 使用拦截器方式加密
     */
    @EncryptField
    @TableField("phoneNo")
    private String phoneNo;
    @TableField("gender")
    private String gender;
    /**
     * 使用类型转换器加密解密
     */
    @TableField("idNo")
    private Encrypt idNo;
}

/**
 * 用户dto
 * 继承父类，需要做脱敏处理
 */
@Data
public class UserDto extends UnSensitiveDto {
    private String name;
    /**
     * 对手机号码做脱敏的主机，脱敏算法是手机号码
     */
    @UnSensitive(type = UN_SENSITIVE_PHONE)
    private String phoneNo;
    private String gender;
    private Encrypt idNo;
}

    /**
     * 保存，保存后还需要使用
     * @param userDto
     * @return
     */
    @PostMapping("save-error")
    public R<UserDto> saveError(@RequestBody UserDto userDto) {
        // 保存
        User user = new User();
        BeanUtils.copyProperties(userDto, user);
        mapper.insert(user);

        // 使用
        BeanUtils.copyProperties(user, userDto);
        return R.success(userDto);
    }

加密效果：


总结：

  1. 页面字段脱敏利用spring mvc 的ResponseBodyAdvice，在返回结果前改变对象为密文

  2. 数据库加密解密，既可以采用mybatis的拦截器，也可以采用mybatis的类型转换器，拦截器在加密的同时会改变内存数据为密文，mybatis类型转换器不会改变原对象

详细demo

GitHub - qwzhang01/crypto_field: 字段页面脱敏，数据库加密解密无侵入方案

LC题解-左旋转字符串

  • 反转区间为前n的子串

  • 反转区间为n到末尾的子串

  • 反转整个字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] sc = s.toCharArray();

        // 前 sc.length - n 翻转 
        int l = 0;
        int r = n - 1;
        while(l < r) {
            char t = sc[l];
            sc[l++] = sc[r];
            sc[r--] = t;
        }

        // n 到 结尾翻转
        l = n;
        r = sc.length - 1;
        while(l < r) {
            char t = sc[l];
            sc[l++] = sc[r];
            sc[r--] = t;
        }

        // 全部翻转
        l = 0;
        r = sc.length - 1;
        while(l < r) {
            char t = sc[l];
            sc[l++] = sc[r];
            sc[r--] = t;
        }

        return new String(sc);
    }
}

JDK的Arrays.sort源码阅读

    Arrays.sort分基本类型排序和对象排序。基本类型排序由DualPivotQuicksort.sort实现，对象排序由TimSort.sort实现。涉及的主要算法包括TimSort、插入排序、双插入排序、双轴快排、荷兰国旗问题等。

TimSort

  • TimSort是归并算法的改进算法

  • TimSort不一定比归并算法速度快，但是对部分有序的数组排序会快很多，现实中很多数据又一定程度有序，因此TimSort速度快

  • TimSort逻辑，将数组拆分成若干单调递增的子数组，每个子数组称为一个run，拆分完后再两两将run合并起来。拆分过程中，将每个run尽量拆分成数量相近

  • 能被拆分成少量run的数组称为高度结构化的数组

  • 归并时候将结果归并在临时数组，最后一次的时候再将数据拷贝回去，JDK做了优化，辅助数组轮流做，只要保证最后一次归并在主数组即可，这样可以省去最后再做数组拷贝

插入排序与双插入排序

  • 插入排序，每次从待排序的数字从取一个，插入到前方以有序的数组中

  • 双插入排序，每次从待排序的数字中取两个，从大到小排序，将大的插入到前方有序的数组中，从大的数字插入的位置向前将小的数字插入

双轴快排

  • 快排取一个基数，然后将数组按照基数为界分到左右两边，往复递归

  • 双轴快排则取2个基数，将数组按照基数分左中右三遍，往复递归

  • 荷兰国旗问题，使用双指针进行双轴快排的分区思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void sortColors(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int i = 0;

        while (i <= r) {
            if (nums[i] == 0) {
                swap(nums, i, l);
                l++;
            } else if (nums[i] == 2) {
                swap(nums, i, r);
                r--;
            }
            if (i < l || nums[i] == 1) i++;
        }
    }

    private void swap(int[] arr, int i, int j) { 
        if(i == j || arr[i] == arr[j]){
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
    }
基本数据类型排序逻辑

  • 当长度大到286，MAX_RUN_LENGTH< 33，即连续相等数字小于33，MAX_RUN_COUNT < 67，即run数量小于67，则采取简化版的TimSort排序（简化版TimSort指拆分不保障每个run小块大小接近），其他情况使用 sort(a, left, right, true)

  • 数组长度小于INSERTION_SORT_THRESHOLD=47，采用插入排序或双插入排序，其他情况采用双轴快排。如果是从最左端开始则使用插入排序，如果不是从最左端开始则使用双插入排序

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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
/**
     * Sorts the specified range of the array using the given
     * workspace array slice if possible for merging
     *
     * @param a the array to be sorted
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     * @param work a workspace array (slice)
     * @param workBase origin of usable space in work array
     * @param workLen usable size of work array
     */
    static void sort(int[] a, int left, int right,
                     int[] work, int workBase, int workLen) {
        // Use Quicksort on small arrays
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }

        /*
         * Index run[i] is the start of i-th run
         * (ascending or descending sequence).
         */
        int[] run = new int[MAX_RUN_COUNT + 1];
        int count = 0; run[0] = left;

        // Check if the array is nearly sorted
        for (int k = left; k < right; run[count] = k) {
            if (a[k] < a[k + 1]) { // ascending
                while (++k <= right && a[k - 1] <= a[k]);
            } else if (a[k] > a[k + 1]) { // descending
                while (++k <= right && a[k - 1] >= a[k]);
                for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                    int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                }
            } else { // equal
                for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        sort(a, left, right, true);
                        return;
                    }
                }
            }

            /*
             * The array is not highly structured,
             * use Quicksort instead of merge sort.
             */
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);
                return;
            }
        }

        // Check special cases
        // Implementation note: variable "right" is increased by 1.
        if (run[count] == right++) { // The last run contains one element
            run[++count] = right;
        } else if (count == 1) { // The array is already sorted
            return;
        }

        // Determine alternation base for merge
        byte odd = 0;
        for (int n = 1; (n <<= 1) < count; odd ^= 1);

        // Use or create temporary array b for merging
        int[] b;                 // temp array; alternates with a
        int ao, bo;              // array offsets from 'left'
        int blen = right - left; // space needed for b
        if (work == null || workLen < blen || workBase + blen > work.length) {
            work = new int[blen];
            workBase = 0;
        }
        if (odd == 0) {
            System.arraycopy(a, left, work, workBase, blen);
            b = a;
            bo = 0;
            a = work;
            ao = workBase - left;
        } else {
            b = work;
            ao = 0;
            bo = workBase - left;
        }

        // Merging
        for (int last; count > 1; count = last) {
            for (int k = (last = 0) + 2; k <= count; k += 2) {
                int hi = run[k], mi = run[k - 1];
                for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                        b[i + bo] = a[p++ + ao];
                    } else {
                        b[i + bo] = a[q++ + ao];
                    }
                }
                run[++last] = hi;
            }
            if ((count & 1) != 0) {
                for (int i = right, lo = run[count - 1]; --i >= lo;
                    b[i + bo] = a[i + ao]
                );
                run[++last] = right;
            }
            int[] t = a; a = b; b = t;
            int o = ao; ao = bo; bo = o;
        }
    }

    /**
     * Sorts the specified range of the array by Dual-Pivot Quicksort.
     *
     * @param a the array to be sorted
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     * @param leftmost indicates if this part is the leftmost in the range
     */
    private static void sort(int[] a, int left, int right, boolean leftmost) {
        int length = right - left + 1;

        // Use insertion sort on tiny arrays
        if (length < INSERTION_SORT_THRESHOLD) {
            if (leftmost) {
                /*
                 * Traditional (without sentinel) insertion sort,
                 * optimized for server VM, is used in case of
                 * the leftmost part.
                 */
                for (int i = left, j = i; i < right; j = ++i) {
                    int ai = a[i + 1];
                    while (ai < a[j]) {
                        a[j + 1] = a[j];
                        if (j-- == left) {
                            break;
                        }
                    }
                    a[j + 1] = ai;
                }
            } else {
                /*
                 * Skip the longest ascending sequence.
                 */
                do {
                    if (left >= right) {
                        return;
                    }
                } while (a[++left] >= a[left - 1]);

                /*
                 * Every element from adjoining part plays the role
                 * of sentinel, therefore this allows us to avoid the
                 * left range check on each iteration. Moreover, we use
                 * the more optimized algorithm, so called pair insertion
                 * sort, which is faster (in the context of Quicksort)
                 * than traditional implementation of insertion sort.
                 */
                for (int k = left; ++left <= right; k = ++left) {
                    int a1 = a[k], a2 = a[left];

                    if (a1 < a2) {
                        a2 = a1; a1 = a[left];
                    }
                    while (a1 < a[--k]) {
                        a[k + 2] = a[k];
                    }
                    a[++k + 1] = a1;

                    while (a2 < a[--k]) {
                        a[k + 1] = a[k];
                    }
                    a[k + 1] = a2;
                }
                int last = a[right];

                while (last < a[--right]) {
                    a[right + 1] = a[right];
                }
                a[right + 1] = last;
            }
            return;
        }

        // Inexpensive approximation of length / 7
        int seventh = (length >> 3) + (length >> 6) + 1;

        /*
         * Sort five evenly spaced elements around (and including) the
         * center element in the range. These elements will be used for
         * pivot selection as described below. The choice for spacing
         * these elements was empirically determined to work well on
         * a wide variety of inputs.
         */
        int e3 = (left + right) >>> 1; // The midpoint
        int e2 = e3 - seventh;
        int e1 = e2 - seventh;
        int e4 = e3 + seventh;
        int e5 = e4 + seventh;

        // Sort these elements using insertion sort
        if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }

        if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
        }
        if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
            }
        }
        if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
                }
            }
        }

        // Pointers
        int less  = left;  // The index of the first element of center part
        int great = right; // The index before the first element of right part

        if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
            /*
             * Use the second and fourth of the five sorted elements as pivots.
             * These values are inexpensive approximations of the first and
             * second terciles of the array. Note that pivot1 <= pivot2.
             */
            int pivot1 = a[e2];
            int pivot2 = a[e4];

            /*
             * The first and the last elements to be sorted are moved to the
             * locations formerly occupied by the pivots. When partitioning
             * is complete, the pivots are swapped back into their final
             * positions, and excluded from subsequent sorting.
             */
            a[e2] = a[left];
            a[e4] = a[right];

            /*
             * Skip elements, which are less or greater than pivot values.
             */
            while (a[++less] < pivot1);
            while (a[--great] > pivot2);

            /*
             * Partitioning:
             *
             *   left part           center part                   right part
             * +--------------------------------------------------------------+
             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
             * +--------------------------------------------------------------+
             *               ^                          ^       ^
             *               |                          |       |
             *              less                        k     great
             *
             * Invariants:
             *
             *              all in (left, less)   < pivot1
             *    pivot1 <= all in [less, k)     <= pivot2
             *              all in (great, right) > pivot2
             *
             * Pointer k is the first index of ?-part.
             */
            outer:
            for (int k = less - 1; ++k <= great; ) {
                int ak = a[k];
                if (ak < pivot1) { // Move a[k] to left part
                    a[k] = a[less];
                    /*
                     * Here and below we use "a[i] = b; i++;" instead
                     * of "a[i++] = b;" due to performance issue.
                     */
                    a[less] = ak;
                    ++less;
                } else if (ak > pivot2) { // Move a[k] to right part
                    while (a[great] > pivot2) {
                        if (great-- == k) {
                            break outer;
                        }
                    }
                    if (a[great] < pivot1) { // a[great] <= pivot2
                        a[k] = a[less];
                        a[less] = a[great];
                        ++less;
                    } else { // pivot1 <= a[great] <= pivot2
                        a[k] = a[great];
                    }
                    /*
                     * Here and below we use "a[i] = b; i--;" instead
                     * of "a[i--] = b;" due to performance issue.
                     */
                    a[great] = ak;
                    --great;
                }
            }

            // Swap pivots into their final positions
            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
            a[right] = a[great + 1]; a[great + 1] = pivot2;

            // Sort left and right parts recursively, excluding known pivots
            sort(a, left, less - 2, leftmost);
            sort(a, great + 2, right, false);

            /*
             * If center part is too large (comprises > 4/7 of the array),
             * swap internal pivot values to ends.
             */
            if (less < e1 && e5 < great) {
                /*
                 * Skip elements, which are equal to pivot values.
                 */
                while (a[less] == pivot1) {
                    ++less;
                }

                while (a[great] == pivot2) {
                    --great;
                }

                /*
                 * Partitioning:
                 *
                 *   left part         center part                  right part
                 * +----------------------------------------------------------+
                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
                 * +----------------------------------------------------------+
                 *              ^                        ^       ^
                 *              |                        |       |
                 *             less                      k     great
                 *
                 * Invariants:
                 *
                 *              all in (*,  less) == pivot1
                 *     pivot1 < all in [less,  k)  < pivot2
                 *              all in (great, *) == pivot2
                 *
                 * Pointer k is the first index of ?-part.
                 */
                outer:
                for (int k = less - 1; ++k <= great; ) {
                    int ak = a[k];
                    if (ak == pivot1) { // Move a[k] to left part
                        a[k] = a[less];
                        a[less] = ak;
                        ++less;
                    } else if (ak == pivot2) { // Move a[k] to right part
                        while (a[great] == pivot2) {
                            if (great-- == k) {
                                break outer;
                            }
                        }
                        if (a[great] == pivot1) { // a[great] < pivot2
                            a[k] = a[less];
                            /*
                             * Even though a[great] equals to pivot1, the
                             * assignment a[less] = pivot1 may be incorrect,
                             * if a[great] and pivot1 are floating-point zeros
                             * of different signs. Therefore in float and
                             * double sorting methods we have to use more
                             * accurate assignment a[less] = a[great].
                             */
                            a[less] = pivot1;
                            ++less;
                        } else { // pivot1 < a[great] < pivot2
                            a[k] = a[great];
                        }
                        a[great] = ak;
                        --great;
                    }
                }
            }

            // Sort center part recursively
            sort(a, less, great, false);

        } else { // Partitioning with one pivot
            /*
             * Use the third of the five sorted elements as pivot.
             * This value is inexpensive approximation of the median.
             */
            int pivot = a[e3];

            /*
             * Partitioning degenerates to the traditional 3-way
             * (or "Dutch National Flag") schema:
             *
             *   left part    center part              right part
             * +-------------------------------------------------+
             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
             * +-------------------------------------------------+
             *              ^              ^        ^
             *              |              |        |
             *             less            k      great
             *
             * Invariants:
             *
             *   all in (left, less)   < pivot
             *   all in [less, k)     == pivot
             *   all in (great, right) > pivot
             *
             * Pointer k is the first index of ?-part.
             */
            for (int k = less; k <= great; ++k) {
                if (a[k] == pivot) {
                    continue;
                }
                int ak = a[k];
                if (ak < pivot) { // Move a[k] to left part
                    a[k] = a[less];
                    a[less] = ak;
                    ++less;
                } else { // a[k] > pivot - Move a[k] to right part
                    while (a[great] > pivot) {
                        --great;
                    }
                    if (a[great] < pivot) { // a[great] <= pivot
                        a[k] = a[less];
                        a[less] = a[great];
                        ++less;
                    } else { // a[great] == pivot
                        /*
                         * Even though a[great] equals to pivot, the
                         * assignment a[k] = pivot may be incorrect,
                         * if a[great] and pivot are floating-point
                         * zeros of different signs. Therefore in float
                         * and double sorting methods we have to use
                         * more accurate assignment a[k] = a[great].
                         */
                        a[k] = pivot;
                    }
                    a[great] = ak;
                    --great;
                }
            }

            /*
             * Sort left and right parts recursively.
             * All elements from center part are equal
             * and, therefore, already sorted.
             */
            sort(a, left, less - 1, leftmost);
            sort(a, great + 1, right, false);
        }
    }

排序-计数排序、基数排序、桶排序

计数排序

  • 计算待排序数组的最大值和最小值

  • 计数数组位最大值到最小值的长度

  • 循环待排序数组，计数并按照值减最小是的下标放入计数数组

  • 循环计数数组，计算每个值前面的个数和

  • 再次循环待排序数组，找到计数小标的值，即为当前的排位，同步给排位加一（加一处理相当的情况）

  • 时间复杂度为O(n+k)，k为数组区间范围，由此可见该方法适用于区间比较短的排序，空间复杂度O(n+k)

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
private void countingSort(int[] arr) {

        int min = arr[0];
        int max = arr[0];
        for (int e : arr) {
            if (e < min) min = e;
            if (e > max) max = e;
        }

        int length = max - min + 1;

        int[] tmp = new int[length];
        for (int e : arr) {
            tmp[e - min]++;
        }

        int preCount = 0;
        for (int i = 0; i < tmp.length; i++) {
            int pt = tmp[i];
            tmp[i] = preCount;
            preCount += pt;
        }

        int[] tmpArr = new int[arr.length];
        for (int e : arr) {
            tmpArr[tmp[e - min]] = e;
            tmp[e - min]++;
        }
        for (int i = 0; i < tmpArr.length; i++) {
            arr[i] = tmpArr[i];
        }
    }

概率

    “猜数字”游戏：一方从 [1, 100][1,100] 中随机选取一个数字，另一方来猜。每次猜测都会得到「高了」或者「低了」的回答。怎样才能以最少的次数猜中呢？    

    二分。

    二分算法能够保证每次都排除一半的数字。每次猜测不会出现惊喜（一次排除了多于一半的数字），也不会出现悲伤（一次只排除了少于一半的数字），因为答案的每一个分支都是等概率的，所以它在最差的情况下表现是最好的，猜测的一方在logn次以内必然能够猜中。

    基于比较的排序算法与“猜数字”是类似的，每次比较，我们只能得到 a > ba>b 或者 a ≤ ba≤b 两种结果，如果我们把数组的全排列比作一块区域，那么每次比较都只能将这块区域分成两份，也就是说每次比较最多排除掉1/2的可能性。

    计数排序算法，计数排序时申请了长度为 k 的计数数组，在遍历每一个数字时，这个数字落在计数数组中的可能性共有 k 种，但通过数字本身的大小属性，一次即可把它放到正确的位置上。相当于一次排除了 (k - 1)/k(k−1)/k 种可能性。这就是计数排序算法比基于比较的排序算法更快的根本原因。

基数排序

  • 找出最大值

  • 计算最大值的长度，需根据最大值的长度计算基数，并对基数做比较

  • 从尾到头或从头到尾的方式，一位一位比较，一位一位比较的时候使用计数排序，因为每一位的数字是0-9，为了处理负数，使用从-9-9的方式（如果使用0-9，负数加变正数容易引起int越界）

  • 人排序的时候从头到尾更快，计算机排序的话从尾到头更容易

  • 基数排序是稳定的排序

  • 基数排序的时间复杂度为 O(d(n + k))O(d(n+k))(d 表示最长数字的位数，k 表示每个基数可能的取值范围大小)。空间复杂度为 O(n + k)O(n+k)（k 表示每个基数可能的取值范围大小）

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
/**
     * 基数排序
     *
     * @param arr
     */
    private int[] radixSort(int[] arr) {
        // 获取最值
        int max = 0;
        int min = 0;

        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) max = arr[i];
            if (min > arr[i]) min = arr[i];
        }

        // 获取最值的最大长度
        int maxDigitLengthTmp = 0;
        while (max != 0) {
            maxDigitLengthTmp++;
            max /= 10;
        }
        int maxDigitLength = maxDigitLengthTmp;
        maxDigitLengthTmp = 0;
        while (min != 0) {
            maxDigitLengthTmp++;
            min /= 10;
        }
        maxDigitLength = Math.max(maxDigitLength, maxDigitLengthTmp);

        // -9 —— 9 做计数排序
        int[] countingArr = null;
        int[] arrTmp = new int[arr.length];


        int dev = 1;
        // 循环基数
        while (maxDigitLength-- > 0) {
            countingArr = new int[19];
            // 计数排序
            for (int i = 0; i < arr.length; i++) {
                // 获取基数
                countingArr[arr[i] / dev % 10 + 9]++;
            }
            int preCount = 0;
            for (int i = 0; i < countingArr.length; i++) {
                int tmp = countingArr[i];
                countingArr[i] = preCount;
                preCount += tmp;
            }
            for (int i = 0; i < arr.length; i++) {
                arrTmp[countingArr[arr[i] / dev % 10 + 9]] = arr[i];
                countingArr[arr[i] / dev % 10 + 9]++;
            }
            for (int i = 0; i < arr.length; i++) {
                arr[i] = arrTmp[i];
            }
            // 升升一位
            dev *= 10;
        }

        return arr;
    }

桶排序

  • 桶排序适合排序数据量很大，内存无法一次性读进去的数据

  • 设置桶的数量

  • 计算最大值，最小值，根据最大值、最小值、桶的数量、排序数总数量，计算每个桶边界值，(max - min) / (bucketCount - 1) 为桶之间的差值，待排序数字在桶的索引 index = (int) ((value - min) / gap)

  • 对每个桶排序

  • 合并桶为一个数组

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
private void bucketSort(int[] arr) {
        if (arr == null || arr.length <= 0) return;

        int min = arr[0];
        int max = arr[0];

        for (int e : arr) {
            if (e > max) max = e;
            if (e < min) min = e;
        }

        int bucketCount = 1;
        if (arr.length > 10) {
            bucketCount = arr.length / 10;
        }

        double gap = ((double) (max - min) / (bucketCount - 1));

        List<Integer>[] bucketTmp = new LinkedList[bucketCount];

        for (int e : arr) {
            List<Integer> list = bucketTmp[(int) ((e - min) / gap)];
            if (list == null) {
                bucketTmp[(int) ((e - min) / gap)] = new LinkedList();
                list = bucketTmp[(int) ((e - min) / gap)];
            }
            list.add(e);
        }
        int index = 0;
        for (List<Integer> list : bucketTmp) {
            if (list == null || list.size() <= 0) continue;

            int[] tmp = new int[list.size()];
            for (int n = 0; n < list.size(); n++) {
                tmp[n] = list.get(n);
            }
            radixSort(tmp);
            for (int m = 0; m < tmp.length; m++) {
                arr[index++] = tmp[m];
            }
        }
    }

排序-时间复杂度O（nlongn）汇总

    时间复杂度是O(nlogn)的排序算法有希尔排序、堆排序、快排、归并排序。

希尔排序

  • 取arr.length / 2 做为间隔，逐一减小间隔

  • 按照间隔，将子数组做插入排序

堆排序

  • 构建大顶堆，从堆最后一个非叶子（数组下标 n/2 - 1）节点开始堆化，一直到堆顶

  • 取出大顶堆的堆顶元素，与数组最后一位交换

  • 从当前堆顶，重新堆化

快排

  • 随机取一个基准，即privot，将大于基准的放入右侧，小于基准的放入左侧

  • 递归的跳出条件，start = end || start = end + 1

  • 将大于基准放入左侧，小于基准放入右侧采用双指针法

归并排序

  • 将连个有序数组合并为一个数组

  • 通过递归，将数组拆分为只有一个的数组

  • 反过来，再按照合并有序数组的方式合并

对比

  • 时间复杂度都在O(n) ~ O($n^2$)

  • 希尔排序、堆排序、快排是不稳定的排序，归并是稳定的排序

  • 空间复杂度不一样，希尔排序、堆排序是O(1)，快排是O(logn)，归并是O(n)

排序-归并排序

    归并排序是时间复杂度O(nlogn)，O(n)空间复杂度的排序算法。

算法基本思想

  • 对两个有序数组合并成为有序数组，只需要O(n)的时间复杂度

  • 将数组从中间拆分为2个数组，递归拆分，直到只剩一个数字

  • 一个数字本身即为有序的，此时按照合并有序数组的方式开始合并

  • 每次合并的数组本身就都是有序的，因此最后返回的即为有序数组

空间复杂度降低思路

  • 开始定义一个和排序数组长度一致的数组做为临时储存使用，这样就不用每次都创建空间了

  • 无法进行原地排序，如果使用原地排序后即变为插入排序

  • 归并排序也为稳定的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
private int[] mergeSort(int[] arr) {
    int[] tmp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, tmp);

    return arr;
}

private void mergeSort(int[] arr, int start, int end, int[] tmp) {
    if (start == end) return;
    int middle = (end - start) / 2 + start;

    mergeSort(arr, start, middle, tmp);
    mergeSort(arr, middle + 1, end, tmp);

    merge(arr, start, end, tmp);
}

private void merge(int[] arr, int start, int end, int[] tmp) {
    int middle = (end - start) / 2 + start;

    int start1 = start;
    int end1 = middle;


    int start2 = middle + 1;
    int end2 = end;

    for (int i = start1; i <= end2; i++) {
        if (start1 > end1) {
            // 只处理第二段
            tmp[i] = arr[start2++];
        } else if (start2 > end2) {
            // 只处理第一段
            tmp[i] = arr[start1++];
        } else if (arr[start1] > arr[start2]) {
            // 比较后处理2段
            tmp[i] = arr[start2++];
        } else {
            // 比较后处理1段
            tmp[i] = arr[start1++];
        }
    }

    for (int i = start; i <= end; i++) {
        arr[i] = tmp[i];
    }
}

LC题解-多数元素题解-摩尔投票法

原题
题解

  • 排序，取中位数即为答案

  • 使用摩尔投票法

摩尔投票法

    要获取的数据大于n/2，基于此理解。取一个数，与下一个数比较，如果想当则count+1，如果不等则count-1,等count等于0的时候，取下一个数继续该过程，最后留下的那个数一定是大于n/2的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int majorityElement(int[] nums) {
        // 摩尔投票法思路

        int result = nums[0];
        int count = 1;

        for(int i = 1; i < nums.length; i++) {
            if(result == nums[i]){
                count++;
            } else {
                count--;
            }

            if(count == 0) {
                i++;
                if(i < nums.length){
                    result = nums[i];   
                    count = 1;
                }
            }
        }

        return result;
    }
}

排序-快排

    快排平均时间复杂度O(nlogn)，平均空间复杂度O(logn)。效率和使用比较多的排序算法。

快排基本思想

  • 从数组取出一个数，叫基数（privot）

  • 遍历数组，将数组中的数按照大于和小于基数，分布在基数的两边

  • 将左右两个数组再次重复以上步骤，直到分成的子数组数量只要1个或2个

快排退出递归的边界

  • 当某个区域只剩下一个数字或0个数字的时候就不需要排序了

  • start 存在 等于middle，等于middle-1；end存在等于middle，等于end-1，则start == end 或end+1 = start情况下退出递归

  • 进一步推理，start >= end 则退出递归，因为start正常情况下都小于end

基数选择

  • 选择第一个做为基数

  • 选择最后一个做为基数

  • 随机选择基数，随机选择基数时间复杂度最优

分区算法

  • 简单分区算法，从left开始，遇到比基数大的，则交换到数组最后并将right减1，直到left和right相遇，再将基数和中间的数交换，返回中间值的下标

  • 双指针分区算法

快排优化

  • 随机获取基数

  • 防止数组正序或逆序，先将数组用洗牌算法打乱

洗牌算法

    每次从未处理的数据中，随机取一个数字，将其放入数字末尾。即JDK的Collections.shuffle()

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
class Solution {

    public int[] sortArray(int[] nums) {
        quickSort(nums);
        return nums;
    }

    private void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int start, int end) {
        if (start == end || start == end + 1) {
            return;
        }

        int middle = partition(arr, start, end);

        quickSort(arr, start, middle - 1);
        quickSort(arr, middle + 1, end);
    }

    /**
     * 快排分区
     * <p>
     * 我要成为亿万富翁
     * 我要财富自由
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] arr, int start, int end) {
        Random rand = new Random();
        int middle = rand.nextInt((end - start) + 1) + start;

        // 将基数放在第一位
        swap(arr, middle, start);
        // 基数
        int privot = arr[start];

        int left = start + 1;
        int right = end;

        while (left < right) {
            while (left < right && arr[left] <= privot) left++;
            while (left < right && arr[right] >= privot) right--;
            if (left < right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }

        if (left == right && arr[right] > privot) right--;
        swap(arr, start, right);
        return right;
    }

    /**
     * 交换数组arr 下标 i j  的数据
     *
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        if (i == j) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
    }
}