字符串的常见操作

1.char*和char[]的区别
2.字符串的转换
3.字符串比较
- 用“==”比较的结果
4.子串（string）
5.反转
- 反转一个整数
  - 转换成字符串实现
  - 直接对整数操作实现
6.有序字符串（数组）去重
7.旋转字符串（或数组）
- 方法1
- 方法2
- 方法3
8.字符串的分割

1.char*和char[]的区别

一般来讲，我们有两种方式声明一个字符数组：

char* s1 = "Hello";
char s2[10] = "Hello";

这两种写法的区别是，s1是一个指针变量（4 bytes），它被存在栈中指向我们初始化的字符串，而此时字符串在我们的代码内存中，因此我们无法通过下标对任何字符做修改，因此这里编译器会建议我们在前面加上const，但是可以让这个指针指向别的字符串。s2声明为一个数组（10 bytes），和其他类型的数组如整形数组并无区别。

2.字符串的转换

很多函数需要我们输入的是一个char*的字符数组而非string，这时我们就需要将二者相互转换的方法。

string转char*

第一种可行的方法是使用c_str()，它会返回一个const char*。

std::string str = "string";
const char* cstr = str.c_str();

第二种是使用data()，并将结果转换为char*：

string str = "abc";
char* p = (char*)str.data();

char*转string

如果我们需要将char*转换成string，可以利用string的构造函数：

const char *s = "Hello, World!";
string str(s);

string转整数

string s = "123";
int a = atoi(s.c_str());

atoi接收的是一个字符型数组（C-string），c_str可以将string转化为const char *，注意c_str返回的是一个const char*而不是char* p，因此如果需要将其转化为字符数组要先new一个空间出来，再用strcpy将其拷贝过去。

3.字符串比较

这是很常规的一个操作，使用strcmp函数实现，它依次比较两个字符串的字符，返回值有三种可能：

<0: the first character that does not match has a lower value in ptr1 than in ptr2
0: the contents of both strings are equal
>0: the first character that does not match has a greater value in ptr1 than in ptr2

注意这里输入的应该是char*。例如：

bool comp(Info info1, Info info2) {
    // 先按分数排序
    if (info1.score != info2.score)
        return info1.score > info2.score;
    char* a = (char*)info1.name.data();
    char* b = (char*)info2.name.data();
    // 再按名字字母顺序排序
    return strcmp(a, b);
}

如果我们需要比较两个string类型的字符串，可以用string::compare：

str1.compare(str2)

类似的，如果它们完全相同返回0，第一个不相同的字符值比第二个大返回>0，反之小于零。如果需要，也可以输入参数pos和len比较子串。

用“==”比较的结果

char str1[] = "abc";
char str2[] = "abc";
const char str3[] = "abc";
const char str4[] = "abc";
const char* str5 = "abc";
const char* str6 = "abc";
char* str7 = "abc";
char* str8 = "abc";
cout << (str1 == str2) << endl;
cout << (str3 == str4) << endl;
cout << (str5 == str6) << endl;
cout << (str7 == str8) << endl;

以上代码会输出 0 0 1 1 ，也就是说指针会指向同一块内存，不论是否为常量。

4.子串（string）

使用std::string::substr在字符串中提取子串，该函数定义为string substr(size_t pos, size_t len) const;。下面是用法：

int main () {
    std::string str="We think in generalities, but we live in details."; // (quoting Alfred N. Whitehead)
    std::string str2 = str.substr (3,5);     // "think"
    std::size_t pos = str.find("live");      // position of "live" in str
    std::string str3 = str.substr (pos);     // get from "live" to the end
    std::cout << str2 << ' ' << str3 << '\n';
    return 0;
}

输出：

think live in details.

5.反转

顾名思义，将输入的字符串完全反向，然后输出。如abcd输出dcba。

要实现这个并不难，只需要循环的交换头尾元素即可。

void reverseString(vector<char>& s) {
    int i = 0, j = s.size() - 1;
    if(s.size() == 0)
        return;
    while(i < j){
        swap(s[i], s[j]);
        i++;
        j--;
    }
}

反转一个整数

转换成字符串实现

我们可以用翻转字符串的思路来实现，先将输入的整数转换成字符串，用翻转字符串的方法翻转过后再转换回整数。整数转换成字符串可以直接用to_string函数，当然还有其他方法：

使用itoa()：

