瞎扯淡 被一道 leetcode 中等题难住了
题目： 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
我不是程序员，但我尝试了下，也是卡在同样的位置。 这是我的代码。我一直想能不能先从 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
才发现循环赋值得到 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