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)

4. 得出了nums[0]，其他数字都可以用nums[i] = sums[i-1] - nums[0]推出来

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

sums[] = { 223, 224, 225, 225, 226, 226, 227, 227, 228, 229 }
nums[n] = { 111, 112, 113, 114, 115 }
a + b = 223
a + c = 224
a + d = 225
a + e = 226
b + c = 225 // 打破了第2条假设，不是按升序排序！

在给定的和有重复元素的情况下，我们再按照上面的步骤1排序好数组sums，算出来的nums[0]就是错误的，因为这个时候b+c < a+e，a+e排到了b+c的位置，再套用步骤3的算法就不对了。
$a + b + a + c \neq 2a + a + e$

综上所述，重新整理后我们会发现，排序数组不是目的。真正的目的是能够让数组符合步骤3的公式nums[0] = (sums[0] + sums[1] - sums[n-1]) / 2，让b+c能够正确地出现在sums[n-1]的位置。
可是，我们并没有原数组，怎么做的出来呢？

数学家思维：给定一个有序的数组nums，其中元素按升序排列，一定存在一个有序两两和序列sums。

找到这个有序两两和序列，就可以根据上面的算法反推出原来的数组。

我不知道有没有一种数学算法可以优雅地找到有序两两和序列sums，一举这个问题。但是全排列一定能找到这个sums。以下是第51题的全部代码：

import java.util.Arrays;

public class Main {
    
    static String ans;

    public static String solution(int n, int[] sums) {
        ans = "Impossible";
        fullArrange(sums, 0, n);
        // System.out.println(ans);
        return ans;
    }
    
    private static void check(int n, int[] sums) {
        int[] nums = new int[n];
        nums[0] = (int) Math.round((sums[0] + sums[1] - sums[n-1]) / 2.0);
        for (int i = 1; i < n; i += 1) {
            nums[i] = sums[i-1] - nums[0];
        }
        
        for (int i = 0, k = 0; i < n; i += 1) {
            for (int j = i+1; j < n; j += 1) {
                if (nums[i] + nums[j] != sums[k++]) {
                    return;
                }
            }
        }
    
        StringBuilder result = new StringBuilder();
        Arrays.sort(nums);
        for (int num: nums) {
            result.append(num + " ");
        }
        ans = new String(result.deleteCharAt(result.length()-1));
    }

    // 全排列，确定sums第k位的值
    private static void fullArrange(int[] sums, int k, int n) {
        if (k == sums.length) {
            check(n, sums);
            return;
        }
        
        for (int i = k, l = sums.length; i < l; i += 1) {
            swap(sums, i, k);
            fullArrange(sums, k + 1, n);
            swap(sums, i, k);
        }
    }
    
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

454 最少时间收集RGB灯

#滑动窗口
之前做过滑动窗口的题目，如最长不重复数组，但是没有理解滑动窗口的本质，遇到这题还是没有思路。

滑动窗口的本质：给定一个数组，你需要遍历所有的子数组才能得到答案，但是并不需要每次都从头扫描。你需要的结果中，有一部分是始终存在的、重复的。

例如这个RGB问题，最先想到的方法就是遍历所有的子数组，检查每个子数组是否包含RGB，然后求最短长度。
但是，扫描RRGGGBR，我们得到两个RGB，分别是RGGGB和GBR。可见，我们不需要重复扫描中间的3个G来得到最终结果。而是要确定开头和结尾，确定范围仅此而已。

滑动窗口就是双指针，确定开头与结尾。
而其中一个指针，结尾，是必定要遍历整个数组的，不然得不到答案。
那么，怎样确定开头呢？

满足条件后，确定本次开头，并寻找下一个开头。

• 判断满足条件：在我们的题目里，可以维护一个Set，来检查是否找到了RGB三个字母。

if (charSet.size() == 3) { // 满足条件
    // 1. 确认本次长度
    // 2. 从Set中移除第一个字母
    // 3. 确定下一个start
}

• 确定本次开头：三个字母找到后，我们需要做的是，找到第一个字母最后出现的位置，确认长度。
  我们可以分别用R, G, B来记录字母最后下标。

if (ch == 'R') R = end;
if (ch == 'G') G = end;
if (ch == 'B') B = end;
if (charSet.size() == 3) { // 满足条件
    // 1. 确认本次长度
    start = min(R, G, B); // 第一个字母最后位置
    length = Math.min(length, end - start);
    // 2. 从Set中移除第一个字母
    charSet.remove(S.charAt(start));
}

• 寻找下一个开头：下一个开头，就是第二个字母最后出现的位置。

start = secondRGB(R, G, B);

int secondRGB(int R, int G, int B) {
    int[] arr = {R, G, B}; 
    Arrays.sort(arr); 
    return arr[1];
}

以下是454全部代码（两个函数合并为一次数组排序）：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static int solution(int N, String S) {
        int start, end;
        int length = Integer.MAX_VALUE;
        Set<Character> charSet = new HashSet<>();
        int R, G, B;
        R = G = B = -1;
        for (start = end = 0; end < N; end += 1) {
            char ch = S.charAt(end);
            charSet.add(ch);
            if (ch == 'R') R = end;
            if (ch == 'G') G = end;
            if (ch == 'B') B = end;
            if (charSet.size() == 3) {
                int[] charIndex = {R, G, B};
                Arrays.sort(charIndex);
                start = charIndex[0];
                length = Math.min(length, end - start);
                charSet.remove(S.charAt(start));
                start = charIndex[1];
            }
        }
        // System.out.println(length);
        return length == Integer.MAX_VALUE ? -1 : length;
    }
    
