瞎扯淡 被一道 leetcode 中等题难住了

lyb124553153 · 2022年06月30日 · 最后由 xerox51 回复于 2023年12月24日 · 1018 次阅读

题目: https://leetcode.cn/problems/maximum-number-of-removable-characters/

思路是按照官方题解实现二分,但是最后三个测试用例总是会卡超时,求大家帮我优化一下,或者写一个能通过测试用例的答案出来

def maximum_removals(s, tp, removable)
  left = 0
  @m = s.size
  @n = tp.size
  right = [removable.size(),@m - @n].min 
  while left < right
    mid = (right - left + 1) / 2 + left
    if can_remove?(s,tp,removable, mid)
      left = mid 
    else
      right = mid - 1 
    end
  end

  left 
end

def can_remove?(s, tp, removable, k)
  r = []
  (0...k).each do |i|
    r[removable[i]] = true
  end
  i = 0
  j = 0

  while i < @m do
    if s[i] == tp[j] && !r[i]
        j += 1
        return true if j == @n
    end
    i += 1
  end

  false
end

提交的测试: https://leetcode.cn/submissions/detail/330830006/

ruby 做算法题在耗时上有劣势。同样的算法用其他语言写可以过。

我不是程序员,但我尝试了下,也是卡在同样的位置。 这是我的代码。我一直想能不能先从 removable 得到一个 hash 后,然后使用 hash 的 slice API 来用 O(1)的时间复杂度得到需要部分的键值数据,貌似不行。 我把你这个循环赋值得到 hash 的代码改成 (removable[0, mid]).to_h {|item| [item,true]} 貌似也没啥作用。

def maximum_removals(s, p, removable)
  @m = s.length
  @n = p.length
  left = 0
  right = [removable.length, @m - @n].min
  while left < right
    mid = (right - left + 1) / 2 + left
    temp = (removable[0, mid]).to_h {|item| [item,true]}
    if judge(s, p, temp)
      left = mid
    else
      right = mid - 1
    end
  end
  return left
end

def judge(s, p, r)
  j = 0
  i = 0
  while i < @m
    unless r[i]
      if s[i] == p[j]
        j += 1
        if j == @n
          return true
        end
      end
    end
    i += 1
  end
  return false
end

超时一般就是算法时间复杂度不够低

这题 O(NLogN) 够快了吗?

lithium4010 回复

不,这题是 Ruby 自己慢的原因,官方给的题解都是 NLogN 复杂度,其它语言都 OK,唯独 Ruby 过不去。

才发现循环赋值得到 hash,从一次到最后一次无非也就是 n/2,n/4,n/8……,最后一次判定时,在最坏的情况下,最后一次 hash.size 只有 1,与下面那个线性时间判定是不是子串的循环来说可以忽略不计了,最后也还是 O(n),然后与二分相乘也是 O(nlogn) ,我的努力方向不对,即使每次得到 hash 的耗时是 O(1),最后也还是 O(nlogn),还是需要更牛的算法。我还是太菜了。感谢楼主分享此题,学习 Ruby 果然很快乐,正如 matz 所说,写 Ruby 就像是在写伪代码。

终于在 Leetcode 美国网站上找到了 Ruby 可通过解,纠结了这么久,果然在世界范围内找高人还是有

def maximum_removals(s, t, a)
  s, t = [s, t].map! { _1.each_char.map(&:ord) }
  r, iz, jz = 0, s.size, t.size
  (1..[iz - jz, a.size].min).bsearch do |k|
    c = s.clone
    (0...k).each { c[a[_1]] = 0 }
    i = j = 0
    while j < jz
      i += 1 while i < iz && c[i] != t[j]
      break if i == iz
      i += 1
      j += 1
    end
    j == jz ? (r = k if k > r; 1) : -1
  end
  r
end
需要 登录 后方可回复, 如果你还没有账号请 注册新账号