[LeetCode]Math主题系列{第7，9，13，273题}

昊楠Hacking

发布于 2018-03-30 10:22:51

7150

发布于 2018-03-30 10:22:51

文章被收录于专栏：专注数据中心高性能网络技术研发专注数据中心高性能网络技术研发专注数据中心高性能网络技术研发

1.内容介绍

本篇文章记录在leetcode中Math主题下面的题目和自己的思考以及优化过程，具体内容层次按照{题目，分析，初解，初解结果，优化解，优化解结果，反思}的格式来记录，供日后复习和反思[注：有些题目的解法比较单一，就没有优化过程]。题目的顺序按照leetcode给出的题目顺序，有些题目在并不是按照题目本身序号顺序排列的，也不是严格按照难易程度来排列的。

因此，这篇文章并不具有很强的归类总结性，归类总结性知识将会在其他文章记录，本篇重点在记录解题过程中的思路，希望能对自己有所启发。

2.题目和解题过程

2.1 Reverse Integer

题目：Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
分析：题目求解需要对给定的32bit整数进行逐位提取然后逆序生成，其中包含了对逆序溢出和前置0的边界检查。
初解：要提取最低位值需要取模运算，而提取每一位上的值则需要将该位移动到最低位上，例如：321，提取1执行321%10，提取2执行32%10，提取3执行3%10。因此每次提取到最低位的值之后需要对原有的值进行低位截断，也就是整除10操作。而原有的值与逆序之后的值的权重序列正好相反，也就是说3的权重由原来的100变为逆序后的1,2的权重由原来的10变为逆序后的10,1的权重由原来的1变为逆序后的100,。这可以用一个递归的过程来描述：对每一位上的值提取需要从后向前计算，而逆序数每一位权重的生成则需要从前向后计算。符合先进后出的逻辑。计算出新的逆序数之后判断是否溢出的原理是：32位整数如果溢出后，该32bit代表的值与原来的值不同，因此可以先用一个64位数来计算逆序数，然后转存到32位数上，再对两者进行对比检查是否相等即可。

class Solution {
public:
    int reverse(int x) {
        if(x==0)
            return 0;
        bool flag = true;
        if(x<0)
        {
            flag = false;
            x = -x;
        } 
        int times = 1;
        long re_val = re(x, times);
        int tmp = re_val;
        if(tmp != re_val)
            return 0;
        if(flag==false)
            tmp = -tmp;
        return tmp;
    }
    long re(int val, int& times)
    {
        if(val == 0)
            return 0;
        long extract_val = val % 10;
        val = val/10;
        long res = re(val, times);
        if(val != 0)
            times = times * 10;
        res += extract_val * times;
        return res;
    }
};

初解结果：

反思：逆序的逻辑与栈后进先出的逻辑相似。

2.2 Palindrome Number

题目：Determine whether an integer is a palindrome. Do this without extra space.
分析：回文数的性质是数值按位对称，12321中3是对称中心，12和21分别按位对称。那么判断是否是回文数就可以从两端位值进行对比直到相遇。
初解：先计算给定的数有几位，然后分别从高位向下递减和从低位向上递增，提取高位和低位的值作对比，使用递归或迭代均可。

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 10 && x >=0 )
            return true;
        if(x < 0 || x == 10)
            return false;
        int front = 1, val = x, end = 1;
        while(1)
        {
            val = val / 10;
            if(val != 0)
                front = front * 10;
            else break;
        }
        return judge_bit(x, front, end);
    }
    bool judge_bit(int x, int front, int end)
    {
        if(front > end)
        {
            if(((x / front) % 10) == ((x / end) % 10))
            {
                if(judge_bit(x, front / 10, end * 10) == true)
                    return true;
                else return false;
            }
            else return false;
        }
        else return true;
    }
};

初解结果：

反思：熟悉递归和迭代的性质。

2.3 Integer to Roman

题目：Given an integer, convert it to a roman numeral.Input is guaranteed to be within the range from 1 to 3999.
分析：罗马数的表示单位值是1000,500,100,50,10,5,1，分别对应于字母M,D,C,L,X,V,I。每个相同单位不能连续出现超过3次，比如：3是III，而4是VI。而且每个值只有一种表示形式，必须以大值单位优先表达。
初解：对于给定的整数值，先从大值单位开始计算该单位上对应的数，然后检查此数落在哪个范围：[0,3]，[4,8]，[9]；然后予以不同的处理。最后将该数乘以对应的单位值保存起来向后累加，值得注意的是需要跳过500,50,5这三个单位，因为这样才能使得每个单位上的数落在上述范围内。