    public static void main(String[] args) {
        System.out.println(solution(5, "RRGGB") == 3);
        System.out.println(solution(4, "RRRR") == -1);
        System.out.println(solution(6, "RGBRGB") == 2);
    }
}

索引原理

MySQL使用的是B+树作为索引的数据结构

B树是一个分支内按顺序存放多个节点数据的数据结构；而B+树在此基础上，在分支内只存储索引，只在叶子节点存储数据（这样每一层可以存储更多索引，减少层数），并且在叶节点之间用指针互相连接，提高访问效率。

引擎

MyISAM，B+树存储的Data就是数据的地址（非聚集索引、稀疏索引）
InnoDB，直接存储数据（聚集索引）

为什么InnoDB建议每张表必须建立主键，并用自增整型？

ibd必须用B+树索引，而整型是天然的索引；否则ibd会自己维护一个唯一id行（隐藏的主键）。
因此UUID比较效率会比整型更低。
而自增则根本避免了重复，并且只在一端变化，已经有的数据无需做修改，减少了维持有序的成本。
如果不自增，而是随机添加，那么新增的数很可能会触发分裂、平衡，造成冗余索引。

B+树如何支持范围查询

Hash结构的索引，不支持范围查询；而B+树只用找到两端，然后顺着指针拿到所有节点就好了（叶节点是双指针连接的，并且有序）。

联合主键索引，为什么是最左前缀原则？

最左前缀原则：不能跳过左边的索引，必须从最左边索引开始，逐步增加条件。
因为联合主键索引底层的B+树就是按照主键顺序排序的，会从左到右进行比较；如果跳过了左边的主键，那就找不到了，因为第二个主键不一定是排好序的！。
首先按照第一个主键排序，然后按照第二个主键排序。在同一个主键内，二级主键是有序的，但是跳出这个圈，就是无序的。

索引优化原则

explain性能分析

explain extended: $rows * filtered/100$可以估算出将要和explain中前一个表达式进行连接的行数。
show warning: Mysql的提示信息，可能会帮你优化。

字段解释

select_type

• Primary 最外层的select。
• Subquery 不在from语句中，包含在select中的子查询。
• Derived 包含在from语句中的子查询。派生表。
  id
• 表示执行顺序，顺序越靠后优先级越高
  type
  效率优先级 system > const > eq_ref > ref > range > index > ALL

一般来说range是及格线，最好达到ref

• NULL mysql通过优化和底层原理，不访问表或索引就取到值。如求最小值，通过B+树直接拿到。
• system, const system是const的特例，const表示常量查询。表只有一行，为const查询。只有一条元组匹配，为system查询。
• eq_ref 主键关联查询，表有几行。
• ref 使用非主键（不唯一）索引，表有很多行。使用普通索引或唯一索引的部分前缀。
• range 范围查找，包括比较符号。
• index 无查询条件，全选。扫描全索引就能拿到结果，一般扫描二级索引（Mysql优先选择同等条件下更小的索引）。
• ALL 全表扫描。扫描聚集索引，比index更大

