狗家挂经

eejchen 发表于 2018-10-14 14:03
应该是HC挂的

这样啊，不是说一般match上team，过HC概率会大吗？看来都不一定~~楼主不要灰心，继续加油哈~

eejchen 发表于 2018-10-13 23:11
team就是说有自己这方和对手一方，跟下面一个同学说的BFS或者DFS找边界差不多，但是问题是他要求怎么样判 ...

那是不是bfs然后看被包围的有多少棋子然后根据包围的棋子数目看是不是差一个就可以kill

Junny69 发表于 2018-10-14 16:44
请问楼主什么时候onsite的

10.8号。。。。。

请问下楼主第三题怎么做的

JamesJi 发表于 2018-10-16 06:44
请问下楼主第三题怎么做的

其实我也不知道，我用的两个循环。。。

狗家一轮需要面两道题。lz可能做得有点慢， 所以就一轮面了一道

补充内容 (2018-10-15 19:51):
加油！

a_stray 发表于 2018-10-16 08:50
狗家一轮需要面两道题。lz可能做得有点慢， 所以就一轮面了一道

补充内容 (2018-10-15 19:51):

谢谢鼓励！

第三题给一个nlogn的思路，greedy，还得证明，代码量也好多，感觉面试的时候很难都写完啊。

1. /* return the minimum number of deletion and copy to get target String
   
2.          store the index of characters in source into index table
   
3.          replace target string with the its charactes's index in source string, and try to find as much as continuous increasing index as possible.
   
4.          To achieve that, we want to choose index as small as possible, however, need to be greater than previous char's index;
   
5.          1. O(n) process the index table
   
6.          2. for each character, O(log n) - binary search to find the smallest index that is greater than previous index, if no such index, assign the smallest index of current character
   
7.          3. rebuild answer list O(n)
   
8.          total: Time: O(n log n) Space: O(n)
   
9.          End case, no such character in source. return empty list
   
10.          AZAB -> ZBAZ
    
11.          i.e.
    
12.          1. get table
    
13.          A: 2
    
14.          Z: 0, 3
    
15.          B: 1
    
16.          2. assign index: 2,3,2,1
    
17.          3. find how many continuous increasing subArray
    
18.                  answer: [2,3],[2],[1]
    
19.          */
    
20.         public List<List<Integer>> canTransForm(String target, String source){
    
21.                 // assume only capital letter in target and source
    
22.                 if(target == null || source == null || target.length() == 0 || source.length() == 0){
    
23.                         return new ArrayList<>();
    
24.                 }
    
25.                
    
26.                 // init index table
    
27.                 Map<Character, List<Integer>> map = new HashMap<>();
    
28.                 for(int i = 0; i < source.length(); i++){
    
29.                         char c = source.charAt(i);
    
30.                         List<Integer> indexes = map.get(c);
    
31.                         if(indexes == null){
    
32.                                 indexes = new ArrayList<>();
    
33.                                 map.put(c, indexes);
    
34.                         }
    
35.                         indexes.add(i);
    
36.                 }
    
37.                
    
38.                 // init the target index array
    
39.                 int[] targetIdx = new int[target.length()];
    
40.                
    
41.                 for(int i = 0; i < target.length(); i++){
    
42.                         List<Integer> indexes = map.get(target.charAt(i));
    
43.                         if(indexes == null){
    
44.                                 return new ArrayList<>();
    
45.                         }else{
    
46.                                 // binary search index
    
47.                                 targetIdx[i] = find(indexes, i == 0 ? Integer.MAX_VALUE : targetIdx[i - 1]);
    
48.                         }
    
49.                 }
    
50.                
    
51.                 // build final result list               
    
52.                 return buildList(targetIdx);
    
53.         }
    
54.        
    
55.         // binary search smallest number that larger than i
    
56.         private int find(List<Integer> indexes, int i){
    
57.                 int l = 0;
    
58.                 int r = indexes.size() - 1;
    
59.                 while(l < r){
    
60.                         int mid = l + (r - l) / 2;
    
61.                         if(indexes.get(mid) <= i){
    
62.                                 l = mid + 1;
    
63.                         }else{
    
64.                                 r = mid;
    
65.                         }
    
66.                 }
    
67.                
    
68.                 if(indexes.get(l) <= i){
    
69.                         return indexes.get(0);
    
70.                 }else{
    
71.                         return indexes.get(l);
    
72.                 }
    
73.         }
    
74.        
    
75.         // build final list by count continuous increasing subArray
    
76.         private List<List<Integer>> buildList(int[] targetIdx){
    
77.                 List<List<Integer>> res = new ArrayList<>();
    
78.                 List<Integer> cur = new ArrayList<>();
    
79.                 cur.add(targetIdx[0]);
    
80.                 for(int i = 1; i < targetIdx.length; i++){
    
81.                         if(targetIdx[i] > targetIdx[i - 1]){
    
82.                                 cur.add(targetIdx[i]);
    
83.                         }else{
    
84.                                 res.add(cur);
    
85.                                 cur = new ArrayList<>();
    
86.                                 cur.add(targetIdx[i]);
    
87.                         }
    
88.                 }
    
89.                 if(cur.size() != 0){
    
90.                         res.add(cur);
    
91.                 }
    
92.                 return res;
    
93.         }

复制代码