class Solution {
public:
    string intToRoman(int num) {
        char unit[7] ={'M','D','C','L','X','V','I'};
        int  val[7]  ={1000,500,100,50,10,5,1};
        string res = "";
        int unit_index = 0;
        while(num != 0)
        {
            int multiple = num / val[unit_index];
            if( multiple > 0 ) 
            {
                switch(multiple)
                {
                    case 1:res+=unit[unit_index];break;
                    case 2:res+=string(2,unit[unit_index]);break;
                    case 3:res+=string(3,unit[unit_index]);break;
                    case 4:res+=string(1,unit[unit_index])+string(1,unit[unit_index-1]);break;
                    case 5:res+=unit[unit_index-1];break;
                    case 6:res+=string(1,unit[unit_index-1])+string(1,unit[unit_index]);break;
                    case 7:res+=string(1,unit[unit_index-1])+string(2,unit[unit_index]);break;
                    case 8:res+=string(1,unit[unit_index-1])+string(3,unit[unit_index]);break;
                    case 9:res+=string(1,unit[unit_index])+string(1,unit[unit_index-2]);break;
                }
            }
            num = num - multiple * val[unit_index];
            unit_index += 2;
        }
        return res;
    }
};

初解结果：

反思：严密分析题目逻辑最重要。

2.3 Roman to Integer

题目：Given a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.
分析：给定的罗马数字符串序列中，每个字符代表一个权重值，而权重大的在权重小的前面时是相加操作，相反则是相减操作。
初解：

class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        unordered_map<char, int> flag_val;
        flag_val['I'] = 1;
        flag_val['X'] = 10;
        flag_val['C'] = 100;
        flag_val['V'] = 5;
        flag_val['L'] = 50;
        flag_val['D'] = 500;
        flag_val['M'] = 1000;
        
        for(int i = 0; i < s.size(); ++i)
        {
            if(i+1 < s.size())
            {
                if(flag_val[s[i]] >= flag_val[s[i+1]])
                    res += flag_val[s[i]];
                else res -= flag_val[s[i]];
            }
            else res += flag_val[s[i]];
        }
        return res;
    }
};

初解结果：

反思：。。。

2.4 Integer to English Words

题目： Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.For example, 123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
分析：英文中是以1000为倍率单位向上增长的，低于1000的单位是0*1000，一百万到1000之间的单位是n×1000，高于一百万但低于10亿的单位是n×1000*1000*1000。其次提取每一个范围内各个位的数即可。
初解：从1000以内开始提取个位，十位，百位上面的数，然后截断低三位的数，重新提取低三位的值，更新此范围的大单位值。

class Solution {
public:
    string numberToWords(int num) {
        if(num == 0)
            return string("Zero");
        
        string unit[] = {"Zero"," One", " Two", " Three", " Four"," Five"," Six"," Seven"," Eight"," Nine"," Ten"," Eleven"," Twelve"," Thirteen"," Fourteen"," Fifteen"," Sixteen"," Seventeen"," Eighteen"," Nineteen"};
        string decade[] = {"Zero"," Ten"," Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"};
        string radix[] = {""," Thousand"," Million"," Billion"};
        int radix_index = 0;
        string res = "";
        while(num != 0)
        {
            int a = num % 100, b = num % 10, c = (num / 10) % 10, d = (num / 100) % 10;
            string tmp = "";
            if(a < 20 && a != 0)
            {
                tmp = unit[a];
            }
            else
            {
                if(b != 0)
                    tmp = unit[b];
                if(c != 0)
                    tmp = decade[c] + tmp;
            }
            if(d != 0)
                tmp = unit[d] + string(" Hundred") + tmp;
            if(a !=0 || b!=0 || c!=0 || d!=0)
                res = tmp + radix[radix_index] + res;
            num = num / 1000;
            ++radix_index;
        }
        return res.substr(1,res.size());
    }
};

初解结果：

反思：数学类型的题目要抓住数字规律即可。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

[LeetCode]Math主题系列{第7，9，13，273题}

[LeetCode]Math主题系列{第7，9，13，273题}

1.内容介绍

2.题目和解题过程

2.1 Reverse Integer

2.2 Palindrome Number

2.3 Integer to Roman

2.3 Roman to Integer

2.4 Integer to English Words

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