sql语句优化

• 尽量使用覆盖索引

-- 推荐，其中name和age都有索引
select name, age from your_table where condition
-- 不推荐
select * from your_table where condition

• 少用or或in；不对索引用函数；不让索引发生隐式转换
• 减少搜索范围；范围过大，mysql会认为全表扫描更快，从而不走索引
• force index(your_index) 强制索引（注意，不一定更快！可能更多回表）
• 试试用like代替范围查询

缓存

Mysql8以后移除了缓存。

Mysql缓存的本质是KV Map。然而，对于高频修改的数据，Map缓存下来的是脏数据，因此不实用。

事务

原子性 Atomicity

BUSINESS
sql语句1
sql语句2
COMMIT

原子性：事务操作要么同时发生，要么同时失败，不存在中间情况

通过Undo Log回滚实现

一致性 Consistency

账户500元 -> 扣除1000元 -> 账户-500元
-- 非法操作

一致性：每个操作都必须是合法的，账户信息应该从一个有效状态到另一个有效状态。

隔离性 Isolation

商户1转账500元 -> 余额更新为500元
商户2转账500元 -> 余额更新为500元
-- 没有隔离性

隔离性：两个操作对同一个账户并发操作时，应该表现为不相互影响类似串行的操作。

持久性 Durability

转账500元到余额 --服务器宕机--> 余额0元

持久性：操作更新成功后，更新的结果应该永久地保留下来，不会因为宕机等问题而丢失。

一号标题

Title 2

三号标题

Title 4

五号标题

Title 6

• Unordered List
  • Unordered List

1. Ordered List
   2. Ordered List

• [x] TO-DO List
• [] TO-DO List

Delete Line
Blod
Italic
Code
$E = MC^2$
Link

^[1]Hello, World!

public static void main(String[] args) {
    System.out.println("Hello World!");
}

--- auto_detect: ture
+++ auto_detect: false

No Silver Bullet

By Brooks

[!NOTE]
Note that it is a note.

[!WARNING]
WARNING!

[!DANGER]
Notice the DANGER!

[!SUCCESS]
Now it is SUCCESS.

[!INFO]
Here is some INFO.

基本操作

