转置矩阵：给你一个二维整数数组 matrix，返回 matrix 的 转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

class Solution:
 def transpose(self, matrix):
     row = len(matrix)
     column = len(matrix[0])
     new_matrix = [[0 for i in range(row)] for j in range(column)]
     for i in range(row):
         for j in range(column):
             new_matrix[j][i] = matrix[i][j]
     return new_matrix

丑数：我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

class Solution:
 def nthUglyNumber(self, n: int) -> int:
     nums = [1]
     pointer = [0, 0, 0]
     while True:
         if len(nums) == n:
             break
         tmp = (nums[pointer[0]] * 2, nums[pointer[1]] * 3, nums[pointer[2]] * 5)
         x = min(tmp)
         nums.append(x)
         if x == tmp[0]:
             pointer[0] += 1
         if x == tmp[1]:
             pointer[1] += 1
         if x == tmp[2]:
             pointer[2] += 1
     return nums[-1]

所有排列中的最大和：有一个整数数组nums，和一个查询数组requests，其中requests[i] = [starti, endi]。第i个查询求nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]的结果，starti 和endi数组索引都是 从 0 开始 的。你可以任意排列 nums中的数字，请你返回所有查询结果之和的最大值。由于答案可能会很大，请你将它对10^9 + 7取余后返回。

# 贪心 差分数组
class Solution:
 def maxSumRangeQuery(self, nums: list[int], requests: list[list[int]]) -> int:
     length = len(nums)
     count = [0 for i in range(length)]
     for x, y in requests:
         count[x] += 1
         if y + 1 < length:
             count[y + 1] -= 1
     for i in range(1, length):
         count[i] += count[i - 1]
     count.sort()
     nums.sort()
     total = 0
     for i in range(length):
         total += count[i] * nums[i]
     return total % (10 ** 9 + 7)

统计打字方案数：Alice 在给 Bob 用手机打字。数字到字母的 对应如下图所示。为了 打出一个字母，Alice 需要 按对应字母 i次，i是该字母在这个按键上所处的位置。比方说，为了按出字母's'，Alice 需要按'7'四次。类似的， Alice 需要按'5'两次得到字母'k'。注意，数字'0' 和'1'不映射到任何字母，所以Alice 不使用它们。但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息。比方说，Alice 发出的信息为"bob"，Bob 将收到字符串"2266622"。给你一个字符串pressedKeys，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息。由于答案可能很大，将它对109 + 7取余 后返回。

# 动态规划
class Solution:
 def countTexts(self, pressedKeys: str) -> int:
     pressedKeys_split = self.split_text(pressedKeys)
     info = 1
     memo3 = {}
     memo4 = {}
     keyboard = ("7", "9")
     for item in pressedKeys_split:
         if item[0] in keyboard:
             info *= self.func(4, len(item), memo4)
         else:
             info *= self.func(3, len(item), memo3)
     return info % (10 ** 9 + 7)

 def split_text(self, s: str) -> list:
     start = 0
     pressedKeys_split = []
     for end in range(1, len(s)):
         if s[end] != s[end - 1]:
             pressedKeys_split.append(s[start: end])
             start = end
     pressedKeys_split.append(s[start:])
     return pressedKeys_split

 def func(self, item, num, memo) -> int:
     if num == 1 or num == 0:
         return 1
     if num < 0:
         return 0
     if num in memo:
         return memo[num]
     if item == 4:
         infos = self.func(item, num - 1, memo) + self.func(item, num - 2, memo) + self.func(item, num - 3, memo) + self.func(item, num - 4, memo)
     else:
         infos = self.func(item, num - 1, memo) + self.func(item, num - 2, memo) + self.func(item, num - 3, memo)
     memo[num] = infos
     return infos

三除数：给你一个整数 n 。如果 n 恰好有三个正除数 ，返回 true ；否则，返回 false 。如果存在整数 k ，满足 n = k * m ，那么整数 m 就是 n 的一个 除数 。

class Solution:
 def isThree(self, n: int) -> bool:
     if n == 1:
         return False
     if int(str(n ** (1/2)).split('.')[1]) == 0:
         for i in range(2, int(n ** (1/2))):
             if int(n / i) == n / i:
                 return False
         return True
     return False


s = Solution()
print(s.isThree(8))