偷掉月亮

月是故乡明

0%

发表于 分类于 Valine：

学习来自尚硅谷宋红康JVM全套教程（详解java虚拟机）_哔哩哔哩_bilibili

https://moonshuo.cn/posts/31.html

Java虚拟机

我们目前的Java虚拟机都是基于HotSpot虚拟机，是市面上高性能虚拟机的代表作之一

image-20220708153809780

Java代码的执行流程

image-20220708155824686

JVM的架构模型

Java编译器的指令流基本上是一种基于栈的指令集架构，另外一个是基于寄存器指令集架构

image-20220708160744046

区别

栈式架构特点

  1. 设计和实现更加简单，适用于资源受限的系统
  2. 避开了寄存器分配难题，使用零地址指令方式分配，jvm仅仅有一个寄存器，而零地址则是表示没有存储数据或者操作的地址，只是设计到出栈进栈操作
  3. 指令流中的指令大部分是零地址，执行过程依赖于栈，编译器更加容易实现
  4. 不需要硬件支持，可移植性比较好

但是这样也会带来一些弊端，与寄存器结构相比，完成同样的操作，栈式架构的指令更加多

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @author 21050
 * @date 2022-07-08 16:12:48
 * @description
 */
public class Test {
    public static void main(String[] args) {
        int i=2;
        int j=1;
        int x=i+j;
    }
}

对这个文件进行反编译

image-20220708161654233

上述分别为写入2，存储到1，写入1存储到2，加载1，加载2，相加，结构存储到地址3，返回

但是对于其他的寄存器的计算流程

1
2
mov eax,1
add eax,2

JVM的生命周期

发表于 更新于 分类于 Valine：

反转字符串

344. 反转字符串 - 力扣（LeetCode）

这道题比较简单，进行数组索引的方法即可，其实也可以认为是双指针

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public void reverseString(char[] s) {
        int length=s.length;
        for (int i=0;i<length/2;i++){
            char c=s[i];
            s[i]=s[length-i-1];
            s[length-i-1]=c;
        }

    }
}

反转字符串II

541. 反转字符串 II - 力扣（LeetCode）

这个知识前面的变种，我们需要找准换算的位置，但是下面这个复杂度就高了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        int length = arr.length;
        for (int i = 0; i < length; i = i + k * 2) {
            int j = i;
            int end;
            if (i + k > length) {
                end = length;
            } else {
                end = j + k;
            }

            while (j < (i + end) / 2) {
                int l=end - (j - i) - 1;
                //下面对arr【i】到arr【i+k-1】进行反转
                char temp = arr[j];
                arr[j] = arr[l];
                arr[l] = temp;
                j++;
            }
        }
        return new String(arr);
    }

看一下官方的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

}

思路相同，但是相差1ms左右，呃(⊙﹏⊙)，可能是中间运算比官方的多插眼

替换空格

剑指 Offer 05. 替换空格 - 力扣（LeetCode）

扩展数组

仔细观察这个替换的规则，使得每一个空格变成原来的三倍，那么现在我们可以创建数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
   public String replaceSpace(String s) {
        char []arr=new char[s.length()*3];
        int length=s.length();
        int size=0;
        for (int i=0;i<length;i++){
            char c=s.charAt(i);
            if (c==32){
                arr[size++]='%';
                arr[size++]='2';
                arr[size++]='0';
            }else {
                arr[size++]=c;
            }
        }
        return new String(arr,0,size);
    }

}

当然我们也可以调用jdk所提供的方法

1
2
3
4
5
class Solution {
   public String replaceSpace(String s) {
        return s.replace(" ","%20");
    }
}

强制替换

