leetcode刷题记录

目录

字符串

无重复字符的最长子串（力扣3）

给定一个字符串 s ，请你找出其中不含有重复字符的最长

子串

的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

思路：用一个map维护每个字母最后出现的下标

class Solution {public int lengthOfLongestSubstring(String s) {if (s.length() <= 1) {return s.length();}int left = 0;int result = 0;Map<Character, Integer>  map = new HashMap<>();for (int i = 0; i< s.length(); i++) {char current = s.charAt(i);if (!map.containsKey(current)) {map.put(current, i);} else {left = Math.max(left, map.get(current)+1);map.put(current, i);}result = Math.max(result, i-left+1);}return result;}
}

最长连续序列（力扣128）

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

思路：

class Solution {public int longestConsecutive(int[] nums) {if (nums.length == 0) {return 0;}Set<Integer> set = new HashSet<>();for(int i : nums) {set.add(i);}int result = 1;for (int i : nums) {if (set.contains(i-1)) {continue;}int temp = 1;while(set.contains(i+1)) {i++;temp++;}result = Math.max(result, temp);}return result;}
}

数组

合并区间（力扣56）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0 || intervals[0].length == 0) {return new int[0][0];}Arrays.sort(intervals, new Comparator<int[]>(){public int compare(int[] a, int[] b) {return a[0] - b[0];}});List<int[]> list = new ArrayList<>();list.add(intervals[0]);for (int i = 1; i< intervals.length; i++) {int[] current = list.get(list.size() - 1);if (intervals[i][0] <= current[1]) {current[1] = Math.max(intervals[i][1], current[1]);} else {list.add(intervals[i]);}}int[][] result = new int[list.size()][2];for (int i = 0; i< list.size(); i++) {result[i][0] = list.get(i)[0];result[i][1] = list.get(i)[1];}return result;}
}

树

二叉树展开为链表（力扣114）

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]

class Solution {public void flatten(TreeNode root) {while(root != null) {if (root.left == null) {root =  root.right;} else {TreeNode pre = root.left;while(pre.right != null) {pre = pre.right;}pre.right = root.right;root.right = root.left;root.left = null;root = root.right;}}}
}

双指针

三数之和（力扣15）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路：. - 力扣（LeetCode）

细节：排序后如[-1,-1,0,1,1]，如果前一个数与当前数相同，需要忽略，不然会重复

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();if (nums.length < 3) {return result;}Arrays.sort(nums);for (int i = 0; i < nums.length-2; i++) {//如果前一个数重复了，忽略跳过if (i!=0 && nums[i-1] == nums[i]) {continue;}int left = i+1;int right = nums.length -1;while(left < right) {//如果前一个数重复了，忽略跳过if (left != i+1 && nums[left] == nums[left-1]) {left++;continue;}//如果前一个数重复了，忽略跳过if (right != nums.length-1 && nums[right] == nums[right+1]) {right--;continue;}int temp = nums[left] + nums[right] + nums[i];if(temp > 0) {right--;} else if (temp < 0) {left++;} else {result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));left++;right--;}}}return result;}
}

回溯

括号生成（力扣22）

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

思路：剩余左括号总数要小于等于右括号

