【 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