Google MTV 20160921 onsite.

搭车同求最大假期。。。马克

最大假期问题，我按照我的理解写了一段测试代码，欢迎评论：

1. class City(object):
   
2.     def __init__(self, id, dstcity, weekholidays):
   
3.         self.cityid = id
   
4.         # key:city_id,value-distance to the destination
   
5.         self.dstcity = dstcity
   
6.         # x weeks holidays, index means the number of weeks
   
7.         self.weekholidays = weekholidays
   
8. 
   
9. class MaxHoliday(object):
   
10.     def dfs(self, citys, start_city, week, maxweek, memhash, maxdistance):
    
11.         if week == maxweek:
    
12.             return 0
    
13.         # if we have searched before, directly return
    
14.         key = str(week) + '-' + str(start_city.cityid)
    
15.         if key in memhash:
    
16.             return memhash[key]
    
17.         maxdays = 0
    
18.         for cityid in start_city.dstcity:
    
19.             if start_city.dstcity[cityid] <= maxdistance:
    
20.                 maxdays = max(maxdays, self.dfs(citys, citys[cityid], week + 1, maxweek, memhash, maxdistance))
    
21.         maxdays += start_city.weekholidays[week]
    
22.         memhash[key] = maxdays
    
23.         return maxdays
    
24. 
    
25.     def maxholidayweeks(self, citys, maxweek, maxdistance):
    
26.         # key: weeky+cityid,value: maxholiday
    
27.         memhash = {}
    
28.         return self.dfs(citys, citys['A'], 0, maxweek, memhash, maxdistance)
    
29. 
    
30. 
    
31. cityA = City('A', {'B': 6, 'C': 2, 'D': 30}, [2, 0, 3])
    
32. cityB = City('B', {'A': 6, 'C': 20, 'D': 7}, [1, 1, 0])
    
33. cityC = City('C', {'A': 2, 'B': 20, 'D': 10}, [1, 1, 1])
    
34. cityD = City('D', {'A': 20, 'B': 7, 'C': 10}, [0, 0, 2])
    
35. citys = {'A': cityA, 'B': cityB, 'C': cityC, 'D': cityD}
    
36. 
    
37. T = MaxHoliday()
    
38. print T.maxholidayweeks(citys, 3, 2)

复制代码

第四题可以直接找就可以。

1.         public String solve(String s, int k) {
   
2.                 if (s == null || s.length() < k)
   
3.                         throw new IllegalArgumentException();
   
4. 
   
5.                 int n = s.length();
   
6.                 int left = 0;
   
7.                 int right = n - k;
   
8.                 StringBuilder ansBuilder = new StringBuilder();
   
9.                 while (right < n) {
   
10.                         int best = left;
    
11.                         for (int i = left; i <= right; i++) {
    
12.                                 if (s.charAt(i) < s.charAt(best))
    
13.                                         best = i;
    
14.                         }
    
15.                         ansBuilder.append(s.charAt(best));
    
16.                         left = best + 1;
    
17.                         right += 1;
    
18.                 }
    
19.                 return ansBuilder.toString();
    
20.         }

复制代码

Iterator那个题目能用额外空间吗？

1. public class P000_FunnyIterator implements Iterable<Integer> {
   
2.         List<Integer> data;
   
3. 
   
4.         P000_FunnyIterator(int[] input) {
   
5.                 if (input == null || (input.length & 1) == 1)
   
6.                         throw new IllegalArgumentException();
   
7.                 int n = input.length;
   
8. 
   
9.                 this.data = new ArrayList<>();
   
10.                 for (int i = 0; i < n; i += 2) {
    
11.                         for (int c = 0; c < input[i]; c++)
    
12.                                 this.data.add(input[i + 1]);
    
13.                 }
    
14.         }
    
15. 
    
16.         @Override
    
17.         public Iterator<Integer> iterator() {
    
18.                 return data.iterator();
    
19.         }
    
20. }

复制代码

不用额外空间的话也可以

1. public class P000_FunnyIterator implements Iterator<Integer> {
   
2.         int[] data;
   
3.         int curPos = 0;
   
4.         int curCount = 0;
   
5. 
   
6.         P000_FunnyIterator(int[] input) {
   
7.                 if (input == null || (input.length & 1) == 1)
   
8.                         throw new IllegalArgumentException();
   
9.                 for (int i = 0; i < input.length; i += 2)
   
10.                         if (input[i] < 0)
    
11.                                 throw new IllegalArgumentException();
    
12.                 this.data = input;
    
13.         }
    
14. 
    
15.         @Override
    
16.         public boolean hasNext() {
    
17.                 while (curPos < data.length && data[curPos] == 0)
    
18.                         curPos += 2;
    
19. 
    
20.                 return curPos < data.length;
    
21.         }
    
22. 
    
23.         @Override
    
24.         public Integer next() {
    
25.                 int ans = data[curPos + 1];
    
26.                 curCount += 1;
    
27.                 if (curCount == data[curPos]) {
    
28.                         curPos += 2;
    
29.                         curCount = 0;
    
30.                 }
    
31.                 return ans;
    
32.         }
    
33. 
    
34.         @Override
    
35.         public void remove() {
    
36.                 throw new UnsupportedOperationException();
    
37.         }

复制代码

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

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

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

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

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

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

第二题是直接暴力输出么？

liurudahai 发表于 2016-10-3 05:10
突然看懂这题了，楼主说是BFS，但其实是DFS把，DFS可以算完一条路径的总时间之后再算另一条路径，比较清 ...

这个题飞行时间是不计在假期／工作时间里的，只是用来约束从一个城市能飞到哪些城市。