代码随想录 (programmercarl.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
		//选用 StringBuilder 单线程使用，比较快，选不选都行
        StringBuilder sb = new StringBuilder();
		//使用 sb 逐个复制 str ，碰到空格则替换，否则直接复制
        for (int i = 0; i < str.length(); i++) {
		//str.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
        //if (" ".equals(String.valueOf(str.charAt(i)))){
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }

双指针法

仔细观察上面的几个代码，我们可以发现他们都是拥有一个目的。因为想要添加东西，就必须扩展原来的字符串空间只不过扩展的思路和方法不同。

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
/方式二：双指针法
public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

发表于 更新于 分类于 Valine：

关机重启

1
2
3
4
5
6
shutdown -h now  立即进行关机，h代表的英文单词是halt
shutdown -h 1    hello，1分钟之后要进行关机了，会给登录终端的人发送消息（也是linux默认的方式）
shutdown -r now  现在重启计算机，r代表reboot
halt 			 关机作用和第二个一样
reboot    		 现在重新启动计算机
sync			 把内存的数据同步到磁盘，放置内存中的数据丢失

注意：不管是重启系统还是关闭系统，先运行sync命令，把内存中的数据读入到磁盘中，目前的上述关机重启命令均已经在关机前进行了磁盘同步，但是小心驶得万年船

用户登录和注销

  1. 在登录的时候尽量少使用root账号进行登录，因为他是系统管理员，最大权限，避免操作失误，可以利用普通账号登录，登录之后使用“su -用户名”命令来切换成系统管理员
  2. 在提示符下输入logout即可注销用户

image-20220706112855143

用户管理

Linux是一个多用户多任务的操作系统，任何一个要使用系统资源的用户，都必须首先向系统管理员申请个一个账号，然后以这个账号的身份进入系统

添加用户

useradd 用户名

当我们添加完毕之后，会自动创建和目录同名的家目录

image-20220706113621678

image-20220706113605284

当然我们也可以自己指定目录所在的位置，如下：

useradd -d 指令目录名称 用户名

passwd 用户名 —–修改密码(如果用户名我们不写，那么默认就是当前用户的密码修改)

从root切换到其他用户不需要输入密码

image-20220706114412182

显示当前用户所在的目录： PWD

userdel 用户名 删除用户（这样删除了用户，但是用户的家目录还是存在的）

发表于 更新于 分类于 Valine：

Vi和Vim文本编辑器

基本介绍

Linux系统内置了vi文本编辑器，而vim具有程序编辑的能力，可以看作是vi的升级版，具有字体颜色矫正等等功能

三种模式

正常模式

以vim打开一个文档就可以直接进入一般模式，在这个模式中，可以使用左右键移动光标，也可以删除字符，或者赋值粘贴等等操作

插入模式

按下i，o，a，r等任何一个字母之后才会进入到编辑模式，可以正常的编辑内容

命令行模式

按下esc，然后在输入:我们即可进入到命令行模式，在这个模式中，可以提供相关发指令，完成读取，存盘替换，离开vim等等操作

image-20220705151741554

实战

现在我需要使用vim开发一个hello.Java的程序

vim Hello.Java进入到vim开发模式

image-20220705151259478

现在我们需要保存这个文件

：wq表示保存并且退出vim模式

我们可以看到文件已经完成

image-20220705151535115

image-20220705151652218

快捷键

  1. 拷贝当前行yy，拷贝当前行向下的5行，并粘贴p（该命令实在一般模式下运行）
  2. 删除当前行dd，删除当前行向下的5行5dd
  3. 在文件中查找某个单词 ，在命令行模式下 /关键词，回车查找，输入n就是查找下一个
  4. 设置文件的行号，取消文件的行号（命令行下 ：set nu和：set nonu）image-20220705153145549
  5. 编辑某个文件，使用快捷键到达文件的最末行或者最首行，定位到最末行G，最首行gg（在一般模式下使用）
  6. 在一个文件中输入了hello，现在需要撤销这个动作 u（在一般模式下执行）
  7. 快速定位到某一行，（在一般模式下）20+shift+g，注意在一般模式下我们的输入是不可见的

发表于 分类于 ， Valine：

Java中代码块的执行

代码块的格式

{执行的语句}

代码块的主要用途

当我们定义了代码块之后，我们每一次调用构造器，代码块的语句都会被执行一次。我们可以看出代码块在构造器的第一列就被调用执行了。如果有多个代码块则会按照顺序进行调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Test {
    public static void main(String[] args) {
        aa b= new aa("小明");
        aa c= new aa("小明",99);
    }
}
class  aa{
    public String name;
    public  int age;
    {

        System.out.println("我是代码块");
    }
    public  aa(String name){
        this.name=name;
        System.out.println(name+age);
    }
    public  aa(String name,int age){
        this.name=name;
        this.age=age;
        System.out.println(name+age);
    }
}

image-20220705113224248

注意事项

  • static代码块叫做静态代码块，作用时对类进行初始化，而且他随着类的加载而执行，并且只会执行一次。如果时普通代码块，每创建一个对象，就会执行。那么类什么时候会被加载那？？？①创建对象实例时（new）②创建子类对象实例，父类也会被加载③使用类的静态成员（静态方法，静态变量）

对于第一种情况我们已经演示过，我们来看第二种情况，当我们创建aa的子类bb，并且实例化bb，会调用父类的代码块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Test {
    public static void main(String[] args) {
        bb b=new bb();
    }
}
class  aa{
    public static String name;
    public  int age;
    static {

        System.out.println("我是代码块");
    }
    {

        System.out.println("我是代码块2");
    }
}
class bb extends aa{

}

image-20220705113622578

对于第三种情况，我们调用aa的静态方法，发现代码块也被调用了，至于为什么第二个非静态代码块没有执行，是因为这只是加载了类，却并没有创建类实例对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Test {
    public static void main(String[] args) {
        System.out.println(aa.name);
    }
}
class  aa{
    public static String name="张三丰";
    public  int age;
    static {

        System.out.println("我是代码块");
    }
    {

        System.out.println("我是代码块2");
    }
}

image-20220705113717597

  • 对于在调用过程中同时出现静态初始化变量与静态代码块，其中顺序按照代码中的顺序进行执行。比如：在下面这个代码中静态初始化变量在前，静态代码块在后，优先执行静态初始化变量，而普通代码块最后执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Test {
    public static void main(String[] args) {
        aa A=new aa();
    }
}
class  aa{
    public static int n1=get1();
    {
        System.out.println("我是一个普通代码块");
    }
    static {

        System.out.println("我是第一个静态代码块");
    }
    public static int get1(){
        System.out.println("我是getn1函数");
        return 100;
    }
}

image-20220705113851394

所以说，我们代码块在执行过程中会优先完成静态代码块，静态初始化等，然后在去完成普通的变量初始化与普通代码块。

  • 我们经常会遇到类的继承关系，那么在继承关系中我们代码块的执行会怎么执行。

执行如下代码，正如我们前面提到的，static在加载类时就被调用了，后面创建类时，会优先执行父类的构造器，然后执行子类的元素。

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 class Test {
    public static void main(String[] args) {
        aa A=new aa();
    }
    public Test(){
        System.out.println("我是父类的无参构造器");
    }
    {
        System.out.println("我是父类的代码块");
    }
}
class  aa extends Test{
    public  int n1=get1();
    {
        System.out.println("我是一个普通代码块");
    }
    static {

        System.out.println("我是一个静态代码块");
    }
    public static int get1(){
        System.out.println("我是getn1函数");
        return 100;
    }
}

image-20220705114106955

总结

代码块是继承执行顺序为

  1. 父类静态代码块与静态属性（子类加载中必须进行父类加载）
  2. 子类的静态代码块与静态属性（子类加载的执行）
  3. 父类的普通代码块与普通属性初始化（子类创建对象调用父类）
  4. 父类构造方法
  5. 子类的普通代码块与普通属性初始化
  6. 子类的构造方法
  7. 静态代码块只能调用静态的成员与方法，而普通代码块则可以调用任意成员与方法。因为在普通代码块执行时，静态代码块已经全部执行完毕。

发表于 更新于 分类于 Valine：

树

预备知识

  1. 树：由称作根的节点以及0个或者多个非空字数组成，这些子树每一个根都被来自根r的一条有向的边所连接。
  2. 儿子/父亲/兄弟：每一个子树的根叫做根r的儿子，而r是每一个子树的根的父亲，具有相同父亲节点的称为兄弟。
  3. 树叶：没有儿子节点的称为树叶

树的实现

实现树的一种方法可以是在每一个节点除数据之外还要有一些链，使得该节点的每一个儿子节点都指向他。但是每一个节点的儿子是不确定的，在数据结构中直接建立与子节点的链接是不可行的，这样不清楚需要多少个链

但是我们可以将所有的儿子节点放到树节点的链表中

1
2
3
4
5
6
7
8
9
10
11
//一个树节点的定义，这里就不使用泛型了
class TreeNode{
    //本节点的数据
    String data;
    //第一儿子的链，这样里面相当于嵌套了链表，而firstChild表示头节点
    TreeNode firstChild;
    //下一兄弟节点
    TreeNode nextSibling;
    //定义父节点
    TreeNode parent;
}

image-20220705093937391

现在要实现上面的这一个树

image-20220705103741710

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
package 数据结构和算法.树;

import java.util.List;

/**
 * @author 21050
 * @date 2022-07-05 09:27:18
 * @description
 */
public class TreeImpl {


    public static void main(String[] args) {
        TreeNode root=new TreeNode("A");
        TreeNode node1=new TreeNode("B");
        TreeNode node2=new TreeNode("C");
        TreeNode node3=new TreeNode("D");
        TreeNode node4=new TreeNode("E");
        TreeNode node5=new TreeNode("F");
        TreeNode node6=new TreeNode("G");
        TreeNode node7=new TreeNode("H");
        TreeNode node8=new TreeNode("I");

        //根节点添加第一个子节点
        root.addAsChild(root,node1);
        //B节点添加兄弟节点,或者为根节点A添加子节点C,都可以实现
        node1.addAsSib(node1,node2);
        //同理实现其他节点的添加,添加DE
        node1.addAsChild(node1,node3);
        node1.addAsChild(node1,node4);
        //添加F
        node2.addAsChild(node2,node5);
        //添加GHI
        node4.addAsChild(node4,node6);
        node4.addAsChild(node4,node7);
        node4.addAsChild(node4,node8);
    }


}

//一个树节点的定义，这里就不使用泛型了
class TreeNode {
    //本节点的数据
    String data;
    //第一儿子的链，这样里面相当于嵌套了链表，而firstChild表示头节点
    TreeNode firstChild;
    //下一兄弟节点
    TreeNode nextSibling;
    //定义父节点
    TreeNode parent;

    public TreeNode(String data) {
        this.data = data;
    }
    /**
     * @param node    表示当前节点
     * @param newNode 新加入的节点
     *                表示添加子节点
     */
    public void addAsChild(TreeNode node, TreeNode newNode) {
        //为node添加子节点其实为node的firstChild添加兄弟节点
        //如果是叶子节点，就第一个子节点就是newnode
        if (isLeaf(node)) {
            node.firstChild = newNode;
        } else {
            //不是子节点，就在子节点的兄弟链上加上一个节点
            TreeNode temp = node.firstChild;
            addAsSib(temp, newNode);
        }
    }

    //这里添加兄弟节点直接添加到最后了
    public void addAsSib(TreeNode node, TreeNode newNode) {
        TreeNode temp = node;
        while (node.nextSibling != null) {
            node = node.nextSibling;
        }
        node.nextSibling = newNode;
    }

    //是否是叶子节点
    public boolean isLeaf(TreeNode node) {
        return node.firstChild == null;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data='" + data + '\'' +
                '}';
    }
}

当然上面的这个树结构还是存在一定的瑕疵，比如无法判断根节点，总不能给根节点添加兄弟节点，这个时候我们可以在添加一个parent等等，许多元素我们可以自定义添加。

树的遍历

前面已经实现了一个树，那么如果进行遍历？？

前序遍历

前序遍历的是根左右（这是对于二叉树），而对于下面的非二叉树也是相应的规则，只不过这个称为根左中右

image-20220705093937391

这个遍历出来应该是ABDEGHICF

那么遍历的代码，我们首先分析一下递归遍历的顺序，这样方便我们书写代码

image-20220706101053246

1
2
3
4
5
6
7
8
9
10
//传入一个普通树的根节点
public void preorderTraversal(TreeNode root) {
    System.out.println(root);
    if (!isLeaf(root)) {
        preorderTraversal(root.firstChild);
    }
    if (root.nextSibling != null) {
        preorderTraversal(root.nextSibling);
    }
}

image-20220706100444411

中序遍历

多余这个子节点数不确定的树，中序遍历无法进行

后序遍历

后序遍历可以认为左右根，那么这个其实我们也可以根据递归遍历出,但是这样我们就不能立即将这个root输出，因为传入的root是最后才输出的，我们需要先将他的字节点全部遍历完毕。

image-20220705093937391

那么输出的方式为DGHIEBFCA

1
2
3
4
5
6
7
8
9
10
11
12
//传入一个普通树的根节点
public void postOrderTraversal(TreeNode root){
    if (!isLeaf(root)){
        postOrderTraversal(root.firstChild);
    }
    //当第一次到达这里的时候，其实已经找到属于最左边的节点了
    System.out.println(root);
    //查看最左边节点是否有兄弟节点
    if (root.nextSibling!=null){
        postOrderTraversal(root.nextSibling);
    }
}

image-20220706104428125

这个代码的思路和前序遍历相同，只是这个的顺序不同罢了

二叉树

二叉树是我们经常使用到的一个结构，每一个节点都不能超过两个儿子

二叉树的一个性质是一个平均二叉树的深度要比节点个数N小得多，这是性质很重要，其平均深度为N^1/2,即二叉查找树。

实现

二叉树的子节点个数可以确定，那么我们就可以使用左右节点表示两个节点

1
2
3
4
5
class TreeNode{
    String data;
    TreeNode left;
    TreeNode right;
}

现在要实现下面这个二叉树

image-20220707141022177

写到这里我发现，上面实现那个普通的二叉树其实不用直接写函数，直接指定指定即可！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package 数据结构和算法.树;

/**
 * @author 21050
 * @date 2022-07-07 14:06:25
 * @description
 */
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("A");
        TreeNode node1 = new TreeNode("B");
        TreeNode node2 = new TreeNode("C");
        TreeNode node3 = new TreeNode("D");
        TreeNode node4 = new TreeNode("E");
        TreeNode node5 = new TreeNode("F");
        TreeNode node6 = new TreeNode("G");
        TreeNode node7 = new TreeNode("H");

        root.left=node1;
        root.right=node2;
        node1.left=node3;
        node1.right=node4;
        node2.right=node5;
        node4.left=node6;
        node4.right=node7;
    }

}

class TreeNode {
    String data;
    TreeNode left;
    TreeNode right;

    

