首页 > 代码库 > IT公司100题-26-左旋转字符串

IT公司100题-26-左旋转字符串

2024-07-18 19:12:44   219人阅读

问题描述：
给定字符串和左旋的字符数，写程序实现字符串的左旋操作。例如对于字符串”12345678″, 左旋转4个字符后，变成”56781234″。要求时间复杂度为O(n)，空间复杂度O(1)。
 
分析：
假设字符串表示为XY，X表示需要左旋的部分，左旋后字符串表示为YX。
根据公式：1
 

代码实现：

 1 // 26.cc 2 #include <iostream> 3 #include <string> 4 #include <cstring> 5 using namespace std; 6  7 // 反转字符串 8 void reverse_str(char* start, char* end) { 9     if (!start || !end)10         return;11     while (start < end) {12         swap(*start, *end);13         start++;14         end--;15     }16 }17 18 // 左移k个字符19 void left_rotate_str(char*& str, size_t k) {20     if (!str || k <= 0)21         return;22 23     size_t n = strlen(str);24     k = k % n;25     26     reverse_str(str, str + k - 1);27     reverse_str(str + k, str + n - 1);28     reverse_str(str, str + n - 1);29 }30 31 int main() {32     cout << "input a str:" << endl;33 34     string s;35     getline(cin, s);36 37     char* str = new char[s.size() + 1];38     strcpy(str, s.c_str());39     int k = 5 < s.size() ? 5 : 0;40     left_rotate_str(str, k);41 42     cout << "after left rotate " << k << " chars:" << endl << str << endl;43     return 0;44 }

输出：

$ ./a.exeinput a str:12345678after left rotate 5 chars:67812345

 


联系
我们