# -*- coding: utf-8 -*-
# 101: 剑指 Offer 15. 二进制中1的个数
# 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为
# '1'
# 的个数（也被称为
# 汉明重量).）。
# 示例 1：
# 输入：n = 11 (控制台输入 00000000000000000000000000001011)
# 输出：3
# 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
#
# 示例 2：
# 输入：n = 128 (控制台输入 00000000000000000000000010000000)
# 输出：1
# 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
#
# 示例 3：
# 输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
# 输出：31
# 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
class Solution101:
def hammingWeight(self, n: int) -> int:
# 转二进制
# 直接获取1的次数
return bin(n).count("1")
s101 = Solution101()
r101 = s101.hammingWeight(99)
print(r101) # 4
# 102: 剑指 Offer II 083. 没有重复元素集合的全排列
# 给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
# 示例 1：
# 输入：nums = [1,2,3]
# 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
#
# 示例 2：
# 输入：nums = [0,1]
# 输出：[[0,1],[1,0]]
#
# 示例 3：
# 输入：nums = [1]
# 输出：[[1]]
class Solution102:
def permute(self, nums: list[int]) -> list[list[int]]:
import itertools
new_list = []
for i in itertools.permutations(nums, len(nums)):
new_list.append(list(i))
return new_list
s102 = Solution102()
r102 = s102.permute([1, 2, 3])
print(r102) # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
# 103: 子集
# 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
# 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
# 示例 1：
# 输入：nums = [1,2,3]
# 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
#
# 示例 2：
# 输入：nums = [0]
# 输出：[[],[0]]
class Solution103:
def subsets(self, nums: list[int]) -> list[list[int]]:
new_list = []
new_list.append([])
new_list.append(nums)
import itertools
for i in range(1, len(nums)):
for j in itertools.combinations(nums, i):
new_list.append(list(j))
return new_list
s103 = Solution103()
r103 = s103.subsets([1, 2])
print(r103) # [[], [1, 2], [1], [2]]
# 104: 剑指 Offer II 084. 含有重复元素集合的全排列
# 给定一个可包含重复数字的整数集合
# nums ，按任意顺序
# 返回它所有不重复的全排列。
# 示例 1：
# 输入：nums = [1,1,2]
# 输出：
# [[1,1,2],
# [1,2,1],
# [2,1,1]]
#
# 示例 2：
# 输入：nums = [1,2,3]
# 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution104:
def permuteUnique(self, nums: list[int]) -> list[list[int]]:
import itertools
new_list = set()
for i in itertools.permutations(nums, len(nums)):
a = list(i)
new_list.add(i)
new_list = list(new_list)
return [list(i) for i in new_list]
s104 = Solution104()
r104 = s104.permuteUnique([1, 2])
print(r104) # [[1, 2], [2, 1]]
# 105: 排列序列
# 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
# 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
# "123"
# "132"
# "213"
# "231"
# "312"
# "321"
# 给定 n 和 k，返回第 k 个排列。
# 示例 1：
# 输入：n = 3, k = 3
# 输出："213"
#
# 示例 2：
# 输入：n = 4, k = 9
# 输出："2314"
#
# 示例 3：
# 输入：n = 3, k = 1
# 输出："123"
class Solution105:
def getPermutation(self, n: int, k: int) -> str:
# 全排列
# 变成数字，排序
# 取出
s = "".join([str(i) for i in range(1, n + 1)])
import itertools
new_list = []
for i in itertools.permutations(s, len(s)):
new_list.append("".join(list(i)))
new_list = [int(i) for i in new_list]
new_list.sort()
return str(new_list[k - 1])
s105 = Solution105()
r105 = s105.getPermutation(5, 2)
print(r105) # 12354
# 106: 剑指 Offer 38. 字符串的排列
# 输入一个字符串，打印出该字符串中字符的所有排列。
# 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
# 示例:
# 输入：s = "abc"
# 输出：["abc","acb","bac","bca","cab","cba"]
class Solution106:
def permutation(self, s: str) -> list[str]:
import itertools
words = []
for i in itertools.permutations(s, len(s)):
words.append("".join(list(i)))
init_set = set()
for i in words:
if i not in init_set:
init_set.add(i)
words = list(init_set)
return words
s106 = Solution106()
r106 = s106.permutation("six")
print(r106) # ['isx', 'ixs', 'sxi', 'xis', 'six', 'xsi']
# 107: 将句子排序
# 一个 句子 指的是一个序列的单词用单个空格连接起来，且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。
# 我们可以给一个句子添加 从 1 开始的单词位置索引 ，并且将句子中所有单词 打乱顺序 。
# 比方说，句子 "This is a sentence" 可以被打乱顺序得到 "sentence4 a3 is2 This1" 或者 "is2 sentence4 This1 a3" 。
# 给你一个 打乱顺序 的句子 s ，它包含的单词不超过 9 个，请你重新构造并得到原本顺序的句子。
# 示例 1：
# 输入：s = "is2 sentence4 This1 a3"
# 输出："This is a sentence"
# 解释：将 s 中的单词按照初始位置排序，得到 "This1 is2 a3 sentence4" ，然后删除数字。
#
# 示例 2：
# 输入：s = "Myself2 Me1 I4 and3"
# 输出："Me Myself and I"
# 解释：将 s 中的单词按照初始位置排序，得到 "Me1 Myself2 and3 I4" ，然后删除数字。
class Solution107:
def sortSentence(self, s: str) -> str:
# 1、变成列表，存储每个单词和数字
# 2、key = 数字，v = 单词。
# 3、按顺序取
new_list = s.split(" ")
d = {int(i[-1]): i[:-1] for i in new_list}
list1 = list(d.keys())
list1.sort()
list2 = [d[i] for i in list1]
r = " ".join(list2)
return r
s107 = Solution107()
r107 = s107.sortSentence("Myself2 Me1 I4 and3")
print(r107) # Me Myself and I
# 108: 面试题 16.02. 单词频率
# 设计一个方法，找出任意指定单词在一本书中的出现频率。
# 你的实现应该支持如下操作：
# WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
# get(word)查询指定单词在书中出现的频率
# 示例：
# WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});
# wordsFrequency.get("you"); //返回0，"you"没有出现过
# wordsFrequency.get("have"); //返回2，"have"出现2次
# wordsFrequency.get("an"); //返回1
# wordsFrequency.get("apple"); //返回1
# wordsFrequency.get("pen"); //返回1
class WordsFrequency:
def __init__(self, book: list[str]):
import collections
self.book_dict = collections.Counter(book)
def get(self, word: str) -> int:
return self.book_dict.get(word, 0)
s108 = WordsFrequency(["i", "have", "an", "apple", "he", "have", "a", "pen"])
r1081 = s108.get("I")
r1082 = s108.get("have")
print(r1081) # 0
print(r1082) # 2
# 109: 只出现一次的数字 III
# 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
# 进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
# 示例 1：
# 输入：nums = [1,2,1,3,2,5]
# 输出：[3,5]
# 解释：[5, 3] 也是有效的答案。
#
# 示例 2：
# 输入：nums = [-1,0]
# 输出：[-1,0]
#
# 示例 3：
# 输入：nums = [0,1]
# 输出：[1,0]
class Solution109:
def singleNumber(self, nums: list[int]) -> list[int]:
import collections
result = collections.Counter(nums)
new_list = []
for k, v in result.items():
if v == 1:
new_list.append(k)
return new_list
s109 = Solution109()
r109 = s109.singleNumber([1, 2, 1, 9, 2, 5, 2])
print(r109) # [9, 5]
# 110: 只出现一次的数字 II
# 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
# 示例 1：
# 输入：nums = [2,2,3,2]
# 输出：3
#
# 示例 2：
# 输入：nums = [0,1,0,1,0,1,99]
# 输出：99
class Solution110:
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
s110 = Solution110()
r110 = s110.singleNumber([0, 1, 0, 1, 0, 1, 88])
print(r110) # 88
微信公众号：玩转测试开发
欢迎关注，共同进步，谢谢！
