class Solution {
public int maxSubArray(int[] nums) {
//使用动态规划
int len = nums.length;
if(len == 1){
return nums[0];
}
int max = nums[0];//用来存储最大和
int now = 0;//用来存储当前和
for(int i = 0;i < len;i++){
if(now < 0){
now = nums[i];//如果now小于0，那么更新指针到最新一位，即当前和为当前数
}else{
now += nums[i];//如果now大于0，那么可以继续加
}
if(now > max){//如果当前和大于最大和 那么更新最大和
max = now;
System.out.println("max = " + max);
}
}
return max;
}
}class Solution {
public int[][] merge(int[][] intervals) {
//获取数组长度
int length = intervals.length;
//初始化一个新的数组存放合并后的值，但是长度可能存在多余
int[][] merge = new int[length][2];
//对数组的左端点进行排序
Arrays.sort(intervals,(x,y)->{
return x[0] - y[0];
});
//将第一个值直接放入数组初始化
merge[0] = intervals[0];
//新数组中最后一个元素下标的位置
int index = 0;
//循环遍历
for(int i = 1; i < length; i++){
//因为数组中的左端点已经按照从大到小的顺序排列
//那么当新数组中最后一个右端点如果小于当前元素的左端点，那么一定不重合，
//直接加入新的数组集合，否则就是一定会有重合需要合并的
if(intervals[i][0] > merge[index][1]){
merge[++index] = intervals[i];
}else{
//这里要获取两个右端点的最大值作为合并后的右端点，
//因为左端点排序之后你不知道右端点到底是大是小的。
merge[index][1] = Math.max(intervals[i][1], merge[index][1]);
}
}
//这里copy新的数组是因为原来的初始化的merge数组是最大长度length，这样如果
//存在合并的数组之后，那么merge就存在了[0,0]这种给的元素，这样是不符合要求的
//所以重新复制一个新的数组，长度是index+1是因为index是实际元素的下标，
//如果变成长度要+1
return Arrays.copyOf(merge, index+1);
}
}class Solution {
public void rotate(int[] nums, int k) {
/**
简单实现 直接求余的方式
*/
/**
int numlen = nums.length;
if(numlen == 1){
return;
}
int[] result = new int[numlen];
for(int i = 0;i < numlen; i++){
result[(i + k) % numlen] = nums[i];
}
System.out.println(result[1]);
System.arraycopy(result, 0, nums, 0, numlen);
*/
/**
进阶实现 使用三次数组翻转实现
*/
int numlen = nums.length;
k = k % numlen;//注意给k求余 防止k大于numlen多轮的情况
if(numlen == 1){
return;
}
reserve(nums, 0, numlen - 1);
reserve(nums, 0, k - 1);
reserve(nums, k, numlen - 1);
}
public void reserve(int[] nums, int left, int right){
int temp = 0;
while(left < right){//左右指针翻转数组
temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}class Solution {
public int[] productExceptSelf(int[] nums) {
/**
//更加清晰版 可以看到上下三角的求解过程。
int length = nums.length;
// L 和 R 分别表示左右两侧的乘积列表
int[] L = new int[length];
int[] R = new int[length];
int[] answer = new int[length];
// L[i] 为索引 i 左侧所有元素的乘积
// 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
L[0] = 1;
for (int i = 1; i < length; i++) {
L[i] = nums[i - 1] * L[i - 1];
}
// R[i] 为索引 i 右侧所有元素的乘积
// 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
R[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
R[i] = nums[i + 1] * R[i + 1];
}
// 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
for (int i = 0; i < length; i++) {
answer[i] = L[i] * R[i];
}
return answer;
*/
//空间复杂度为O（1）的方法直接在结果数组中操作
int numlen = nums.length;
if(numlen == 0) return new int[0];
if(numlen == 1) return nums;
int[] result = new int[numlen];
result[0] = 1;
int temp = 1;
for(int i = 1;i < numlen; i++){
result[i] = result[i - 1] * nums[i - 1];
}
for(int i = numlen - 2;i >= 0; i--){
temp *= nums[i + 1];
result[i] *= temp;
}
return result;
}
}class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
/**
要找到缺失的第一个正数，首先要确定边界
首先如果是小于0或者大于数组长度的数，他们一定是缺位的。
这个正数一定在[1, len + 1]这个范围内
为什么？
当都为负数是 1 就是最大正数
当都在范围内时 len + 1 就是最小正数
若有在这个区间中的数
再一个一个排除
*/
for(int i = 0;i < len; i++){
while(nums[i] > 0 && nums[i] < len && nums[nums[i] - 1] != nums[i]){//这里就是找到在区间范围内的数，把他们放对位
swapNums(nums, nums[i] - 1, i);//即这个数的值就是它的位置
}
}
for(int i = 0;i < len; i++){//找到第一个不对位的数，直接返回就是最小正数
if(nums[i] != i + 1){
return i + 1;
}
}
return len + 1;//如果到最后都没返回，证明都在范围内。返回 len + 1。
}
public void swapNums(int[] nums, int index1, int index2){
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}解题方法都写在注释里了。最后再提需要注意的点。
53注意动态规划的步骤，第一次写很顺利几分钟写完了，再写竟然写不出了。主要是now小于0更新指针到最新一位，否则可以继续加。
56注意两个函数的调用
Arrays.sort(intervals,(x,y)->{
return x[0] - y[0];
});
return Arrays.copyOf(merge, index+1);这两个Arrays不熟悉要记。特别sort这样可以根据第一个值排序。
189注意巧妙解法，用三个reserve翻转解决。
238比较难，注意上下三角的面积计算。说白了就是先乘前面的，再乘后面的，最后放在一起乘。想要优化空间复杂度就是在结果数组先乘前面的，再乘后面的，直接返回。
41代码比较简单，要理解这道题目的边界，第一个最小正数的判断步骤以及和边界的关系。从而找到对应值。
Comments NOTHING