azl397985856/leetcode

【专题】 反向思考

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

1358. 包含所有三种字符的子字符串数目

不要思考往前舍去 多少，而是思考往后加上多少

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