开始正式了解结构...😊
一、认识顺序表
1、基本结构
顺序表是一种线性表，它用一段地址连续的存储单元依次存储线性表的数据元素
比喻：电影院座位把顺序表想象成电影院里一排连续的座位连续存储：这些座位是紧挨着的，一个接一个，这就是“顺序”的含义---数据在物理内存中是连续存储的快速“按号找座”：如果你想找第5个座位上坐的是谁，你可以计算出来并直接走过去“插队”与“离场”麻烦：插入：如果这排座位已经坐满了，你想在中间加一个人，那么从这个位置开始以后的所有人都需要向后移动一个位置，才能空出一个新的座位删除：同理，如果中间有一个人离开了，那么他后面的所有人都需要向前移动一个位置来填补空位，以保持座位的连续性
2、手动实现：
package structure; public interface IList { //新增元素,默认在数组最后插入 void add(int data); //在 pos 位置插入新增元素 void add(int pos, int data); //判定是否包含某个元素 boolean contains(int toFind); //查找某个元素对应的位置 int indexOf(int toFind); //获取 pos 位置的元素 int get(int pos); //给 pos 位置的元素设为 value void set(int pos, int value); //删除第一次出现的关键字key void remove(int toRemove); //获取顺序表长度 int size(); //清空顺序表 void clear(); //打印顺序表,该方法并不是顺序表中的方法,是方便看测试结果给出的 void display(); //空的还是满的 boolean isFull(); boolean isEmpty(); }
package structure; import loose.ListEmptyException; import java.lang.management.MemoryManagerMXBean; import java.util.ArrayList; import java.util.Arrays; import java.util.EmptyStackException; public class MarryList implements IList { private int[] array; //私有的：只在类内部调用 //静态的：所有创建的对象共享，不用反复创建占用内存 //常量的：规定常量不变，命名采用“全大写+下划线” //代表默认数组容量 private static final int DEFAULT_CAPACITY = 5; //数组元素个数 private int count = 0; public MarryList(){ array = new int[DEFAULT_CAPACITY]; } //自己实现的方法，并进行了封装，不希望外部调用 //数组扩容 private void grow(){ if(isFull()){ array = Arrays.copyOf(array,array.length*2); } } //检查pos位置合法性 private void checkPos(int pos){ if(pos < 0 || pos > count){ throw new OutBoundException("pos位置不合法:" + "pos = "+pos); } } @Override public void add(int data) { grow(); array[count++] = data; // array[count] = data; // count++; } //在指定pos位置插入元素 @Override public void add(int pos, int data) { grow(); checkPos(pos); //从最后一个元素位置开始，数据依次前移， //直到插入位置pos(包括pos)时停止 for (int i = count-1; i >= pos; i--) { array[i+1] = array[i]; } array[pos] = data; //最后别忘了更新元素个数 count++; } @Override public boolean contains(int toFind) { for (int i = 0; i < count; i++) { if(array[i] == toFind){ return true; } } return false; } @Override public int indexOf(int toFind) { for (int i = 0; i < count; i++) { if (array[i] == toFind){ return i; } } return -1; } @Override public int get(int pos) { //先验证数组是不是空的，再检查位置合法性 if (isEmpty()) { throw new ListEmptyException("数组是空的"); } checkPos(pos); return array[pos]; } @Override public void set(int pos, int value) { checkPos(pos); array[pos] = value; } @Override public void remove(int toRemove) { int s = indexOf(toRemove); if (s == -1){ System.out.println("没有要删除的元素"); //别忘了return防止继续往下执行 return; } //注意这里跟add的区别 for (int i = s; i < count - 1 ; i++) { array[i] = array[i+1]; } //别忘了最后减一个元素 count--; } @Override public int size() { return count; } @Override public void clear() { //让如果是引用类型，需要一个个遍历并给它们设置成null // for (int i = 0; i < count; i++) { // array[i] = null; // } count = 0; } @Override public void display() { for (int i = 0; i <count; i++) { System.out.print(array[i]+" "); } System.out.println(); } @Override public boolean isFull() { return array.length == count; } @Override public boolean isEmpty() { return count == 0; } //endregion public static void main(String[] args) { MarryList m = new MarryList(); m.add(1); m.add(2); m.add(3); m.add(4); m.add(5); m.add(99); m.display(); } }
package structure; public class OutBoundException extends RuntimeException{ public OutBoundException(String message) { super(message); } }
自己实现过后有助于更好的理解顺序表，有助于后面使用ArrayList
3、对于add与remove移动方向的着重分析😮
①add的在指定位置pos增添元素
如图：
array[i+1] = array[i];
②remove删除元素
如图：
array[i] = array[i+1];
稍微注意一下这两个方法的区别即可
二、几种遍历手法😆
随着学的容器越来越多，延伸出来的遍历写法也会更灵活：
package structure; import java.util.ArrayList; import java.util.Iterator; public class Demo4 { public static void main(String[] args) { ArrayList<Integer> arrayList = new ArrayList<>(); arrayList.add(1); arrayList.add(2); arrayList.add(3); arrayList.add(4); arrayList.add(5); // 直接就能打印数组 System.out.println(arrayList); // 常规遍历：先获取下标再取值 for (int i = 0; i < arrayList.size(); i++) { System.out.print(arrayList.get(i) + " "); } System.out.println(); // 更简洁的遍历写法：for-each遍历 for (Integer x : arrayList) { System.out.print(x+" "); } System.out.println(); // 各种各样的迭代器写法... Iterator<Integer> it = arrayList.iterator(); // hasNext(): 检查还有没有下一个元素 while (it.hasNext()){ // next(): 取出下一个元素 int x = it.next(); System.out.print(x + " "); } System.out.println(); } }
可以注意下后两种，有时候要比传统遍历要简洁
三、两个ArrayList具体实现的题目：
1、杨辉三角
118. 杨辉三角 - 力扣（LeetCode）2、简单的洗牌算法
代码示例：
①
package structure; import java.util.ArrayList; import java.util.List; public class Solution1 { public List<List<Integer>> generate(int numRows){ //先把第一行处理了 //创建二维结构 List<List<Integer>> ret = new ArrayList<>(); //创建第一行的表 List<Integer> list = new ArrayList<>(); list.add(1); ret.add(list); //开始处理每一行 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]+[i-1][j-1] int num = preRow.get(j)+preRow.get(j-1); curRow.add(num); } //每一行的最后一个数字 curRow.add(1); ret.add(curRow); } return ret; } public static void main(String[] args) { System.out.println(new Solution1().generate(5)); } }
②
package structure; public class Card { public String suit; public String rank; public Card(String suit, String rank) { this.suit = suit; this.rank = rank; } @Override public String toString() { return suit + rank; } }
package structure; import java.util.ArrayList; import java.util.List; import java.util.Random; public class CardGame { public String[] suits = {"♠","♣","♥","♦"}; public String[] ranks = {"A","2","3","4","5", "6","7","8","9","10","J","Q","K"}; static List<Card> cards = new ArrayList<>(); //获取牌 public void getCards(){ // for (int i = 0; i < suits.length; i++) { // for (int j = 0; j < ranks.length; j++) { // Card card = new Card(suits[i],ranks[j]); // cards.add(card); // } // } for (String suit : suits){ for (String rank : ranks){ Card card = new Card(suit,rank); cards.add(card); } } } //洗牌 public void shuffle(List<Card> cards){ //写到外边，防止每次循环都创建 Random r = new Random(); //.size()方法取的是元素个数 for (int i = cards.size() - 1;i > 0;i--){ //取的是0到i的随机数 int index = r.nextInt(i + 1); swap(cards,index,i); } } public void swap(List<Card> cards, int i, int j){ //List结构不支持下标访问 // Card tmp = cards[i]; // 把i柜的东西拿出来 // cards[i] = cards[j]; // 把j柜的东西放进i柜 // cards[j] = tmp; // 把拿出来的东西放进j柜 Card tmp = cards.get(i); cards.set(i,cards.get(j)); cards.set(j,tmp); } //抓牌 public void grab(){ List <List<Card>> hands = new ArrayList<>(); List <Card> hands0 = new ArrayList<>(); List <Card> hands1 = new ArrayList<>(); List <Card> hands2 = new ArrayList<>(); hands.add(hands0); hands.add(hands1); hands.add(hands2); //模拟三人轮流抓取五张牌 //注意此处写法 for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { Card card = cards.remove(0); hands.get(j).add(card); } } System.out.println("第一个人抓取的牌："+ hands0); System.out.println("第二个人抓取的牌："+ hands1); System.out.println("第三个人抓取的牌："+ hands2); } public static void main(String[] args) { CardGame cardGame = new CardGame(); cardGame.getCards(); cardGame.shuffle(cards); System.out.println("洗完后的牌："+cards); cardGame.grab(); } }
题目解析 😎：
例①、首先我们需要创建如下结构：
public List<List<Integer>> generate(int numRows)
这里画成图，本质就是一个二维数组结构：
把杨辉三角画成这样，更利于我们解决问题：
这里核心解决思路就是需要发现，中间元素的值等于上一行同列元素与上一行前一列元素之和，结合上面代码就明白怎么解决了😊
例②、首先创建一张牌的结构（一张牌包括花色和点数）：
public class Card {
}
给定数组常量，遍历所有花色点数按顺序拿到每一张牌：
public void getCards(){}
接着开始洗牌，洗牌算法的本质就是🙂：
“第i步，在0到i之间随机选一个位置，和i交换”
这里是从后往前换，从前往后写麻烦且不符合习惯
最后的抓牌又可以看成一个二维结构：
抓牌的逻辑可以看成不断remove第一张牌，轮流保存到三人的手牌中
其他具体代码细节可见代码示例🤗
本章完