int a = 10;
char *intStr = itoa(a);
string str = string(intStr);

或者使用字符串流：

int a = 10;
stringstream ss;
ss << a;
string str = ss.str();

直接对整数操作实现

思路很简单，初始化sum = 0，通过对输入的整数对10取余得到个位数，加上sum * 10，然后除以10抹掉最后一位，重复上述操作，直到取到0为止。

int reverse(int x) {
    long long temp = (long long)x;
    if(x < 0)
        temp = -1 * temp;
    long long res = 0;
    while(temp){
        long long dig = temp % 10;
        res = res * 10 + dig;
        temp /= 10;
    }
    // 如果题目要求答案范围不超出+-2^31
    if(res > pow(2,31) || res < -pow(2, 31) + 1)
        return 0;
    return x > 0 ? res : res * -1;
}

6.有序字符串（数组）去重

void del_duplicates(string& s) {
    int count = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == s[i - 1]) {
            count++;
        }
        else {
            s[i - count] = s[i];
        }
    }
    s = s.substr(0, s.size() - count);
}

注意这个写法只能给排好序的字符串或者数组去重，也就是说删去的是连续的重复元素，如abbbc就会删除中间的两个b。思路很简单，用一个count记录重复元素的个数（这里字符串的字符和数组的元素表示方法一样），如果发现重复元素则count++，

7.旋转字符串（或数组）

旋转分左旋和右旋，说简单点就是左移和右移，每次移动最后一位给到开头补齐，要完成这个操作，至少有三种方法。

方法1

通过三次反转完成。以右移为例，如果如果要把 1234567 右移三位，会得到 5671234 ，如果我们直接对原数（或字符串）翻转，会得到 7654321，可以看到前三位和后四位的元素已经和右移的结果一样，只是顺序反了，这时我们只需要分别翻转前三位和后四位，就可以得到右移的结果。因此我们需要对普通的翻转函数进行修改。让它可以只翻转字符串中的一部分：

void reverse(string& s, int left, int right){
    if(left < 0 || right >= s.size())
        return;
    while(left < right){
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

void rotate_right(string& s, int k){
    int n = s.size();
    if(n <= 1)
        return;
    k %= n; // 保证 k 比 n 小
    reverse(s, 0, n - 1);
    reverse(s, 0, k - 1);
    reverse(s, k, n - 1);
}

void rotate_left(string& s, int k){
    int n = s.size();
    if(n <= 1)
        return;
    k %= n; // 保证 k 比 n 小
    reverse(s, 0, n - 1);
    reverse(s, 0, n - k - 1);
    reverse(s, n - k, n - 1);
}

这种方法的时间复杂度是O(n)，消耗常数的空间。

方法2

声明一个新的数组，然后按左右移动的顺序依次改写得到答案，这样做时间和空间复杂度都是O(n)。这里可以用求余的性质：

nums[(i + k)%n] = numsCopy[i];

方法3

将数组中前 k 位和后 k 位的元素调换位置，如果是要右移的话，那么前 k 个元素已经就位，剩下的需要把右边剩下的元素向右移三位，我们可以在子数组中重复刚才的操作，再次交换，直到只剩下一个元素，这个过程很明显可以用递归实现，但是需要小心其中的细节：

void rotate(vector<int>& nums, int k) {
    if(k == 0 || nums.size() == 1)
        return;
    int n = nums.size();
    k = k % n;
    rotate_recursion(nums, 0, n - 1, k);
}

void rotate_recursion(vector<int> &nums, int l, int r, int k){
    if(k == 0)
        return;
    int n = nums.size();
    k = k % (r - l + 1);
    if(l > n - 1)
        return;
    int left = l;
    for(int i = 0; i < k; i++){
        if(l > n - 1 || r - k + 1 < left)
            break;
        swap(nums[l++], nums[r++ - k + 1]);
    }
    rotate_recursion(nums, left + k, n - 1, k);
}

8.字符串的分割

用关键词strtok将字符数组按输入的一个或多个字符分割成不同字符，如需分割出超过一个，则后续需输入NULL而非数组。

string s = "THis is a - str,ing,.";
char* p = new char[s.length() + 1];
p = strcpy(p, s.c_str());
char* pch = strtok(p, " ,");
while (pch != NULL) {
    cout << pch << endl;
    pch = strtok(NULL, " ,");
}