数据结构(Java版)第四期:ArrayLIst和顺序表(上)

目录

一、顺序表

1.1. 接口的实现

二、ArrayList简介

2.1. ArrayList的构造

2.2. ArrayList的常见操作

2.3. ArrayList的扩容机制 

三、ArrayList的具体使用

3.1. 洗牌算法

3.2. 杨辉三角


一、顺序表

       上一期我们讲到过,顺序表本质上和数组是差不多的,只不过数组只能访问或修改某个元素,而作为顺序表,需要实现更多的功能。

1.1. 接口的实现

 //新增元素,默认在数组最后新增
 
public void add(int data) {  }
 // 在pos位置新增元素
 
public void add(int pos, int data) {  }
 //判定是否包含某个元素
 
public boolean contains(int toFind) { return true; }
 //查找某个元素对应的位置
 
public int indexOf(int toFind) { return -1; }
 //获取pos位置的元素
 
public int get(int pos) { return -1; }
 // 给pos位置的元素设为
 value 
public void set(int pos, int value) {    
//删除第⼀次出现的关键字key 
public void remove(int toRemove) {    
// 获取顺序表⻓度
 
public int size() { return 0; }
//清空顺序表
 
public void clear() {    
}

二、ArrayList简介

2.1. ArrayList的构造

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //第一种方式,创建ArrayList对象,构造空的顺序表
        ArrayList<String> arrayList1 = new ArrayList<>();

        //第二种方式
        List<String> list = new ArrayList<>();
    }
}

      其中ArrayList里面,也是实现了List的接口。也就是说,我们完全可以通过向上转型,把List引用指向ArrayList的实例。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

       我们来看下面两段代码的,两个都是构造空的顺序表,二者有什么区别呢?第一个是创建了一个盒子,盒子里面为空,而第二个却连盒子都没有。

ArrayList<String> arrayList1 = new ArrayList<>();
ArrayList<String> arrayList2 = null;
//使用arrayList1复制一份,生成arrayList3
ArrayList<String> arrayList3 = new ArrayList<>(arrayList1);
//构造的同时,可以去指定初始容量
ArrayList<String> arrayList4 = new ArrayList<>(10);

        当前构造出来的ArrayList初始容量为10,这里与数组的区别是:数组我们在一开始就规定好了它的容量,不能在进行修改了;而ArrayList的容量可以进行动态扩容,只要机器内存允许,就能一直扩容,把想要的元素容纳进去。

2.2. ArrayList的常见操作

(1)add尾插操作 

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        System.out.println(list);
    }
}

(2)获取元素个数

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //获取元素个数,数组提供了.length属性获取到元素个数,集合类提供了size()方法获取元素个数
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        System.out.println(list.size());
    }
}

      事实上,不仅是List,只要是集合类,都可以通过.size来获取长度。

(3)ArrayList的访问和修改

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //获取或者设置list中的元素
        
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");//进行了自动扩容
        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(2));
        System.out.println(list.get(3));
        System.out.println(list.get(4));
    }
}

        如果我们运行一下,此时也会出现下标越界访问的异常。 

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //获取或者设置list中的元素

        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");//进行了自动扩容

        list.set(0,"eee");
        System.out.println(list);
    }
}

(4)ArrayList的遍历

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");

        //遍历是可能会进行各种操作的,不一定是打印
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        //for-each写法
        for (String s : list) {
            System.out.print(s+" ");
        }
    }
}

       并不是所有的类都能写进for-each里面,要求这个类必须能够实现Iterable接口。实现Iterable接口中的iterator方法,得到一个迭代器对象,进行近一步循环遍历。

public interface List<E> extends Collection<E>
public interface Collection<E> extends Iterable<E> 
Iterator<E> iterator();

      迭代也是计算机中的专业术语,可以理解成“逐渐接近目标”。集合类中用到迭代。上面的for-each循环,我们可以看作是以下代码的简化。

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
        System.out.println(iterator.next());
}

          hasNext用于判断有没有下一个元素,iterator.next用于取出当前元素,并准备下一个元素。hasNext的工作机理可以如下图所示,按照箭头从上到下依次去遍历。

