接上次博客：数据结构初阶（2）（ArrayList简介、ArrayList()的构造方法、ArrayList的扩容、方法和三种遍历方法、ArrayList实现杨辉三角、ArrayList 的优缺点）_di-Dora的博客-CSDN博客

1、给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须确保时间复杂度为O(N)，空间复杂度为O，并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

力扣链接：27. 移除元素 - 力扣（Leetcode）

因为它这里要求的是直接在原数组上进行修改，那么我们可以通过双指针法来原地修改输入数组，来实现移除元素的操作。

1、使用两个指针 left 和 right，初始化为数组的起始位置。

2、当 right 指向的元素等于要移除的值 val 时，将 right 指针向右移动一位。

3、当 right 指向的元素不等于要移除的值 val 时，将 right 指向的元素复制到 left 指向的位置，并同时将 left 和 right 指针都向右移动一位。

4、重复步骤 2 和步骤 3，直到 right 指针超过数组的长度。

5、返回 left 指针的值，即为新的长度。

public class RemoveElement {public static int removeElement(int[] nums, int val) {int left = 0;int right = 0;while (right < nums.length) {if (nums[right] != val) {nums[left] = nums[right];left++;}right++;}return left;}public static void main(String[] args) {int[] nums = {3, 2, 2, 3};int val = 3;int newLength = removeElement(nums, val);System.out.println("New Length: " + newLength);System.out.print("Modified Array: ");for (int i = 0; i < newLength; i++) {System.out.print(nums[i] + " ");}}
}

其实总的来说就是：

右指针指向当前将要处理的元素，左指针指向下一个将要被赋值的位置。

如果右指针指向的元素不等于 val ，那么就代表它是我们最后数组里面保留的数字，我们就可以将右指针指向的元素赋值给左指针，然后将左右指针同时++；

如果右指针指向的元素等于 val ，那么我们就要把它覆盖掉，这个时候保持左指针不动，右指针继续右移去寻找下一个不等于 val 的值，如果找到，那么把那个数字赋值给我们左指针仍指向的这个等于 val 的数字，相当于把它覆盖掉了。如果没有找到，那么就遗留在数组的最后不用去管它，当左右指针遍历完输入数组以后，我们 left 的值就是输出数组的长度。

在力扣的官方题解中还给出了一种效率更高的方法，这个方法避免了需要保留的元素的重复赋值操作（在原来的方法中，我们对需要保存下来的值也进行了一次从right到left赋值的操作）： 

作者：力扣官方题解
链接：https://leetcode.cn/problems/remove-element/solutions/730203/yi-chu-yuan-su-by-leetcode-solution-svxi/

class Solution {public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length;while (left < right) {if (nums[left] == val) {nums[left] = nums[right - 1];right--;} else {left++;}}return left;}
}

我们才学完 ArrayList ，可以试试使用 ArrayList 来实现移除元素的操作，尽管题目要求是原地修改输入数组，但是其实这里也是可以通过 ArrayList 辅助进行处理的。

