【数据结构】蓝桥杯常见习题(一)

简介: 【数据结构】蓝桥杯常见习题(一)

1.ArrayList 动态数组


ArrayList 是 Java 中的一个类,它实现了 List 接口,是一个动态数组。它可以自动扩容、支持泛型、支持随机访问等特性。

动态数组是一种可以自动调整大小的数组。当数组满了之后,动态数组会自动扩容,以容纳更多的元素。相比于普通的数组,动态数组的容量是可以动态调整的,因此更加灵活和方便。


ArrayList 的常用方法包括:


add(E e):向列表的末尾添加一个元素。

add(int index, E element):在列表的指定位置插入指定元素。

get(int index):返回列表中指定位置的元素。

set(int index, E element):用指定元素替换列表中指定位置的元素。

remove(int index):删除列表中指定位置的元素。

size():返回列表中的元素数。


import java.util.ArrayList;
public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        list.add("apple");
        list.add("banana");
        list.add("orange");
        System.out.println("List size: " + list.size()); // 输出:List size: 3
        System.out.println("Element at index 1: " + list.get(1)); // 输出:Element at index 1: banana
        list.remove(1);
        System.out.println("List size after removing element at index 1: " + list.size()); // 输出:List size after removing element at index 1: 2
    }
}


2.链表LinkedList


Java中的链表是一种数据结构,它由节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以分为单向链表、双向链表和循环链表。

在Java中,可以使用Java集合框架提供的LinkedList类来实现链表。LinkedList类实现了List接口和Deque接口,因此它既可以作为列表使用,也可以作为队列或栈使用。LinkedList类内部实现了链表的操作,例如添加、删除、插入和遍历等。


使用LinkedList类时,需要注意以下几点:


LinkedList类是线程不安全的,如果需要在多线程环境下使用,可以使用并发包中的ConcurrentLinkedDeque类。

操作LinkedList时,需要考虑链表的头和尾部。在头部添加元素可以使用addFirst()方法,在尾部添加元素可以使用addLast()方法。

遍历LinkedList时,可以使用Iterator或foreach循环。在使用Iterator时,需要在循环体中调用next()方法获取下一个元素。

LinkedList类还提供了一些其他的方法,例如getFirst()、getLast()、removeFirst()和removeLast()等,可以根据实际需求选择使用。


下面是一个简单的示例代码,演示如何使用LinkedList类实现链表:

import java.util.LinkedList;
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        System.out.println(list);
        list.addFirst("first");
        list.addLast("last");
        System.out.println(list);
        list.removeFirst();
        list.removeLast();
        System.out.println(list);
        for (String s : list) {
            System.out.println(s);
        }
    }
}

输出结果:

[hello, world, java]
[first, hello, world, java, last]
[hello, world, java]
hello
world
java


例题:约瑟夫环模拟

import java.util.*;
public class LinkedListDemo {
    public static void main(String[] args) {
        int n = 7; // 约瑟夫环总人数
        int m = 3; // 数到第几个人出圈
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        System.out.println("初始链表:" + list);
        int count = 0;
        int index = 0;
        while (list.size() > 1) {
            int num = list.get(index);
            count++;
            if (count == m) {
                list.remove(index);
                System.out.println("出圈的人:" + num);
                count = 0;
            } else {
                index++;
            }
            if (index >= list.size()) {
                index = 0;
            }
        }
        System.out.println("剩余的人:" + list.get(0));
    }
}

运行结果:

初始链表:[1, 2, 3, 4, 5, 6, 7]
出圈的人:3
出圈的人:6
出圈的人:2
出圈的人:7
出圈的人:5
出圈的人:1
剩余的人:4


说明:


首先创建一个LinkedList对象,用来存放约瑟夫环中的人;
循环添加n个人到链表中;
如果链表中还有人,则继续循环;
每次数到第m个人,就将该人从链表中移除,并输出该人的编号;
如果链表中的当前位置已经是最后一个元素,则将当前位置重置为0;
最终剩下的一个人即为约瑟夫环的胜利者。


