1.9.10號(hào)每日一題蒸殿，好的優(yōu)化時(shí)間養(yǎng)成的好習(xí)慣比默，使得沒有被暴力卡住
一個(gè)班級(jí)里有 n 個(gè)學(xué)生，編號(hào)為 0 到 n - 1 驼修。每個(gè)學(xué)生會(huì)依次回答問題殿遂，編號(hào)為 0 的學(xué)生先回答，然后是編號(hào)為 1 的學(xué)生乙各，以此類推墨礁，直到編號(hào)為 n - 1 的學(xué)生，然后老師會(huì)重復(fù)這個(gè)過程耳峦，重新從編號(hào)為 0 的學(xué)生開始回答問題恩静。
給你一個(gè)長(zhǎng)度為 n 且下標(biāo)從 0 開始的整數(shù)數(shù)組 chalk 和一個(gè)整數(shù) k 。一開始粉筆盒里總共有 k 支粉筆。當(dāng)編號(hào)為 i 的學(xué)生回答問題時(shí)驶乾，他會(huì)消耗 chalk[i] 支粉筆邑飒。如果剩余粉筆數(shù)量 嚴(yán)格小于 chalk[i] ，那么學(xué)生 i 需要 補(bǔ)充 粉筆级乐。
請(qǐng)你返回需要 補(bǔ)充 粉筆的學(xué)生 編號(hào) 疙咸。
示例 1：
輸入：chalk = [5,1,5], k = 22
輸出：0
解釋：學(xué)生消耗粉筆情況如下：
- 編號(hào)為 0 的學(xué)生使用 5 支粉筆，然后 k = 17 风科。
- 編號(hào)為 1 的學(xué)生使用 1 支粉筆撒轮，然后 k = 16 。
- 編號(hào)為 2 的學(xué)生使用 5 支粉筆丐重，然后 k = 11 腔召。
- 編號(hào)為 0 的學(xué)生使用 5 支粉筆，然后 k = 6 扮惦。
- 編號(hào)為 1 的學(xué)生使用 1 支粉筆臀蛛，然后 k = 5 。
- 編號(hào)為 2 的學(xué)生使用 5 支粉筆崖蜜，然后 k = 0 浊仆。
編號(hào)為 0 的學(xué)生沒有足夠的粉筆，所以他需要補(bǔ)充粉筆豫领。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有抡柿。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處等恐。
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
#按理說應(yīng)該使用二分查找對(duì)值查找更靠譜（排序數(shù)組的快速查找洲劣，
#因?yàn)橥ㄟ^索引查找），而不是遍歷值到答案
while k not in dict_:
k+=1
F=True
return dict_[k] if F else (dict_[k]+1)%n
2.好數(shù)字课蔬，大腦分析囱稽，大致得出了算法的正確性，得益于優(yōu)化算法的好習(xí)慣提交發(fā)現(xiàn)算法的高效性是有的
編寫一個(gè)算法來(lái)判斷一個(gè)數(shù) n 是不是快樂數(shù)二跋。
「快樂數(shù)」定義為：
對(duì)于一個(gè)正整數(shù)战惊，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和。
然后重復(fù)這個(gè)過程直到這個(gè)數(shù)變?yōu)?1扎即，也可能是 無(wú)限循環(huán) 但始終變不到 1吞获。
如果 可以變?yōu)? 1，那么這個(gè)數(shù)就是快樂數(shù)谚鄙。
如果 n 是快樂數(shù)就返回 true 各拷；不是，則返回 false 闷营。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/happy-number
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有烤黍。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
class Solution:
def isHappy(self, n: int) -> bool:
def happyca(n):
ans=0
while n:
ans+=(n%10)**2
n//=10
return ans
#最后到一個(gè)拆分仍為本身的數(shù)
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. 正方形數(shù)組的數(shù)目
難度困難74 收藏 分享 切換為英文 接收動(dòng)態(tài) 反饋
給定一個(gè)非負(fù)整數(shù)數(shù)組A莫杈，如果該數(shù)組每對(duì)相鄰元素之和是一個(gè)完全平方數(shù)互例，則稱這一數(shù)組為正方形數(shù)組。
返回 A 的正方形排列的數(shù)目筝闹。兩個(gè)排列A1和A2不同的充要條件是存在某個(gè)索引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:
#使用二叉樹糊秆，且同一層不能使用相同數(shù)值的元素
#在二叉樹先序遍歷的時(shí)候判斷是否是完全平凡數(shù)
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]
