文档章节

字符串旋转

yejq8
 yejq8
发布于 2015/05/15 21:43
字数 1617
阅读 70
收藏 3

题目描述
给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部,使得原字符串变成字符串“cdefab”。请写一个函数完成此功能

对于这个问题,我们首先想到的就是暴力移位法,就是将字符串的第一个字符保存起来,其余的往前挪动一格,然后将保存起来的字符放到字符串的最末尾,然后循环执行这个过程。得到代码:

void LeftShiftOne(char *buff, int n) {
  char temp = buff[0];
  int i;
  for(i=1;i<n;i++) {
    buff[i-1] = buff[i];
  }
  buff[n-1] = temp;
}

void LeftRotateString(char *buff, int n, int m) {
  while(m--) {
    LeftShiftOne(buff, n);
  }

}

当然,我们也可以牺牲一点空间,重新开辟一个等大小的字符串,然后将字符从旧字符串中依次按要求移动过来。

然而我们采取一种原地处理的办法。

将一个字符串分成X和Y两个部分,在每部分字符串上定义反转操作,如X^T,即把X的所有字符反转(如,X="abc",那么X^T="cba"),那么就得到下面的结论:(X^TY^T)^T=YX,显然就解决了字符串的反转问题。

例如,字符串 abcdef ,若要让def翻转到abc的前头,只要按照下述3个步骤操作即可:

1. 首先将原字符串分为两个部分,即X:abc,Y:def;
2. 将X反转,X->X^T,即得:abc->cba;将Y反转,Y->Y^T,即得:def->fed。
3. 反转上述步骤得到的结果字符串X^TY^T,即反转字符串cbafed的两部分(cba和fed)给予反转,cbafed得到defabc,形式化表示为(X^TY^T)^T=YX,这就实现了整个反转。

得到下面代码:

#include <stdio.h>

void Reverse(char * buff, int begin, int end) {

  char temp;

  while(end > begin) {
    temp = buff[begin];
    buff[begin] = buff[end];
    buff[end] = temp;
    begin++;
    end--;
  }

}

void LeftRotateString(char *buff, int n, int m) {

  Reverse(buff, 0, m-1);
  Reverse(buff, m, n-1);
  Reverse(buff, 0, n-1);

}


举一反三:
1、链表翻转。给出一个链表和一个数k,比如,链表为1→2→3→4→5→6,k=2,则翻转后2→1→6→5→4→3,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→6→5,用程序实现。

2、编写程序,在原字符串中把字符串尾部的m个字符移动到字符串的头部,要求:长度为n的字符串操作时间复杂度为O(n),空间复杂度为O(1)。 例如,原字符串为”IloveSYSU”,m=7,输出结果为:”SYSUIlove”。

3、单词翻转。输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变,句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如,输入“I am a student.”,则输出“student. a am I”。


1、链表的指定翻转:

我们可以用上面题目的反向思维,即是先将连链表的前k个元素全部挪动到链表的末尾,然后将整个链表翻转过来,恰好得到了我们所需要的结果。

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct nodeh {
  int data;
  struct node * next;
  unsigned int size;
} nodeh;

typedef struct node {
  int data;
  struct node * next;
} node;

nodeh * push(nodeh * head, int c, int k);
nodeh * delete(nodeh * head, int k);
nodeh * roate_list(nodeh * head, int k);

nodeh * build_list_from_string(nodeh * head, char * s);
void list_to_string(nodeh * head);

int main() {
  nodeh * head = NULL;
  char s[1000];
  int k;
  scanf("%s", s);
  scanf("%d", &k);
  head = build_list_from_string(head, s);
  head = roate_list(head, k);
  list_to_string(head);
  return 0;
}

