LeetCode热门100题算法和思路（day10）
LeetCode538 把二叉搜索树转换为累加树
题目详情
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1]
输出：[1,null,1]
示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
提示：
树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
代码
public class LeetCode538 {
public static void main(String[] args) {
TreeNode.prettyPrintTree(new Solution().convertBST(TreeNode.buildBinaryTree(new Integer[]{4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8})));
}
static class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root != null) {
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
}
return root;
}
}
}
LeetCode543二叉树的直径
题目详情
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
代码
public class LeetCode543 {
public static void main(String[] args) {
System.out.println(new Solution().diameterOfBinaryTree(TreeNode.buildBinaryTree(new Integer[]{1, 2, 2, null, 3, null, 3})));
}
/*
深度优先搜索
*/
static class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
depth(root);
return ans - 1;
}
public int depth(TreeNode node) {
if (node == null) {
return 0; // 访问到空节点了，返回0
}
int L = depth(node.left); // 左儿子为根的子树的深度
int R = depth(node.right); // 右儿子为根的子树的深度
ans = Math.max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
}
}
}
LeetCode560 和为K的子数组
题目详情
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
代码
class LeetCode560 {
public static void main(String[] args) {
System.out.println(new Solution().subarraySum(new int[]{1, 2, 3, 0, 2, 1, 3, 2, 4}, 3));
System.out.println(new Solution().subarraySum1(new int[]{1, 2, 3, 0, 2, 1, 3, 2, 4}, 3));
System.out.println(new Solution().subarraySum2(new int[]{1, 2, 3, 0, 2, 1, 3, 2, 4}, 3));
System.out.println(new Solution().subarraySum3(new int[]{1, 2, 3, 0, 2, 1, 3, 2, 4}, 3));
}
static class Solution {
/*
暴力法
*/
public int subarraySum(int[] nums, int k) {
// 初始化，使用count储存结果
int count = 0;
//遍历nums考虑每个位置start作为子数组结尾的情况
for (int start = 0; start < nums.length; ++start) {
//记录当前子数组的和
int sum = 0;
for (int end = start; end >= 0; --end) {
sum += nums[end];
if (sum == k) {
count++;
}
}
}
return count;
}
/*
暴力法
*/
public int subarraySum1(int[] nums, int k) {
int len = nums.length;
int sum = 0;
int count = 0;
//双重循环
for (int i = 0; i < len; ++i) {
for (int j = i; j < len; ++j) {
sum += nums[j];
//发现符合条件的区间
if (sum == k) {
count++;
}
}
//记得归零，重新遍历
sum = 0;
}
return count;
}
public int subarraySum2(int[] nums, int k) {
//前缀和数组
int[] presum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
//这里需要注意，我们的前缀和是presum[1]开始填充的
presum[i + 1] = nums[i] + presum[i];
}
//统计个数
int count = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = i; j < nums.length; ++j) {
//注意偏移，因为我们的nums[2]到nums[4]等于presum[5]-presum[2]
//所以这样就可以得到nums[i,j]区间内的和
if (presum[j + 1] - presum[i] == k) {
count++;
}
}
}
return count;
}
public int subarraySum3(int[] nums, int k) {
if (nums.length == 0) {
return 0;
}
// hash
// 记录合适的连续字符串数量
int count = 0;
// 记录前面数字相加之和
int pre = 0;
// map记录前几个数字之和为K出现相同和的次数为V
HashMap<Integer, Integer> map = new HashMap<>();
// 初始化
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
// 前缀和
// 设
// pre[i]=pre[i−1]+nums[i]
// 由于补上了0，1这个情况 问题由多少个连续数字之和等于k 转为
// pre[i]−pre[j−1]==k （前缀和之差为k，代表这两个前缀和中间的数字相加就是K）
// 如果前面某些数字之和加上这个数字正好等于K（存在一个数字加上nums[i]结果为K
// 说明找到了
if (map.containsKey(pre - k)) {
// 累计
count += map.get(pre - k);
}
// 计算新的和放入map
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return count;
}
}
}
LeetCode581 最短无序连续子数组
题目详情
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4]
输出：0
示例 3：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 104
-105 <= nums[i] <= 105
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
代码
public class LeetCode581 {
public static void main(String[] args) {
System.out.println(new Solution().findUnsortedSubarray(new int[]{2, 6, 4, 8, 10, 9, 15}));
System.out.println(new Solution2().findUnsortedSubarray(new int[]{2, 6, 4, 8, 10, 9, 15}));
}
static class Solution {
public int findUnsortedSubarray(int[] nums) {
int l = nums.length, r = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
r = Math.max(r, j);
l = Math.min(l, i);
}
}
}
return r - l < 0 ? 0 : r - l + 1;
}
}
static class Solution2 {
public int findUnsortedSubarray(int[] nums) {
Stack<Integer> stack = new Stack<Integer>();
int l = nums.length, r = 0;
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
l = Math.min(l, stack.pop());
stack.push(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
r = Math.max(r, stack.pop());
stack.push(i);
}
return r - l > 0 ? r - l + 1 : 0;
}
}
}
LeetCode617 合并二叉树
题目详情
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
提示：
两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104
代码
public class LeetCode617 {
public static void main(String[] args) {
TreeNode.prettyPrintTree(new Solution().mergeTrees(
TreeNode.buildBinaryTree(new Integer[]{1, 3, 2, 5}),
TreeNode.buildBinaryTree(new Integer[]{2, 1, 3, null, 4, null, 7})));
}
/*
递归
*/
static class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
}
LeetCode621 任务调度器
题目详情
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例 1：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2：
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类
示例 3：
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：
1 <= task.length <= 104
tasks[i] 是大写英文字母
n 的取值范围为 [0, 100]
代码
public class LeetCode621 {
public static void main(String[] args) {
System.out.println(new Solution().leastInterval(new char[]{'A', 'A', 'A', 'B', 'B', 'B'}, 3));
System.out.println(new Solution2().leastInterval(new char[]{'A', 'A', 'A', 'B', 'B', 'B'}, 3));
System.out.println(new Solution3().leastInterval(new char[]{'A', 'A', 'A', 'B', 'B', 'B'}, 3));
}
/*
1、手下把最大的任务量排好，并列的最大按照最小间隔排好；
2、剩下的任务（出来最大的任务以及与最大并列的最后一个任务），需要插前边的空（不需要插最后一组后边的）；
3、假如空不够插，直接返回task长度，否则就是此时最后一个最大量任务的结束时间
*/
static class Solution {
public int leastInterval(char[] tasks, int n) {
int count[] = new int[26];
for (int i = 0; i < tasks.length; i++) {
count[tasks[i] - 'A']++;
}
Arrays.sort(count);
int max = count[25];
int numMax = 0;//与最大数并列的任务数
for (int i = 25; i >= 0; i--) {
if (max == count[i]) {
numMax++;
} else {
break;
}
}
//最大任务产生空隙：n*(max-1)
//需要插空的其他任务的数量task.length-max-(numMax-1)
return n * (max - 1) <= tasks.length - max - (numMax - 1) ? tasks.length : (n + 1) * (max - 1) + numMax;
}
}
/*
模拟
一种容易想到的方法是，我们按照时间顺序，依次给每一个时间单位分配任务。
那么如果当前有多种任务不在冷却中，那么我们应该如何挑选执行的任务呢？
直觉上，我们应当选择剩余执行次数最多的那个任务，将每种任务的剩余执行次数尽可能平均，
使得 CPU 处于待命状态的时间尽可能少。当然这也是可以证明的，详细证明见下一个小标题。
*/
static class Solution2 {
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> freq = new HashMap<Character, Integer>();
for (char ch : tasks) {
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
// 任务总数
int m = freq.size();
List<Integer> nextValid = new ArrayList<Integer>();
List<Integer> rest = new ArrayList<Integer>();
Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();
for (Map.Entry<Character, Integer> entry : entrySet) {
int value = entry.getValue();
nextValid.add(1);
rest.add(value);
}
int time = 0;
for (int i = 0; i < tasks.length; ++i) {
++time;
int minNextValid = Integer.MAX_VALUE;
for (int j = 0; j < m; ++j) {
if (rest.get(j) != 0) {
minNextValid = Math.min(minNextValid, nextValid.get(j));
}
}
time = Math.max(time, minNextValid);
int best = -1;
for (int j = 0; j < m; ++j) {
if (rest.get(j) != 0 && nextValid.get(j) <= time) {
if (best == -1 || rest.get(j) > rest.get(best)) {
best = j;
}
}
}
nextValid.set(best, time + n + 1);
rest.set(best, rest.get(best) - 1);
}
return time;
}
}
/*
构造
我们首先考虑所有任务种类中执行次数最多的那一种，记它为 A,的执行次数maxExeC
*/
static class Solution3 {
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> freq = new HashMap<Character, Integer>();
// 最多的执行次数
int maxExec = 0;
for (char ch : tasks) {
int exec = freq.getOrDefault(ch, 0) + 1;
freq.put(ch, exec);
maxExec = Math.max(maxExec, exec);
}
// 具有最多执行次数的任务数量
int maxCount = 0;
Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();
for (Map.Entry<Character, Integer> entry : entrySet) {
int value = entry.getValue();
if (value == maxExec) {
++maxCount;
}
}
return Math.max((maxExec - 1) * (n + 1) + maxCount, tasks.length);
}
}
}
LeetCode647 回文子串
题目详情
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000
s 由小写英文字母组成
代码
public class LeetCode647 {
public static void main(String[] args) {
System.out.println(new Solution().countSubstrings("aaa"));
System.out.println(new Solution2().countSubstrings("aaa"));
}
/*
中心拓展
*/
static class Solution {
public int countSubstrings(String S) {
int N = S.length(), ans = 0;
for (int center = 0; center <= 2 * N - 1; ++center) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < N && S.charAt(left) == S.charAt(right)) {
ans++;
left--;
right++;
}
}
return ans;
}
}
/*
Manacher 算法
*/
static class Solution2 {
public int countSubstrings(String s) {
int n = s.length();
StringBuffer t = new StringBuffer("$#");
for (int i = 0; i < n; ++i) {
t.append(s.charAt(i));
t.append('#');
}
n = t.length();
t.append('!');
int[] f = new int[n];
int iMax = 0, rMax = 0, ans = 0;
for (int i = 1; i < n; ++i) {
// 初始化 f[i]
f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
// 中心拓展
while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
++f[i];
}
// 动态维护 iMax 和 rMax
if (i + f[i] - 1 > rMax) {
iMax = i;
rMax = i + f[i] - 1;
}
// 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
ans += f[i] / 2;
}
return ans;
}
}
}
LeetCode739 每日温度
题目详情
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
代码
class LeetCode739 {
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution().dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
System.out.println(Arrays.toString(new Solution2().dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
System.out.println(Arrays.toString(new Solution3().dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
}
/*
暴力
*/
static class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length];
int[] next = new int[101];
Arrays.fill(next, Integer.MAX_VALUE);
for (int i = length - 1; i >= 0; --i) {
int warmerIndex = Integer.MAX_VALUE;
for (int t = temperatures[i] + 1; t <= 100; ++t) {
if (next[t] < warmerIndex) {
warmerIndex = next[t];
}
}
if (warmerIndex < Integer.MAX_VALUE) {
ans[i] = warmerIndex - i;
}
next[temperatures[i]] = i;
}
return ans;
}
}
/*
输入: temperatures = [73,74,75,71,69,72,76,73]
单调栈
可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。
如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
*/
static class Solution2 {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
//存储结果
int[] ans = new int[length];
//双端队列，作为队列时，add和remove方法，作为栈时，push和pop
Deque<Integer> stack = new LinkedList<Integer>();
for (int i = 0; i < length; i++) {
int temperature = temperatures[i];
//当栈不为空，且 当前温度大于栈顶温度
while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
//匹配成功，出栈并赋值
int prevIndex = stack.pop();
ans[prevIndex] = i - prevIndex;
}
//因为判断需要以后的元素，所以最后入栈
stack.push(i);
}
return ans;
}
}
static class Solution3 {
public int[] dailyTemperatures(int[] T) {
int[] ans = new int[T.length];
Stack<Integer> stack = new Stack();
for (int i = T.length - 1; i >= 0; --i) {
while (!stack.isEmpty() && T[i] >= T[stack.peek()]) stack.pop();
ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
stack.push(i);
}
return ans;
}
}
}
