面试经典 150 题——数组/字符串（一）

1、合并两个有序数组

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

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

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

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

提示：

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

1.3 解题代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; 
        int j = n - 1;
        int index = m + n - 1;
        while(i >= 0 && j >= 0){
            if(nums1[i] > nums2[j]){
                nums1[index] = nums1[i];
                --i;
            } else{
                nums1[index] = nums2[j];
                --j;
            }
            --index;
        }
        while(j >= 0){
            nums1[index] = nums2[j];
            --index;
            --j;
        }
    }
}

1.4 解题思路

1. 使用双指针来解决该问题。
2. 因为是原地修改，nums1数组后面为空，又因为nums1数组和nums2数组都是按照非递减排序的，所以可以通过逆序遍历的方式获取每个数组中的当前最大的元素。
3. 添加数组时，从nums1的m+n-1位置开始添加，每次都比较nums1和nums2中的最大元素即可。
4. 如果nums1没遍历完就保持原状即可，如果nums2没遍历完，还需要将nums2中的剩余元素放在nums1中。

2、移除元素

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

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

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

提示：

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

2.3 解题代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        int j = 0;
        int n = nums.length;
        int ret = 0;
        while(j < n){
            if(nums[j] != val){
                nums[i] = nums[j];
                ++i;
                ++ret;
            }
            ++j;
        }
    return ret;
    }
}

2.4 解题思路

1. 使用双指针来解决问题
2. 一个指针用来遍历数组，判断当前数组是否等于val，如果不等于则需要存放进nums数组中。另一个指针作为存放下标，来存放需要存放的元素。
3. 最后返回存放的数字量即可。

3、删除有序数组中的重复项

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

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

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

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

提示：

• 1 <= nums.length <= 3 * 10⁴
• -10⁴ <= nums[i] <= 10⁴
• nums 已按 非严格递增 排列

3.3 解题代码

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int idx = 0;
        int i = 0;
        int j = 0;
        while(i < n){
            if(i == n - 1){
                nums[idx] = nums[i];
                ++i;
                ++idx;
            } else{
                j = i + 1;
                while(j < n && nums[j] == nums[i]){
                    ++j;
                }
                nums[idx] = nums[j - 1];
                idx++;
                i = j;
            }
        }
    return idx;
    }
}

3.4 解题思路

1. 使用双指针来解决问题
2. 用idx从0开始更新数组，一个指针用来遍历数组，另一个指针负责来遍历该指针所在的位置，记录当前的数为num，右边所有相同的数，直到遍历到不等于num，将num放在idx的位置，然后更新idx和左端指针。
3. 最后根据idx返回nums 中唯一元素的个数。

4、删除有序数组中的重复项 II

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

4.3 解题代码

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int idx = 0;
        int i = 0;
        int j = 0;
        while(i < n){
            if(i == n - 1){
                nums[idx] = nums[i];
                ++i;
                ++idx;
            } else{
                j = i + 1;
                int num = 0;
                while(j < n && nums[j] == nums[i]){
                    num++;
                    ++j;
                }
                if(num >= 1){
                    nums[idx] = nums[j - 1];
                    idx++;
                    nums[idx] = nums[j - 1];
                    idx++;
                } else{
                    nums[idx] = nums[j - 1];
                    idx++;
                }        
                i = j;
            }
        }
    return idx;
    }
}

4.4 解题思路

1. 与题目3思路一样，只是需要增加判断，相同的数是否大于等于2个，大于等于2个则需要往数组里面添加2次。

5、多数元素

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

提示：

• n == nums.length
• 1 <= n <= 5 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

5.3 解题代码

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

5.4 解题思路

1. 先对原来的数组进行排序。
2. 输出数组的中位数即为次数 大于 ⌊ n/2 ⌋ 的元素。

6、轮转数组

6.1 题目链接

点击跳转到题目位置

6.2 题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

提示：

• 1 <= nums.length <= 105
• -2³¹ <= nums[i] <= 2³¹ - 1
• 0 <= k <= 105

6.3 解题代码

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] ret = new int[n];
        for(int i = 0; i < n; ++i){
            ret[(i + k) % n] = nums[i]; 
        }
        for(int i = 0; i < n; ++i){
            nums[i] = ret[i];
        }
    }
}

6.4 解题思路

1. 使用额外数组，然后找到变换后数组的坐标j和原数组中坐标i的关系，即j = （i + k）% n。
2. 最后将额外数组的值赋值给原数组即可。

7、买卖股票的最佳时机

7.1 题目链接

点击跳转到题目位置

7.2 题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

7.3 解题代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int max_price = 0;
        for(int i = 1; i < n; ++i){
            int now_price = prices[i];
            prices[i] = Math.min(prices[i - 1], prices[i]);
            max_price = Math.max(max_price, now_price - prices[i]);   
        }       
    return max_price;
    }
}

7.4 解题思路

1. 一次遍历数组，从下标为1开始遍历，每次先储存当前price为now_price。
2. 接着prices[i]用来存储0~i范围内最低价格的股票，获取一个最大的盈利为now_price - prices[i]。
3. 最后返回比较的结果（如果不存在盈利就返回一开始初始化的max_price = 0）。

8、买卖股票的最佳时机 II

8.1 题目链接

点击跳转到题目位置

8.2 题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

8.3 解题代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int sum = 0;
        int min_price = prices[0];
        for(int i = 1; i < n; ++i){
            if(min_price < prices[i]){
                sum += (prices[i] - min_price);
                min_price = prices[i];
            } else{
                min_price = Math.min(prices[i], min_price);
            }
        }
    return sum;
    }
}

8.4 解题思路

1. 使用贪心算法的思想来解决。
2. 如果当天的价格比之前最低价格要高就卖出，否则就更新最低价格即可。（如果卖出就更新为当天价格）