【 No.1 Maximum number of words that can be entered 】
Problem solving ideas to sign in, cycle traversal judgment can be.
The code shown
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 Added minimum number of steps]
The second sign-in problem, two to calculate the difference, need to judge whether it can be divisible.
The code shown
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 Maximum score after deduction 】
The idea of problem solving is coordinate type dynamic programming
DPI is the maximum return at the position of coordinate I and j
Normal coordinate conversion times out
So let’s say that for every j, it’s going to shift from the left and the right of j, and we only want the one that has the highest payoff
So when you go through j, you record the maximum payoff on the left and the maximum payoff on the right for the next layer
There is room for optimization, I can be compressed into two lines
The code shown
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]; Int j = 0; int j = 0; j < m; j++) { dp[0][j] = points[0][j]; } for (int i = 1; i < n; I++) {// For all the numbers to the left of the previous line, add its coordinates minus its own coordinates; // For all the numbers on the right-hand side of the previous row, we subtract its coordinates and add its own coordinates; 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 query the maximum gene difference 】
Binary dictionary tree: convert numbers into binary and record them in the dictionary tree
Build a tree for easy DFS
Every time a number is searched, the number is updated into the dictionary tree
Calculates the ultimate maximum XOR value on the dictionary tree
The code shown
class Trie {
Trie left; // 1 Trie right; // 0 int[] count = new int[2]; Public void insert(int val, int s) {public void insert(int val, int s) {int flag = (1 << 30); Trie node = this; while (flag > 0) { int bit = (flag & val); If (bit > 0) {if (node.left == null) {node.left = new Trie(); } node.count[1] += s; node = node.left; } else {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); If (bit > 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 (root, res, map, trie); 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); }}
Pay attention to our
Hangzhou Arrival Algorithm Network Technology Co. Ltd