HOT 100（81~100）
前言
2023-7-2 10:44:12
推荐
337. 打家劫舍 III【中等】
打家劫舍 III
中等
1.7K
相关企业
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1: 输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7 示例 2: 输入: root = [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
树的节点数在 [1, 104] 范围内
0 <= 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 { Map<TreeNode,Integer> f=new HashMap<>();//选择结点o Map<TreeNode,Integer> g=new HashMap<>();//不选择结点o public int rob(TreeNode root) { dfs(root); return Math.max(f.getOrDefault(root,0),g.getOrDefault(root,0)); } public void dfs(TreeNode node){ if(node==null){ return; } dfs(node.left); dfs(node.right); //选择了o，就不能选择左 右孩子 f.put(node,node.val+g.getOrDefault(node.left,0)+g.getOrDefault(node.right,0)); //不选择o，可选择最大的（选择左||不选择左）+（选择右||不选择右） g.put(node,Math.max(f.getOrDefault(node.left,0),g.getOrDefault(node.left,0)) +Math.max(f.getOrDefault(node.right,0),g.getOrDefault(node.right,0))); } }
338. 比特位计数【简单】
338.比特位计数
简单
1.1K
相关企业
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1： 输入：n = 2 输出：[0,1,1] 解释： 0 --> 0 1 --> 1 2 --> 10 示例 2： 输入：n = 5 输出：[0,1,1,2,1,2] 解释： 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
提示：
0 <= n <= 105
进阶：
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
调用函数
class Solution { public int[] countBits(int n) { int[] count=new int[n+1]; for(int i=0;i<=n;i++){ count[i]=Integer.bitCount(i); } return count; } }
实现bitCount
class Solution { public int[] countBits(int n) { int[] count=new int[n+1]; for(int i=0;i<=n;i++){ count[i]=bitCount(i); } return count; } int bitCount(int i){ int count=0; while(i!=0){ if(i%2==1){ count++; } i/=2; } return count; } }
//Brian Kernighan 算法的原理是：对于任意整数 xxx，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」 public int countOnes(int x) { int ones = 0; while (x > 0) { x &= (x - 1); ones++; } return ones; }
347. 前 K 个高频元素【中等】
- 前 K 个高频元素
中等
1.6K
相关企业
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
Map排序
import java.util.Map.Entry; class Solution { public int[] topKFrequent(int[] nums, int k) { //统计 HashMap<Integer,Integer> map=new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i],map.getOrDefault(nums[i],0)+1); } Stream<Entry<Integer, Integer>> sorted = map.entrySet().stream().sorted(new Comparator<Entry<Integer, Integer>>() { @Override public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) { return o2.getValue() - o1.getValue(); } }); // sorted.forEach(t-> System.out.println(t.getKey()+" "+t.getValue())); int[] res=new int[k]; int c=0; ArrayList<Integer> list=new ArrayList<>(); sorted.limit(k).forEach(entry->list.add(entry.getKey())); for (Integer i : list) { res[c++]=i; } return res; } }
参考
堆（优先队列）
import java.util.Map.Entry; class Solution { public int[] topKFrequent(int[] nums, int k) { //统计 HashMap<Integer,Integer> map=new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i],map.getOrDefault(nums[i],0)+1); } //int[] 的第一个元素代表数组的值，第二个元素代表了改值出现的次数 PriorityQueue<int[]> queue=new PriorityQueue<int[]>(new Comparator<int[]>(){ public int compare(int[] m,int[] n){ return m[1]-n[1]; } }); for(Map.Entry<Integer,Integer> entry:map.entrySet()){ int num=entry.getKey(),count=entry.getValue(); //队列大小保持k个 if(queue.size()==k){ if(queue.peek()[1]<count){//小的话，逐出 添加当前 queue.poll(); queue.offer(new int[]{num,count}); } }else{//不到k个，直接添加 queue.offer(new int[]{num,count}); } } int[] res=new int[k]; for (int i=0;i<k;i++) { res[i]=queue.poll()[0]; } return res; } }
394. 字符串解码【中等】
字符串解码
中等
1.5K
相关企业
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1： 输入：s = "3[a]2[bc]" 输出："aaabcbc" 示例 2： 输入：s = "3[a2[c]]" 输出："accaccacc" 示例 3： 输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef" 示例 4： 输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"
提示：
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]
参考
栈
class Solution { int ptr; public String decodeString(String s) { LinkedList<String> stk=new LinkedList<>(); ptr=0; while(ptr<s.length()){ char cur=s.charAt(ptr); if(Character.isDigit(cur)){ //获取一个数字并进栈 String dights=getDights(s); stk.addLast(dights); }else if(Character.isLetter(cur)||cur=='['){ //获取一个字母进栈 stk.addLast(String.valueOf(s.charAt(ptr++))); }else{//有括号的情况 ++ptr; LinkedList<String> sub=new LinkedList<String>(); while(!"[".equals(stk.peekLast())){ sub.addLast(stk.removeLast()); } //逆序 Collections.reverse(sub); //左括号出栈 stk.removeLast(); //此时栈顶为当前sub对应的字符串应该出现的次数 int repTime=Integer.parseInt(stk.removeLast()); StringBuffer t=new StringBuffer(); String o=getString(sub); //构造字符串 while(repTime-->0){ t.append(o); } //将构造好的字符串入栈 stk.addLast(t.toString()); } } return getString(stk); } //数字编码可能不止1位 public String getDights(String s){ StringBuffer ret=new StringBuffer(); while(Character.isDigit(s.charAt(ptr))){ ret.append(s.charAt(ptr++)); } return ret.toString(); } //转换结果 public String getString(LinkedList<String> v) { StringBuffer ret = new StringBuffer(); for (String s : v) { ret.append(s); } return ret.toString(); } }
参考
递归
class Solution { String src; int ptr; public String decodeString(String s) { src=s; ptr=0; return getString(); } public String getString(){ if(ptr==src.length()||src.charAt(ptr)==']'){ //String->EPS return ""; } char cur=src.charAt(ptr); int repTime=1; String ret=""; if(Character.isDigit(cur)){ //String -> Digits [String] String //解析Digits repTime=getDights(); //过滤左括号 ++ptr; //解析String String str=getString(); //过滤有括号 ++ptr; //构造字符串 while(repTime-->0){ ret+=str; } }else if(Character.isLetter(cur)){ //Sting -> Char String //解析Char ret=String.valueOf(src.charAt(ptr++)); } return ret+getString(); } //数字编码可能不止1位 public int getDights(){ int ret=0; while(ptr<src.length()&&Character.isDigit(src.charAt(ptr))){ ret=ret*10+src.charAt(ptr++)-'0'; } return ret; } }