3.栈Stack


栈(Stack)是一种线性数据结构,它支持在一端进行插入和删除操作,这一端被称为栈顶。栈遵循先进后出(Last In First Out,LIFO)的原则,即最后进栈的元素最先出栈,而最先入栈的元素最后出栈。

push(Object element): 将元素压入栈顶
pop(): 弹出栈顶元素并返回,如果栈为空则抛出异常
peek(): 返回栈顶元素但不弹出,如果栈为空则抛出异常
empty(): 判断栈是否为空
search(Object element): 查找元素在栈中的位置,如果不存在则返回-1
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");
        stack.push("JavaScript");
        System.out.println("栈: " + stack);
        System.out.println("栈顶元素: " + stack.peek());
        stack.pop();
        System.out.println("弹出元素后的栈: " + stack);
    }
栈: [Java, Python, C++, JavaScript]
栈顶元素: JavaScript
弹出元素后的栈: [Java, Python, C++]


4.队列Queue


Java中的Queue接口是一个队列数据结构的抽象表示。它定义了以下方法:

add(E e): 将元素e添加到队列末尾,如果队列已满则抛出异常。
offer(E e): 将元素e添加到队列末尾,如果队列已满则返回false。
remove(): 返回队列头部元素并将其从队列中删除,如果队列为空则抛出异常。
poll(): 返回队列头部元素并将其从队列中删除,如果队列为空则返回null。
element(): 返回队列头部元素但不删除,如果队列为空则抛出异常。
peek(): 返回队列头部元素但不删除,如果队列为空则返回null。

此外,Queue接口还继承了Collection接口中的一些方法,如size()、isEmpty()、contains(Object o)等。

  public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        // 向队列中添加元素
        queue.add("John");
        queue.add("Brad");
        queue.add("Angelina");
        queue.add("Julia");
        System.out.println("队列中的元素: " + queue);
        // 从队列中删除元素
        String name = queue.remove();
        System.out.println("删除的元素: " + name);
        System.out.println("删除元素后队列中的元素: " + queue);
        // 访问队列中的元素
        String element = queue.peek();
        System.out.println("队列头部的元素: " + element);
        // 队列的大小
        int size = queue.size();
        System.out.println("队列的大小: " + size);
    }
队列中的元素: [John, Brad, Angelina, Julia]
删除的元素: John
删除元素后队列中的元素: [Brad, Angelina, Julia]
队列头部的元素: Brad
队列的大小: 3


5.集合HashSet——去重


HashSet是Java集合框架中的一种实现,它基于哈希表实现,能够快速地查找、插入和删除元素,其常用方法如下:

add(Object o):将指定元素添加到集合中,如果该元素已经存在于集合中,则不会再次添加。
remove(Object o):从集合中移除指定元素。
size():返回集合中元素的数量。
clear():清空集合中的所有元素。
contains(Object o):判断集合中是否包含指定元素。
isEmpty():判断集合是否为空。
toArray():将集合转化为数组。
iterator():返回集合的迭代器,用于遍历集合中的所有元素。

除了以上常用方法外,HashSet还有一些其他方法,如:

hashCode():返回该集合的哈希码值。
equals(Object o):判断该集合是否与指定对象相等。
retainAll(Collection c):从集合中保留指定集合中包含的元素,其余元素将被移除。
removeAll(Collection c):从集合中移除指定集合中包含的元素。
containsAll(Collection c):判断集合是否包含指定集合中的所有元素。
addAll(Collection c):将指定集合中的所有元素添加到该集合中。

总之,HashSet提供了丰富的方法来操作集合中的元素,具有高效、快速的特点。

  public static void main(String[] args) {
        HashSet<String> set = new HashSet<String>();
        set.add("element1");
        set.add("element2");
        set.add("element3");
        set.add("element1");
        System.out.println(set);
        set.remove("element2");
        System.out.println(set);
        System.out.println("元素1是否在集合中? " + set.contains("element1"));
        System.out.println("集合大小: " + set.size());
        set.clear();
        System.out.println(set);
        System.out.println("集合是否为空? " + set.isEmpty());
    }
