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è)長度為 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ǔ)充 粉筆。
請你返回需要 補(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ǔ)充粉筆。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

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è)算法來判斷一個(gè)數(shù) n 是不是快樂數(shù)。
「快樂數(shù)」定義為：
對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和。
然后重復(fù)這個(gè)過程直到這個(gè)數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。
如果 可以變?yōu)? 1，那么這個(gè)數(shù)就是快樂數(shù)。
如果 n 是快樂數(shù)就返回 true ；不是，則返回 false 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/happy-number
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

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]