文章目录
题目:最大子数组和
原题链接:最大子数组和
方法1 动态规划
public class T53 {
//动态规划
public static int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length]; // dp[i] 表示以 nums[i] 结尾的最大子数组和
dp[0] = nums[0]; // 初始化状态
int res = dp[0]; // 初始化最大子数组和
// 动态规划状态转移
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); //状态转移方程
res = Math.max(res, dp[i]);
}
return res;
}
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(nums)); // 输出: 6
}
}
方法2
方法二可能不容易想到
public class T53 {
public int maxSubArray(int[] nums) {
// 初始化为int类型最小值
int res = nums[0];
int tempTotal = 0;
for (int i = 0; i < nums.length; i++) {
tempTotal += nums[i];
// 记录最大数值
res = Math.max(tempTotal, res);
if (tempTotal < 0) {
// 如果和小于0,就重置为0,因为任何数加上一个负数一定小于当前数值
tempTotal = 0; //0加任何数都等于任何数
}
}
return res;
}
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(nums)); // 输出: 6
}
}
题目:合并区间
原题链接:合并区间
题解
public static int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
// 可使用Lambda表达式
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] interval1, int[] interval2) {
return interval1[0]-interval2[0];
}
});
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
int L = interval[0], R = interval[1];
// 如果merged列表为空,或者当前区间与上一个区间不重叠,直接添加当前区间
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
// 否则更新上一个区间的右边界
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
//List.toArray(T[] a) 方法将列表中的所有元素存储到指定类型的数组中
return merged.toArray(new int[merged.size()][]);
}
核心:
如果新区间
的起始值大于 merged 列表中最后一个区间的结束值,则直接将新的区间添加到 merged 列表中;否则,更新 merged 列表中最后一个区间的结束值。
- 排序区间: 确保区间按照起始值从小到大排列,方便后续合并操作。
- 遍历和合并: 遍历排序后的区间数组,使用一个 merged 列表来存储合并后的区间。如果当前区间与前一个区间不重叠,直接添加到 merged 列表;如果重叠,更新 merged 列表中最后一个区间的结束值。
题目:轮转数组
原题链接:轮转数组
方法1-使用额外的数组
方法1是自己写出来的。方法2参考的别人的,方法2太👍了,不易发现这个规律
public static void rotate(int[] nums, int k) {
int[] temp = new int[nums.length];
int j = 0;
k = k % nums.length; // 数组长度大于k时,旋转次数取余---关键
for (int i = nums.length - k; i < nums.length; i++) {
temp[j++] = nums[i];
}
for (int i = 0; i < nums.length - k; i++) {
temp[j++] = nums[i];
}
System.arraycopy(temp, 0, nums, 0, nums.length);
}
方法2-三次反转数组
private static void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
public static void rotate1(int[] nums, int k) {
k = k % nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
题目:除自身以外数组的乘积
原题链接:除自身以外数组的乘积
方法1-用到了除法
当时没看题目中不让用除法,当时一下就想到这个思路了,哈哈哈
public static int[] productExceptSelf(int[] nums) {
int temp = 1;
int zero = 0;
// 先看数组中0的个数 大于1则结果数组全为0 等于1则结果数组中0的位置为其他元素乘积
for (int num : nums) {
if (num != 0) {
temp *= num;
} else {
zero++;
if (zero > 1) return new int[nums.length];
}
}
List<Integer> res = new ArrayList<>();
for (int num : nums) {
if (zero == 1) {
//num==0 则当前结果数组该位置的结果为其他元素乘积
res.add(num == 0 ? temp : 0);
} else {
res.add(temp / num);
}
}
return res.stream().mapToInt(Integer::intValue).toArray();
}
方法2-前后缀乘积法
方法2使用两次遍历分别计算数组元素左边
和右边
的乘积,从而构建出结果数组
public static int[] productExceptSelf1(int[] nums) {
int n = nums.length;
int[] res = new int[n];
// 第一次遍历,计算左边所有元素的乘积
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
// 第二次遍历,计算右边所有元素的乘积,并更新结果数组
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right; //res[i]是当前i左边元素全部乘积
right *= nums[i]; //用一个变量记录当前元素右边的所有元素乘积
}
return res;
}
❤觉得有用的可以留个关注~~❤