Pow(x, n)，数值的整数次方 快速幂

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
输入：x = 2.00000, n = 10
输出：1024.00000
输入：x = 2.10000, n = 3
输出：9.26100
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

  1. class Solution(object):
  2.     def myPow(self, x, n):
  3.         if x == 0.0: 
  4.             return 0.0
  5.         # 当n < 0 时：把问题转化至n≥0 的范围内，即执行x = 1/x，n = - n
  6.         if n < 0: 
  7.             x = 1 / x
  8.             n = -n
  10.         res = 1
  11.         while n:
  12.             if n & 1: 
  13.                 res = res * x
  14.             x = x * x
  15.             n = n >> 1
  16.             # n = n // 2
  17.         return res
  1. 当x = 0.0时：直接返回0.0，以避免后续1除以0操作报错。分析：数字0的正数次幂恒为0；0的0次幂和负数次幂没有意义，因此直接返回0.0即可
  2. 初始化res = 1
  3. 当n < 0 时：把问题转化至n≥0 的范围内，即执行x = 1/x，n = - n
  4. 循环计算：当 x=0 时跳出
    1. 当n & 1 = 1时：将当前x乘入res（即 res = res * x ）
    2. 执行x = x * x
    3. 执行n右移一位（即 n >>= 1）

  5. 返回res

    递归乘法

    递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
    输入：A = 1, B = 10
    输出：10
    输入：A = 3, B = 4
    输出：12

    1. class Solution(object):
    2.  def multiply(self, A, B):
    3.      # 将其中的B拆成2进制，那么每一位对应的就是2的幂，那么可以由A+=A得到
    4.      res = 0
    5.      while B:
    6.          # 当前位为奇数时，加一次 A
    7.          # 当前位为 偶数时，加两次 A
    8.          if B & 1: 
    9.              res += A
    10.          # B 不断地向右移动一位计算，直至B为0
    11.          B = B >> 1
    12.          if B:
    13.              A += A
    14.      return res

    基本计算器

    给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
    输入：s = “1 + 1”
    输出：2
    输入：s = “ 2-1 + 2 “
    输出：3
    输入：s = “(1+(4+5+2)-3)+(6+8)”
    输出：23

    1. class Solution(object):
    2.  def calculate(self, s):
    3.      # 用栈保存遇到左括号时前面计算好了的运算符
    4.      stack = [1]
    5.      # sign表示当前运算符
    6.      sign = 1
    7.      # res表示左边表达式除去栈内保存元素的计算结果
    8.      res = 0
    10.      i = 0
    11.      while i < len(s):
    12.          if s[i] == ' ':
    13.              i += 1
    14.          # 如果是+用sign记录下来
    15.          elif s[i] == '+':
    16.              sign = stack[-1]
    17.              i += 1
    18.          # 如果是-用sign记录下来
    19.          elif s[i] == '-':
    20.              sign = -stack[-1]
    21.              i += 1
    22.          # 如果是(，将当前sign记录到栈
    23.          elif s[i] == '(':
    24.              stack.append(sign)
    25.              i += 1
    26.          # 如果是)，将sign剔除
    27.          elif s[i] == ')':
    28.              stack.pop()
    29.              i += 1
    30.          else:
    31.              # 为了解决可能出现连续的数字
    32.              num = 0
    33.              # 下标没越界且s[i]是数字
    34.              while i < len(s) and s[i].isdigit():
    35.                  num = num * 10 + int(s[i])
    36.                  i += 1
    37.              # num加上sign运算符更新到res中
    38.              res += num * sign
    39.      return res

    基本计算器 II

    注意：这个题一定要切到Python3提交，2过不了
    给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
    整数除法仅保留整数部分。
    输入：s = “3+2*2”
    输出：7
    输入：s = “ 3/2 “
    输出：1
    输入：s = “ 3+5 / 2 “
    输出：5

    1. class Solution:
    2.  def calculate(self, s: str) -> int:
    3.      stack = []
    4.      pre_ops = '+'
    5.      num = 0
    6.      i = 0
    7.      while i < len(s):
    8.          if s[i].isdigit():
    9.              num = 10 * num + int(s[i])
    10.          if i == len(s) - 1 or s[i] in '+-*/':
    11.              if pre_ops == '+':
    12.                  stack.append(num)
    13.              elif pre_ops == '-':
    14.                  stack.append(-num)
    15.              elif pre_ops == '*':
    16.                  stack.append(stack.pop() * num)
    17.              elif pre_ops == '/':
    18.                  stack.append(int(stack.pop() / num))
    19.              pre_ops = s[i]
    20.              num = 0
    21.          i += 1
    22.      return sum(stack)

    两整数之和

    不使用运算符 + 和 - ，计算两整数 a 、b 之和。
    输入: a = 1, b = 2
    输出: 3
    输入: a = -2, b = 3
    输出: 1

    1. class Solution:
    2.  # 根本就不会
    3.  def getSum(self, a: int, b: int) -> int:
    4.      a &= 0xFFFFFFFF
    5.      b &= 0xFFFFFFFF
    6.      while b:
    7.          carry = a & b
    8.          a ^= b
    9.          b = ((carry) << 1) & 0xFFFFFFFF
    10.          # print((a, b))
    11.      return a if a < 0x80000000 else ~(a^0xFFFFFFFF)

    水壶问题

    有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
    如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
    你允许：
    装满任意一个水壶
    清空任意一个水壶
    从一个水壶向另外一个水壶倒水，直到装满或者倒空
    输入: x = 3, y = 5, z = 4
    输出: True
    输入: x = 2, y = 6, z = 5
    输出: False

    1. class Solution:
    2.  def canMeasureWater(self, jug1Capacity, jug2Capacity, targetCapacity):
    3.      # 方法一：贝祖定理
    4.      x = jug1Capacity
    5.      y = jug2Capacity
    6.      z = targetCapacity
    7.      if z == 0:
    8.          return True
    9.      if x == 0:
    10.          if z == y:
    11.              return True
    12.          else:
    13.              return False
    14.      if y == 0:
    15.          if z == x:
    16.              return True
    17.          else:
    18.              return False
    19.      if z > x + y:
    20.          return False
    22.      # 而贝祖定理告诉我们，ax+by=z有解当且仅当z是x, y的最大公约数的倍数。因此我们只需要找到x,y的最大公约数并判断z是否是它的倍数即可。
    23.      if x > y:
    24.          x, y = y, x
    25.      if y % x == 0:
    26.          if z % x == 0:
    27.              return True
    28.          else:
    29.              return False
    30.      else:
    31.          if y % (y % x) == 0:
    32.              if z % (y % x) == 0:
    33.                  return True
    34.              else:
    35.                  return False
    36.          else:
    37.              return True
    39.      # 方法二：调包侠
    40.      x = jug1Capacity
    41.      y = jug2Capacity
    42.      z = targetCapacity
    43.      if x + y < z:
    44.          return False
    45.      if x == 0 or y == 0:
    46.          return z == 0 or x + y == z
    47.      return z % math.gcd(x, y) == 0

    多数元素*（摩尔投票法）

    给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    输入：[3,2,3]
    输出：3
    输入：[2,2,1,1,1,2,2]
    输出：2

    1. class Solution(object):
    2.  def majorityElement(self, nums):
    3.      count = 0
    4.      major = 0
    6.      for i in nums:
    7.          if count == 0:
    8.              major = i
    9.          if i == major:
    10.              count += 1
    11.          else:
    12.              count -= 1
    13.      return major

    快乐数

    编写一个算法来判断一个数 n 是不是快乐数。
    「快乐数」定义为：
    对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
    然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
    如果 可以变为 1，那么这个数就是快乐数。
    如果 n 是快乐数就返回 true ；不是，则返回 false 。
    输入：19
    输出：true
    解释：
    12 + 92 = 82
    82 + 22 = 68
    62 + 82 = 100
    12 + 02 + 02 = 1
    输入：n = 2
    输出：false

    1. class Solution(object):
    2.  def isHappy(self, n):
    3.      dicts = {}
    5.      while True:
    6.          n = sum(int(i) ** 2 for i in str(n))
    7.          if n == 1:
    8.              return True
    9.          if n in dicts:
    10.              return False
    11.          dicts[n] = 1

    只出现一次的数字

    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
    输入: [2,2,1]
    输出: 1
    输入: [4,1,2,1,2]
    输出: 4

    1. class Solution(object):
    2.  def singleNumber(self, nums):
    3.      # 异或，当同位相同时结果为0，不同结果为1
    4.      res = 0
    5.      for i in nums:
    6.          res ^= i
    7.      return res

    数组中数字出现的次数*

    一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
    输入：nums = [4,1,4,6]
    输出：[1,6] 或 [6,1]
    输入：nums = [1,2,10,4,1,4,3,3]
    输出：[2,10] 或 [10,2]

    1. class Solution(object):
    2.  def singleNumbers(self, nums):
    3.      res = 0  # 所有数字异或的结果
    4.      a = 0
    5.      b = 0
    6.      for i in nums:
    7.          res ^= i
    8.      # 找到第一位不是0的
    9.      h = 1
    10.      while(res & h == 0):
    11.          h <<= 1
    12.      for n in nums:
    13.          # 根据该位是否为0将其分为两组
    14.          if (h & n == 0):
    15.              a ^= n
    16.          else:
    17.              b ^= n
    19.      return [a, b]

    除自身以外数组的乘积，构建乘积数组

    给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
    输入: [1,2,3,4]
    输出: [24,12,8,6]

    1. class Solution(object):
    2.  def productExceptSelf(self, nums):
    3.      # 根据表格的主对角线，可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积
    4.      res = [1] * len(nums)
    6.      for i in range(1, len(nums)):
    7.          res[i] = res[i-1] * nums[i-1] # 下三角
    9.      tmp = 1
    10.      for j in range(len(nums) - 2, -1, -1):
    11.          tmp *= nums[j+1] # 上三角
    12.          res[j] *= tmp # 下三角 * 上三角
    13.      return res

    把数字翻译成字符串

    给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
    输入: 12258
    输出: 5
    解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”

    1. class Solution(object):
    2.  def translateNum(self, num):
    3.      # 方法一：从左向右遍历
    4.      s = str(num)
    5.      a = b = 1
    6.      for i in range(2, len(s) + 1):
    7.          # 如果当前值和前一个数字能组成10到25的数
    8.          if "10" <= s[i-2:i] <= "25":
    9.              c = a + b
    10.          else:
    11.              c = a
    12.          b = a
    13.          a = c
    14.      return a

    最小数

    输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
    输入: [10,2]
    输出: “102”
    输入: [3,30,34,5,9]
    输出: “3033459”

    1. class Solution(object):
    2.  def minNumber(self, nums):
    3.      if len(nums)==0:
    4.          return ""
    6.      # 将元素都转换成字符串
    7.      for i in range(len(nums)):
    8.          nums[i] = str(nums[i])
    10.      # 冒泡排序。。
    11.      for i in range(len(nums)):
    12.          for j in range(i+1, len(nums)):
    13.              if nums[i] + nums[j] > nums[j] + nums[i]:
    14.                  nums[i], nums[j] = nums[j], nums[i]
    15.      return "".join(nums)

    最大数

    给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
    注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
    输入：nums = [10,2]
    输出：”210”
    输入：nums = [3,30,34,5,9]
    输出：”9534330”

    1. class Solution(object):
    2.  def largestNumber(self, nums):
    3.      # 方法一：堆排序
    4.      s = []
    5.      for i in nums:
    6.          tmp = (str(i)*10)[:10]
    7.          heapq.heappush(s, [-int(tmp), str(i)])
    8.      ans = ""
    9.      while s:
    10.          ans += heapq.heappop(s)[1]
    11.      return str(int(ans))
    13.      # 方法二：冒泡排序
    14.      for i in range(len(nums)):
    15.          for j in range(len(nums) - i - 1):
    16.              if str(nums[j]) + str(nums[j + 1]) > str(nums[j + 1]) + str(nums[j]):
    17.                  nums[j], nums[j + 1] = nums[j + 1], nums[j]
    18.      s = ''
    19.      if nums[-1] == 0:
    20.          return('0')
    21.      for i in nums:
    22.          s = str(i) + s
    23.      return s

    扑克牌中的顺子

    从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
    输入: [1,2,3,4,5]
    输出: True
    输入: [0,0,1,2,5]
    输出: True

    1. class Solution(object):
    2.      # 排序后首先排除0，然后累加相邻元素差，这是为了在相邻元素差为0（即相邻元素相等）时，直接返回False，如果累加差值<5，则为顺子。
    3.      nums.sort()
    4.      count = 0
    5.      for i in range(4):
    6.          if nums[i] == 0:
    7.              continue
    8.          if nums[i+1] == nums[i]:
    9.              return False
    10.          count += nums[i+1] - nums[i]
    11.      if count < 5:
    12.          return True
    13.      return False

    丑数

    给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
    丑数 就是只包含质因数 2、3 和/或 5 的正整数。
    输入：n = 6
    输出：true
    解释：6 = 2 × 3
    输入：n = 8
    输出：true
    解释：8 = 2 × 2 × 2

    1. class Solution(object):
    2.  def isUgly(self, n):
    3.      if n <= 0:
    4.          return False
    6.      factors = [2, 3, 5]
    7.      for factor in factors:
    8.          while n % factor == 0:
    9.              n //= factor
    10.      return n == 1

    丑数 II

    给你一个整数 n ，请你找出并返回第 n 个 丑数 。
    丑数 就是只包含质因数 2、3 和/或 5 的正整数。
    输入：n = 10
    输出：12
    解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
    输入：n = 1
    输出：1
    解释：1 通常被视为丑数。

    1. class Solution(object):
    2.  def nthUglyNumber(self, n):
    3.      if n < 0:
    4.          return 0
    5.      dp = [1] * n
    6.      index2, index3, index5 = 0, 0, 0
    7.      for i in range(1, n):
    8.          dp[i] = min(2 * dp[index2], 3 * dp[index3], 5 * dp[index5])
    9.          if dp[i] == 2 * dp[index2]: 
    10.              index2 += 1
    11.          if dp[i] == 3 * dp[index3]: 
    12.              index3 += 1
    13.          if dp[i] == 5 * dp[index5]: 
    14.              index5 += 1
    15.      return dp[n - 1]

    用两个栈实现队列

    1. class CQueue:
    2.  def __init__(self):
    3.      self.A, self.B = [], []
    5.  def appendTail(self, value):
    6.      self.A.append(value)
    8.  def deleteHead(self):
    9.      if self.B: return self.B.pop()
    10.      if not self.A: return -1
    11.      while self.A:
    12.          self.B.append(self.A.pop())
    13.      return self.B.pop()

    比较版本号

    给你两个版本号 version1 和 version2 ，请你比较它们。
    输入：version1 = “1.01”, version2 = “1.001”输出：0
    解释：忽略前导零，”01” 和 “001” 都表示相同的整数 “1”
    输入：version1 = “1.0”, version2 = “1.0.0”
    输出：0
    解释：version1 没有指定下标为 2 的修订号，即视为 “0”
    输入：version1 = “0.1”, version2 = “1.1”
    输出：-1
    解释：version1 中下标为 0 的修订号是 “0”，version2 中下标为 0 的修订号是 “1” 。0 < 1，所以 version1 < version2
    输入：version1 = “1.0.1”, version2 = “1”
    输出：1 ```python class Solution: def compareVersion(self, version1, version2):

    1.  # 方法一：补齐元素再比大小
    2.  nums1 = version1.split('.')
    3.  nums2 = version2.split('.')
    5.  # 补齐长度
    6.  if len(nums1) > len(nums2):
    7.      nums2 = nums2 + ['0'] * (len(nums1)-len(nums2))
    8.  if len(nums2) > len(nums1):
    9.      nums1 = nums1 + ['0'] * (len(nums2) - len(nums1))
    11.  # 分别比较两个版本号每一位的大小
    12.  for i in range(len(nums1)):
    13.      if int(nums1[i]) > int(nums2[i]):
    14.          return 1
    15.      elif int(nums1[i]) < int(nums2[i]):
    16.          return -1
    17.      else:
    18.          continue
    19.  return 0

class Solution: def compareVersion(self, version1, version2):

  1.     # 方法二：与方法一类似，只是不补齐，两个复杂度一样都不是最优解
  2.     nums1 = version1.split('.')
  3.     nums2 = version2.split('.')
  5.     for i in range(max(len(nums1), len(nums2))):
  6.         # 分别比较两个版本号每一位的大小
  7.         if i < len(nums1):
  8.             i1 = int(nums1[i])
  9.         else:
  10.             i1 = 0 
  11.         if i < len(nums2):
  12.             i2 = int(nums2[i])
  13.         else:
  14.             i2 = 0
  16.         if i1 > i2:
  17.             return 1
  18.         elif i1 < i2:
  19.             return -1
  20.         else:
  21.             continue
  22.     return 0 
  1. <a name="lds2J"></a>
  2. ## 小数循环节
  3. ```python
  4. def xun_huan_jie(a, b):
  5.     # 不再判断余数是否为0，而是把所有的小数都看为循环小数，0.5可以看为：0.5[0]，这样就统一处理了
  6.     zheng = str(a // b)  ## 商的整数部分
  7.     shang = ""  ## 商的小数部分
  8.     yu = [a % b]
  10.     while True:
  11.         # 求商
  12.         x = (yu[-1] * 10) // b
  13.         # 求余
  14.         y = (yu[-1] * 10) % b
  16.         shang += str(x)
  17.         yu.append(y)
  18.         i = yu.index(yu[-1])
  19.         if i != len(yu) - 1:
  20.             shang = shang[:i] + "[" + shang[i:] + "]"
  21.             break
  23.     r = zheng + "." + shang
  24.     # 如果以[0]结尾，就删去
  25.     if r.endswith("[0]"):
  26.         r = r[:-3]
  27.     # 如果没有小数部分，小数点也删去
  28.     if r.endswith("."):
  29.         r = r[:-1]
  30.     return r
  33. if __name__ == '__main__':
  34.     print(xun_huan_jie(100, 5))
  35.     print(xun_huan_jie(1, 8))
  36.     print(xun_huan_jie(1, 7))
  37.     print(xun_huan_jie(12345, 1700))
  39. 20
  40. 0.125
  41. 0.[142857]
  42. 7.26[1764705882352941]