124. 二叉树中的最大路径和【困难】
124.二叉树中的最大路径和
困难
2K
相关企业
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1： 输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 示例 2： 输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000
参考
递归
/** * 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 { int maxSum=Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } public int maxGain(TreeNode node){ if(node==null){ return 0; } // 递归计算左右子节点的最大贡献值 // 只有在最大贡献值大于 0 时，才会选取对应子节点 int leftGain=Math.max(maxGain(node.left),0); int rightGain=Math.max(maxGain(node.right),0); // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值 int priceNewpath=node.val+leftGain+rightGain; // 更新答案 maxSum=Math.max(maxSum,priceNewpath); // 返回节点的最大贡献值 return node.val+Math.max(leftGain,rightGain); } }
128. 最长连续序列【中等】
128.最长连续序列
中等
1.7K
相关企业
给定一个未排序的整数数组 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
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
参考
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> num_set=new HashSet<>(); for(int num:nums){ num_set.add(num); } int longestStreak=0; for(int num:num_set){ //只有当一个数是连续序列的第一个数的情况下才会进入内层循环 if(!num_set.contains(num-1)){ int currentNum=num; int currentStreak=1; //内层循环中匹配连续序列中的数 while(num_set.contains(currentNum+1)){ currentNum+=1; currentStreak+=1; } longestStreak=Math.max(longestStreak,currentStreak); } } return longestStreak; } }
136. 只出现一次的数字【简单】
136.只出现一次的数字
简单
2.9K
相关企业
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ： 输入：nums = [2,2,1] 输出：1 示例 2 ： 输入：nums = [4,1,2,1,2] 输出：4 示例 3 ： 输入：nums = [1] 输出：1
提示：
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次。
异或
class Solution { public int singleNumber(int[] nums) { int single = 0; for (int num : nums) { single ^= num; } return single; } }
哈希表
class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (map.containsKey(num)){ map.remove(num); } else { map.put(num, 1); } } Set<Integer> set = map.keySet(); Iterator<Integer> iterator = set.iterator(); return iterator.next(); } }
139. 单词拆分【中等】
139.单词拆分
中等
2.2K
相关企业
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1： 输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。 示例 2： 输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。 示例 3： 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同
官方
public class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> wordDictSet = new HashSet(wordDict); boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordDictSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[s.length()]; } }
141. 环形链表【简单】
141.环形链表
简单
1.9K
相关企业
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
快慢指针
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { ListNode low=head; ListNode fast=head; while(fast!=null&&fast.next!=null){ low=low.next; fast=fast.next.next; if(low==fast){ return true; } } return false; } }
