META 电面

人很好的亚洲小哥上来就是两道题


1.163 要输出string
2.没见过 和这道题很像 https://www

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

到tree里，然后就是常规dfs 代码比较长结果没写完但小哥说on right track。估计要没但还是希望别杀我...........

我是一个来自中国大湾区的大哥，也是两道变种（哭了，为啥就我不是原题），是做出来了但也是提醒，加自我感觉不是bug free prefect

求求让过吧，大哥我给你积福

匿名用户 发表于 2024-11-2 22:33
想问一下楼主第一题要输出string是什么意思？

if only one number is missing represent it by that one missing number in string
if two numbers are missing represent them by number1,number2
if more than two numbers are missing represent it by number1-numbern

At the end connect all of them by a comma like 'number1, number2, number3-number4 ........'

匿名用户 发表于 2024-11-2 22:14
电面这么多code也太难顶了把。。

这么长主要这题我没见过问问题加讨论就已经十分钟了最后我也就有时间写一半。

店面这么复杂的题

链接里写得看起来太难受了，  ChatGPT的结果，显然不需要再遍历输入了，直接  DFS

1. class Solution {
   
2.     private TrieNode root = new TrieNode();
   
3. 
   
4.     // Function to insert a word into the trie
   
5.     public void insert(String word) {
   
6.         TrieNode node = root;
   
7.         for (char ch : word.toCharArray()) {
   
8.             node.children.putIfAbsent(ch, new TrieNode());
   
9.             node = node.children.get(ch);
   
10.             node.count++;
    
11.         }
    
12.     }
    
13. 
    
14.     // Function to find the shortest unique prefix for a word
    
15.     public String findPrefix(String word) {
    
16.         TrieNode node = root;
    
17.         StringBuilder prefix = new StringBuilder();
    
18.         for (char ch : word.toCharArray()) {
    
19.             prefix.append(ch);
    
20.             node = node.children.get(ch);
    
21.             if (node.count == 1) {
    
22.                 return prefix.toString();
    
23.             }
    
24.         }
    
25.         return word; // if no unique prefix, return the word itself
    
26.     }
    
27. 
    
28.     // Main function to find all shortest unique prefixes for a list of words
    
29.     public List<String> shortestUniquePrefixes(String[] words) {
    
30.         for (String word : words) {
    
31.             insert(word); // Insert each word into the trie
    
32.         }
    
33. 
    
34.         List<String> result = new ArrayList<>();
    
35.         for (String word : words) {
    
36.             result.add(findPrefix(word)); // Find and add the unique prefix
    
37.         }
    
38.         return result;
    
39.     }
    
40. }
    
41. 
    
42. class TrieNode {
    
43.     Map<Character, TrieNode> children = new HashMap<>();
    
44.     int count; // count occurrences of words passing through this node
    
45. }

复制代码

1. class Solution {
   
2.     private TrieNode root = new TrieNode();
   
3. 
   
4.     // Function to insert a word into the trie
   
5.     public void insert(String word) {
   
6.         TrieNode node = root;
   
7.         for (char ch : word.toCharArray()) {
   
8.             node.children.putIfAbsent(ch, new TrieNode());
   
9.             node = node.children.get(ch);
   
10.             node.count++;
    
11.         }
    
12.     }
    
13. 
    
14.     // Function to find the shortest unique prefix for a word
    
15.     public String findPrefix(String word) {
    
16.         TrieNode node = root;
    
17.         StringBuilder prefix = new StringBuilder();
    
18.         for (char ch : word.toCharArray()) {
    
19.             prefix.append(ch);
    
20.             node = node.children.get(ch);
    
21.             if (node.count == 1) {
    
22.                 return prefix.toString();
    
23.             }
    
24.         }
    
25.         return word; // if no unique prefix, return the word itself
    
26.     }
    
27. 
    
28.     public void findUniquePrefixes(TrieNode node, StringBuilder prefix, List<String> result) {
    
29.         if (node == null) return;
    
30.         
    
31.         // If this node is end of a word and count is 1, it's a unique prefix
    
32.         if (node.count == 1) {
    
33.             result.add(prefix.toString());
    
34.             return;
    
35.         }
    
36.         
    
37.         // Recur for all children
    
38.         for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
    
39.             prefix.append(entry.getKey());
    
40.             findUniquePrefixes(entry.getValue(), prefix, result);
    
41.             prefix.deleteCharAt(prefix.length() - 1); // Backtrack
    
42.         }
    
43.     }
    
44.     // Main function to find all shortest unique prefixes for a list of words
    
45.     public List<String> shortestUniquePrefixes(String[] words) {
    
46.         for (String word : words) {
    
47.             insert(word); // Insert each word into the trie
    
48.         }
    
49. 
    
50.         List<String> result = new ArrayList<>();
    
51.         StringBuilder sb = new StringBuilder();
    
52.         findUniquePrefixes(root, sb, result);
    
53.         return result;
    
54.     }
    
55. }
    
56. 
    
57. class TrieNode {
    
58.     Map<Character, TrieNode> children = new HashMap<>();
    
59.     int count; // count occurrences of words passing through this node
    
60. }

复制代码

Falldawn 发表于 2024-11-2 19:58
链接里写得看起来太难受了，  ChatGPT的结果，显然不需要再遍历输入了，直接  DFS

电面这么多code也太难顶了把。。

想问一下楼主第一题要输出string是什么意思？

Falldawn 发表于 2024-11-2 20:58
链接里写得看起来太难受了，  ChatGPT的结果，显然不需要再遍历输入了，直接  DFS

这么长主要这题我没见过问问题加讨论就已经十分钟了最后我也就有时间写一半。

Ezhao1995 发表于 2024-11-02 22:38:34
这么长主要这题我没见过问问题加讨论就已经十分钟了最后我也就有时间写一半。

是不是可以sort一下然后只比较相邻的，