`
java-mans
  • 浏览: 11710388 次
文章分类
社区版块
存档分类
最新评论

算法学习之字符串左移&右移

 
阅读更多

1.设计一个算法,把一个含有N个元素的数组循环右移K位,要求时间复杂度为O(N),

且只允许使用两个附加变量。
方法一:
每次将数组中的元素右移一位,循环K次,则实现了右移K位。
例如,
原始字符串:abcd1234
右移一位:4abcd123
右移一位:34abcd12
右移一位:234abcd1
右移一位:1234abcd
循环4次,则实现了右移4次

实现函数如下:

void right_shift(char *str, int N, int K)
{
	char temp;
	K %= N; //目的是,当K > N时,移动K次与移动K-i*N次是一样的。
	while(K--)
	{
		t = str[N -1];
		for(int i = N - 1; i > 0; i--)
			str[i] = str[i - 1];
		str[0] = t;
	}
}


从上面的实现代码可以看出,
由于K %= N, 所以while循环的K值是小于N的。所以时间复杂度最大为O(N^2), 空间复杂度为O(1),不符合题目要求。

方法二:
对于原始字符串abcd1234,右移2位后为:34abcd12。
通过比较可以看出,有两段子字符串的顺序是不变的。abcd12和34。
则可发现,右移K位的过程就是把数组的两部分交换的过程。

例如:abcd12|34.
对abcd12逆序排列:21dcba
对34逆序排列: 43
对全部的21dcba|43进行逆序排列:34abcd21.

得出如下结论:
将字符串S="abcd1234"分为两部分X="abcd12"和Y="34"。那么S=(X, Y)
X逆序记为X'="21dcba"
Y逆序记为Y'="43"
则(X', Y')="21dcba43"整体再逆序为"34abcd12" = (Y, X)

即(X', Y')' = (Y, X)

代码实现如下:

void reverse(char* str, int begin, int end)
{
	char temp;
	for( ; begin < end; begin++)
	{
		temp = str[end];
		str[end] = str[begin];
		str[begin] = temp;
	}
}

void right_shift(char *str, int N, int K)
{
	K %= N;
	reverse(str, 0, N - K -1);
	reverse(str, N - K, N - 1);
	reverse(str, 0, N - 1);
}


该算法则实现了在线性时间内实现右移操作了。

编写主函数测试如下:

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

int main()
{
	char str[] = "abcd1234";
	printf("The initial string:%s\n", str);
	
	right_shift(str, 8, 2);
	printf("The string after right shift:%s\n", str);
	
	system("pause");
	return 0
}

2.实现对字符串进行左旋转的函数,要求对长度为n的字符串操作的时间复杂度为O(n), 空间复杂度为O(1).
例如,原始字符串:abcd1234,左旋转2位后为:cd1234ab
通过上面的1的分析,只是把右移改为左移。其他方法相同。
代码实现如下:

void reverse(char* str, int begin, int end)
{
	char temp;
	for( ; begin < end; begin++)
	{
		temp = str[end];
		str[end] = str[begin];
		str[begin] = temp;
	}
}

void right_shift(char *str, int N, int K)
{
	K %= N;
	reverse(str, 0, K -1);
	reverse(str, K, N - 1);
	reverse(str, 0, N - 1);
}

int main()
{
	char str[] = "abcd1234";
	printf("The initial string:%s\n", str);
	
	right_shift(str, 8, 2);
	printf("The string after right shift:%s\n", str);
	
	system("pause");
	return 0
}


内容整理于:http://blog.csdn.net/v_JULY_v/article/details/6322882

分享到:
评论

相关推荐

    数据结构和算法:字符串

    在计算机科学中,字符串是一系列字符的集合,是编程语言中非常重要的数据类型...通过对字符串循环左移、全排列等基本问题的学习和练习,可以加深对字符串操作的理解,并在面试或实际工作中更好地应对字符串相关的问题。

    基于位运算的两种字符串加密解密算法

    ### 基于位运算的两种字符串加密解密算法 #### 一、位运算概述及特点 位运算是一种直接在二进制位上进行的操作,主要用于处理数据的底层细节。在计算机科学领域,特别是操作系统、计算机网络协议以及软件设计等...

    Obama64字符串加密

    其次,位运算:加密过程中常用到的技巧之一是位运算,包括按位与(&),按位或(|),按位异或(^),左移()和右移(&gt;&gt;). 这些运算是对二进制数据进行操作,可以用来混淆原始数据的模式,达到加密的效果。例如,我们可以为...

    第二章 字符串处理和进制转换(C++)_codes.rar

    在C++编程语言中,字符串处理和进制转换是两个重要的概念,对于参与NOIP(全国青少年信息学奥林匹克竞赛)和信奥学习的学生来说,掌握这些技能至关重要。本章将深入探讨这两个主题,并通过实际代码示例进行讲解。 ...

    算法学习笔记.pdf

    算法学习是计算机科学与技术领域中非常重要的基础知识,掌握常用算法对于解决各类问题至关重要。在本篇算法学习笔记中,对一系列重要且常用的算法进行了整理和总结,以下是对文档内容中提及的知识点的详细解读。 一...

    算法学习笔记

    - Rotate String:字符串循环左移或右移指定的字符数。 - Reverse Words in a String:反转字符串中的所有单词。 - Valid Palindrome:检查一个字符串是否是回文。 - Longest Palindromic Substring:找到字符串中的...

    字符串MD5加密源代码实现可直接编译使用

    这些操作基于位运算(如异或、与、或、左移、右移等)和四个预定义的64位常量函数,以确保算法的复杂性和不可逆性。 4. **结果输出**:经过四轮计算后,A、B、C、D这四个32位变量组合成了最终的128位摘要,通常以32...

    一个c语言 位运算 的程序

    位运算包括但不限于按位与(&)、按位或(|)、按位异或(^)、按位取反(~)、左移()、右移(&gt;&gt;)等操作。接下来,我们将结合程序代码深入分析这些概念。 #### 程序代码分析 ```c #include #include #include void main() ...

    四川计算机C语言考试机试真题33次(含答案)

    1. **位运算**:理解二进制数的位运算,如左移和右移。 2. **数学运算**:掌握幂运算和累加运算的基本原理。 3. **字符串遍历**:熟悉如何从字符串中提取数字字符并转换为数值。 **算法步骤**: - 遍历字符串中的...

    C语言算法速查手册 完整代码

    6. **字符串处理**:包括字符串比较、模式匹配(如KMP算法)以及字符串操作函数的使用。 7. **数据结构**:如数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图等的基本操作和应用。 8. **计算几何**...

    leetcode卡-LeetCode---Arrays-and-Strings:LeetCode---数组和字符串

    通过学习和实践LeetCode上的数组和字符串题目,你将能够增强自己在算法设计、问题解决以及代码优化等方面的能力。这不仅有助于提升编程技能,也有助于在面试中脱颖而出。所以,如果你打算在这个领域深入,这个压缩包...

    精确字串匹配算法手册

    《精确字串匹配算法手册》是一本详尽的指南,由Christian Charras与Thierry Lecroq合著,旨在深入解析并探讨30种精确字串匹配...通过学习和掌握这些算法,可以极大地提高在实际项目中处理字符串匹配问题的能力和效率。

    易语言八种方法实现文本倒转源码

    本资源提供了八种不同的方法来实现文本倒转的功能,这对于学习易语言的字符串处理和算法设计具有很高的参考价值。下面,我们将详细探讨这八种方法。 1. **数组反转法**: 这种方法是将文本转换为字符数组,然后...

    MIPS-simulator:使用8位字典对二进制字符串进行压缩和解压缩

    - 二进制字符串压缩和解压缩的算法实现 - 测试用例和输入数据 - 编译和运行脚本 如果你想要深入学习这个项目,你可以下载MIPS-simulator-master压缩包,查阅源代码,理解其工作原理,并尝试修改和优化压缩算法,以...

    三级网络技术南开上机100题

    这些知识点主要涵盖基础数据结构(如数组、结构体)、排序算法、数值计算、字符串处理、素数判断和递推序列等,这些都是计算机科学与信息技术的基础内容,特别是在编程语言的学习和应用中至关重要。对于准备网络技术...

    网络技术上机100题

    `StrOR` 函数实现了字符串中所有"o"左边的字符右移,"o"本身删除,其余字符左移。这个题目涉及字符串处理和内存操作: - 字符串遍历 - 字符数组操作 - 字符比较和删除 - 内存填充(memset) 4. **字符串倒序...

    组合数学_999按6个算法839647521

    这是一种在计算机编程中常见的操作,尤其在处理数组或字符串时。例如,对于序列“12345”,一次循环左移后变为“23451”。 ### 邻位对换 邻位对换指的是交换序列中相邻位置的两个元素。这种操作常用于生成序列的...

    字符穿加密系统C语言实现

    总之,字符穿加密系统在C语言中的实现是一个涉及位操作、字符串处理和算法设计的过程。通过学习和实践,开发者不仅可以掌握加密技术,还能提升C语言编程能力,尤其是在处理底层数据和内存操作方面的技能。

    c语言常用算法

    10. **位运算**:C语言提供丰富的位运算符,如按位与、按位或、按位异或、左移、右移等,这些在进行位级操作的算法中非常有用,如位掩码技术、位图法等。 以上只是"常用算法"中的一部分知识点,实际学习中,还需要...

Global site tag (gtag.js) - Google Analytics