美文网首页
LeetCode热门100题算法和思路(day3)

LeetCode热门100题算法和思路(day3)

作者: 码农朱同学 | 来源:发表于2022-08-17 09:28 被阅读0次

    LeetCode32 最长有效括号

    题目详情

    给你一个只包含 '('和 ')'的字符串,找出最长有效(格式正确且连续)括号子串的长度。
    示例 1:
    输入:s = "(()"
    输出:2
    解释:最长有效括号子串是 "()"
    示例 2:
    输入:s = ")()())"
    输出:4
    解释:最长有效括号子串是 "()()"
    示例 3:
    输入:s = ""
    输出:0
    提示:
    0 <= s.length <= 3 * 104
    s[i] 为 '(' 或 ')'

    代码
    public class LeetCode32 {
        public static void main(String[] args) {
            System.out.println(new Solution().longestValidParentheses(")()())"));
        }
    
        static class Solution {
            public int longestValidParentheses(String s) {
                int maxans = 0;
                Stack<Integer> stack = new Stack<>();
                stack.push(-1);
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) == '(') {
                        stack.push(i);
                    } else {
                        stack.pop();
                        if (stack.empty()) {
                            stack.push(i);
                        } else {
                            maxans = Math.max(maxans, i - stack.peek());
                        }
                    }
                }
                return maxans;
            }
        }
    }
    

    LeetCode33 搜索旋转排序数组

    题目详情

    整数数组 nums 按升序排列,数组中的值互不相同 。
    在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
    给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
    你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
    示例 1:
    输入:nums = [4,5,6,7,0,1,2], target = 0
    输出:4
    示例 2:
    输入:nums = [4,5,6,7,0,1,2], target = 3
    输出:-1
    示例 3:
    输入:nums = [1], target = 0
    输出:-1
    提示:
    1 <= nums.length <= 5000
    -104 <= nums[i] <= 104
    nums 中的每个值都 独一无二
    题目数据保证 nums 在预先未知的某个下标上进行了旋转
    -104 <= target <= 104

    代码
    public class LeetCode33 {
        public static void main(String[] args) {
            System.out.println(new Solution().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 1));
            System.out.println(new Solution().search2(new int[]{4, 5, 6, 7, 0, 1, 2}, 1));
        }
    
        static class Solution {
            //递归求解
            public int search(int[] nums, int target) {
                //对非法输入或不满足helper的情况提前处理
                if (nums == null || nums.length == 0) return -1;
                if (nums.length == 1) return target == nums[0] ? 0 : -1;
    
                return helper(nums, target, 0, nums.length - 1);
            }
    
            //递归辅助函数
            public int helper(int[] nums, int target, int left, int right) {
                //确定中间指针
                int mid = (left + right) >>> 1;
    
                //递归退出条件
                //找到了
                if (nums[mid] == target) return mid;
                //没找到
                if (left == right && nums[left] != target) return -1;
    
                //前一半有序
                if (nums[mid] >= nums[left]) {
                    //答案在前一半,因为前面退出条件对=target已经做了判定,这里就不存在相等了(target = nums[mid])
                    if (target >= nums[left] && target < nums[mid]) {
                        //同样此处的=mid已经被排除了(right = mid)
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else {
                    if (target > nums[mid] && target <= nums[right]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                //递归的求解
                return helper(nums, target, left, right);
            }
    
            /*
            二分搜索
            -关键词:排序,搜索
            -模式识别:有序或部分有序,基本使用二分搜索及其变种
            -算法描述:"丢弃"一半的数据
    
    
    可以发现的是,我们将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。拿示例来看,我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分,其中左边 [4, 5, 6] 这个部分的数组是有序的,其他也是如此。
    
    这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的,并根据有序的那个部分确定我们该如何改变二分查找的上下界,因为我们能够根据有序的那部分判断出 target 在不在这个部分:
    
    如果 [l, mid - 1] 是有序数组,且 target 的大小满足[nums[l],nums[mid]),则我们应该将搜索范围缩小至 [l, mid - 1],否则在 [mid + 1, r] 中寻找。
    如果 [mid, r] 是有序数组,且 target 的大小满足(nums[mid+1],nums[r]],则我们应该将搜索范围缩小至 [mid + 1, r],否则在 [l, mid - 1] 中寻找。
    
             */
            public int search2(int[] nums, int target) {
                int n = nums.length;
                if (n == 0) {
                    return -1;
                }
                if (n == 1) {
                    return nums[0] == target ? 0 : -1;
                }
                int l = 0, r = n - 1;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (nums[mid] == target) {
                        return mid;
                    }
                    if (nums[0] <= nums[mid]) {
                        if (nums[0] <= target && target < nums[mid]) {
                            r = mid - 1;
                        } else {
                            l = mid + 1;
                        }
                    } else {
                        if (nums[mid] < target && target <= nums[n - 1]) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                }
                return -1;
            }
        }
    }
    

    LeetCode34 在排序数组中查找元素的第一个和最后一个位置

    题目详情

    给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
    如果数组中不存在目标值 target,返回 [-1, -1]。
    你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
    示例 1:
    输入:nums = [5,7,7,8,8,10], target = 8
    输出:[3,4]
    示例 2:
    输入:nums = [5,7,7,8,8,10], target = 6
    输出:[-1,-1]
    示例 3:
    输入:nums = [], target = 0
    输出:[-1,-1]
    提示:
    0 <= nums.length <= 105
    -109 <= nums[i] <= 109
    nums 是一个非递减数组
    -109 <= target <= 109

    代码
    public class LeetCode34 {
        public static void main(String[] args) {
            System.out.println(Arrays.toString(new Solution().searchRange(new int[]{2, 3, 3, 3, 5, 6, 8}, 3)));
            System.out.println(Arrays.toString(new Solution().searchRange(new int[]{2, 2}, 2)));
            System.out.println(Arrays.toString(new Solution().searchRange(new int[]{}, 2)));
    
            System.out.println("----------------");
    
            System.out.println(Arrays.toString(new Solution().searchRange2(new int[]{2, 3, 3, 3, 5, 6, 8}, 3)));
            System.out.println(Arrays.toString(new Solution().searchRange2(new int[]{2, 2}, 2)));
            System.out.println(Arrays.toString(new Solution().searchRange2(new int[]{}, 2)));
        }
    
        static class Solution {
            /*
            二分查找算法
    
            - 二分查找的基本思想:在一个区间范围里看处在中间位置的元素的值nums[mid]与目标元素target大小关系,进而决定目标值落在哪一部分里
            - 目标元素target在有序数组中很可能存在多个。
            - 使用二分查找方法看到处在中间位置的元素的值nums[mid]恰好等于目标元素target的时候,还需要继续查找下去。
            - 此时容易陷入误区的是线性查找,正确的做法是继续二分查找。
             */
            public int[] searchRange(int[] nums, int target) {
                //第一个位置
                int leftIdx = binarySearch(nums, target, true);
                //最后一个位置
                int rightIdx = binarySearch(nums, target, false) - 1;
                if (leftIdx <= rightIdx &&
                        rightIdx < nums.length &&
                        nums[leftIdx] == target &&
                        nums[rightIdx] == target) {
                    return new int[]{leftIdx, rightIdx};
                }
                return new int[]{-1, -1};
            }
    
            public int binarySearch(int[] nums, int target, boolean lower) {
                int left = 0, right = nums.length - 1, ans = nums.length;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] > target || (lower && nums[mid] >= target)) {
                        right = mid - 1;
                        ans = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                return ans;
            }
    
            /*
            更简洁版本
             */
            public int[] searchRange2(int[] nums, int target) {
                return new int[]{find(nums, target, true), find(nums, target, false)};
            }
    
            public int find(int[] nums, int target, boolean minType) {
                int left = 0, right = nums.length - 1;
                int ans = -1;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (nums[mid] == target) {
                        ans = mid;
                        if (minType) {
                            right = mid - 1;
                        } else {
                            left = mid + 1;
                        }
                    } else if (target < nums[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                return ans;
            }
        }
    }
    

    LeetCode39 组合总和

    题目详情

    给你一个 无重复元素 的整数数组 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
    输出: []
    提示:
    1 <= candidates.length <= 30
    1 <= candidates[i] <= 200
    candidate 中的每个元素都 互不相同
    1 <= target <= 500

    代码
    public class LeetCode39 {
        public static void main(String[] args) {
            System.out.println(new Solution().combinationSum(new int[]{2, 3, 5}, 8));
            System.out.println(new Solution2().combinationSum(new int[]{2, 3, 5}, 8));
            System.out.println(new Solution3().combinationSum(new int[]{2, 3, 5}, 8));
            System.out.println(new Solution4().combinationSum(new int[]{2, 3, 5}, 8));
        }
    
        static class Solution {
            private List<List<Integer>> res = new ArrayList<>();
            private int[] candidates;
            private int len;
    
            private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
                if (residue == 0) {
                    // Java 中可变对象是引用传递,因此需要将当前 path 里的值拷贝出来
                    res.add(new ArrayList<>(pre));
                    return;
                }
                // 优化添加的代码2:在循环的时候做判断,尽量避免系统栈的深度
                // residue - candidates[i] 表示下一轮的剩余,如果下一轮的剩余都小于 0 ,就没有必要进行后面的循环了
                // 这一点基于原始数组是排序数组的前提,因为如果计算后面的剩余,只会越来越小
                for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
                    pre.add(candidates[i]);
                    // 【关键】因为元素可以重复使用,这里递归传递下去的是 i 而不是 i + 1
                    findCombinationSum(residue - candidates[i], i, pre);
                    pre.pop();
                }
            }
    
            public List<List<Integer>> combinationSum(int[] candidates, int target) {
                int len = candidates.length;
                if (len == 0) {
                    return res;
                }
                // 优化添加的代码1:先对数组排序,可以提前终止判断
                Arrays.sort(candidates);
                this.len = len;
                this.candidates = candidates;
                findCombinationSum(target, 0, new Stack<>());
                return res;
            }
        }
    
        /*
    
        搜索回溯
        对于这种寻找所以可行解的题,我们都可以尝试用"搜索回溯"的方法来解决
        更形象化地说,如果我们将整个搜索过程用一个树来表达,每次的搜索都会延伸出两个分叉,直到递归的终止条件,这样我们就能不重复且不遗漏地找到所有可行解;
    
         */
        static class Solution2 {
            public List<List<Integer>> combinationSum(int[] candidates, int target) {
                List<List<Integer>> ans = new ArrayList<List<Integer>>();
                List<Integer> combine = new ArrayList<Integer>();
                dfs(candidates, target, ans, combine, 0);
                return ans;
            }
    
            public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
                if (idx == candidates.length) {
                    return;
                }
                if (target == 0) {
                    ans.add(new ArrayList<Integer>(combine));
                    return;
                }
                // 直接跳过
                dfs(candidates, target, ans, combine, idx + 1);
                // 选择当前数
                if (target - candidates[idx] >= 0) {
                    combine.add(candidates[idx]);
                    dfs(candidates, target - candidates[idx], ans, combine, idx);
                    combine.remove(combine.size() - 1);
                }
            }
        }
    
        static class Solution3 {
    
            private List<List<Integer>> res = new ArrayList<>();
            private int[] candidates;
            private int len;
    
            private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
                if (residue == 0) {
                    // Java 中可变对象是引用传递,因此需要将当前 path 里的值拷贝出来
                    res.add(new ArrayList<>(pre));
                    return;
                }
                // 优化添加的代码2:在循环的时候做判断,尽量避免系统栈的深度
                // residue - candidates[i] 表示下一轮的剩余,如果下一轮的剩余都小于 0 ,就没有必要进行后面的循环了
                // 这一点基于原始数组是排序数组的前提,因为如果计算后面的剩余,只会越来越小
                for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
                    pre.add(candidates[i]);
                    // 【关键】因为元素可以重复使用,这里递归传递下去的是 i 而不是 i + 1
                    findCombinationSum(residue - candidates[i], i, pre);
                    pre.pop();
                }
            }
    
            public List<List<Integer>> combinationSum(int[] candidates, int target) {
                int len = candidates.length;
                if (len == 0) {
                    return res;
                }
                // 优化添加的代码1:先对数组排序,可以提前终止判断
                Arrays.sort(candidates);
                this.len = len;
                this.candidates = candidates;
                findCombinationSum(target, 0, new Stack<>());
                return res;
            }
        }
    
        /*
        深度优先 回溯
         */
        static class Solution4 {
            private List<List<Integer>> pathList = new LinkedList<>();
    
            public List<List<Integer>> combinationSum(int[] candidates, int target) {
                backtracking(candidates, new LinkedList<>(), 0, target, 0);
                return pathList;
            }
    
            private void backtracking(int[] candidates, List<Integer> path, int pathSum, int target, int startIndex) {
                //递归终点
                if (pathSum == target) {
                    //必需这样经过new LinkedList(path)
                    pathList.add(new LinkedList(path));
                    return;
                }
                for (int i = startIndex; i < candidates.length; i++) {
                    if (pathSum + candidates[i] <= target) {
                        path.add(candidates[i]);
                        backtracking(candidates, path, pathSum + candidates[i], target, i);
                        //回退
                        path.remove(path.size() - 1);
                    }
                }
            }
        }
    }
    
    

    LeetCode42 接雨水

    题目详情

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
    示例 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
    提示:
    n == height.length
    1 <= n <= 2 * 104
    0 <= height[i] <= 105
    代码
    public class LeetCode42 {
        public static void main(String[] args) {
            System.out.println(new Solution().trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        }
    
        static class Solution {
            public int trap(int[] height) {
                int sum = 0;
                int max_left = 0;
                int max_right = 0;
                int left = 1;
                int right = height.length - 2; // 加右指针进去
                for (int i = 1; i < height.length - 1; i++) {
                    //从左到右更
                    if (height[left - 1] < height[right + 1]) {
                        max_left = Math.max(max_left, height[left - 1]);
                        int min = max_left;
                        if (min > height[left]) {
                            sum = sum + (min - height[left]);
                        }
                        left++;
                        //从右到左更
                    } else {
                        max_right = Math.max(max_right, height[right + 1]);
                        int min = max_right;
                        if (min > height[right]) {
                            sum = sum + (min - height[right]);
                        }
                        right--;
                    }
                }
                return sum;
            }
        }
    }
    

    LeetCode46 全排列

    题目详情

    给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    示例 1:
    输入:nums = [1,2,3]
    输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    示例 2:
    输入:nums = [0,1]
    输出:[[0,1],[1,0]]
    示例 3:
    输入:nums = [1]
    输出:[[1]]
    提示:
    1 <= nums.length <= 6
    -10 <= nums[i] <= 10
    nums 中的所有整数 互不相同

    代码
    public class LeetCode46 {
        public static void main(String[] args) {
            System.out.println(new Solution().permute(new int[]{1, 2, 3}));
        }
    
        /*
         回溯
         */
        static class Solution {
            public void backtrack(int n, ArrayList<Integer> nums, List<List<Integer>> output, int first) {
                // 如果所有整数都用完了
                if (first == n)
                    //拷贝进去
                    output.add(new ArrayList<Integer>(nums));
                for (int i = first; i < n; i++) {
                    // 将第 i 个整数放在当前排列的首位
                    Collections.swap(nums, first, i);
                    // 使用下一个整数来完成排列
                    backtrack(n, nums, output, first + 1);
                    // 回溯
                    Collections.swap(nums, first, i);
                }
            }
    
            public List<List<Integer>> permute(int[] nums) {
                // 初始化输出列表
                List<List<Integer>> output = new LinkedList();
    
                // 将 nums 转换为列表,因为输出是列表的列表
                ArrayList<Integer> nums_lst = new ArrayList<Integer>();
                for (int num : nums)
                    nums_lst.add(num);
    
                int n = nums.length;
                backtrack(n, nums_lst, output, 0);
                return output;
            }
        }
    }
    

    LeetCode 48 旋转图像

    题目详情

    给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
    你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
    示例 1:

    输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出:[[7,4,1],[8,5,2],[9,6,3]]
    示例 2:

    输入:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
    输出:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
    提示:
    n == matrix.length == matrix[i].length
    1 <= n <= 20
    -1000 <= matrix[i][j] <= 1000

    代码
    public class LeetCode48 {
        public static void main(String[] args) {
            int[][] matrix1 = {
                    {5, 1, 9, 11},
                    {2, 4, 8, 10},
                    {13, 3, 6, 7},
                    {15, 14, 12, 16}
            };
            new Solution().rotate(matrix1);
            System.out.println(Arrays.deepToString(matrix1));
    
            int[][] matrix2 = {
                    {5, 1, 9, 11},
                    {2, 4, 8, 10},
                    {13, 3, 6, 7},
                    {15, 14, 12, 16}
            };
            new Solution().rotate2(matrix2);
            System.out.println(Arrays.deepToString(matrix2));
        }
    
        static class Solution {
            public void rotate(int[][] matrix) {
                int n = matrix.length;
                // 转置矩阵
                for (int i = 0; i < n; i++) {
                    for (int j = i; j < n; j++) {
                        int tmp = matrix[j][i];
                        matrix[j][i] = matrix[i][j];
                        matrix[i][j] = tmp;
                    }
                }
                // 反转每一行
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n / 2; j++) {
                        int tmp = matrix[i][j];
                        matrix[i][j] = matrix[i][n - j - 1];
                        matrix[i][n - j - 1] = tmp;
                    }
                }
            }
            /*
            原地旋转
             */
            public void rotate2(int[][] matrix) {
                int n = matrix.length;
                for (int i = 0; i < n / 2; ++i) {
                    for (int j = 0; j < (n + 1) / 2; ++j) {
                        int temp = matrix[i][j];
                        matrix[i][j] = matrix[n - j - 1][i];
                        matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                        matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                        matrix[j][n - i - 1] = temp;
                    }
                }
            }
        }
    }
    

    LeetCode49 字母异位词分组

    题目详情

    给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
    字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
    示例 1:
    输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
    示例 2:
    输入: strs = [""]
    输出: [[""]]
    示例 3:
    输入: strs = ["a"]
    输出: [["a"]]
    提示:
    1 <= strs.length <= 104
    0 <= strs[i].length <= 100
    strs[i] 仅包含小写字母

    代码
    public class LeetCode49 {
        public static void main(String[] args) {
            System.out.println(new Solution().groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
            System.out.println(new Solution().groupAnagrams2(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
        }
    
        static class Solution {
            /*
            方法一:排序
    由于互为字母异位词的两个字符串包含的字母相同,因此对两个字符串分别进行排序之后得到的字符串一定是相同的,故可以将排序之后的字符串作为哈希表的键。
             */
            public List<List<String>> groupAnagrams(String[] strs) {
                Map<String, List<String>> map = new HashMap<String, List<String>>();
                for (String str : strs) {
                    char[] array = str.toCharArray();
                    Arrays.sort(array);
                    String key = new String(array);
                    List<String> list = map.getOrDefault(key, new ArrayList<String>());
                    list.add(str);
                    map.put(key, list);
                }
                return new ArrayList<List<String>>(map.values());
            }
    
            /*
            方法二:计数
    由于互为字母异位词的两个字符串包含的字母相同,因此两个字符串中的相同字母出现的次数一定是相同的,故可以将每个字母出现的次数使用字符串表示,作为哈希表的键。
    
    由于字符串只包含小写字母,因此对于每个字符串,可以使用长度为 2626 的数组记录每个字母出现的次数。需要注意的是,在使用数组作为哈希表的键时,不同语言的支持程度不同,因此不同语言的实现方式也不同。
             */
            public List<List<String>> groupAnagrams2(String[] strs) {
                if (strs.length == 0) return new ArrayList();
                Map<String, List> ans = new HashMap<String, List>();
                int[] count = new int[26];
                for (String s : strs) {
                    Arrays.fill(count, 0);
                    for (char c : s.toCharArray()) count[c - 'a']++;
    
                    // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串,作为哈希表的键
                    StringBuilder sb = new StringBuilder("");
                    for (int i = 0; i < 26; i++) {
                        sb.append('#');
                        sb.append(count[i]);
                    }
                    String key = sb.toString();
                    if (!ans.containsKey(key)) ans.put(key, new ArrayList());
                    ans.get(key).add(s);
                }
                return new ArrayList(ans.values());
            }
        }
    }
    

    LeetCode53 最大子数组和

    题目详情

    给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
    子数组 是数组中的一个连续部分。
    示例 1:
    输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出:6
    解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
    示例 2:
    输入:nums = [1]
    输出:1
    示例 3:
    输入:nums = [5,4,-1,7,8]
    输出:23
    提示:
    1 <= nums.length <= 105
    -104 <= nums[i] <= 104

    代码
    public class LeetCode53 {
        public static void main(String[] args) {
            System.out.println(new Solution().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
            System.out.println(new Solution2().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        }
    
        static class Solution {
            /*
            动态规划
             */
            public int maxSubArray(int[] nums) {
                int n = nums.length;
                int currSum = nums[0], maxSum = nums[0];
    
                for (int i = 1; i < n; ++i) {
                    currSum = Math.max(nums[i], currSum + nums[i]);
                    maxSum = Math.max(maxSum, currSum);
                }
                return maxSum;
            }
    
            /*
            快慢指针法
             */
            public int maxSubArray2(int[] nums) {
    
                return 0;
            }
        }
    
        /*
        分治
         */
        static class Solution2 {
            public class Status {
                public int lSum, rSum, mSum, iSum;
    
                public Status(int lSum_, int rSum_, int mSum_, int iSum_) {
                    lSum = lSum_;
                    rSum = rSum_;
                    mSum = mSum_;
                    iSum = iSum_;
                }
            }
    
            public Status pushUp(Status l, Status r) {
                int iSum = l.iSum + r.iSum;
                int lSum = Math.max(l.lSum, l.iSum + r.lSum);
                int rSum = Math.max(r.rSum, r.iSum + l.rSum);
                int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
                return new Status(lSum, rSum, mSum, iSum);
            }
    
            public Status getInfo(int[] a, int l, int r) {
                if (l == r) return new Status(a[l], a[l], a[l], a[l]);
                int m = (l + r) >> 1;
                Status lSub = getInfo(a, l, m);
                Status rSub = getInfo(a, m + 1, r);
                return pushUp(lSub, rSub);
            }
    
            public int maxSubArray(int[] nums) {
                return getInfo(nums, 0, nums.length - 1).mSum;
            }
        }
    }
    

    LeetCode55 跳跃游戏

    题目详情

    给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    判断你是否能够到达最后一个下标。
    示例 1:
    输入:nums = [2,3,1,1,4]
    输出:true
    解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
    示例 2:
    输入:nums = [3,2,1,0,4]
    输出:false
    解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
    提示:
    1 <= nums.length <= 3 * 104
    0 <= nums[i] <= 105

    代码
    public class LeetCode55 {
        public static void main(String[] args) {
            System.out.println(new Solution().canJump(new int[]{2, 3, 1, 1, 4}));
            System.out.println(new Solution().canJump2(new int[]{2, 3, 1, 1, 4}));
        }
    
        /*
        我们可以用贪心的方法解决这个问题。
    
         */
        static class Solution {
            public boolean canJump(int[] nums) {
                int n = nums.length;
                int rightmost = 0;
                for (int i = 0; i < n; ++i) {
                    if (i <= rightmost) {
                        rightmost = Math.max(rightmost, i + nums[i]);
                        if (rightmost >= n - 1) {
                            return true;
                        }
                    }
                }
                return false;
            }
    
            /*
            贪心
             */
            public boolean canJump2(int[] nums) {
                int lastPos = nums.length - 1;
                for (int i = nums.length - 1; i >= 0; i--) {
                    if (i + nums[i] >= lastPos) {
                        lastPos = i;
                    }
                }
                return lastPos == 0;
            }
        }
    }
    

    LeetCode56 合并区间

    题目详情

    以数组 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 <= intervals.length <= 104
    intervals[i].length == 2
    0 <= starti <= endi <= 104

    代码
    public class LeetCode56 {
        public static void main(String[] args) {
            System.out.println(new Solution().merge(Arrays.asList(
                    new Solution.Interval(1, 3)
                    , new Solution.Interval(2, 6)
                    , new Solution.Interval(8, 10)
                    , new Solution.Interval(15, 18)
            )));
        }
    
        static class Solution {
            private class IntervalComparator implements Comparator<Interval> {
                @Override
                public int compare(Interval a, Interval b) {
                    return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
                }
            }
    
            public List<Interval> merge(List<Interval> intervals) {
                Collections.sort(intervals, new IntervalComparator());
    
                LinkedList<Interval> merged = new LinkedList<Interval>();
                for (Interval interval : intervals) {
                    // 如果合并区间列表为空,或者当前区间与前一个区间不重叠,则简单地追加它。
                    if (merged.isEmpty() || merged.getLast().end < interval.start) {
                        merged.add(interval);
                    }
                    // 否则,有重叠,所以我们合并当前和以前的间隔。
                    else {
                        merged.getLast().end = Math.max(merged.getLast().end, interval.end);
                    }
                }
                return merged;
            }
    
            private static class Interval {
                public int start;
                public int end;
    
                public Interval(int start, int end) {
                    this.start = start;
                    this.end = end;
                }
    
                @Override
                public String toString() {
                    return "{" +
                            "start=" + start +
                            ", end=" + end +
                            '}';
                }
            }
        }
    }
    
    

    LeetCode62 不同路径

    题目详情

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
    问总共有多少条不同的路径?
    示例 1:


    输入:m = 3, n = 7
    输出:28
    示例 2:
    输入:m = 3, n = 2
    输出:3
    解释:
    从左上角开始,总共有 3 条路径可以到达右下角。
    1. 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向下
      示例 3:
      输入:m = 7, n = 3
      输出:28
      示例 4:
      输入:m = 3, n = 3
      输出:6
      提示:
      1 <= m, n <= 100
      题目数据保证答案小于等于 2 * 109
    代码
    class LeetCode62 {
        public static void main(String[] args) {
            System.out.println(new Solution().uniquePaths(9, 8));
            System.out.println(new Solution().uniquePaths2(9, 8));
            System.out.println(new Solution().uniquePaths3(9, 8));
            System.out.println(new Solution().uniquePaths4(9, 8));
        }
    
        static class Solution {
            public int uniquePaths(int m, int n) {
                int[] cur = new int[n];
                Arrays.fill(cur, 1);
                for (int i = 1; i < m; i++) {
                    for (int j = 1; j < n; j++) {
                        cur[j] += cur[j - 1];
                    }
                }
                return cur[n - 1];
            }
    
            /*
            动态规划
             */
            public int uniquePaths2(int m, int n) {
                int[][] dp = new int[m][n];
                for (int i = 0; i < n; i++) dp[0][i] = 1;
                for (int i = 0; i < m; i++) dp[i][0] = 1;
                for (int i = 1; i < m; i++) {
                    for (int j = 1; j < n; j++) {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
                return dp[m - 1][n - 1];
            }
    
            public int uniquePaths3(int m, int n) {
                int[] pre = new int[n];
                int[] cur = new int[n];
                Arrays.fill(pre, 1);
                Arrays.fill(cur, 1);
                for (int i = 1; i < m; i++) {
                    for (int j = 1; j < n; j++) {
                        cur[j] = cur[j - 1] + pre[j];
                    }
                    pre = cur.clone();
                }
                return pre[n - 1];
            }
    
            public int uniquePaths4(int m, int n) {
                int[] cur = new int[n];
                Arrays.fill(cur, 1);
                for (int i = 1; i < m; i++) {
                    for (int j = 1; j < n; j++) {
                        cur[j] += cur[j - 1];
                    }
                }
                return cur[n - 1];
            }
        }
    }
    

    LeetCode64 最小路径和

    题目详情

    给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
    说明:每次只能向下或者向右移动一步。
    示例 1:

    输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出:7
    解释:因为路径 1→3→1→1→1 的总和最小。
    示例 2:
    输入:grid = [[1,2,3],[4,5,6]]
    输出:12
    提示:
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 200
    0 <= grid[i][j] <= 100

    代码
    public class LeetCode64 {
        public static void main(String[] args) {
            System.out.println(new Solution().minPathSum(new int[][]{
                    {1, 3, 1},
                    {1, 5, 1},
                    {4, 2, 1}
            }));
        }
    
        static class Solution {
            public int minPathSum(int[][] grid) {
                int[][] dp = new int[grid.length][grid[0].length];
                for (int i = grid.length - 1; i >= 0; i--) {
                    for (int j = grid[0].length - 1; j >= 0; j--) {
                        if (i == grid.length - 1 && j != grid[0].length - 1)
                            dp[i][j] = grid[i][j] + dp[i][j + 1];
                        else if (j == grid[0].length - 1 && i != grid.length - 1)
                            dp[i][j] = grid[i][j] + dp[i + 1][j];
                        else if (j != grid[0].length - 1 && i != grid.length - 1)
                            dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                        else
                            dp[i][j] = grid[i][j];
                    }
                }
                return dp[0][0];
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:LeetCode热门100题算法和思路(day3)

          本文链接:https://www.haomeiwen.com/subject/fdrdgrtx.html