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
分享到:
相关推荐
关于经典算法--压缩字符串(将字符串内连续重复出现的字符进行压缩),个人的想法
将一个字符串循环右移的三种方法, 第一种:逐个右移;第二种,调用strcpy()函数;第三种,调用memcpy()函数
编写一个函数,作用是把一个char组成的字符串循环右移n个。比如原来是“abcdefghi”如果n=2,移位后应该是“hiabcdefgh” 函数头是这样的: //pStr是指向以'\0'结尾的字符串的指针
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
字符串循环左移算法问题描述:暴力法利用三次翻转巧妙实现 问题描述: 给定一个字符串s[0…n-1],要求将s的前k个字符移动到字符串s的尾部。 举个栗子:将字符串“HelloWorld”的前5个字符移动到字符串的尾部,即要...
运行程序之后输入任意的字符串,将字符串转化成二进制数字字符串,然后利用LZ78算法实现对二进制字符串压缩解压,最后再恢复原来的字符串
基于Qt写了一个字符串加密的算法模块(有源码),并封装成了动态库,有测试用例。实现的加密解密算法是AES加密对称算法和BlowFish。用户可以直接用动态库,也可以用源码编译。
bat文件 字符串提取以及替换等操作 在dos窗口下运行 供学习参考
主要内容 需要掌握的内容 字符串循环左移 LCS最长递增子序列 字符串全排列 递归、非递归 KMP Huffman编码 需要了解的内容 Manacher算法 BM算法 数据结构-字符串全文共87页,当前为第3页。 字符串循环左移 4/88 给定...
Java版本算法练习+笔记总结 按照数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构进行系统的练习 每道题都有标号和题目链接.zip
给定一个字符串S[0…N-1],要求把S的前k个字符移动到S的尾部,如把字符串“abcdef”前面的2个字符‘a’、‘b’移动到字符串的尾部,得到新字符串“cdefab”:即字符串循环左移k位。 循环左移k位等价于循环右移n-k位...
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
1.编程学习的初学者,对字符串以及对应的Hex比较陌生人群。 2.需要对字符串有批量特定输出格式的。 3.对字符串的内存码有特定需求的。 备注: 希望该工具能帮助各位,由于积分不够故在此赚点资源分,大家如果在使用...
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
编辑距离算法,比较字符串相似度 pb11.5版本
2.1 字符串 & 方法区 2.2 字符串 & 堆 2.3 总结
主要介绍了使用java自带des加密算法实现文件加密和字符串加密的示例,需要的朋友可以参考下
带通配符的字符串匹配算法,带通配符的字符串匹配算法
参考清华大学的《算法设计与分析》课后的习题,输入两个字符串后输出其编辑距离。
也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'和pattern='ababc',子串是包含在主串中的,同时它...