The leetcode from wilkice

{
    "name": "darcy",
    "city": "shenzhen"
}

leetcode's People

Contributors

Watchers

leetcode's Issues

1365. How Many Numbers Are Smaller Than the Current Number

https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/

第一种遍历：O(n²)

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        return [sum(i > j for j in nums) for i in nums]

第二种先排序后遍历：O(nlogn)

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sorted_nums = sorted(nums)
        return [sorted_nums.index(num) for num in nums]

nlogn(排序) + n = nlogn

#1342 Number of Steps to Reduce a Number to Zero

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

分析题目可以得知此题解法与 bit 有关。当最后一位 bit 是 1（并且此时值不为1）的时候，需要2步（1步是减去1，1步是除以2），当最后一位 bit 是0的时候，只需要一步，即除以2.

解法一：

class Solution:
    def numberOfSteps (self, num: int) -> int:
        total = 0

        # num 为0或者1，直接返回0或1
        if num <= 1:
            return num

        while num >1:
            # 如果 num 为奇数，则加2步
            if num & 1 == 1:
                total += 2
            # 偶数加1步
            else:
                total += 1
            num >>= 1

        # +1 是因为上面的循环在num=1的时候退出，所以此时需要加上1变为0的步数
        return total+1

解法二（推荐）：直接计算bit中1和0的个数

class Solution:
    def numberOfSteps (self, num: int) -> int:
        value = f'{num:b}'  # 也可以用 bin(num)[2:]
        return value.count("1") -1 + len(value)