【专题】 反向思考
azl397985856 opened this issue · 3 comments
azl397985856 commented
记录反向思考的题目。比如: 991. 坏了的计算器
class Solution:
def brokenCalc(self, startValue: int, target: int) -> int:
ans = 0
while startValue != target:
if target < startValue: return ans + startValue - target
if target & 1:
target += 1
else:
target = target // 2
ans += 1
return ans
azl397985856 commented
azl397985856 commented
azl397985856 commented
不要思考往前舍去 多少,而是思考往后加上多少
class Solution:
def numberOfSubstrings(self, s: str) -> int:
i = ans = 0
w = collections.Counter()
for j in range(len(s)):
w[s[j]] += 1
while i < j and len(w) == 3:
ans += len(s) - j
w[s[i]] -= 1
if w[s[i]] == 0: del w[s[i]]
i += 1
return ans