Leetcode 面试150题

NO.88 ：合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

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

示例 1：

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

1
2
3
4
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

1
2
3
4
5
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

分析：

这个题我一开始的思路是做两个指针p1和p2 从前往后来遍历把元素插入到nums1中，但是我发现对于循环条件的判断不是很明确，所以我采用了这个思路，从后往前遍历，判断循环出去的条件就是是否指针遍历为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution () {
	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) {
		//因为是非递减，谁大就把谁放到末尾然后-1
         //nums1[p--]
			if (nums1[p1] >= nums2[p2]) nums1[p--] = nums1[p1--];
             else nums1[p--] = nums2[p2--];
		}
		//最后如果有多余的nums2的元素就放入就可以
		while (p2 >=0) {
			nums1[p--] = nums2[p2--];
		}
	}
}

NO：27：移除元素

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

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

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

用户评测：

评测机将使用以下代码测试您的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

1
2
3
4
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

1
2
3
4
5
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

思路：

交换思想，也就是交换val元素与不相等的val元素的值，这样就可以变成删除的感觉

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int ans = nums.length;
            for (int i = 0; i < ans; ) {
                if (nums[i] == val) {
                    nums[i] = nums[ans - 1];
                    ans--;
                } else  i++;
            }
            return ans;
    }
}

NO：26. 删除有序数组中的重复项

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

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

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

No.120: Triangle（三角形最小路径和）

📖 题目描述

给定一个三角形结构的二维整数列表 triangle：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

从顶端出发，每次只能移动到下一行中相邻的两个数字，求从顶到底路径的 最小总和。

✅ 解题思路：自底向上动态规划（Bottom-Up DP）

🧠 思想

从倒数第二层开始，逐层往上，把每个位置的值更新为：

1
当前位置值 + 下面两条路径中较小的值

最终，顶端的位置就会变成整个三角形的最小路径和。

💡 状态转移公式

1
f[i][j] = triangle[i][j] + min(f[i+1][j], f[i+1][j+1])

🧪 示例演算

以如下 triangle 为例：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

从底向上更新：

1
2
3
第 3 层更新为: [7, 6, 10] ← 来自 [6+min(4,1), 5+min(1,8), 7+min(8,3)]
第 2 层更新为: [9, 10]
第 1 层更新为: [11]

最终结果：11

🧾 Java 实现（原地修改 triangle）

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minimumTotal(List<List<Integer>> f) {
        for (int i = f.size() - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f.get(i).set(j, f.get(i).get(j) + Math.min(f.get(i + 1).get(j), f.get(i + 1).get(j + 1)));
            }
        }
        return f.get(0).get(0);
    }
}

🔍 关键语句解释

f.get(i).get(j)

  • 获取第 i 行第 j 个元素的值，相当于二维数组中的 f[i][j]

f.get(i).set(j, value)

  • 将 value 设置到第 i 行第 j 个位置，等同于更新 f[i][j]

这句核心代码可以拆解为：

1
2
3
4
5
int cur = f.get(i).get(j);
int down = f.get(i + 1).get(j);
int downRight = f.get(i + 1).get(j + 1);
int newVal = cur + Math.min(down, downRight);
f.get(i).set(j, newVal);

⏱️ 复杂度分析

  • 时间复杂度：O(n²)，每个点都遍历一次
  • 空间复杂度：O(1)，直接在原数组中更新，无需额外空间