---

面试题 08.04. 幂集

中等
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。

示例:
输入： nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

class S0804:def func(self,nums):res=[]def dfs(path,used,startIndex):res.append(path[:])if len(path)==len(nums):returnfor i in range(startIndex,len(nums)):if i>=0 and nums[i]==nums[i-1] and used[i-1]==False:continueif used[i]==True:continueused[i]=Truepath.append(nums[i])dfs(path,used,i)used[i]=Falsepath.pop()dfs([],[False]*len(nums),0)return resr=S0804()
nums=[1,2,3]
print(r.func(nums))

367. 有效的完全平方数

简单

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。

示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

class S367:def func(self,num):left=1right=numwhile left<=right:mid=(left+right)//2if mid*mid==num:return Trueelif mid*mid<num:left=mid+1else:right=mid-1return Falser=S367()
num=14
print(r.func(num))

192. 统计词频

中等
写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。
为了简单起见，你可以假设：
words.txt只包括小写字母和 ’ ’ 。
每个单词只由小写字母组成。
单词间由一个或多个空格字符分隔。
示例:
假设 words.txt 内容如下：
the day is sunny the the
the sunny is is
你的脚本应当输出（以词频降序排列）：

the 4
is 3
sunny 2
day 1

class S192:def func(self):with open('word.txt',mode='r',encoding='utf-8') as f:res=f.read()ans=res.split()a=Counter(ans)for k,v in a.items():print(k,v)r=S192()
r.func()

747. 至少是其他数字两倍的最大数

简单

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

示例 1：
输入：nums = [3,6,1,0]
输出：1
解释：6 是最大的整数，对于数组中的其他整数，6 至少是数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。

示例 2：
输入：nums = [1,2,3,4]
输出：-1
解释：4 没有超过 3 的两倍大，所以返回 -1 。

class S747:def func(self, nums):new = sorted(nums)  # todo 递增if new[-1] >= nums[-2] * 2:  # todo 比较最后1个数和倒数第2个数return nums.index(new[-1])  # todo 如果满足的话在原列表中求索引else:return -1r = S747()
nums = [1, 2, 3, 4]
print(r.func(nums))

718. 最长重复子数组

中等
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

class Solution718:def func(self, nums1, nums2):nums1.sort()nums2.sort()i = 0j = 0res = []while i < len(nums1) and j < len(nums2):if nums1[i] > nums2[j]:j += 1elif nums1[i] < nums2[j]:i += 1else:res.append(nums1[i])i += 1j += 1return resr = Solution718()
nums1 = [0,0,0,0,0]
nums2 = [0,0,0,0,0]
print(r.func(nums1, nums2))

---