狗家昂塞挂经

chenyijia055 发表于 2019-5-31 11:52
第五轮 给了一个字符串，返汉包含特定序列的最短长度。 这个特定序列的定义是  包含a 到z的所有26个字母 并 ...

1. 
   
2.     static int shortest26(String input) {
   
3.         int len = input.length();
   
4.               int shortest = len;
   
5.         Map<Character, List<int[]>> map = new HashMap<>();//<char, {<index, steps><index, steps>---} >
   
6.         for (int i = 0; i < len; i++) {
   
7.             char ch = input.charAt(i);
   
8.                   if ('a' <= ch && ch <= 'z') {
   
9.                 map.putIfAbsent(ch, new ArrayList<>());
   
10.                 if (ch == 'a') {
    
11.                     map.get(ch).add(new int[] {i, 1});
    
12.                 } else if (map.containsKey((char)(ch - 1)) && !map.get((char)(ch - 1)).isEmpty()) {//other letters
    
13.                     int[] cur = {i, Integer.MAX_VALUE};
    
14.                     for (int[] pair : map.get((char)(ch - 1))) {
    
15.                         if (cur[1] > pair[1] + i - pair[0]) {
    
16.                             cur[1] = pair[1] + i - pair[0];
    
17.                         }
    
18.                     }
    
19.                           if (ch == 'z') shortest = Math.min(shortest, cur[1]);
    
20.                     map.get(ch).add(cur);
    
21.                 }
    
22.             }
    
23.         }
    
24.               return shortest;
    
25.     }  

复制代码

随手写了下 欢迎纠错

现在狗家也有一轮bq？

第五轮 刷题网 柒饵柒

唉，积分好少，看不到啊

松鼠山 发表于 2019-6-1 08:29
[mw_shl_code=java,true]
    static int shortest26(String input) {
        int len = input.length ...

import collections
class Solution:
  def find(self, s):
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
      d[ord(c)-ord('a')].append(i)
    curr = [(start, start) for start in d[0]]
    level = 1
    while curr and level<26:
      next = []
      for start, curr in curr:
          for nxt in d[level]:
            if nxt > curr:
              break
          else:
            break
          next.append((start, nxt))
      curr = next
      level += 1
    return min(curr, key = lambda s:s[1]-s[0] or [0])

不知道该怎么编辑原帖子。我把面镜又copy了一下 把积分门槛降低了

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

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

这无语了 发表于 2019-5-31 16:58
第五轮 刷题网 柒饵柒

对啊 才发现discussion里的sliding window解法超好理解  也容易分析表达

geyu625 发表于 2019-5-31 19:44
不知道该怎么编辑原帖子。我把面镜又copy了一下 把积分门槛降低了
**** 本内容被作者隐藏 ****

第一轮是union find做的吗？ 每次某选手选个位置都检查一遍是否是4个union？

谁能讲讲第一题

我感觉这些都不会啊。第一题啥意思，最后一题是啥意思，