399. 除法求值【中等】
399.除法求值
提示
中等
953
相关企业
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
示例 1： 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000] 解释： 条件：a / b = 2.0, b / c = 3.0 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ] 示例 2： 输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] 输出：[3.75000,0.40000,5.00000,0.20000] 示例 3： 输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] 输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj 由小写英文字母与数字组成
官方
并查集
import java.util.HashMap; import java.util.List; import java.util.Map; public class Solution { public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { int equationsSize = equations.size(); UnionFind unionFind = new UnionFind(2 * equationsSize); // 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码 Map<String, Integer> hashMap = new HashMap<>(2 * equationsSize); int id = 0; for (int i = 0; i < equationsSize; i++) { List<String> equation = equations.get(i); String var1 = equation.get(0); String var2 = equation.get(1); if (!hashMap.containsKey(var1)) { hashMap.put(var1, id); id++; } if (!hashMap.containsKey(var2)) { hashMap.put(var2, id); id++; } unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]); } // 第 2 步：做查询 int queriesSize = queries.size(); double[] res = new double[queriesSize]; for (int i = 0; i < queriesSize; i++) { String var1 = queries.get(i).get(0); String var2 = queries.get(i).get(1); Integer id1 = hashMap.get(var1); Integer id2 = hashMap.get(var2); if (id1 == null || id2 == null) { res[i] = -1.0d; } else { res[i] = unionFind.isConnected(id1, id2); } } return res; } private class UnionFind { private int[] parent; /** * 指向的父结点的权值 */ private double[] weight; public UnionFind(int n) { this.parent = new int[n]; this.weight = new double[n]; for (int i = 0; i < n; i++) { parent[i] = i; weight[i] = 1.0d; } } public void union(int x, int y, double value) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } parent[rootX] = rootY; // 关系式的推导请见「参考代码」下方的示意图 weight[rootX] = weight[y] * value / weight[x]; } /** * 路径压缩 * * @param x * @return 根结点的 id */ public int find(int x) { if (x != parent[x]) { int origin = parent[x]; parent[x] = find(parent[x]); weight[x] *= weight[origin]; } return parent[x]; } public double isConnected(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return weight[x] / weight[y]; } else { return -1.0d; } } } }
406. 根据身高重建队列【中等】
406.根据身高重建队列
提示
中等
1.6K
相关企业
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1： 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。 示例 2： 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
题目数据确保队列可以被重建
参考
数组排序
class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, new Comparator<int[]>() { @Override public int compare(int[] person1, int[] person2) { if(person1[0]==person2[0]){ return person1[1]-person2[1]; } return person2[0]-person1[0]; } }); List<int[]> ans=new ArrayList<>(); for(int[] person:people){ ans.add(person[1], person); } return ans.toArray(new int[ans.size()][]); } }
416. 分割等和子集【中等】
416.分割等和子集
中等
1.8K
相关企业
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
参考
动态规划
class Solution { public boolean canPartition(int[] nums) { int len= nums.length; int sum=0; for (int i : nums) { sum += i; } if((sum&1)==1){ return false; } int target=sum/2; boolean[][] dp=new boolean[len][target+1]; if (nums[0]<=target){ dp[0][nums[0]]=true; } for (int i = 1; i < len; i++) { for (int j = 0; j <=target; j++) { dp[i][j]=dp[i-1][j]; if(nums[i]==j){ dp[i][j]=true; continue; } if(nums[i]<j){ dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]; } } if(dp[i][target]){ return true; } } return dp[nums.length-1][sum/2]; } }
437. 路径总和 III【中等】
437.路径总和 III
中等
1.6K
相关企业
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1： 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。 示例 2： 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
提示:
二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000
参考
递归
class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) { return 0; } int ret = rootSum(root, targetSum); ret += pathSum(root.left, targetSum); ret += pathSum(root.right, targetSum); return ret; } public int rootSum(TreeNode root, long targetSum) { int ret = 0; if (root == null) { return 0; } int val = root.val; if (val == targetSum) { ret++; } ret += rootSum(root.left, targetSum - val); ret += rootSum(root.right, targetSum - val); return ret; } }
参考
前缀和
class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) { return 0; } int ret = rootSum(root, targetSum); ret += pathSum(root.left, targetSum); ret += pathSum(root.right, targetSum); return ret; } public int rootSum(TreeNode root, long targetSum) { int ret = 0; if (root == null) { return 0; } int val = root.val; if (val == targetSum) { ret++; } ret += rootSum(root.left, targetSum - val); ret += rootSum(root.right, targetSum - val); return ret; } }
438. 找到字符串中所有字母异位词【中等】
438.找到字符串中所有字母异位词
中等
1.2K
相关企业
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
官方
class Solution { public List<Integer> findAnagrams(String s, String p) { int sLen = s.length(), pLen = p.length(); if (sLen < pLen) { return new ArrayList<Integer>(); } List<Integer> ans = new ArrayList<Integer>(); int[] sCount = new int[26]; int[] pCount = new int[26]; for (int i = 0; i < pLen; ++i) { ++sCount[s.charAt(i) - 'a']; ++pCount[p.charAt(i) - 'a']; } if (Arrays.equals(sCount, pCount)) { ans.add(0); } for (int i = 0; i < sLen - pLen; ++i) { --sCount[s.charAt(i) - 'a']; ++sCount[s.charAt(i + pLen) - 'a']; if (Arrays.equals(sCount, pCount)) { ans.add(i + 1); } } return ans; } }
超限
class Solution { public List<Integer> findAnagrams(String s, String p) { //滑动窗口 窗口长度固定 p.length List<Integer> list=new ArrayList<>(); int n=s.length(); int start=0; int end=p.length()-1; while (end<n){ //如果是异位词 String ss=s.substring(start,end+1); if (yiwei(ss,p)){ list.add(start); } //窗口长度固定 start++; end++; } return list; } private static boolean yiwei(String s, String p) { char[] chars = s.toCharArray(); char[] charp = p.toCharArray(); Arrays.sort(chars); Arrays.sort(charp); for (int i = 0; i < chars.length; i++) { if (chars[i]!=charp[i]){ return false; } } return true; } }
桶异位
class Solution { public List<Integer> findAnagrams(String s, String p) { //用桶来判断异位 int []pTon =new int[26]; for (int i = 0; i < p.length(); i++) { ++pTon[p.charAt(i)-'a']; } //滑动窗口 窗口长度固定 p.length List<Integer> list=new ArrayList<>(); int n= s.length(); int start=0; int end= p.length()-1; while (end<n){ //如果是异位词 String ss= s.substring(start,end+1); int []ssTon =new int[26]; for (int i = 0; i < p.length(); i++) { ++ssTon[ss.charAt(i)-'a']; } if (compare(ssTon,pTon)){ list.add(start); } //窗口长度固定 start++; end++; } return list; } private static boolean compare(int[] ssTon, int[] pTon) { for (int i = 0; i < ssTon.length; i++) { if (ssTon[i]!=pTon[i]){ return false; } } return true; } }
评论
class Solution { public List<Integer> findAnagrams(String s, String p) { //变长窗口版本。diff也可以不预先统计，将它转变为遍历s的时候一种“消耗品”——当“消耗品”不足， // 唯一可以做的就是移动左窗口释放一些出来。 // 这里面有一个比较特殊的corner case，s中有一个p中没有的字符。下面的代码刚好自洽： int[] cnt = new int[128]; for (char c : p.toCharArray()) cnt[c]++; int lo = 0, hi = 0; List<Integer> res = new ArrayList<>(); while (hi < s.length()) { if (cnt[s.charAt(hi)] > 0) { cnt[s.charAt(hi++)]--; if (hi - lo == p.length()) res.add(lo); } else { cnt[s.charAt(lo++)]++; } } return res; } }
