参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
该用set的时候,还是得用set
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 True ;不是,则返回 False 。
示例:
输入:19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
这道题目看上去貌似一道数学问题,其实并不是!
题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!
正如:关于哈希表,你该了解这些!中所说,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法了。
所以这道题目使用哈希法,来判断这个sum是否重复出现,如果重复了就是return false, 否则一直找到sum为1为止。
判断sum是否重复出现就可以使用unordered_set。
还有一个难点就是求和的过程,如果对取数值各个位上的单数操作不熟悉的话,做这道题也会比较艰难。
C++代码如下:
class Solution {
public:
// 取数值各个位上的单数之和
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 如果这个sum曾经出现过,说明已经陷入了无限循环了,立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
- 时间复杂度: O(logn)
- 空间复杂度: O(logn)
class Solution {
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
while (n != 1 && !record.contains(n)) {
record.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n) {
int res = 0;
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}
(版本一)使用集合
class Solution:
def isHappy(self, n: int) -> bool:
record = set()
while True:
n = self.get_sum(n)
if n == 1:
return True
# 如果中间结果重复出现,说明陷入死循环了,该数不是快乐数
if n in record:
return False
else:
record.add(n)
def get_sum(self,n: int) -> int:
new_num = 0
while n:
n, r = divmod(n, 10)
new_num += r ** 2
return new_num
(版本二)使用集合
class Solution:
def isHappy(self, n: int) -> bool:
record = set()
while n not in record:
record.add(n)
new_num = 0
n_str = str(n)
for i in n_str:
new_num+=int(i)**2
if new_num==1: return True
else: n = new_num
return False
(版本三)使用数组
class Solution:
def isHappy(self, n: int) -> bool:
record = []
while n not in record:
record.append(n)
new_num = 0
n_str = str(n)
for i in n_str:
new_num+=int(i)**2
if new_num==1: return True
else: n = new_num
return False
(版本四)使用快慢指针
class Solution:
def isHappy(self, n: int) -> bool:
slow = n
fast = n
while self.get_sum(fast) != 1 and self.get_sum(self.get_sum(fast)):
slow = self.get_sum(slow)
fast = self.get_sum(self.get_sum(fast))
if slow == fast:
return False
return True
def get_sum(self,n: int) -> int:
new_num = 0
while n:
n, r = divmod(n, 10)
new_num += r ** 2
return new_num
(版本五)使用集合+精简
class Solution:
def isHappy(self, n: int) -> bool:
seen = set()
while n != 1:
n = sum(int(i) ** 2 for i in str(n))
if n in seen:
return False
seen.add(n)
return True
(版本六)使用数组+精简
class Solution:
def isHappy(self, n: int) -> bool:
seen = []
while n != 1:
n = sum(int(i) ** 2 for i in str(n))
if n in seen:
return False
seen.append(n)
return True
func isHappy(n int) bool {
m := make(map[int]bool)
for n != 1 && !m[n] {
n, m[n] = getSum(n), true
}
return n == 1
}
func getSum(n int) int {
sum := 0
for n > 0 {
sum += (n % 10) * (n % 10)
n = n / 10
}
return sum
}
var isHappy = function (n) {
let m = new Map()
const getSum = (num) => {
let sum = 0
while (n) {
sum += (n % 10) ** 2
n = Math.floor(n / 10)
}
return sum
}
while (true) {
// n出现过,证明已陷入无限循环
if (m.has(n)) return false
if (n === 1) return true
m.set(n, 1)
n = getSum(n)
}
}
// 方法二:使用环形链表的思想 说明出现闭环 退出循环
var isHappy = function(n) {
if (getN(n) == 1) return true;
let a = getN(n), b = getN(getN(n));
// 如果 a === b
while (b !== 1 && getN(b) !== 1 && a !== b) {
a = getN(a);
b = getN(getN(b));
}
return b === 1 || getN(b) === 1 ;
};
// 方法三:使用Set()更简洁
/**
* @param {number} n
* @return {boolean}
*/
var getSum = function (n) {
let sum = 0;
while (n) {
sum += (n % 10) ** 2;
n = Math.floor(n/10);
}
return sum;
}
var isHappy = function(n) {
let set = new Set(); // Set() 里的数是惟一的
// 如果在循环中某个值重复出现,说明此时陷入死循环,也就说明这个值不是快乐数
while (n !== 1 && !set.has(n)) {
set.add(n);
n = getSum(n);
}
return n === 1;
};
// 方法四:使用Set(),求和用reduce
var isHappy = function(n) {
let set = new Set();
let totalCount;
while(totalCount !== 1) {
let arr = (''+(totalCount || n)).split('');
totalCount = arr.reduce((total, num) => {
return total + num * num
}, 0)
if (set.has(totalCount)) {
return false;
}
set.add(totalCount);
}
return true;
};
function isHappy(n: number): boolean {
// Utils
// 计算val各位的平方和
function calcSum(val: number): number {
return String(val).split("").reduce((pre, cur) => (pre + Number(cur) * Number(cur)), 0);
}
let storeSet: Set<number> = new Set();
while (n !== 1 && !storeSet.has(n)) {
storeSet.add(n);
n = calcSum(n);
}
return n === 1;
};
// number 每个位置上的数字的平方和
func getSum(_ number: Int) -> Int {
var sum = 0
var num = number
while num > 0 {
let temp = num % 10
sum += (temp * temp)
num /= 10
}
return sum
}
func isHappy(_ n: Int) -> Bool {
var set = Set<Int>()
var num = n
while true {
let sum = self.getSum(num)
if sum == 1 {
return true
}
// 如果这个sum曾经出现过,说明已经陷入了无限循环了
if set.contains(sum) {
return false
} else {
set.insert(sum)
}
num = sum
}
}
class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function isHappy($n) {
// use a set to record sum
// whenever there is a duplicated, stop
// == 1 return true, else false
$table = [];
while ($n != 1 && !isset($table[$n])) {
$table[$n] = 1;
$n = self::getNextN($n);
}
return $n == 1;
}
function getNextN(int $n) {
$res = 0;
while ($n > 0) {
$temp = $n % 10;
$res += $temp * $temp;
$n = floor($n / 10);
}
return $res;
}
}
use std::collections::HashSet;
impl Solution {
pub fn get_sum(mut n: i32) -> i32 {
let mut sum = 0;
while n > 0 {
sum += (n % 10) * (n % 10);
n /= 10;
}
sum
}
pub fn is_happy(n: i32) -> bool {
let mut n = n;
let mut set = HashSet::new();
loop {
let sum = Self::get_sum(n);
if sum == 1 {
return true;
}
if set.contains(&sum) {
return false;
} else { set.insert(sum); }
n = sum;
}
}
}
int get_sum(int n) {
int sum = 0;
div_t n_div = { .quot = n };
while (n_div.quot != 0) {
n_div = div(n_div.quot, 10);
sum += n_div.rem * n_div.rem;
}
return sum;
}
// (版本1)使用数组
bool isHappy(int n) {
// sum = a1^2 + a2^2 + ... ak^2
// first round:
// 1 <= k <= 10
// 1 <= sum <= 1 + 81 * 9 = 730
// second round:
// 1 <= k <= 3
// 1 <= sum <= 36 + 81 * 2 = 198
// third round:
// 1 <= sum <= 81 * 2 = 162
// fourth round:
// 1 <= sum <= 81 * 2 = 162
uint8_t visited[163] = { 0 };
int sum = get_sum(get_sum(n));
int next_n = sum;
while (next_n != 1) {
sum = get_sum(next_n);
if (visited[sum]) return false;
visited[sum] = 1;
next_n = sum;
};
return true;
}
// (版本2)使用快慢指针
bool isHappy(int n) {
int slow = n;
int fast = n;
do {
slow = get_sum(slow);
fast = get_sum(get_sum(fast));
} while (slow != fast);
return (fast == 1);
}
object Solution {
// 引入mutable
import scala.collection.mutable
def isHappy(n: Int): Boolean = {
// 存放每次计算后的结果
val set: mutable.HashSet[Int] = new mutable.HashSet[Int]()
var tmp = n // 因为形参是不可变量,所以需要找到一个临时变量
// 开始进入循环
while (true) {
val sum = getSum(tmp) // 获取这个数每个值的平方和
if (sum == 1) return true // 如果最终等于 1,则返回true
// 如果set里面已经有这个值了,说明进入无限循环,可以返回false,否则添加这个值到set
if (set.contains(sum)) return false
else set.add(sum)
tmp = sum
}
// 最终需要返回值,直接返回个false
false
}
def getSum(n: Int): Int = {
var sum = 0
var tmp = n
while (tmp != 0) {
sum += (tmp % 10) * (tmp % 10)
tmp = tmp / 10
}
sum
}
public class Solution {
private int getSum(int n) {
int sum = 0;
//每位数的换算
while (n > 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
public bool IsHappy(int n) {
HashSet <int> set = new HashSet<int>();
while(n != 1 && !set.Contains(n)) { //判断避免循环
set.Add(n);
n = getSum(n);
}
return n == 1;
}
}
# @param {Integer} n
# @return {Boolean}
def is_happy(n)
@occurred_nums = Set.new
while true
n = next_value(n)
return true if n == 1
return false if @occurred_nums.include?(n)
@occurred_nums << n
end
end
def next_value(n)
n.to_s.chars.sum { |char| char.to_i ** 2 }
end