import java.util.ArrayList;public class RemoveElement {public static int removeElement(int[] nums, int val) {ArrayList<Integer> list = new ArrayList<>();// 将不等于 val 的元素添加到 ArrayList 中for (int num : nums) {if (num != val) {list.add(num);}}// 将 ArrayList 中的元素复制回原数组int newSize = list.size();for (int i = 0; i < newSize; i++) {nums[i] = list.get(i);}return newSize;}public static void main(String[] args) {int[] nums = {3, 2, 2, 3};int val = 3;int newLength = removeElement(nums, val);System.out.println("New Length: " + newLength);System.out.print("Modified Array: ");for (int i = 0; i < newLength; i++) {System.out.print(nums[i] + " ");}}
}

我们这里甚至把原数组的值也改变了，使之只包含我们需要的数据。

2、给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。 nums 的其余元素与 nums 的大小不重要。返回 k 。

例如；

输入：nums = [0,0,1,1,1,2,2,3,3,4]

输出：5, nums = [0,1,2,3,4]

解释：函数应该返回新的长度5.并且原数组 nums 的前五个元素被修改为【0，1，2，3，4】不需要考虑数组中超出新长度后面的元素。

力扣链接：26. 删除有序数组中的重复项 - 力扣（Leetcode） 

这一题有一个地方值得注意：这是一个有序的数组，所以如果有重复元素，那么它们一定是相邻的，我们仍然可以沿用刚刚的双指针方法：

    public int removeDuplicates(int[] nums) {int left = 0;int right = 0;while (right < nums.length) {if (nums[left] == nums[right]) {right++;} else {if (nums[right] != nums[left + 1]) {nums[left + 1] = nums[right];}left++;right++;}}return left + 1;}

3、给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

对于这道题，如果要在不使用额外空间的情况下合并两个有序数组，我们可以考虑从后向前进行合并，避免元素的频繁移动。所以我们还是可以使用双指针法来完成：

1、初始化指针 p1，指向 nums1 的第一个元素，指针 p2，指向 nums2 的第一个元素。

2、创建一个临时数组 merged，用于存储合并后的数组。

3、比较 nums1[p1] 和 nums2[p2] 的值，将较小的值添加到 merged 数组中，并将对应指针向后移动一位。

4、重复步骤 3，直到其中一个数组的所有元素都添加到 merged 数组中。

5、将剩余的数组中的元素添加到 merged 数组中，如果是 nums1 数组剩余元素，无需处理；如果是 nums2 数组剩余元素，则直接复制到 merged 数组中。

6、将 merged 数组中的元素复制回 nums1 数组中。

 public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1;int p2 = n - 1;int p = m + n - 1;while (p1 >= 0 && p2 >= 0) {if (nums1[p1] > nums2[p2]) {nums1[p] = nums1[p1];p1--;} else {nums1[p] = nums2[p2];p2--;}p--;}// 将 nums2 中剩余的元素合并到 nums1 中while (p2 >= 0) {nums1[p] = nums2[p2];p2--;p--;}}

这种方法只使用了常量级的额外空间，符合题目要求的空间复杂度为 O(1)，同时也满足题目要求的将合并后的数组存储在 nums1 中。

如果用上了 ArrayList 就会有点复杂：

import java.util.ArrayList;
import java.util.List;public class MergeSortedArray {public static void merge(int[] nums1, int m, int[] nums2, int n) {List<Integer> merged = new ArrayList<>();int p1 = 0;int p2 = 0;while (p1 < m && p2 < n) {if (nums1[p1] < nums2[p2]) {merged.add(nums1[p1]);p1++;} else {merged.add(nums2[p2]);p2++;}}while (p1 < m) {merged.add(nums1[p1]);p1++;}while (p2 < n) {merged.add(nums2[p2]);p2++;}// 将 merged 数组复制回 nums1for (int i = 0; i < merged.size(); i++) {nums1[i] = merged.get(i);}}public static void main(String[] args) {int[] nums1 = {1, 3, 5, 0, 0, 0};int[] nums2 = {2, 4, 6};int m = 3;int n = 3;merge(nums1, m, nums2, n);System.out.print("Merged Array: ");for (int num : nums1) {System.out.print(num + " ");}}
}

这种方法使用了额外的 ArrayList 来存储合并后的数组，然后将其复制回 nums1 数组。

注意，这种方法的空间复杂度为 O(m+n)，不符合题目要求的原地修改输入数组的要求。

4、简单的洗牌算法：

我们先来定义一下我们的扑克牌类：

public class Card {public int rank; // 扑克牌的数字public String suit; // 花色public int getRank() {return rank;}public void setRank(int rank) {this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public Card() {}public Card(String suit,int rank) {this.rank = rank;this.suit = suit;}@Overridepublic String toString() {return String.format("[%s %d]", suit, rank);}}

好了，现在我们要开始洗牌发牌了：

先思考一下，一共需要几个方法？

我们是不是得先有一副完整的扑克牌？（当然啦，没有“大小王”的，否则就太困难了） 

所以我们首先需要买一副完整的扑克牌。

有了一副完整的扑克，那我们是不是得先打乱这副牌的顺序？

因为刚买回来的牌必然是按照花色和数字排好的，这将导致大家拿到的牌是相邻的，花色几乎一样。

所以我们还需要一个洗牌的方法。

我们还需要注意：每个人摸牌的时候是怎么摸的？

我们定义，三个人，每个人轮流抓 5 张牌，每轮一人拿一张牌。

import java.awt.*;
import java.util.*;
import java.util.List;public class CardList {public static final String[] SUITS = {"♠", "♥", "♣", "♦"};//花色一般不会改变，所以可以加static// 买一副牌private static List<Card> buyDeck() {List<Card> deck = new ArrayList<>(52);for (int i = 0; i < SUITS.length; i++) {for (int j = 1; j <= 13; j++) {//1
/*                String suit = SUITS[i];int rank = j;Card card = new Card();card.rank = rank;card.suit = suit;*///2
/*                String suit = SUITS[i];int rank = j;Card card = new Card(suit,rank);*///3Card card = new Card(SUITS[i],j);deck.add(card);}}return deck;}//交换牌面private static void swap(List<Card> deck, int i, int j) {Card t = deck.get(i);deck.set(i, deck.get(j));deck.set(j, t);}//洗牌private static void shuffle(List<Card> deck) {Random random = new Random();//倒着遍历，50的时候生成的就是1~49的随机数for (int i = deck.size() - 1; i > 0; i--) {int r = random.nextInt(i);swap(deck, i, r);}}public static void main(String[] args) {List<Card> deck = buyDeck();System.out.println("刚买回来的牌:");System.out.println(deck);shuffle(deck);System.out.println("洗过的牌:");System.out.println(deck);// 总共有三个人，每个人轮流抓 5 张牌//每轮一人拿一张牌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); //控制每个人摸牌的次数for (int i = 0; i < 5; i++) {//三个人轮流揭牌for (int j = 0; j < 3; j++) {//hands.get(j).add(deck.remove(0));Card card = deck.remove(0);hands.get(j).add(card);}}System.out.println("剩余的牌:");System.out.println(deck);System.out.println("A 手中的牌:");System.out.println(hands.get(0));System.out.println("B 手中的牌:");System.out.println(hands.get(1));System.out.println("C 手中的牌:");System.out.println(hands.get(2));}}

这里面有一句代码可能比较难以理解：

hands.get(j).add(deck.remove(0)) ;

或者我们也可以写为： Card card = deck.remove(0);       hands.get(j).add(card);

它表示将牌堆 deck 中的第一张牌（索引为0）移除，并将其添加到 hands 列表中第 j 个玩家的手牌中。

具体步骤如下：

1、  hands.get(j)：根据索引 j 获取 hands 列表中第j个玩家的手牌列表。
2、 .add(deck.remove(0))：将 deck 列表中的第一张牌移除，并使用 .add() 方法将其添加到玩家的手牌列表中。

当然，你可能会疑惑：

这个代码里面：Card card = deck.remove(0);  hands.get(j).add(card);，

一旦执行deck.remove(0); 不就代表那个牌已经被移除了吗？还怎么添加到集合里？

其实：deck.remove(0)会从列表中删除指定位置的元素，并将其返回。

因此，执行完deck.remove(0)后，牌堆中的第一张牌已经被移除，而card变量中保存了该牌的引用。

接下来，hands.get(j).add(card)将card添加到相应玩家的手牌集合中，即将已经移除的牌加入到集合中，这样玩家就获得了这张牌。

最后实现效果如下：