文章目录
- 算法的分类
- 硬计算类算法
- 软计算类算法
- 数据结构分类(宏观)
- 连续结构
- 跳转结构
- 链表
- 按值传递,按引用传递
- 单链表和双链表
- 链表反转
- 需求
- 实现
- 代码
- 合并两个有序链表
- 需求
- 实现
- 代码
算法的分类
硬计算类算法
精确求解,但是某些问题都是使用硬计算类的算法,可能会让计算的复杂度高
大厂算法和数据结构笔试,面试题,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;
}
}
单链表和双链表
一个链表是由一系列的节点构成的
单链表就是每个节点上有俩个区域,一个区域存在该节点的数据,一个节点存放指向下一个节点的地址
双链表就是每个节点上有三个区域,一个区域放该节点的数据,一个区域放上一个节点指向该节点的地址,最后一个区域放指向下一个节点的地址
链表反转
需求
假设是一个节点数为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;
}
}
合并两个有序链表
需求
将两个有序链表合并成一个有序链表
实现
比较两个有序链表中节点的数据大小,其中一个比完跳到下一节点,若其中一个链表比完直接返回另一个链表的剩余部分
代码
class Solution{
public static ListNode reverseList(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 = head1 == head ? 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;
}
}