(5)其他的一些操作

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //通过contains判读元素是否存在
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ccc");
        list1.add("ccc");
        list1.add("ddd");
        System.out.println(list1.contains("aaa"));
        //通过indexOf获取元素第一次出现的位置
        System.out.println(list1.indexOf("ccc"));
        //通过lastIndexOf获取元素最后一次出现的位置
        list1.lastIndexOf("ccc");
        main1(args);
        main2(args);
        main3(args);
    }
    public static void main3(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ddd");

        //按照元素内删除
        list1.remove("ddd");
        System.out.println(list1);
    }
    public static void main2(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ddd");

        //按照下标删除元素
        list1.remove(2);
        System.out.println(list1);
    }
    public static void main1(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ddd");

        //在任意位置添加元素
        list1.add(1,"eee");
        System.out.println(list1);
    }
}

2.3. ArrayList的扩容机制 

       当ArrayList内存不够时,就会自动申请额外的内存空间。ArrayList内部持有一个数组,设置的初始容量相当于数组的大小。比如说我们初始容量为10,当循环到第11次的时候,发现元素已经满了;add真正写进元素之前,就要创建一个更大的数组。新的数组要把旧的数组里的元素添加进来,新的元素也要添加进新的数组里面,原来旧的数组要进行释放。

三、ArrayList的具体使用

3.1. 洗牌算法

       问题描述:现有一副扑克牌,对其进行洗牌。

      我们先来定义一个Card类,用来表示一张扑克牌。

class Card {
    public String suit;//表示花色
    public String rank;//表示点数

    public Card(String suit, String rank) {
        this.suit = suit;
        this.rank = rank;
    }

    public String getSuit() {
        return suit;
    }

    public void setSuit(String suit) {
        this.suit = suit;
    }

    public String getRank() {
        return rank;
    }

    public void setRank(String rank) {
        this.rank = rank;
    }

    @Override
    public String toString() {
        return this.suit+this.rank;
    }
}

     接下来要先把Card这个对象实例化,并用ArrayList把所有的牌添加进去。

public class Main {
    public static void main(String[] args) {
        //使用ArrayList表示一副扑克牌
    }
    public static ArrayList<Card> CreateDeck() {
        //创建一副扑克牌
        ArrayList<Card> deck = new ArrayList<>();
        String[] suits = {"♠","♦","♥","♣"};
        //通过两层for循环,第一层先循环花色,第二层在循环点数
        //每个花色中,生成对应的点数
        for (String suit:suits){
            for (int i = 2; i <= 10; i++) {
                Card cardNum = new Card(suit,""+i);
                deck.add(cardNum);//添加到扑克牌中
            }

            Card cardJ = new Card(suit,"J");
            Card cardQ = new Card(suit,"Q");
            Card cardK = new Card(suit,"K");
            Card cardA = new Card(suit,"A");
            deck.add(cardJ);
            deck.add(cardQ);
            deck.add(cardK);
            deck.add(cardA);
        }
        return deck;
    }
}

       然后我们调用CreateDeck方法,对这副牌进行一个打印。

public class Main {
    public static void main(String[] args) {
        //使用ArrayList表示一副扑克牌
        ArrayList<Card> deck = CreateDeck();
        System.out.println(deck);
    }
}

      接下来是进行洗牌的操作,在Java标准库中,提供了进行洗牌的方法shuffle。 

import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        //使用ArrayList表示一副扑克牌
        ArrayList<Card> deck = CreateDeck();
        System.out.println("原始牌组:"+deck);
        //洗牌
        Collections.shuffle(deck);
        System.out.println("洗牌之后:"+deck);
    }
}

      我们也可以自己写一个方法,来进行洗牌。

    public static void shuffle(ArrayList<Card> deck){
        //把整个ArrayList从后往前遍历
        //每次取一张牌,生成一个随机下标,用当前的拍和随机下标的牌进行交换
        Random random = new Random();
        for (int i = deck.size(); i >0 ; i--) {
            int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)
            //交换操作
            Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标,不能交换的时候发生修改
            deck.set(i, deck.get(j));
            deck.set(j, tmp);
        }
    }

      下面是发牌,一共有3个人,每个人发5张牌。我们可以看成一个3行5列的一个二维数组。

        ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组
        //先创建 3 个人手里的牌
        for (int i = 0; i < 3; i++) {
            ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌
            hands.add(hand);//发到每个人手里
            //已经添加了3个元素进去,但还是长度为0的ArrayList
        }

       最后是发牌的过程。

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                //发牌是轮流的过程.
                ArrayList<Card> currentHand = hands.get(j);
                Card card = deck.remove(0);
                currentHand.add(card);
                //一次循环,相当于取出一张牌交给玩家
            }
        }

 完整代码:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

