数据结构之ArrayList与序次表（下）

找往期文章包括但不限于本期文章中不懂的知识点：
   个人主页：我要学编程(ಥ_ಥ)-CSDN博客
  所属专栏：数据结构（Java版）
  目次
ArrayList的详细利用 
118. 杨辉三角
扑克洗牌算法 

---

接上篇：数据结构之ArrayList与序次表（上）-CSDN博客
ArrayList的详细利用 

118. 杨辉三角

   给定一个非负整数 numRows，天生「杨辉三角」的前 numRows 行。
  在「杨辉三角」中，每个数是它左上方和右上方的数的和。
  
  

  示例 1:

1. <strong>输入:</strong> numRows = 5
2. <strong>输出:</strong> [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

复制代码

示例 2:

1. <strong>输入:</strong> numRows = 1
2. <strong>输出:</strong> [[1]]

复制代码

• 1 <= numRows <= 30
  

  分析：起首是一个杨辉三角的问题，杨辉三角其实就是一个只有一半的二维数组。 

1. public class Test {
2.     public static void main(String[] args) {
3.         // 打印杨辉三角
4.         Scanner scanner = new Scanner(System.in);
5.         int n = scanner.nextInt();
6.         int count = 0;
7.         // 创建一个n行n列的二维数组
8.         int[][] array = new int[n][n];
9.         for (int i = 0; i < n; i++) {
10.             for (int j = 0; j < n; j++) {
11.                 if (i == j) {
12.                     array[i][j] = 1;
13.                 }else if (j == 0) {
14.                     array[i][j] = 1;
15.                 }else {
16.                     // 只有从第二行开始才会有下面的规律
17.                     if (i >= 2) {
18.                         array[i][j] = array[i-1][j] + array[i-1][j-1];
19.                     }
20.                 }
21.             }
22.         }
23.         for (int[] x:array) {
24.             for (int y:x) {
25.                 if (y != 0) {
26.                     System.out.print(y+" ");
27.                 }
28.             }
29.             System.out.println();
30.         }
31.     }
32. }

复制代码

打印效果：

留意：杨辉三角尚有一个规律就是第 i-1 行有 i 个元素。 
这里主要的难点是：List<List<Integer>>   这个代码的意思是什么？分开看，List<Integer> 这个代码的意思是有一个线性表，这个线性表中存放的是 Integer 范例。List<List<Integer>> 岂非这个代码的意思是有一个线性表，这个线性表内里存放的是一个线性表？没错！不过这个不叫线性表了。如果我们把这个List看成一个数组，那就是一个数组内里存放的是一个一个的数组元素，然后这些数组元素内里的元素是一个一个的整形包装类。这就是二维数组嘛！二维数组内里是一个一个的一维数组，而一维数组内里是一个一个的整型元素。
比方：

1. public class Test {
2.     public static void main(String[] args) {
3.         // 二维数组
4.         // 根据顺序表的特点这个二维数组为0行0列
5.         List<List<Integer>> list = new ArrayList<>();
6.         //二维数组的初始化
7.         list.add(new ArrayList<>()); // 二维数组的元素是一维数组
8.         list.add(new ArrayList<>()); // 二维数组的元素是一维数组
9.         list.add(new ArrayList<>()); // 二维数组的元素是一维数组
10.         // 一维数组的初始化
11.         list.get(0).add(10); // list.get(0)得到的是下标为0的一维数组，接着尾插10
12.         list.get(1).add(20); // list.get(1)得到的是下标为1的一维数组，接着尾插20
13.         list.get(2).add(30); // list.get(2)得到的是下标为2的一维数组，接着尾插30
14.     }
15. }

复制代码

画图理解：

 上面搞懂了，就可以开始做题了。这个标题的意思就是让我们把存放杨辉三角二维数组改成一个ArrayList。
根据我们用二维数组做题时的代码改编一下就可以了。
下面是改编的代码：
方法一：

1. public class Test {
2.     public static List<List<Integer>> generate(int numRows) {
3.         // 创建一个二维数组
4.         List<List<Integer>> list = new ArrayList<List<Integer>>();
5.         for (int i = 0; i < numRows; i++) {
6.             // 不用下标直接尾插也是可以的
7.             list.add(i, new ArrayList<>());
8.         }
9.         // 开始为二维数组存放元素
10.         for (int i = 0; i < numRows; i++) {
11.             List<Integer> list1 = list.get(i);
12.             //        注意这里j的条件
13.             for (int j = 0; j <= i; j++) {
14.                 if (i == j) {
15.                     list1.add(1);
16.                 }else if (j == 0) {
17.                     list1.add(1);
18.                 }else if (i >= 2) {
19.                     // 实现这个代码：a[i][j] = a[i-1][j]+a[i-1][j-1];
20.                     // 得到i-1下标数组的j位置的值  得到i-1下标数组的j-1位置的值
22.                     // 这个写法有问题。就像：3 = 5
23.                     // list.get(i).get(j) = list.get(i-1).get(j)  + list.get(i-1).get(j-1);
24.                     // 这个就是对上面的代码进行翻译一下
25.                     int t  = list.get(i - 1).get(j) + list.get(i - 1).get(j - 1);
26.                     list1.add(j , t);
27.                 }
28.             }
29.         }
30.         return list;
31.     }
32.     public static void main(String[] args) {
33.         List<List<Integer>> listList = generate(5);
34.         for (List<Integer> list : listList) {
35.             for (Integer x : list) {
36.                 System.out.print(x+" ");
37.             }
38.             System.out.println();
39.         }
40.     }
41. }

复制代码

方法二： 

1. public class TestDrive {
2.     public static List<List<Integer>> generate(int numRows) {
3.         // 创建一个二维数组
4.         List<List<Integer>> list = new ArrayList<List<Integer>>();
5.         for (int i = 0; i < numRows; i++) {
6.             // 不用下标直接尾插也是可以的
7.             list.add(i, new ArrayList<>());
8.             // 为二维数组的每一位元素的初始化为0
9.             for (int j = 0; j < numRows; j++) {
10.                 list.get(i).add(j,0);
11.             }
12.         }
13.         // 开始为二维数组存放元素
14.         for (int i = 0; i < numRows; i++) {
15.             List<Integer> list1 = list.get(i);
16.             //      注意这里的j和方法进行区别
17.             for (int j = 0; j < numRows; j++) {
18.                 if (i == j) {
19.                     // 因为所有元素都有初始值了，所以这里就都是set而不是add
20.                     list1.set(j,1);
21.                 }else if (j == 0) {
22.                     list1.set(j,1);
23.                 }else if (i >= 2) {
24.                     int t  = list.get(i - 1).get(j) + list.get(i - 1).get(j - 1);
25.                     list1.set(j , t);
26.                 }
27.             }
28.         }
29.         return list;
30.     }
31.     public static void main(String[] args) {
32.         List<List<Integer>> listList = generate(5);
33.         for (List<Integer> list : listList) {
34.             for (Integer x : list) {
35.                 if (x != 0) {
36.                     System.out.print(x+" ");
37.                 }
38.             }
39.             System.out.println();
40.         }
41.     }
42. }

复制代码

方法一与方法二的区别：
方法二就是完全对前面代码的改编。因为前面我们在创建一个二维数组的同时是举行了初始化的，以是这里的所有元素都是有初始值的。但我们用序次表来创建二维数组的时间，如果没有初始化，那么其值就是null，这个是不能参与运算的。因此，我们要手动的置为0，这样就可以参与运算了，否则就会发生异常。
方法一就是改进了方法二的不足之处。既然你不初始化，在运算时，会发生异常，那么我就把你的范围卡在只参与运算的部分。也就是 j <= i 。我们仔细观察会发现杨辉三角是一个等腰直角三角形。如下图：

杨辉三角训练完了，接下来，就要进入重磅戏了：扑克洗牌算法。 
扑克洗牌算法 

要求：
1. 天生一副扑克牌。
2. 而且把这副扑克牌打乱。
3. 发给3个人，每人每轮发一张，总共发5轮。 
一张一张的牌，一张牌包括牌面值和花色 

1. // 一张牌
2. public class Card {
3.     public int rank; // 牌面值
4.     public String suit; // 对应的花色
6.     public Card(int rank, String suit) {
7.         this.rank = rank;
8.         this.suit = suit;
9.     }
11.     @Override
12.     public String toString() {
13.         return ""+suit+rank+" ";
14.     }
15. }

复制代码

有了一张一张的牌，就可以天生一副牌和存放牌的容器，也就是序次表

1. public class Cards {
2.     // 生成牌的四色
3.     public static final String suit[] = {"♠","♣","♥","♦"};
4.     public List<Card> cardList;
6.     // 在new一个对象的时候，就会生成存储一副牌的数组
7.     public Cards() {
8.         this.cardList = new ArrayList<>();
9.     }
11.     // 生成一副牌
12.     // 为了方便，这里的牌面值都用数字表示
13.     public List<Card> generateCards() {
14.         for (int i = 1; i <= 14; i++) {
15.             int count = 0;
16.             for (int j = 0; j < suit.length; j++) {
17.                 // 生成一张牌
18.                 Card card = new Card(i, suit[j]);
19.                 // 把牌存放到数组中
20.                 cardList.add(card);
21.                 if (i > 13 && count < 2) {
22.                     count++;
23.                 }
24.                 if (count == 2) {
25.                     break;
26.                 }
27.             }
28.         }
29.         return cardList;
30.     }
31. }

复制代码

接下来就是要开始洗牌了。

1.     // 洗牌
2.     public void shuffle() {
3.         // 通过随机下标进行交换
4.         Random random = new Random();
5.         // i=0就是自己和自己交换了
6.         for (int i = cardList.size()-1; i > 0; i--) {
7.             // 生成[0,i)之间的值，也就是[0,i-1]
8.             int index = random.nextInt(i);
9.             swap(cardList, index, i);
10.         }
11.     }
13.     private void swap(List<Card> cardList, int index, int i) {
14.         // 交换index和i下标对应的数组元素
15.         // int tmp = a; a = b; b = tmp;
16.         Card tmp = cardList.get(i);
17.         // 把i下标的值，改为index下标对应的值
18.         cardList.set(i, cardList.get(index));
19.         cardList.set(index, tmp);
20.     }

复制代码

 发牌

1.     // 发牌
2.     // 给3人发5轮牌，每人每轮发一张
3.     public List<List<Card>> dealCards() {
4.         // 创建一个二维数组
5.         List<List<Card>> listList = new ArrayList<>();
6.         for (int i = 0; i < 3; i++) {
7.             listList.add(new ArrayList<>());
8.         }
9.         for (int i = 0; i < 5; i++) {
10.             for (int j = 0; j < 3; j++) {
11.                 // 第j个人拿到第0下标的牌
12.                 listList.get(j).add(cardList.get(0)); // 假设从最上面开始拿
13.                 // 每拿一张就少一张
14.                 cardList.remove(0);
15.             }
16.         }
17.         return listList;
18.     }

复制代码

测试：

1. public class Test {
2.     public static void main(String[] args) {
3.         // 生成一副牌
4.         Cards cards = new Cards();
5.         List<Card> cardList = cards.generateCards();
6.         System.out.println(cardList);
8.         // 开始洗牌——将牌的顺序打乱
9.         cards.shuffle();
10.         System.out.println(cardList);
12.         // 开始发牌
13.         List<List<Card>> listList = cards.dealCards();
16.         // 查看结果
17.         int i = 1;
18.         for (List<Card> list: listList) {
19.             System.out.print("第"+i+"个人拿到的牌：");
20.             for (Card x : list) {
21.                 System.out.print(x+" ");
22.             }
23.             i++;
24.             System.out.println();
25.         }
26.     }
27. }

复制代码

 好啦！本期 数据结构之ArrayList与序次表（下）的学习就到此结束啦！我们下一期再一起学习吧！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。