字符串逆序

https://github.com/yuanoOo/Algorithm/tree/master/String/%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%80%86%E5%BA%8F%E7%9B%B8%E5%85%B3%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%97%AE%E9%A2%98

1、"dog loves pig" to "pig loves dog"问题

image.png

• 解题步骤：

• ①翻转整个字符串

• ②逐个翻转单词

• implement by C programmer language：

#include<iostream>
#include<string.h> 
using namespace std;

void reverse(char *str, int start, int end);


int main()
{
    int flag = 0;
    char str[] = "pig loves dog";
    reverse(str,0,12);
    cout<<str<<endl;
    for(int i = 0; i < strlen(str); ++i)
    {
        if(str[i] == ' ')
        {
            reverse(str, flag, i - 1);
            flag = i + 1;
        }
        
        if(i == strlen(str) - 1)
            reverse(str, flag, i);
    }   
    cout<<str<<endl;
} 

void reverse(char *str, int start, int end)
{
    if(start > end) return;
    if(start < 0 || end >= strlen(str)) return;
    
    //exchange all elements between start to end
    while(start < end)
    {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        
        ++start;
        --end;
    }
}

2、以O(1)的空间复杂度调整字符串

本题的关键在于不能用额外的空间，因此利用字符串逆序来解决此类问题，是非常有效的，也几乎是唯一的解法。

image.png

• 解题步骤
• ①翻转局部字符串
• ②翻转整个字符串

#include<iostream>
#include<string.h>
using namespace std;

void reverse(char *str, int start, int end); 

int main()
{
    char str[] = "ABCDE";
    int k = 2;//给定的移动位置
    
    reverse(str,0,2);
    reverse(str,3,4);
    reverse(str,0,4);
    cout<<str; 
} 

//逆序start to end之间的字符 
void reverse(char *str, int start, int end)
{
    if(start > end) return;
    if(start < 0 || end >= strlen(str)) return;
    
    //exchange all elements between start to end
    while(start < end)
    {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        
        ++start;
        --end;
    }
}