class Card {
    public String suit;//表示花色
    public String rank;//表示点数

    public Card(String suit, String rank) {
        this.suit = suit;
        this.rank = rank;
    }

    public String getSuit() {
        return suit;
    }

    public void setSuit(String suit) {
        this.suit = suit;
    }

    public String getRank() {
        return rank;
    }

    public void setRank(String rank) {
        this.rank = rank;
    }

    @Override
    public String toString() {
        return this.suit+this.rank;
    }
}

public class Main {
    public static void main(String[] args) {
        //使用ArrayList表示一副扑克牌
        ArrayList<Card> deck = CreateDeck();
        System.out.println("原始牌组:"+deck);
        //洗牌
        //Collections.shuffle(deck);
        System.out.println("洗牌之后:"+deck);

        ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组
        //先创建 3 个人手里的牌
        for (int i = 0; i < 3; i++) {
            ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌
            hands.add(hand);//发到每个人手里
            //已经添加了3个元素进去,但还是长度为0的ArrayList
        }
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                //发牌是轮流的过程.
                ArrayList<Card> currentHand = hands.get(j);
                Card card = deck.remove(0);
                currentHand.add(card);
                //一次循环,相当于取出一张牌交给玩家
            }
        }
        //打印每个人的手牌
        for (int i = 0; i < 3; i++) {
            System.out.println("第"+i+"个人的手牌"+hands.get(i));
        }
    }

    public static void shuffle(ArrayList<Card> deck){
        //把整个ArrayList从后往前遍历
        //每次取一张牌,生成一个随机下标,用当前的拍和随机下标的牌进行交换
        Random random = new Random();
        for (int i = deck.size(); i >0 ; i--) {
            int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)
            //交换操作
            Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标,不能交换的时候发生修改
            deck.set(i, deck.get(j));
            deck.set(j, tmp);
        }
    }
    public static ArrayList<Card> CreateDeck() {
        //创建一副扑克牌
        ArrayList<Card> deck = new ArrayList<>();
        String[] suits = {"♠","♦","♥","♣"};
        //通过两层for循环,第一层先循环花色,第二层在循环点数
        //每个花色中,生成对应的点数
        for (String suit:suits){
            for (int i = 2; i <= 10; i++) {
                Card cardNum = new Card(suit,""+i);
                deck.add(cardNum);//添加到扑克牌中
            }

            Card cardJ = new Card(suit,"J");
            Card cardQ = new Card(suit,"Q");
            Card cardK = new Card(suit,"K");
            Card cardA = new Card(suit,"A");
            deck.add(cardJ);
            deck.add(cardQ);
            deck.add(cardK);
            deck.add(cardA);
        }
        return deck;
    }
}

3.2. 杨辉三角

      问题描述:给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。在「杨辉三角」中,每个数是它左上方和右上方的数的和。

示例 1: 输入: numRows = 5  输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2: 输入: numRows = 1 输出: [[1]]

       通过上面的图,我们可以总结出以下规律:1.第i行有i+1个列(因为要用二维数组解决,所以把第一行定义第0行);2.每一行的第一列和最后一列都是1;3.第i行第j列的元素 = 第i-1行第j-1列的元素 + 第i-1行第j列的元素。

