【LeetCode简单题选手】简单的数学题(8.1)

  时间:2020-08-02 13:26:48  阅读量:52  评论数:0  作者:看,未来

该篇文章介绍【LeetCode简单题选手】简单的数学题(8.1),除了讲述概念知识,还有代码分析,想了解这类技术的可以参考阅读,提高水平。

快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。

示例:

输入:19
输出:true
解释:
12   92 = 82
82   22 = 68
62   82 = 100
12   02   02 = 1

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xw99u7/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路

不知为何,这找不到官方题解了,所以,只能锻炼一下我的语文表达能力了。

思路一:枚举
经过上面的操作,肯定要经过10以内的数,那就把10以内的不快乐数枚举出来,后面每次运算时都去比对一下,看看是不是快乐数。
为什么要经过10以内的数?因为照那样的运算方式,总会进入100吧,100以内的数都会有进入10的一次的,这个可以放心。
粗略的看了一下,10以内的不快乐数只有4。

思路二:每次结果纪录并比对
如果那个数不快乐,那么肯定会形成圈,那就把匹配快乐数时经过的数纪录到数组中,然后每次经过的时候比对一下,看看有没有重复,有重复就是不快乐数了。

代码实现(自然是最简单的)

bool isHappy(int n) {

        while(n>0){
            int number = 0;
            while(n){
                number  = (n % 10) * (n % 10);
                n/=10;
            }

            if(number == 1)
                return true;
            else if(number == 4)
                return false;
            n = number;

        }
        return true;
    }

阶乘后的零

给定一个整数 n,返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xwehi5/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路

其实很简单,几个5的倍数就几个0。

代码实现

int trailingZeroes(int n) {
        int count = 0;
        for( ; n/5>=1;){
            count = count   n/5;
            n = n/5;
        }
        return count;
    }

分数到小数

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

如果小数部分为循环小数,则将循环的部分括在括号内。

示例 1:

输入: numerator = 1, denominator = 2
输出: "0.5"
示例 2:

输入: numerator = 2, denominator = 1
输出: "2"
示例 3:

输入: numerator = 2, denominator = 3
输出: "0.(6)"

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xwm8ne/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路

1、可以写成分数的都是有理数,而有理数要么是有限的,要么是无限循环小数
2、由于还存在正负情况,处理方式是按正数处理,符号最后在判断
3、由于整型数INT的取值范围是-2147483648~2147483647,而对-2147483648取绝对值就会超出范围,所以我们需要先转为long long型再取绝对值
4、找循环:得到一个数字后要看看之前有没有出现这个数
5、还有一个小技巧,由于我们要算出小数每一位,采取的方法是每次把余数乘10,再除以除数,得到的商即为小数的下一位数字。等到新算出来的数字在之前出现过,则在循环开始出加左括号,结束处加右括号。

代码实现

string fractionToDecimal(int numerator, int denominator) {
        int s1 = numerator >= 0 ? 1 : -1;
        int s2 = denominator >= 0 ? 1 : -1;
        long long num = abs( (long long)numerator );
        long long den = abs( (long long)denominator );
        long long out = num / den;
        long long rem = num % den;
        unordered_map<long long, int> m;
        string res = to_string(out);
        if (s1 * s2 == -1 && (out > 0 || rem > 0)) res = "-"   res;
        if (rem == 0) return res;
        res  = ".";
        string s = "";
        int pos = 0;
        while (rem != 0) {
            if (m.find(rem) != m.end()) {
                s.insert(m[rem], "(");
                s  = ")";
                return res   s;
            }
            m[rem] = pos;
            s  = to_string((rem * 10) / den);
            rem = (rem * 10) % den;
              pos;
        }
        return res   s;
    }

关键词:leetcode,算法,简单,选手,简单的,数学,数学题