【数据结构与算法】——学习笔记

学习数据结构与算法的第一天

前言

概述：

今天从恩师那里受赠一本C语言版本的数据结构，
万分感动，在此立誓，誓要学好数据结构，掌握好算法，争取做出一番成就，绝不辜负恩师的期望。

以下是本篇文章正文内容

第一部分 语言基础

基础

数组

数组的定义

用来存储固定大小的同类型元素

特点：

1.本身就是引用数据类型，但数组中的元素可以是任意数据类型

2.数组会在内部开辟一整块连续的空间，占据的大小取决于数组的长度和数组中的元素类型

3.数组中的元素在内存了是依次紧密连续的

4.数组一旦初始化完成，那么数组的长度就不能修改

5.可以直接通过下标的方式调用指定位置的元素-数组名中引用的是这块连续空间的首地址

6.数组的索引是从0开始的

数组的声明

一维数组 int[] arr; 二维数组 int[][] arr;

初始化

静态：int[] arr = new int[]{1,2,3,4,5,6};

动态：int[] arr = new int[5];

遍历数组

一维数组 for循环for(int i = 0; i < arr.length; i++) 或 for(int k : arr)

二维数组 两层for循环

java.util.Arrays类

可以方便操作数组，提供的所有方法都是静态的

Arrays.fill对数组进行赋值 Arrays.sort对数组进行排序（默认升序）

List（链表）

List集合实例化

步骤：

1.导入java.util包

2.通过ArrayList类创造一个List对象

3.格式：List list = new List<>();

常用方法

ArrayList是一个可以动态修改的数组，于普通数组的区别是没有固定大小的限制，我们可以添加或删除元素

1.add(Object element):        像列表末尾添加指定元素2.size():                                 返回列表中的元素个数3.get(int index):                    返回列表中指定位置的元素，index从0开始4.isEmpty():                           判断列表是否为空，为空返回true，负否则返回false5.contains():                          如果列表包含指定元素，则返回true6.remove(int index):              移除列表中指定位置的元素，并返回被删除的元素

List集合特点

1.元素的添加顺序于取出顺序是一致的，并且可以重复

2.每个元素都有其对应的舒徐索引（从0开始）

3.可以根据喜好存取容器中的元素

排序

数组排序

Arrays.sort(int[] arr)对数组arr进行排序（默认升序）

    Integer[] arr = {1,2,3,4,5,1,5,6,2};//升序Arrays.sort(arr);System.out.println(Arrays.toString(arr));//降序Arrays.sort(arr, new Comparator<Integer>(){@Overridepublic int compare(Integer o1, Integer o2){return o2 - o1;}});System.out.println(Arrays.toString(arr));//第二种模式，上面的简写Integer[] arr = {1,2,3,4,5,1,5,6,2};//升序Arrays.sort(arr, (a,b)->a-b);System.out.println(Arrays.toString(arr));//降序Arrays.sort(arr, (a,b)->b-a);System.out.println(Arrays.toString(arr));

集合排序

Collections.sort(List<> arr)

ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(4);list.add(3);list.add(4);list.add(5);list.add(4);//升序Collections.sort(list);System.out.println(list);//降序Collections.sort(list, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});System.out.println(list);//第二种模式，上面的简写
ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(4);list.add(3);list.add(4);list.add(5);list.add(4);//升序Collections.sort(list, (a,b)->a-b);System.out.println(list);//降序Collections.sort(list, (a,b)->b-a);System.out.println(list);

Set集合（集合）

Set的定义

是一个不允许出现重复元素，并且无序的集合，主要有HashSet类

在判断重复元素的时候，Set集合会调用hashCode()和equal()的方法来实现

注重独一无二的性质，该体系集合可以知道某物是否已经存在于集合中，不会存储重复的元素

用于存储无序的元素，值不能重复

特点：

1.可以用来去重

2.元素无序

HashSet类

定义：

Set<Integer> set = new HashSet<>();
Set<String> set = new HashSet<>();

1.实现了Set接口

2.无序，疾病和记录插入地方顺序

3.不允许有重复元素的集合

4.谓语java.util包里面，需要引入

常用方法

Set<Integer> set = new HashSet<>();
boolean a =  set.add(1);
boolean b =  set.add(1);
System.out.println(a);//true
System.out.println(b);//false
Set<Integer> set = new HashSet<>();
boolean a =  set.add(1);    
boolean b =  set.add(1);
System.out.println(set.size());//1
boolean c =  set.add(2);
System.out.println(set.size());//2
System.out.println(a+" "+b);   //true false
System.out.println(a+" "+c);   //true true
Set<Integer> set = new HashSet<>();
set.add(1);
boolean a = set.remove(1);
boolean b = set.remove(5);
System.out.println(a+" "+b);//true false
Set<Integer> set = new HashSet<>();
set.add(1);
boolean a = set.contains(1);
boolean b = set.contains(5);        
System.out.println(a+" "+b);//true false
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);
System.out.println(set.size());//3
set.clear();
System.out.println(set.size());//0

Map（键值对集合）

Map集合实例化

步骤

1.导包，导入java.util.Map

2.通过HashMap实现类创造对象

3.语法格式:

Map<引用数据类型，引用数据类型> map = new HashMap<>();

特点:

1.HashMap是一个散列表，它存储的内容师键值对(key-value)映射。

2.HashMap实现了Map接口，根据键的HashMap值存储数据，具有很快的访问速度，最多允许一条记录的键为null，不支持线程同步

