面试经典150题
1. 数组/字符串
1.1 合并两个有序数组
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
?输入：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：
?输入：nums1 = [1], m = 1, nums2 = [], n = 0
?输出：[1]
?解释：需要合并 [1] 和 [] 。
?合并结果是 [1] 。
示例 3：
?输入：nums1 = [0], m = 0, nums2 = [1], n = 1
?输出：[1]
?解释：需要合并的数组是 [] 和 [1] 。
?合并结果是 [1] 。
?注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
题解
方法1
将nums2赋值到nums1的后半部分，再调用Arrays的sort方法。
public static int[] merge_1(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
return nums1;
}方法2
借鉴归并排序的思想。从末尾开始，从大到小排序。
public static int[] merge_2(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
return nums1;
}1.2移除元素
题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
?输入：nums = [3,2,2,3], val = 3
?输出：2, nums = [2,2]
?解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
?输入：nums = [0,1,2,2,3,0,4,2], val = 2
?输出：5, nums = [0,1,3,0,4]
?解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
题解
遍历int数组，将不等于val的值加入到新的list中。循环赋值，返回结果。
public static ResultType removeElement(int[] nums, int val) {
ArrayList<Integer> list = new ArrayList<>();
for (int num : nums) {
if (num != val) {
list.add(num);
}
}
for (int i = 0; i < list.size(); i++) {
nums[i] = list.get(i);
}
return new ResultType(list.size(), list);
}1.3 删除有序数组中的重复项
题目
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k
示例 1：
?输入：nums = [1,1,2]
?输出：2, nums = [1,2,_]
?解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
?输入：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 。不需要考虑数组中超出新长度后面的元素。
题解
利用快慢指针(双指针)。慢指针用来锁定满足条件的元素。快指针检索相邻的元素是否相等，如果不相等，则将快指针指向的元素赋值给慢指针指向的元素。
public static ResultType removeDuplicates(int[] nums) {
// Double pointer
int slow=1;
for (int fast = 1; fast < nums.length; fast++) {
if(nums[fast]!=nums[fast-1])
nums[slow++]=nums[fast];
}
return new ResultType(slow, nums);
}1.4 删除有序数组中的重复项 II ***
题目
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
?输入：nums = [1,1,1,2,2,3]
?输出：5, nums = [1,1,2,2,3]
?解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例 2：
?输入：nums = [0,0,1,1,1,1,2,3,3]
?输出：7, nums = [0,0,1,1,2,3,3]
?解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
题解
方法1
经典双指针。
public static ResultType removeDuplicates_1(int[] nums) {
int n = nums.length;
if (n <= 2) {
return new ResultType(-1, nums);
}
int slow = 2, fast = 2;
while (fast < n) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return new ResultType(slow, nums);
}方法2
使用计数法。
public static ResultType removeDuplicates_2(int[] nums) {
// skip 1st and 2nd element
int count = 2;
for(int i = 2 ; i < nums.length ; i++) {
if(nums[i] != nums[count-2]) {
nums[count++] = nums[i];
}
}
return new ResultType(count, nums);
}1.5 多数元素
题目
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
?输入：nums = [3,2,3]
?输出：3
示例 2：
?输入：nums = [2,2,1,1,1,2,2]
?输出：2
题解
方法1
摩尔投票
public static int majorityElement(int[] nums) {
//诸王争霸赛开始【规则是目前投票数为0的话换候选人，自己人给自己人投票，敌方减票】
//摩尔投票法为啥成立？因为这里的众数是指大于总数数目的二分之一，举两个个极端例子
//121311【肯定有相邻的，其他的】或者111123【全部联合起来，敌方都抵消不了】
int num = nums[0];//我先来做霸王
int cnt = 1;//目前帮派就我一个人，遍历下去看看还有没有自己人为自己撑腰打气，首先遇到对手就被搞下去了
for(int i = 1; i < nums.length; ++i){
if(nums[i] == num){
cnt++;//帮派的人来撑腰了，票数++
}
else{
cnt--;//敌方来骚扰我当霸王，票数--
if(cnt == 0){//没了，目前帮派人不够地方多，话语权没有
num = nums[i];//更换霸王
cnt = 1;//新的霸王重新计数
}
}
}
//选出来笑到最后的霸王
return num;
}方法2
排序。如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为\(\frac{n}{2}\)的元素一定是众数
public static int majorityElement_2(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}1.6 旋转数组
题目
给定一个整数数组 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位就是从第n-k位往后的n个数字(n为数组长度)。
public static int[] rotate_1(int[] nums, int k) {
int n = nums.length;
k %= n;
// initialize 2*n size int array
int[] arr = new int[n << 1];
System.arraycopy(nums, 0, arr, 0, n);
System.arraycopy(nums, 0, arr, n, n);
System.arraycopy(arr, n - k, nums, 0, n);
return nums;
}方法2
使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)?mod?n 的位置，最后将新数组拷贝至原数组即可。
public static int[] rotate_2(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr, 0, nums, 0, n);
return nums;
}1.7 买卖股票的最佳时机
题目
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例 1：
?输入：[7,1,5,3,6,4]
?输出：5
?解释：在第 2 天(股票价格 = 1)的时候买入，在第 5 天(股票价格 = 6)的时候卖出，最大利润 = 6-1 = 5。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
?输入：prices = [7,6,4,3,1]
?输出：0
?解释：在这种情况下, 没有交易完成, 所以最大利润为 0。