稳定的常州网站推广,广州网页设计网站,帮忙做任务网站,傻瓜网站开发软件普通数组 1. 最大子数组和#xff08;Maximum Subarray#xff09;解题思路动态规划的优化解法#xff08;Kadane 算法#xff09;核心思想 代码解析 2. 合并区间#xff08;Merge Intervals#xff09;解题思路代码实现 3. 旋转数组#xff08;Rotate Array#xff09… 普通数组 1. 最大子数组和Maximum Subarray解题思路动态规划的优化解法Kadane 算法核心思想 代码解析 2. 合并区间Merge Intervals解题思路代码实现 3. 旋转数组Rotate Array解题思路代码实现 4. 除自身以外数组的乘积Product of Array Except Self解题思路代码实现 5. 缺失的第一个正整数First Missing Positive解题思路代码实现 1. 最大子数组和Maximum Subarray
给定一个整数数组 nums你需要找到一个具有最大和的连续子数组并返回其和。
解题思路
这个问题使用 动态规划 或者 贪心算法 来解决。解题的关键在于如何选择包含当前元素的最大和子数组。
动态规划的优化解法Kadane 算法 动态规划状态定义 sum: 当前子数组的和即以当前元素结尾的最大和子数组的和。如果当前和 sum 是正的则可以继续累加到后面的元素否则从当前元素重新开始。ans: 存储迄今为止遇到的最大子数组和。 过程 从左到右遍历数组依次计算每个位置 i 的最大和子数组。如果当前 sum 是负数则不继续累加重新从当前元素开始。每次计算完 sum 后更新全局最大值 ans。
核心思想
当前的子数组和与前一个子数组和的关系如果前一个子数组和 sum 为正则将其累加到当前元素中否则重新从当前元素开始计算新的子数组。这样可以保证每次计算出的子数组和是局部最大和从而得到全局最大和。
代码解析
class Solution {public int maxSubArray(int[] nums) {int sum 0; // 用来表示前缀和int ans nums[0]; // 初始化答案为数组的第一个元素// 遍历数组for (int i 0; i nums.length; i) {// 如果 sum 0 就说明 sum 对后续子数组有贡献sum sum 0 ? sum nums[i] : nums[i]; // 继续累加或者从当前元素重新开始// 更新最大子数组和ans Math.max(sum, ans); // 比较当前的 sum 和之前的最大和更新结果}return ans; // 返回最终的最大子数组和}
}2. 合并区间Merge Intervals
给定一个由区间组成的二维数组 intervals合并所有重叠的区间并返回一个不重叠的区间数组。
解题思路
排序首先根据区间的起始端点对数组进行排序。这样区间之间的关系就可以通过顺序来判断。合并从排好序的区间开始逐个判断是否可以合并 如果当前区间与结果集的最后一个区间重叠即当前区间的起始点小于等于结果集最后一个区间的终点则合并它们将合并后的区间的终点更新为两个区间终点的最大值。如果当前区间与结果集最后一个区间不重叠直接将当前区间加入结果集。
代码实现
class Solution {public int[][] merge(int[][] intervals) {// 先对二维数组的每一项的左端点进行排序Arrays.sort(intervals, (p, q) - p[0] - q[0]);// 使用List是因为不知道最终的结果里面会有几个元素Listint[] ans new ArrayList();// 遍历每个区间for (int[] p : intervals) {int m ans.size();// 判断是否能合并合并时更新右端点为两个区间的最大值if (m 0 ans.get(m-1)[1] p[0]) {ans.get(m-1)[1] Math.max(ans.get(m-1)[1], p[1]);} else {// 不能合并时直接将当前区间加入结果集ans.add(p);}}// 将 List 转成二维数组返回return ans.toArray(new int[ans.size()][]);}
}3. 旋转数组Rotate Array
给定一个数组将数组中的元素向右旋转 k 步要求使用 O(1) 的空间复杂度。
解题思路 翻转法本题的核心思路是通过数组的翻转来解决 首先对整个数组进行一次翻转这样数组中需要旋转的部分会被反转到数组的前面。然后将这两个部分分别翻转回去得到最终的结果。 步骤 步骤 1对整个数组进行一次翻转。步骤 2对数组的前 k 个元素进行翻转。步骤 3对数组的剩余部分从 k 到数组的末尾进行翻转。
代码实现
class Solution {public void rotate(int[] nums, int k) {/*** 首先对整个数组实行翻转这样原数组中需要翻转的子数组就会跑到数组最前面。* 这时候从 k 处分隔数组左右两数组各自进行翻转即可。*/k k % nums.length; // 处理 k 大于数组长度的情况reverse(nums, 0, nums.length - 1); // 翻转整个数组reverse(nums, 0, k - 1); // 翻转前 k 个元素reverse(nums, k, nums.length - 1); // 翻转剩余的部分}// 辅助翻转函数public void reverse(int[] nums, int start, int end) {while (start end) {// 交换 nums[start] 和 nums[end]int temp nums[start];nums[start] nums[end];nums[end] temp;start;end--;}}
}4. 除自身以外数组的乘积Product of Array Except Self
给定一个整数数组 nums返回一个数组 answer其中 answer[i] 等于 nums 中除 nums[i] 以外的所有元素的乘积。
要求 不使用除法并且在 O(n) 时间复杂度内完成算法。
解题思路 两次遍历法 第一次遍历计算每个元素左侧所有元素的乘积保存在 ans 数组中。第二次遍历从右侧遍历数组同时计算每个元素右侧所有元素的乘积并与 ans 数组中的值相乘得到最终结果。 步骤 步骤 1初始化一个 ans 数组ans[i] 用来存储从左到 i-1 位置的乘积。步骤 2从左到右遍历数组更新 ans 数组。步骤 3初始化一个变量 R用于存储当前元素右边所有元素的乘积。然后从右到左遍历数组将右边的乘积与 ans 数组中的值相乘。
代码实现
class Solution {public int[] productExceptSelf(int[] nums) {int ans[] new int[nums.length];// 用 ans 数组来存储左边的积ans[0] 1;for (int i 1; i nums.length; i) {ans[i] ans[i - 1] * nums[i - 1]; // 左侧所有元素的乘积}int R 1;for (int i nums.length - 1; i 0; i--) {ans[i] ans[i] * R; // 左侧积与右侧积的乘积R R * nums[i]; // 更新右侧积}return ans;}
}5. 缺失的第一个正整数First Missing Positive
给定一个未排序的整数数组 nums请你找出其中缺失的第一个正整数。
要求
你必须实现时间复杂度为 O(n) 的解法。你只能使用常数级别的额外空间。
解题思路
这个问题的关键在于通过对数组进行原地交换排序使得每个正整数 x 被放置在索引 x-1 上。通过这种方式我们可以在一次遍历后找到第一个不符合条件的索引返回该索引加一即为缺失的第一个正整数。 原地排序 遍历数组对每个符合条件的正整数 nums[i]将其放置到对应的位置 nums[nums[i] - 1]。只有当 nums[i] 在有效范围内且与目标位置的元素不相等时才进行交换。 查找缺失的第一个正整数 遍历数组查找第一个索引 i使得 nums[i] ! i 1。这个索引加一即为缺失的第一个正整数。 若数组中没有缺失的正整数 如果数组中的所有位置都符合 nums[i] i 1说明所有从 1 到 n 的正整数都存在则缺失的第一个正整数为 n 1。
代码实现
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;for (int i 0; i n; i) {// 只处理有效范围内的正整数while (nums[i] 1 nums[i] n nums[nums[i] - 1] ! nums[i]) {// 交换元素到正确位置nums swap(nums, i, nums[i] - 1);}}// 查找第一个不符合条件的位置for (int i 0; i n; i) {if (nums[i] ! i 1) {return i 1; // 返回缺失的第一个正整数}}return n 1; // 如果数组中没有缺失的正整数返回 n 1}// 交换数组中的两个元素public int[] swap(int[] nums, int index1, int index2) {int temp nums[index1];nums[index1] nums[index2];nums[index2] temp;return nums;}
}
