普通数组
53. 最大子数组和
方法一:暴力解
依次遍历数组中的每个子数组,进而判断res
的最大值
超时
class Solution {
public int maxSubArray(int[] nums) {
int res = 0;
for(int i=0; i<nums.length; i++) {
int sum = 0;
for(int j=i; j<nums.length; j++) {
sum += nums[j];
res = Math.max(res, sum);
}
}
return res;
}
}
方法二:贪心算法
贪心算法,保证累加后的结果始终对当前结果存在增益效果即可
sum
用于记录前几项的元素和,动态更新;res用于记录最大的元素和,动态更新- 求解的关键在于
sum
值的更新,假设不考虑nums[i]
的值,此处仅关注nums[i-1]
:- 如果
nums[i-1]>0
,那么对nums[i]
均有增益作用 - 如果
nums[i-1]<0
,无论nums[i]
为正还是负,对nums[i]
均无增益作用;例如nums[i-1]=-1,nums[i]=-3
,此时,重新累加的值为-3
,而叠加后的值却为-4
- 如果
- 那么何时应该累加
sum
?将上述思路扩展至前几项的和sum
:如果sum
值小于0,则sum
再加上nums[i]
值会更小,无有增益作用。因此此时sum应从0开始计算。 - 初始化,
res = Integer.MIN_VALUE
,sum = 0
表示从0
开始累加
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
int sum = 0;
for(int i=0; i<nums.length; i++) {
// 如果 sum<0, 说明前几项无增益作用,重新累计sum
if(sum<0) {
sum = 0;
}
sum += nums[i];
res = Math.max(res, sum);
}
return res;
}
}
方法三:动态规划
与上述贪心算法的实现思路似乎比较类似,动态规划问题设计了一个状态转移方程,而贪心算法则侧重于取当前最优方案
- 状态转移方程:
dp[i] = max(dp[i-1]+nums[i], nums[i])
,如果加上nums[i]
的元素后的值还小于nums[i]
,则舍弃之前的元素 - 优化上述方程,更新时只需要
dp[i-1]
和dp[i]
,因此可采用变量sum
进行更新 - 初始化,
res = Integer.MIN_VALUE
,sum = 0
表示从0
开始累加
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
int sum = 0;
for(int i=0; i<nums.length; i++) {
sum = Math.max(sum+nums[i], nums[i]);
res = Math.max(res, sum);
}
return res;
}
}
56. 合并区间
先将给定数组按照左边界进行排序,之后依次比较右边界的值,即可确定合并区间。
变量定义:ArrayList<int[]> res
存储结果
左边界leftBound
,右边界rightBound
注意表达含义:
Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));
res.add(new int[]{leftBound, rightBound});
这句表述,以leftBound
和rightBound
为值,构建了一个int[]
,并将int[]
存入ArrayList<int[]>
中res.toArray(new int[res.size()][]);
List的toArray()方法_list.toarray-CSDN博客
class Solution {
public int[][] merge(int[][] intervals) {
// 将数组Intervals按照左边界排序,调用compare方法
Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));
ArrayList<int[]> res = new ArrayList<>();
int leftBound = intervals[0][0];
int rightBound = intervals[0][1];
for(int i=1; i<intervals.length; i++) {
if(intervals[i][0] > rightBound) {
// 边界不重叠,将结果存入res中,并且同时更新左右边界
res.add(new int[]{leftBound, rightBound});
leftBound = intervals[i][0];
rightBound = intervals[i][1];
} else {
// 边界重叠,更新右边界,大中取大
rightBound = Math.max(rightBound, intervals[i][1]);
}
}
// 上述循环最后一次更新右边界,结果未写入res中,将此次结果插入
res.add(new int[]{leftBound, rightBound});
return res.toArray(new int[res.size()][]);
}
}
189. 轮转数组
方法一:模拟
-
向后移动
k
位,可利用取余操作(i+k)%len
,计算更新后的元素位置 -
数组复制相关知识:深入解析Java中的数组复制:System.arraycopy、Arrays.copyOf和Arrays.copyOfRange - 知乎 (zhihu.com)
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length;
// 复制数组int[] nums,到int[] temp
int[] temp = Arrays.copyOf(nums, len);
int count = 0;
for(int i=0; i<len; i++) {
// 使用取余运算,判断nums中的值
nums[(i+k) % len] = temp[i];
}
}
}
方法二:反转数组
将数组进行三次反转即可,例如:nums = [1,2,3,4,5,6,7], k=3
- 第一次反转,从0到nums.length-1:
nums = [7,6,5,4,3,2,1]
- 第二次反转,从0到k-1:
nums = [5,6,7,4,3,2,1]
- 第三次反转,从k到nums.length:
nums = [5,6,7,1,2,3,4]
class Solution {
public void rotate(int[] nums, int k) {
// 注意此处应该取余,处理nums=[1,2], k=3的情况
k %= nums.length;
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k-1);
reverse(nums, k, nums.length-1);
}
private void reverse(int[] nums, int left, int right) {
while(left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}
方法三:环状替代
【待补充】
238. 除自身以外数组的乘积
方法一:前缀积 + 后缀积
为了避免重复计算,可将nums[i]
的前缀积和后缀积均计算出来,则数组中除nums[i]
的乘积则为前缀积 * 后缀积
;计算时应注意边界条件
初始化:前缀积leftMul[0] = 1
,从左向右计算;后缀积rightMul[nums.length - 1] = 1
从右向左计算
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
int[] leftMul = new int[nums.length];
int[] rightMul = new int[nums.length];
leftMul[0] = 1;
rightMul[nums.length - 1] = 1;
// 计算时,最后一个元素不用计算,假如取到最后一个元素,其乘积不用计算自己
for(int i=0; i<nums.length-1; i++) {
leftMul[i+1] = leftMul[i] * nums[i];
// System.out.print(leftMul[i] + ",");
}
for(int i=nums.length-1; i>0; i--) {
rightMul[i-1] = rightMul[i] * nums[i];
// System.out.print(rightMul[i-1] + ",");
}
for(int i=0; i<nums.length; i++) {
res[i] = leftMul[i] * rightMul[i];
}
return res;
}
}
方法二:优化
上述实现方法中,leftMul
和rightMul
中的值仅在计算res[]
时使用一次,并未重复使用,因此可以直接将计算结果写入res数组中,利用变量R
记录后缀积,将空间复杂度从O(n)
降为O(1)
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
res[0] = 1;
// 先计算前缀乘积
for(int i=0; i<nums.length-1; i++) {
res[i+1] = res[i] * nums[i];
// System.out.print(res[i+1] + ",");
}
// 再乘以后缀乘积
int R = 1;
for(int i=nums.length-1; i>=0; i--) {
res[i] = res[i] * R;
// 更新后缀乘积
R *= nums[i];
// System.out.print(res[i-1] + ",");
}
return res;
}
}
41. 缺失的第一个正数
方法一:HashSet
先将正数放入HashSet中,之后枚举正整数,判断其是否在HashSet中
时间复杂度为O(n)
,符合要求;空间复杂度为O(1)
,不符合要求
class Solution {
public int firstMissingPositive(int[] nums) {
int res = -1;
HashSet<Integer> set = new HashSet<>();
// 将nums中符合要求的数放入hashSet中
for(int i=0; i<nums.length; i++) {
if(nums[i] > 0) {
set.add(nums[i]);
}
}
// 从1开始遍历,判断哪个i不在hashSet中
for(int i=1; i<Integer.MAX_VALUE; i++) {
if(!set.contains(i)) {
res = i;
break;
}
}
return res;
}
}
方法二:置换
class Solution {
public int firstMissingPositive(int[] nums) {
int res = -1;
// 从i开始遍历,一次操作后,nums[i]中元素置换完成
for(int i=0; i<nums.length; i++) {
// 只有当元素的值位于[0, nums.length]时才开始交换
// 并且当交换的值恰好在当前位置时则不进行交换
while(nums[i]>0 && nums[i]<=nums.length && nums[nums[i]-1] != nums[i]) {
int temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
}
}
for(int i=0; i<nums.length; i++) {
if(nums[i] != i+1) {
return i+1;
}
}
return nums.length+1;
}
}
方法三:哈希表
- 将数组中的非正数修改为N+1
- 将小于等于N的元素值修改为负数
- 遍历数组,确定第一个正数的位置