// k = 0 means insert before head
nodeh * push(nodeh * head, int c, int k) {
  
  if(head == NULL) {
    if(k == 0) {
      head = (nodeh *)malloc(sizeof(nodeh));
      head->data = c;
      head->next = NULL;
      head->size = 1;
      return head;
    } else {
    return NULL;
    }
  }

  unsigned int size = head->size;
  int i;

  if(size < k) {
    return NULL;
  }

  node * element;
  element = (node *)malloc(sizeof(node));
  if(element == NULL) {
    printf("element allocation failed!");
    return NULL;
  }
  element->data = c;
  element->next = NULL;

  if (k == 0) {
    int temp_c = head->data;
    head->data = c;
    element->data = temp_c;
    
    element->next = head->next;
    head->next = element;
    head->size++;
    return head;
  }

  if(k == 1) {
    element->next = head->next;
    head->next = element;
    head->size++;
    return head;
  }

  node * positioner = head->next;
  
  i = 2;
  while(i++ < k) {
    positioner = positioner->next;
  }
  element->next = positioner->next;
  positioner->next = element;

  head->size++;
  return head;
}

nodeh * delete(nodeh * head, int k) {
  if(head == NULL) {
    return NULL;
  }

  unsigned int size = head->size;

  if (k > size) {
    return head;
  }
  
  if (size == 1) {
    free(head);
    return NULL;
  }

  node * to_delete = head->next;
  
  if(k == 0) {
    head->data = head->next->data;
    head->next = head->next->next;
    free(to_delete);
    head->size--;
    return head;
  }

  node * positioner = head->next;
  to_delete = to_delete->next;

  int i = 1;
  
  while(i++ < k) {
    to_delete = to_delete->next;
    positioner = positioner->next;
  }

  positioner->next = to_delete->next;
  free(to_delete);
  head->size--;
  return head;
}

nodeh * build_list_from_string(nodeh * head, char * s) {
  if(s == NULL) {
    head = NULL;
    return;
  } else if(strlen(s) == 0) {
    head = NULL;
    return;
  }
  
  const char Delimiter = '-';
  
  int i, temp = 0;
  for(i = 0; i <strlen(s); i++) {
    if(s[i] >= '0' && s[i] <= '9') {
      temp *= 10;
      temp += s[i] - '0';
    } else if(s[i] == Delimiter) {
      head = push(head, temp, head == NULL ? 0 : head->size);
      temp = 0;
    }
  }
  head = push(head, temp, head == NULL ? 0 : head->size);
}

void list_to_string(nodeh * head) {
  node * positioner = NULL;

  if(head == NULL) {
    return;
  }

  printf("%d : ", head->size);
  printf("%d", head->data);

  for(positioner = head->next; positioner != NULL; positioner = positioner->next) {
    printf("->%d", positioner->data);
  }
  printf("\n");
}

nodeh * roate_list(nodeh * head, int k) {
  if (head == NULL || k <= 0 || k > head->size) {
    return head;
  }

  int temp;
  while(k--) {
    temp = head->data;
    head = delete(head, 0);
    head = push(head, temp, head == NULL ? 0 : head->size);
  }

  node * head_next = head->next;
  node * saver = (node *)head;
  node * positioner = saver->next;
  node * new_head = NULL;
  
  while(positioner != NULL) {
    saver->next = new_head;
    new_head = (node *)saver;
    saver = positioner;
    positioner = positioner->next;
  }
  saver->next = new_head;
  new_head = (node *)saver;
  
  saver = new_head->next;
  temp = new_head->data;
  free(new_head);

  nodeh * true_new_head;
  true_new_head = (nodeh *)malloc(sizeof(nodeh));
  true_new_head->next = saver;
  true_new_head->data = temp;
  true_new_head->size = head->size;

  temp = head->data;
  free(head);

  node * tail = malloc(sizeof(node));
  tail->next = NULL;
  tail->data = temp;
  
  head_next->next = tail;

  return true_new_head;
}


2、程序也是一个应用题目很典型的例子,我们只需要把前面(n-k)个字符往后移动就相当于把后k个字符往前移动了。

#include <stdio.h>
#include <string.h>

