找往期文章包括但不限于本期文章中不懂的知識(shí)點(diǎn)：

個(gè)人主頁(yè)：我要學(xué)編程(?_?)-CSDN博客

所屬專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)（Java版）

目錄

ArrayList的具體使用?

118. 楊輝三角

撲克洗牌算法?

---

接上篇：數(shù)據(jù)結(jié)構(gòu)之ArrayList與順序表（上）-CSDN博客

ArrayList的具體使用?

118. 楊輝三角

給定一個(gè)非負(fù)整數(shù)?numRows，生成「楊輝三角」的前?numRows?行。

在「楊輝三角」中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。

示例 1:

輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例?2:

輸入: numRows = 1
輸出: [[1]]

• 1 <= numRows <= 30

分析：首先是一個(gè)楊輝三角的問(wèn)題，楊輝三角其實(shí)就是一個(gè)只有一半的二維數(shù)組。?

public class Test {public static void main(String[] args) {// 打印楊輝三角Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int count = 0;// 創(chuàng)建一個(gè)n行n列的二維數(shù)組int[][] array = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) {array[i][j] = 1;}else if (j == 0) {array[i][j] = 1;}else {// 只有從第二行開(kāi)始才會(huì)有下面的規(guī)律if (i >= 2) {array[i][j] = array[i-1][j] + array[i-1][j-1];}}}}for (int[] x:array) {for (int y:x) {if (y != 0) {System.out.print(y+" ");}}System.out.println();}}
}

打印結(jié)果：

注意：楊輝三角還有一個(gè)規(guī)律就是第 i-1 行有 i 個(gè)元素。?

這里主要的難點(diǎn)是：List<List<Integer>>? ?這個(gè)代碼的意思是什么？分開(kāi)看，List<Integer> 這個(gè)代碼的意思是有一個(gè)線(xiàn)性表，這個(gè)線(xiàn)性表中存放的是 Integer 類(lèi)型。List<List<Integer>> 難道這個(gè)代碼的意思是有一個(gè)線(xiàn)性表，這個(gè)線(xiàn)性表里面存放的是一個(gè)線(xiàn)性表？沒(méi)錯(cuò)！不過(guò)這個(gè)不叫線(xiàn)性表了。如果我們把這個(gè)List看成一個(gè)數(shù)組，那就是一個(gè)數(shù)組里面存放的是一個(gè)一個(gè)的數(shù)組元素，然后這些數(shù)組元素里面的元素是一個(gè)一個(gè)的整形包裝類(lèi)。這就是二維數(shù)組嘛！二維數(shù)組里面是一個(gè)一個(gè)的一維數(shù)組，而一維數(shù)組里面是一個(gè)一個(gè)的整型元素。

例如：

public class Test {public static void main(String[] args) {// 二維數(shù)組// 根據(jù)順序表的特點(diǎn)這個(gè)二維數(shù)組為0行0列List<List<Integer>> list = new ArrayList<>(); //二維數(shù)組的初始化list.add(new ArrayList<>()); // 二維數(shù)組的元素是一維數(shù)組list.add(new ArrayList<>()); // 二維數(shù)組的元素是一維數(shù)組list.add(new ArrayList<>()); // 二維數(shù)組的元素是一維數(shù)組// 一維數(shù)組的初始化list.get(0).add(10); // list.get(0)得到的是下標(biāo)為0的一維數(shù)組，接著尾插10list.get(1).add(20); // list.get(1)得到的是下標(biāo)為1的一維數(shù)組，接著尾插20list.get(2).add(30); // list.get(2)得到的是下標(biāo)為2的一維數(shù)組，接著尾插30}
}

畫(huà)圖理解：

?上面搞懂了，就可以開(kāi)始做題了。這個(gè)題目的意思就是讓我們把存放楊輝三角二維數(shù)組改成一個(gè)ArrayList。

根據(jù)我們用二維數(shù)組做題時(shí)的代碼改編一下就可以了。

下面是改編的代碼：

方法一：

public class Test {public static List<List<Integer>> generate(int numRows) {// 創(chuàng)建一個(gè)二維數(shù)組List<List<Integer>> list = new ArrayList<List<Integer>>();for (int i = 0; i < numRows; i++) {// 不用下標(biāo)直接尾插也是可以的list.add(i, new ArrayList<>());}// 開(kāi)始為二維數(shù)組存放元素for (int i = 0; i < numRows; i++) {List<Integer> list1 = list.get(i);//        注意這里j的條件for (int j = 0; j <= i; j++) {if (i == j) {list1.add(1);}else if (j == 0) {list1.add(1);}else if (i >= 2) {// 實(shí)現(xiàn)這個(gè)代碼：a[i][j] = a[i-1][j]+a[i-1][j-1];// 得到i-1下標(biāo)數(shù)組的j位置的值  得到i-1下標(biāo)數(shù)組的j-1位置的值// 這個(gè)寫(xiě)法有問(wèn)題。就像：3 = 5// list.get(i).get(j) = list.get(i-1).get(j)  + list.get(i-1).get(j-1);// 這個(gè)就是對(duì)上面的代碼進(jìn)行翻譯一下int t  = list.get(i - 1).get(j) + list.get(i - 1).get(j - 1);list1.add(j , t);}}}return list;}public static void main(String[] args) {List<List<Integer>> listList = generate(5);for (List<Integer> list : listList) {for (Integer x : list) {System.out.print(x+" ");}System.out.println();}}
}

方法二：?

public class TestDrive {public static List<List<Integer>> generate(int numRows) {// 創(chuàng)建一個(gè)二維數(shù)組List<List<Integer>> list = new ArrayList<List<Integer>>();for (int i = 0; i < numRows; i++) {// 不用下標(biāo)直接尾插也是可以的list.add(i, new ArrayList<>());// 為二維數(shù)組的每一位元素的初始化為0for (int j = 0; j < numRows; j++) {list.get(i).add(j,0);}}// 開(kāi)始為二維數(shù)組存放元素for (int i = 0; i < numRows; i++) {List<Integer> list1 = list.get(i);//      注意這里的j和方法進(jìn)行區(qū)別for (int j = 0; j < numRows; j++) {if (i == j) {// 因?yàn)樗性囟加谐跏贾盗?#xff0c;所以這里就都是set而不是addlist1.set(j,1);}else if (j == 0) {list1.set(j,1);}else if (i >= 2) {int t  = list.get(i - 1).get(j) + list.get(i - 1).get(j - 1);list1.set(j , t);}}}return list;}public static void main(String[] args) {List<List<Integer>> listList = generate(5);for (List<Integer> list : listList) {for (Integer x : list) {if (x != 0) {System.out.print(x+" ");}}System.out.println();}}
}

方法一與方法二的區(qū)別：

方法二就是完全對(duì)前面代碼的改編。因?yàn)榍懊嫖覀冊(cè)趧?chuàng)建一個(gè)二維數(shù)組的同時(shí)是進(jìn)行了初始化的，所以這里的所有元素都是有初始值的。但我們用順序表來(lái)創(chuàng)建二維數(shù)組的時(shí)候，如果沒(méi)有初始化，那么其值就是null，這個(gè)是不能參與運(yùn)算的。因此，我們要手動(dòng)的置為0，這樣就可以參與運(yùn)算了，否則就會(huì)發(fā)生異常。

方法一就是改進(jìn)了方法二的不足之處。既然你不初始化，在運(yùn)算時(shí)，會(huì)發(fā)生異常，那么我就把你的范圍卡在只參與運(yùn)算的部分。也就是 j <= i 。我們仔細(xì)觀察會(huì)發(fā)現(xiàn)楊輝三角是一個(gè)等腰直角三角形。如下圖：

楊輝三角練習(xí)完了，接下來(lái)，就要進(jìn)入重磅戲了：撲克洗牌算法。?

撲克洗牌算法?

要求：

1. 生成一副撲克牌。

2. 并且把這副撲克牌打亂。

3. 發(fā)給3個(gè)人，每人每輪發(fā)一張，總共發(fā)5輪。?

一張一張的牌，一張牌包括牌面值和花色?

// 一張牌
public class Card {public int rank; // 牌面值public String suit; // 對(duì)應(yīng)的花色public Card(int rank, String suit) {this.rank = rank;this.suit = suit;}@Overridepublic String toString() {return ""+suit+rank+" ";}
}

有了一張一張的牌，就可以生成一副牌和存放牌的容器，也就是順序表

public class Cards {// 生成牌的四色public static final String suit[] = {"?","?","?","?"};public List<Card> cardList;// 在new一個(gè)對(duì)象的時(shí)候，就會(huì)生成存儲(chǔ)一副牌的數(shù)組public Cards() {this.cardList = new ArrayList<>();}// 生成一副牌// 為了方便，這里的牌面值都用數(shù)字表示public List<Card> generateCards() {for (int i = 1; i <= 14; i++) {int count = 0;for (int j = 0; j < suit.length; j++) {// 生成一張牌Card card = new Card(i, suit[j]);// 把牌存放到數(shù)組中cardList.add(card);if (i > 13 && count < 2) {count++;}if (count == 2) {break;}}}return cardList;}
}

接下來(lái)就是要開(kāi)始洗牌了。