    public TreeNode(String data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data='" + data + '\'' +
                '}';
    }
}

image-20220707142257449

前序遍历

其实就是上面的普通的改变一下，前面的普通树的遍历，是兄弟节点和子节点之间选择，而这个是左右子节点之间的选择

1
2
3
4
5
6
7
8
9
10
//传入一个二叉树的根节点
public void preorderTraversal(TreeNode root) {
    System.out.println(root);
    if (root.left!=null){
        preorderTraversal(root.left);
    }
    if (root.right!=null){
        preorderTraversal(root.right);
    }
}

image-20220707143002949

中序遍历

中序遍历是左中右

那么这个中序遍历是DBGEHACF

1
2
3
4
5
6
7
8
9
public void inorderTraversal(TreeNode root){
    if (root.left!=null){
        inorderTraversal(root.left);
    }
    System.out.println(root);
    if (root.right!=null){
        inorderTraversal(root.right);
    }
}

image-20220707143703446

后序遍历

后序遍历是左右中，那么这个输出应该是

DGHEBFCA

1
2
3
4
5
6
7
8
9
public void postOrderTraversal(TreeNode root){
    if (root.left!=null){
        postOrderTraversal(root.left);
    }
    if (root.right!=null){
        postOrderTraversal(root.right);
    }
    System.out.println(root);
}

image-20220707144051399

表达式树

二叉树的主要用处之一是在编译器设计领域，我们现在看一个表达式树

image-20220707144703193

在这个结构中叶子节点全部为数字，而其他节点为符号运算

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
package 数据结构和算法.树;

/**
 * @author 21050
 * @date 2022-07-07 14:06:25
 * @description
 */
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("+");
        TreeNode node1 = new TreeNode("+");
        TreeNode node2 = new TreeNode("*");
        TreeNode node3 = new TreeNode("a");
        TreeNode node4 = new TreeNode("*");
        TreeNode node5 = new TreeNode("d");
        TreeNode node6 = new TreeNode("e");
        TreeNode node7 = new TreeNode("b");
        TreeNode node8 = new TreeNode("c");

        root.left=node1;
        root.right=node2;
        node1.left=node3;
        node1.right=node4;
        node2.left=node5;
        node2.right=node6;
        node4.left=node7;
        node4.right=node8;
        root.postOrderTraversal(root);
    }

}

class TreeNode {
    String data;
    TreeNode left;
    TreeNode right;


    //传入一个二叉树的根节点
    public void preorderTraversal(TreeNode root) {
        System.out.print(root);
        if (root.left!=null){
            preorderTraversal(root.left);
        }
        if (root.right!=null){
            preorderTraversal(root.right);
        }
    }

    public void inorderTraversal(TreeNode root){
        if (root.left!=null){
            inorderTraversal(root.left);
        }
        System.out.print(root);
        if (root.right!=null){
            inorderTraversal(root.right);
        }
    }

    public void postOrderTraversal(TreeNode root){
        if (root.left!=null){
            postOrderTraversal(root.left);
        }
        if (root.right!=null){
            postOrderTraversal(root.right);
        }
        System.out.print(root);
    }


    public TreeNode(String data) {
        this.data = data;
    }

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

现在我们使用中序遍历（并没有使用括号判断）

image-20220707145307973

前序遍历

image-20220707145415334

后序遍历

image-20220707145502830

其实我们清除后序遍历出的是后缀表达式，符合计算机的计算，而中序遍历我们人容易读懂

栈实现中缀表达式转换后缀表达式

那么现在我们需要输入一个后缀表达式树，要生成对应的二叉树，这个也要使用到对应的栈空间

加入说现在输入ab+cde+**

  1. 创建一个栈空间，当读到字母的时候，直接压入栈中
  2. 读到符号的时候，我们将栈中的头和次节点弹出栈，作为符号的左右节点，将符号入栈

ab入栈

image-20220707151113137

+入栈，弹出ab作为节点，而+作为新的入栈，然后cde入栈

image-20220707151457780

遇到+，de出栈作为节点

image-20220707151609625

接下来相同的操作，即可完成一个树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static TreeNode beginTree(String str){
        //建立一个栈
        Stack<TreeNode> stack=new Stack<>();
        for (char c:str.toCharArray()){
            //如果是字母，入栈
            if (0<=c-'a'&&c-'a'<=26){
                stack.add(new TreeNode(c+""));
            }else {
                //不是字母出栈
                TreeNode treeNode1=stack.pop();
                TreeNode treeNode2=stack.pop();
                //符号入栈
                TreeNode temp =new TreeNode(c+"");
                //成为子节点
                temp.left=treeNode1;
                temp.right=treeNode2;
                stack.add(temp);
            }
        }
        return stack.get(0);
    }

}

image-20220707153549912

image-20220707153648926

查找树ADT–二叉查找树

二叉查找树：对于树中的每一个节点X，都有左子树中所有项的值小于X，而右子树的所有项的值大于X中的值

在这里我们建议使用CompareTo进行比较，他的比较类型更加广泛

CompareTo的优点

实现

1
2
3
4
5
6
//这里泛型继承compareable是为了方便使用compareto的比较操作
class TreeNode<Object extends Comparable<? super Object>>  {
    Object data;
    TreeNode<Object> left;
    TreeNode<Object> right;
}

contains方法

如果存在则返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param t 表示查找的树的根节点
 * @param x 表示要查找的数据
 */
