面试经典150题刷题记录
数组部分
1. 合并两个有序的子数组 —— 倒序双指针避免覆盖
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
参考题解：. - 力扣（LeetCode）
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {/* 倒序双指针法：从尾部开始，从而避免覆盖问题 m,n 分别表示 nums1 和 nums2 的元素个数*/ int p1 = m - 1; // 指向第一个数组的最后一个元素int p2 = n - 1; // 指向第二个元素数组的最后一个元素int insert_position = m + n - 1; // 指向要插入的位置while (p2 >= 0) { // nums2 还有要合并的元素// 如果 p1 < 0，那么走 else 分支，把 nums2 合并到 nums1 中if (p1 >= 0 && nums1[p1] > nums2[p2]) {nums1[insert_position--] = nums1[p1--]; // 填入 nums1[p1]} else {nums1[insert_position--] = nums2[p2--]; // 填入 nums2[p1]}}}
}2. 移除元素 —— 数组末尾元素交换法
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
class Solution {public int removeElement(int[] nums, int val) {/**idea & steps:1. 从左往右遍历数组nums，，2. 如果与val相同，则与数组最后一个元素交换，3. 数组长度 -- 4. 注：如果相同了则继续遍历当前元素；（因为当前元素是末尾交换过来的元素，不一定不等于val）5. 结束的条件：当前判断的位置与更改后的数组位置相同*/int cur = 0; // 起始指针int rear = nums.length - 1; // 终止指针while(cur <= rear) {if(nums[cur] == val) {nums[cur] = nums[rear];rear --;}else {cur ++;}}return cur;}
}3. 删除有序数组中的重复项
26. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
class Solution {public int removeDuplicates(int[] nums) {/**idea & steps1. 利用递增的特性，那么相同元素一定是在挨在一起的2. 原地删除如果后面的元素与前面的元素相同，则为重复项，不保留如果后面的元素与前面的元素不相同，则为重复项，不保留用指针 k 指向保留的元素要填入的下标// 最后的前k个元素包含唯一元素*/ int k = 1; // 记录存放元素的位置for(int i=1; i < nums.length; i++) {if(nums[i] != nums[i-1]) {nums[k++] = nums[i];}}return k;}
}4. 删除有序数组中的重复项 Ⅱ - 比较前k位
80. 删除有序数组中的重复项 II
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
class Solution {public int removeDuplicates(int[] nums) {/**目标：使得出现超过两次的元素只出现两次，返回删除后数组的新长度注：出现1次的元素，仍然进行保留===> 推广到一般情况：将保留2位 修改为 保留k位idea & steps: 1. 前k个元素直接保存2. 后面的元素进行遍历，将其与前k个元素比较，因为是有序的，故只需要与 nums[u-k]进行比较即可只有不同才会进行保留；// 保留k位只用把代码中的2修改为k即可，或者封装为一个函数，传入参数k*/int insert_pos = 0; // 记录当前插入的位置for(int num : nums) {// 注意这里是 insert_pos - 2 而不是 i-2; insert_pos表示当前元素要插入的位置// 即可以理解为要插入的元素// 如果要插入的元素 与 该位置前面两个元素都相同，则不能插入，继续遍历下一个元素if(insert_pos < 2 || nums[insert_pos - 2] != num){nums[insert_pos ++] = num;} // 前两个元素直接保留// printArray(nums);}return insert_pos;}// public void printArray(int[] nums) {// for(int num : nums) // System.out.print(num + " ");// System.out.println();// }
}5. 多数元素-摩尔投票法【正负抵消】
参考题解：. - 力扣（LeetCode）
169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution {public int majorityElement(int[] nums) {/**返回大于 n/2 的元素比如 n = 8 , 则返回大于等于5个元素的比如 n = 7, 则返回大于等于4个元素的尝试设计实践复杂度为 O(n); 不可以进行排序了，因为快排的时间复杂度为 O(nlogn)遍历一遍进行解决 */// 摩尔投票法：核心理念为票数正负抵消。此方法时间与空间复杂度分别为 O(N) 和 O(1)// 众数 与 非众数 进行一对一抵消，剩下的就是众数了int x = 0; // 众数int votes = 0; // 初始投票为0，vote表示众数的票；每次为vote为0时，则重新选择一个众数，因为之前的众数已经被抵消完了for(var num : nums) {// if(votes == 0) {// x = num; // 当前num为新的众数// votes ++;// }else{// if(num == x) {// votes ++;// }else {// votes --;// }// }if(votes == 0) x = num;votes += num == x ? 1 : -1;}// 验证环节// 验证 x 是否为众数// for (int num : nums)// if (num == x) count++;// return count > nums.length / 2 ? x : 0; // 当无众数时返回 0return x;}
}6. 轮转数组 —— 反转三次
189. 轮转数组
给定一个整数数组 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]
7. 买卖股票的最佳规划 —— 贪心/动态规划
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
dp[i][0] 表示 第i天持有该股票的最大现金
dp[i][1] 表示第i天不持有该股票的最大现金
class Solution {
public:int maxProfit(vector<int>& prices) {/*// 即求当前元素与后面元素的最大差值法一： 暴力查找 O(n^2)法二：贪心思想：取左边的最小值，取右边最大值 O(n) O(1)法二：动态规划：假设 dp[i] 表示第i天可获得的最大利润如果第i天卖出了股票 dp[i]如果第i天不卖出股票又怎么样*/return method4(prices);}private: int method2(vector<int>& prices) {// 法二： 贪心思想// 比如 7 1 5 3 6 4// 最小值为1，取到之后拿右边的值减它，记录减结果之后的最大利润// 7 100 1 20 // 先取的是7 然后记录了最值 93，到1之后在记录最大值也只有19，相当于每个元素都取了最小的情况int low = INT_MAX; // 记录左边的最小镇int ans = 0; // 记录最后结果int n = prices.size();for(int i=0; i < n; i++) { // 遍历数组low = min(prices[i],low); // 左边的最小ans = max(ans, prices[i] - low); // 取最大区间的利润}return ans;}int method3(vector<int>& prices) {/* 法三：动态规划 1. dp数组的含义dp[i][0] 表示第i天持有股票所得最多现金；dp[i][1] 表示第i天不持有股票所得最多现金；注意持有的意思并不是说在这一天买入，也可以在之前买入，只不过一直没有卖出2. dp公式第i天持有股票所得最多现金，应该等于第i-1天持有股票的最大利润 或者 是今天买入时的现金最大值dp[i][0] = max(dp[i-1][0] , -prices[i]);第i天未持有股票所得最多现金，应该等于第i-1天未持有股票所得最多现金 或者 是今天卖出时的现金最大值而今天卖出现金就应该是第i-1天持有的最大值 + prices[i] （今天卖出说明前一天是持有的）dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])3. 初始化dp[0][0] : 此时持有股票就是一定买入了; dp[0][0] = -prices[0]dp[0][1] : 第一天不持有就是不买 dp[0][1] = 0;4. 遍历顺序从左到右，从前到后*/int n = prices.size();// 第一个参数为外层vector的大小，第二个参数它创建了一个大小为 2 的一维整数向量// ，这个一维向量会作为外层向量的每个元素的初始值。vector<vector<int>> dp(n, vector<int>(2));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i=1; i< n ; i++) {dp[i][0] = max(dp[i-1][0] , -prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);}return dp[n-1][1]; // 一直要考虑到最后一天，故最大值为到最后一天的不持有股票的结果}// 法3改进：节省空间int method4(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(2, vector<int>(2));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i=1; i< n ; i++) {dp[i%2][0] = max(dp[(i-1)%2][0] , -prices[i]);dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-1)%2][0] + prices[i]);}return dp[(n - 1) % 2][1]; // 一直要考虑到最后一天，故最大值为到最后一天的不持有股票的结果}
};8. 买卖股票的最佳时机 Ⅱ
122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
分析：
与第7题唯一不同的就是在dp[i][0]的处理上，因为第7题中只能买一次股票，所以持有股票时的现金一定是 -prices[i]; 但是在本题中可以买卖多次股票，即在买当前股票时可能之前就有了股票的消费，故如果在第i天买入，那dp[i][0] 就应该等于 dp[i-1][1] - prices[i] ; （前一天不持有股票的现金减去今天买股票的钱）
class Solution {public int maxProfit(int[] prices) {/**动态规划思想：1. dp含义：dp[i][0] 表示第i天持有该股票的现金dp[i][1] 表示第i天不持有股票的现金2. 状态方程dp[i][0] 有两种情况：case1: 第i-1天就持有 dp[i-1][0]case2: 在第i天买入 dp[i-1][1] - prices[i]dp[i][1] 两种情况：case1 : 第i天没有卖出,故为前面不持有 dp[i-1][1]case2: 第i天卖出，故为前一天持有的钱 + prices[i] 即 dp[i-1][0]+prices[i]3. 初始值dp[0][0] = -prices[0];dp[0][1] = 0;4. 遍历顺序：从前到后*/int len = prices.length;int[][] dp = new int[len][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i=1; i < len; i++) {dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);}return dp[len-1][1];}
}9. 跳跃游戏 —— 贪心（注意代码的写法）
55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
class Solution {public boolean canJump(int[] nums) {int cover = 0;// 只在可跳的范围内进行变化// 初始时下标为0for(int i=0; i <= cover; i++) {cover = Math.max(i + nums[i], cover); // 更新覆盖范围if(cover >= nums.length - 1) return true; // 可以跳出去}return false;}
}10. 跳跃游戏Ⅱ——（明确什么时候要跳下一步，以及怎样跳步数最少）
45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
class Solution {public int jump(int[] nums) {/**本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？，以及怎么走呢只有在当前的最大覆盖范围不能覆盖到终点时需要步数加1而下一步的覆盖范围要是最大的，才可以得到最少的跳跃次数；不用关注具体的跳跃方法，因为求的只是一个次数问题所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。*/// 比如：2 3 1 1 4 开始可至2的位置，然后一直走2之后，找到这个范围内最大下标可至结果，故而返回2次int curDistance = 0; // 记录当前最远下标 // 并不是每次都要更新这个，只要在达不到时才更新int nextDistance = 0; // 记录下一步覆盖最远距离下标int ans = 0; int len = nums.length;if(len == 1) return 0;for(int i=0; i < len; i++) {nextDistance = Math.max(nextDistance, nums[i] + i); // 更新下一步覆盖最远距离下标if(i == curDistance) { // 这样才算正真找到了下一次的最远下标，故更新ans ++; // 走下一步curDistance = nextDistance; // 继续往下走if(curDistance >= len - 1) return ans;}}return ans;}
}11. H指数
12. O(1) 时间插入、删除和获取随机元素 —— 数据结构的运用；list如何同时实现O(1)复杂度的删除与访问（尾元素替代法）
380. O(1) 时间插入、删除和获取随机元素
实现RandomizedSet 类：
RandomizedSet()初始化RandomizedSet对象bool insert(int val)当元素val不存在时，向集合中插入该项，并返回true；否则，返回false。bool remove(int val)当元素val存在时，从集合中移除该项，并返回true；否则，返回false。int getRandom()随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
// O(1)的时间复杂度，所以选择使用哈希表来实现操作
// 而随机数的生成则可以随机生成一个下标，可以使用list同时来存储每个元素，这样在生成随机数时可以利用list的随机存取功能
// Map(val, index) 第一个元素为具体值，第二个元素为其对应下标（在list中）
class RandomizedSet {Random random;HashMap<Integer, Integer> map;List<Integer> list;int size;public RandomizedSet() { random = new Random();map = new HashMap<>();list = new ArrayList<>();size = 0;}public boolean insert(int val) { if(map.containsKey(val)){ // 哈希表中含有这个键return false;}map.put(val, size++); // value为其下标list.add(val);return true;}// 在list中删除指定元素索引的操作，为了实现O(1)复杂度，所以选择用最后一个元素来代替要删除的元素// 然后改为删除最后一个元素即可；类似堆的删除public boolean remove(int val) {if(!map.containsKey(val)){return false;}int index = map.get(val); // 得到这个值的索引int last = list.get(size - 1); // list.set(index, last); // 用最后一个元素来填充list中删除的元素，从而达到一个O（1）的删除效果 map.put(last, index); // 更新mapmap.remove(val); list.remove(--size);return true;}public int getRandom() { // 利用list进行随机数的生成int index = random.nextInt(list.size());return list.get(index);}
}13. 除自身以外数组的乘积 —— 前后缀分解法
前后缀分解法题单：. - 力扣（LeetCode）
238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
本题的难点在于不可以使用除法： 且需要在O(1) 的额外空间复杂度内完成这个题目
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
参考题解：. - 力扣（LeetCode）
. - 力扣（LeetCode）
class Solution { public int[] productExceptSelf(int[] nums) {// 方式一：未优化，O(n) O(n)// return methods1(nums);// 方式二：O(n) O(1)return methodsOptimize(nums);}private int[] methods1(int[] nums) {/**1. 如果使用除法就是把所有元素乘起来，然后除以每个位置的元素即可。前后缀的思想：把当前nums[i]的左右两个部分分为前缀pre[i] 与 后缀suf[i]最后的结果即 pre[i] * suf[i] 如果算出了 nums[0] ~ nums[i-2] 的乘积 pre[i-1] 再乘上 nums[i-1] 即可得到 pre[i]即 pre[i] = pre[i-1] * nums[i-1];同理有 suf[i] = suf[i+1] * nums[i+1]初始值 pre[0] = suf[n - 1] = 1;算出 answer = pre[i] * suf[i]*/// 1. 求出每个元素的前缀乘积 （类似前缀和的求和，从前往后相乘）int n = nums.length;int[] pre = new int[n];pre[0] = 1; // 初始化; for(int i = 1; i < n; i++) {pre[i] = pre[i-1] * nums[i-1]; // eg: pre[1] = pre[0] * nums[0]; // pre[0] 是一个初值1，表示未开始乘}// 2. 求出每个元素的后缀;int[] suf = new int[n];suf[n - 1] = 1; for(int i = n-2; i >=0 ;i--) {suf[i] = suf[i+1] * nums[i+1];}// 3. 将前缀乘积 与 后缀乘积 相乘从而得到每个元素的结果int[] ans = new int[n];for(int i=0 ; i<n; i++) {ans[i] = pre[i] * suf[i];}return ans;}private int[] methodsOptimize(int[] nums) {/**优化：先计算suf, 然后一边计算 pre, 一边把 pre直接乘到 suf[i] 中最后得到的 suf后缀乘积 即为 ans*/int n = nums.length;int[] suf = new int[n];suf[n - 1] = 1; for(int i=n-2; i >= 0; i--) {suf[i] = suf[i+1] * nums[i+1]; // 计算后缀}int pre = 1;for(int i = 0; i < n; i++) { // 计算前缀，但不存储，而是直接与suf进行运算suf[i] *= pre;pre = pre * nums[i]; // 更新pre 用pre代表每一层的前缀乘积}return suf;}
}