`
kenby
  • 浏览: 724582 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

编程之美3.1 字符串移位包含的问题

 
阅读更多

题目

给定两个字符串 s1 和 s2, 要求判定 s2 是否能够被通过 s1 作循环移位 ( rotate )

得到的字符串包含. 例如, 给定 s1 = AABCD 和 s2 = CDAA, 返回 true; 给定

s1 = ABCD 和 s2 = ACBD, 返回 false.

 

 

解法1

直接模拟, 对 s1 进行循环移位, 在判断字符串 s2 是否在移位后的字符串中.

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

int main()
{
	char src[] = "AABBCD";
	char des[] = "CDAA";

	int len = strlen(src);
	int i, j;

	for (i = 0; i < len; i++) {
		char tempchar = src[0];
		for (j = 0; j < len - 1; j++) {
			src[j] = src[j + 1];
		}
		src[j] = tempchar;
		if (strstr(src, des) == 0) {
			printf("Yes\n");
			getchar();
			return 1;
		}
	}
	printf("No\n");
	getchar();
	return 0;
}
 

解法2

其实没必要对 s1 进行真正的移位, 依次从 s1[0], s1[1], ... 开始比较, 如果 s1 的下标超出范围, 就对

其取余, 这样就相当于延长字符串 s1 了.

 

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


int main()
{
	char src[] = "AEBBCD";
	char des[] = "CDAE";

	int len_src = strlen(src);
	int len_des = strlen(des);
	int i, j, k;

	for (i = 0; i < len_src; i++) {
		j = i;
		k = 0;
		while (src[j] == des[k]) {
			j = (j + 1) % len_src;
			k++;
		}
		if (k == len_des) {
			printf("Yes\n");
			getchar();
			return 1;
		}
	}
	printf("No\n");
	getchar();
	return 0;
}
 

解法3

解法2通过取余数的方法, 达到延长字符串的目的, 当然这是一种伪延长, 我们也可以把

s1 延长成 s1s1, 那么对 s1 做循环移位所得到的字符串都将是字符串 s1s1 的子字符串.

如果 s2 可以由 s1 循环移位得到, 那么 s2 一定在 s1s1 上. 至此我们将问题转换成考察

s2 是否在 s1s1 上, 可通过调用一次 strstr 函数得到结果. 

 

总结

解法1直接模拟, 效率最低, 解法3是典型的空间换时间的做法, 解法2是解法1和解法3的折中,

既不需要额外的空间, 也不需要对字符串做移动

 

分享到:
评论

相关推荐

    程序员编程艺术:面试和算法心得

    - **题目描述**: 给定一个字符串,如 "abcdef",要求把字符串前面的若干个字符移动到字符串的尾部,例如将 "a" 和 "b" 移动到尾部,使得原字符串变成 "cdefab"。要求实现一个函数,其时间复杂度为 O(n),空间复杂度...

    S71200移位指令 附跑马灯程序.docx

    在自动化领域,特别是PLC(可编程逻辑控制器)编程中,掌握移位和循环移位指令对于编写高效、精准的控制程序至关重要。S7-1200 PLC提供了SHL、SHR、ROL和ROR这四种指令,帮助实现数据位的移位操作。 首先,我们来...

    C 语言编程常见问题解答.chm

    C 语言编程常见问题解答 【作者】[美]Paul S.R. Chisholm 译:张芳妮 吕 波 【出版社】清华大学出版社 C语言编程常见问题解答(目录) 第l章 C语言 1. 1 什么是局部程序块(local block)? 1. 2 可以把变量保存...

    Perl 语言编程

    - **什么是真**:在 Perl 中,任何非零值和非空字符串都被认为是真的。 - **if 和 unless 语句**:用于基于条件执行代码。 - **循环**: - `while` 和 `until` 循环。 - `for` 循环,用于迭代固定数量的次数。 - ...

    三菱FX系列可编程控制器编程手册

    - **字符串操作指令**:介绍用于处理字符串的指令。 - **ASCII码转换**:解释如何将数据转换为ASCII码格式。 ##### 7.2 文件管理 (P.416) - **文件创建与删除**:介绍如何在PLC中创建、删除文件。 - **文件读写**...

    单片机常用知识 (2).pdf

    字符串处理函数在string.h头文件中定义,如`strcat`用于连接两个字符串,`strcmp`比较字符串大小,`strlen`获取字符串长度,`strchr`查找特定字符,`strncpy`复制指定长度的字符串等。 最后,内部函数库包含了一些...

    perl programing 编程基础版本

    - `$` 开头表示标量变量,用于存储单一的值,如整数、浮点数、字符串等。 - **1.2.3 复数变量** - `@` 表示数组变量,用于存储一系列的值。 - `%` 表示散列(哈希)变量,用于存储键值对。 - **1.2.4 复杂...

    PERL语言编程

    - 单引号(`'`)用于普通字符串,双引号(`"`)用于允许变量插入的字符串。 - **2.6.4 要么就完全不管引起** - 引号的选择。 - **2.6.5 代换数组数值** - 在字符串中插入数组元素。 - **2.6.6 “此处”文档** - 使用...

    三菱Q系列PLC编程指令

    - **字符串处理指令**:STRLEN、STRCAT等,用于字符串操作。 - **特殊功能指令**:如PID控制等。 - **数据控制指令**:用于数据的控制操作。 - **转换指令**:如ASCII与数字之间的转换等。 - **时钟指令**:用于获取...

    宋劲彬的嵌入式C语言一站式编程

    2.7. 以字符串为单位的I/O函数 2.8. 以记录为单位的I/O函数 2.9. 格式化I/O函数 2.10. C标准库的I/O缓冲区 2.11. 本节综合练习 3. 数值字符串转换函数 4. 分配内存的函数 26. 链表、二叉树和哈希表 1. 链表 1.1. ...

    C#编程经验技巧宝典

    76 &lt;br&gt;0111 计算字符串中子字符串出现的次数 76 &lt;br&gt;0112 获得字符串中大写字母的个数 77 &lt;br&gt;0113 获得某字符在字符串中最后出现的位置 78 &lt;br&gt;0114 如何找出字符串中某一字符的所有位置 78...

    Perl 语言编程 全面讲解Perl各个部分

    - **字符串操作符**:用于连接字符串(`.`)或匹配正则表达式(`=~`)。 - **赋值操作符**:用于将值赋给变量,如 `=`。 - **单目算术操作符**:如前缀加(`++`)和前缀减(`--`)。 - **逻辑操作符**:用于构建逻辑...

    单片机常用知识 (3).pdf

    单片机是微控制器的一...总的来说,掌握单片机常用知识,包括硬件接口、寄存器配置、I/O操作、串口通信、内存管理和字符串处理,是进行单片机编程的基础。理解和运用这些知识点,可以有效地开发和调试单片机应用系统。

    LabVIEW宝典课件

    1.4章节详细介绍了各种基本控件的使用,包括数值、布尔、字符串、路径、下拉列表、枚举、数组、簇、时间标识和波形数据控件等,这些是LabVIEW编程中最常见的元素。 在基础函数的学习中,2.1章节详述了基本的算术...

    编程思想下篇

    3.13 字符串操作符 + 和 += 3.14 使用操作符时常犯的错误 3.15 类型转换操作符 3.15.1 截尾和舍入 3.15.2提升 3.16 Java没有“sizeof” 3.17 操作符小结 3.18 总结 第4章 控制执行流程 4.1 true和false 4.2 if-else ...

Global site tag (gtag.js) - Google Analytics