1.9.10号每日一题，好的优化时间养成的好习惯，使得没有被暴力卡住
一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。
给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。
请你返回需要 补充 粉笔的学生 编号 。
示例 1：
输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
n=len(chalk)
R,F=chalk[0],False
dict_={R:0}
for i in range(1,n):
R+=chalk[i]
dict_[R]=i
k%=R
#按理说应该使用二分查找对值查找更靠谱（排序数组的快速查找，
#因为通过索引查找），而不是遍历值到答案
while k not in dict_:
k+=1
F=True
return dict_[k] if F else (dict_[k]+1)%n
2.好数字，大脑分析，大致得出了算法的正确性，得益于优化算法的好习惯提交发现算法的高效性是有的
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/happy-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def isHappy(self, n: int) -> bool:
def happyca(n):
ans=0
while n:
ans+=(n%10)**2
n//=10
return ans
#最后到一个拆分仍为本身的数
dict_=set()
while n!=1:
new=happyca(n)
if new in dict_:
return False
n=new
dict_.add(n)
if n==1:
return True
稍加分析，一遍过掉hard题，且可以保证算法的高效性
996. 正方形数组的数目
难度困难74 收藏 分享 切换为英文 接收动态 反馈
给定一个非负整数数组A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
返回 A 的正方形排列的数目。两个排列A1和A2不同的充要条件是存在某个索引i，使得 A1[i] != A2[i]。
示例 1：
输入：[1,17,8]
输出：2
解释：
[1,8,17] 和 [17,8,1] 都是有效的排列。
示例 2：
输入：[2,2,2]
输出：1
class Solution:
def numSquarefulPerms(self, nums: List[int]) -> int:
#使用二叉树，且同一层不能使用相同数值的元素
#在二叉树先序遍历的时候判断是否是完全平凡数
ans=[0]
n=len(nums)
isvisited=[False]*n
def dfs(isvisited,cnt,re,i):
if i==-1:
hash_set=set()
for j in range(n):
if not isvisited[j] and nums[j] not in hash_set:
hash_set.add(nums[j])
isvisited[j]=True
dfs(isvisited,cnt+1,re,j)
isvisited[j]=False
else:
per_judge=re+nums[i]
if int(math.sqrt(per_judge))**2==per_judge:
if cnt==n:
ans[0]+=1
return
else:
hash_set=set()
for j in range(n):
if not isvisited[j] and nums[j] not in hash_set:
hash_set.add(nums[j])
isvisited[j]=True
dfs(isvisited,cnt+1,nums[i],j)
isvisited[j]=False
hash_set=set()
for i in range(n):
if nums[i] not in hash_set:
#print('hi')
#print(hash_set)
hash_set.add(nums[i])
isvisited[i]=True
dfs(isvisited,1,nums[i],-1)
isvisited[i]=False
return ans[0]
