ArrayList集合的两个实例应用,有趣的洗牌算法与杨辉三角

简介: ArrayList集合的两个实例应用,有趣的洗牌算法与杨辉三角



一、杨辉三角

这不是普通的杨辉三角,这是力扣里面的杨辉三角

1.题目详情及链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

有同学说,这里的题目也看不出跟ArrayList集合有鸡毛关系呀?我说,你别急,继续往下看

看到这里,你急了没有,题目给的类型是什么狗屎?这不就与ArrayList扯上关系了嘛,这到底是什么意思呢?接着往下看

2.剖析题目  

(1)题目的要求是根据参数,生成杨辉三角的前numRows行,并返回存放杨辉三角的空间

比如:numRows=3,就生成杨辉三角的前面3行;如果你用普通的二维数组存储,那就返回该二维数组的地址。

(2)剖析返回值

我们也应该可以猜到,List<List<Integer>>也是表示二维数组的意思

此时还不算完整的二维数组,List只是一个接口,需要实例化对象

(3)我们需要将这些数字放入该二维数组中

3.思路及代码

(1)思路解析

通过面向对象的思想来完成

第一步:分析杨辉三角的规律

题目要求生成杨辉三角的前numRows行,也就是可以一行一行生成

规律是显而易见的,除了第一行,其他每行的第一个元素和最后一个元素的值都是1;从第3行开始,中间的值与前一行的值紧密相连

第二步:创建二维数组并单独完成杨辉三角的第一行

不用担心测试用例一行都没有,1<=numRows<=30

List<List<Integer>> list = new ArrayList<>();
List<Integer> first = new ArrayList<>();
//先设置第一行的元素
first.add(1);
list.add(first);

核心思想:先单独建立一个一维的顺序表,存放好一行的元素,然后再将这个一维的顺序表当成一个元素放入二维的顺序表中,后面也是一样的思想

第三步:存放第二行及后面的元素

for (int i = 1; i < numRows; i++) {//每层循环代表一行
     List<Integer> ret = new ArrayList<>();//定义一个一维数组    
}

我们将在这个循环里面存放完成后续的行,如果只有一行,就不会进入这个循环内

第四步:分析如何将每一行存入

由前面分析知道,第二行开始,第一个和最后一个元素都是1,我们可以在前面和最后面存入1

for (int i = 1; i < numRows; i++) {//每层循环代表一行
            List<Integer> ret = new ArrayList<>();//定义一个一维数组
            //1.添加第一个元素
            ret.add(1);
            //2.设置中间元素,从第二列开始
           
            //3.添加最后元素
            ret.add(1);
            list.add(ret);//将每一行放入二维数组中
    }

然后中间的元素如何添加?第二行是没有中间元素的,而且中间的元素都是与前一行的元素有着紧密的关系,所以我们也需要考虑好。首先,我们需要从第二个位置开始存放;然后,第几行就说明那一行有多少个元素,就与行号绑定了关系

for (int i = 1; i < numRows; i++) {//每层循环代表一行
            List<Integer> ret = new ArrayList<>();//定义一个一维数组
            //1.添加第一个元素
            ret.add(1);
            //2.设置中间元素,从第二列开始
            for (int j = 1; j < i; j++) {
                //利用面向对象的思想,拿到元素
                int tmp = list.get(i-1).get(j)+list.get(i-1).get(j-1);
                ret.add(tmp);
            }
            //3.添加最后元素
            ret.add(1);
            list.add(ret);
        }

(2)完整代码

public List<List<Integer>> generate(int numRows) {
         List<List<Integer>> list = new ArrayList<>();
        List<Integer> first = new ArrayList<>();
        //先设置第一行的元素
        first.add(1);
        list.add(first);
        //从第二行开始
        for (int i = 1; i < numRows; i++) {//每层循环代表一行
            List<Integer> ret = new ArrayList<>();//定义一个一维数组
            //1.添加第一个元素
            ret.add(1);
            //2.设置中间元素,从第二列开始
            for (int j = 1; j < i; j++) {
                int tmp = list.get(i-1).get(j)+list.get(i-1).get(j-1);
                ret.add(tmp);
            }
            //3.添加最后元素
            ret.add(1);
            list.add(ret);
        }
        return list;
}

(3)总结一下思路

