文章目录杨辉三角(LC118)题目描述解题思路代码示例旋转数组(LC189)题目描述解题思路代码示例洗牌算法1. 功能描述2. 代码设计3. 核心功能1 定义扑克牌实体Card类2 创建完整牌组buyCards()方法3洗牌算法shuffle()方法4发牌逻辑play()方法4. 测试杨辉三角(LC118)杨辉三角题目描述给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。在「杨辉三角」中每个数是它左上方和右上方的数的和。示例 1:输入: numRows 5输出:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:输入: numRows 1输出:[[1]]解题思路杨辉三角可以当做二维数组处理每一层是一个List列表整体由多层List列表构成。先定义二维列表ret作为杨辉三角1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ...第一行只有一个1比较特殊要单独处理。定义list0并添加1接着ret添加list0作为第一行第二行以后就可以用循环实现。外层循环从i1开始到指定行数截止。定义列表curRow先添加1再调用循环添加中间数据。定义列表prevRow用来获取上一行的元素。当前行第j个数据就是上一行第j-1与第j个数据之和。循环从1开始到i结束。最后在尾部添加1并把curRow加到ret中代码示例publicclassSolution1{publicListListIntegergenerate(intnumRows){ListListIntegerretnewArrayList();ListIntegerlist0newArrayList();list0.add(1);ret.add(list0);for(inti1;inumRows;i){ListIntegercurRownewArrayList();//头部curRow.add(1);//中间ListIntegerprevRowret.get(i-1);for(intj1;ji;j){curRow.add(prevRow.get(j-1)prevRow.get(j));}//尾部curRow.add(1);ret.add(curRow);}returnret;}}旋转数组(LC189)旋转数组题目描述给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。示例 1:输入:nums [1,2,3,4,5,6,7], k 3输出:[5,6,7,1,2,3,4]解释:向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]示例 2:输入nums [-1,-100,3,99], k 2输出[3,99,-1,-100]解释:向右轮转 1 步:[99,-1,-100,3]向右轮转 2 步:[3,99,-1,-100]解题思路思路1 当k大于数组长度时只需要取余。令kk % nums.length创建变量tmp存放nums[0],再依次向左挪动元素把tmp赋给最后一个空间循环k次。这种解法虽然正确但是时间花销太大力扣不予通过。思路2先整体翻转再分两次翻转回来定义一个方法翻转数组先整体翻转把下标k-1之前的元素翻转回来把下标k以后的元素翻转回来代码示例classSolution2{voidrotate(int[]nums,intleft,intright){while(leftright){inttempnums[left];nums[left]nums[right];nums[right]temp;left;right--;}}publicvoidrotate(int[]nums,intk){k%nums.length;rotate(nums,0,nums.length-1);//7 6 5 4 3 2 1rotate(nums,0,k-1);//5 6 7 4 3 2 1rotate(nums,k,nums.length-1);// 5 6 7 1 2 3 4}}洗牌算法1. 功能描述生成一副牌52张打乱顺序分发给三个人每次发五张2. 代码设计Card类封装一张扑克牌的属性花色点数是数据载体CardDemo类包含创建牌组、洗牌、发牌的核心方法是行为实现的工具类。3. 核心功能1 定义扑克牌实体Card类一张牌包含花色和点数两个属性同时需要重写toString()方法直观表示这两个属性。publicclassCard{//花色♥️、♠️、♣️、♦️、点数1-13对应A-KprivateStringsuit;privateintrank;publicCard(Stringsuit,intrank){this.suitsuit;this.rankrank;}OverridepublicStringtoString(){// 将1转为A11转为J12转为Q13转为KStringrankStrswitch(rank){case1-A;case11-J;case12-Q;case13-K;default-String.valueOf(rank);};returnsuitrankStr;}publicStringgetSuit(){returnsuit;}publicintgetRank(){returnrank;}}关键说明rank点数用1-13表示后续通过toString()转为更易读的“A、2-10、J、Q、K”必须重写toString()否则调用cardList.toString()时会输出[Card.Card1b6d3586, ...]这类对象地址无法看到实际牌面。2 创建完整牌组buyCards()方法staticfinalString[]suits{♥️,♠️,♣️,♦️};publicListCardbuyCards(){ListCardcardListnewArrayList();// 遍历点数1-13对应A-Kfor(inti1;i13;i){// 遍历花色for(intj0;j4;j){CardnewCardnewCard(suits[j],i);cardList.add(newCard);}}returncardList;}3洗牌算法shuffle()方法算法原理从牌组的最后一张牌索引size-1开始向前遍历对于当前索引i生成一个[0, i]范围内的随机索引j交换索引i和j对应的两张牌重复步骤2-3直到遍历到第2张牌索引1。为什么从后往前确保每一张牌被交换到随机位置的概率均等每一步都有1/(i1)的概率被选中避免重复交换导致的随机性偏差。publicvoidshuffle(ListCardcardList){RandomrandomnewRandom();for(inticardList.size()-1;i0;i--){// 生成[0, i]范围内的随机索引jnextInt(i1)的范围是0到iintjrandom.nextInt(i1);swap(cardList,i,j);}}voidswap(ListCardcardList,inti,intj){CardtmpcardList.get(j);cardList.set(j,cardList.get(i));cardList.set(i,tmp);}注意random.nextInt(i 1)必须加1否则nextInt(i)的范围是[0, i-1]会导致最后一张牌永远不会被交换到第1个位置4发牌逻辑play()方法发牌的需求是“将洗好的牌分发给3个人每人5张”核心思路是“循环发牌每次给1个人发1张直到发完15张3人×5张”。publicvoidplay(ListCardcardList){// 存储3个玩家的牌组每个玩家是一个ListCardListListCardpersonListnewArrayList(3);ListCardperson1newArrayList();ListCardperson2newArrayList();ListCardperson3newArrayList();personList.add(person1);personList.add(person2);personList.add(person3);for(inti0;i5;i){for(intj0;j3;j){CardcardcardList.removeFirst();personList.get(j).add(card);}}4. 测试publicstaticvoidmain(String[]args){CardDemocardDemonewCardDemo();// 买牌ListCardcardListcardDemo.buyCards();System.out.println(买牌后未洗牌cardList);// 洗牌cardDemo.shuffle(cardList);System.out.println(\n洗牌后cardList);// 发牌System.out.println(\n发牌结果);cardDemo.play(cardList);// 剩余牌组System.out.println(\n剩余牌数cardList.size()张);System.out.println(剩余牌组cardList);}测试结果买牌后[♥️A, ♠️A, ♣️A, ♦️A, ♥️2, ♠️2, ..., ♦️K] 洗牌后[♣️5, ♥️J, ♦️7, ♠️3, ♣️Q, ..., ♥️8] 发牌结果 玩家1的牌[♣️5, ♦️3, ♠️J, ♣️7, ♦️Q] 玩家2的牌[♥️J, ♥️5, ♦️K, ♠️8, ♣️2] 玩家3的牌[♦️7, ♠️A, ♣️K, ♥️9, ♦️2] 剩余牌数37张 剩余牌组[♠️10, ♥️3, ..., ♥️8]
【算法日记】杨辉三角，轮转数组，洗牌算法
文章目录杨辉三角(LC118)题目描述解题思路代码示例旋转数组(LC189)题目描述解题思路代码示例洗牌算法1. 功能描述2. 代码设计3. 核心功能1 定义扑克牌实体Card类2 创建完整牌组buyCards()方法3洗牌算法shuffle()方法4发牌逻辑play()方法4. 测试杨辉三角(LC118)杨辉三角题目描述给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。在「杨辉三角」中每个数是它左上方和右上方的数的和。示例 1:输入: numRows 5输出:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:输入: numRows 1输出:[[1]]解题思路杨辉三角可以当做二维数组处理每一层是一个List列表整体由多层List列表构成。先定义二维列表ret作为杨辉三角1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ...第一行只有一个1比较特殊要单独处理。定义list0并添加1接着ret添加list0作为第一行第二行以后就可以用循环实现。外层循环从i1开始到指定行数截止。定义列表curRow先添加1再调用循环添加中间数据。定义列表prevRow用来获取上一行的元素。当前行第j个数据就是上一行第j-1与第j个数据之和。循环从1开始到i结束。最后在尾部添加1并把curRow加到ret中代码示例publicclassSolution1{publicListListIntegergenerate(intnumRows){ListListIntegerretnewArrayList();ListIntegerlist0newArrayList();list0.add(1);ret.add(list0);for(inti1;inumRows;i){ListIntegercurRownewArrayList();//头部curRow.add(1);//中间ListIntegerprevRowret.get(i-1);for(intj1;ji;j){curRow.add(prevRow.get(j-1)prevRow.get(j));}//尾部curRow.add(1);ret.add(curRow);}returnret;}}旋转数组(LC189)旋转数组题目描述给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。示例 1:输入:nums [1,2,3,4,5,6,7], k 3输出:[5,6,7,1,2,3,4]解释:向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]示例 2:输入nums [-1,-100,3,99], k 2输出[3,99,-1,-100]解释:向右轮转 1 步:[99,-1,-100,3]向右轮转 2 步:[3,99,-1,-100]解题思路思路1 当k大于数组长度时只需要取余。令kk % nums.length创建变量tmp存放nums[0],再依次向左挪动元素把tmp赋给最后一个空间循环k次。这种解法虽然正确但是时间花销太大力扣不予通过。思路2先整体翻转再分两次翻转回来定义一个方法翻转数组先整体翻转把下标k-1之前的元素翻转回来把下标k以后的元素翻转回来代码示例classSolution2{voidrotate(int[]nums,intleft,intright){while(leftright){inttempnums[left];nums[left]nums[right];nums[right]temp;left;right--;}}publicvoidrotate(int[]nums,intk){k%nums.length;rotate(nums,0,nums.length-1);//7 6 5 4 3 2 1rotate(nums,0,k-1);//5 6 7 4 3 2 1rotate(nums,k,nums.length-1);// 5 6 7 1 2 3 4}}洗牌算法1. 功能描述生成一副牌52张打乱顺序分发给三个人每次发五张2. 代码设计Card类封装一张扑克牌的属性花色点数是数据载体CardDemo类包含创建牌组、洗牌、发牌的核心方法是行为实现的工具类。3. 核心功能1 定义扑克牌实体Card类一张牌包含花色和点数两个属性同时需要重写toString()方法直观表示这两个属性。publicclassCard{//花色♥️、♠️、♣️、♦️、点数1-13对应A-KprivateStringsuit;privateintrank;publicCard(Stringsuit,intrank){this.suitsuit;this.rankrank;}OverridepublicStringtoString(){// 将1转为A11转为J12转为Q13转为KStringrankStrswitch(rank){case1-A;case11-J;case12-Q;case13-K;default-String.valueOf(rank);};returnsuitrankStr;}publicStringgetSuit(){returnsuit;}publicintgetRank(){returnrank;}}关键说明rank点数用1-13表示后续通过toString()转为更易读的“A、2-10、J、Q、K”必须重写toString()否则调用cardList.toString()时会输出[Card.Card1b6d3586, ...]这类对象地址无法看到实际牌面。2 创建完整牌组buyCards()方法staticfinalString[]suits{♥️,♠️,♣️,♦️};publicListCardbuyCards(){ListCardcardListnewArrayList();// 遍历点数1-13对应A-Kfor(inti1;i13;i){// 遍历花色for(intj0;j4;j){CardnewCardnewCard(suits[j],i);cardList.add(newCard);}}returncardList;}3洗牌算法shuffle()方法算法原理从牌组的最后一张牌索引size-1开始向前遍历对于当前索引i生成一个[0, i]范围内的随机索引j交换索引i和j对应的两张牌重复步骤2-3直到遍历到第2张牌索引1。为什么从后往前确保每一张牌被交换到随机位置的概率均等每一步都有1/(i1)的概率被选中避免重复交换导致的随机性偏差。publicvoidshuffle(ListCardcardList){RandomrandomnewRandom();for(inticardList.size()-1;i0;i--){// 生成[0, i]范围内的随机索引jnextInt(i1)的范围是0到iintjrandom.nextInt(i1);swap(cardList,i,j);}}voidswap(ListCardcardList,inti,intj){CardtmpcardList.get(j);cardList.set(j,cardList.get(i));cardList.set(i,tmp);}注意random.nextInt(i 1)必须加1否则nextInt(i)的范围是[0, i-1]会导致最后一张牌永远不会被交换到第1个位置4发牌逻辑play()方法发牌的需求是“将洗好的牌分发给3个人每人5张”核心思路是“循环发牌每次给1个人发1张直到发完15张3人×5张”。publicvoidplay(ListCardcardList){// 存储3个玩家的牌组每个玩家是一个ListCardListListCardpersonListnewArrayList(3);ListCardperson1newArrayList();ListCardperson2newArrayList();ListCardperson3newArrayList();personList.add(person1);personList.add(person2);personList.add(person3);for(inti0;i5;i){for(intj0;j3;j){CardcardcardList.removeFirst();personList.get(j).add(card);}}4. 测试publicstaticvoidmain(String[]args){CardDemocardDemonewCardDemo();// 买牌ListCardcardListcardDemo.buyCards();System.out.println(买牌后未洗牌cardList);// 洗牌cardDemo.shuffle(cardList);System.out.println(\n洗牌后cardList);// 发牌System.out.println(\n发牌结果);cardDemo.play(cardList);// 剩余牌组System.out.println(\n剩余牌数cardList.size()张);System.out.println(剩余牌组cardList);}测试结果买牌后[♥️A, ♠️A, ♣️A, ♦️A, ♥️2, ♠️2, ..., ♦️K] 洗牌后[♣️5, ♥️J, ♦️7, ♠️3, ♣️Q, ..., ♥️8] 发牌结果 玩家1的牌[♣️5, ♦️3, ♠️J, ♣️7, ♦️Q] 玩家2的牌[♥️J, ♥️5, ♦️K, ♠️8, ♣️2] 玩家3的牌[♦️7, ♠️A, ♣️K, ♥️9, ♦️2] 剩余牌数37张 剩余牌组[♠️10, ♥️3, ..., ♥️8]