OCI店面挂经

今天店面，是infra data组
上来聊经历，半个小时。然后做一题，题目是
一个file里有重

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

fs recursion。楼主刷题少在LC没有见过原题。

方便細說一下dfs recursion怎麼用嗎

DFS的话也许是用Trie Tree？如果段落只有后几个词不同的话，这个方法还可以

求指正 求加米

1. public class CompressFile {
   
2.     @Test
   
3.     public void test0() {
   
4.         String[] lines = {"123 456 789", "987 654 321"};
   
5.         Util util = new Util();
   
6.         util.compress(lines);
   
7.         assertArrayEquals(lines, util.depress());
   
8.     }
   
9.     @Test
   
10.     public void test1() {
    
11.         String[] lines = {"123 456 789", "123 456"};
    
12.         Util util = new Util();
    
13.         util.compress(lines);
    
14.         assertArrayEquals(lines, util.depress());
    
15.     }
    
16. 
    
17.     private class Util {
    
18.         int size = 0;
    
19.         Trie trie = new Trie();
    
20. 
    
21.         public String[] depress() {
    
22.             String[] res = new String[size];
    
23.             for (int i = 0; i < size; ++i) {
    
24.                 res = trie.get(i);
    
25.             }
    
26.             return res;
    
27.         }
    
28. 
    
29.         public void compress(String[] lines) {
    
30.             size = lines.length;
    
31.             for (int i = 0; i < lines.length; ++i) {
    
32.                 trie.insert(i, lines);
    
33.             }
    
34.         }
    
35.     }
    
36. 
    
37.     private class TrieNode {
    
38.         // line # - next word's node
    
39.         Map<Integer, TrieNode> map = new HashMap<>();
    
40.         String word;
    
41. 
    
42.         TrieNode(String word) {
    
43.             this.word = word;
    
44.         }
    
45.     }
    
46. 
    
47.     private class Trie {
    
48.         TrieNode root = new TrieNode(null);
    
49. 
    
50.         void insert(int index, String[] lines) {
    
51.             String line = lines[index];
    
52.             String[] words = line.split(" ");
    
53.             TrieNode curr = root;
    
54.             TrieNode next = null;
    
55.             for (String word : words) {
    
56.                 // get next word in this line
    
57.                 next = curr.map.getOrDefault(index, new TrieNode(word));
    
58.                 curr.map.put(index, next);
    
59.                 curr = next;
    
60.             }
    
61.         }
    
62. 
    
63.         String get(int index) {
    
64.             List<String> list = new ArrayList<>();
    
65.             TrieNode node = root;
    
66.             while (node.map.containsKey(index)) {
    
67.                 TrieNode next = node.map.get(index);
    
68.                 list.add(next.word);
    
69.                 node = next;
    
70.             }
    
71.             return String.join(" ", list);
    
72.         }
    
73.     }
    
74. }

复制代码

landy622 发表于 2020-8-31 15:34
DFS的话也许是用Trie Tree？如果段落只有后几个词不同的话，这个方法还可以

求指正 求加米

请忽略上文 似乎不太对我再想想

这个是不是压缩的时候可以用Trie然后在每个单词结尾的时候记录它的index。index就是二维的。行数和具体的空格切割的index
然后解压缩的时候可以直接通过trie decode？

Black Liu 发表于 2020-9-15 13:03
这个是不是压缩的时候可以用Trie然后在每个单词结尾的时候记录它的index。index就是二维的。行数和具体的空 ...

思路是对的