完整代码: 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public List<List<Integer>> generate(int numRows) {
        //先写一个表示结果的二维数组
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        //先来构造行
        for (int i = 0; i < numRows; i++) {
            List<Integer> rows = new ArrayList<>();//用到了向上转型。需要往这一行里面里面添加元素
            for (int j = 0; j < i+1; j++) {
                if (j==0 || j==i){
                    rows.add(1);
                } else {
                    List<Integer> prevRow = result.get(i - 1);
                    int current = prevRow.get(j - 1) + prevRow.get(j);
                    rows.add(current);
                }
            }
            //一行构造好了之后,把这一行添加到result中
            result.add(rows);
        }
        return result;
    }

    public static void main(String[] args) {
        Main m = new Main();
        Scanner num = new Scanner(System.in);
        int b = num.nextInt();
        List<List<Integer>> result = m.generate(b);
        System.out.println(result);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/956971.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

阿里云 Serverless 助力盟主直播:高并发下的稳定性和成本优化

在直播场景中&#xff0c;阿里云 Serverless 应用引擎 SAE 提供的无缝弹性伸缩与极速部署能力&#xff0c;确保直播间高并发时的流畅体验&#xff0c;降低了我们的运营成本&#xff0c;简化了运维流程。结合阿里云云原生数据库 PolarDB 的 Serverless 能力&#xff0c;实现了数…

【机器学习实战入门】基于深度学习的乳腺癌分类

什么是深度学习&#xff1f; 作为对机器学习的一种深入方法&#xff0c;深度学习受到了人类大脑和其生物神经网络的启发。它包括深层神经网络、递归神经网络、卷积神经网络和深度信念网络等架构&#xff0c;这些架构由多层组成&#xff0c;数据必须通过这些层才能最终产生输出。…

Qt之QDjango-db的简单使用

QDjango是一款由C编写、依托于Qt库的Web开发框架&#xff0c;其设计理念受到了广受欢迎的Python框架Django的影响。这个项目旨在提供一个高效、灵活且易于使用的工具集&#xff0c;帮助开发者构建高质量的Web应用。其项目地址: https://gitcode.com/gh_mirrors/qd/qdjango&…

[2025分类时序异常检测指标R-AUC与VUS]

梳理了一下分类中常见的指标&#xff0c;这些指标与时序异常检测中新提出的A-RUC与VUS之间的关系 真正例(True Positive,TP): 被正确识别为正样本的数量。真负例(True Negative,TN): 被正确识别为负样本的数量。假正例(False Positive ,FP): 被错误识为正样本数量假负例(Fals…

python3GUI--仿崩坏三二次元登录页面(附下载地址) By:PyQt5

文章目录 一&#xff0e;前言二&#xff0e;预览三&#xff0e;实现方案1.实现原理1.PyQt52. 具体实现 2.UI设计1.UI组件化、模块化2.UI设计风格思路 3.项目代码结构4.使用方法3.代码分享1.支持跳转网页的QLabel组件2.三角形ICON按钮 四&#xff0e;总结 大小&#xff1a;33.3 …

STM32 FreeRTOS中断管理

目录 FreeRTOS的中断管理 1、STM32中断优先级管理 2、FreeRTOS任务优先级管理 3、寄存器和内存映射寄存器 4、BASEPRI寄存器 5、FreeRTOS与STM32中断管理结合使用 vPortRaiseBASEPRI vPortSetBASEPRI 6、FromISR后缀 7、在中断服务函数中调用FreeRTOS的API函数需注意 F…

如何在idea中搭建SpringBoot项目

如何在idea中快速搭建SpringBoot项目 目录 如何在idea中快速搭建SpringBoot项目前言一、环境准备&#xff1a;搭建前的精心布局 1.下载jdk &#xff08;1&#xff09;安装JDK&#xff1a;&#xff08;2&#xff09;运行安装程序&#xff1a;&#xff08;3&#xff09;设置安装…

Linux:expect spawn简介与用法

一、背景 大家在使用linux系统的很多时候&#xff0c;都用linux指令来实现一些操作&#xff0c;执行特定的job&#xff0c;有时一些场景中需要执行交互指令来完成任务&#xff0c;比如ssh登录这个命令大家一定很熟悉&#xff1a; ssh-keygen -t rsa # 以及 ssh-copy-id -i /hom…

服务器硬盘RAID速度分析

​ 在现代数据中心和企业环境中&#xff0c;服务器的存储性能至关重要&#xff0c;RAID&#xff08;独立磁盘冗余阵列&#xff09;技术通过将多块硬盘组合成一个逻辑单元&#xff0c;提供了数据冗余和性能优化&#xff0c;本文将详细探讨不同RAID级别对服务器硬盘速度的影响&am…

Android开发与网络请求

目标:快速开发一个安卓页面(用户登录&跳转) 抓包就是在后端逻辑与API之间截取信息。 1.安卓UI和后台逻辑 1.1 安卓UI 将activity_main.xml文件中的代码替换后,将会得到上面的UI界面 <?xml version="1.0" encoding="utf-8"?> <Linear…

【Linux】利用‘shell脚本’快速查看linux服务器的基本信息

一、脚本目的 为了方便&#xff0c;当拿到一台linux服务器的时候&#xff0c;我们应首先了解服务器的硬件、操作系统信息。俗话说“工欲善其事必先利其器” 只有熟悉了自己的武器&#xff0c;才能更好的发挥武器的威力。所以写了一个shell脚本&#xff0c;方便快速获取服务器C…

Solana 套利机器人原理

引言 加密货币的交易世界中&#xff0c;套利是利用市场价格差异进行无风险获利的一种策略。随着 DeFi&#xff08;去中心化金融&#xff09;的快速发展&#xff0c;套利机会屡见不鲜&#xff0c;尤其是在高速、高效能的区块链上&#xff0c;如 Solana。这些区块链通过提供低交易…

麦田物语学习笔记:制作[SceneName]Attribute特性

基本流程 因为在现有的项目中,像开始场景的切换或者Telepot组件都需要手动输入场景名,有时还可能键入出错,而该特性能用选择的方式去解决这一问题 1.代码实现 SceneNameDrawer.cs //参数绘制 using UnityEditor; using UnityEngine; #if UNITY_EDITOR [CustomPropertyDrawer(…

OCP使用中的常见问题与解决方法

OCP的常见问题 页面卡顿&#xff1a; 遇到页面卡顿的问题时&#xff0c;首先需要区分是全局性的卡顿&#xff0c;即所有页面都出现延迟或响应缓慢&#xff0c;还是仅限于特定的监控页面。 监控数据看不到: 需要明确是全部数据都无法查看&#xff0c;还是仅限于特定集群的数…

大模型LLM-微调 RAG

RAG小结 这篇文章是一篇关于大型语言模型&#xff08;LLMs&#xff09;增强技术的综述论文&#xff0c;特别聚焦于检索增强生成&#xff08;Retrieval-Augmented Generation, RAG&#xff09;这一领域。详细考察了RAG的发展、技术基础、关键技术、评估框架以及未来的研究方向。…

51c~缺陷检测~合集2

我自己的原文哦~ https://blog.51cto.com/whaosoft/12386431 一、缺陷检测~使用深度学习1 这里研究工业ai, 在制造业中任何公司的主要目标都是为客户生产无缺陷产品。如果在产品开发过程中出现任何内部孔、凹坑、磨损或划痕&#xff08;由于多种原因&#xff0c;从生产设备…

25春秋杯wp

春秋杯 图片不显示的去我blog找&#x1f447; 25春秋杯 | DDLS BLOG 文章所有内容部分来自自己写的&#xff0c;部分来自各路非公开wp&#xff0c;部分来自公开wp(附上链接&#xff0c;在文章末尾) easy_flask {{().__class__.__mro__.__getitem__(1).__subclasses__()[13…

C# 事件(Event)详解

C# 事件详解 事件&#xff08;Event&#xff09;是 C# 中的一种特殊类型的委托&#xff0c;它是基于委托的基础上构建的&#xff0c;用来实现事件驱动编程。在 C# 中&#xff0c;事件常用于处理用户输入、系统通知、数据更新等场景&#xff0c;允许一个对象通知其他对象某些行…

三维扫描赋能文化:蔡司3D扫描仪让木质文化遗产焕发新生-沪敖3D

挪威文化历史博物馆在其修复工作中融入现代3D扫描技术&#xff0c;让数百年的历史焕发新生。 文化历史博物馆的工作 文化历史博物馆是奥斯陆大学的一个院系。凭借其在文化历史管理、研究和传播方面的丰富专业知识&#xff0c;该博物馆被誉为挪威博物馆研究领域的领先机构。馆…

Ubuntu 24.04 LTS 系统语言英文改中文

Ubuntu 24.04 LTS 修改软件源 Ubuntu 更改软件源 修改语言 无需输入命令&#xff0c;为Ubuntu 24.04系统添加中文智能拼音输入法 在 setting 的 system 中按下图操作 点击“Apply Changes”。需要管理员密码&#xff0c;安装完成后&#xff0c;退出登录&#xff0c;重新登…