private boolean contains(Object x, TreeNode<Object> t) {
    //为空，则返回false
    if (t == null) {
        return false;
    }
    //现在比较两个数的值，以便找到我们要找的方法,如果返回小0，则说明t中数据比较大
    int result = x.compareTo(t.data);
    if (result == 0) {
        return false;
    } else if (result < 0) {
        return contains(x, t.left);
    } else {
        return contains(x, t.right);

findmax（）与findmin方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private TreeNode<Object> findMax(TreeNode<Object> t){
    if (t!=null){
        while (t.right!=null){
            t=t.right;
        }
    }
    return t;
}

private TreeNode<Object> findMin(TreeNode<Object> t){
    if (t!=null){
        while (t.left!=null){
            t=t.left;
        }
    }
    return t;
}

insert方法

这里规定了不允许插入相同的值，可以自行按照需求更改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
     * @param t 表示根节点
     * @param x 表示插入的数据
     * */
    public TreeNode<Object> insert(Object x,TreeNode<Object> t){
        if(t==null){
            return new TreeNode<>(x, null, null);
        }
        int result=x.compareTo(t.data);
        if (result==0){
            System.out.println("不允许插入相同的值");
        }else if (result<0){
            t.left=insert(x,t.left);
        }else {
            t.right=insert(x,t.right);
        }
        return t;
    }

remove方法

remove方法其实是一种比较难的方法，我们这里删除的时候，如果是一个叶子节点，我们直接删除即可，如果有一个子节点，直接使用这个子节点代替删除的节点。

但是如果存在两个子节点，那么我们可以使用这个删除节点的右子树的最小节点代替删除的节点，这样，我们仍旧可以保持查找树的状态，当然也可以使用左子树的最大节点来代替

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
/**
 * @param x 表示要删除节点的数据
 * @param t 表示填入的根节点
 * */
private TreeNode<Object> remove(Object x,TreeNode<Object> t){
    if (t==null){
        return t;
    }
    int result= x.compareTo(t.data);
    
    if (result<0){
        t.left=t.remove(x,t.left);
    }else if (result>0){
        t.right=t.remove(x,t.right);
        //如果为0.则表示已经找到，含有两个节点
    }else if (t.right!=null&&t.left!=null){
        //现在要找到右子节点的最小值
        TreeNode<Object> temp=t.findMin(t.right);
        //删除此节点，将这个值替换上去，这里也有两种方式，将找到节点的data直接替换掉要删除的data，而；另外一种则是和我们删除链表的操作一样，这里采用第一种
        t.data=temp.data;
        //现在删除temp
        remove(temp.data,t.right);
    }
    //含有一个或者0个节点
    else {
        t=(t.left!=null)?t.left:t.right;
    }
    return t;
}

实战

现在学生有成绩年龄等等属性，要求编号不同，而且按照同学3的标号为根构造树，排序按照编号进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Student implements Comparable<Student>{
    int order;
    int age;
    int score;

    public Student(int order, int age, int score) {
        this.order = order;
        this.age = age;
        this.score = score;
    }

    @Override
    public int compareTo(Student o) {
        return this.order-o.order;
    }
}

现在思考一个问题，对于这个树来说，哪一个遍历可以按照从小到大进行输出？？？

左中右，中序遍历

在这里给出大家所有代码,其实这里的比较规则我们可以自己定义，比如按照年龄排序，年龄相同按照成绩排序等等

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
package 数据结构和算法.树;

import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author 21050
 * @date 2022-07-07 14:06:25
 * @description
 */
public class BinaryTree implements Comparator<Student> {
    public static void main(String[] args) {
        Student student1=new Student(1,12,99);
        Student student2=new Student(1,12,98);
        Student student3=new Student(2,56,99);
        Student student4=new Student(3,56,99);
        Student student5=new Student(4,16,88);
        Student student6=new Student(5,3,60);

        //左右节点我们不直接指定，测试插入方法
        TreeNode<Student> treeNode1=new TreeNode<>(student3);


        treeNode1.insert(student1,treeNode1);
        treeNode1.insert(student2,treeNode1);
        treeNode1.insert(student4,treeNode1);
        treeNode1.insert(student5,treeNode1);
        treeNode1.insert(student6,treeNode1);

        treeNode1.inorderTraversal(treeNode1);

    }

    @Override
    public int compare(Student o1, Student o2) {
        return o1.order-o2.order;
    }
}

class TreeNode<Object extends Comparable<? super Object>> {
    Object data;
    TreeNode<Object> left;
    TreeNode<Object> right;

    /**
     * @param t 表示查找的树的根节点
     * @param x 表示要查找的数据
     */
    private boolean contains(Object x, TreeNode<Object> t) {
        //为空，则返回false
        if (t == null) {
            return false;
        }
        //现在比较两个数的值，以便找到我们要找的方法,如果返回小0，则说明t中数据比较大
        int result = x.compareTo(t.data);
        if (result == 0) {
            return false;
        } else if (result < 0) {
            return contains(x, t.left);
        } else {
            return contains(x, t.right);
        }
    }

    private TreeNode<Object> findMax(TreeNode<Object> t){
        if (t!=null){
            while (t.right!=null){
                t=t.right;
            }
        }
        return t;
    }

    private TreeNode<Object> findMin(TreeNode<Object> t){
        if (t!=null){
            while (t.left!=null){
                t=t.left;
            }
        }
        return t;
    }



    /**
     * @param x 表示要删除节点的数据
     * @param t 表示填入的根节点
     * */
    private TreeNode<Object> remove(Object x,TreeNode<Object> t){
        if (t==null){
            return t;
        }
        int result= x.compareTo(t.data);

        if (result<0){
            t.left=t.remove(x,t.left);
        }else if (result>0){
            t.right=t.remove(x,t.right);
            //如果为0.则表示已经找到，含有两个节点
        }else if (t.right!=null&&t.left!=null){
            //现在要找到右子节点的最小值
            TreeNode<Object> temp=t.findMin(t.right);
            //删除此节点，将这个值替换上去，这里也有两种方式，将找到节点的data直接替换掉要删除的data，而；另外一种则是和我们删除链表的操作一样，这里采用第一种
            t.data=temp.data;
            //现在删除temp
            remove(temp.data,t.right);
        }
        //含有一个或者0个节点
        else {
            t=(t.left!=null)?t.left:t.right;
        }
        return t;
    }

    /**
     * @param t 表示根节点
     * @param x 表示插入的数据
     * */
    public TreeNode<Object> insert(Object x,TreeNode<Object> t){
        if(t==null){
            return new TreeNode<>(x, null, null);
        }
        int result=x.compareTo(t.data);
        if (result==0){
            System.out.println("不允许插入相同的值");
        }else if (result<0){
            t.left=insert(x,t.left);
        }else {
            t.right=insert(x,t.right);
        }
        return t;
    }

    public TreeNode(Object data, TreeNode<Object> left, TreeNode<Object> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public TreeNode(Object data) {
        this.data = data;
    }

    public void inorderTraversal(TreeNode<Object> root){
        if (root.left!=null){
            inorderTraversal(root.left);
        }
        System.out.println(root);
        if (root.right!=null){
            inorderTraversal(root.right);
        }
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data=" + data +
                '}';
    }
}

class Student implements Comparable<Student>{
    int order;
    int age;
    int score;

    public Student(int order, int age, int score) {
        this.order = order;
        this.age = age;
        this.score = score;
    }

    @Override
    public int compareTo(Student o) {
        return this.order-o.order;
    }

    @Override
    public String toString() {
        return "Student{" +
                "order=" + order +
                ", age=" + age +
                ", score=" + score +
                '}';
    }
}

image-20220708100933538

发表于 更新于 分类于 Valine：

Java中final关键字

基本介绍

final中文意思为最后的，最终的，final可以修饰类，属性，方法和局部变量。

应用场景：

  1. 当不希望类被继承时，可以用final修饰
  2. 当不希望父类的某个方法被子类覆盖或者被重写时，可以用关键字修饰
  3. 当不希望类的某个属性值被修改，可以用final修饰

使用细节

  • final其实可以认为成常量，所以在变量命名中用XXX大写来表示常量
  • final修饰的属性在定义时，必须赋初值，并且以后不能在修改。
  • 如果final修饰的为静态变量，对final的赋值不能在构造器之中进行赋值操作。静态变量是在类加载时就要调用，而构造器则在创建对象时才进行使用的（当你运行以下代码时，会发现对于age2的操作会报错）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Test {
    
}
class aa{
    final static int age=88;
    final static int age1;
    final static int age2 ;
    static {
        age1=99;
    }

    public aa() {
        age2=18;
    }
}

  • final类不可以被继承，但是可以进行实例化对象

  • 如果一个类已经是final类，就不需要在将方法修饰成final方法

  • final与static配合使用，可以使类不被加载，静态代码块不用执行 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public class Test {
        public static void main(String[] args) {
            System.out.println(aa.age);
        }
    }
    class aa{
        final static int age=88;
        static {
            System.out.println("静态代码块被调用了");
        }

    }

发表于 更新于 分类于 Valine：

排序算法

冒泡排序

bubbleSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class BubbleSort {
    //这个冒泡排序我们使用从小到大进行排序
    public int[] sort1(int []array){
        long count=0;
        for (int i=0;i<array.length;i++){
            for (int j=0;j<array.length-1;j++){
                if (array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;

                }
                count++;
            }
        }
        System.out.println("总共走了"+count+"次循环");
        return array;
    }

    public static void main(String[] args) {
        BubbleSort bubbleSort=new BubbleSort();
        System.out.println(Arrays.toString(bubbleSort.sort1(new int[]{1, 5, 6, 2, 8, 6, 4})));
    }
}

这里的时间复杂度为n*n-1，这里没有进行优化，不在中间进行判断排序提前结束，强制执行这么多次循环

image-20220615112619203

我们仔细观察这个冒泡排序，可以每一次进行排序完毕，其实都可以确定一个最大值，所以我们可以改进代码，也就是每一次执行得到的最大值，可以不进行循环遍历了，可以在确定的最大值之前提前结束

image-20220615112907498

image-20220703135701766

这里的复杂度为n-1+…+1=(n-1+1)*(n-1)/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
package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-15 11:06:39
 * @description
 */
public class BubbleSort {
    //这个冒泡排序我们使用从小到大进行排序
    public int[] sort1(int []array){
        int count=0;
        for (int i=0;i<array.length;i++){
            boolean flag=false;
            for (int j=0;j<array.length-i-1;j++){
                if (array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    //发生交换，flag为true
                    flag=true;
                }
                count++;
            }
            if (!flag){
                System.out.println("提前结束，总共走了"+count+"次循环");
                return array;
            }
        }
        System.out.println("总共走了"+count+"次循环");
        return array;
    }

    public static void main(String[] args) {
        BubbleSort bubbleSort=new BubbleSort();
        System.out.println(Arrays.toString(bubbleSort.sort1(new int[]{1,2,3,5,7,6})));
    }
}

image-20220703135720093

选择排序

selectionSort

选择排序又叫最小选择排序，每一次选择最小的元素与前面的元素进行交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//这种方式进行排序的过程中，需要经过n-1+n-2+....+1+0=(n-1)*n/2
public int[] sort1(int []array){
        long count=0;
        for (int i=0;i<array.length-1;i++){
            int temp=array[i];
            int index=i;
            for (int j=i;j<array.length-1;j++){
                if (temp>array[j+1]){
                     temp=array[j+1];
                     index=j+1;
                }
                count++;
            }
            array[index]=array[i];
            array[i]=temp;
        }
        System.out.println("一共经过了"+count+"次循环");
        return array;
    }

image-20220619083635817

其实相比较来说，选择排序是不稳定的，比如5，4，5，2，1我们在排序的过程中我们将第一个5与2交换，这样导致第一个5变成了第二个5，如果仅仅是数字排序问题可能不大，但是如果数字表示某一种含义，会导致问题发发生。

速度比较

这里的选择排序和冒泡排序其实时间复杂度都为n(n-1)/2,不考虑冒泡提前结束，那么这两个排序算法的效率如何？？？

1
2
3
4
5
6
7
8
9
10
long beginTime=System.currentTimeMillis();
      selectionSort.sort1(array);
      long overTime=System.currentTimeMillis();
      System.out.println("选择排序时间为"+(overTime-beginTime));


      long beginTime1=System.currentTimeMillis();
      bubbleSort.sort1(array1);
      long overTime1=System.currentTimeMillis();
      System.out.println("冒泡排序时间为"+(overTime1-beginTime1));

这里虽然两个排序对应的数组相同，但是数组的大小相同，并不会影响结果，我们多的测试几下，看最终的结果

image-20220703140012310

最终导致这种差异的原因是什么？？？，在这个过程中循环次数相同，那么最终导致结果不同的原因是因为冒泡排序在一次循环过程中交换的次数比较多，耗费时间，而选择排序一次循环仅仅进行一次交换

插入排序

image-20220703140026989

插入排序的思想是我们刚开始进行排序的时候，从第二个数开始，依次与前面的数进行比较，找到对应的位置，并插入其中

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
package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-19 09:20:43
 * @description
 */
public class InsertionSort {
    public int[] sort1(int []arr){
        long count =0;
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
                count++;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        System.out.println("循环了"+count+"次");
        return arr;
    }


    public static void main(String[] args) {
        InsertionSort insertionSort=new InsertionSort();
        System.out.println(Arrays.toString(insertionSort.sort1(new int[]{5, 8, 9, 7, 5, 1, 5, 68})));
    }
}

image-20220703140042593

与其他排序算法比较

插入排序和冒泡排序对比 - 知乎 (zhihu.com)，在这个过程之中，冒泡排序位置交换进行了三次，而插入排序进行了位置交换进行了一次

image-20220703140129522

在插入排序中，比如34,8,64,51,32,21存在9个逆序，即（34，8）、（34，32）….（32，21），而这9个逆序，则是我们排序中执行的交换的次数，我们假设一个数组的逆序数为I,那么插入排序的运行时间为O(N+I)

希尔排序

对于插入排序，每一次需要将下一个元素插入对应的位置，而这个过程需要不断的和前面的数进行比较，如果要插入的数比较小，那么可以知道他需要比较很多次才可以找到对应的位置。

希尔排序是插入排序一个更高版本的排序，又叫做缩小增量排序

希尔排序算法（排序详解）_lghhtoto的博客-CSDN博客_希尔排序算法

image-20220703140151945

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-20 10:26:15
 * @description
 */
public class HillSort {
    public void sort1(int[] array) {
        for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
            //这里定义gap是相当于定义了从gap开始插入操作
            for (int i = gap; i < array.length; i++) {
                int j = i;
                int temp = array[i];
                while (j - gap >= 0 && temp < array[j - gap]) {
                    array[j] = array[j - gap];
                    j = j - gap;
                }
                if (j != i) {
                    array[j] = temp;
                }
            }
            System.out.println("本次排序完毕数组为" + Arrays.toString(array));
        }
    }

    public static void main(String[] args) {
        HillSort hillSort = new HillSort();
        hillSort.sort1(new int[]{9, 1, 2, 5, 7, 4, 8, 6, 3, 5});
    }
}

image-20220703140248346

这里只是将希尔排序的编码写了出来，但是其实这个希尔排序并不是稳定的排序，加入现在是6，5，5，9，那么经过一次排序之后，我们会将第二个5调用到第一个前面。

速度比较

我们现在比较希尔排序与插入排序的速度

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
public static void main(String[] args) {
        SelectionSort selectionSort=new SelectionSort();
        BubbleSort bubbleSort=new BubbleSort();
        InsertionSort insertionSort=new InsertionSort();
        HillSort hillSort=new HillSort();
        int []array=new int[100000];
        int []array1=new int[100000];
        int []array2=new int[100000];
        int []array3=new int[100000];
        for (int i=0;i<array.length;i++){
            array[i]= (int) (Math.random()*(100000));
        }
        for (int i=0;i<array1.length;i++){
            array1[i]= (int) (Math.random()*(100000));
        }
        for (int i=0;i<array2.length;i++){
            array2[i]= (int) (Math.random()*(100000));
        }
        for (int i=0;i<array3.length;i++){
            array3[i]= (int) (Math.random()*(100000));
        }

        long beginTime=System.currentTimeMillis();
        selectionSort.sort1(array);
        long overTime=System.currentTimeMillis();
        System.out.println("选择排序时间为"+(overTime-beginTime));


        long beginTime1=System.currentTimeMillis();
        bubbleSort.sort1(array1);
        long overTime1=System.currentTimeMillis();
        System.out.println("冒泡排序时间为"+(overTime1-beginTime1));

        long beginTime2=System.currentTimeMillis();
        insertionSort.sort1(array2);
        long overTime2=System.currentTimeMillis();
        System.out.println("插入排序时间为"+(overTime2-beginTime2));

        long beginTime3=System.currentTimeMillis();
        hillSort.sort1(array3);
        long overTime3=System.currentTimeMillis();
        System.out.println("希尔排序时间为"+(overTime3-beginTime3));
    }

image-20220703140307719

现在我们总结一下各个排序算法的为什么时间会加快？？？

比较 原因 优劣
选择排序与冒泡排序 选择排序在这个过程中内部循环每一次结束都可以明确得知进行了一次数据的交换，而冒泡排序则是因为在中间过程中因为n次的数据交换，导致在时间复杂度相同的条件下，速度比较慢，当然这个对于速度的影响也仅仅是3-4倍 冒泡排序可以在没有数据交换的时候提前选择结束，而且稳定性比较高
选择排序与插入排序 其实在测试结果我们可以看到循环的次数大大减少，那么选择如何减少次数的那？？？仔细对比在选择排序的内部循环中，不一定每一次都要将内部循环走完，找到合适的位置即可结束，但是选择排序要将内部循环走完，才能确保找到最小的数 选择排序不稳定，而插入排序稳定
希尔排序与插入排序 希尔排序巧妙优化了插入排序移动过程的循环的次数，使得在移动的过程中不需要逐个与临近的进行比较 希尔排序不稳定

image-20220703140317956

快速排序

我们先来看快速排序的示意图

我们首先选取基准值，这里选择第一个为基准值，将比其小的值放到前面，将比其大的值放到后面，为了实现这个目标我们

初始数组，我们设置初始值为6，现在我们设置一个left指针和right指针分别指向除开6之外的第一个数和最后一个数，left用红色，right用绿色

6 1 2 7 9 3 4 5 10 8

现在我们开始寻找，left负责寻找比6大的数，而right寻找比6小的数，知道之后，将两个进行交换，**记住left与right不能同时移动，必须有一个找到符合条件的位置之后，才可以移动另外一个**

6 1 2 7 9 3 4 5 10 8

交换之后，变为下面的函数

6 1 2 5 9 3 4 7 10 8

紧接着，继续移动，找到之后，进行交换

6 1 2 5 9 3 4 7 10 8

交换之后，继续移动，发现right与left相遇了，此时，将6与相遇的地方进行交换

6 1 2 5 4 3 9 7 10 8

交换之后，结束第一轮交换，此时完成目标

3 1 2 5 4 6 9 7 10 8

然后我们在将6左边的部分与右边的部分都进行相应的运算，下面以左边为举例

3 1 2 5 4

这个时候我们首先移动right指针，检测到2小于3，此时再移动left，移动一下发现在2相遇，则2与3发生交换

2 1 3 5 4

对2 1，在开始便相遇的，交换21成为12

首先给大家展示一个错误的写法，

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
package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-20 18:28:47
 * @description
 */
public class QuickSort {
    public void sort1(int []array,int left,int right){
        if (left>right){
            return;
        }
        int refValue=array[left];
        int i=left+1;
        int j=right;
        while (i<j){
            //从右边找比基准值小的数
            while (refValue<array[j]&&j>i){
                j--;
            }
            //从左边寻找到比基准值大的数
            while (refValue>array[i]&&j>i){
                i++;
            }
            if (j>i) {
                //都找成功之后，交换值
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //当i==j的时候
        array[left]=array[j];
        array[j]=refValue;
        //左右边都进行相应操作
        System.out.println("本次交换完毕，数组变为"+ Arrays.toString(array));
        sort1(array,left,i-1);
        sort1(array,i+1,right);
    }

    public static void main(String[] args) {
        QuickSort quickSort=new QuickSort();
        int []array=new int[]{6,1,2,7,9,3,4,5,10,8};
        quickSort.sort1(array,0,array.length-1);

    }
}

这是我犯的错误，比较愚蠢

仔细看这个报的错误以及前面输出的例子，前三行还是没有问题的，但是第四行发生了问题，是什么问题的导致的？？？

其实这里的思路没有问题的，问题出现在我们递归调用的方式上面，下面我们看一下递归调用的顺序

image-20220620205239397

所以说我们现在需要解决这个循环问题，同时使得交换能够正常进行，微调一下即可

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
package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-20 18:28:47
 * @description
 */
public class QuickSort {
    public void sort1(int []array,int left,int right){
        if (left>=right){
            return;
        }
        int refValue=array[left];
        int i=left;
        int j=right;
        while (i<j){
            //从右边找比基准值小的数
            while (refValue<=array[j]&&j>i){
                j--;
            }
            //从左边寻找到比基准值大的数
            while (refValue>=array[i]&&j>i){
                i++;
            }
            if (j>i) {
                //都找成功之后，交换值
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //当i==j的时候
        array[left]=array[j];
        array[j]=refValue;
        //左右边都进行相应操作
        System.out.println("本次交换完毕，数组变为"+ Arrays.toString(array));
        sort1(array,left,i-1);
        sort1(array,i+1,right);
    }

    public static void main(String[] args) {
        QuickSort quickSort=new QuickSort();
        int []array=new int[]{6,1,2,7,9,3,4,5,10,8};
        quickSort.sort1(array,0,array.length-1);

    }
}

image-20220703135500657

优化

其实在这个过程之中，基准值的选择对于算法的速度有较大的影响，如果这个数组是随机的，没有预排序，那么选取第一个元素可能没有什么影响，但是如果此时数组已经是正序或者反序，那么对速度的影响比较大

上述的例子中加入一开始便是

12345678910，那么这个便会将2345678910都划入右边，同时下一次之中也会将345678910也都划入右边，这样循环需要不断右递归10次，那么快速排序的花费时间是o(n*n),这样的话快速排序的又是就不会存在

所以说我们要找到一个合适的基准值

在这种情况下，我们可以发现其实中值是最好的选择，但是如果过我们使用中值，这个过程反而会拖累速度，所以我们采用选择arr[0],arr[（0+length-1）/2],a[length-1]中中间值的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int getRefValue(int[] array,int left,int right){
    int center=(left+right)/2;
    if (array[left]<array[center]){
        swapReferences(array,left,center);
    }
    if (array[right]<array[left]){
        swapReferences(array,left,right);
    }
    if (array[right]<array[center]){
        swapReferences(array,center,right);
    }

    return array[left];

}
//这一段来自《数据结构与算法分析Java版》，final会加快执行，但是不知道为什么，插眼！！！！

public final void swapReferences(int []array,int index1,int index2){
    int temp=array[index1];
    array[index1]=array[index2];
    array[index2]=temp;
}

归并排序

图片来自：【算法】排序算法之归并排序 - 知乎 (zhihu.com)

v2-2958d4f3d9dd9156f1b5dca6788fe8a7_r

这个算法中基本的操作是合并两个已经排序的表，应为这两个表已经排序，所以将输出放到第三个表格中，该算法可以通过对输入数据的一趟排序来完成。

基本的排序算法是两个已经排好序的数组A与B,一个输出数组C

image-20220621101100972

将AB指针指向的位置不断比较大小，小的进入到C中，对应指针++

image-20220621101222844

如果一方先完成，则将剩余的全部加入到C中，此时A已经完成

image-20220621101347922

B不需要比较直接加入即可

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
package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-21 10:15:23
 * @description
 */
public class MergeSort {
    //判断是否继续排序
    public void judgeSort(int[] array,int []tempArr,int left,int right){
        if (left<right){
            int center=(left+right)/2;
            judgeSort(array,tempArr,left,center);
            judgeSort(array,tempArr,center+1,right);
            //如果满足条件，则开始排序
            sort(array,tempArr,left,center+1,right);
        }
    }

    //制造临时数组
    public  void makeArray(int []array){
        int []tempArr=new int[array.length];
        judgeSort(array,tempArr,0,array.length-1);
    }

    public void sort(int []array,int []tempArr,int left,int center,int right){
        //我们分析两个数组，发现这两个数组的边界为left~center-1和center~right
        int leftEnd=center-1;
        int tempLeft=left;
        int tempCenter=center;
        //定义开始存储数组的位置
        int tempArrIndex=left;
        //当两个数组都在范围之内的时候
        while (tempLeft<=leftEnd&&tempCenter<=right){
            if (array[tempLeft]<=array[tempCenter]){
                tempArr[tempArrIndex]=array[tempLeft];
                tempLeft++;
                tempArrIndex++;
            }else {
                tempArr[tempArrIndex]=array[tempCenter];
                tempCenter++;
                tempArrIndex++;
            }
        }
        //当结束的时候，我们将另外一个数组中的未赋值的元素全部加入其中
        while (tempLeft<=leftEnd){
            tempArr[tempArrIndex++]=array[tempLeft++];
        }
        while (tempCenter<=right){
            tempArr[tempArrIndex++]=array[tempCenter++];
        }

        //全部赋值完毕之后，将这个数放到其中
        if (right + 1 - left >= 0) {
            System.arraycopy(tempArr, left, array, left, right + 1 - left);
        }
        System.out.println(Arrays.toString(array));
    }

    public static void main(String[] args) {
        MergeSort mergeSort=new MergeSort();
        mergeSort.makeArray(new int[]{14,12,15,13,11,16});
    }

}

image-20220621113516332

《数据结构与算法分析》：虽然归并排序的运行时间是较小的，但是合并两个已经排序的表用到线性附加内存中，在整个算法中还要花费将数据拷贝到临时数组在拷贝回来的这样的附加操作，明显减慢了速度。

与其他排序算法比较，归并排序的运行时间严重依赖比较数组和数组移动的开销，这些开销与语言有关，在Java中执行一次泛型排序，进行一次元素排序是昂贵的，但是移动元素是省时的，因为特们是引用赋值，而不是对象拷贝。归并排序是所有排序算法中比较次数最小的，在Java中是较好的选择。

​ p287页

只能看懂一部分<(￣︶￣)↗[GO!]

堆排序

堆排序是利用堆的方法进行的排序，堆分为大顶堆与小顶堆，其中的大顶堆是中间节点永远比两边的大，而小顶堆则是中间节点比两边的节点小

1024555-20161217182750011-675658660

此时我们按照堆的节点进行排序，映射之后得到数组

1024555-20161217182857323-2092264199

堆排序思路

将待排序的序列构造成一个大顶堆，此时，整个序列最大值就是中间节点，将其与尾部元素进行交换，此时尾部成为最大值，将n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复。

而堆排序的难点是构造大顶堆或者小顶堆，假设原先的堆结构如下

1024555-20161217192038651-934327647

现在我们需要从最底层的非叶子节点开始比较，逐个将这个堆调节成大顶堆

错误代码

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
package 排序;

/**
 * @author 21050
 * @date 2022-07-03 09:14:29
 * @description
 */

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5,6,8,96,1,5,82,3,8,53,5,7,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int length=arr.length;
        //我们首先构造大顶堆，而对于长度为length的数组来说，除去叶子节点，其节点有length/2-1个，也就是说除去叶子节点右边的节点代表序列为length/2-1
        //从节点开始依次向上构造大顶堆
        for (int j=length;j>0;j--){
            for (int i=j/2-1;i>=0;i--){
                percDown(arr,i,j);
            }
            //构造完毕之后我们进行交换
            int temp=arr[j-1];
            arr[j-1]=arr[0];
            arr[0]=temp;
        }
    }

    /**
     * i表示我们要调整比较的中间节点在数组的位置
     * 这个函数使得一个节点和左右节点完成大顶堆
     */
    public static void percDown(int[] arr, int i, int length) {
        int temp=arr[i];
        //那么我们可以得知这个左节点为2i+1
        int leftChild = 2 * i + 1;
        int child;
        //现在我们需要找出左节点，右节点，和中间节点的最大值
        //leftChild!=length-1表示判断是否存在右节点，arr[leftChild]<arr[leftChild+1]比较左右两个节点的大小
        if (leftChild < length - 1 && arr[leftChild] < arr[leftChild + 1]) {
            //如果说右节点比较大
            child = leftChild + 1;
        } else {
            child = leftChild;
        }
        //如果temp小于左右节点中比较大的节点，那么交换位置
        if (temp < arr[child]) {
            arr[i] = arr[child];
            arr[child] = temp;
        }
    }

}

image-20220703103815343

以上的代码虽然可以实现了排序但是，这个过程还是存在错误，这只是一个顾头不顾屁股的错误的方法，错在并没有实现大顶堆，只是将最大值筛选出来，下面看一下过程

那么初始为

image-20220703141035134

第一次交换为

image-20220703141054974

紧接着轮换到498这个节点，交换完毕之后变为

image-20220703141201414

然后在将9与6交换位置

image-20220703141238659

其实根据我写的代码分析，到这里已经交换完毕，但是其实此时并没有实现大顶堆，这只是一个冒泡排序的变种，每一次筛选出最大值

所以说我们在堆上面的元素排序时，还要注意是否影响到了下面元素的大顶堆的操作

正确代码

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
package 排序;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int []arr= {4,6,8,5,9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 堆排序
     */
    private static void sort(int[] arr) {
        // 1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--)
        {
            // 从第一个非叶子节点从下到上，从右往左调整结构
            adjustHeap(arr,i,arr.length);
        }
        // 2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--)
        {
            // 将堆顶元素与末尾元素进行交换
            swap(arr,0,j);
            // 重新对堆进行调整
            adjustHeap(arr, 0, j);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int temp=arr[i];
        // 从i节点的左子节点开始，也就是2*i+1 然后继续往下调整 就是保证以他为首的树是大根堆
        for(int k=i*2+1;k<length;k=k*2+1)
        {
            // 如果左子节点小于右子节点，k指向右子节点
            if(k+1<length&&arr[k]<arr[k+1]){
                k++;
            }

            // 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            //找到第一个需要交换的点
            if(arr[k]>temp) {
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;//将temp值放到最终的位置
    }
}

这个代码与上面的不同的特点是在检测每一个节点的时候，不单单检测此节点是否符合特点，还检测是否会影响到子节点

比如变换496节点变换的时候，通过for循环的检测，会对一次变换的元素进行检测

image-20220703141054974

变换为，但是子节点不符合大顶堆的定义，继续进行变换

image-20220703142232815

这样才算变化完毕

image-20220703142316990

基数排序

基数排序是桶排序的一种优化，基数排序将0123456789看成10个桶，每一位数进行之后可以得到一个正确的排序

1.10 基数排序 | 菜鸟教程 (runoob.com)

基本思想：基数排序是将整数按照位数分割为不同的数字，每一个位数进行比较。

实现逻辑：

  1. 将所有待比较的数统一为同样的数位长度，数位较短的前面补0
  2. 从低位开始，依次进行排序
  3. 这样从最低位排序一直到最高位排序完成后，数列变为一个有序数列

img

现在我们比较这个需要确定的两点：

  1. 基数排序循环到数组的次数如何确定？ 根据最大位数进行确定，比如上面的列子，最大位数为2，则需要循环到数组中两次
  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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-07-03 14:51:26
 * @description
 */
public class RadixSort {
    public void sort(int[] array) {
        int maxLength = getMaxLength(array);
        //需循环maxLength才可以将所有位数比较完毕
        for (int i = 0; i < maxLength; i++) {
            //建立一个array.length行，10列的二维数组，列数为0，代表存储为0的数,其中第一行的数代表已经存入数的个数
            int[][] arr = new int[array.length][10];
            //每一次循环分割出1位进行比较，并存入对应的数组中
            for (int j = 0; j < array.length; j++) {
                //假设这是第一次循环，则应该分割出个位，第二次则应该分割出十位
                String str = array[j] + "";
                int temp = 0;
                if (str.length() - 1 - i >= 0) {
                    temp = Integer.parseInt(str.substring(str.length() - 1 - i, str.length() - i));
                }
                //将得到的数存入数组中,并且计数+1
                arr[0][temp]++;
                //计数为1，则存入第一行，计数为2，则存入第二行
                arr[arr[0][temp]][temp] = array[j];
            }
            //第一轮循环完毕，我们要将二维数组的数重新存入array数组中
            int flag=0;
            for (int k=0;k<arr[0].length;k++){
                int m=arr[0][k];
                int count=1;
                while (m>=count){
                    array[flag]=arr[count][k];
                    count++;
                    flag++;
                }
            }
            System.out.println("经过第"+(i+1)+"次循环，数组变为"+ Arrays.toString(array));
        }
    }

    //将数字转换为字符串，根据str.length可以直接得到位数
    public int getMaxLength(int[] array) {
        int maxLength = (array[0] + "").length();
        for (int i = 1; i < array.length; i++) {
            String str = array[i] + "";
            int temp = str.length();
            if (temp > maxLength) {
                maxLength = temp;
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int []arr=new int[]{15, 89, 5, 63, 4, 75, 2};
        radixSort.sort(arr);
    }

}

image-20220703155043036

上述的代码时根据排序的思路得到的，我们可以看到在中间其实经过了很多for循环，我们看一看别人的代码

别人代码

这是一种比较主流的代码，仔细查看我们可以看出在得到循环次数（也就是最大位数）的代码不同，上面是通过字符串进行比较，而这里是通过乘法进行比较。而在存储的方面这里使用了Java的api中ArrayList进行存储，操作更加方便，而上面的代码实现是更加原始的代码，更加清晰中间的替换过程

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
import java.util.ArrayList;
 
public class Main {
 
    public static void main(String[] args) {
        int[] arr = new int[] { 321, 1234, 543, 324, 24, 960, 540, 672, 783, 1000 };
        radixSort(arr);
        printArray(arr);
    }
 
    public static void radixSort(int[] arr) {
        int digit = getMaxDigit(arr); // 获取最大的数是多少位
        for (int i = 0; i < digit; i++) {
            bucketSort(arr, i); // 执行 digit 次 bucketSort 排序即可
        }
    }
 
    public static int getMaxDigit(int[] arr) {
        int digit = 1; // 默认只有一位
        int base = 10; // 十进制每多一位，代表其值大了10倍
        for (int i : arr) {
            while (i > base) {
                digit++;
                base *= 10;
            }
        }
        return digit;
    }
 
    public static void bucketSort(int[] arr, int digit) {
        int base = (int) Math.pow(10, digit);
        // init buckets
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) { // 只有0~9这十个数，所以准备十个桶
            buckets.add(new ArrayList<Integer>());
        }
        // sort
        for (int i : arr) {
            int index = i / base % 10;
            buckets.get(index).add(i);
        }
        // output: copy back to arr
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            for (int i : bucket) {
                arr[index++] = i;
            }
        }
    }
 
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
}

计数基数排序

技术基数排序是对计数排序的优化，不用使用那么临时二维数组进行存储，for循环复杂度也下降

假如初始的数组如下：

image-20220703163411601

我们统计个位数的个数

0 1 2 3 4 5 6 7 8 9
0 0 1 0 0 0 2 0 1 0

现在我们将每一个位数进行进行累加和

小于等于0 小于等于1 小于等于2 小于等于3 小于等于4 小于等于5 小于等于6 小于等于7 小于等于8 小于等于9
0 0 1 1 1 1 3 3 4 4

那么根据第二个表格的顺序，我们可以得到这一次排列之后顺序为

122-56-956-78

接下来我们对十位进行检验，然后是百位，最终可以得到正确的排序

计数基数排序法_sherilindas的博客-CSDN博客_计数基数排序

感觉差一点东西，回来在写，插眼

发表于 更新于 分类于 Valine：

哈希表类型

有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isAnagram(String s, String t) {
    //英文字母只有26个，所以我们定义26个
    int[] array =new int[26];
    for (char qs:s.toCharArray()){
        array[qs-'a']+=1;
    }
    for (char qs:t.toCharArray()){
        array[qs-'a']-=1;
    }
    for (int i:array){
        if (i!=0){
            return false;
        }
    }
    return true;
}

在这里我们不一定要使用Java提供的hascode方法，我们这里相当于自己重写了hascode方法，使得数组的不同位置可以代表不同的数

两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

使用set接口提供

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    for (int i : nums1) {
        set1.add(i);
    }
    for (int j : nums2) {
        if (set1.contains(j)) {
            set2.add(j);
        }
    }
    int []arr=new int[set2.size()];
    int j=0;
    for (int i:set2){
        arr[j++]=i;
    }
    return arr;
}

排序+双指针

  • 思路：数组排序，然后用两个指针分别遍历数组，如果两个指针指向的元素相等 就是其中一个交集，否则比较两个指针指向的元素的大小，较小的向前移动
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
public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    ArrayList<Integer> arrayList=new ArrayList<>();
    int index2=0;
    for (int index1=0;index1<nums1.length&&index2<nums2.length;){
        if (nums1[index1]==nums2[index2]){
            if (!arrayList.contains(nums1[index1])){
                arrayList.add(nums1[index1]);
            }
            index1++;
            index2++;
        }else if (nums1[index1]<nums2[index2]){
            index1++;
        }else {
            index2++;
        }
    }
    int []arr=new int[arrayList.size()];
    int j=0;
    for (int i:arrayList){
        arr[j]=i;
        j++;
    }
    return arr;
}

这里调用了Java提供的集合类，其实这里不进行调用也可以进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

快乐数

202. 快乐数 - 力扣（LeetCode）

其实这道题目拥有三种可能，结果为1，得到循环，数值接近无穷大，而其实数值接近无穷大是不能存在的，快乐数 - 快乐数 - 力扣（LeetCode），我们知道n的范围，而且9的平方是十个数中值最大的，我们寻找出最大值n其实可以最大可以表示10位数，但是表示不到10个9，这里我们采用9999999999表示最大数，第一次进行运算之后

递归

image-20220615093328977 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//这里使用递归进行运算，但是这样会造成栈空间的溢出，所以可以使用循环来代替
public boolean isHappy(int n) {
    ArrayList<Integer> arrayList=new ArrayList<>();
    int sum=0;
    int a=n;
    arrayList.add(n);
    while (n!=0){
        int temp=n%10;
        n=n/10;
        sum=sum+temp*temp;
    }
    if (sum==1){
        return true;
    }
    if (arrayList.contains(sum)){
        return false;
    }
    return isHappy(sum);
}

集合

这是循环的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isHappy(int n) {
    ArrayList<Integer> arrayList=new ArrayList<>();
    int sum=n;
    arrayList.add(n);
    while (sum!=1) {
        n=sum;
        sum=0;
        while (n != 0) {
            int temp = n % 10;
            n = n / 10;
            sum = sum + temp * temp;
        }
        if (arrayList.contains(sum)){
            return false;
        }else {
            arrayList.add(sum);
        }
    }
    return true;
}

双指针

快乐数 - 快乐数 - 力扣（LeetCode）

其实这里面有一个双指针的方法证明存在环形结构，这里其实模拟了一个单链表，只不过我们改变了单链表的next域的指向规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner));
        }
        return fastRunner == 1;
}

两数之和

暴力排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int []a = new int[2];
        for(int i=0;i< nums.length;i++)
            for(int k=i+1;k< nums.length;k++)
                if(nums[i]+nums[k]==target)
                {a[0]=i;a[1]=k;}
        
                 return a;   
    }
}

