• leetcode刷题记录


    目录

    字符串

    无重复字符的最长子串(力扣3)

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

    子串

     的长度。

    示例 1:

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

    示例 2:

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

    示例 3:

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

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

    1. class Solution {
    2. public int lengthOfLongestSubstring(String s) {
    3. if (s.length() <= 1) {
    4. return s.length();
    5. }
    6. int left = 0;
    7. int result = 0;
    8. Map map = new HashMap<>();
    9. for (int i = 0; i< s.length(); i++) {
    10. char current = s.charAt(i);
    11. if (!map.containsKey(current)) {
    12. map.put(current, i);
    13. } else {
    14. left = Math.max(left, map.get(current)+1);
    15. map.put(current, i);
    16. }
    17. result = Math.max(result, i-left+1);
    18. }
    19. return result;
    20. }
    21. }

    最长连续序列(力扣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

    思路:

    1. class Solution {
    2. public int longestConsecutive(int[] nums) {
    3. if (nums.length == 0) {
    4. return 0;
    5. }
    6. Set set = new HashSet<>();
    7. for(int i : nums) {
    8. set.add(i);
    9. }
    10. int result = 1;
    11. for (int i : nums) {
    12. if (set.contains(i-1)) {
    13. continue;
    14. }
    15. int temp = 1;
    16. while(set.contains(i+1)) {
    17. i++;
    18. temp++;
    19. }
    20. result = Math.max(result, temp);
    21. }
    22. return result;
    23. }
    24. }

    数组

    合并区间(力扣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] 可被视为重叠区间。
    1. class Solution {
    2. public int[][] merge(int[][] intervals) {
    3. if (intervals.length == 0 || intervals[0].length == 0) {
    4. return new int[0][0];
    5. }
    6. Arrays.sort(intervals, new Comparator<int[]>(){
    7. public int compare(int[] a, int[] b) {
    8. return a[0] - b[0];
    9. }
    10. });
    11. List<int[]> list = new ArrayList<>();
    12. list.add(intervals[0]);
    13. for (int i = 1; i< intervals.length; i++) {
    14. int[] current = list.get(list.size() - 1);
    15. if (intervals[i][0] <= current[1]) {
    16. current[1] = Math.max(intervals[i][1], current[1]);
    17. } else {
    18. list.add(intervals[i]);
    19. }
    20. }
    21. int[][] result = new int[list.size()][2];
    22. for (int i = 0; i< list.size(); i++) {
    23. result[i][0] = list.get(i)[0];
    24. result[i][1] = list.get(i)[1];
    25. }
    26. return result;
    27. }
    28. }

    二叉树展开为链表(力扣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]
    1. class Solution {
    2. public void flatten(TreeNode root) {
    3. while(root != null) {
    4. if (root.left == null) {
    5. root = root.right;
    6. } else {
    7. TreeNode pre = root.left;
    8. while(pre.right != null) {
    9. pre = pre.right;
    10. }
    11. pre.right = root.right;
    12. root.right = root.left;
    13. root.left = null;
    14. root = root.right;
    15. }
    16. }
    17. }
    18. }

    双指针

    三数之和(力扣15)

    给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != 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],如果前一个数与当前数相同,需要忽略,不然会重复
    1. class Solution {
    2. public List> threeSum(int[] nums) {
    3. List> result = new ArrayList<>();
    4. if (nums.length < 3) {
    5. return result;
    6. }
    7. Arrays.sort(nums);
    8. for (int i = 0; i < nums.length-2; i++) {
    9. //如果前一个数重复了,忽略跳过
    10. if (i!=0 && nums[i-1] == nums[i]) {
    11. continue;
    12. }
    13. int left = i+1;
    14. int right = nums.length -1;
    15. while(left < right) {
    16. //如果前一个数重复了,忽略跳过
    17. if (left != i+1 && nums[left] == nums[left-1]) {
    18. left++;
    19. continue;
    20. }
    21. //如果前一个数重复了,忽略跳过
    22. if (right != nums.length-1 && nums[right] == nums[right+1]) {
    23. right--;
    24. continue;
    25. }
    26. int temp = nums[left] + nums[right] + nums[i];
    27. if(temp > 0) {
    28. right--;
    29. } else if (temp < 0) {
    30. left++;
    31. } else {
    32. result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
    33. left++;
    34. right--;
    35. }
    36. }
    37. }
    38. return result;
    39. }
    40. }

    回溯

    括号生成(力扣22)

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

    示例 1:

    输入:n = 3
    输出:["((()))","(()())","(())()","()(())","()()()"]
    

    示例 2:

    输入:n = 1
    输出:["()"]

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

    1. class Solution {
    2. List res = new ArrayList<>();
    3. public List generateParenthesis(int n) {
    4. if(n <= 0){
    5. return res;
    6. }
    7. getParenthesis("",n,n);
    8. return res;
    9. }
    10. //left,right分别表示剩余的左括号,右括号数量
    11. private void getParenthesis(String str,int left, int right) {
    12. //左右括号全部用完时,加入res
    13. if(left == 0 && right == 0 ){
    14. res.add(str);
    15. return;
    16. }
    17. if(left == right){
    18. //剩余左右括号数相等,下一个只能用左括号
    19. getParenthesis(str+"(",left-1,right);
    20. }else if(left < right){
    21. //剩余左括号小于右括号,下一个可以用左括号也可以用右括号
    22. if(left > 0){
    23. getParenthesis(str+"(",left-1,right);
    24. }
    25. getParenthesis(str+")",left,right-1);
    26. }
    27. }
    28. }

    组合总和(力扣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)

    • 先对数组排序,然后回溯
    1. class Solution {
    2. List> result = new ArrayList<>();
    3. public List> combinationSum(int[] candidates, int target) {
    4. if (candidates.length == 0) {
    5. return result;
    6. }
    7. //对数组先排序,方便回溯时剪枝
    8. Arrays.sort(candidates);
    9. backtrack(0, new ArrayList<>(), target, candidates);
    10. return result;
    11. }
    12. public void backtrack(int start, List current, int target, int[] candidates) {
    13. // 当前的数组,已经满足和为target,加入答案里
    14. if (target == 0) {
    15. result.add(new ArrayList<>(current));
    16. return;
    17. }
    18. // 遍历所有选择
    19. // 剪枝二:从 start 开始遍历,避免生成重复子集
    20. for (int i = start; i< candidates.length; ++i) {
    21. // 剪枝一:若子集和超过 target ,则直接结束循环
    22. // 这是因为数组已排序,后边元素更大,子集和一定超过 target
    23. if (candidates[i] > target) {
    24. return;
    25. }
    26. //开始回溯
    27. current.add(candidates[i]);
    28. //之所以是i,不是i+1,是因为数组元素可以重复使用
    29. backtrack(i, current, target - candidates[i], candidates);
    30. current.remove(current.size() - 1);
    31. }
    32. }
    33. }

    分割回文串(力扣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进行回溯
    1. class Solution {
    2. List> result = new ArrayList<>();
    3. public List> partition(String s) {
    4. if (s.length() == 0) {
    5. return result;
    6. }
    7. if (s.length() == 1) {
    8. List temp = new ArrayList<>();
    9. temp.add(s);
    10. result.add(temp);
    11. return result;
    12. }
    13. //先生成二维回文的动态规划
    14. boolean[][] dp = generateDp(s);
    15. //回溯
    16. backTrack(0, new ArrayList<>(), dp, s);
    17. return result;
    18. }
    19. //dp[x][y]表示字符串[x,y]是否是回文的
    20. public boolean[][] generateDp(String s) {
    21. int length = s.length();
    22. boolean[][] dp = new boolean[length][length];
    23. //i代表长度,j代表从第j位开始循环遍历
    24. for (int i = 1; i <= length; i++) {
    25. for (int j = 0; j< length; j++) {
    26. int end = j + i -1;
    27. if (end >= length) {
    28. break;
    29. }
    30. if (i == 1) {
    31. dp[j][j] = true;
    32. } else if (i == 2) {
    33. dp[j][end] = s.charAt(j) == s.charAt(end);
    34. } else {
    35. dp[j][end] = dp[j+1][end-1] && s.charAt(j) == s.charAt(end);
    36. }
    37. }
    38. }
    39. return dp;
    40. }
    41. public void backTrack(int start, List current, boolean[][] dp, String s) {
    42. //string中所有字母已经处理完成,加到答案中
    43. if (start == s.length()) {
    44. result.add(new ArrayList<>(current));
    45. return;
    46. }
    47. for (int i = start; i < s.length(); ++i) {
    48. //如果从第start位到第i位,不是回文的:代表行不通,直接contine
    49. if (!dp[start][i]) {
    50. continue;
    51. } else {
    52. //如果从第start位到第i位,是回文的:从i+1开始回溯
    53. current.add(s.substring(start, i+1));
    54. backTrack(i+1, current, dp, s);
    55. current.remove(current.size()-1);
    56. }
    57. }
    58. }
    59. }

    动态规划

    接雨水(力扣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

    1. class Solution {
    2. public int trap(int[] height) {
    3. if (height.length == 0) {
    4. return 0;
    5. }
    6. int[] left = new int[height.length];
    7. int[] right = new int[height.length];
    8. left[0] = height[0];
    9. right[height.length-1] = height[height.length-1];
    10. int j;
    11. for (int i = 1; i< height.length; i++) {
    12. j = height.length -i -1;
    13. left[i] = Math.max(left[i-1], height[i]);
    14. right[j] = Math.max(right[j+1], height[j]);
    15. }
    16. int result = 0;
    17. for (int i = 0; i < height.length; i++) {
    18. result += Math.min(left[i],right[i]) - height[i];
    19. }
    20. return result;
    21. }


    乘积最大子数组(力扣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个元素结尾的乘积最大子数组的乘积

    1. class Solution {
    2. public int maxProduct(int[] nums) {
    3. int[] dpmax = new int[nums.length];
    4. int[] dpmin = new int[nums.length];
    5. dpmax[0] = nums[0];
    6. dpmin[0] = nums[0];
    7. int result = nums[0];
    8. for (int i = 1; i < nums.length; ++i) {
    9. dpmax[i] = Math.max(Math.max(dpmax[i-1] * nums[i], dpmin[i-1] * nums[i]), nums[i]);
    10. dpmin[i] = Math.min(Math.min(dpmax[i-1] * nums[i], dpmin[i-1] * nums[i]), nums[i]);
    11. result = Math.max(result, dpmax[i]);
    12. }
    13. return result;
    14. }
    15. }

    最长递增子序列(力扣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]
    1. class Solution {
    2. public int lengthOfLIS(int[] nums) {
    3. if (nums.length <= 1) {
    4. return nums.length;
    5. }
    6. //定义一个result,在后面for循环中会不断更新result
    7. int result = 1;
    8. int[] dp = new int[nums.length];
    9. dp[0] = 1;
    10. for (int i = 1; i < nums.length; i++) {
    11. for (int j = 0; j< i; j++) {
    12. dp[i] = 1;
    13. if (nums[i] > nums[j]) {
    14. dp[i] = Math.max(dp[i], dp[j] +1);
    15. }
    16. }
    17. result = Math.max(result, dp[i]);
    18. }
    19. return result;
    20. }
    21. }

    贪心

    跳跃游戏 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

    1. //DP
    2. class Solution {
    3. public int jump(int[] nums) {
    4. if (nums.length <= 1) {
    5. return 0;
    6. }
    7. int[] dp = new int[nums.length];
    8. Arrays.fill(dp, nums.length-1);
    9. dp[0] = 0;
    10. for (int i = 1; i< nums.length; i++) {
    11. for (int j = i-1; j>=0; j--) {
    12. if (j+nums[j] >= i) {
    13. dp[i] = Math.min(dp[i], dp[j]+1);
    14. }
    15. }
    16. }
    17. return dp[nums.length-1];
    18. }
    19. }
    20. //贪心
    21. class Solution {
    22. public int jump(int[] nums) {
    23. int length = nums.length;
    24. int end = 0;
    25. int maxPosition = 0;
    26. int steps = 0;
    27. for (int i = 0; i < length - 1; i++) {
    28. maxPosition = Math.max(maxPosition, i + nums[i]);
    29. if (i == end) {
    30. end = maxPosition;
    31. steps++;
    32. }
    33. }
    34. return steps;
    35. }
    36. }

    链表

    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)递归

    1. class Solution {
    2. public ListNode reverseKGroup(ListNode head, int k) {
    3. ListNode tail = head;
    4. for (int i = 1; i< k; i++) { //选取k个节点,需要向后移动了k-1次
    5. if (tail == null) {
    6. return head;
    7. }
    8. tail = tail.next;
    9. }
    10. if (tail == null) { //这里需要对第k个节点特判,否则会空指针
    11. return head;
    12. }
    13. ListNode next = tail.next; //next指向第k+1个节点
    14. tail.next = null;
    15. ListNode newHead = reverse(head);
    16. head.next = reverseKGroup(next, k);
    17. return newHead;
    18. }
    19. //反转链表
    20. private ListNode reverse(ListNode head) {
    21. if (head == null) {
    22. return head;
    23. }
    24. ListNode pre = null;
    25. while(head != null) {
    26. ListNode temp = head.next;
    27. head.next = pre;
    28. pre = head;
    29. head = temp;
    30. }
    31. return pre;
    32. }
    33. }

    矩阵

    螺旋矩阵(力扣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]
    1. class Solution {
    2. public List spiralOrder(int[][] matrix) {
    3. List list = new ArrayList<>();
    4. if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    5. return list;
    6. }
    7. int left =0;
    8. int right = matrix[0].length -1;
    9. int up = 0;
    10. int down = matrix.length - 1;
    11. while(true) {
    12. for (int i =left; i<= right; i++) {
    13. list.add(matrix[up][i]);
    14. }
    15. if (up+1>down) break;
    16. up++;
    17. for (int i = up; i<= down; i++) {
    18. list.add(matrix[i][right]);
    19. }
    20. if (left+1>right) break;
    21. right--;
    22. for (int i = right; i>=left; i--) {
    23. list.add(matrix[down][i]);
    24. }
    25. if (up+1>down) break;
    26. down--;
    27. for (int i = down; i>=up; i--) {
    28. list.add(matrix[i][left]);
    29. }
    30. if (left+1>right) break;
    31. left++;
    32. }
    33. return list;
    34. }
    35. }

  • 相关阅读:
    安卓性能优化,UI优化漫谈
    Java基础之《Ajax+JQuery(JavaEE开发进阶Ⅱ)》—JQuery事件与动画(1)
    第一章:最新版零基础学习 PYTHON 教程(第三节 - 下载并安装Python最新版本)
    zabbix 自动发现
    Flask快速入门(路由、CBV、请求和响应、session)
    本地笔记同步到博客
    数据思维总结:
    解读《互联网政务应用安全管理规定》网络和数据安全中的身份认证和审计合规建设
    AFG EDI 解决方案
    开源Windows12网页版HTML源码
  • 原文地址:https://blog.csdn.net/qq_41157876/article/details/138013155