# -*- coding: utf-8 -*-
# 121: 删除有序数组中的重复项 II
# 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
# 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
# 示例 1：
# 输入：nums = [1,1,1,2,2,3]
# 输出：5, nums = [1,1,2,2,3]
# 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
# 不需要考虑数组中超出新长度后面的元素。
#
# 示例 2：
# 输入：nums = [0,0,1,1,1,1,2,3,3]
# 输出：7, nums = [0,0,1,1,2,3,3]
# 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
# 不需要考虑数组中超出新长度后面的元素。


class Solution121:
    def removeDuplicates(self, nums: list[int]) -> int:
        nums1 = nums[:]
        flag = True
        while flag:
            for i in nums1:
                if nums1.count(i) > 2:
                    nums1.remove(i)
            import collections
            if max(list(collections.Counter(nums1).values())) < 3:
                flag = False
            nums[:] = nums1


s121 = Solution121()
data121 = [0, 1, 0, 1, 0, 1, 8]
r121 = s121.removeDuplicates(data121)
print(data121)  # [0, 1, 0, 1, 8]


# 122: 有效的完全平方数
# 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
# 进阶：不要 使用任何内置的库函数，如  sqrt 。
# 示例 1：
# 输入：num = 16
# 输出：true
# 示例 2：
# 输入：num = 14
# 输出：false


class Solution122:
    def isPerfectSquare(self, num: int) -> bool:
        r = num ** 0.5
        return True if int(r) == r else False


s122 = Solution122()
r122 = s122.isPerfectSquare(64)
print(r122)  # True


# 123: 找不同
# 给定两个字符串 s 和 t，它们只包含小写字母。
# 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
# 请找出在 t 中被添加的字母。
# 示例 1：
# 输入：s = "abcd", t = "abcde"
# 输出："e"
# 解释：'e' 是那个被添加的字母。
# 示例 2：
# 输入：s = "", t = "y"
# 输出："y"


class Solution123:
    def findTheDifference(self, s: str, t: str) -> str:
        # 如果s为空，结果=t0
        # 1计数器，2计数器
        # 遍历2的k，如果k在1，并且数目相等，继续遍历。
        # 如果k不在1或者数目不相等，则k
        if s == "":
            return t
        else:
            import collections
            d1 = collections.Counter(s)
            d2 = collections.Counter(t)

            for k, v in d2.items():
                if (k not in d1) or v != d1[k]:
                    return k


s123 = Solution123()
r123 = s123.findTheDifference("god", "good")
print(r123)  # o


# 124: 找到所有数组中消失的数字
# 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n]
# 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
# 示例 1：
# 输入：nums = [4,3,2,7,8,2,3,1]
# 输出：[5,6]
# 示例 2：
# 输入：nums = [1,1]
# 输出：[2]


class Solution124:
    def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
        # 新建列表
        # 求出实际长度，
        # 求出1-n所有
        # my_list  如果i不在nums  加入列表
        lend = len(nums)
        nums = set(nums)
        my_list = [i for i in range(1, lend + 1) if i not in nums]
        return my_list


s124 = Solution124()
r124 = s124.findDisappearedNumbers([2, 4, 5, 1, 8, 7])
print(r124)  # [3, 6]


# 125: 找到所有数组中消失的数字
# 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
# 你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
# 示例 1：
# 输入：num1 = "11", num2 = "123"
# 输出："134"
# 示例 2：
# 输入：num1 = "456", num2 = "77"
# 输出："533"
# 示例 3：
# 输入：num1 = "0", num2 = "0"
# 输出："0"


class Solution125:
    def addStrings(self, num1: str, num2: str) -> str:
        # return eval(num1) + eval(num2)
        return str(int(num1) + int(num2))


s125 = Solution125()
r125 = s125.addStrings("8", "9")
print(r125)  # 17


