【NO.1 字符串转化后的各位数字之和】
解题思路
循环 k 次加和即可。
代码展现
class Solution {
public int getLucky(String s, int k) {
String s2 = "";
for (int i = 0; i < s.length(); i++) {s2 += String.valueOf((int) (s.charAt(i) - 'a' + 1));
}
int result = 0;
for (int i = 0; i < k; i++) {
result = 0;
for (int j = 0; j < s2.length(); j++) {result += s2.charAt(j) - '0';
}
s2 = String.valueOf(result);
}
return result;
}}
【NO.2 子字符串渐变后可能失去的最大整数】
解题思路
贪婪，这个子串的终点要尽可能得靠左，并且渐变后肯定要变大。
代码展现
class Solution {
public String maximumNumber(String num, int[] change) {
StringBuilder result = new StringBuilder();
int status = 0;
for (int i = 0; i < num.length(); i++) {char oldChar = num.charAt(i);
char newChar = (char) (change[oldChar - '0'] + '0');
if (status == 2) { // status == 2 示意曾经完结了渐变，间接应用 oldChar
result.append(oldChar);
} else if (status == 1) { // status == 1 示意正在渐变，进行比照，决定是否完结渐变
if (oldChar <= newChar) {result.append(newChar);
} else {result.append(oldChar);
status = 2;
}
} else if (status == 0) { // status == 0 示意还没开始渐变，进行比照，决定是否开始渐变
if (oldChar < newChar) {result.append(newChar);
status = 1;
} else {result.append(oldChar);
}
}
}
return result.toString();}
}
【NO.3 最大兼容性评分和】
解题思路
回溯，枚举所有的可能性即可。
代码展现
class Solution {
int max;
public int maxCompatibilitySum(int[][] students, int[][] mentors) {
max = 0;
boolean[] vis = new boolean[mentors.length];
int[][] compat = new int[students.length][mentors.length];
for (int i = 0; i < students.length; i++) {for (int j = 0; j < mentors.length; j++) {for (int k = 0; k < students[0].length; k++) {if (students[i][k] == mentors[j][k]) {compat[i][j]++;
}
}
}
}
dfs(0, 0, compat, students.length, students[0].length, vis);
return max;}
void dfs(int stu, int sum, int[][] compat, int n, int m, boolean[] vis) {
max = Math.max(max, sum);
// 剪枝优化：若前面的学生每对儿都是最大匹配度，也不迭以后的最优解，则不必要再持续递归
if (stu == n || sum + (n - stu) * m <= max) {return;}
for (int i = 0; i < n; i++) {if (!vis[i]) {vis[i] = true;
dfs(stu + 1, sum + compat[stu][i], compat, n, m, vis);
vis[i] = false;
}
}}
}
【NO.4 删除零碎中的反复文件夹】
解题思路
Hash
文件目录零碎是树结构，为每棵子树计算哈希值，最初将哈希值雷同的子树删掉即可。
计算哈希的办法比拟多，最简略的能够间接转换成 JSON 字符串，然而效率略低。能够利用子节点的哈希值计算以后节点的哈希值，效率较高。
代码展现
class Solution {
static class Node {
boolean deleted;
int hash;
TreeMap<String, Node> children = new TreeMap<>();}
private final Node root;
private final Map<String, Integer> hash;
private final Map<Integer, Integer> count;
public Solution() {
root = new Node();
hash = new HashMap<>();
count = new HashMap<>();}
public void add(List<String> word) {
Node node = root;
for (String i : word) {if (!node.children.containsKey(i)) {Node child = new Node();
node.children.put(i, child);
}
node = node.children.get(i);
}}
private void calcHash(Node node) {
if (node.children.size() == 0) {
node.hash = 0;
return;
}
StringBuilder sb = new StringBuilder();
for (var child : node.children.navigableKeySet()) {Node childNode = node.children.get(child);
calcHash(childNode);
if (sb.length() != 0) {sb.append("/");
}
sb.append(childNode.hash);
sb.append(getHash(child));
}
node.hash = getHash(sb.toString());
count.put(node.hash, count.getOrDefault(node.hash, 0) + 1);}
private int getHash(String child) {
if (!hash.containsKey(child)) {hash.put(child, hash.size() + 1);
}
return hash.get(child);}
private void delete(Node node) {
for (var child : node.children.entrySet()) {delete(child.getValue());
}
if (count.getOrDefault(node.hash, 0) > 1) {node.deleted = true;}}
private List<List<String>> toList(Node node) {
List<List<String>> result = new LinkedList<>();
if (node != root) {result.add(new LinkedList<>());
}
if (node.children.size() == 0) {return result;}
for (var child : node.children.entrySet()) {if (child.getValue().deleted) {continue;}
List<List<String>> childList = toList(child.getValue());
for (var l : childList) {((LinkedList<String>) l).addFirst(child.getKey());
result.add(l);
}
}
return result;}
public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
for (var path : paths) {add(path);
}
calcHash(root);
delete(root);
return toList(root);}
}
杭州上岸算法网络科技有限公司
上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮忙学生更好的在待业市场中定位以及求职的公司。咱们以顶级的课程品质，高互动性的教学方式以及独特的小班教学模式来帮忙学生更快的跨过求职的鸿沟，用最高效，经济，正当的形式帮忙更多学生疾速找到梦寐以求的工作。