深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构与算法】杨辉三角，相同字符的截取以及扑克牌

2023-04-05

int list card
✨个人主页：bitme✨当前专栏：数据结构✨每日一语：不要等到了你的人生垂暮，才想起俯拾朝花，且行且珍惜。ArrayList题训🌵一.杨辉三角🌴二.相同字符的截取🌲三.扑克牌🌵一.杨辉三角给定一个非负整数numRows，生成「杨辉三角」的前numRows行。在「杨辉三角」中，每个数是它左上方

✨个人主页：bit me
✨当前专栏：数据结构
✨每日一语：不要等到了你的人生垂暮，才想起俯拾朝花，且行且珍惜。

ArrayList题训

  • 🌵 一. 杨辉三角
  • 🌴二.相同字符的截取
  • 🌲三.扑克牌

🌵 一. 杨辉三角

给定一个非负整数 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和j来分别表示行和列，用二维数组来表示就是[i][j] = [i-1][j] + [i-1][j-1]

  1. 先定义一个二维数组ret
List<List<Integer>> ret = new ArrayList<>();//二维数组

  • 1
  1. 第0行的元素不参与规律计算，我们直接给第0行赋值为1
List<Integer> one = new ArrayList<>();
one.add(1);
ret.add(one);

  • 1
  • 2
  • 3
  1. 定义行数为i，遍历行数
for (int i = 1; i < numRows; i++) {
...
}

  • 1
  • 2
  • 3

①：数组的每一行第一个元素都是固定的为1，把遍历到的数组都定义为curRow，然后赋值第一个元素1

List<Integer> curRow = new ArrayList<>();
curRow.add(1);

  • 1
  • 2

②定义这一行的每个元素为j，根据我们上述规律[i][j] = [i-1][j] + [i-1][j-1]来遍历数组实现打印

