問題
原文
Write an algorithm to determine if a number
n
is happy.A happy number is a number defined by the following process:
- Starting with any positive integer, replace the number by the sum of the squares of its digits.
- Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
- Those numbers for which this process ends in 1 are happy.
Return
true
ifn
is a happy number, andfalse
if not.
Example 1:
1234567 Input: n = 19Output: trueExplanation:1<sup>2</sup> + 9<sup>2</sup> = 828<sup>2</sup> + 2<sup>2</sup> = 686<sup>2</sup> + 8<sup>2</sup> = 1001<sup>2</sup> + 0<sup>2</sup> + 0<sup>2</sup> = 1Example 2:
12 Input: n = 2Output: false
Constraints:
1 <= n <= 231 - 1
内容
数字nがhappyであるかを判定するアルゴリズムを書いてください。
happy numberは以下のプロセスによって定義されます。
・正の整数を各桁の2乗の合計値に置き換える
・数字が1になるか、1以外の数字で無限ループに入るまで繰り返す
・最終的に1になったらhappy number
happy numberならTrue、そうでなければFalseを返してください。
※正しくない可能性があります。
解答
解答1:Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#整数nから各桁の2乗の合計値を求める #求めた合計値から、さらに各桁の2乗の合計値を求める #上記を繰り返して1になったらハッピーナンバー class Solution: def isHappy(self, n: int) -> bool: #1度処理を実行した数字を格納する変数。無限ループ防止用 visited = set() #nが1以外であり、nがvisitedにない限り繰り返す while n != 1 and n not in visited: #visitedにnを追加 visited.add(n) #temp_nを毎回0にする。 temp_n = 0 #nが0よりも大きい限り繰り返す while n > 0: #n%10はnを10で割った余りを求めている→必ず下一桁を取得できる #pow(n%10, 2)で、nの下一桁の2乗を求めている #temp_nに、上記の処理で求めた値を加える temp_n += pow(n%10, 2) #nを10で割り、下一桁の数字をnから外す。2進数で言うビットシフトと同じ操作に見える #内側のwhileの最後は、nは0になり、temp_nは各桁の2乗の合計値になっている n //= 10 #nにtemp_nの値を代入 n = temp_n return n == 1 |
・1つ目のwhile文では、nが1以外であり、まだ出現していない数なら処理を繰り返している。
・temp_nはnの各桁の二乗の合計を保持する変数。
・2つ目のwhile文が終了するまでは保持しておき、1つ目のwhile文で次のループに移った時に0で初期化する。こうしないと、前回のnの合計数値をもちこしてしまう。
・出現した数字をvisitedに加えて記録しておき、1つ目のwhile文の次回のループを始める前に判定を行う。
・2つ目のwhile文の内部では、各桁の二乗の合計値を求めている。
・nの数字の1桁目を、%を使って求め、これを二乗して変数に加える。
・nは//を使って1桁目を除外している
解答2:Python, 英語コメント
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#Input number is n. #We need to return True if sum of squares of each digit is 1. #In any other case, we need to return False. class Solution: def isHappy(self, n: int) -> bool: #keep number once occured in loop. occured_number = set() #do loop while n is not 1 while n!=1: #Initialize a variable to store the sum of squares of each digit in every loop sum_of_squares = 0 #If n has cccurred once, return False. if n in occured_number: return False #Add n to occured_number variable. occured_number.add(n) #Calculate the sum of squares of each digit # while n>0: #obtain one's place number last_digit = n%10 #exclude first digit from n n = n // 10 #Add square of last_digit variable sum_of_squares += last_digit**2 #Assign sum_of_squares to n n = sum_of_squares #if n is 1, escape loop and return True return True |
解き方は解答1と同じ。
英語での練習の表現用
メモ・参考・感想
■メモ
今更ながら、かつ初歩的だけど「n//=10」の操作で2進数のビットシフトのイメージをつかんだかもしれない。
・2進数のビットシフトを行うと、桁が1つ下がり、10進数では半分の数字になる。
・10進数を10で割ると、桁が1つ下がり、10進数で10分の1の数字になる。
前:637. Average of Levels in Binary Tree
次:1523. Count Odd Numbers in an Interval Range
LeeetCodeの問題をアルゴリズムとデータ構造による分類
コメント