使用Hashmap1

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
public int[] twoSum(int[] nums, int target) {
        HashMap<Integer ,Integer> hashMap=new HashMap<>();
        for (int i=0;i<nums.length;i++){
            hashMap.put(i,nums[i]);
        }
        int index1=0;
        int index2=0;
        for (int i=0;i<nums.length;i++){
            int temp=target-nums[i];
            hashMap.remove(i);
            if (hashMap.containsValue(temp)){
                index1=i;
                index2=getKey(hashMap,temp);
            }
        }
        return new int[]{index1,index2};
    }

    public int getKey(HashMap<Integer,Integer> hashMap,Integer value){
        for (Integer key: hashMap.keySet()){
            if (hashMap.get(key).equals(value)){
                return key;
            }
        }
        return -1;
    }

使用Hashmap2

这里使用的是将num数组的值作为key，而数组的下标作为value，因为结果将要返回的是数组的下标，而将数组的下标作为值，可以轻松得到值，而不用使用另外的方法去寻找相关发键

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i) {
        if (hashtable.containsKey(target - nums[i])) {
            return new int[]{hashtable.get(target - nums[i]), i};
        }
        hashtable.put(nums[i], i);
    }
    return new int[0];
}

四数之和

454. 四数相加 II - 力扣（LeetCode）

