LeetCode Weekly Contest 250解题报告

上岸算法 · 发表于 2021-7-19 18:02:58

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

关注我们：杭州上岸算法网络科技有限公司
【 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 扣分后的最大得分】

解题思路
坐标型动态规划

dp[i][j]表示处于坐标 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;    // 1
Trie right;    // 0
int[] 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);
}
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] LeetCode Weekly Contest 250解题报告

登录后可回复主题