【 NO.1 能够输出的最大单词数】
解题思路
签到题，循环遍历判断即可。
代码展现
class Solution {
public int canBeTypedWords(String text, String brokenLetters) { if (text == null || text.length() == 0) { return 0; } String[] texts = text.split(" "); Set<Character> set = new HashSet<>(); for (char c : brokenLetters.toCharArray()) { set.add(c); } int ans = 0, flag = 0; for (String word : texts) { for (char c : word.toCharArray()) { if (set.contains(c)) { flag = 1; break; } } if (flag == 0) { ans++; } flag = 0; } return ans;}}
【 NO.2 新增的起码台阶数】
解题思路
第二道签到题，两两计算差值，须要判断一下是否能够整除。
代码展现
class Solution {
public int addRungs(int[] rungs, int dist) { if (rungs == null || rungs.length == 0) { return 0; } int ans = 0; int preRun = 0; for (int rung : rungs) { int diff = rung - preRun; // 整除的状况可梯子少一个 if (diff % dist == 0) { ans += diff / dist - 1; } else { ans += diff / dist; } preRun = rung; } return ans;}}
【 NO.3 扣分后的最大得分】
解题思路
坐标型动静布局
dpi示意处于坐标 i j 的地位的最大收益
一般的坐标转化会超时
思考针对每一个j,会从 j的左侧和右侧转移过去，咱们只想要一个收益最大的
因而在遍历 j 的时候记录这个左侧和右侧最大的收益，给下一层用
还有优化的空间，i 能够压缩成两行
代码展现
class Solution {
public long maxPoints(int[][] points) { if (points == null || points.length == 0 || points[0].length == 0) { return 0; } int n = points.length; int m = points[0].length; long[][] dp = new long[n][m]; // 首行初始化 for (int j = 0; j < m; j++) { dp[0][j] = points[0][j]; } for (int i = 1; i < n; i++) { // 对于所有上一行右边的数，都是加上它的坐标减去本人的坐标； // 对于上一行所有左边的数，都是减去它的坐标加上本人的坐标； long leftMax = Integer.MIN_VALUE; long rightMax = Integer.MIN_VALUE; for (int j = 0; j < m; j++) { leftMax = Math.max(leftMax, dp[i - 1][j] + j); rightMax = Math.max(rightMax, dp[i - 1][m - 1 - j] - (m - 1 - j)); dp[i][j] = Math.max(dp[i][j], points[i][j] + leftMax - j); dp[i][m - 1 - j] = Math.max(dp[i][m - 1 - j], points[i][m - 1 - j] + rightMax + m - 1 - j); } } long ans = 0; for (int j = 0; j < m; j++) { ans = Math.max(ans, dp[n - 1][j]); } return ans;}}
【 NO.4 查问最大基因差】
解题思路
二进制的字典树：将数字转化成二进制记录在字典树当中
构建树，不便做DFS
每搜寻一个数字，将该数字更新到字典树当中
在字典树上计算最终最大的异或值
代码展现
class Trie {
Trie left; // 1Trie right; // 0int[] count = new int[2];public Trie() {}// s == 1 增加， s == -1 删除public void insert(int val, int s) { int flag = (1 << 30); Trie node = this; while (flag > 0) { int bit = (flag & val); if (bit > 0) { // 1 走右边 if (node.left == null) { node.left = new Trie(); } node.count[1] += s; node = node.left; } else { // 0 走左边 if (node.right == null) { node.right = new Trie(); } node.count[0] += s; node = node.right; } flag >>>= 1; }}public int getMax(int val) { Trie node = this; int flag = (1 << 30); int res = 0; while (flag > 0) { int bit = (flag & val); // 贪婪算法，1 的话走左边，0 的话走右边 if (bit > 0) { // 走左边，左边不行走右边 if (node.right != null && node.count[0] > 0 ) { node = node.right; res |= flag; } else if (node.left != null && node.count[1] > 0) { node = node.left; } else { return -1; } } else { // 优先走右边 if (node.left != null && node.count[1] > 0) { node = node.left; res |= flag; } else if (node.right != null && node.count[0] > 0) { node = node.right; } else { return -1; } } flag >>>= 1; } return res;}}
public class Solution2 {
static class TreeNode { List<TreeNode> son = new ArrayList<>(); int val; public TreeNode(int val) { this.val = val; }}Map<Integer, List<int[]>> map = new HashMap<>();Trie trie;public int[] maxGeneticDifference(int[] parents, int[][] queries) { int n = parents.length, m = queries.length; // 封装查问的信息 for (int i = 0; i < m; i++) { int node = queries[i][0], val = queries[i][1]; if (!map.containsKey(node)) { map.put(node, new ArrayList<>()); } map.get(node).add(new int[]{val, i}); } Map<Integer, TreeNode> nodeMap = new HashMap<>(); // 构建树 TreeNode root = null; for (int i = 0; i < parents.length; i++) { int p = parents[i]; if (!nodeMap.containsKey(i)) { nodeMap.put(i, new TreeNode(i)); } if (p != -1) { if (!nodeMap.containsKey(p)) { nodeMap.put(p, new TreeNode(p)); } nodeMap.get(p).son.add(nodeMap.get(i)); } else { root = nodeMap.get(i); } } trie = new Trie(); int[] res = new int[m]; // 在树上进行DFS dfs(root, res, map, trie); return res;}private void dfs(TreeNode root, int[] res, Map<Integer, List<int[]>> map, Trie t) { if (root == null) { return; } t.insert(root.val, 1); if (map.containsKey(root.val)) { for (int[] each : map.get(root.val)) { int idx = each[1], v = each[0]; res[idx] = t.getMax(v); } } for (TreeNode s : root.son) { dfs(s, res, map, t); } // delete t.insert(root.val, -1);}}
关注咱们
杭州上岸算法网络科技有限公司