LeetCode冲刺：Day38

发布于 2022-12-15 41 次阅读

1. 转换数字的最少位翻转次数

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

逐位对比，或者异或后计算二进制1的个数。

后一种方法居然没能超过100%。

代码

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        # ans = 0
        # s, g = 0, 0
        # while start != 0 or goal != 0:
        #     s = (start & 1)
        #     g = (goal & 1)
        #     if s != g: ans += 1
        #     start >>= 1
        #     goal >>= 1
        # return ans
        start ^= goal
        return start.bit_count()

2. 数组的三角和

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

直接模拟，可以通过。

代码

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        while len(nums) > 1:
            newNums = [0 for i in range(len(nums) - 1)]
            for i in range(len(newNums)):
                newNums[i] = (nums[i] + nums[i + 1]) %10
            nums = newNums
        return nums[0]

3. 选择建筑的方案数

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

注意到，当中间建筑种类确定时，左右建筑种类也就确定了。因此可以枚举每一个建筑作为中间建筑的情况，统计其左右两边另一种类建筑的数目，其乘积即为以当前建筑为中心，可构成的合法组合数。

代码

class Solution:
    def numberOfWays(self, s: str) -> int:
        n = len(s)
        nums = [[0, 0] for i in range(n)]
        leftResNum = rightResNum = leftOffNum = rightOffNum = 0
        for i in range(n):
            if s[i] == '0':
                leftOffNum += 1
                nums[i][0] = leftResNum
            else:
                leftResNum += 1
                nums[i][0] = leftOffNum
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                rightOffNum += 1
                nums[i][1] = rightResNum
            else:
                rightResNum += 1
                nums[i][1] = rightOffNum
        ans = 0
        for i in range(n):
            ans += nums[i][0] * nums[i][1]
        return ans