Java杨辉三角、洗牌算法详细示例代码_Java

一、杨辉三角

给定一个非负数numrows，生成杨辉三角的前 numrows 行。

在杨辉三角中，每个数是它左上方和右上方的数之和。

示例：输入：numrows = 5

输出: [ [1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1] ]

思路：使用二维数组的思路，使用列表的思路创建二维数组，定义行和列。

我们说过要用list列表的思路去创建二维数组：

示例：可以往这个列表中添加元素，只不过这个元素是一个个实例化的对象（传递的参数是一个泛型类，那么它也需要明确传递的参数类型，因此需要实例化对象），证明是一个二维数组：

输出结果：

那么，具体如何向这个二维数组存放具体的元素呢？

—— 前面说过，传递的参数是一个泛型类，因此需要实例化对象，但是不可以这样：

那么我们可以单独将列表每个实例化的元素写出来，往这一个个元素中，使用add方法添加元素，然后再将这些实例化的对象的引用传递给列表：

输出结果：

我们也可以通过调试观察：

前面的准备知识学习完后，我们正式开始写杨辉三角：

使用 [i][j] = [i-1][j-1] + [i-1][j-1] 的思路。

写一个方法 generate ，它的返回值是list<list<integer>>，在方法中，我们首先处理第一行，因为杨辉三角的第一行只有一个元素，那就是1，因此，我们先处理第一行，将这一行的元素先添加到列表中；然后从第二行开始，进行求每一个元素（使用前面的公式），由于杨辉三角的每一行的第一个元素和最后一个元素都是1，于是也可以直接添加，从每一行的第二个元素开始求，也就是中间的这些位置：根据公式，需要先求该行的前一行的元素信息，然后利用这些信息进行该行的元素求解；最后返回列表。

public class test {
    public static list<list<integer>> generate(int numrows) {
        list<list<integer>> ret = new arraylist<>();
        //处理第一行
        list<integer> list0 = new arraylist<>();
        list0.add(1);
        ret.add(list0);
    
        //从第2行开始 进行求元素
        for(int i = 1;i < numrows; i++) {
            //处理第一个元素
            list<integer> currow = new arraylist<>();
            currow.add(1);

            //中间
            //从第二个元素开始求元素
            list<integer> prerow = ret.get(i-1);//前一行
            for(int j = 1;j < i; j++) {
                //[i][j] = [i-1][j-1] + [i-1][j-1] 
                int val1 = prerow.get(j);
                int val2 = prerow.get(j-1);
                ret.add(val1 + val2);
            }            

            //尾巴
            currow.add(1);
            ret.add(currow);
        }
        return ret;
    }
    public static void main(string[] args) {
        list<list<integer>> list = new arraylist<>();
        list<list<integer>> ret = generate(4);
        for(int i = 0;i < ret.size(); i++) {
            for(int j = 0;j < ret.get(i).size(); j++) {
                system.out.print(ret.get(i).get(j) + " ");
            }
            system.out.println();
        }
    }
}

输出结果：

二、洗牌算法

要完成洗牌，有三个步骤：

1.买扑克牌 52张牌
2.洗牌
3.设有3个人，每个人轮流揭5张牌

1.card类——描述一副牌的组成

首先我们写一个类card，用来描述买来的一副牌的组成：

public class card {
    private string suit;//花色
    private int rank;//牌面值

    //构造方法
    public card(string suit,int rank) {
        this.suit = suit;
        this.rank = rank;
    } 

    //重写tostring
    public void tostring() {
        return "{" + suit + rank + "}";
    }
}

2.carddemo类——完成买牌、洗牌等操作

然后再写一个类carddemo，在这个类中，完成买牌、洗牌等一些列事情；一副牌中，包括四种花色，分别是红心、方块、梅花和黑桃，每种花色有13张牌，总计52张牌。

因此，我们可以先定义一个字符串数组，数组内存放四种花色牌，各一张，由于这四种花色是固定不变的，可以写成一个常量数组（final修饰）；

然后写一个 buycard 方法，它的返回值是list<card>，表示买牌的动作，在这个方法中：先实例化一个card类对象，然后通过for循环嵌套将各个花色的所有牌放入对象中（每个花色的牌各有13张，一样的牌各有4张），最后通过add方法添加到card类对象中。

注意：该方法的返回值是一个泛型类，它的参数是一个card类类型，因此，需要实例化card类对象，这里每添加一个花色牌就利用card的构造方法初始化一下suit和rank，最后将这个card类型引用作为参数传递给泛型类。

public class carddemo {
    public static final string[] suits = {"♥","♠","♣","♦"};

    //买一副牌
    public list<card> buycard() {
        list<card> cardlist = new arraylist<>();
        for(int i = 1;i <= 13; i++) {
            for(int j = 0;j < 4; j++) {
                int rank = i;
                string suit = suits[j];
                card card = new card(suit,rank);
                cardlist.add(card);
            }
        }
        return cardlist;
    }
}

接着写一个 shuffle 方法，表示洗牌的动作，在这个方法中，我们需要做的就是打乱牌的顺序，即洗牌。这里需要用到一个类——random，这个类中的一个 nextint 方法，用于生成一个随机数值，该方法的有两种使用方式：