[element1, element2, element3]
[element1, element3]
元素1是否在集合中? true
集合大小: 2
[]
集合是否为空? true


6.HashMap——存放键值对


HashMap 是 Java 中的一个集合类,它用来存储键值对。它实现了 Map 接口,可以存储不同类型的键和值,并且允许 null 值。在 HashMap 中,键是唯一的,值可以重复。

HashMap 中最常用的方法包括:

put(key, value):将键值对添加到 HashMap 中。
get(key):获取指定键对应的值。
remove(key):删除指定键对应的键值对。
containsKey(key):判断 HashMap 是否包含指定的键。
keySet():返回 HashMap 中所有键组成的 Set 集合。
    public static void main(String[] args) {
        // 创建一个名为capitalCities的HashMap对象
        HashMap<String, String> capitalCities = new HashMap<String, String>();
        // 添加键和值(国家,城市)
        capitalCities.put("England", "London");
        capitalCities.put("Germany", "Berlin");
        capitalCities.put("Norway", "Oslo");
        capitalCities.put("USA", "Washington DC");
        // 通过使用键访问值
        System.out.println("英格兰的首都是 " + capitalCities.get("England"));
        // 删除一个键和值
        capitalCities.remove("Norway");
        // 打印键
        System.out.println("键: " + capitalCities.keySet());
        // 检查一个键是否在HashMap中
        System.out.println("capitalCities是否包含Norway作为键? " + capitalCities.containsKey("Norway"));
    }
英格兰的首都是 London
键: [USA, England, Germany]
capitalCities是否包含Norway作为键? false


getOrDefault 是 Map 接口提供的一个方法,用于获取 Map 中指定键对应的值,如果该键不存在,则返回一个默认值:

getOrDefault(Object key, V defaultValue);

其中,key 表示要获取的键,defaultValue 表示默认值。如果 Map 中存在 key,则返回该 key 对应的值;否则,返回 defaultValue。

示例:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);
// 获取存在的键对应的值
int value1 = map.getOrDefault("apple", 0); // 返回 1
int value2 = map.getOrDefault("banana", 0); // 返回 2
// 获取不存在的键对应的默认值
int value3 = map.getOrDefault("pear", 0); // 返回 0


注意:getOrDefault 方法只是获取 Map 中指定键对应的值,不会修改 Map 中的数据。如果需要修改 Map 中的数据,请使用 put 方法。


7.TreeSet - 带排序的集合


TreeSet 是 Java 中的一个集合类,它实现了 SortedSet 接口,可以存储元素,并按照元素的自然顺序或指定的比较器顺序进行排序。

TreeSet 的主要方法包括:

add(E e):将指定的元素添加到集合中。
clear():从集合中移除所有元素。
contains(Object o):判断集合是否包含指定的元素。
first():返回集合中的第一个元素。
last():返回集合中的最后一个元素。
remove(Object o):从集合中移除指定的元素。
size():返回集合中的元素个数。
toArray():将集合转换为数组。

使用 TreeSet 时,需要注意以下几点:

TreeSet 中的元素必须实现 Comparable 接口,或者在创建 TreeSet 时提供一个 Comparator 比较器。
TreeSet 中的元素必须是可比较的,否则将抛出 ClassCastException 异常。
TreeSet 中的元素不允许为 null 值,否则将抛出 NullPointerException 异常。
TreeSet 中的元素是按照元素的自然顺序或指定的比较器顺序进行排序的。
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<String>();
        treeSet.add("apple");
        treeSet.add("orange");
        treeSet.add("banana");
        treeSet.add("cool");
        treeSet.add("dodo");
        System.out.println(treeSet);
      }


[apple, banana, cool, dodo, orange]

目录
相关文章
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
6月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
43 2
|
6月前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
79 1
|
6月前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
48 1
|
6月前
|
机器学习/深度学习
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
42 1
|
6月前
|
算法
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
39 0
|
6月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
38 0
|
6月前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
38 0
|
6月前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
36 0