Xoay chuỗi trong c + +?

Question

Tôi đang tìm cách xoay chuỗi bằng C++. Tôi dành tất cả thời gian của tôi trong python, vì vậy C++ của tôi là rất gỉ.

Đây là những gì tôi muốn nó làm: nếu tôi có một chuỗi 'abcde' tôi muốn nó thay đổi thành 'bcdea' (ký tự đầu tiên di chuyển đến cùng). Đây là cách tôi đã làm điều đó trong python:

def rotate(s): 
    return s[1:] + s[:1] 

Tôi không chắc chắn làm thế nào để làm điều đó trong cpp. Có thể sử dụng một loạt các ký tự?

Answer 1

Tôi khuyên bạn nên std::rotate:

std::rotate(s.begin(), s.begin() + 1, s.end()); 

Answer 2

Đây là giải pháp "nổi" ký tự đầu tiên vào cuối chuỗi, giống như một lần lặp lại kiểu bong bóng đơn lẻ.

#include <algorithm> 

string rotate(string s) { 
    for (int i = 1; i < s.size(); i++) 
    swap(s[i-1], s[i]); 
    return s; 
} 

nếu bạn muốn chức năng để xoay chuỗi tại chỗ:

#include <algorithm> 

void rotate(string &s) { 
    for (int i = 1; i < s.size(); i++) 
    swap(s[i-1], s[i]); 
} 

Answer 3

Đây là một cách tương đối đơn giản:

void RotateStringInPlace(char buffer[]) 
{ 
    // Get the length of the string. 

    int len = strlen(buffer); 
    if (len == 0) { 
     return; 
    } 

    // Save the first character, it's going to be overwritten. 

    char tmp = buffer[0]; 

    // Slide the rest of the string over by one position. 

    memmove(&buffer[0], &buffer[1], len - 1); 

    // Put the character we saved from the front of the string in place. 

    buffer[len - 1] = tmp; 
    return; 
} 

Lưu ý rằng điều này sẽ thay đổi bộ đệm tại chỗ.

Answer 4

Thực hiện yêu cầu chưa?

Nếu không, bạn có lẽ tốt nhất nên lấy một chuỗi con của tất cả trừ char thứ nhất và sau đó chắp thêm char đầu tiên vào cuối.

Answer 5

Có một rotate chức năng tiêu chuẩn tìm trong tiêu đề thuật toán.
Nếu bạn muốn làm điều này cho mình, bạn có thể thử như sau:

#include <iostream> 
#include <string> 

std::string rotate_string(std::string s) { 
    char first = s[0]; 

    s.assign(s, 1, s.size() - 1); 
    s.append(1, first); 

    return s; 
} 

int main() { 
    std::string foo("abcde"); 

    std::cout << foo << "\t" << rotate_string(foo) << std::endl; 

    return 0; 
} 

Nhưng tất nhiên, bằng cách sử dụng thư viện chuẩn là một lợi thế ở đây, và trong hầu hết các trường hợp.

EDIT: Tôi vừa xem câu trả lời của câu trả lời. Đánh bại một lần nữa!
EDIT # 2: Tôi chỉ muốn đề cập đến hàm rotate_string bị lỗi trên chuỗi có độ dài 0. Bạn sẽ nhận được lỗi std :: out_of_range. Bạn có thể khắc phục điều này bằng khối try/catch đơn giản hoặc sử dụng std :: rotate :-)

Answer 6

Nếu bạn không muốn các giải pháp tại chỗ này, thì mã python của bạn có thể được dịch trực tiếp sang C++, với bit của mã phụ để đối phó với thực tế là chỉ số ngoài giới hạn là tin xấu trong C++.

s[1:] --> s.substr(1); 
s[:1] --> s[0]; // s[0] is a char not a string, but that's good enough 

Vì vậy,

std::string rotate(const std::string &s) { 
    if (s.size() > 0) return s.substr(1) + s[0]; 
    return s; 
} 

Đây không phải là hiệu quả nhất: nó gần như chắc chắn sẽ làm tạo ra chuỗi hơn mức tối thiểu có thể. Nhưng bạn thường không cần hiệu quả nhất, và bạn có reserve và append nếu bạn muốn kết nối mà không cần phân bổ không cần thiết.

Answer 7

Tại một số điểm tôi đã bị ám ảnh với chia để trị, và sử dụng như sau

vì nó 'chia' các vấn đề để vấn đề nhỏ hơn tôi đoán là điều này thực hiện tốt hơn. Nhận xét của chuyên gia về hành vi truy cập bộ nhớ phức tạp và bộ nhớ được chào đón :).

Initial Call: 
rotate_about(rots_g, 0, i, j - 2); 


