上岸算法LeetCode Weekly Contest 287解题报告
【 NO.1 转化时间需要的最少操作数】解题思路
将时间转换为分钟数更有利于算术运算。
代码展示
class Solution {
public int convertTime(String current, String correct) {
int cur = toMinutes(current);
int cor = toMinutes(correct);
if (cor < cur) { // 第二天，将 cor 加 24 小时
cor += 24 * 60;
}
int diff = cor - cur;
int cnt60 = diff / 60;
diff %= 60;
int cnt15 = diff / 15;
diff %= 15;
int cnt5 = diff / 5;
diff %= 5;
return cnt60 + cnt15 + cnt5 + diff;
}
private int toMinutes(String time) {
return Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
}
}
【 NO.2 找出输掉零场或一场比赛的玩家】
解题思路
使用一个 Map 维护每个玩家输掉了几场比赛即可。
代码展示
class Solution {
public List<List<Integer>> findWinners(int[][] matches) {
Map<Integer, Integer> loseCount = new HashMap<>();
for (var m : matches) {
loseCount.put(m, loseCount.getOrDefault(m, 0) + 1);
}
List<Integer> res1 = new ArrayList<>();
List<Integer> res2 = new ArrayList<>();
for (var m : matches) {
if (!loseCount.containsKey(m)) {
res1.add(m);
loseCount.put(m, 2); // avoid duplicates
}
if (loseCount.getOrDefault(m, 0) == 1) {
res2.add(m);
loseCount.put(m, 2); // avoid duplicates
}
}
Collections.sort(res1);
Collections.sort(res2);
return List.of(res1, res2);
}
}
【 NO.3 每个小孩最多能分到多少糖果】
解题思路
典型的二分答案题目。
代码展示
class Solution {
public int maximumCandies(int[] candies, long k) {
int l = 0, r = Arrays.stream(candies).max().getAsInt();
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid, candies, k)) {
l = mid;
} else {
r = mid;
}
}
return check(r, candies, k) ? r : l;
}
private boolean check(int r, int[] candies, long k) {
for (int c : candies) {
k -= c / r;
}
return k <= 0;
}
}
【 NO.4 加密解密字符串】
解题思路
使用 Map 储存 keys 和 values 的映射，即可完成加密。
解密需要借助 Trie 树判断当前解密的字符串分支 (因为一个密文可能对应多种明文) 是否属于 dictionary
代码展示
class Encrypter {
char[] keys;
String[] values;
String[] dictionary;
String[] keyToVal;
Map<String, List<Character>> valToKey;
Trie dictTrie;
static class Trie {
public Trie() {
root = new Trie.Node();
}
public void add(String word) {
Trie.Node node = root;
for (var i : word.toCharArray()) {
if (!node.children.containsKey(i)) {
node.children.put(i, new Trie.Node());
}
node = node.children.get(i);
}
node.isWord = true;
}
public boolean containsWord(String word) {
Trie.Node node = root;
for (var i : word.toCharArray()) {
if (!node.children.containsKey(i)) {
return false;
}
node = node.children.get(i);
}
return node.isWord;
}
public final Trie.Node root;
static class Node {
boolean isWord;
Map<Character, Trie.Node> children;
public Node() {
this.isWord = false;
this.children = new HashMap<>();
}
}
}
public Encrypter(char[] keys, String[] values, String[] dictionary) {
this.keys = keys;
this.values = values;
this.dictionary = dictionary;
keyToVal = new String;
valToKey = new HashMap<>();
for (int i = 0; i < keys.length; i++) {
keyToVal - 'a'] = values;
if (!valToKey.containsKey(values)) {
valToKey.put(values, new ArrayList<>());
}
valToKey.get(values).add(keys);
}
dictTrie = new Trie();
for (String s : dictionary) {
dictTrie.add(s);
}
}
public String encrypt(String word1) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < word1.length(); i++) {
builder.append(keyToVal);
}
return builder.toString();
}
public int decrypt(String word2) {
return decrypt(word2, dictTrie.root);
}
final private List<Character> emptyList = new ArrayList<>();
private int decrypt(String word2, Trie.Node node) {
if (word2.length() == 0) {
return node.isWord ? 1 : 0;
}
if (!valToKey.containsKey(word2.substring(0, 2))) {
return 0;
}
var cand = valToKey.get(word2.substring(0, 2));
int res = 0;
for (var c : cand) {
if (node.children.containsKey(c)) {
res += decrypt(word2.substring(2), node.children.get(c));
}
}
return res;
}
}
页:
[1]