目录
给定一个字符串
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
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;
- }
- }
给定一个未排序的整数数组
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
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;
- }
- }
以数组
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;
-
- }
- }
给你二叉树的根结点
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;
- }
- }
- }
- }
给你一个整数数组
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 。
- class Solution {
- public List
> threeSum(int[] nums) {
- List
> 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;
- }
- }
数字
n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]示例 2:
输入:n = 1 输出:["()"]
思路:剩余左括号总数要小于等于右括号
- class Solution {
- List
res = new ArrayList<>(); - public List
generateParenthesis(int n) { - if(n <= 0){
- return res;
- }
- getParenthesis("",n,n);
- return res;
- }
-
- //left,right分别表示剩余的左括号,右括号数量
- private void getParenthesis(String str,int left, int right) {
- //左右括号全部用完时,加入res
- if(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);
- }
- }
- }
给你一个 无重复元素 的整数数组
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 输出: []
- class Solution {
-
- List
> result = new ArrayList<>();
-
- public List
> 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
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 ,则直接结束循环
- // 这是因为数组已排序,后边元素更大,子集和一定超过 target
- if (candidates[i] > target) {
- return;
- }
- //开始回溯
- current.add(candidates[i]);
- //之所以是i,不是i+1,是因为数组元素可以重复使用
- backtrack(i, current, target - candidates[i], candidates);
- current.remove(current.size() - 1);
- }
- }
- }
给你一个字符串
s
,请你将s
分割成一些子串,使每个子串都是 回文串。返回s
所有可能的分割方案。示例 1:
输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]示例 2:
输入:s = "a" 输出:[["a"]]
- class Solution {
-
- List
> result = new ArrayList<>();
-
- public List
> partition(String s) {
- if (s.length() == 0) {
- return result;
- }
- if (s.length() == 1) {
- List
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
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位,不是回文的:代表行不通,直接contine
- if (!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);
- }
- }
- }
- }
给定
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;
- }
给你一个整数数组
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;
- }
- }
给你一个整数数组
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)的方法一
- class Solution {
- public int lengthOfLIS(int[] nums) {
- if (nums.length <= 1) {
- return nums.length;
- }
- //定义一个result,在后面for循环中会不断更新result
- int 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;
- }
- }
给定一个长度为
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;
- }
- }
给你链表的头节点
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;
- }
- }
给你一个
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
spiralOrder(int[][] matrix) { - List
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;
- }
- }