算法练习week1--leetcode16

标签: leetcode

题目介绍

本周联系简单的字符串数组问题,选取leetcode13进行练习。简单来说,就是将罗马文转换为整数数字。题目截图如下。

算法设计

我们可以从题目看出,罗马字母和整数一一对应,一个罗马字母对应一个整数或者一对罗马字母对应一个整数,因此我们只需要从前到后遍历整个字符串,将字母和数字对应并求和即可。可以看到一对字母对应一个整数的状况,因此我们必须从前到后按两个一组实现对应关系,这样一个一个往后退到末尾为止。

一些坑

这道题一开始打的时候还挺顺手,测试了一些例子均的出正确结果,但是放到leetcode上跑的时候却出现wrong answer。其实需要特别注意的是,字符串数组类题目一定到考虑到边界条件!这道题存在的边界条件主要有以下3个:

  • 字符串长度为1
  • 字符串最后一位字母是否匹配成对
  • 字符串最后两位字母是否匹配成对

如何解决这些问题呢?针对上诉三个条件主要由下面的一些措施解决:

  • 将字符串长度为1是单独判断
  • 设置flag值以标记最后一位是否被匹配。除此之位,在匹配最后一对后,判断s[i]是否指向最后一位以作判断。

代码

int romanToInt(string s) {
    bool flag = true;
    int number = 0;
    string temp;
    for(int i = 0;i < s.size()-1;i++) {
        flag = true;
        temp = s[i];
        temp += s[i+1];
        cout << temp << endl;
        if(temp == "IV") {
            number += 4;
            i++;
            if(i == s.size()-2){
                flag= false;
            }
        }else if(temp == "IX") {
            number += 9;
            i++;
            if(i == s.size()-2){
                flag= false;
            }
        }else if(temp == "XL") {
            number += 40;
            i++;
            if(i == s.size()-2){
                flag= false;
            }
        }else if(temp == "XC") {
            number += 90;
            i++;
            if(i == s.size()-2){
                flag= false;
            }
        }else if(temp == "CD") {
            number += 400;
            i++;
            if(i == s.size()-2){
                flag= false;
            }
        }else if(temp == "CM") {
            number += 900;
            i++;
            if(i == s.size()-2){
                flag= false;
            }
        }else{
            flag = false;
            switch(s[i]){
                case 'I': number += 1; break;
                case 'V': number += 5; break;
                case 'X': number += 10; break;
                case 'L': number += 50; break;
                case 'C': number += 100; break;
                case 'D': number += 500; break; 
                case 'M': number += 1000; break;
                default: number += 0; break;
            }
        }
    }

    if(!flag || (s.size() == 1)){
        switch(s[s.size()-1]){
            case 'I': number += 1; break;
            case 'V': number += 5; break;
            case 'X': number += 10; break;
            case 'L': number += 50; break;
            case 'C': number += 100; break;
            case 'D': number += 500; break;
            case 'M': number += 1000; break;
            default: number += 0; break;
        }
    }   

    return number;
}

 

原文链接:加载失败,请重新获取