力扣第 170 场双周赛

653
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

3750. 最少反转次数得到翻转二进制字符串 - 力扣（LeetCode） ​

题目类型 ​

#位运算

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def minimumFlips(self, n: int) -> int:
        return sum(int(x != y) for x, y in zip(bin(n)[2:], bin(n)[2:][::-1]))
python
class Solution:
    def minimumFlips(self, n: int) -> int:
        s = bin(n)[2:]
        return sum(s[i] != s[~i] for i in range(len(s)))

3751. 范围内总波动值 I - 力扣（LeetCode） ​

题目类型 ​

#枚举 #数位DP

解题思路 ​

参考：思路同 3753

示例代码 ​

python
class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        ans = 0
        for x in range(num1, num2 + 1):
            s = list(map(int, str(x)))
            for i in range(1, len(s) - 1):
                if (s[i] - s[i - 1]) * (s[i] - s[i + 1]) > 0:
                    ans += 1
        return ans

3752. 字典序最小和为目标值且绝对值是排列的数组 - 力扣（LeetCode） ​

题目类型 ​

#贪心 #排序

解题思路 ​

初始选择全正元素排列，从大到小选择元素，枚举每个元素取反计算贡献，最后特判是否满足

参考：贪心，O(n) 做法（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def lexSmallestNegatedPerm(self, n: int, target: int) -> List[int]:
        m = n * (n + 1) // 2
        ans = []
        for i in range(n, 0, -1):
            if m - 2 * i >= target:
                ans.append(-i)
                m -= 2 * i
            else:
                ans.append(i)
        return sorted(ans) if m == target else []

3753. 范围内总波动值 II - 力扣（LeetCode） ​

题目类型 ​

#数位DP

解题思路 ​

套用数位 DP 模板 v2.0 即可

参考：上下界数位 DP（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def count_numbers_in_range(self, low: int, high: int) -> int:
        n = len(str(high))
        diff = n - len(str(low))
        low = list(map(int, str(low).zfill(n)))
        high = list(map(int, str(high)))

        @lru_cache(None)
        def dfs(i: int, limit_low: bool, limit_high: bool, is_num: bool, pre1: int, pre2: int, cnt: int) -> int:
            if i == len(high):
                return cnt
            res = 0

            if i < diff and not is_num:
                res += dfs(i + 1, True, False, False, pre1, pre2, cnt)

            lo = low[i] if limit_low else 0
            hi = high[i] if limit_high else 9

            for d in range(max(lo, 1 - is_num), hi + 1):
                tmp = 0
                if pre1 >= 0 and pre2 >= 0:
                    if (pre1 - pre2) * (pre1 - d) > 0:
                        tmp = 1
                res += dfs(i + 1, limit_low and d == lo, limit_high and d == hi, True, d, pre1, cnt + tmp)
            return res

        ans = dfs(0, True, True, False, -1, -1, 0)
        dfs.cache_clear()
        return ans

    def totalWaviness(self, num1: int, num2: int) -> int:
        return self.count_numbers_in_range(num1, num2)
力扣第 477 场周赛
力扣第 169 场双周赛