class Solution {List<String> res = new ArrayList<>();public List<String> generateParenthesis(int n) {if(n <= 0){return res;}getParenthesis("",n,n);return res;}//left,right分别表示剩余的左括号，右括号数量private void getParenthesis(String str,int left, int right) {//左右括号全部用完时，加入resif(left == 0 && right == 0 ){res.add(str);return;}if(left == right){//剩余左右括号数相等，下一个只能用左括号getParenthesis(str+"(",left-1,right);}else if(left < right){//剩余左括号小于右括号，下一个可以用左括号也可以用右括号if(left > 0){getParenthesis(str+"(",left-1,right);}getParenthesis(str+")",left,right-1);}}}

组合总和（力扣39）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []

思路：. - 力扣（LeetCode）

先对数组排序，然后回溯

class Solution {List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {if (candidates.length == 0) {return result;}//对数组先排序，方便回溯时剪枝Arrays.sort(candidates);backtrack(0, new ArrayList<>(), target, candidates);return result;}public void backtrack(int start, List<Integer> current, int target, int[] candidates) {// 当前的数组，已经满足和为target，加入答案里if (target == 0) {result.add(new ArrayList<>(current));return;}// 遍历所有选择// 剪枝二：从 start 开始遍历，避免生成重复子集for (int i = start; i< candidates.length; ++i) {// 剪枝一：若子集和超过 target ，则直接结束循环// 这是因为数组已排序，后边元素更大，子集和一定超过 targetif (candidates[i] > target) {return;}//开始回溯current.add(candidates[i]);//之所以是i,不是i+1,是因为数组元素可以重复使用backtrack(i, current, target - candidates[i], candidates);current.remove(current.size() - 1);}}
}

分割回文串（力扣131）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]

思路：. - 力扣（LeetCode）

先生成boolean的dp[][]，dp[i][j]表示字符串的[i,j]是否是回文的
再对dp进行回溯

class Solution {List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {if (s.length() == 0) {return result;}if (s.length() == 1) {List<String> temp = new ArrayList<>();temp.add(s);result.add(temp);return result;}//先生成二维回文的动态规划boolean[][] dp = generateDp(s);//回溯backTrack(0, new ArrayList<>(), dp, s);return result;}//dp[x][y]表示字符串[x,y]是否是回文的public boolean[][] generateDp(String s) {int length = s.length();boolean[][] dp = new boolean[length][length];//i代表长度,j代表从第j位开始循环遍历for (int i = 1; i <= length; i++) {for (int j = 0; j< length; j++) {int end = j + i -1;if (end >= length) {break;}if (i == 1) {dp[j][j] = true;} else if (i == 2) {dp[j][end] = s.charAt(j) == s.charAt(end);} else {dp[j][end] = dp[j+1][end-1] && s.charAt(j) == s.charAt(end);}}}return dp;}public void backTrack(int start, List<String> current, boolean[][] dp, String s) {//string中所有字母已经处理完成,加到答案中if (start == s.length()) {result.add(new ArrayList<>(current));return;}for (int i = start; i < s.length(); ++i) {//如果从第start位到第i位,不是回文的:代表行不通,直接contineif (!dp[start][i]) {continue;} else {//如果从第start位到第i位,是回文的:从i+1开始回溯current.add(s.substring(start, i+1));backTrack(i+1, current, dp, s);current.remove(current.size()-1);}          }}
}

动态规划

接雨水（力扣42）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

思路：二维dp

class Solution {public int trap(int[] height) {if (height.length == 0) {return 0;}int[] left = new int[height.length];int[] right = new int[height.length];left[0] = height[0];right[height.length-1] = height[height.length-1];int j;for (int i = 1; i< height.length; i++) {j = height.length -i -1;left[i] = Math.max(left[i-1], height[i]);right[j] = Math.max(right[j+1], height[j]);}int result = 0;for (int i = 0; i < height.length; i++) {result += Math.min(left[i],right[i]) - height[i];}return result;}

乘积最大子数组（力扣152）

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续

子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路：同和最大子数组，dp[i]表示以第 i个元素结尾的乘积最大子数组的乘积

class Solution {public int maxProduct(int[] nums) {int[] dpmax = new int[nums.length];int[] dpmin = new int[nums.length];dpmax[0] = nums[0];dpmin[0] = nums[0];int result = nums[0];for (int i = 1; i < nums.length; ++i) {dpmax[i] = Math.max(Math.max(dpmax[i-1] * nums[i], dpmin[i-1] * nums[i]), nums[i]);dpmin[i] = Math.min(Math.min(dpmax[i-1] * nums[i], dpmin[i-1] * nums[i]), nums[i]);result = Math.max(result, dpmax[i]);}return result;}
}

最长递增子序列（力扣300）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

思路：. - 力扣（LeetCode）的方法一

定义dp[i]为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度
例子：输入：nums = [10,9,2,5,3,7,101,18]，dp = [1,1,1,2,2,3,4,4]

class Solution {public int lengthOfLIS(int[] nums) {if (nums.length <= 1) {return nums.length;}//定义一个result,在后面for循环中会不断更新resultint result = 1;int[] dp = new int[nums.length];dp[0] = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j< i; j++) {dp[i] = 1;if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] +1);}}result = Math.max(result, dp[i]);}return result;}
}

贪心

跳跃游戏 II（力扣45）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

思路：. - 力扣（LeetCode）贪心，或者DP

//DP
class Solution {public int jump(int[] nums) {if (nums.length <= 1) {return 0;}int[] dp = new int[nums.length];Arrays.fill(dp, nums.length-1);dp[0] = 0;for (int i = 1; i< nums.length; i++) {for (int j = i-1; j>=0; j--) {if (j+nums[j] >= i) {dp[i] = Math.min(dp[i], dp[j]+1);}}}return dp[nums.length-1];}
}//贪心
class Solution {public int jump(int[] nums) {int length = nums.length;int end = 0;int maxPosition = 0; int steps = 0;for (int i = 0; i < length - 1; i++) {maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) {end = maxPosition;steps++;}}return steps;}
}

链表

K个一组翻转链表（力扣25）

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

思路：. - 力扣（LeetCode）递归

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode tail = head;for (int i = 1; i< k; i++) { //选取k个节点，需要向后移动了k-1次if (tail == null) {return head;}tail = tail.next;}if (tail == null) {  //这里需要对第k个节点特判，否则会空指针return head;}ListNode next = tail.next;  //next指向第k+1个节点tail.next = null;ListNode newHead = reverse(head);head.next = reverseKGroup(next, k);return newHead;}//反转链表private ListNode reverse(ListNode head) {if (head == null) {return head;} ListNode pre = null;while(head != null) {ListNode temp = head.next;head.next = pre;pre = head;head = temp;}return pre;}
}

矩阵

螺旋矩阵（力扣54）

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list = new ArrayList<>();if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return list;}int left =0;int right = matrix[0].length -1;int up = 0;int down = matrix.length - 1;while(true) {for (int i =left; i<= right; i++) {list.add(matrix[up][i]);}if (up+1>down) break;up++;for (int i = up; i<= down; i++) {list.add(matrix[i][right]);}if (left+1>right) break;right--;for (int i = right; i>=left; i--) {list.add(matrix[down][i]);}if (up+1>down) break;down--;for (int i = down; i>=up; i--) {list.add(matrix[i][left]);}if (left+1>right) break;left++;}return list;}
}