[刷题]剑指offer之左旋转字符串

news/2024/7/5 4:54:54

题目

题目：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移n位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

思路

这个题乍一看超级简单，将左边的长度为n的子字符串拿出来，拼接在字符串的后面即可。

代码一

class Solution {
public:
    string LeftRotateString(string str, int n) {
        string str1 = str.substr(0,n);
        string str2 = str.substr(n);
        return str2+str1;
    }
};

然后提交之后通过不了。。。terminate called after throwing an instance of 'std::out_of_range' what(): basic_string::substr: __pos (which is 6) > this->size() (which is 0) 。意思就是str的大小是0，却索引了字符串的第6位。

代码二

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(str.length() == 0)
            return str;
        string str1 = str.substr(0,n);
        string str2 = str.substr(n);
        return str2+str1;
    }
};

修改代码后，就通过了。但是仔细想一想，n有可能比字符串的长度大，这个时候还是可能发生越界，但是这题的案例应该没设计好，没有暴露问题！如果n大于str.length()，左移n位其实就相当于左移n % str.length()位。

代码三

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(str.length() == 0)
            return str;
        n %= str.size();
        string str1 = str.substr(0,n);
        string str2 = str.substr(n);
        return str2+str1;
    }
};

修改完之后代码就算是完美了，各种情况都考虑到了。

注意

如果想到了n可能大于字符串的长度，却没有想到字符串可能为空，那么n %= str.length()就会报浮点错误:您的程序运行时发生浮点错误，比如遇到了除以 0 的情况 的错误。

C++求子串

std::string::substr

Returns a substring [pos, pos+count). If the requested substring extends past the end of the string, or if count == npos, the returned substring is [pos, size()).

Parameters
pos - position of the first character to include
count - length of the substring

Return value
String containing the substring [pos, pos+count).

Exceptions
std::out_of_range if pos > size()

Complexity
Linear in count

Important points

The index of the first character is 0 (not 1).
If pos is equal to the string length, the function returns an empty string.
If pos is greater than the string length, it throws out_of_range. If this happen, there are no changes in the string.
If for the requested sub-string len is greater than size of string, then returned sub-string is [pos, size()).