`
ibvjc36f
  • 浏览: 13438 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

《算法之美》の字符串相关问题の壹

 
阅读更多

  题目:编写一个单词逆序输出的算法,例如输入"SEE YOU IN ANOTHER LIFE",要求输出"LIFE ANOTHER IN YOU SEE"。
  解答:
  解法一:只需扫描一遍:
  #include
  void ReverseWord(constchar* src, char* dest)
  {
  assert(src != NULL && dest != NULL);
  constchar* head = src; //记住头指针
  while(*src++);
  int count = 0;
  for(src -= 2;;src--) //从尾到头遍历
  {
  if(src == head) //到头部额,退出循环
  {
  do
  {
  *dest++ = *src++;
  } while(count--);
  break;
  } 
  if(*src == ' ') //遇到空格
  {
  constchar* temp = src + 1;
  while(count--)
  {
  *dest++ = *temp++;              
  }
  *dest++ = ' ';
  count = 0;
  }
  else
  {
  count++;   //计算每个单词的长度
  }
  }
  *dest = '\0';
  }
  int main()
  {
  constchar* str = "SEE YOU IN ANOTHER LIFE";
  char *dest = newchar[strlen(str) + 1];
  ReverseWord(str, dest);    
  std::cout字符串,将第一个字符和最后一个字符交换,第二个和倒数第二个交换,依次循环。接着进行第二次遍历,对每个单词反转一次,这样每个单词就恢复成原有顺序,得到题目要求的功能了:
  #include
  char* ReverseWord(constchar* str)
  {
  assert(str != NULL);
  int len = strlen(str);
  char* restr = newchar[len + 1];
  strcpy(restr, str);
  //第一次扫描,头尾反转
  for(int i=0, j=len-1; i字符串,一个这个字符串的子串,将第一个字符串反转,但保留子串的顺序不变。例如:
  输入:第一个字符串:"See you in another life"
  子串:"in"
  输出:"efil rehtona in uoy eeS"
  解答:一般的方法是先扫描一遍第一个字符串,用stack把它反转,同时记录下子串出现的位置;然后再扫描一遍反转后的字符串,扫描过程中将原来子串再反转,其他的不变,这样就得到答案了。
  那么只扫描一遍怎么办呢?只需在扫描的过程中将子串反序压入堆栈;扫描完之后,将堆栈中字符弹出,这样子串就还是原来的顺序了。实现代码如下:
  #include
  #include
  #include
  constchar* reverse(constchar* s1, constchar* token)
  {
  assert(s1 && token);
  std::stack stackOne;
  constchar* ptoken = token;
  constchar* head = s1;
  constchar* rear = s1;
  while(*head != '\0')
  {         while(*head != '\0' && *ptoken == *head)         {             ptoken++;             head++;                     }         if(*ptoken == '\0') //包含字符串token
  {
  constchar* p;
  for(p=head-1; p>=rear; p--) //从尾到头将token存入堆栈
  {
  stackOne.push(*p);              
  }          
  ptoken = token;
  rear = head;
  } 
  else//不是分割的字符串
  {
  stackOne.push(*rear);
  head = ++rear;
  ptoken = token;   
  }
  } 
  char* ret = newchar[strlen(s1)+1];
  int i = 0;
  while(!stackOne.empty()) //非空
  {
  ret[i++] = stackOne.top();
  stackOne.pop(); 
  }     
  ret[i] = '\0';
  return ret;
  } 
  int main()
  {
  std::cout<<"See you in another life"<<std::endl;
  std::cout<<reverse("See you in another life", "in")<<std::endl;
  system("pause");
  return 0;
  }
分享到:
评论

相关推荐

    LZ78算法实现对任意字符串的压缩与解压

    这种算法的主要思想是创建一个动态更新的字典,字典中的条目是输入字符串中的已编码子串。 在Java环境中实现LZ78算法,首先我们需要理解其基本步骤: 1. 初始化:创建一个空的字典,通常用一个数组或哈希表表示,...

    字符串逆序 - 字符串逆序算法

    字符串逆序是一种常见的算法问题,主要涉及将一个给定的字符串中的字符顺序颠倒过来,以形成一个新的字符串。在不同的编程语言中,实现字符串逆序的方法可能有所不同,但基本思想是相似的。字符串逆序算法的核心在于...

    字符串 - 字符串算法问题

    字符串算法问题主要研究如何高效地处理和分析字符串数据,解决与字符串相关的各种计算问题。给定两个字符串s和t,可能涉及到的字符串算法问题包括但不限于字符串比较、字符串搜索、字符串匹配、字符串编辑距离、最长...

    基于字符串模式匹配算法的病毒感染检测问题_算法_数据结构_

    3. **Boyer-Moore算法**:根据模式字符串的字符出现频率构建跳跃表,使得在目标字符串中可以跳过部分字符,进一步提升效率。时间复杂度在最坏情况下为O(n + m)。 4. **Horspool算法**:是Boyer-Moore算法的简化版本...

    字符串相似度比较算法

    在计算机科学领域,字符串相似度比较算法是一种用于评估两个字符串之间相似程度的技术。这些算法广泛应用于文本处理、信息检索、生物信息学等多个领域。当我们要判断两个字符串是否含有相同或相近的信息时,这类算法...

    字符串相似性算法【最长公共字符串算法】 【LCS】

    字符串相似性算法是计算机科学中一个重要的领域,用于衡量两个字符串之间的相似度。最长公共子序列(Longest Common Subsequence, LCS)是其中一种广泛应用的方法,尤其在文本处理、生物信息学和数据比较中有着广泛...

    带通配符的字符串匹配算法

    在IT领域,字符串匹配是计算机科学中的一个基本问题,尤其在文本处理、数据搜索和模式识别等场景中广泛应用。带通配符的字符串匹配算法则是这个领域的延伸,它允许在模式字符串中包含特殊字符,如星号(*)或问号(?),...

    delphi计算两个字符串相似度源码 Levenshtein算法版

    在信息技术领域,字符串处理是常见的任务之一,其中计算两个字符串的相似度是尤为重要的一个环节。Levenshtein算法,也称为编辑距离算法,就是用于衡量两个字符串之间差异程度的一种方法。本文将深入探讨如何使用...

    字符串查找算法BM

    为了解决这一问题,Boyer和Moore提出了BM算法,这是一种更为高效的字符串查找方法。 #### 二、BM算法原理 BM算法的核心思想是在匹配过程中利用模式字符串的信息来实现快速跳过,从而减少不必要的比较次数。具体来...

    ACM比赛常见算法之BFS算法+back回文字符串

    ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文...

    基于字符串模式匹配算法的病毒感染检测问题 实验四(源代码+实验报告)

    本实验“基于字符串模式匹配算法的病毒感染检测问题”聚焦于如何利用这些算法来识别潜在的恶意代码,从而预防计算机病毒感染。 《数据结构(C语言版 第2版)》一书由著名计算机科学家严蔚敏编著,书中涵盖了各种...

    C# 文本对比算法比较两个字符串的不同

    一种常见的算法是Levenshtein距离,它计算了将一个字符串转换为另一个字符串所需的最少单字符编辑次数。其他算法,如Longest Common Subsequence(最长公共子序列)和Diff Match Patch,也能提供类似的功能。 2. **...

    字符串算法

    字符串算法是计算机科学中的一个重要领域,它涉及到对字符串(一串字符序列)进行操作和分析的各种算法。在处理文本、编程语言、数据压缩、搜索、排序等问题时,字符串算法起着至关重要的作用。这里我们将深入探讨...

    DELPHI Levenshtein算法 字符串相似度计算(附源码)

    Levenshtein算法,也称为编辑距离算法,是由俄国数学家Vladimir Levenshtein在1965年提出的一种衡量两个字符串相似度的方法。这个算法基于动态规划原理,可以计算出将一个字符串转换成另一个字符串所需要的最少单...

    字符串处理算法

    在当今的计算机科学领域,字符串处理是一个极其重要的课题,尤其在算法竞赛如ACM(ACM国际大学生程序设计竞赛)中,高效的字符串处理算法是解决许多问题的关键。本文将介绍一些常见的字符串处理算法:Hash、KMP、...

    字符串匹配算法总结

    字符串匹配是计算机科学中的一种基本问题,涉及到对文本数据的搜索和分析。在这个问题中,目标是找出一个较长的字符串(匹配串)中是否存在一个较短的子串(模式串)。这里我们将深入探讨几种常见的字符串匹配算法,...

    字符串问题详解

    字符串问题在计算科学中占有重要的地位,涉及字符处理的各种算法和数据结构。常见的字符串处理包括查找、替换、连接、插入和删除等基本操作,而更深入的算法如最长公共子序列(LCS)和最长公共子串(LIS)则是研究字符串...

    字符串匹配算法ppt

    字符串匹配是计算机科学中一个基础且重要的问题,广泛应用于文本搜索、数据分析等领域。在这个主题中,我们将探讨三种经典的字符串匹配算法:穷举法、KMP(Knuth-Morris-Pratt)算法和BM(Boyer-Moore)算法。 1. *...

    字符串匹配算法C代码实现

    字符串匹配是计算机科学中一个基础且重要的问题,广泛应用于文本处理、搜索引擎、数据挖掘等领域。在C语言中,实现字符串匹配算法通常涉及到对字符数组的操作和逻辑控制结构。本篇文章将详细探讨四种常见的字符串...

    C++实现定点算法将浮点数转为字符串

    ### C++实现定点算法将浮点数转为字符串 #### 概述 本文旨在探讨一种特殊的浮点数转字符串的方法——定点法。该方法通过对IEEE 754标准下的浮点数编码规则进行硬解码,进而实现浮点数到字符串的转换。尽管这种方法...

Global site tag (gtag.js) - Google Analytics