算法和数据结构简介

算法的分类

硬计算类算法

精确求解，但是某些问题都是使用硬计算类的算法，可能会让计算的复杂度高
大厂算法和数据结构笔试，面试题，acm比赛或者和acm形式类似的比赛，考察的搜的硬计算类算法

软计算类算法

更注重逼近解决问题，而不是精确求解。计算时间可控
模糊逻辑，神经网络，概率理论，群体智能

数据结构分类(宏观)

连续结构

数组

跳转结构

链表
注：任何数据结构都一定是这俩个结构拼出来的！

链表

按值传递，按引用传递

class Number{
    int val;

    public Number(int val){
        this.val = val;
    }
}
public class Demo1 {
    public static void main(String[] args){
        //按值传递
        int a = 9;
        getNumber1(9);
        System.out.println(a);

        //按引用传递
        Number num = new Number(9);
        getNumber2(num);
        System.out.println(num.val);
        
        getNumber3(num);
        System.out.println(num.val);

    }

    public static void getNumber1(int num){
        num = 0;
    }

    public static void getNumber2(Number num){
        num = null;
    }

    public static void getNumber3(Number num){
        num.val = 0;
    }

}

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

单链表和双链表

一个链表是由一系列的节点构成的
单链表就是每个节点上有俩个区域，一个区域存在该节点的数据，一个节点存放指向下一个节点的地址
双链表就是每个节点上有三个区域，一个区域放该节点的数据，一个区域放上一个节点指向该节点的地址，最后一个区域放指向下一个节点的地址

链表反转

需求

假设是一个节点数为3的单链表，最后一个节点指向null；将单链表反转，上面的最后一个节点指向第二个节点，第二个节点指向第一个节点，第一个节点指向null

实现

将第一个节点指向null，然后跳到第二个节点上，指向第一个节点，然后跳转到第三个节点上，指向第二个节点

代码

class Solution{
        
        public static ListNode reverseList(ListNode head){
            
            ListNode pre = null;
            ListNode next = null;
            
            while (head != null){
                next = head.next;  //next到下一节点
                head.next = pre;   //第一个节点指向为null
                pre = head;        //pre和head位置相同
                head = next;       //head到下一节点
            }
            
            return pre;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试

https://leetcode.cn/problems/reverse-linked-list/

合并两个有序链表

需求

将两个有序链表合并成一个有序链表

实现

比较两个有序链表中节点的数据大小，其中一个比完跳到下一节点，若其中一个链表比完直接返回另一个链表的剩余部分

代码

class Solution{

        public static ListNode mergeTwoLists(ListNode head1,ListNode head2){
            if (head1 == null || head2 == null){
                return head1 == null ? head2 : head1;
            }
            
            ListNode head = head1.val <= head2.val ? head1 : head2;
            ListNode cu1 = head.next;
            ListNode cu2 = head == head1 ? head2 : head1;
            ListNode pre = head;
            while (cu1 != null && cu2 != null){
                if (cu1.val <= cu2.val){
                    pre.next = cu1;
                    cu1 = cu1.next;
                }else {
                    pre.next = cu2;
                    cu2 = cu2.next;
                }
                pre = pre.next;
            }
            pre.next = cu1 == null ? cu2 : cu1;
            return head;
        }
    }

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

测试

https://leetcode.cn/problems/merge-two-sorted-lists/

链表相加

需求

和加法一样有进位

实现

定义一个进位，初始化为0，然后俩个链表的节点数据相加，然后对除以10得到的结果为进位结果，对10取余为和

代码

class Solution {

        public static ListNode addTwoLists(ListNode head1, ListNode head2) {
            ListNode ans = null;
            ListNode cur = null;


            int carry = 0;  //进位

            int sum = 0;  //和
            int val = 0;  //节点数据

            while (head1 != null || head2 != null) {

                sum = (head1 == null ? 0 : head1.val) + (head2 == null ? 0 : head2.val) + carry;

                val = sum % 10;
                carry = sum / 10;

                if (ans == null) {
                    ans = new ListNode(val);
                    cur = ans;
                } else {
                    cur.next = new ListNode(val);
                    cur = cur.next;
                }

                head1 = head1 == null ? null : head1.next;
                head2 = head2 == null ? null : head2.next;
            }


            if (carry == 1) {
                cur.next = new ListNode(1);
            }

            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

划分链表

需求

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。

实现

定义四个变量，小头，小尾，大头，大尾，然后分别算，最后小尾的下一节点尾大头

代码

class Solution {

        public static ListNode addTwoLists(ListNode head, int num) {
            ListNode bigHead = null;    //大头
            ListNode bigTail = null;    //大尾
            ListNode smaHead = null;    //小头
            ListNode smaTail = null;    //小尾

            ListNode next = null;
            while (head != null){
                next = head.next;
                head.next = null;
                if (head.val < num){
                    if (smaHead == null){
                        smaHead = head;
                    }else {
                        smaTail.next = head;
                    }
                    smaTail = head;
                }else {
                    if (bigHead == null){
                        bigHead = head;
                    }else {
                        bigTail.next = head;
                    }
                    bigTail = head;
                }
                head = next;
            }
            if (smaHead == null ){
                return bigHead;
            }
            smaTail.next = bigHead;
            return smaHead;
        }
    }
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