狗家onsite 过经

dfs生成迷宫已经很厉害了,楼主还自己followup自己给增加了难度系数 orz

恭喜恭喜！又多了一个未来的国人面试官！

迷彩的瓜皮帽 发表于 2019-6-21 05:13
dfs生成迷宫已经很厉害了,楼主还自己followup自己给增加了难度系数 orz

层主才是大神啊。。。

可以问一下第一题怎么样能够达到o（n）吗？

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

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

Raymee 发表于 2019-6-22 16:56
我觉得可能需要先clarify一些问题吧，比如怎么样算是一个单词，有什么符号，是否有连续空格，即便楼主说 ...

这是我写的，也是o（m+n）复杂度

1. public class Main {
   
2.     public static void main(String[] args) {
   
3.         
   
4.         String s = "The quick brown fox jumps over a lazy dog.";
   
5.         List<seq>list = new ArrayList<>();
   
6.         list.add(new seq(16,"fox","catle"));
   
7.         list.add(new seq(4,"quick","slow"));
   
8.         System.out.println(replace(s,list));
   
9.     }
   
10.    
    
11.     public static String replace(String s,List<seq> list){
    
12.         Map<Integer,seq> map = new HashMap<>();
    
13.         int[] target = new int[s.length()];
    
14.         for(int i = 0; i<list.size(); i++){
    
15.             seq se = list.get(i);
    
16.             target[se.i] = i+1;
    
17.             map.put(i+1,se);
    
18.         }
    
19.         String res = "";
    
20.         int last = 0;
    
21.         int i = 0;
    
22.         while(i < target.length){
    
23.             if(target[i] != 0){
    
24.                 seq se= map.get(target[i]);
    
25.                 res+=s.substring(last,i)+se.n;
    
26.                 i+=se.o.length();
    
27.                 last = i;
    
28.             }else{
    
29.                 i++;
    
30.             }
    
31.         }
    
32.         if(last < s.length())
    
33.             res+=s.substring(last);
    
34.         return res;
    
35.     }
    
36. }
    
37. class seq{
    
38.         int i;
    
39.         String o;
    
40.         String n;
    
41.         seq(int i,String o, String n){
    
42.             this.i = i;
    
43.             this.o = o;
    
44.             this.n = n;
    
45.         }
    
46.     }

复制代码

blackarrow3542 发表于 2019/06/21 00:01:56


直接写dp应该可以。面试官只要求我用二维和1维dp了

请问一下楼主一维dp的意思就是把空间从n方优化成n吧？思路那些都一样吧

ymillyh 发表于 2019-6-25 13:20
请问一下楼主一维dp的意思就是把空间从n方优化成n吧？思路那些都一样吧

应该是，网上edit distance讨论很多。

很好的信息

请问生成迷宫的代码 在哪能找到