【leetcode】杨辉三角 、移除元素（Java语言描述）

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

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

示例 2:

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

解题思路

杨辉三角（Pascal's Triangle）是一个由数字排列成的三角形，每个数字等于其上方两个数字之和。下面是两种方案的解题思路及对应的Java代码。

解题思路

1. 使用二维数组：

   • 创建一个二维数组来存储杨辉三角的每一行。
   • 第一行和第二行的元素为1。
   • 从第三行开始，每个元素为其上方两个元素的和。
   • 逐行填充数组，直到达到所需的行数。

2. 使用顺序表（ArrayList）：

   • 使用ArrayList来存储每一行的内容。
   • 每一行创建一个新的ArrayList，第一列和最后一列为1。
   • 中间的元素则由前一行的两个上方元素相加得出。
   • 最终将每一行的ArrayList添加到一个大的ArrayList中。

方案一：使用二维数组

public class PascalTriangle {
    public int[][] generate(int numRows) {
        int[][] triangle = new int[numRows][];
        
        for (int i = 0; i < numRows; i++) {
            triangle[i] = new int[i + 1]; // 每行的长度
            triangle[i][0] = 1; // 第一列赋值为1
            triangle[i][i] = 1; // 最后一列赋值为1
            
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
        }
        
        return triangle;
    }
 
    public static void main(String[] args) {
        PascalTriangle pt = new PascalTriangle();
        int[][] result = pt.generate(5); // 生成前5行的杨辉三角
        for (int[] row : result) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

方案二：使用顺序表（ArrayList）

import java.util.ArrayList;
import java.util.List;
 
public class PascalTriangle {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            row.add(1); // 第一列赋值为1
            
            if (i > 0) {
                List<Integer> prevRow = triangle.get(i - 1);
                for (int j = 1; j < i; j++) {
                    // 中间的元素
                    row.add(prevRow.get(j - 1) + prevRow.get(j));
                }
                row.add(1); // 最后一列赋值为1
            }
            
            triangle.add(row);
        }
        
        return triangle;
    }
 
    public static void main(String[] args) {
        PascalTriangle pt = new PascalTriangle();
        List<List<Integer>> result = pt.generate(5); // 生成前5行的杨辉三角
        for (List<Integer> row : result) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

总结

两种方案都能够有效地生成杨辉三角，使用二维数组的方式在内存上相对更高效，而使用ArrayList的方法更加灵活，适合需要动态调整大小情况下的存储需求。根据实际情况选择合适的方案。

移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

解题思路

在处理“移除元素”的问题时，我们可以采用两种常见解法。下面将用文字解析并提供 Java 代码实现这两种方案。

解法一：双指针法

这种方法使用两个指针，其中一个指针遍历数组，另一个指针用于记录不等于 val 的元素的插入位置。遍历数组的过程中，当我们遇到不等于 val 的元素时，就把它放到有效数组的位置。

代码实现：

public class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0; // k表示不等于val的元素数量
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i]; // 将不等于val的元素移动到前面
                k++; // 不等于val的元素计数器加一
            }
        }
        return k; // 返回不等于val的元素个数
    }
}

解析：

1. 初始化一个指针 k 为 0，用于记录不等于 val 的元素个数。
2. 使用一个循环遍历数组中的每个元素，当遇到不等于 val 的元素时，将其存入 nums[k]，然后 k 加一。
3. 最终，k 就是数组中不等于 val 的元素数量。

解法二：覆盖法

这种方法也是通过一个指针遍历数组，但在遍历的过程中，如果元素等于 val，就继续向后查找，找到不等于 val 的元素后进行覆盖。

代码实现：

public class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == val) {
                // 如果当前元素是val，就从后面开始找
                while (n - 1 > i && nums[n - 1] == val) {
                    n--; // 缩短数组长度
                }
                if (n - 1 > i) {
                    nums[i] = nums[n - 1]; // 将后面的不等于val的元素移到当前位置
                    n--; // 缩短数组长度
                }
            }
        }
        return n; // n即为不等于val的元素个数
    }
}

解析：

1. 使用 n 记录当前数组长度，通过循环遍历每个元素。
2. 当遇到等于 val 的元素时，使用一个内部的 while 循环从后往前查找，找到不等于 val 的元素来进行覆盖。
3. 每次完成覆盖后，n 减少表示当前数组长度减少，最终返回的 n 即为不等于 val 的元素数量。

总结

这两种解法都能有效地实现需求，使用不同的指针策略，可以根据具体情况选择实现。双指针法相对简洁直观，而覆盖法在某些情况下可能更高效。此题所采用的数组原地操作符合要求，元素顺序可被打乱，这是其允许的特性。