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

文章目录

1、合并两个有序数组
- 1.1 题目链接
- 1.2 题目描述
- 1.3 解题代码
- 1.4 解题思路
2、移除元素
- 2.1 题目链接
- 2.2 题目描述
- 2.3 解题代码
- 2.4 解题思路
3、删除有序数组中的重复项
- 3.1 题目链接
- 3.2 题目描述
- 3.3 解题代码
- 3.4 解题思路
4、删除有序数组中的重复项 II
- 4.1 题目链接
- 4.2 题目描述
- 4.3 解题代码
- 4.4 解题思路
5、多数元素
- 5.1 题目链接
- 5.2 题目描述
- 5.3 解题代码
- 5.4 解题思路
6、轮转数组
- 6.1 题目链接
- 6.2 题目描述
- 6.3 解题代码
- 6.4 解题思路
7、买卖股票的最佳时机
- 7.1 题目链接
- 7.2 题目描述
- 7.3 解题代码
- 7.4 解题思路
8、买卖股票的最佳时机 II
- 8.1 题目链接
- 8.2 题目描述
- 8.3 解题代码
- 8.4 解题思路

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 解题思路

使用双指针来解决该问题。
因为是原地修改，nums1数组后面为空，又因为nums1数组和nums2数组都是按照非递减排序的，所以可以通过逆序遍历的方式获取每个数组中的当前最大的元素。
添加数组时，从nums1的m+n-1位置开始添加，每次都比较nums1和nums2中的最大元素即可。
如果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 解题思路

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

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 解题思路

使用双指针来解决问题
用idx从0开始更新数组，一个指针用来遍历数组，另一个指针负责来遍历该指针所在的位置，记录当前的数为num，右边所有相同的数，直到遍历到不等于num，将num放在idx的位置，然后更新idx和左端指针。
最后根据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 解题思路

与题目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 解题思路

先对原来的数组进行排序。
输出数组的中位数即为次数大于 ⌊ 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 解题思路

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

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开始遍历，每次先储存当前price为now_price。
接着prices[i]用来存储0~i范围内最低价格的股票，获取一个最大的盈利为now_price - prices[i]。
最后返回比较的结果（如果不存在盈利就返回一开始初始化的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;
    }
}