【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; // 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);
}}
关注咱们
杭州上岸算法网络科技有限公司