整数转罗马数字

问题描述

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:
输入: 3
输出: "III"

示例 2:
输入: 4
输出: "IV"

示例 3:
输入: 9
输出: "IX"

示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman

思路

思路很简单，就是从最高位开始抽离每一位进行计算。

题解

class Solution {
public:
   string intToRoman(int num) {
        string ret;
        if (num > 3999 || num < 1) return ret;
        else {
            int tmp1=num/1000;
            int tmp11= num % 1000;
            int tmp2=tmp11/100;
            int tmp21=tmp11%100;
            int tmp3= tmp21/10;
            int tmp31=tmp21%10;
            for(int i=0;i<tmp1;i++){
                ret+="M";
            }
            if(tmp2==4){
                ret+="CD";
            } else if(tmp2==9){
                ret+="CM";
            } else if(tmp2<5){
                for(int i=0;i<tmp2;i++){
                    ret+="C";
                }
            } else if(5<=tmp2){
                ret+="D";
                for(int i=0;i<tmp2-5;i++){
                    {
                        ret+="C";
                    }
                }
            }
            if(tmp3==4){
                ret+="XL";
            } else if(tmp3==9){
                ret+="XC";
            } else if(tmp3<5){
                for(int i=0;i<tmp3;i++){
                    ret+="X";
                }
            } else if(5<=tmp3){
                ret+="L";
                for(int i=0;i<tmp3-5;i++){
                    {
                        ret+="X";
                    }
                }
            }
            if(tmp31==4){
                ret+="IV";
            } else if(tmp31==9){
                ret+="IX";
            } else if(tmp31<5){
                for(int i=0;i<tmp31;i++){
                    ret+="I";
                }
            } else if(5<=tmp31){
                ret+="V";
                for(int i=0;i<tmp31-5;i++){
                    {
                        ret+="I";
                    }
                }
            }

        }
        return ret;
    }
};

字符串相加

问题描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-strings

思路

和两数相加的思路一样

题解

class Solution {
public:
    string addStrings(string num1, string num2) {
        int len1=num1.length();
        int len2=num2.length();
        string ret="";
        int array=0;
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        if(len1<len2){
            for(int i=0;i<len1;i++){
                ret+=to_string(((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)%10);
                array=((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)/10;
            }
            for(int i=len1;i<len2;i++){
                ret+=to_string(((int)(num2[i]-'0')+array)%10);
                array=(array+(int)(num2[i])-'0')/10;
            }
            if(array==1){
                ret+="1";
            }

        }else if(len1>len2){
            for(int i=0;i<len2;i++){
                ret+=to_string(((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)%10);
                array=((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)/10;
            }
            for(int i=len2;i<len1;i++){
                ret+=to_string(((int)(num1[i]-'0')+array)%10);
                array=(array+(int)(num1[i])-'0')/10;
            }
            if(array==1){
                ret+="1";
            }

        } else{
            for(int i=0;i<len2;i++){
                ret+=to_string(((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)%10);
                array=((num1[i]-'0')+(int)(num2[i]-'0')+array)/10;
            }
            if(array==1){
                ret+="1";
            }
        }
        reverse(ret.begin(),ret.end());
        return  ret;
    }
};

看到一个很简单的实现。感觉自己还是很菜很菜的，向大佬学习...

class Solution {
public:
    string addStrings(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        int i = m - 1, j = n - 1, carry = 0;
        string ret = "";
        while (j >= 0 || i >= 0 || carry != 0) {
            if (i >= 0) carry += num1[i--] - '0';
            if (j >= 0) carry += num2[j--] - '0';
            ret += carry % 10 + '0';
            carry /= 10;
        }

        // 翻转字符串
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

作者：autuanliu
链接：https://leetcode-cn.com/problems/two-sum/solution/shu-shi-ji-suan-by-autuanliu/

字符串相乘

问题描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"

说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multiply-strings

思路

字符串num1的长度是m，字符串num2的长度是n，两个字符串相乘的结果的长度肯定不会超过m+n；因此结果ret的大小申请为m+n，并将每一个字符都初始化为0；

然后根据竖式计算的计算方法，可以得出
ret[i+j+1]=((ret[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0')) %10 +'0';
其中 (ret[i + j + 1] - '0')是之前的进位。
ret[i + j] = ( (ret[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0')/10;
为进位

因为最开始ret申请的大小为n+m，如果num1和num2比较小的话，前边肯定有0空余，因此需要从第一个不为'0'的位置开始截取出返回结果ret。

题解

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.length(), n = num2.length();
        string ret(m + n, '0');  // 所有的进位初始化为 '0'
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                // 进位和乘积的和，当前要加上上一步计算的进位
                int sum = (ret[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');
                ret[i + j + 1] = (sum % 10) + '0';  // 保存当前计算的数字(低位)
                ret[i + j] += sum / 10;  // 更新当前进位(高位)
            }
        }

        // 从第一个不为 '0' 的字符开始是有效结果或者结果是个位数
        for (int i = 0; i < ret.length(); i++) {
            if (ret[i] != '0')
                return ret.substr(i);  // 从 i 到最后的子字符串
        }
        return "0";
    }
};

字符串解码

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string

思路

遇到这种括号匹配的问题，自然会想到用栈解决。
在遇到左括号前，将重复的次数存储在num中。
遇到左括号入栈，并将num清0。
将左括号之后，右括号之前的字母存到ret中。
碰到左括号入栈，并将并将num、ret清0。
如此重复，在遇到右括号的时候，将nums.top()次【因为数字在最内层括号的左边】的ret【要重复的部分还没入栈】，加到strs.top()中，然后令ret=str.top()作为新一次的需要重复的部分,在这个过程中别忘记弹出nums.pop()、strs.pop()。
重复以上步骤即可。

题解

class Solution {
public:
    string decodeString(string s) {
        string ret = "";
        int len = s.length();
        int num = 0;
        stack<int> nums;
        stack<string> strs;
        for (int i = 0; i < len; i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + s[i] - '0';
            } else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
            { ret = ret + s[i]; }
            else if (s[i] == '[') {
                nums.push(num);
                num = 0;
                strs.push(ret);
                ret = "";
            } else {
                int tmp=nums.top();
                nums.pop();
                for(int j=0;j<tmp;j++){
                    strs.top()=strs.top()+ret;
                }
                ret=strs.top();
                strs.pop();
            }
        }
        return ret;
    }
};

最大数

问题描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:
输入: [10,2]
输出: 210

示例 2:
输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-number

思路

将int数组转化为字符串，将字符串按从大到小的顺序排序，这里需要注意的是手写cmp比较字符串的大小时，用return str1+str2>str2+str1;将排序好的string类型的数组拼接成一个字符串。最后必须要进行除0操作。如"00"->"0","0123"->"123"

题解

class Solution {
public:
    static  bool cmp(string str1,string str2){
        return str1+str2>str2+str1;
    }
    string largestNumber(vector<int>& nums) {
        vector<string> tmp;
        for(int i=0;i<nums.size();i++){
            tmp.push_back(to_string(nums[i]));
        }
        string ret="";
        int n=tmp.size();
        sort(tmp.begin(),tmp.end(),cmp);
        for(int i=0;i<n;i++){
            ret+=tmp[i];
        }
        int flag=0;
        int location=0;
        for(int i=0;i<ret.size();i++){
            if(ret[i]!='0'){
                flag=1;
                location=i;
                break;
            }
        }
        if(flag==0) ret="0";
        else{
            string ret1="";
            for(int i=location;i<ret.size();i++){
                ret1+=ret[i];
            }
            ret=ret1;
        }
        return ret;
    }
};