• <C-o>, <C-i>：回到前一个/后一个位置（例如，打开文件默认在第一行，<C-o>回到上次编辑位置）。注意这个操作是跨文件的。
• `0：返回上次位置
• 词：w（下一个词），b（词初），e（词尾）
• 行：0（行初），^（第一个非空格字符），$（行尾）
• 文件：gg（文件头），G（文件尾）
• 搜索:/{正则表达式},n/N用于导航匹配
• x删除字符（等同于dl）
• :s(substitute)替换字符（等同于xi）
  • 替换命令:{作用范围}s/{目标文本}/{替换文本}/{替换标志}
  • :%s/s_content/o_content/g 全局替换

• 可视化模式 + 操作
  • 选中文字,d删除（剪切） 或者c改变
• u撤销，<C-r>重做
• y复制 / “yank” （其他一些命令比如d也会复制）
• p粘贴
  • +p 粘贴系统剪贴板
• 更多值得学习的:
  • :<line> 跳到line行
  • ~改变字符的大小写
  • 3w向前移动三个词
  • A（大写）可以迅速定位到行尾进行修改
  • :!python prog.py 使用！直接运行shell命令
• %匹配括号

Change

ce 替换一个单词
cs"' 把当前词块的"全部替换成’

多行操作

<C-v> 选中多行，Shift + i输入后Esc，即可多行同步输入

Esc Map

Vim和NeoVim内置了<C-[>作为<Esc>的映射；
还可以通过<A->Alt加上任何键（Meta键）的方式触发<Esc>-。

宏

录制宏

命令模式下，

1. 按q<marcoName>进行录制，<marcoName>是宏的名字，例如qa
2. 执行一系列操作后，再次按q结束录制

使用宏

命令模式下，使用@<marcoName>即可执行；使用5@<marcoName>可以重复执行宏

文件操作

• :e filename切换到filename文件
• :bn/bp切换到下/上个文件
• <C-x><C-f> 自动补全路径

Shortcuts 快捷键

• CTRL+N|P 下、上一条命令
• CTRL+A|E 跳到行首、行尾
• ALT+F|B 或 CTRL+←|→ 下、上一个单词（右ALT开始使用~）
• CTRL+W 删除前面的单词
• CTRL+D|H 删除一个字符（D向后删除=Delete，H向前删除=Backspace）
• CTRL+U 删除整行
• CTRL+R 搜索整行，Esc退出

Proxy

export https_proxy=http://host:port;
export http_proxy=http://host:port;
export all_proxy=socks5://host:port;

Bash prompt string配置

使用Windows CMD比使用MinTTY更快！

• PS(prompt string): 是命令行的默认显示文本，如：

username@hostname /work_directory
$ 

• 可以在~/.bash_profile或.bashrc中修改默认显示（Windows Git Bash是git-prompt.sh）

# Windows Git Bash默认配置，其中\007前面的$TITLEPREFIX和$PWD是标签栏的内容，git_ps1会显示git工作分支
export PS1="\[\e]0;$TITLEPREFIX:$PWD\007\]\n\[\e[32m\]\u@\h \[\e[35m\]$MSYSTEM \[\e[33m\]\w\[\e[36m\]`__git_ps1`\[\e[0m\]\n$ " 
# 显示效果
username@hostname MINGW /work_directory
$ 

# 简洁配置，将\h换成了指定文本，保留了命令行前的换行，将标签名改为当前目录
export PS1="\[\e]0;\W\007\] \n\[\e[32m\]\u@Host \[\e[33m\]\w\[\e[36m\]`__git_ps1`\[\e[0m\]\n$ " 
# 显示效果
username@Host /work_directory
$ 

• Windows虚拟环境后不会换行：设置venv/Scripts/activate

if [ -z "${VIRTUAL_ENV_DISABLE_PROMPT-}" ] ; then
    _OLD_VIRTUAL_PS1="${PS1-}"
    PS1="\n(${VIRTUAL_ENV_PROMPT}) ${PS1-}" # 添加换行符
    export PS1
fi

• MSYS2显示git prompt

# etc/profile.d/git-prompt.sh
if test -f /etc/profile.d/git-sdk.sh
then
        TITLEPREFIX=SDK-${MSYSTEM#MINGW}
else
        TITLEPREFIX=$MSYSTEM
fi
 
if test -f ~/.config/git/git-prompt.sh
then
        . ~/.config/git/git-prompt.sh
else
        PS1='\[\033]0;$TITLEPREFIX:$PWD\007\]' # set window title
        PS1="$PS1"'\n'                 # new line
        PS1="$PS1"'\[\033[32m\]'       # change to green
        PS1="$PS1"'\u@\h '             # user@host<space>
        PS1="$PS1"'\[\033[35m\]'       # change to purple
        PS1="$PS1"'$MSYSTEM '          # show MSYSTEM
        PS1="$PS1"'\[\033[33m\]'       # change to brownish yellow
        PS1="$PS1"'\w'                 # current working directory
        if test -z "$WINELOADERNOEXEC"
        then
                GIT_EXEC_PATH="$(git --exec-path 2>/dev/null)"
                COMPLETION_PATH="${GIT_EXEC_PATH%/libexec/git-core}"
                COMPLETION_PATH="${COMPLETION_PATH%/lib/git-core}"
                COMPLETION_PATH="$COMPLETION_PATH/share/git/completion"
                if test -f "$COMPLETION_PATH/git-prompt.sh"
                then
                        . "$COMPLETION_PATH/git-completion.bash"
                        . "$COMPLETION_PATH/git-prompt.sh"
                        PS1="$PS1"'\[\033[36m\]'  # change color to cyan
                        PS1="$PS1"'`__git_ps1`'   # bash function
                fi
        fi
        PS1="$PS1"'\[\033[0m\]'        # change color
        PS1="$PS1"'\n'                 # new line
        PS1="$PS1"'$ '                 # prompt: always $
fi
 
MSYS2_PS1="$PS1"               # for detection by MSYS2 SDK's bash.basrc
 
# Evaluate all user-specific Bash completion scripts (if any)
if test -z "$WINELOADERNOEXEC"
then
        for c in "$HOME"/bash_completion.d/*.bash
        do
                # Handle absence of any scripts (or the folder) gracefully
                test ! -f "$c" ||
                . "$c"
        done
fi

# ~/.bashrc || ~/.bash_profile
shopt -q login_shell || . /etc/profile.d/git-prompt.sh

微服务

非单体项目，可以用下面的脚本启动微服务。

#!/bin/bash

# 获取用户输入的服务名称
SERVICE_NAME=$1

# 检查是否输入参数
if [ -z "$SERVICE_NAME" ]; then
  echo "Usage: ./run.sh <servicename|all>"
  exit 1
fi

# 定义运行单个服务的函数
run_service() {
  local service=$1
  echo "Building and running $service..."
  mvn clean install -pl $service -am
  mvn spring-boot:run -pl $service
}

# 如果输入 "all"，运行所有服务
if [ "$SERVICE_NAME" == "all" ]; then
  echo "Building and running all services..."
  mvn clean install
  # 假设所有 Spring Boot 模块都在根目录下
  for module in $(mvn help:evaluate -Dexpression=project.modules -q -DforceStdout | sed -e 's/<[^>]*>//g' -e 's/\s*//g' | tr ',' '\n'); do
    echo "Running $module..."
    mvn spring-boot:run -pl $module &
  done
else
  # 运行指定的单个服务
  run_service $SERVICE_NAME
fi

0.0 代码合并流程

1. 在各自的分支self上进行开发
2. 切换到develop分支，git pull同步最新代码
3. 切换到自己的分支self，git rebase develop对齐代码合并冲突

1.0 第一件事git config

• git config --list --show-origin查看所有git配置以及所在文件
• 使用git config --global可以设置git的基本信息（如用户名、邮箱），使用--unset取消设置
  1. 配置你的名称、邮箱以及编辑器

git config --global user.name "191220000-Zhang San" 
# 全局设置名称
git config --global user.email "zhang3@email.com"
git config --global core.editor vim

# instead of
git config --global url.git@github.com:.insteadOf https://github.com/
# alias
git config --global alias.cin "commit --amend --no-edit"

2.0 初始化仓库

1. 本地仓库：git init创建一个新的 git 仓库，其数据会存放在一个名为 .git 的目录下
   删除仓库：删除 .git 文件夹

git add <文件名字，*表示全部>
# 提交到暂存区，并附上注释
git commit -m 'initial project version' 
# 修改最近的一次提交
git commit --ammend

2. 远程仓库：git clone克隆远端仓库

# 查看remote
git remote -v

# 添加remote
git remote add origin project_repository_url.git
# 设置push分支为自己的仓库
git remote set-url --add --push origin your_repository_url.git

git clone <网址> <仓库存放文件夹名>
# 使用http克隆

配置SSH

不推荐dsa和rsa，推荐ed25519

ssh-keygen -t ed25519 -C "your_email@email.com"

Tag

git tag v0.0.version
git tag -a v0.version -m "Your Comments to the version"

Nacos 更全能的注册中心

Nacos 相当于 Eureka + Config 的组合。

Sentinel

相当于 Hystix，用于流量控制。

Tomcat

JRE报错

一般教程会让我们配置JAVA_HOME和JRE_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就能正常启动

微服务

微服务：解决接口越来越多，单体应用运行缓慢问题。

踩坑记录

找不到Mapper

***************************
APPLICATION FAILED TO START
***************************

Description:

Field deviceMapper in com.esagent.es.EsDataInit required a bean of type 'com.example.mapper.YourMapper' that could not be found.

The injection point has the following annotations:
    - @org.springframework.beans.factory.annotation.Autowired(required=true)


Action:

Consider defining a bean of type 'com.example.mapper.YourMapper' in your configuration.

原因是mybatis版本有问题！

<dependencyManagement>
    <dependencies>
        <dependency>
            <groupId>org.mybatis.spring.boot</groupId>
            <artifactId>mybatis-spring-boot-starter</artifactId>
            <version>3.0.4</version>
            <!-- 版本需要和其他依赖对上 -->
        </dependency>
    </dependencies>
</dependencyManagement>