# -*- coding: utf-8 -*-
# 111: 剑指 Offer II 004. 只出现一次的数字
# 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
# 示例 1：
# 输入：nums = [2,2,3,2]
# 输出：3
#
# 示例 2：
# 输入：nums = [0,1,0,1,0,1,100]
# 输出：100


class Solution111:
    def singleNumber(self, nums: list[int]) -> int:
        import collections
        result = collections.Counter(nums)
        new_list = 0
        for k, v in result.items():
            if v == 1:
                new_list = k
        return new_list


s111 = Solution111()
r111 = s111.singleNumber([0, 1, 0, 1, 0, 1, 8])
print(r111)  # 8


# 112: 数组中重复的数据
# 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
# # 找到所有出现两次的元素。
# # 示例：
# # 输入:
# # [4,3,2,7,8,2,3,1]
# # 输出:
# # [2,3]


class Solution112:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        import collections
        result = collections.Counter(nums)
        new_list = []
        for k, v in result.items():
            if v == 2:
                new_list.append(k)
        return new_list


s112 = Solution112()
r112 = s112.findDuplicates([0, 1, 0, 1, 8])
print(r112)  # [0, 1]


# 113: 面试题 08.07. 无重复字符串的排列组合
# 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
# 示例1:
#  输入：S = "qwe"
#  输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
#
# 示例2:
#  输入：S = "ab"
#  输出：["ab", "ba"]


class Solution113:
    def permutation(self, S: str) -> list[str]:
        from itertools import permutations as per
        new_list = []
        for i in per(S, len(S)):
            new_list.append("".join(i))
        return new_list


s113 = Solution113()
r113 = s113.permutation("abc")
print(r113)  # ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']


# 114: 字符串中的单词数
# 统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
# 请注意，你可以假定字符串里不包括任何不可打印的字符。
# 示例:
# 输入: "Hello, my name is John"
# 输出: 5
# 解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。


class Solution114:
    def countSegments(self, s: str) -> int:
        # s.split()不加任何的时候None  表示移除任何空格，不管是一个两个三个
        return len(s.split())


s114 = Solution114()
r114 = s114.countSegments("Hello, I am Tom. Good afternoon.")
print(r114)  # 6


# 115: 反转单词前缀
# 给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ，反转 word 中从下标 0 开始、
# 直到下标 i 结束（含下标 i ）的那段字符。如果 word 中不存在字符 ch ，则无需进行任何操作。
# 例如，如果 word = "abcdefd" 且 ch = "d" ，那么你应该 反转 从下标 0 开始、直到下标 3 结束（含下标 3 ）。
# 结果字符串将会是 "dcbaefd" 。
# 返回 结果字符串 。
# 示例 1：
# 输入：word = "abcdefd", ch = "d"
# 输出："dcbaefd"
# 解释："d" 第一次出现在下标 3 。
# 反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "dcbaefd" 。
#
# 示例 2：
# 输入：word = "xyxzxe", ch = "z"
# 输出："zxyxxe"
# 解释："z" 第一次也是唯一一次出现是在下标 3 。
# 反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "zxyxxe" 。
#
# 示例 3：
# 输入：word = "abcd", ch = "z"
# 输出："abcd"
# 解释："z" 不存在于 word 中。
# 无需执行反转操作，结果字符串是 "abcd" 。

class Solution115:
    def reversePrefix(self, word: str, ch: str) -> str:
        if ch not in word:
            return word
        else:
            index_ch = word.index(ch)
            if index_ch == len(word) - 1:
                return word[::-1]
            else:
                w1 = word[0:index_ch + 1:]
                w2 = w1[::-1]
                word = w2 + word[index_ch + 1:]
            return word


s115 = Solution115()
r115 = s115.reversePrefix("afternoon", "n")
print(r115)  # nretfaoon


# 116: 二分查找
# 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
# 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
# 示例 1:
# 输入: nums = [-1,0,3,5,9,12], target = 9
# 输出: 4
# 解释: 9 出现在 nums 中并且下标为 4
#
# 示例 2:
# 输入: nums = [-1,0,3,5,9,12], target = 2
# 输出: -1
# 解释: 2 不存在 nums 中因此返回 -1

class Solution116:
    def search(self, nums: list[int], target: int) -> int:
        try:
            r = nums.index(target)
        except:
            r = -1
        return r


