LeetCode12~14 Integer to Roman/Roman to Integer/Longest Common Prefix

淡淡的烟草味﹌ 2022-08-07 11:58 26阅读 0赞

**一：Integer to Roman**

题目：

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

链接：https://leetcode.com/problems/integer-to-roman/

分析：此题关键是确定罗马数字如何表示，比如4并不是IIII而是IV，9并不是VIIII而是IX, 通过不断的取出最高位和余下的得到结果

代码：

class Solution {
    public:
        // 关键在于4 9 400 等表示方式的不同
        string intToRoman(int num) {
            string roman[13] ={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};  // 确定相互之间的对应关系
            int arabic[13] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
            string result;
            for(int i = 0; i < 13; i++){
                int fac = num/arabic[i];   // 取出最高位，不是按照十进制/10
                for(int j = 0; j < fac; j++){
                    result += roman[i];
                }
                num = num % arabic[i];   // 余下的
            }
            return result;
            
        }
    
    };

**二：**

###  ###

Roman to Integer

题目：

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

链接：https://leetcode.com/problems/roman-to-integer/

分析：这个更简单，只要分析当前字符串中字符位与后面一位对应大小关系判断是否为4,9等这样的特殊情况进行判断就可以了。

class Solution {
    public:
        Solution(){
            string roman ={"MDCLXVI"};
            int arabic[7] = {1000,500,100,50,10,5,1};
            for(int i = 0; i < 7; i++){
                hmap.insert(pair<char,int>(roman[i], arabic[i]));    // 确定两者对应关系
            }
        }
        int romanToInt(string s) {
           int result = 0;
           int i = 0;
           if(s.size() == 0) return 0;
           if(s.size() == 1) return hmap[s[0]];
           while(i < s.size()){
                int x1 = hmap[s[i]];
                int x2 = hmap[s[i+1]];
                if(x1 >= x2){                   // 大于 正常
                    result += x1;
                    i = i+1;
                }
                else {                       // 小于 不正常说明是4 9 400 900 等这些数字
                    result += x2-x1;
                    i = i+2;
                }
            }
            return result;
        }
    private:
        map<char, int> hmap;
    };

**三：Longest Common Prefix**

题目：

Write a function to find the longest common prefix string amongst an array of strings.

链接：https://leetcode.com/problems/longest-common-prefix/

分析：此题就是求最长公共前缀，这个可以采用hash\_set, 用第一个字符串的所有前缀建立一个set，然后对于后面每个字符串，看他的前缀是否在hash\_set中，不在则判断是否比之前的preCommon小，小则取最短的

代码：

class Solution {
    public:
        string longestCommonPrefix(vector<string> &strs) {
            if(strs.size() <= 0) return "";
            set<string> hset;
            string str0 = strs[0];
            int preCommon =  str0.size();
            for(int i = 0; i < str0.size(); i++){  // 第一个字符串的前缀建立一个hash_set
                hset.insert(str0.substr(0,i+1));
            }
            for(int i = 1; i < strs.size(); i++){
                string str = strs[i];
                 preCommon = min(preCommon, (int)str.size());   // 公共前缀肯定是字符串中最短的
                 if(preCommon == 0) break;
                for(int j = 0; j < str.size(); j++){
                    if(!hset.count(str.substr(0,j+1))){         // 判断是否为前面字符串的前缀 O(1)时间搞定
                       preCommon = min(preCommon, j);      // hash_set中不存在了 则为最短
                       break;
                    }
                }
            }
            return str0.substr(0, preCommon);
        }
    };