for (int j = 1; j < i; j++) {
    //curRow[i][j] = [i-1][j] + [i-1][j-1];
    List<Integer> preRow = ret.get(i-1);
    int x = preRow.get(j) + preRow.get(j-1);
    curRow.add(x);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

③每一行的最后一个元素也是固定不变的，也是元素1，所以我们直接在最后添加一个元素就ok了

curRow.add(1);
ret.add(curRow);

  • 1
  • 2

附上总的代码：

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ret = new ArrayList<>();//二维数组
    List<Integer> one = new ArrayList<>();
    one.add(1);
    ret.add(one);

    //i代表每一行
    for (int i = 1; i < numRows; i++) {
        List<Integer> curRow = new ArrayList<>();
        //这一行开始的1
        curRow.add(1);
        //j代表这一行的每个元素
        for (int j = 1; j < i; j++) {
            //curRow[i][j] = [i-1][j] + [i-1][j-1];
            List<Integer> preRow = ret.get(i-1);
            int x = preRow.get(j) + preRow.get(j-1);
            curRow.add(x);
        }
        //j == i 这一行最后的一个1
        curRow.add(1);
        ret.add(curRow);
    }
    return ret;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

 

🌴二.相同字符的截取

给定两串字符串s1，s2
要求：去掉第一串字符串当中所有的第二串字符串当中的字符

示例：
输入字符串：

String s1 = “welcome to my world”;
String s2 = “come”;

输出：

wl t y wrld

在思考这一题的代码实现中，我们先从边角开始考虑

  1. 先考虑特殊情况，两串字符串中有任何一个字符串为空的时候，或者长度为空，我们就需要把它置为空
if(s1 == null || s2 == null){
    return null;
}
if(s1.length() == 0 || s2.length() == 0){
    return null;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  1. 创建链表
List<Character> ret = new ArrayList<>();

  • 1
  1. 对第一串字符串进行遍历，然后记录下每个元素下角标，用第二串数组中的元素进行比较，去掉出现相同的字符串，最后返回未出现相同字符的元素
for (int i = 0; i < s1.length(); i++) {
    char ch = s1.charAt(i);
    if(!s2.contains(ch+"")){
        ret.add(ch);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

此处简单介绍两种方法：

①charAt()方法是用来检索特定索引下的字符的String实例的方法，返回指定索引位置的char值，索引范围为0~length()-1
②contains()方法是当且仅当此字符串包含指定的char值序列时，返回true。

最后在我们主函数里就可以进行相应的操作了：

public static void main(String[] args) {
    String s1 = "welcome to my world";
    String s2 = "come";
    List<Character> ret = func(s1,s2);
    for (char ch:ret) {
        System.out.print(ch);
    }
    System.out.println();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

如上执行的结果：

附上总代码：

public static List<Character> func(String s1,String s2){
    if(s1 == null || s2 == null){
        return null;
    }
    if(s1.length() == 0 || s2.length() == 0){
        return null;
    }
    List<Character> ret = new ArrayList<>();
    for (int i = 0; i < s1.length(); i++) {
        char ch = s1.charAt(i);
        if(!s2.contains(ch+"")){
            ret.add(ch);
        }
    }
    return ret;
}

public static void main(String[] args) {
    String s1 = "welcome to my world";
    String s2 = "come";
    List<Character> ret = func(s1,s2);
    for (char ch:ret) {
        System.out.print(ch);
    }
    System.out.println();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

 

🌲三.扑克牌

要求我们自己写一副扑克牌

①：完成刚买牌的顺序打印出来
②：我们再完成洗牌随机打乱顺序
③：三个人轮流每个人揭5张牌
④：还要输出最后剩余的牌

  1. 我们需要先创建一副牌，用来我们一系列的操作，单独创建一个Card类，定义花色和数字，写带两个参数的构造方法，以及getter和setter方法，重写ToString方法
class Card {
    private String suit;
    private int rank;

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

    public String getSuit() {
        return suit;
    }

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

    public int getRank() {
        return rank;
    }

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

    @Override
    public String toString() {
        return "[ " + suit+" "+rank+" ]";
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  1. 写一个刚买的牌，按照花色和顺序打印出来，J，Q，K我们按照数字11，12，13来打印，再把花色和序号融合在一起组成每个牌每个花色
public static final String[] suits = {"♥","♠","♣","♦"};

public static List<Card> buyCard() {
    List<Card> desk = new ArrayList<>();
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= 13 ; j++) {
            String suit = suits[i];
            Card card = new Card(suit,j);
            desk.add(card);
        }
    }
    return desk;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

最后运行出来的一副新牌就是按照花色的数字从小到大依次打印

  1. 洗牌后随机打乱的函数，那我们如何很好的打乱呢？交换每个元素的下标，让它遍历的时候随机和其他元素下标交换，达到我们的目的，在此处我们还可以优化一下，让下标随机数取元素长度里的任何一个下标，所以反向遍历更好
public static void shuffle(List<Card> cardList) {
    for (int i = cardList.size()-1; i > 0 ; i--) {
        Random random = new Random();
        int index = random.nextInt(i);
        swap(cardList,i,index);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

在这里我们提及之前学过的元素交换：

int tmp = array[i];
array[i] = array[j];
array[j] = tmp;

  • 1
  • 2
  • 3

所以这里的swap函数就仿照这个来写

private static void swap(List<Card> cardList,int i,int j) {
    Card tmp = cardList.get(i);
    cardList.set(i,cardList.get(j));
    cardList.set(j,tmp);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  1. 五个人每个人都轮流揭五张牌，最后揭的牌还需要删除，方便后面我们打印剩余的牌
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 3; j++) {
        //每次揭牌都去获取 cardList的0下标的数据【删除】
        Card card = cardList.remove(0);
        List<Card> hand = hands.get(j);
        hand.add(i,card);//这里使用add 不能是set
        /*hands.get(j).add(card);*/
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  1. 当我们此时打印cardList就是剩余的牌了，然后把所有的代码执行结果打印出来（此处主函数省略了，在后面总代码中有，结果截图只有部分结果）

附上总代码：

class Card {
    private String suit;
    private int rank;

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

    public String getSuit() {
        return suit;
    }

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

    public int getRank() {
        return rank;
    }

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

    @Override
    public String toString() {
        return "[ " + suit+" "+rank+" ]";
    }
}

public class TestCard {
    public static final String[] suits = {"♥","♠","♣","♦"};
    
    public static List<Card> buyCard() {
        List<Card> desk = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13 ; j++) {
                String suit = suits[i];
                Card card = new Card(suit,j);
                desk.add(card);
            }
        }
        return desk;
    }

    public static void shuffle(List<Card> cardList) {
        for (int i = cardList.size()-1; i > 0 ; i--) {
            Random random = new Random();
            int index = random.nextInt(i);
            swap(cardList,i,index);
        }
    }

    private static void swap(List<Card> cardList,int i,int j) {
        /*
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
         */
        Card tmp = cardList.get(i);

        cardList.set(i,cardList.get(j));

        cardList.set(j,tmp);
    }
    
    public static void main(String[] args) {
        List<Card> cardList = buyCard();
        System.out.println("买牌："+cardList);
        shuffle(cardList);
        System.out.println("洗牌："+cardList);

        List<Card> hand1 = new ArrayList<>();
        List<Card> hand2 = new ArrayList<>();
        List<Card> hand3 = new ArrayList<>();

        List<List<Card>> hands = new ArrayList<>();
        hands.add(hand1);
        hands.add(hand2);
        hands.add(hand3);

        // 5个人  轮流揭牌5张 i=0就是第一次
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                //每次揭牌都去获取 cardList的0下标的数据【删除】
                Card card = cardList.remove(0);
                List<Card> hand = hands.get(j);
                hand.add(i,card);//这里使用add 不能是set
                /*hands.get(j).add(card);*/
            }
        }

        System.out.println("第1个人的牌："+hand1);
        System.out.println("第2个人的牌："+hand2);
        System.out.println("第3个人的牌："+hand3);

        System.out.println("剩余的牌："+cardList);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览43103 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