上岸算法LeetCode Weekly Contest 287解题报告

上岸算法 · 发表于 2022-4-6 21:14:31

登录后可回复主题

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

x

【 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[1], loseCount.getOrDefault(m[1], 0) + 1);
   }
   List<Integer> res1 = new ArrayList<>();
   List<Integer> res2 = new ArrayList<>();
   for (var m : matches) {
         if (!loseCount.containsKey(m[0])) {
            res1.add(m[0]);
            loseCount.put(m[0], 2); // avoid duplicates
      }
         if (loseCount.getOrDefault(m[1], 0) == 1) {
            res2.add(m[1]);
            loseCount.put(m[1], 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[26];
   valToKey = new HashMap<>();
   for (int i = 0; i < keys.length; i++) {
         keyToVal[keys[i] - 'a'] = values[i];
         if (!valToKey.containsKey(values[i])) {
            valToKey.put(values[i], new ArrayList<>());
      }
         valToKey.get(values[i]).add(keys[i]);
   }
   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[word1.charAt(i) - 'a']);
   }
   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;
  }
}

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

[吹水聊天] 上岸算法LeetCode Weekly Contest 287解题报告

登录后可回复主题