nextint()：生成一个随机的 int 值，范围是所有可能的 int 值
nextint(int bound)：生成一个在 [0, bound) 范围内的随机 int 值，包含 0 但不包含 bound

而我们此时需要用的是第2种方式。

写一个for循环，初始条件从最后一张牌开始，在这个循环中，使用random.nextint() 方法，每次将随机生成的数值和最后一张牌进行随机交换，比如，有52张牌，它们对应下标是0~51，对这副牌进行洗牌，从最后一张牌开始进入循环，通过random.nextint(51)生成0~50之间的随机牌，让最后一张牌，即第52张牌与随机的一张牌进行位置交换，接着是通过random.nextint(50)生成0~49之间的随即牌，再将此时的最后一张牌与随机牌位置交换，直到全部牌交换完成，就完成了洗牌的动作。

注意：循环继续直到i > 0，当i变成0时，循环停止。这是因为当i=0时，只有一个元素 left，不需要交换自己。

而位置交换的动作则写一个 swap 方法来完成：按照之前写swap方法的思路：

card tmp = cardlist[i];
cardlist[i] = cardlist[j];
cardlist[j] = tmp;

但是这样写是不行的，cardlist引用的类型是list<card>泛型类，并不是一个数组，不可以使用数组下标运算符[]，对于list<card>类，应该使用 get() 和 set() 方法来代替进行位置交换操作。

public void shuffle(list<card> cardlist) {
    random random = new random();
    for(int i = cardlist.size()-1;i > 0; i--) {
        int index = random.nextint(i);
        swap(cardlist,i,index);
    }
}
public void swap(list<card> cardlist,int i,int j) {
    card tmp = cardlist.get(i);
    cardlist.set(i,cardlist.get(j));
    cardlist.set(j,tmp);
}

最后写一个轮流揭牌的方法 play ，假设有3个人，每个人要揭5张牌，那么每个人的5张牌要如何存放呢？—— 3个人各自实例化一个list泛型类，将各自的牌存放在各自的引用对象中；使用for循环嵌套，进行轮流揭牌，每次揭玩一张牌，牌就会少一张，使用remove方法，每次揭玩一张牌就删除最上面的那张牌，即下标为0的那张牌。

问题：如何将对应的牌放到对应的人手里呢？

—— 使用二维数组。

public <list<card>> play(list<card> cardlist) {
    list<card> hand0 = new arraylist<>();
    list<card> hand1 = new arraylist<>();
    list<card> hand2 = new arraylist<>();
    
    list<list<card>> hand = new arraylist<>();
    hand.add(hand0);
    hand.add(hand1);
    hand.add(hand2);
    
    for(int i = 0;i < 5; i++) {
        for(int j = 0;j < 3; j++) {
            card card = cardlist.remove(0);
            hand.get(j).add(card);//比如：hand.hand0.add(card);
        }
    }
    return hand;
}

3.完整代码

//card类

public class card {
    private string suit;
    private int rank;

    public card(string suit,int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    public void tostring() {
        return "{" + suit + rank + "}";
    }
}

//carddemo类

public class carddemo {
    public static final string[] suits = {"♥","♠","♣","♦"};

    //买一副牌
    public list<card> buycard() {
        list<card> cardlist= new arraylist<>();
        for(int i = 1;i <= 13; i++) {
            for(int j = 0;j < 4; j++) {
                int rank = i;
                string suit = suits[j];
                card card = new card(suit,rank);
                cardlist.add(card);
            }
        }
        return cardlist;
    }

    //洗牌
    public void shuffle(list<card> cardlist) {
        random random = new random();
        for(int i = cardlist.size()-1;i > 0; i--) {
            int index = random.nextint(i);
            swap(cardlist,i,index);
        }
    }
    public void swap(list<card> cardlist,int i,int j) {
        card tmp = cardlist.get(i);
        cardlist.set(i,cardlist.get(j));
        cardlist.set(j,tmp);
    }

    //3个人，轮流揭5张牌
    public list<list<card>> play(list<card> cardlist) {
        list<catd> hand0 = new arraylist<>();
        list<card> hand1 = new arraylist<>();
        list<card> hand1 = new arraylist<>();

        list<list<card>> hand = new arraylist<>();
        
        for(int i = 0;i < 5; i++) {
            for(int j = 0;j < 3; j++) {
                card card = cardlist.remove(0);
                hand.get(j).add(card);
            }
        }
        return hand;
    }
}

4.测试

public class test {
    public static void main(string[] args) {
        carddemo carddemo = new carddemo();
        //买一副牌
        system.out.println("洗牌前：");
        list<card> cardlist = carddemo.buycard();
        system.out.println(cardlist);
        //洗牌
        system.out.println("洗牌后：");
        carddemo.shuffle(cardlist);
        system.out.println(cardlist);
        //3个人轮流揭5张牌
        system.out.println("抽牌：");
        list<list<card>> ret = carddemo.play(cardlist);
        for(int i = 0;i < ret,size(); i++) {
            system.out.println("第"+(i+1)+"个人的牌："+ret.get(i));
        }
        system.out.println("剩下的牌：");
        system.out.println(cardlist);
    }
}

输出结果：