3.HashMap是无序的，既不会记录插入的顺序

常用方法

HashMap<Integer,Integer> map = new HashMap<>();map.put(key, value);//在 Map 中添加一对键值对，如果 key 已存在则会覆盖原有的 value 值map.get(key);//根据 key 获取 value，如果 key 不存在则返回 null。int size = map.size();//获取 Map 的大小（即键值对的数量）Set<map.Entry<String, Integer>> entrySet = map.entrySet();//作用是为了遍历Map集合//返回 Map 中所有键值对组成的 Set 集合，其中每个元素都是一个 Map.Entry 对象，包含 key 和 value 两部分。// 遍历 entrySet，获取每个键值对并处理for (Map.Entry<String, Integer> entry : entrySet) {String key = entry.getKey();Integer value = entry.getValue();// 处理键值对System.out.println("Key: " + key + ", Value: " + value);}int value = map.getOrDefault(key,defaultVaule);//如果存在第一个参数（key）对应的Value，那么九江Value赋值给value，反之将defaulValue赋给value

Stack（栈）

Stack的实例化

步骤:

1.导包，导入java.util.Stack

2.实例化对象，格式:

Stack stack = new Stack<>();

特点:

先进后出

常用方法

Stack<Object> stack = new Stack<>();
stack.push(Object element);  // 向栈中压入元素
stack.pop();  // 从栈中弹出（移除）并返回栈顶元素
stack.peek();  // 返回栈顶元素，但不弹出（移除）
stack.isEmpty();  // 检查栈是否为空
int element = stack.get(index); // 获取索引为1的元素，即栈顶元素下面的元素
element = stack.elementAt(index); // 获取索引为2的元素，即栈顶元素下面的元素又下面的元素
int size = stack.size(); // 获取栈中元素的个数
// 在栈中查找元素o的位置(从栈顶往下数),如果，没有这个元素，则返回1
int position = stack.search(Object o);

Queue（队列）

队列的实例化

步骤:

1.导包，导入java.util.Queue;

2.通过LinkList类创造对象

Queue queue = new LinkedList<>();

特点：

先进先出

常用方法

queue.add(Objects element);//添加元素
queue.poll();              //取出元素
queue.peek();              //获取头部元素，不取出
queue.isEmpty();           //判断队列是否为空
//将元素添加到队列的末尾，并返回 true。如果队列已满，该方法会立即返回 false。
queue.offer(Objects o);
//移除并返回队列的头部元素。如果队列为空，该方法会抛出 NoSuchElementException 异常
queue.remove();
//element()：返回队列的头部元素，但不会将其移除。如果队列为空，该方法会抛出 NoSuchElementException 异常。
queue.element();
//移除队列中的所有元素。
queue.clear();

例题

数位排序

https://www.lanqiao.cn/problems/2122/learning/page=1&first_category_id=1&name=%E6%95%B0%E4%BD%8D%E6%8E%92%E5%BA%8F

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] arr = new int[n][2];for (int i = 0; i < n; i++){arr[i][0] = i+1;String s = arr[i][0]+"";for (int k = 0; k < s.length(); k++){arr[i][1] += s.charAt(k) - '0';}}Arrays.sort(arr, (o1,o2)->(o1[1] == o2[1]?o1[0]-o2[0]:o1[1]-o2[1]));System.out.println(arr[m-1][0]);}
}

顺子日期

https://www.lanqiao.cn/problems/2096/learning/page=1&first_category_id=1&name=%E9%A1%BA%E5%AD%90%E6%97%A5%E6%9C%9F

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);HashMap<Integer,Integer> map = new HashMap<>();map.put(1,31);map.put(2,29);map.put(3,31);map.put(4,30);map.put(5,31);map.put(6,30);map.put(7,31);map.put(8,31);map.put(9,30);map.put(10,31);map.put(11,30);map.put(12,31);int count = 0;for (int i = 1; i <= 12; i++){for (int k = 1; k <= map.get(i); k++){String month = String.format("%02d", i);String day = String.format("%02d", k);String str = "2022"+month+day;if (str.indexOf("012")!=-1||str.indexOf("123")!=-1||str.indexOf("234")!=-1||str.indexOf("345")!=-1||str.indexOf("456")!=-1||str.indexOf("567")!=-1||str.indexOf("678")!=-1||str.indexOf("789")!=-1){count++;}}}System.out.println(count);}
}

小明和完美序列

https://www.lanqiao.cn/problems/3199/learning/page=1&first_category_id=1&name=%E5%AE%8C%E7%BE%8E%E5%BA%8F%E5%88%97

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++)arr[i] = sc.nextInt();Arrays.sort(arr);int ans = 1; // 连续的长度int count = 0;//要删除的个数HashMap<Integer, Integer> map = new HashMap<>();int temp = arr[0];for (int i = 1; i < n; i++){int m = arr[i];if (m == temp){ans++;}else {map.put(temp, ans);ans = 1;}temp = m;}map.put(temp, ans);ans = 1;for (Map.Entry<Integer, Integer> entry : map.entrySet()){Integer k = entry.getKey();//数Integer v = entry.getValue();//长度if (k > v) count += v;else if(k < v) count += v - k;}System.out.println(count);}
}

总结

这里对文章进行总结：
以上就是今天要讲的内容，本文仅仅是万里长征的第一步，以后面临的困难还有很多，希望我能坚持下来，温故而知新，克服万难排除艰险，去争取胜利！
与诸君共勉，请各位监督。