对于四个数相加，我们可以先分成两组，每一组中组成的数是两个数组的和，同时设置一个专门用记录一组中一个个数的的数

基础做法

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
import java.util.HashMap;
import java.util.Set;

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //在这个中我们使用hashmap，而对于这个形成值的个数是改变的，所以这个值作为hasmap的值而不是键
        HashMap<Integer,Integer> hashMap1=new HashMap<>();
        HashMap<Integer,Integer> hashMap2=new HashMap<>();

        traverseArray(nums1,nums2,hashMap1);
        traverseArray(nums3,nums4,hashMap2);

        int count=0;
        Set<Integer> keySet1=hashMap1.keySet();
        Set<Integer> keySet2=hashMap2.keySet();
        for (Integer key:keySet1){
            int temp= -key;
            if (keySet2.contains(temp)){
                count=count+hashMap2.get(temp)*hashMap1.get(key);
            }
        }

        return count;

    }
    public void traverseArray(int[] nums1, int[] nums2,HashMap<Integer,Integer> hashMap){
        for (int j : nums1) {
            for (int k : nums2) {
                int num = j + k;
                //如果存在，则+1
                if (hashMap.containsKey(num)) {
                    int a = hashMap.get(num) + 1;
                    hashMap.put(num, a);
                    //如果不存在，则直接添加
                } else {
                    hashMap.put(num, 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int []num1=new int[]{-1,-1};
        int []num2=new int[]{-1,1};
        int []num3=new int[]{-1,1};
        int []num4=new int[]{1,-1};
        Solution solution=new Solution();
        solution.fourSumCount(num1,num2,num3,num4);
    }
}

官方做法

官方思路与上述的相同，但是效率却很不同，原来第二次我们就可以不使用再次进行遍历，在这里已经可以直接对这个值相加是否为0进行判断，而且getOrDefault可以直接是我们少很多步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }


}

赎金信

383. 赎金信 - 力扣（LeetCode）

基础解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (char a : magazine.toCharArray()) {
            hashMap.put(a, hashMap.getOrDefault(a, 0) + 1);
        }
        for (char a:ransomNote.toCharArray()) {
            if (hashMap.containsKey(a)) {
                hashMap.put(a, hashMap.get(a) - 1);
            }else {
                return false;
            }
            if (hashMap.containsValue(-1)){
                return false;
            }
        }
        return true;
    }
}

