LeetCode热门100题算法和思路（day3）
2022-08-17 本文已影响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 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 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];
}
}
}