第一:将杨辉三角分成两个部分存储(第一行和第一行后面的

第二:存储第一行后面的时候,又分成三部分存储(第一个元素、中间部分元素、最后一个元素)

第三:存储中间部分元素时,通过与前一行的元素的关系进行存储(利用面向对象的思想获得前一行的元素)

二、洗牌算法

其实,洗牌算法就是ArrayList的一种应用,或者运用,没有那么的高大尚,下面简单介绍洗牌算法的一些基本功能和流程

下面是程序运行起来的结果:

什么是洗牌算法?

(1)使用类和对象的知识定义一个牌对象

(2)创造出一副排序好的牌,存储在ArrayList中(有牌)

(3)然后将这些牌的顺序打乱(洗牌)

(4)将洗乱的牌随机分发给三个人(发牌)

下面开始讲解洗牌算法

1.创造牌对象

牌这个对象的属性有两个:第一是花色,第二就是号码;然后我们提供一下构造方法,在创建每一张牌的时候就赋值;最后,重写一下toString方法,用来打印牌。

public class Card {
    //用来定义一张牌
    public String suit;//牌的花色
    public int num;//号码
    public Card(String suit, int num) {
        this.suit = suit;
        this.num = num;
    }
    @Override
    public String toString() {
       return suit+num;
    }
}
2.创造一副牌

main函数,用来实例化对象,和调用对象中的方法(创造牌的方法)

public static void main(String[] args) {
        PlayCard game = new PlayCard();
        System.out.println("设置牌:");
        List<Card> cards = game.setCard();
        System.out.println(cards);
}

创建一个类,用来表示玩牌的游戏,里面存放创建牌、洗牌和发牌的操作

public class PlayCard {
    
    public static final String[] suits = {"♠","♥","♣","♦"};//定义花色的数组
    //1.设置牌操作
    public List<Card> setCard() {
        List<Card> cards = new ArrayList<>();//定义一个数组,用来存放所有牌
        for (int i = 0; i < 4; i++) {//每次循环代表一个花色
            for (int j = 1; j <=13 ; j++) {//13个号码
                String suit = suits[i];//获得一个花色
                Card card = new Card(suit,j);//定义一个牌对象并赋值
                cards.add(card);//将牌放入一个牌数组中
            }
        }
        return cards;//返回一副牌
    }
}

(1)这是一个带返回值的函数。

(2)第一层循环,代表花色;第二层循环代码号码;每循环一次:拿到一个花色和号码,然后将这两个赋值给牌对象,并将牌放入ArrayList集合中(cards)

(3)最后将这个集合返回(接收返回值就拿到了返回值)

3.洗牌操作

这里先把上一阶段创造牌的操作隐藏,独将洗牌操作

这里洗牌的思想是:(1)从后面遍历这副牌,每张牌都随机与前面某一张牌交换

(2)获得前面随机牌使用产生随机数种子

(3)交换则单独包装成一个方法

public class PlayCard {
    //在这里类里面操作牌:设置牌,洗牌和发牌
    public static final String[] suits = {"♠","♥","♣","♦"};//定义花色的数组
    //1.设置牌操作
   //这里介绍洗牌操作,所以设置牌的操作就省略了
    //2.洗牌操作
    public void shuffle(List<Card> cards) {
        Random random = new Random();
        for (int i = 51; i > 0; i--) {
            int index  = random.nextInt(i);//随机获取一个牌下标与i下标的牌交换
            swap(cards,i,index);
        }
        //return cards;
    }
    private static void swap(List<Card> cards,int i,int j) {
        //交换两张牌
        Card tmp = cards.get(i);
        cards.set(i,cards.get(j));
        cards.set(j,tmp);
    }
}
4.发牌操作

同样的,我们把前面创造牌和洗牌的操作隐藏起来,单独介绍发牌操作

我们发牌的思路是:(1)有三个人轮流接牌,每次接一张,一共接五轮(2)每个人随机接牌,每拿到一张牌,就从这副牌中删除(3)每个人拿到五张牌,每个人看作一个一维数组;要保存三个人的牌,就需要一个二维数组。

public class PlayCard {
    //在这里类里面操作牌:设置牌,洗牌和发牌
    public static final String[] suits = {"♠","♥","♣","♦"};//定义花色的数组
    //1.设置牌操作
  
    //2.洗牌操作
  
    //3.发牌操作
    public List<List<Card>> getCard(List<Card> cards) {
        //定义三个对象,存取牌
        List<Card> hand1 =new ArrayList<>();
        List<Card> hand2 =new ArrayList<>();
        List<Card> hand3 =new ArrayList<>();
        //定义一个二维数组,存取三个对象
        List<List<Card>> hand = new ArrayList<>();
        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);
        //每个人只能拿五张牌
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
              Card card = cards.remove(0);//每次拿到第一张牌,并从数组中删掉
              //放入每个人手中
              hand.get(j).add(card);
            }
        }
        return hand;
    }
}

(1)用三个一维的集合代表三个一维数组 (2)再定义一个集合,存放三个一维集合 (3)第一层循环,每循环一次就是一张牌;第二层循环就是每个人轮流拿牌 (4) hand.get(j)代表第几个人,add(card)代表把这张牌给某个人

完整代码:

