首页 > 试题广场 >

字符串左移，void *pszStringRotate(ch

[问答题]

字符串左移:

void *pszStringRotate(char *pszString, intnCharsRotate)

比如ABCDEFG，移3位变DEFGABC，要求空间复杂度O（1），时间复杂度O（n）。

查看答案及解析

推荐

xxj

翻手算法：

设置有个函数为倒序排列：void Rorder(char *pF,char *pE);

void Rorder(char *pF, char *pE)
{
    char temp;
    while (pF <= pE)
    {
        temp = *pF;
        *pF = *pE;
        *pE = temp;
    }
}

void *pszStringRotate(char *pszString, int nCharsRotate)
{
    char *pR = pszString;
    int n = 0;
    while (pszString + n++ ！ = ‘\n’); //得到字符串长度
    if (n < nCharsRotate) return pR; //入口参数检测

    Rorder(pszString, pszString + nCharsRotate ); //C B A
    pszString = pR;//归位
    Rorder( pszString + nCharsRotate, pszString + n - 1); //GFED
    pszString = pR;
    Rorder(pszString, pszString + n - 1); //DEFGABC
    return pR;
}

大致过程如下：
ABCDEFG
第一步：局部翻转
ABC DEFG == = 》 CBA GFED
第二步：整体翻转
CBA GFED == = 》 DEFGABC

编辑于 2015-01-09 15:26:19 回复(2)

若水/爆米花

#include <iostream>

#include <cstring>

using namespace std;

void Rorder(char *pF, char *pE)

{

char temp;

while (pF <= pE)

{

temp = *pF;

*pF = *pE;

*pE = temp;

pF++;

pE--;

}

char *pszStringRotate(char *pszString, int nCharsRotate)

{

char *pR = pszString;

int n = strlen(pszString);

if (n < nCharsRotate) return pR; //入口参数检测

Rorder(pszString, pszString + nCharsRotate - 1); //C B A

Rorder(pszString + nCharsRotate, pszString + n - 1); //GFED

Rorder(pszString, pszString + n - 1); //DEFGABC

return pR;

}

int main()

{

char s[] = "ABCDEFG";

char *a;

a = pszStringRotate(s, 3);

cout <<a;

system("pause");

return 0;

}

发表于 2015-07-30 09:35:11 回复(1)

叫我大头

#include <stdio.h>
#include <stdlib.h>

void reverse(char *str_start,char * str_end){
    if(str_start == NULL || str_end == NULL ){
        return ;
    }
    while(str_start<str_end){

        char tmp=*str_end;
        *str_end=*str_start;
        *str_start=tmp;
         str_end--;
         str_start++;
    }
}
char * leftrotatestring(char *str,int n){
    //注意保存备份
    char *back_str=str;
    if(str != NULL){
      int i=0;
      while(*str!='\0'){
        i++;
        str++;
      }
      char * pFirstStart=back_str;
      char * pFirstEnd=back_str+n-1;
      char * pSecondStart=back_str+n;
      char * pSecondEnd=back_str+i-1;

      //前面部分
      reverse(pFirstStart,pFirstEnd);
      //printf("%s\n",*back_str);
      //后面部分
      reverse(pSecondStart,pSecondEnd);
      //整体
      reverse(pFirstStart,pSecondEnd);
  }

  return back_str;
}
int main()
{
    char  str[10]="ABCD";
    printf("%s\n",str);
    char* getstr = leftrotatestring(str,2);
    printf("Hello world! %s\n",getstr);
    printf("Hello world! %s\n",str);
    return 0;
}

编辑于 2017-12-28 17:21:21 回复(0)

小饮贼

  #include<iostream> 
  #include<string> 
  using namespace std; 
  voidL(char*a,n) 
  {    
      chart=s[0]; 
      for(inti=1;i<n;i++) 
         { 
          s[i-1]=s[i]; 
      } 
      s[n-1]=t; 
  } 
  voidLR(char*s,intn,intm) 
  { 
      while(m--) 
      { 
          L(s,n); 
      } 
  } 
  int main() 
  { 
       char a[]="ABCEDFG" 
       int len=sizeof(a)-1; 
       LR(a,len,3); 
       cout << a << endl; 
  } 
  
 

发表于 2017-09-02 19:48:50 回复(0)

牛牛1113

   publicclassStringRotateDemo {  
      
   publicstaticvoidmain(String[]
    args) {  
           StringRotateDemo
    srd=newStringRotateDemo();  
           String
    str="ABCDEFG";  

            str=srd.StringRotate(str,3);  

            System.out.println(str);  
       }  
       publicString
    StringRotate(String str,intn){  
           StringBuilder
    strb=newStringBuilder();  

            intlen=str.length();  
           if(len>n){  

                strb.append(str.substring(n-1));  

                for(inti=0;i<n;i++){  

                    strb.append(str.charAt(i));  
               }            
           }    

            returnstrb.toString();  
       }  

    }
    

  

发表于 2016-04-21 18:43:59 回复(0)

MarkAlive

<div> void<span style="color:#333333;"> </span>pszStringRotate(char<span style="color:#333333;"> </span>*pszString, int nCharsRotate) </div> <div> <b>{</b> </div> <div> <b>    if (</b><span>pszString == NULL || </span><span>nCharsRotate <=0 || strlen(</span><span>pszString</span><span>) <= </span><span>nCharsRotate</span><b>)</b> </div> <div> <span><b>        return;</b></span> </div> <div> <span><b><br /> </b></span> </div> <div> <span><b>    int lenStr = strlen(</b></span><span>pszString</span><b>);</b> </div> <div> <b><br /> </b> </div> <div> <b>    int start = 0;</b> </div> <div> <b>    int end = </b><span>nCharsRotate -1;</span> </div> <div> <span>    while(start<end)</span> </div> <div> <span>    {</span> </div> <div> <span>        </span><span>pszString[start] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span><span>pszString[end] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span><span>pszString[start] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span> </div> <div> <span>        </span><span>start ++;</span> </div> <div> <span>        end --;<br /> </span> </div> <div> <span>    }</span> </div> <div> <span><br /> </span> </div> <div> <div> <b>    start = </b><span>nCharsRotate</span><b>;</b> </div> <div> <b>    end = </b><b>lenStr</b><span> -1;</span> </div> <div> <span>    while(start<end)</span> </div> <div> <span>    {</span> </div> <div> <span>        </span><span>pszString[start] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span><span>pszString[end] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span><span>pszString[start] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span> </div> <div> <span>        </span><span>start ++;</span> </div> <div> <span>        end --;<br /> </span> </div> <div> <span>    }</span> </div> </div> <div> <span><br /> </span> </div> <div> <span>    </span><b>start = </b><span>0</span><b>;</b> </div> <div> <b>    end = </b><b>lenStr</b><span> -1;</span> </div> <div> <span>    while(start<end)</span> </div> <div> <span>    {</span> </div> <div> <span>        </span><span>pszString[start] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span><span>pszString[end] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span><span>pszString[start] </span><span>=  </span><span>pszString[start] ^ </span><span>pszString[end];</span> </div> <div> <span>        </span> </div> <div> <span>        </span><span>start ++;</span> </div> <div> <span>        end --;<br /> </span> </div> <div> <span>    }</span> </div> <div> <span><br /> </span> </div> <div> <b>}</b> </div> <div> <b><br /> </b> </div> <div> <b><br /> </b> </div> <div> <br /> </div>

发表于 2015-09-17 11:51:55 回复(0)

指上弹兵赵小括

第一种方法：

ba=(a^b^)^ ；其中^表示逆序，空间复杂度是O(1)，时间复杂度是O(2n)，但是O(2n)是不是也等于O（n）呢；

第二种方法：

1 i与(i + nCharsRotate)%strlen(pszString)交换

2 i = (i + nCharsRotate)%strlen；重复1；

差不多也是O(1)和O(n);

编辑于 2015-09-09 17:40:48 回复(0)

小V变大牛

<pre class="prettyprint lang-cpp">#include "iostream" #include "string" using namespace std; void Reverse(char *pBegin, char *pEnd) { char temp = 0; if(pBegin == NULL || pEnd == NULL) return; while(pBegin < pEnd) { temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; pBegin++; pEnd--; } } void (*pszStringRotate)(char *pszString, int nCharsRotate); void StringLeftRotate(char *str, int n) { int length=0; char *pBegin1=NULL, *pEnd1=NULL, *pBegin2=NULL,*pEnd2=NULL; if(str==NULL) return; length = strlen(str); if(n<=0 || n >= length) return; pBegin1 = str; pEnd1 = str + length - n - 1; pBegin2 = str + length - n; pEnd2 = str + length - 1; Reverse(pBegin1, pEnd2); Reverse(pBegin1, pEnd1); Reverse(pBegin2, pEnd2); return; } </pre> <div> <br /> </div> <br />

发表于 2015-08-27 16:14:26 回复(0)

牛客733423号

//字符串逆序函数
char* reversal(char *str,int length)
{
if(str == NULL || length == 0)
{
  return NULL;
}
for(int i=0; i<length/2; i++)
{
  char ch = str[i];
  str[i] = str[length -i];
  str[length - i] = ch;
}
return str;
}
char *pszStringRotate(char *pszString, int nCharsRotate)
{
if(pszString == NULL || nCharsRotate < 0)
{
  cout<<"error"<<endl;
  exit(1);
}

int length = 0;
while(*pszString != '\n')
{
length++;
}

reversal(pszString,nCharsRotate);
reversal(pszString+nCharsRotate,length - nCharsRotate);
reversal(pszString,length);

return pszString;

}

发表于 2015-04-05 17:39:41 回复(0)

念润

#include <iostream>
#include <cstring>
using namespace std;

//反转单词
void ReverseWord(char* words,int begin,int end){
    int temp;
    if(words == NULL || begin > end || begin < 0){
        return;
    }
    //反转
    while(begin < end){
        temp = words[begin];
        words[begin] = words[end];
        words[end] = temp;
        begin ++;
        end --;
    }
}

char *pszStringRotate(char *pszString, int nCharsRotate){
   nCharsRotate = nCharsRotate % strlen(pszString);
   if(pszString == nullptr){
        return "";
   }//if
   int len = strlen(pszString);
   ReverseWord(pszString,0,nCharsRotate-1);
   //反转剩余
   ReverseWord(pszString,nCharsRotate,len-1);
   //全部反转
   ReverseWord(pszString,0,len-1);
   return pszString;
}

int main() {
    int i,n;
    char* str = (char*)malloc(sizeof(char)*1001);
    while(scanf("%s",str) != EOF){
        scanf("%d",&n);
        //左旋转
        //注意一下n需要取余就可以了，不能超过字符串自身的长度
        str = pszStringRotate(str,n);
        //输出
        for(i = 0;i < strlen(str);i++){
            printf("%c",str[i]);
        }
        printf("\n");
    }//while
    return 0;
}

发表于 2015-03-29 23:21:15 回复(0)

mqh

void *pszStringRotate(char *pszString, intnCharsRotate)
{
    char *start1 = pszString;
    char *start2 = pszString;
    char *tail  = pszString + intnCharsRotate;
    int n = 0;
    while (*start1++ != '\0')
    {
        n++;
    }
    for (int i = 0 ; i < intnCharsRotate; i++)
    {
        char  t = *start1;
        *start1++ = *tail++;
        *(start2 + n - (intnCharsRotate - i)) = t;
    }
}

编辑于 2015-01-09 15:08:29 回复(0)

流血的手指

void *pszStringRotate(char *pszString, int nCharsRotate){
    int len = strlen(pszString);
    reverse(pszString, 0, nCharsRotate);
    reverse(pszString, nCharsRotate -1, len);
    reverse(pszString, 0, len);
}

void reverse(char *pszString, int start, int end){
    while(start < end-1){
         swap(pszString[start], pszString[end]);
     }
}

发表于 2014-12-20 11:30:18 回复(0)

流

void *pszStringRotate(char *pszString, int nCharsRotate)
{
    int len = strlen(pszString);
    for (int i = nCharsRotate; i < len; i++)
    {
        char temp = pszString[i];
        pszString[i] = pszString[i - nCharsRotate];
        pszString[i - nCharsRotate] = temp;
    }
    for (int i = len - nCharsRotate; i < len; i++)
    {
        char temp = pszString[i];
        pszString[i] = pszString[len - 1];
        pszString[llen - 1] = temp;
    }
}

编辑于 2015-01-09 15:08:51 回复(0)

墨半成霜

for(int i=0;i<pszString.lenth;i++){

char *s=malloc(sizeof(char)*pszString.lenth);

int k=(i-3)%pszString.lenth;

s[i]=pszString[k];

returen s;

}

发表于 2014-12-03 20:56:51 回复(1)

rodin

交换3次

发表于 2014-12-01 19:58:28 回复(0)

xcy7703

对左3位翻转变为cba,右边4位翻转变为gfed，现在整个变为了cbagfed，再翻转一次变为defgabc。只要实现翻转这一基本操作，就可以实现循环左移。

发表于 2014-11-26 11:46:00 回复(0)

asyoguo

用一个额外变量保存最后一个元素的值，然后从最后一个元素开始

发表于 2014-11-25 18:59:09 回复(0)

solamoon

发表于 2014-11-19 22:52:34 回复(0)

撒

rtrttr

发表于 2014-11-18 21:29:35 回复(0)

提交观点

问题信息

字符串复杂度百度

来自：百度2013研发工程师...

上传者：Clark

难度：

19条回答 49收藏 7560浏览

字符串左移，void *pszStringRotate(ch

问题信息

热门推荐

相关试题