| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (62.47%) | 868 | - |
airbnb | twitter | uber
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
提示：
1 <= n <= 231 - 1麒麒先说明一下，题解1和题解2都没有beat100%，题解3才优化到beat100%
主要思路是先将取n的字符串形式s,再遍历s,其中使用HashMap类型的变量map的key来保存s的元素，value来保存个数，于是然后再遍历map，将key对应的元素处理，逐个平方相加再乘于value个数就得到新的n值。当n的小于10时，判断n是否等于1，是，则返回true;反之添加到集合set里面，如果set以及存在了，那么就返回false.
前提引入：
- 先使用一个集合set来保存n小于10的情况，当小于10，如果没有等于1，那么就变成该小于10的值；
- 用s字符串类型变量来保存n的字符串形式；
- 使用
HashMap<Character, Integer>类型的map来处理s的每一个元素
分析过程：
- 因为每次处理后的n最终一定会小于10，因此在外层循环的结构体里使用一个判断当（n小于10时），如果等于1则返回true，反之,则添加到集合set里面，如果set也添加不了，就说明该n值重复了，题目的n并不是快乐数
- 先构造n的字符串形式s，再逐个遍历s的字符c，遍历时，
- 当字符c不存在于map的key里面，就添加该key，并且相应的value赋值为1；
- 如果map的key有值，就对应的value加1；
- 更新n值（先改为0）；
- 遍历该map:
for (char c : map.keySet())
- 定义变量num为n的某一位数:
int num = c - '0';- 取该位数的个数，用count来记录：
int count = map.get(c);- map的keySet的每个值的遍历时都要跟新n:
n += num * num * count;- 每一次都需要清空map，防止原来的值影响。
class Solution {
public boolean isHappy(int n) {
HashMap<Character, Integer> map = new HashMap<>();
HashSet<Integer> set = new HashSet<>();
while (true) {
if(n < 10){
if(n == 1){return true;}
if(!set.add(n)){
return false;
}
}
String s = n + "";
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
int i = map.get(c);
map.replace(c, i + 1);
} else {
map.put(c, 1);
}
}
n = 0;
for (char c : map.keySet()) {
int count = map.get(c);
int num = c - '0';
n += num * num * count;
}
map.clear();
}
}
}
优化思路：寻找出n<10时可以满足最终结果为1的整数（放到idea里面测试啦）；然后就可以在题解里改变一下判断条件：在循环迭代过程中使得n<10时，当n为1或7，便返回true;反之false.(注意，该题比较特殊，因此可以这样优化。)
如下图：
class Solution {
public boolean isHappy(int n) {
HashMap<Character, Integer> map = new HashMap<>();
while (true) {
if(n < 10){
if(n == 1 || n == 7){
return true;
}else{
return false;
}
}
String s = n + "";
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
int i = map.get(c);
map.replace(c, i + 1);
} else {
map.put(c, 1);
}
}
int sum = 0;
for (char c : map.keySet()) {
int count = map.get(c);
int num = c - '0';
sum += num * num * count;
}
n = sum;
map.clear();
}
}
}
还是换回普通思路比较好，麒麒终于成功了，下面题解的思路分析和xin麒写的这片文章的实际上一样的：
leetcode使用java解题202快乐数,beat100%
还有的是这个还是有些冗余的代码，于是麒麒打算后面找时间优化下。
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet<>();
while (true) {
if(n <= 10){
if(n == 1 || n == 7 || n == 10){
return true;
}else{
return false;
}
}
int sum = 0;
int count = 0;
while (n >= 10) {
int ren = n % 10;
if (ren != 0){
count = 1;
}
sum += ren * ren;
n /= 10;
}
if (count == 0 && n == 10){return true;}
sum += n * n;
n = sum;
}
}
}