    // 洗牌public void shuffle() {// 通過(guò)隨機(jī)下標(biāo)進(jìn)行交換Random random = new Random();// i=0就是自己和自己交換了for (int i = cardList.size()-1; i > 0; i--) {// 生成[0,i)之間的值，也就是[0,i-1]int index = random.nextInt(i);swap(cardList, index, i);}}private void swap(List<Card> cardList, int index, int i) {// 交換index和i下標(biāo)對(duì)應(yīng)的數(shù)組元素// int tmp = a; a = b; b = tmp;Card tmp = cardList.get(i);// 把i下標(biāo)的值，改為index下標(biāo)對(duì)應(yīng)的值cardList.set(i, cardList.get(index));cardList.set(index, tmp);}

?發(fā)牌

    // 發(fā)牌// 給3人發(fā)5輪牌，每人每輪發(fā)一張public List<List<Card>> dealCards() {// 創(chuàng)建一個(gè)二維數(shù)組List<List<Card>> listList = new ArrayList<>();for (int i = 0; i < 3; i++) {listList.add(new ArrayList<>());}for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {// 第j個(gè)人拿到第0下標(biāo)的牌listList.get(j).add(cardList.get(0)); // 假設(shè)從最上面開(kāi)始拿// 每拿一張就少一張cardList.remove(0);}}return listList;}

測(cè)試：

public class Test {public static void main(String[] args) {// 生成一副牌Cards cards = new Cards();List<Card> cardList = cards.generateCards();System.out.println(cardList);// 開(kāi)始洗牌——將牌的順序打亂cards.shuffle();System.out.println(cardList);// 開(kāi)始發(fā)牌List<List<Card>> listList = cards.dealCards();// 查看結(jié)果int i = 1;for (List<Card> list: listList) {System.out.print("第"+i+"個(gè)人拿到的牌：");for (Card x : list) {System.out.print(x+" ");}i++;System.out.println();}}
}

?好啦！本期 數(shù)據(jù)結(jié)構(gòu)之ArrayList與順序表（下）的學(xué)習(xí)就到此結(jié)束啦！我們下一期再一起學(xué)習(xí)吧！