void rotate_about(char *str, int start, int pivot, int end) 
{ 
    if(pivot == start) 
    { 
     return ; 
    } 
    else if((pivot - start) <= (end - pivot)) 
    { 
     int move_bytes = pivot-start; 
     swap_bytes(&str[start], &str[pivot],move_bytes); 
     rotate_about(str,pivot,pivot+move_bytes,end); 
    } 
    else 
    { 
     int move_bytes = end - pivot + 1; 
     swap_bytes(&str[start], &str[pivot],move_bytes); 
     rotate_about(str, start+move_bytes ,pivot,end); 
    } 
} 

Answer 8

Đây là mã trong C mà không sử dụng bất kỳ chức năng bên ngoài: Nó xoay chuỗi tại chỗ cả phía trước và phía sau bởi bất kỳ giá trị bất kể có bao lớn.

int stringRotate(int value) 
    { 
    unsigned long I,J,K; 
    unsigned long index0; 
    unsigned long temp1,temp2; 
    unsigned long length; 

    length = stringLength; 

    if (value < 0) 
    value = length - ((0 - value) % length); 

    if (value > length) 
    value = value % length; 

    J = 0; 
    index0 = J; 
    temp1 = stringData[J]; 

    for (I = 0;I < length;I++) 
    { 
    K = (J + value) % length; 
    temp2 = stringData[K]; 
    stringData[K] = temp1; 

    J = K; 

    temp1 = temp2; 

    if (J == index0) 
     { 
     J++; 
     index0 = J; 
     temp1 = stringData[J]; 
     } 
    } 

    return 1; 
    } 

Để xoay chuỗi cả phía trước và phía sau sẽ là một chút tẻ nhạt vì thế nó là tốt hơn để chỉ làm phía trước xoay và tính giá trị chính xác cho backwards.Also nếu giá trị luân chuyển là hơn độ dài của chuỗi , sau đó chúng tôi có thể chỉ cần clip nó kể từ khi kết quả sẽ là như nhau anyway.

giá trị = chiều dài - ((0 - giá trị)% length): có nghĩa là giá trị xoay là âm, sau đó đặt giá trị cho độ dài của chuỗi, trừ đi kết quả tích cực của phần còn lại chia giá trị chiều dài của chuỗi. Ví dụ: xoay một chuỗi có độ dài từ 10 đến 9 vị trí sẽ giống như xoay vòng +1. Xoay cùng một chuỗi bởi -19 vị trí cũng sẽ giống như xoay theo cộng một. giá trị = value% length: có nghĩa là nếu giá trị dương lớn hơn chiều dài chuỗi, sau đó chia cho độ dài chuỗi và lấy phần còn lại. Kết quả sẽ giống như khi chúng tôi làm điều đó một chặng đường dài.

Để thực hiện xoay vòng tại chỗ, chúng tôi sẽ cần phải nhảy theo giá trị của vòng xoay để trao đổi các ký tự cách xa nhau. Chúng tôi bắt đầu ở vị trí 0, di chuyển về phía trước bởi giá trị xoay và tiếp tục nhảy theo số lượng đó. nếu chúng ta đi qua phần cuối của chuỗi, chúng ta chỉ đơn giản là quấn lại từ đầu. Vấn đề là nếu giá trị là một số chẵn, chúng ta sẽ kết thúc đúng nơi chúng ta bắt đầu và sẽ bỏ lỡ tất cả các ký tự lẻ. Biến index0 là ở đó để cho biết chúng ta bắt đầu từ đâu. Nếu chúng ta quay trở lại chỉ số này thì chúng ta cần tiến lên một vị trí chỉ số và tiếp tục nhảy. Chúng tôi tiếp tục làm điều này cho đến khi tất cả các ký tự được hoán đổi Tại thời điểm này, chúng tôi cần hai biến tạm thời để thực hiện hoán đổi tại chỗ. J là vị trí bắt đầu. Chúng ta di chuyển ký tự ở chỉ mục J đến biến tạm thời đầu tiên. Bây giờ chúng tôi lặp tôi đến độ dài của chuỗi. K là chỉ mục đích, J cộng với giá trị xoay Được bọc quanh đầu nếu cần. Di chuyển ký tự ở chỉ mục K sang biến tạm thời thứ hai. Đặt ký tự từ chỉ mục J vào chỉ mục K bằng biến tạm thời đầu tiên. Bằng cách này, lý do tại sao chúng ta không chỉ di chuyển nhân vật trực tiếp từ chỉ mục J vào chỉ mục K là vì phần cuối của vòng lặp, các chỉ số có thể thay đổi giữa các vòng nhưng các ký tự trong temp1 không nên. Bây giờ chúng ta trao đổi temp1 với temp2. Phần cuối cùng này là nơi giá trị là số chẵn và chúng tôi quay lại nơi chúng tôi bắt đầu. Điều này sẽ xảy ra theo thời gian giá trị xoay trừ đi một. chỉ số gia tăng J bởi một và thiết lập lại các giá trị bắt đầu. Lặp lại cho đến khi hoàn thành.

Một cuộc biểu tình video có thể được tìm thấy ở đây: https://www.youtube.com/watch?v=TMzaO2WzR24