# 126: 数组形式的整数加法
# 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。
# 例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
# 给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
# 示例 1：
# 输入：A = [1,2,0,0], K = 34
# 输出：[1,2,3,4]
# 解释：1200 + 34 = 1234
#
# 示例 2：
# 输入：A = [2,7,4], K = 181
# 输出：[4,5,5]
# 解释：274 + 181 = 455
#
# 示例 3：
# 输入：A = [2,1,5], K = 806
# 输出：[1,0,2,1]
# 解释：215 + 806 = 1021


class Solution126:
    def addToArrayForm(self, num: list[int], k: int) -> list[int]:
        # 合并成字符串，转成int
        # 加上K
        # 遍历字符串的总和
        a1 = int("".join([str(i) for i in num])) + k
        return [int(i) for i in str(a1)]


s126 = Solution126()
r126 = s126.addToArrayForm([9, 8, 7, 6], 123)
print(r126)  # [9, 9, 9, 9]


# 127: 剑指 Offer 56 - II. 数组中数字出现的次数 II
# 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
# 示例 1：
# 输入：nums = [3,4,3,3]
# 输出：4
#
# 示例 2：
# 输入：nums = [9,1,7,9,7,9,7]
# 输出：1


class Solution127:
    def singleNumber(self, nums: list[int]) -> int:
        # 计数器
        import collections
        d = [k for k, v in collections.Counter(nums).items() if v == 1]
        return d[0]


s127 = Solution127()
r127 = s127.singleNumber([6, 8, 6, 6, 8, 8, 8, 3])
print(r127)  # 3


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


class Solution128:
    def singleNumbers(self, nums: list[int]) -> list[int]:
        # 计数器
        import collections
        d = [k for k, v in collections.Counter(nums).items() if v == 1]
        return d


s128 = Solution128()
r128 = s128.singleNumbers([4, 1, 4, 6])
print(r128)  # [1, 6]


# 129: 将每个元素替换为右侧最大元素
# 给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
# 完成所有替换操作后，请你返回这个数组。
# 示例 1：
# 输入：arr = [17,18,5,4,6,1]
# 输出：[18,6,6,6,1,-1]
# 解释：
# - 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
# - 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
# - 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
# - 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
# - 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
# - 下标 5 的元素 --> 右侧没有其他元素，替换为 -1
#
# 示例 2：
# 输入：arr = [400]
# 输出：[-1]
# 解释：下标 0 的元素右侧没有其他元素。


class Solution129:
    def replaceElements(self, arr: list[int]) -> list[int]:
        new_list = []
        for i, v in enumerate(arr):
            if i == len(arr) - 1:
                max_num = -1
            else:
                max_num = max(arr[i + 1:])
            new_list.append(max_num)
        return new_list


s129 = Solution129()
r129 = s129.replaceElements([4, 1, 4, 6])
print(r129)  # [6, 6, 6, -1]


# 130: 最常见的单词
# 给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。
# 题目保证至少有一个词不在禁用列表中，而且答案唯一。
# 禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。
# 示例：
# 输入:
# paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
# banned = ["hit"]
# 输出: "ball"
# 解释:
# "hit" 出现了3次，但它是一个禁用的单词。
# "ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。
# 注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"），
# "hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。


class Solution130:
    def mostCommonWord(self, paragraph: str, banned: list[str]) -> str:
        # 计数器
        # 替换,.?
        # 分割句子，计数器
        # 从高到低看是不是在禁用。
        import string
        import collections
        paragraph = paragraph.lower()
        paragraph = paragraph.translate(str.maketrans('', '', string.punctuation))
        new_list = paragraph.split()
        c = collections.Counter(new_list)
        c = c.most_common()
        for i in c:
            if i[0] not in banned:
                return i[0]


s130 = Solution130()
r130 = s130.mostCommonWord("hello world hello python", ["hello", "world"])
print(r130)  # python

微信公众号：玩转测试开发
欢迎关注，共同进步，谢谢！