617. 合并二叉树【简单】
617.合并二叉树
简单
1.2K
相关企业
给你两棵二叉树： 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
递归
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1==null){ return root2; } if (root2==null){ return root1; } root1.val+=root2.val; root1.left=mergeTrees(root1.left,root2.left); root1.right=mergeTrees(root1.right,root2.right); return root1; } }
621. 任务调度器【中等】
任务调度器
中等
1.2K
相关企业
给你一个用字符数组 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]
参考
class Solution { 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>(); //rest表示其剩余执行次数 List<Integer> rest=new ArrayList<>(); 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);//time更新 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; } }
官方
class Solution { 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); } }
647. 回文子串【中等】
647.回文子串
提示
中等
1.2K
相关企业
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1： 输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c" 示例 2： 输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000
s 由小写英文字母组成
官方
class Solution { //中心拓展 public int countSubstrings(String s) { int n = s.length(), ans = 0; for (int i = 0; i < 2 * n - 1; ++i) { int l = i / 2, r = i / 2 + i % 2; while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { --l; ++r; ++ans; } } return ans; } }
自己
class Solution { //中心扩展 int count=0; public int countSubstrings(String s) { char[] chars = s.toCharArray(); int len=chars.length; for(int i=0;i<len;i++){ substrings(chars,i,i); if(i+1<len&&chars[i]==chars[i+1]){ substrings(chars,i,i+1); } } return count; } //统计回文子串的长度 public void substrings(char[] chars,int left,int right){ count++; int len=chars.length; int i=left; int j=right; while(i-1>=0&&j+1<len&&chars[i-1]==chars[j+1]){ count++; i--; j++; } } }
739. 每日温度【中等】
739.每日温度
提示
中等
1.5K
相关企业
给定一个整数数组 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 Solution { //单调栈 public int[] dailyTemperatures(int[] temperatures) { int len= temperatures.length; int[] ans=new int[len]; Deque<Integer> stack=new LinkedList<>(); for (int i = 0; i < len; i++) { while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){ int preIndex=stack.pop(); ans[preIndex]=i-preIndex; } stack.push(i); } return ans; } }
最后
2023-7-2 10:59:37
