微官网和微网站首页,推广一个app的费用,泰坦科技网站建设,微信的网站开发数组部分
1. 合并两个有序的子数组 —— 倒序双指针避免覆盖
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中#xff0c;使…数组部分
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. 从左往右遍历数组nums2. 如果与val相同则与数组最后一个元素交换3. 数组长度 -- 4. 注如果相同了则继续遍历当前元素因为当前元素是末尾交换过来的元素不一定不等于val5. 结束的条件当前判断的位置与更改后的数组位置相同*/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 i1; 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; // 初始投票为0vote表示众数的票每次为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(vectorint prices) {/*// 即求当前元素与后面元素的最大差值法一 暴力查找 O(n^2)法二贪心思想取左边的最小值取右边最大值 O(n) O(1)法二动态规划假设 dp[i] 表示第i天可获得的最大利润如果第i天卖出了股票 dp[i]如果第i天不卖出股票又怎么样*/return method4(prices);}private: int method2(vectorint 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 i0; i n; i) { // 遍历数组low min(prices[i],low); // 左边的最小ans max(ans, prices[i] - low); // 取最大区间的利润}return ans;}int method3(vectorint 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 的一维整数向量// 这个一维向量会作为外层向量的每个元素的初始值。vectorvectorint dp(n, vectorint(2));dp[0][0] -prices[0];dp[0][1] 0;for(int i1; 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(vectorint prices) {int n prices.size();vectorvectorint dp(2, vectorint(2));dp[0][0] -prices[0];dp[0][1] 0;for(int i1; 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 i1; 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 i0; 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 i0; 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;HashMapInteger, Integer map;ListInteger 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中删除的元素从而达到一个O1的删除效果 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[i1] * nums[i1]初始值 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[i1] * nums[i1];}// 3. 将前缀乘积 与 后缀乘积 相乘从而得到每个元素的结果int[] ans new int[n];for(int i0 ; in; 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 in-2; i 0; i--) {suf[i] suf[i1] * nums[i1]; // 计算后缀}int pre 1;for(int i 0; i n; i) { // 计算前缀但不存储而是直接与suf进行运算suf[i] * pre;pre pre * nums[i]; // 更新pre 用pre代表每一层的前缀乘积}return suf;}
} 注本文中的许多思路是参考leetcode题解以及代码随想录的在这里只是记录自己的刷题过程以及用自己的方式表达出思路。