先将magazine存入数组，然后在一个一个进行查找检测，遇到-1。则说明不够，直接false

巧妙自造hash规则

因为这个存放的是26位字母，数量可数，数组的大小的也确定，根据26个字母对应的ascii值，得到对应的位置，而对应的位置中存储的是重复的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] array = new int[26];
        for (char a : magazine.toCharArray()) {
            array[a - 'a']++;
        }
        for (char a : ransomNote.toCharArray()) {
            if (--array[a - 'a'] == -1) {
                return false;
            }
        }
        return true;

    }
}

image-20220705211313343

分析

其实就算法的复杂度上，这两个方法都是m+n级别，但是最终的执行速度结果差别很大。而对比这道题和四数之和这道题，其实思路差不多，但是四数之和不进行自定义hashcode值的方式，是因为这个值的多少与大小无法确定，但是这道题目却可以确定定制的hash数组的大小等等。

三树之和

15. 三数之和 - 力扣（LeetCode）

下面是leetcode给出的代码

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

下面是我的代码

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> listList = new ArrayList<>();
        if (nums.length < 3) {
            return listList;
        }
        //首先进行排序
        Arrays.sort(nums);
        int length = nums.length;

        for (int i = 0; i < length; i++) {
            if (i!=0){
                if (nums[i]==nums[i-1]){
                    continue;
                }
            }
            int temp1 = -nums[i];
            int lowIndex = i + 1;
            for (; lowIndex < length; lowIndex++) {
                int fastIndex = lowIndex + 1;
                boolean flag=false;
                if (fastIndex>=length){
                    continue;
                }
                int temp2 = temp1 - nums[lowIndex];
                while (temp2 != nums[fastIndex]) {
                    fastIndex++;
                    if (fastIndex>=length){
                        flag=true;
                        break;
                    }
                }
                if (flag){
                    continue;
                }
                if (nums[fastIndex] == temp2) {
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    arrayList.add(nums[i]);
                    arrayList.add(nums[lowIndex]);
                    arrayList.add(nums[fastIndex]);
                    if (!listList.contains(arrayList)) {
                        listList.add(arrayList);
                    }
                }
            }
        }
        return listList;
    }
}

