コード:口語聴解作文-7


まず、私は好きなように頭を働かせました.まず、問題から見ると、
https://leetcode.com/problems/perfect-squares/

まず不思議なことに、このような問題を見て、数学で何かをしたいと思っています.また、実はBFS部分にこのような問題があるのに、どうしてこのような問題をBFS事故と見なすことができますか?このような考えで頭が痛くて時間を過ごしました.そこで,以下の方法を試みた.
from collections import deque
def numSquares(n):
    q = deque()
    for i in range(int(n ** 0.5), 0, -1):
        q.append(i)
    while q:
        count = 0
        Yerin = q.popleft()
        Baek = Yerin * Yerin
        if (n - Baek) % 2 == 0:
            count += 1
            new_n = n - Baek
            if new_n % Yerin == 0:
                count += (new_n // Yerin)
        elif (n - Baek) % 2 == 1:
            continue
        return count
print(numSquares(12))
芸琳とBaekが平方なので白芸琳のSquaresを思い出しましたそのまま自分で貼り付けました.とにかく、数学で何かできると思うので、できるだけやりました.まずはデックを使いました.そして別のBFSを開くとマザン各地、whileゲートが回転し、popleft()は、毎回1つの数を抽出し、forゲートとifゲートによって条件を満たす.私が思いついた条件は以下の通りです.まずn以下の可平方数を求める.12なら1 2 3はこんな感じしかし、逆順で考えるので3.2.1です.なぜなら、25の場合、5平方で終わるので、そうすると、答えは1です.一度で終わりしたがって,逆順で行い,配布時に余剰部分がない場合はもう一度チェックする.平方で除算できるかどうか見てみましょう.これで総数を以下のように数えた.しかし、答えは出なかった.例えば、それを回すと、ずっと5が出てきます.そして私は1時間以上数学でどうすればいいか考えて、近づいたときに答えを見ました.ふん.
class Solution:
    def numSquares(self, n):

        # list of square numbers that are less than `n`
        square_nums = [i * i for i in range(1, int(n**0.5)+1)]
    
        level = 0
        queue = {n}
        while queue:
            level += 1
            #! Important: use set() instead of list() to eliminate the redundancy,
            # which would even provide a 5-times speedup, 200ms vs. 1000ms.
            next_queue = set()
            # construct the queue for the next level
            for remainder in queue:
                for square_num in square_nums:    
                    if remainder == square_num:
                        return level  # find the node!
                    elif remainder < square_num:
                        break
                    else:
                        next_queue.add(remainder - square_num)
            queue = next_queue
        return level
この主なアプローチは、まず12と言うときに、3つの平方数の数字が現れることです.1, 2, 3. これらの数字の共通点は、それぞれの平方であってもよい.しかも12以下です.1, 4, 9 < 13. これをコードで解くために、誰もが出します.準数に加えて、平方数が可能かどうかも考慮します.13-1=12は不可能です.11は平方数の和ではありません.13-4=93の平方和.13-9=4-2の平方和.可能であれば、以下の数字level+=1を使用できます.次に2番目の平方の和はlevel+=1...このようにifドアとforドアを組み合わせて一列に下りていきます.それがその答え.ここまで来るとほとんど思い付くのがもったいない