s116 = Solution116()
r116 = s116.search([-1, 0, 3, 5, 9, 12], 3)
print(r116)  # 2


# 117: 查找重复的电子邮箱
# 编写一个 SQL 查询，查找 Person 表中所有重复的电子邮箱。
# 示例：
# +----+---------+
# | Id | Email   |
# +----+---------+
# | 1  | a@b.com |
# | 2  | c@d.com |
# | 3  | a@b.com |
# +----+---------+
# 根据以上输入，你的查询应返回以下结果：
# +---------+
# | Email   |
# +---------+
# | a@b.com |
# +---------+

# select Email from Person group by Email having count(Email) > 1;


# 118: 剑指 Offer II 068. 查找插入位置
# 给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，
# 并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
# 请必须使用时间复杂度为 O(log n) 的算法。
# 示例 1:
# 输入: nums = [1,3,5,6], target = 5
# 输出: 2
# 示例 2:
# 输入: nums = [1,3,5,6], target = 2
# 输出: 1

class Solution118:
    def searchInsert(self, nums: list[int], target: int) -> int:
        # 遍历列表
        # 如果为空，插入
        # 如果遍历的元素 小于 目标值，继续遍历
        # 如果遍历的元素 大于等于目标，插入当前元素位置
        # 如果遍历的元素 都小于目标，插入队尾
        r = 0
        if not nums:
            return 0
        else:
            for i, v in enumerate(nums):
                if nums[-1] < target:
                    nums.append(target)
                    return len(nums) - 1

                if v >= target:
                    r = i
                    break
        return r


s118 = Solution118()
r118 = s118.searchInsert([1, 3, 5, 6], 2)
print(r118)  # 1


# 119: 检查单词是否为句中其他单词的前缀
# 给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。
# 请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。
# 如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。
# 如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。
# 如果 searchWord 不是任何单词的前缀，则返回 -1 。
# 字符串 S 的 前缀 是 S 的任何前导连续子字符串。
# 示例 1：
# 输入：sentence = "i love eating burger", searchWord = "burg"
# 输出：4
# 解释："burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。
#
# 示例 2：
# 输入：sentence = "this problem is an easy problem", searchWord = "pro"
# 输出：2
# 解释："pro" 是 "problem" 的前缀，而 "problem" 是句子中第 2 个也是第 6 个单词，但是应该返回最小下标 2 。
#
# 示例 3：
# 输入：sentence = "i am tired", searchWord = "you"
# 输出：-1
# 解释："you" 不是句子中任何单词的前缀。
#
# 示例 4：
# 输入：sentence = "i use triple pillow", searchWord = "pill"
# 输出：4
#
# 示例 5：
# 输入：sentence = "hello from the other side", searchWord = "they"
# 输出：-1

class Solution119:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        # 切割成列表
        # 遍历列表
        # 每一个的startswith
        list1 = sentence.split()
        list1 = [i.startswith(searchWord) for i in list1]
        try:
            print("list1.index(True):", list1.index(True))
            r = list1.index(True) + 1
        except:
            r = -1
        return r


s119 = Solution119()
r119 = s119.isPrefixOfWord("this problem is an easy problem", "pro")
print(r119)  # 2


# 120: 数组中的字符串匹配
# 给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
# 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
# 示例 1：
# 输入：words = ["mass","as","hero","superhero"]
# 输出：["as","hero"]
# 解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
# ["hero","as"] 也是有效的答案。
#
# 示例 2：
# 输入：words = ["leetcode","et","code"]
# 输出：["et","code"]
# 解释："et" 和 "code" 都是 "leetcode" 的子字符串。
#
# 示例 3：
# 输入：words = ["blue","green","bu"]
# 输出：[]

class Solution120:
    def stringMatching(self, words: list[str]) -> list[str]:
        # 新建列表
        # 取出第一个。
        # 遍历除本身的
        # 如果第一个在非本身的，加入列表
        new_list = set()
        for i in words:
            init_word = i

            for j in words:
                if j == i:
                    continue
                else:
                    if j in i:
                        new_list.add(j)
        return list(new_list)


s120 = Solution120()
r120 = s120.stringMatching(["leetcode", "et", "code"])
print(r120)  # ['et', 'code']

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