LeetCode每日练习

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

输入：x = 2.00000, n = 10
输出：1024.00000

# class Solution:
#     def myPow(self, x: float, n: int) -> float:
#         return pow(x, n)

# 用 低维度 计算 高维度
# 0、n为负数：x^n = (1/x)^(-n)
# 1、n为偶数：x^n = x^(n/2)*x^(n/2)
# 2、n为奇数：x^n = x^((n-1)/2)*x^((n-1)/2)*x

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0.0
        res = 1
        # 当n<0时，对 x 和 n 进行转换 
        if n < 0:
            x = 1 / x
            n = -n
        # 对奇数和偶数进行处理
        while n:
            # n 为奇数，奇数的二进制中有偶数个1，和1与运算的结果必为1
            if n & 1:
                res *= x
            x *= x
            # 右移运算等同于除以二
            n >>= 1
        return res

1051. 高度检查器

学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
返回满足 heights[i] != expected[i] 的 下标数量 。

输入：heights = [1,1,4,2,1,3]
输出：3
解释：
高度：[1,1,4,2,1,3]
预期：[1,1,1,2,3,4]
下标 2 、4 、5 处的学生高度不匹配。

• 方法1：排序前后依次比较

# 非递减的高度顺序：递增
class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        h = sorted(heights)
        # print(h)
        # print(heights)
        res = 0
        for i in range(len(h)):
            if h[i] != heights[i]:
                res += 1
        return res

• 方法2：在递增顺序的位置上是否出现了满足递增条件的数字

# 非递减的高度顺序：递增
class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        # 首先对相同高度的学生进行计数统计
        h_max = max(heights)
        h = [0]*(h_max + 1)
        for hei in heights:
            h[hei] += 1
        # print(h)
        # 然后进行比较
        idx, res = 0,0
        for i in range(1, h_max + 1):
            for j in range(h[i]):
                # 依次进行比较
                if heights[idx] != i:
                    res += 1
                # 更新下标
                idx += 1
        return res