Facebook 电面

shepherd001 发表于 2016-3-31 06:00
OK，那我觉得是题目本身描述的不是那么清楚，不过现在了解了，谢谢。
另外，cooldown＝2的话，AA是2，那 ...

我是想说ABCA，手滑打错了。。。。

这题不就是从左到右扫一遍，然后数有几个相同的字母相邻吗？为什么要hashmap？
total_time = len(tasks) + 5*(number_of_same_task - 1)
如果这样的话未必有些太简单了吧。。。。还是我理解错了？

不知道现在facebook还收不收人， 我听说都freaze了

jeremy_sea 发表于 2016-4-1 01:21
这题不就是从左到右扫一遍，然后数有几个相同的字母相邻吗？为什么要hashmap？
total_time = len(tasks) + ...

我一开始 也是这样想的，  看来意思不是这样， 并不是字母相邻。 比如ABcA, cooldown 是5， 那么输出是ABC...A   所以用map记录上一次char出现的时间点。

gigimei 发表于 2016-3-20 11:39
我用一个HashMap保存上一次任务的时间点。脑袋一发烧存成了在原字符串中的位置。我测试的例子比如ABAB，AAB ...

谢谢提醒，我开始想法也是存放index，仔细一想不对，想不到还有这么一个陷阱。谢谢了。

adiggo 发表于 2016-4-1 02:33
我一开始 也是这样想的，  看来意思不是这样， 并不是字母相邻。 比如ABcA, cooldown 是5， 那么输出是AB ...

哦，这样还稍微make sense一些
不敢相信这是facebook出的题......

写了下代码

1. public class CooldownTime {
   
2.         public static void main(String[] args) {
   
3.                 System.out.println(cooldownBetter("ACDEGFABXYZPLB", 5));
   
4.         }
   
5. 
   
6.         public static int cooldownBetter(String input, int N) {
   
7.                 int extra = 0;
   
8.                 Map<Character, Integer> map = new HashMap<>();
   
9.                 for (int i = 0; i < input.length(); i++) {
   
10.                         char cur = input.charAt(i);
    
11.                         if (map.containsKey(cur) && map.get(cur) >= i + extra - N) {
    
12.                                 extra += (map.get(cur) - (i + extra - N)) + 2;
    
13.                                 System.out.println(extra + " * ");
    
14.                         }
    
15.                         map.put(cur, i + extra - 1);
    
16.                 }
    
17.                 System.out.println(extra);
    
18.                 return input.length() + extra;
    
19.         }
    
20. 
    
21. }
    

复制代码

1. public class Solution {
   
2.   public String cooldown(String s, int cooldown) {
   
3.     StringBuilder sb = new StringBuilder();
   
4.     Map<Character, Integer> m = new HashMap<>();
   
5.     int writeIdx = 0;
   
6.     for (int i = 0; i < s.length(); i++) {
   
7.       char c = s.charAt(i);
   
8.       if (m.containsKey(c)) {
   
9.         while (writeIdx <= m.get(c) + cooldown) {
   
10.           sb.append(".");
    
11.           writeIdx++;
    
12.         }
    
13.       }
    
14.       sb.append(c);
    
15.       writeIdx++;
    
16.       m.put(c, writeIdx - 1);
    
17.     }
    
18.     return sb.toString();
    
19.   }
    
20. 
    
21.   public int cooldown2(String s, int cooldown) {
    
22.     Map<Character, Integer> m = new HashMap<>();
    
23.     int writeIdx = 0;
    
24.     for (int i = 0; i < s.length(); i++) {
    
25.       char c = s.charAt(i);
    
26.       if (m.containsKey(c)) {
    
27.         writeIdx = Math.max(writeIdx, m.get(c) + cooldown + 1);
    
28.       }
    
29.       writeIdx++;
    
30.       m.put(c, writeIdx - 1);
    
31.     }
    
32.     return writeIdx;
    
33.   }
    
34. 
    
35.   public static void main(String[] args) {
    
36.     Solution ss = new Solution();
    
37.     System.out.println(ss.cooldown("AABB", 5));
    
38.     System.out.println(ss.cooldown2("AABB", 5));
    
39.     return;
    
40.   }
    
41. }
    

复制代码

Map<character, lastIdx>

貌似是这个题
https://discuss.leetcode.com/topic/28289/rearrange-tasks