这里写目录标题
- 面试题 08.04. 幂集
- 367. 有效的完全平方数
- 192. 统计词频
- 747. 至少是其他数字两倍的最大数
- 718. 最长重复子数组
面试题 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):
return
for i in range(startIndex,len(nums)):
if i>=0 and nums[i]==nums[i-1] and used[i-1]==False:
continue
if used[i]==True:
continue
used[i]=True
path.append(nums[i])
dfs(path,used,i)
used[i]=False
path.pop()
dfs([],[False]*len(nums),0)
return res
r=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=1
right=num
while left<=right:
mid=(left+right)//2
if mid*mid==num:
return True
elif mid*mid<num:
left=mid+1
else:
right=mid-1
return False
r=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 -1
r = 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 = 0
j = 0
res = []
while i < len(nums1) and j < len(nums2):
if nums1[i] > nums2[j]:
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
res.append(nums1[i])
i += 1
j += 1
return res
r = Solution718()
nums1 = [0,0,0,0,0]
nums2 = [0,0,0,0,0]
print(r.func(nums1, nums2))
