上传到网站,租一个服务器要多少钱,怎么查自己的邮箱号,wordpress 自动连接1. LC56 合并区间
题目链接
Arrays.sort先让intervals里的子数组按照子数组的第一个数字值从小到大排列。开一个新数组#xff0c;newInterval#xff0c;存放合并好的子数组让intervals的当前子数组i的第一个数字与newInterval的当前子数组index的最后一个数字比较大小newInterval存放合并好的子数组让intervals的当前子数组i的第一个数字与newInterval的当前子数组index的最后一个数字比较大小如果区间没有重叠则interval的i加入newInterval; 如果重叠则与newInterval的区间合并注意合并时并不是newInterval[index][1] intervals[i][1] 而是newInterval[index][1] Math.max(newInterval[index][1], intervals[i][1]); 因为有可能是这种情况[1,6],[2,4]——这种情况合并还是[1,6]。
秒懂力扣区间题目重叠区间、合并区间、插入区间
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (v1, v2) - v1[0] - v2[0]);int[][] newInterval new int[intervals.length][2];newInterval[0] intervals[0];int index 0;for (int i1; iintervals.length; i){if (intervals[i][0] newInterval[index][1]){index;newInterval[index] intervals[i];}else{newInterval[index][1] Math.max(newInterval[index][1], intervals[i][1]);}}return Arrays.copyOf(newInterval, index1);}
}2. LC238除自身以外数组的乘积
题目链接
class Solution {public int[] productExceptSelf(int[] nums) {int[] left new int[nums.length];int[] right new int[nums.length];//leftleft[0] 1;for (int i1; ileft.length; i){left[i] left[i-1] * nums[i-1];}//rightright[right.length-1] 1;for (int iright.length-2; i0; i--){right[i] right[i1] * nums[i1];}//合并int[] result new int[nums.length];for (int i0; inums.length; i){result[i] left[i] * right[i];}return result;}
}3.随想录1、二分查找
题目链接
最重要的是确定左闭右闭区间所以while条件是。因为左闭右闭就是左边区间也包括右边区间也包括所以左右区间可以。如果是开区间一个区间不包括一个区间包括那么两个区间必不能相等。
代码
class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length-1;// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target nums[0] || target nums[nums.length - 1]) {return -1;}while(left right){int mid (rightleft)/2;if (nums[mid] target){return mid;}else if (nums[mid] target){right mid - 1;}else if (nums[mid] target){left mid 1;}}return -1;}
}4. LC560 和为k的子数组
题目链接
解法一 暴力算法 易错在外层循环时nums[i] k了之后不要continue还有继续内循环。因为可能会有这种情况满足和为k之后后面出现了1和-1。此时相加和依然为k。
class Solution {public int subarraySum(int[] nums, int k) {int sum 0;int count 0;for (int i0; inums.length; i){sum nums[i];if (nums[i] k){count;}for (int ji1; jnums.length; j){sum nums[j];if (sum k){count;}}}return count;}
}解法二 前缀和
假设数组的前缀和数组为prefixSum其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。
对于任意的两个下标i和ji j如果prefixSum[j] - prefixSum[i] k即从第i个位置到第j个位置的元素之和等于k那么说明从第i1个位置到第j个位置的连续子数组的和为k。
遍历数组计算每个位置的前缀和并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中检查是否存在prefixSum[j] - k的前缀和如果存在说明从某个位置到当前位置的连续子数组的和为k将对应的次数累加到结果中。
这样通过遍历一次数组统计出和为k的连续子数组的个数并且时间复杂度为O(n)其中n为数组的长度。
class Solution {public int subarraySum(int[] nums, int k) {int preSum 0;int count 0;MapInteger, Integer map new HashMap();map.put(0,1); // 初始化前缀和为0的次数为1for (int i0; inums.length; i){preSum nums[i];if (map.containsKey(preSum-k)){count map.get(preSum-k);}if (map.containsKey(preSum)){map.put(preSum, map.get(preSum)1);}else{map.put(preSum, 1);}}return count;}
}为什么要初始化前缀和 如果从数组的开始位置到当前位置的子数组的和恰好等于 k那么这个子数组的前缀和就是 0即 sum - k 等于 0。因此需要初始化一个前缀和为 0 的次数为 1表示从数组的开始位置到当前位置的子数组的和为 k 的情况。如果不初始化那么这种情况会被漏掉导致结果不正确。
