[Leetcode Weekly Contest]258
2021/9/15 23:05:01
本文主要是介绍[Leetcode Weekly Contest]258,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链接:LeetCode
[Leetcode]2000. 反转单词前缀
给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ,反转 word 中从下标 0 开始、直到下标 i 结束(含下标 i )的那段字符。如果 word 中不存在字符 ch ,则无需进行任何操作。
例如,如果 word = "abcdefd" 且 ch = "d" ,那么你应该 反转 从下标 0 开始、直到下标 3 结束(含下标 3 )。结果字符串将会是 "dcbaefd" 。
返回 结果字符串 。
暴力即可。
class Solution { public String reversePrefix(String word, char ch) { for (int i=0; i<word.length(); i++) { if (word.charAt(i) == ch) return reverse(word.substring(0, i+1)) + word.substring(i+1, word.length()); } return word; } private String reverse(String word) { char[] arr = word.toCharArray(); int left = 0, right = arr.length-1; while (left < right) { char temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } return String.valueOf(arr); } }
[Leetcode]2001. 可互换矩形的组数
用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形,其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。
如果两个矩形 i 和 j(i < j)的宽高比相同,则认为这两个矩形 可互换 。更规范的说法是,两个矩形满足 widthi/heighti == widthj/heightj(使用实数除法而非整数除法),则认为这两个矩形 可互换 。
计算并返回 rectangles 中有多少对 可互换 矩形。
宽高比,我们可以直接算出来。但是直接用内建的高精度小数的话,很可能会被卡精度。
所以我们把宽高比化成有理数,即宽和高都除以他们的最大公约数。然后用一个hashmap去算同样宽高比的矩形的数量,再之后就转化成一个组合问题啦。
即宽高比相同的矩形有N个,那么他们组成多少个可互换对呢?
很显然,答案是 N*(N-1)/2
class Solution { private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public long interchangeableRectangles(int[][] arr) { Map<Long, Long> map = new HashMap<Long, Long>(); final long BASE = (long)1e8; for (var p : arr) { int a = p[0], b = p[1]; int div = gcd(a, b); // String frac = (a / div) + "/" + (b / div); // 使用数字压缩 [x, y] 比较快 long frac = (a / div) * BASE + (b / div); map.put(frac, map.getOrDefault(frac, 0L) + 1); } long res = 0L; for (var x : map.values()) { res += x * (x - 1) / 2; } return res; } }
[Leetcode]2002. 两个回文子序列长度的最大乘积
给你一个字符串 s ,请你找到 s 中两个 不相交回文子序列 ,使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符,则它们是 不相交 的。
请你返回两个回文子序列长度可以达到的 最大乘积 。
子序列 指的是从原字符串中删除若干个字符(可以一个也不删除)后,剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样,那么这个字符串是一个 回文字符串 。
看到2 <= s.length <= 12,就应该能想到状态压缩,通过状态压缩我们可以拿到所有的子序列,然后就判断乘积最大的最长子序列即可。总的来说,还是暴力求解,另外加了一些位运算。
class Solution { public int maxProduct(String s) { var total = getTotal(s); int n = total.size(); int res = 1, leng = s.length(); for(int i=0;i<n-1;++i){ for(int j=i+1;j<n;++j){ int num1 = (int)total.get(i), num2=(int)total.get(j); if(check(num1,num2,leng)){ res = Math.max(res,getNum(num1,leng)*getNum(num2,leng)); } } } return res; } public ArrayList getTotal(String s){ int n = s.length(); int m = 1<<n; ArrayList total = new ArrayList<Integer>(); for(int i=1;i<m;++i) { String tmp = ""; for(int ind=0;ind<n;++ind){ if((i&(1<<ind))!=0){ tmp += s.charAt(ind); } } if(getReverse(tmp)){ total.add(i); } } return total; } public int getNum(int num,int n) { int res = 0; for(int ind=0;ind<n;++ind) { if((num&(1<<ind))!=0){ res ++; } } return res; } public boolean check(int num1, int num2, int n) { for (int i=0;i<n;++i){ if((num1&(1<<i))!=0 && (num2&(1<<i))!=0){ return false; } } return true; } public boolean getReverse(String s){ int i=0,j=s.length()-1; while(i<=j) { if(s.charAt(i)!=s.charAt(j)){ return false; } i++; j--; } return true; } }
[Leetcode]2003. 每棵子树内缺失的最小基因值
有一棵根节点为 0 的 家族树 ,总共包含 n 个节点,节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents ,其中 parents[i] 是节点 i 的父节点。由于节点 0 是 根 ,所以 parents[0] == -1 。
总共有 105 个基因值,每个基因值都用 闭区间 [1, 105] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ,其中 nums[i] 是节点 i 的基因值,且基因值 互不相同 。
请你返回一个数组 ans ,长度为 n ,其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。
节点 x 为根的 子树 包含节点 x 和它所有的 后代 节点。
如果一棵子树里没有 1,显然这个子树的答案为 1。通过一次 dfs 找出子树内有没有 1 即可完成这一步。
注意到树上的基因值互不相同,因此有 1 的子树的根形成一条从节点 0 出发,到基因值为 1 的节点的链。接下来计算这条链上的答案即可.
显然链上以深度较浅的节点为根的子树,完全包含以深度较深的节点为根的子树。因此链上的节点的答案从深到浅一定是不降(non-decreasing)的。因此我们再一次通过 dfs,从深到浅遍历链上的节点,并维护以下变量:
变量 now:表示链上算出答案的节点中,答案最大是多少。
数组 vis:表示完成遍历的子树中出现过哪些数。
遍历节点 uu 时,首先递归计算同在链上的子节点 vv 的答案,然后遍历不在链上的子节点 ww,并将以 ww 为根的子树中的所有数加入 vis。最后不断递增 now 直到找到第一个 vis[now] 为 false 的数,即为 uu 的答案。
两次 dfs 复杂度均为 \(\mathcal{O}(n)\),now 的值只增不降且最大为 (n + 1),因此整体复杂度\(\mathcal{O}(n)\)。
class Solution { int n; int[] parent; int[] num; boolean[] exist; int[] ans; int p = 1; Map<Integer, List<Integer>> edges; public int[] smallestMissingValueSubtree(int[] parents, int[] nums) { n = nums.length; parent = parents; num = nums; exist = new boolean[n + 2]; ans = new int[n]; edges = new HashMap<>(); for (int i = 0; i < n; i++) { edges.putIfAbsent(parents[i], new ArrayList<>()); edges.get(parents[i]).add(i); } // 标记完后,计算出不含1的子树的答案都是1,此时含1的子树答案还是0 dfsAbout1(0); // 计算含1的子树的答案是多少 dfsAns(0); return ans; } boolean dfsAbout1(int root) { List<Integer> children = edges.get(root); boolean res = false; if (children != null) { for (int child : children) { res |= dfsAbout1(child); } } if (num[root] == 1) res = true; if (!res) { ans[root] = 1; } return res; } void dfsAns(int root) { List<Integer> children = edges.get(root); if (children != null) { // 先递归处理含1的子树 for (int child : children) { if (ans[child] != 1) { dfsAns(child); } } // 处理不含1的子树,记录当前子树内含有哪些整数 for (int child : children) { if (ans[child] == 1) { dfsAdd(child); } } } // 记录当前子树根节点的整数 exist[num[root]] = true; // 查找当前缺失的第一个整数 while (exist[p]) { p++; } ans[root] = p; } void dfsAdd(int root) { exist[num[root]] = true; List<Integer> children = edges.get(root); if (children != null) { for (int child : children) { dfsAdd(child); } } } }
Leetcode
这篇关于[Leetcode Weekly Contest]258的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25安卓NDK 是什么?-icode9专业技术文章分享
- 2024-12-25caddy 可以定义日志到 文件吗?-icode9专业技术文章分享
- 2024-12-25wordfence如何设置密码规则?-icode9专业技术文章分享
- 2024-12-25有哪些方法可以实现 DLL 文件路径的管理?-icode9专业技术文章分享
- 2024-12-25错误信息 "At least one element in the source array could not be cast down to the destination array-icode9专业技术文章分享
- 2024-12-25'flutter' 不是内部或外部命令,也不是可运行的程序 或批处理文件。错误信息提示什么意思?-icode9专业技术文章分享
- 2024-12-25flutter项目 as提示Cannot resolve symbol 'embedding'提示什么意思?-icode9专业技术文章分享
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享