public static void main(String[] args) {
        PlayCard game = new PlayCard();
        System.out.println("设置牌:");
        List<Card> cards = game.setCard();
        System.out.println(cards);
        System.out.println("洗牌后:");
        game.shuffle(cards);
        System.out.println(cards);
        System.out.println("发牌:");
        List<List<Card>> hand = game.getCard(cards);
        for (int i = 0; i < 3 ; i++) {
            System.out.println("第"+(i+1)+"个人的牌为:"+hand.get(i));
        }
        System.out.println("剩余的牌为:");
        System.out.println(cards);
    }
public class Card {
    //用来定义一张牌
    public String suit;//牌的花色
    public int num;//号码
    public Card(String suit, int num) {
        this.suit = suit;
        this.num = num;
    }
    @Override
    public String toString() {
       return suit+num;
    }
}
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
public class PlayCard {
    //在这里类里面操作牌:设置牌,洗牌和发牌
    public static final String[] suits = {"♠","♥","♣","♦"};//定义花色的数组
    //1.设置牌操作
    public List<Card> setCard() {
        List<Card> cards = new ArrayList<>();//定义一个数组,用来存放所有牌
        for (int i = 0; i < 4; i++) {//四种花色
            for (int j = 1; j <=13 ; j++) {//13个号码
                String suit = suits[i];//获得一个花色
                Card card = new Card(suit,j);//定义一个牌对象并赋值
                cards.add(card);//将牌放入一个牌数组中
            }
        }
        return cards;//返回一副牌
    }
    //2.洗牌操作
    public void shuffle(List<Card> cards) {
        Random random = new Random();
        for (int i = 51; i > 0; i--) {
            int index  = random.nextInt(i);//随机获取一个牌下标与i下标的牌交换
            swap(cards,i,index);
        }
        //return cards;
    }
    private static void swap(List<Card> cards,int i,int j) {
        //交换两张牌
        Card tmp = cards.get(i);
        cards.set(i,cards.get(j));
        cards.set(j,tmp);
    }
    //3.发牌操作
    public List<List<Card>> getCard(List<Card> cards) {
        //定义三个对象,存取牌
        List<Card> hand1 =new ArrayList<>();
        List<Card> hand2 =new ArrayList<>();
        List<Card> hand3 =new ArrayList<>();
        //定义一个二维数组,存取三个对象
        List<List<Card>> hand = new ArrayList<>();
        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);
        //每个人只能拿五张牌
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
              Card card = cards.remove(0);//每次拿到第一张牌,并从数组中删掉
              //放入每个人手中
              hand.get(j).add(card);
            }
        }
        return hand;
    }
}

本节的内容就是介绍ArrayList集合的用法,可以当成一维数组,也可以当成二维数组。看到这里本机就结束了,快趁着这个感觉去刷题吧!

相关文章
|
1天前
|
存储 算法 安全
Python 加密算法详解与应用
Python 加密算法详解与应用
7 1
|
2天前
|
机器学习/深度学习 算法
深度学习中的优化算法及其应用
本文探讨了深度学习中常用的优化算法,包括梯度下降、随机梯度下降、动量方法和Adam方法。通过对比这些算法的优缺点及适用场景,帮助读者更好地理解和应用这些优化方法。
|
14天前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习中的优化算法及其应用
本文旨在探讨深度学习中常用的优化算法,包括梯度下降、动量方法、AdaGrad、RMSProp和Adam等。通过分析每种算法的原理、优缺点及适用场景,揭示它们在训练深度神经网络过程中的关键作用。同时,结合具体实例展示这些优化算法在实际应用中的效果,为读者提供选择合适优化算法的参考依据。
|
15天前
|
算法 前端开发 机器人
一文了解分而治之和动态规则算法在前端中的应用
该文章详细介绍了分而治之策略和动态规划算法在前端开发中的应用,并通过具体的例子和LeetCode题目解析来说明这两种算法的特点及使用场景。
一文了解分而治之和动态规则算法在前端中的应用
|
21天前
|
算法 调度
贪心算法基本概念与应用场景
尽管贪心算法在许多问题中都非常有效,但它并不总是会产生最优解。因此,在应用贪心算法前,重要的是先分析问题是否适合采用贪心策略。一些问题可能需要通过动态规划或回溯等其他算法来解决,以找到确切的全局最优解。
51 1
|
3天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
6 0
|
3天前
|
存储 算法 安全
ArrayList简介及使用全方位手把手教学(带源码),用ArrayList实现洗牌算法,3个人轮流拿牌(带全部源码)
文章全面介绍了Java中ArrayList的使用方法,包括其构造方法、常见操作、遍历方式、扩容机制,并展示了如何使用ArrayList实现洗牌算法的实例。
7 0
|
15天前
|
算法 前端开发
一文了解贪心算法和回溯算法在前端中的应用
该文章深入讲解了贪心算法与回溯算法的原理及其在前端开发中的具体应用,并通过分析LeetCode题目来展示这两种算法的解题思路与实现方法。
|
2天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
4天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。