Hot-100(Java版本)
...大约 20 分钟
哈希表
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标
/**
* 涉及两个变量，枚举右，寻找左
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int j=0; j<nums.length; j++){
if(map.containsKey(target - nums[j]))
return new int[]{map.get(target - nums[j]), j};
map.put(nums[j], j);
}
return null;
}
}
49.字母异位词
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String str : strs){
//单个字符串进行排序并恢复
char[] chars = str.toCharArray();
Arrays.sort(chars);
String s = new String(chars);
//JDK8 Map 新特性
map.computeIfAbsent(s, ()->new ArrayList<>()).add(str);
}
//得到所有的map.values()
return new ArrayList<>(map.values());
}
}
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
/**
* 本质还是一堆数 里面 找一个数是否存在
* 遍历到 j 位，找 nums[j]-1 是否存在，不存在就是作为起点
* 找到本起点的片段长度
*/
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums)
set.add(num);
int res = 0;
for (int num : nums) {
if(!set.contains(num-1)){ //新起点
int len = 1;
while(set.contains(++num)) len++;
res = Math.max(res, len);
}
}
return res;
}
}
/**
* 本质还是一堆数 里面 找一个数是否存在
* 遍历到 j 位，找 nums[j]-1 是否存在，以及 nums[j]+1 是否存在
* 存在就是长度之和 +1
* 并更新当前段落的开头和结尾的长度大小，以及本身的大小(避免本身是头或者尾)
*/
class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int res = 0;
for(int j=0; j<nums.length; j++){
if(map.containsKey(nums[j])) //相同数字跳过
continue;
int min_len = map.getOrDefault(nums[j]-1, 0);
int max_len = map.getOrDefault(nums[j]+1, 0);
int ans = min_len + max_len + 1;
map.put(nums[j]-min_len, ans);
map.put(nums[j]+max_len, ans);
map.put(nums[j], ans);
res = Math.max(res, ans);
}
return res;
}
}
219. 存在重复元素II-扩展
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
/**
* 两个变量，枚举一个(右)，寻找左
*/
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int j=0; j<nums.length; j++){
if(map.containsKey(nums[j]) && Math.abs(map.get(nums[j]) - j) <= k){
return true;
}
map.put(nums[j], j);
}
return false;
}
}
1512. 好数对的数量-扩展
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
/**
* 两个变量，枚举右边，找左边
* 不过枚举顺序已经保证满足 i < j的要求了
* 只需要记录数量即可
*/
class Solution {
public int numIdenticalPairs(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
for(int j=0; j<nums.length; j++){
if(map.containsKey(nums[j])){
ans += map.get(nums[j]);
map.put(nums[j], map.get(nums[j])+1);
}
else map.put(nums[j], 1);
}
return ans;
}
}
双指针
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
请注意 ，必须在不复制数组的情况下原地对数组进行操作
/**
* 复制非零到前指针，后续直接全部置零
*/
class Solution {
public void moveZeroes(int[] nums) {
int l = 0, r = l;
while(r < nums.length){
if(nums[r] != 0){
nums[l++] = nums[r++];
}
else r++;
}
while(l < nums.length)
nums[l++] = 0;
}
}
11. 盛水最多的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量
/**
* [i j] 之间构成容器，后续如果 i < j 所有 i j 内部构成的大小都不会大于 i*当前的wide
* 反之同理
*/
class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length-1;
int ans = 0;
while(l < r){
if(height[l] < height[r]){
ans = Math.max(ans, (r-l)*height[l++]);
}
else{
ans = Math.max(ans, (r-l)*height[r--]);
}
}
return ans;
}
}
15. 三数之和
/**
* l r mid
* 后两个指针去重很熟练了
* 注意第一个指针的去重，有个下标 i>0 保证，是先收集过的才去重
*/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for(int i=0; i<=nums.length-3; i++){
if(i > 0 && nums[i] == nums[i-1]) //第一个元素去重
continue;
if(nums[i]+nums[i+1]+nums[i+2] > 0) break; //剪枝优化
if(nums[i]+nums[nums.length-1]+nums[nums.length-2] < 0) continue;
int l = i+1, r = nums.length-1;
while(l < r){
if(nums[l]+nums[r]+nums[i] < 0)
l++;
else if(nums[l]+nums[r]+nums[i] > 0)
r--;
else{
ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
while(l < r && nums[l] == nums[l+1]) l++; //后两个去重
while(l < r && nums[r-1] == nums[r]) r--;
l++; r--;
}
}
}
return ans;
}
}
42. 接雨水
/**
* 对于每个坐标，找到前后缀高度中的的 "较小" 高度，
* 和自身的高度之差，就是能容纳水的体积
* 更新前后缀高度时，取前面(后面)高度和自身高度的max
*/
class Solution {
public int trap(int[] height) {
int[] pre = new int[height.length]; pre[0] = height[0];
int[] aft = new int[height.length]; aft[height.length-1] = height[height.length-1];
for(int i=1; i<height.length; i++){ //前缀高度
pre[i] = Math.max(height[i], pre[i-1]);
}
for(int i=height.length-2; i>=0; i--){ //后缀高度
aft[i] = Math.max(height[i], aft[i+1]);
}
int ans = 0;
for(int i=1; i<height.length-1; i++){
ans += Math.min(pre[i], aft[i])-height[i];
}
return ans;
}
}
167. 两数之和II-扩展
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这
两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length
/**
* 双指针，和盛水最多的容器思想很像
* 数组本身是排好序的，利用性质
* nums[i] + nums[j] > target 那么所有比 nums[i] 大的都会导致更大，只能 j--
* 反之同理
*/
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length-1;
while(l < r){
if(numbers[l] + numbers[r] > target)
r--;
else if(numbers[l] + numbers[r] < target)
l++;
else return new int[]{l+1, r+1};
}
return null;
}
}
2824. 统计和小于目标的下标对数目-扩展
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目
/**
* 没要求输出下标，就是可以改变顺序了
* 变为有序数组，可以利用双指针的性质了
* l + r < target 时，所有以 l 开头的都会小于 收集一次所有的 l 都会满足，就 l++
*/
class Solution {
public int countPairs(List<Integer> nums, int target) {
Collections.sort(nums); //集合排序 数组是Arrays.sort()
//int[] arr = nums.stream().mapToInt(Integer::intValue).toArray();
//Arrays.sort(arr);
int ans = 0;
int l = 0, r = nums.size()-1;
while(l < r){
if(nums.get(l)+nums.get(r) < target){
ans += r-l;
l++;
}else{
r--;
}
}
return ans;
}
}
16. 最接近的三数之和-扩展
/**
* 三数之和变形
*
*/
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = 0;
int len = Integer.MAX_VALUE;
for(int i=0; i<nums.length; i++){
int l = i+1, r = nums.length-1;
while(l < r){
int index = nums[l]+nums[r]+nums[i];
if(index < target)
l++;
else
r--;
if(Math.abs(target-index) < len){
ans = index;
len = Math.abs(target-index);
}
}
}
return ans;
}
}
18. 四数之和-扩展
/**
* 三数之和 plus 没有剪枝优化
*/
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for(int i=0; i<=nums.length-4; i++){
if(i > 0 && nums[i] == nums[i-1])
continue;
for(int j=i+1; j<=nums.length-3; j++){
if(j-i > 1 && nums[j] == nums[j-1])
continue;
int l = j+1, r = nums.length-1;
while(l < r){
long index = (long)nums[i]+(long)nums[j]+(long)nums[l]+(long)nums[r];
if(index < target){
l++;
}
else if(index > target)
r--;
else {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
while(l < r && nums[l+1] == nums[l]) l++;
while(l < r && nums[r-1] == nums[r]) r--;
l++; r--;
}
}
}
}
return ans;
}
}
611. 有效三角形的个数-扩展
611. 有效三角形的个数 - 力扣（LeetCode）固定最大边解释
给定一个包含非负整数的数组 `nums` ，返回其中可以组成三角形三条边的三元组个数
/**
* 排序后，只需要比较最小的两个数之和 与 最大数的关系了
* 但是特殊点是 需要固定最大边！！！
*/
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int ans = 0;
for(int i=nums.length-1; i>=2; i--){
int l = 0, r = i-1;
while(l < r){
if(nums[l]+nums[r] > nums[i]){
ans += r-l;
r--;
}else{
l++;
}
}
}
return ans;
}
}
滑动窗口
分享丨【题单】滑动窗口（定长/不定长/多指针） - 力扣（LeetCode）
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
/**
* 每次 r 进来的字符可能导致重复，而且只可能是刚进来的 s[r] 导致重复，
* 只需要判断这个单独字符的重复即可
* 关键在于数组判断重复
* 不是只包含字母，所以不能用数组[26] 应该用[128]
*/
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] count = new int[128];
char[] chars = s.toCharArray();
int ans = 0;
for(int l=0, r=0; r<s.length(); r++){
count[chars[r]]++;
while(count[chars[r]] > 1){
count[chars[l++]]--; //右移
}
ans = Math.max(ans, r-l+1);
}
return ans;
}
}
438. 找到字符串中所有字母异位词
/**
* 窗口大小固定的滑动窗口
* 或者
* 还是当普通的滑动窗口来做，只不过收集时，长度也是附加条件 - ***这思路比较简洁***
*/
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] count = new int[26];
List<Integer> ans = new ArrayList<>();
for(int i=0; i<p.length(); i++){
count[p.charAt(i)-'a']--;
}
for(int l=0, r=0; r<s.length(); r++){
count[s.charAt(r)-'a']++;
while(count[s.charAt(r)-'a'] > 0){
count[s.charAt(l++)-'a']--;
}
if(r-l+1 == p.length())
ans.add(l);
}
return ans;
}
}
219. 长度最小的子数组-扩展
给定一个含有 n 个正整数的数组和一个正整数 target
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0
/**
* 都是正数，可以考虑滑动窗口
* 大小不固定的滑动窗口 - 也可以叫双指针啦
*/
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int ans = Integer.MAX_VALUE;
for(int l=0, r=l; r<nums.length; r++){ //nums[r]是每次进来窗口
sum += nums[r];
while(sum >= target){
ans = Math.min(ans, r-l+1);
sum -= nums[l++];
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
/**
* 思路二： 用Map，遇到重复字符的时候，就移动左指针，到上一次出现位置的下一个
*/
class Solution {
public int lengthOfLongestSubstring(String S) {
char[] s = S.toCharArray();
int n = s.length, ans = 0, left = 0;
HashMap<Character, Integer> map = new HashMap<>();
for (int right = 0; right < n; right++) {
char c = s[right];
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1); // 更新左指针位置
}
map.put(c, right); // 更新字符的最后出现位置
ans = Math.max(ans, right - left + 1); // 更新窗口长度最大值
}
return ans;
}
}
713. 乘积小于k的子数组-扩展
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目
/**
* 正数、窗口大小不固定
* 退出 while 时不一定会满足收集条件
* 而且 while 里面还需要判断 l r 边界的条件问题
*
* 下面也有不用边界控制的写法
*/
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int ans = 0;
int sum = 1;
for(int l=0,r=l; r<nums.length; r++){
sum *= nums[r];
while(sum >= k && l <= r){
sum /= nums[l++];
}//end 满足收集条件
if(sum < k)
ans += r-l+1;
}
return ans;
}
}
//这种写法前面判断 k<=1 就保证了后面 l r 不会越界的问题
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(k <= 1) return 0;
int ans = 0;
int sum = 1;
for(int l=0,r=0; r<nums.length; r++){
sum *= nums[r];
while(sum >= k){
sum /= nums[l++]; //当一直不满足要求，退出时 l=r+1,此时乘积=1，一定满足 sum<k, 收集的结果 ans+=0
}
ans += r-l+1;
}
return ans;
}
}
76. 最小覆盖字串-扩展
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串
/**
* 和 428 的区别是，这里面可能包含别的多余字符串
* 不会是 1v1 完全匹配的
* 欠账个数 和 具体的欠账，当个数偿清的时候，可以开始缩进，
* 收集答案要注意条件，以及 return 时需要判断现在是否还清
*/
class Solution {
public String minWindow(String s, String t) {
int[] count = new int[128];
int num = t.length(); //欠账个数
int len = s.length(); //保存答案
int start = 0;
for(int i=0; i<t.length(); i++){
count[t.charAt(i)]--;
}
for(int l=0, r=0; r<s.length(); r++){
if(count[s.charAt(r)] < 0)
num--; //还账
count[s.charAt(r)]++;
while(num == 0 && count[s.charAt(l)] > 0){
count[s.charAt(l++)]--;
}
if(num == 0 && r-l+1 < len){ //收集
start = l;
len = r-l+1;
}
}
return num > 0 ? "" : s.substring(start, start+len); //是否还清
}
}
1004. 最大连续1的个数II-扩展
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
/**
* 找到欠 k 个0的最大长度
* 当区间内含的 0 过多时，开始缩进
* 当区间内含 0 个数 <= k 时，可以收集答案
*/
class Solution {
public int longestOnes(int[] nums, int k){
int ans_len = 0;
for(int l=0,r=0; r<nums.length; r++){
if(nums[r] == 0)
k--;
while(k < 0){
if(nums[l++] == 0)
k++;
}
if(k >= 0 && r-l+1 > ans_len){
ans_len = r-l+1;
}
}
return ans_len;
}
}
子串-(前缀和)
560. 和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数，正负数都存在
/**
* 有负数存在，滑动窗口失效
* 转为前缀和思考，一个数找另一个数，妙
*
* 先计算和还是先寻找数字 - 思考
* compute 方法还挺重要
*/
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int cur_sum = 0;
int ans = 0;
map.put(0, 1);
for(int i=0; i<nums.length; i++){
cur_sum += nums[i];
if(map.containsKey(cur_sum-k)){
ans += map.get(cur_sum-k);
}
map.compute(cur_sum, (key, value)->value != null ? value+1 : 1);
}
return ans;
}
}
239. 滑动窗口的最大值-单调队列
/**
* 单调队列
* 每次队头都是最大的元素
* 涉及到 Deque 用 ArrayDeque 还是 LinkedList 实现
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] ans = new int[nums.length - k + 1];
for(int i=0; i<k; i++) {
//小于的出队
while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
deque.removeLast();
}
deque.addLast(nums[i]);
}
ans[0] = deque.peekFirst(); //获取第一个元素
for(int i=k; i<nums.length; i++) {
if(deque.peekFirst() == nums[i-k])
deque.removeFirst();
//小于的出队
while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
deque.removeLast();
}
deque.addLast(nums[i]);
//收集答案
ans[i-k+1] = deque.peekFirst();
}
return ans;
}
}
// 将窗口合并在一起，不区分开始收集答案前的窗口
// 单独队列里面存下标
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n - k + 1];
Deque<Integer> q = new ArrayDeque<>(); // 双端队列
for (int i = 0; i < n; i++) {
// 1. 入
while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
q.removeLast(); // 维护 q 的单调性
}
q.addLast(i); // 入队
// 2. 出
if (q.peekFirst() == i-k) {
q.removeFirst();
}
// 3. 记录答案
if (i >= k - 1) {
// 由于队首到队尾单调递减，所以窗口最大值就是队首
ans[i - k + 1] = nums[q.peekFirst()];
}
}
return ans;
}
}
76. 最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串
/**
* 和 428 的区别是，这里面可能包含别的多余字符串
* 不会是 1v1 完全匹配的
* 欠账个数 和 具体的欠账，当个数偿清的时候，可以开始缩进，
* 收集答案要注意条件，以及 return 时需要判断现在是否还清
*/
class Solution {
public String minWindow(String s, String t) {
int[] count = new int[128];
int num = t.length(); //欠账个数
int len = s.length(); //保存答案
int start = 0;
for(int i=0; i<t.length(); i++){
count[t.charAt(i)]--;
}
for(int l=0, r=0; r<s.length(); r++){
if(count[s.charAt(r)] < 0)
num--; //还账
count[s.charAt(r)]++;
while(num == 0 && count[s.charAt(l)] > 0){
count[s.charAt(l++)]--;
}
if(num == 0 && r-l+1 < len){ //收集
start = l;
len = r-l+1;
}
}
return num > 0 ? "" : s.substring(start, start+len); //是否还清
}
}
1248. 统计优美子数组-扩展
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目
/**
* 前缀和的另一种应用
* |------|----------|
* map target
*/
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int num = 0;
int ans = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for(int l=0, r=0; r<nums.length; r++){
num += nums[r]%2 == 0 ? 0 : 1;
if(map.containsKey(num-k)){
ans += map.get(num-k);
}
map.compute(num, (key, v) -> v != null ? v+1:1);
}
return ans;
}
}
974. 和可被K整除的子数组-扩展
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
子数组 是数组的 连续 部分
/**
* 有负数，不能滑动窗口
* 考虑前缀和
* |---------|--------------|
* find tar % k sum
* (sum-find) % k == 0
* 用余数去判断，当前 sum % k == 2
* 那就去找到前面也是余数是2的个数，即可
*
* 注意负数 对于负数 sum % k，我们可以通过 (sum % k + k) % k 的方式得到正确的余数
*/
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int[] pre_sum = new int[k + 1];
pre_sum[0] = 1;
int sum = 0;
int ans = 0;
for(int i=0; i<nums.length; i++){
sum += nums[i];
ans += pre_sum[(sum % k + k) % k];
pre_sum[(sum % k + k) % k]++;
}
return ans;
}
}
523. 连续的子数组和-扩展
给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数
/**
* 都是正数，先考虑滑动窗口 - 窗口内的元素和 是倍数
* 但无法判断不满足条件时，是移动右窗口还是左窗口
* 改为前缀和数组 - 还是判断余数的出现次数
* 前缀和怎么控制窗口大小
*
* 将数组存储转为 map 存储，因为不需要计算个数，所以 value 作为出现下标即可
* 并且只需要保存 mod 出现的第一次即可
* |-----|--------------|
* mod2 mod=0 mod1
*/
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int mod = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for(int i=0; i<nums.length; i++){
mod = (mod + nums[i]) % k;
if(map.containsKey(mod)){
if(i-map.get(mod) > 1)
return true;
}else{
map.put(mod, i);
}
}
return false;
}
}
普通数组
53.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分
/**
* 遍历不断找到前面最小的 前缀和
* ans = nums[0] 不这么初始化就会错误，因为只有一个元素的话
* pre_sum - min_pre 就是当前的 nums[0] 如果是负数，ans = 0 则会保存0
*/
class Solution {
public int maxSubArray(int[] nums) {
int min_pre=0, pre_sum=0, ans=nums[0];
for(int i=0; i<nums.length; i++){
pre_sum += nums[i];
ans = Math.max(ans, pre_sum-min_pre);
min_pre = Math.min(min_pre, pre_sum);
}
return ans;
}
}
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
/**
* 根据二元组的首字母进行排序
*
* int[][] Arrays.copyOf 的拷贝操作
* Arrays.sort() lambda 比较器的定义
*
*/
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); //第一个递增
int[][] ans = new int[intervals.length][2];
int index = 0, start = intervals[0][0], end = intervals[0][1];
for(int i=1; i<intervals.length; i++){
if(intervals[i][0] <= end){
end = Math.max(end, intervals[i][1]); //区间包含
}
else{
ans[index++] = new int[]{start, end};
start = intervals[i][0];
end = intervals[i][1];
}
}
ans[index++] = new int[]{start, end};
return Arrays.copyOf(ans, index);
}
}
// 使用 Lambda 表达式对 intervals 进行复合排序
// Arrays.sort(intervals, (a, b) -> {
// if (a[0] != b[0]) {
// // 如果第一个元素不同，则按第一个元素递减排序
// return Integer.compare(b[0], a[0]);
// } else {
// // 如果第一个元素相同，则按第二个元素递增排序
// return Integer.compare(a[1], b[1]);
// }
// });
189. 翻转数组
/**
* 翻转 3 次
*/
class Solution {
int[] nums;
void reverse(int start, int end){
while(start <= end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
public void rotate(int[] nums, int k) {
this.nums = nums; //不用传参数了
k %= nums.length;
reverse(0, nums.length-k-1);
reverse(nums.length-k, nums.length-1);
reverse(0, nums.length-1);
}
}
238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题
/**
* 前缀乘积 * 后缀乘积
*/
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] aft = new int[nums.length];
int sum = 1; aft[nums.length-1] = 1;
int[] ans = new int[nums.length];
for(int i=nums.length-2; i>=0; i--){
aft[i] = aft[i+1]*nums[i+1];
}
for(int i=0; i<nums.length; i++){
ans[i] = sum*aft[i];
sum *= nums[i];
}
return ans;
}
}
41. 缺失的第一个正数
/**
* 交换 标记区域
* 下标 index 上的数字应该是 index+1
* 只保留正确的答案
*
* 防止套娃交换，即当前位置和要交换的位置都是一个数字，那么会一直交换
*/
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int l = 0, index = 0;
while (l < n) {
// 如果元素在有效范围内，并且不在正确的位置上
if (nums[l] > 0 && nums[l] <= n && nums[l] != l + 1 && nums[l] != nums[nums[l] - 1]) {
// 将元素交换到正确的位置上
int temp = nums[l];
nums[l] = nums[temp - 1];
nums[temp - 1] = temp;
} else {
l++;
}
}
while(index < n && nums[index] == index+1)
index++;
return index + 1;
}
}
矩阵
* 240. 搜索二维矩阵II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列
每列的元素从上到下升序排列
/**
* 二维搜索空间递减
*/
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length, m = matrix[0].length;
int i = 0, j = m-1;
while(i < n && j >= 0){
if(matrix[i][j] == target)
return true;
else if(matrix[i][j] > target)
j--;
else i++;
}
return false;
}
}
73. 矩阵置零
/**
* 扫描，有 0 则对应的行列都为 0
*/
class Solution {
public void setZeroes(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
Set<Integer> n_idx = new HashSet<>(); //不允许重复
Set<Integer> m_idx = new HashSet<>();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(matrix[i][j] == 0){
n_idx.add(i);
m_idx.add(j);
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(n_idx.contains(i) || m_idx.contains(j))
matrix[i][j] = 0;
}
}
}
}
链表
160. 相交链表
/**
* 快慢指针
* 好像还有一个走完一个去走另一个链表的做法
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2){
p1 = p1 == null ? headB : p1.next;
p2 = p2 == null ? headA : p2.next;
}
return p1;
}
}
206. 翻转链表
/**
* 头插法 一个q 一个r 防止断尾即可
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode p = new ListNode(-1, head);
ListNode q = p.next;
p.next = null;
while(q != null){
ListNode r = q.next; //防止断尾
q.next = p.next;
p.next = q;
q = r;
}
return p.next;
}
}
234. 回文链表
/**
* 找到中点 翻转后一半 继续匹配
*/
class Solution {
ListNode reverseList(ListNode head) {
ListNode p = new ListNode(-1, head);
ListNode q = p.next;
p.next = null;
while(q != null){
ListNode r = q.next; //防止断尾
q.next = p.next;
p.next = q;
q = r;
}
return p.next;
}//翻转链表
public boolean isPalindrome(ListNode head) {
ListNode fast = new ListNode(-1, head);
ListNode slow = fast;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode p = reverseList(slow.next);
fast = head;
while(p != null && fast.val == p.val){
fast = fast.next;
p = p.next;
}
return p == null;
}
}
141. 环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
return true;
}
return false;
}
}