这两个思路完全相同，而且大部分的测试用例都可以通过，但是我的代码最终超出时间限制了，但是他对排序后的条件再一次进行了使用，判断出最终的值是否在应该排序的范围内部，减少了不必要的无效重复循环。

发表于 更新于 分类于 Valine：

Linux学习基础

网络链接的三种模式

image-20220616155510712

网段：简单来说，上图的三个人都在192.168.0.？？中，我们可以认为他们在同一个网段下面，可以进行相互联系

桥接模式

image-20220705141858298

现在张三开了一个虚拟机，IP地址与李四在同一个网段下面，那么他们就可以同时进行通信，但是加入说这个教室由1000个同学都开了虚拟机，那么可能会发生ip冲突

桥接模式容易和外部系统进行通信，但是容易造成ip冲突

NAT模式

现在王五建立了一个虚拟机，IP地址设置为192.168.100.90

image-20220616160353500

那么这是完成ip地址之后，王五的主机上会产生另外一个ip地址比如192.168.100.80，负责和虚拟机进行联系，那么此时王五的虚拟机可以通过主机的代理完成与外界的通信，避免了ip地址的冲突

NAT模式，网络地址转换模式，虚拟系统可以和外部系统通讯，不造成ip冲突

主机模式

主机模式是一种独立的系统，不和外界发生联系

VM使用

虚拟机的克隆

加入现在我们已经安装了一台linux操作系统，想要安装更多的系统，可以使用虚拟机的克隆

  1. 直接拷贝安装一份安装好的虚拟机文件
  2. 使用vm提供的方法，找到对应的列表，右键点击虚拟机克隆

虚拟机快照

如果说你在使用虚拟机的时候，你想要回到原先的某一个状态，也就是说你可能担心有些误操作造成系统异常，需要回到原先的某个运行状态

image-20220616162239444

image-20220616162352683

这样就可以完成快照的状态的回复

image-20220616162526349

设置共享文件夹

image-20220616164334672

选择对应的文件之后，确定即可，然后，我们到mnt下面的hgfs即可找到对应的文件

image-20220616164447126

虽然说这里完成了window的centos的共享文件夹，但是在实际的开发中，文件的上传和下载是需要远程方式完成的

Linux的目录结构

Linux的根目录为/，而其下面的目录名称是固定的，在Linux世界中，一切皆为文件

比如我们搜索cpu，可以发现cpu下面出现两个文件

image-20220616165410829

这是因为我在分配的时候，给Linux系统分配到了两个cpu

image-20220616165506928

  1. /bin，是Binary的缩写，这个目录存放着最常使用的命令系统
  2. /sbin,这里存放的是系统管理员使用的系统管理程序，权限比较高
  3. /home，是存放普通用户的主目录，每一个用户都有自己的目录image-20220616165921818
  4. /root，系统管理员，也称作超级权限者的用户主目录
  5. /lib系统开机所需要最基本的动态链接共享库，起作用类似于windows中的dll文件，几乎所有的应用程序都会使用到这个文件
  6. /lost+found 这个目录一般为空，当系统非法关机后，这里面就存放了一些文件
  7. /etc 所有系统管理所需要的配置文件和子目录，比如安装mysql数据库的mysql.conf
  8. /user 用户的很多应用程序和文件都放在这个目录下面，类似window下面的peogram files目录
  9. /boot 时linux启动的文件
  10. /proc 是一个虚拟的目录，是内存系统的映射
  11. /dev 类似window的设备管理器，把所有的硬件用文件的形式进行存储
  12. /media系统自动识别一些设备，例如u盘，光驱等等，识别之后，linux会把识别的设备挂载到这个目录下
  13. /mnt 系统提供该目录是为了让用户临时挂在别的文件系统
  14. /opt这是主机额外安装软件所摆放的目录，安装的软件在 这个文件下面，但是一般为空
  15. /user/local是主机额外安装软件所安装的目录，是安装完成之后的目录
  16. /var 存放着不断扩充的东西，习惯将经常修改的目录放到这个下面，包括各种日志文件等等
  17. /selinux 是一种安全子系统，空值程序访问特定的文件

远程登录Linux

linux是开发小组共享的，正式上线项目是运行在公网，因此程序员需要远程登录到Linux进行项目管理或者开发

我们为了控制Linux，我们首先需要知晓linux的ip地址（首先需要确保我们的linux系统 是可以链接网络的）

image-20220705143937971

使用xshell链接对应的linux系统

image-20220705144538339

然后确定之后，可以双击此系统，此时输入账号，密码

image-20220705144706039

此时已经登录成功

image-20220705144753000

远程文件的操作

同样的操作需要进行登录等等，最终我们会发现左边显示的是我们的window操作系统，而右边显示的是Linux操作系统

image-20220705145414006

此时点击传输既可以传输到对应的目录中

image-20220705145625119