void ReverseString(char* s,int from,int to) {
    while (from < to) {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void LeftRotateString(char * s, int k, int length) {
  ReverseString(s, 0, k-1);
  ReverseString(s, k, length-1);
  ReverseString(s, 0, length-1);
}

int main() {
  char s[1000];
  int k;
  scanf("%s%d", s, &k);
  LeftRotateString(s, strlen(s) - k, strlen(s));
  printf("%s\n", s);
  return 0;
}


3、这一个也是一个很好的变式,要输出题目要求的字符串,其实就是将每个空格隔开的字符串旋转,然后再将整体旋转:

#include <stdio.h>
#include <string.h>

void ReverseString(char* s,int from,int to) {
    while (from < to) {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void WordsString(char * s, int length) {
  int f = 0, t;
  int i;
  for(i = 0; i < length;i++) {
    if(s[i] == ' ') {
      t = i-1;
      ReverseString(s, f, t);
      f = i+1;
    }
  }
  ReverseString(s, f, length-1);
  ReverseString(s, 0, length-1);
}

int main() {
  char s[1000];
  gets(s);
  WordsString(s, strlen(s));
  printf("%s\n", s);
  return 0;
}


出处:The-Art-Of-Programming-By-July

https://github.com/julycoding/The-Art-Of-Programming-By-July

© 著作权归作者所有

上一篇: 子字符串包含
下一篇: 求图的连通块
yejq8
粉丝 0
博文 11
码字总数 8967
作品 0
广州
程序员
私信 提问
判断翻转子串

假定有一个方法isSubstring,可检查一个单词是否为其他字符串的子串。给定两个字符串s1,s2,请编写代码检查s2是否为s1旋转而成,要求只能调用一次isSubstring 比如waterbottle是erbottlewat旋转...

一贱书生
2016/11/15
20
0
51Nod 1347 旋转字符串

S[0…n-1]是一个长度为n的字符串,定义旋转函数Left(S)=S[1…n-1]+S[0].比如S=”abcd”,Left(S)=”bcda”.一个串是对串当且仅当这个串长度为偶数,前半段和后半段一样。比如”abcabc”是对串...

Akatsuki__Itachi
2017/12/19
0
0
1347 旋转字符串

1347 旋转字符串 基准时间限制:1 秒 空间限制:131072 KB 分值: 5难度:1级算法题 S[0...n-1]是一个长度为n的字符串,定义旋转函数Left(S)=S[1…n-1]+S[0].比如S=”abcd”,Left(S)=”bcda”...

angel_kitty
2017/02/23
0
0
屏幕方向读取与锁定:Screen Orientation API

什么是 Screen Orientation API Screen Orientation API 为 Web 应用提供了读取设备当前屏幕方向、旋转角度、锁定旋转方向、获取方向改变事件的能力。使得特定应用在屏幕方向方面增强用户体验...

NimitzDEV
02/28
0
0
Lintcode8 Rotate String solution 题解

【题目描述】 Given a string and an offset, rotate string by offset. (rotate from left to right) 给定一个字符串和一个偏移量,根据偏移量旋转字符串(从左向右旋转) 【题目链接】 http...

coderer
2017/04/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

面试官问:平时碰到系统CPU飙高和频繁GC,你会怎么排查?

处理过线上问题的同学基本上都会遇到系统突然运行缓慢,CPU 100%,以及Full GC次数过多的问题。当然,这些问题的最终导致的直观现象就是系统运行缓慢,并且有大量的报警。本文主要针对系统运...

Java高级架构师n
41分钟前
19
0
面向对象编程

1、类和对象 类是对象的蓝图和模板,而对象是实例;即对象是具体的实例,类是一个抽象的模板 当我们把一大堆拥有共同特征的对象的静态特征(属性)和动态特征(行为)都抽取出来后,就可以定...

huijue
今天
20
0
redis异常解决 :idea启动本地redis出现 jedis.exceptions.JedisDataException: NOAUTH Authentication required

第一次安装在本地redis服务,试试跑项目,结果却出现nested exception is redis.clients.jedis.exceptions.JedisDataException: NOAUTH Authentication required错误,真是让人头疼 先检查一...

青慕
今天
32
0
Spring 之 IoC 源码分析 (基于注解方式)

一、 IoC 理论 IoC 全称为 Inversion of Control,翻译为 “控制反转”,它还有一个别名为 DI(Dependency Injection),即依赖注入。 二、IoC方式 Spring为IoC提供了2种方式,一种是基于xml...

星爵22
今天
32
0
Docker安装PostgresSql

Docker安装PostgresSql 拉取docker镜像 # docker pull postgres:10.1010.10: Pulling from library/postgres9fc222b64b0a: Pull complete 38296355136d: Pull complete 2809e135bbdb: Pu......

Tree
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部