`
evasiu
  • 浏览: 169481 次
  • 性别: Icon_minigender_2
  • 来自: 广州
博客专栏
Fa47b089-e026-399c-b770-017349f619d5
TCP/IP详解卷一>阅读...
浏览量:12549
社区版块
存档分类
最新评论

编程之美续

 
阅读更多
看完编程之美后看很多题,都会发现原来只是里面一些题目的变种(也大概因为看的是微软的笔试题吧。。),把原先的算法稍微一改,就变成了题目的解法,还是挺带劲的。

1. 反转单向链表:给出单向链表的头指针,要求把链表反转过来。
struct ListItem
{
	int value;
	struct ListItem* next;
};

ListItem* reverse( ListItem* pHead )
{
	//如果链表为空或只有一个元素,直接返回
	if( pHead==NULL || pHead->next == NULL )
		return pHead;
	ListItem* pNext=pHead->next;
       	ListItem* pCatch=pNext->next;
	pHead->next = NULL;
	while( pCatch != NULL )
	{
		pNext->next = pHead;
		pHead = pNext;
		pNext = pCatch;
		pCatch = pCatch->next;
	}
	pNext->next = pHead;
	pHead = pNext;
	return pHead;
}

[b]1.1 给定两个指针pHead和pStart, pHead是链表的头指针,把链表从pStart处反转过来,如:[\b]
1 -> 2 -> 3 -> 4 -> 5 -> NULL,pStart指向3,反转后变成:
3 -> 2 -> 1 -> 4 -> 5 -> NULL
可以看出,前面的例子是这个问题的特例,即当pStart指向链表的最后一个元素。因此,需要改的地方只有两处:
ListItem* reverse( ListItem* pHead, ListItem* pStart )
{
	//改动1:如果链表为空或只有一个元素,或pStart指向pHead,直接返回
	if( pHead==NULL || pHead == pStart || pStart == NULL )
		return pHead;
	ListItem* pNext=pHead->next;
       	ListItem* pCatch=pNext->next;
	pHead->next = pStart->next;	//改动2:末尾原为NULL,现为pStart->next(下同)
	while( pCatch != pStart->next )
	{
		pNext->next = pHead;
		pHead = pNext;
		pNext = pCatch;
		pCatch = pCatch->next;
	}
	pNext->next = pHead;
	return pStart;
}


2. 多个整数的最大公约数
前面我们提到两个整数的最大公约数,给出了三种做法,最后一种做法结合了一二种做法的优势。现在,如果有多个整数呢?有三种思路:
(1)递归求解,ngcd( arr[0,n-1] ) -> gcd( arr[n-1], ngcd( array[0,n-2] ) ),gcd我们使用最后一种做法:
int gcd( int a, int b )
{
	int base = 1;
	while( a!= b )
	{
		if( a&0x01 == 0 )
		{
			if( b&0x01 == 0 )
			{
				base <<= 1;
				a >>= 1;
				b >>= 1;
			}
			else
				a >>= 1;	
		}
		else
		{
			if( b&0x01 == 0 )
				b >>= 1;
			else
			{
				if( a> b )
					a -= b;
				else 
					b -= a;
			}
		}
	}
	return base*a;
}

//求多个数的最大公约数,函数接收数组的指针及数组大小
int ngcd1( int* array, int size )
{
	//递归求解
	if( size == 1 )
		return *array;
	return gcd( array[size-1], ngcd1( array, size-1 ) );
}


(2)化解递归:不难看出,上面的递归求解化解开来,就是依次求出arr[0,i]的最大公约数,然后通过求该公约数与arr[i+1]的最大公约数,最终得到arr[0,n-1]的公约数。
//继续使用上面的gcd
int ngcd3( int* array, int size )
{
	if( size == 1 )
		return array[0];
	int curGcd = gcd( array[0], array[1] );
	int i=2; 
	//当出现当前最大公约数为1时,无需再求剩下的元素的公约数了
	while( curGcd != 1 && i<size )
		curGcd = gcd( curGcd, array[i++] );
	return curGcd;
}


(3)辗转相除法:从数组中找出当前不为0的元素中的最小元素,剩下元素均余该元素,得到新的数组,直到最后只剩下一个元素不为0,该值即为最大公约数。过程如下:
(120, 168, 328, 624, 320) //当前最小非零元素为120,其余元素均模120
(120, 48, 88, 24, 80) //当前最小非零元素为24
(0, 0, 16, 24, 8 ) //当前最小非零元素为8
(0, 0, 0, 0, 8 ) //最大公约数为8

int ngcd2( int* scrArray, int size )
{
	int minIndex = 0;
	while( minIndex<size && !scrArray[minIndex++] );
	minIndex--;
	//if all elements are 0
	if( scrArray[minIndex] == 0 )
		return 0;
	int* array = new int[size];
	for( int i=0; i<size; i++ )
		array[i] = scrArray[i];
	int res = 1;

	//minElem 为非零元素中最小的那个
	int minElem = array[minIndex];
	for( int i=minIndex+1; i<size; i++ )
		if( array[i] && minElem > array[i] )
		{
			minElem = array[i];
			minIndex = i;
		}
	//找到当前最小非零元素,将其交换到第一个元素的位置
	array[minIndex] = array[0];
	array[0] = minElem;
	
	while( minElem>1 )
	{
		for( int i=1; i<size; i++ )
		{
			array[i] = array[i]%array[0];
			if( array[i] && array[i]<minElem )
			{
				minIndex = i;
				minElem = array[i];
			}
		}
		//如果minElem并没有改变,说明当前除了array[0]之外其余均为0了
		if( minElem == array[0] )
		{
			res = minElem;
			break;
		}
		array[minIndex] = array[0];
		array[0] = minElem;
	}
	delete[] array;
	return res;
}


3. 反转字符串:
本来这是一道挺简单的题目,但是题目说要尽量优化速度和空间,让我感觉压力蛮大。于是我决定上网瞧瞧,但是似乎没有找到挺好的结果。
char* reverse( char* str )
{
	//总共遍历了str两次,一次用于计算strlen,一次用于逐个交换。
	//使用到的额外的空间是两个用于遍历str的指针,一前一后
	int len = strlen(str);
	char* beg = str, *end = str+len-1;
	while( end > beg )
	{
		*end ^= *beg;
		*beg ^= *end;
		*end ^= *beg;
		end--;
		beg++;
	}
	return str;
}

3.1 如果以单词为单位进行反转呢?
即"I am a student" -> "student a am I"
策略:对整个字符串反转,然后再逐个单词反转回来。修改reverse为对字条串某一范围进行反转。
//end是有效下标
char* __reverse( char* str, int beg, int end )
{
	while( end>beg )
	{
		str[end] ^= str[beg];
		str[beg] ^= str[end];
		str[end] ^= str[beg];
		end--;
		beg++;
	}
	return str;
}

char* reverseByWord( char* str )
{
	int len = strlen( str );
	str = __reverse( str, 0, len-1 );
	int iStart =0, iEnd = 0;
	for( int i=0; i<len; i++ )
	{
		if( str[i] == ' ' )
		{
			iEnd = i-1;
			__reverse( str, iStart, iEnd );
			iStart = i+1;
		}
		else if( !((str[i]>='A'&&str[i]<='Z') or (str[i]>='a'&&str[i]<='z')) )
			iStart = i+1;
	}
	__reverse( str, iStart, len-1 );
	return str;
}


4. 约瑟夫环
约瑟夫环是昨晚同学问我的一个问题,问题的大致描述如下:
已知n个人(编号为1, 2, 3, ..., n)围成一圈,从编号为k的人开始报数1,数到m的那个人出列;接着又从出列的那个人的下一位开始报1,数到m的那个人出列,依此规律,求出最后剩下的那个人。
例如有n=5个人,m=2,从编号k=1的人开始报号,整个过程如下:
1 2 3 4 5 -> 2出列
3 4 5 1 -> 4出列
5 1 3 -> 1出列
3 5 -> 5出列
3 -> 最后剩下的人为3
可以通过模拟整个过程来求出最后剩下的那个人的序号,可是如果m,n很大的话,复杂度将会很高,尤其是用数组的时候,如何利用数学方法来求出最后那个人的序号呢?
通过上面的模拟过程,我们也大概可以看到,当有n个人时,第k个出列后,我们对剩下的n-1个人重新编号,编号方法如下:
k+1 -> 1
k+2 -> 2
k+3 -> 3
...
n -> n-k
1 -> 1-k+n
2 -> 2-k+n
...
k-1 -> n-1
这样,整个问题就变成一个n-1个人的小问题了。如果我们知道n-1个人这个问题中最后剩下的那个人的序号,那么通过上面的逆映射,我们便知道了n个人这个问题中最后剩下的那个人的序号。依次类推,要知道n-1个人最后剩下的那个人的序号,只要求出n-2个的,最后问题将会推到求出1个人的,而如果只有一个人,最后剩下的那个人的序号自然为1了。设fm[i]为i个人玩游戏,报数为m的人出列,最后剩下的那个人的编号(我怎么觉得有那么些绕口),那么有f[1]=1.如何从f[i-1]逆映射到f[i]呢?
设x'为某人在n个人时的编号,x为其在n-1个人时的编号,由上面的映射我们可以得到:
x' = (x+k)%n,其中k=m%n,因此,x'=(x+m)%n。问题在于,x'的范围在[0,n-1],没有编号为n的人,而多了个编号为0的人,实际上,编号为0的人其编号为n。因此我们得到:
f[1] = 1
f[i] = (f[i-1]+m)%i,if (f[i-1]+m)%i == 0,f[i]=i
我们的目标就是求出f[n],所以结果如下:
int josephus( int n, int m )
{
	int r = 1;
	for( int i=2; i<=n; i++ )
	{
		r = (r+m)%i;
		if( r == 0 )
			r = i;
	}
	return r;
}

如果从指定从编号为k的人开始报数1,结果是这样:
int josephus( int n, int m, int k )
{
	int r = josephus( n, m );
	return (r+k-1)%n;
}

0
0
分享到:
评论

相关推荐

    [编程珠玑·续].(美)本特利.扫描版.PDF

    [编程珠玑·续].(美)本特利.扫描版.PDF

    编程珠玑编程珠玑续(美)本特利(jb51.net).PDF

    《编程珠玑编程珠玑续(美)本特利(jb51.net).PDF》是一部深受程序员喜爱的经典著作,由知名计算机科学家Jon Bentley撰写。这本书是《编程珠玑》的续篇,延续了前作对编程艺术和算法设计的深入探讨,旨在提升程序员的...

    编程珠玑·续

    [编程珠玑·续].(美)本特利.扫描版

    编程珠玑(美)Jon Bentley

    在文件名“编程珠玑(续) (美)Jon Bentley.pdf”中,我们可以推测这可能是《编程珠玑》的后续篇章或者是扩展版,包含了更多关于编程实践和算法设计的深入探讨。这部分内容可能涵盖了更多现代编程议题,例如并行计算、...

    windows图形编程(PDF)-2

    windows图形编程 - 续上一个分卷包之二

    新三板策略报告:全市场教育策略,少儿编程教育行业龙头初显,童程童美、编玩边学等有何破局之道?-0706-安信证券-21页.pdf

    童程童美、编程猫等公司展现出了强劲的营收增长和市场扩张势头,续课率和复购率等运营指标也反映出市场的积极反馈。 报告还提到了一些具体的企业案例。例如,童程童美作为少儿编程行业的领导品牌,其母公司是达内...

    C#网络应用编程实验指导与开发实例源文件[评价可免费]

    7. **文件上传与下载**:理解如何通过网络传输大文件,包括断点续传、进度条显示等高级特性。 8. **WebSocket编程**:WebSocket是一种提供全双工通信的协议,允许服务器和客户端实时交互。C#提供了WebSocket类来...

    Qt自定义十套精美控件demo_续

    这些自定义控件的源码对学习Qt编程者来说是极好的学习素材,你可以通过阅读和分析代码,理解如何利用Qt的信号与槽机制、事件处理、样式表和动画系统来自定义控件。同时,导入工程直接运行,可以直观地看到每个控件的...

    商业编程-源码-精美的WEB在线文件管理(狐狸修改版)源码.zip

    《商业编程-源码-精美的WEB在线文件管理(狐狸修改版)源码》是一款针对企业和个人用户设计的在线文件管理系统,它集成了强大的文件上传、下载、预览、编辑和管理功能,使得用户可以通过Web界面随时随地访问和操作...

    金梅精美天气预报小偷 v3.0

    同时,为了提高用户体验,软件可能还应用了断点续传和多线程下载技术,确保在不稳定网络环境下也能顺利完成下载任务。 其次,“另类其它”标签暗示了这款应用可能具有非主流或者独特的特性。在天气预报领域,这可能...

    教育-少儿编程教育行业龙头初显,童程童美、编玩边学等有何破局之道?-全市场教育策略.pdf

    - 童程童美:作为少儿编程教育的领导品牌,专注于3-18岁儿童的编程教育,已经形成线上线下教育业务的闭环,通过“童程在线”将业务拓展至线上。 - 盛通股份:通过收购乐博教育,成为A股素质教育的龙头企业,主要面向...

    二十三种设计模式【PDF版】

    CSDN 的透明特别推崇《建筑的永恒之道》,认为从中探寻到软件的永恒之道,并就"设计模式"写了专门文章《探寻软件的永恒 之道 》,其中很多观点我看了很受启发,以前我也将"设计模式" 看成一个简单的解决方案,没有从一种...

    植物大战僵尸2欧美版 图片+xml素材资源

    这是一款由PopCap Games开发并由Electronic Arts发行的塔防类策略游戏,是《植物大战僵尸》的续作。游戏中,玩家需要通过种植各种功能不同的植物来抵御不断进犯的僵尸,保护自己的家园。游戏以其独特的游戏机制、...

    vc++ 应用源码包_6

    vc++动态链接库编程之DLL典型实例源代码下载 VC++仿Dreamweaver取色器源代码 VC++挂机锁屏系统源程序 VC++建立桌面或开始菜单快捷方式 VC++界面库编程 SkinMagic 2.21 动态库版本的使用和 Skin++动态库及静态库版本...

    leetcode和oj-Algorithm:一个曾经共享一些通用算法的项目

    《编程之美》 《编程之法:面试和算法心得》 《算法谜题》 都是思维题 基础 《编程珠玑》Programming Pearls 《编程珠玑(续)》 《数据结构与算法分析》 《Algorithms》 这本近千页的书只有6章,其中四章分别是排序,...

    WebFD v2.0 完全版(个人网络服务器)

    针对文件进行服务,可不改变文件位置的情况下进行文件共享下载,不使用网络编程语言,可自动生成下载HTML页面,免去手动制作的麻烦,全面支持中文名文件下载,支持续传,支持在线播放流媒体文件(*.mp3;*.rm;*.ra;*....

    个人WEB服务器架设绿色软件

    【简单建站】: WebFD 使用简单操作方便,只要拥有公网IP,动动鼠标左右键,即可... 全面支持中文名文件下载,支持续传 支持在线播放流媒体文件(*.mp3;*.rm;*.ra;*.asf)等 局域网内部使用文件交换速度可达 3M 每秒

    swift-Sica可以顺序或并行地执行各种动画

    在Swift编程中,Sica库使得序列化和并行执行多种动画变得异常简单,极大地提升了应用的用户体验和视觉吸引力。 首先,我们要理解Sica的核心特性。Sica库允许开发者顺序执行动画,这意味着一个动画完成后才会开始下...

    MATLAB入门简介PPT课件.pptx

    * 续行符: “…”(三个点),如果语句很长,可用续行符将一个语句写成多行。 * 注释符: “%”,其后面的内容为注释,对MATLAB的计算不产生任何影响。 MATLAB变量的规则包括: * 变量名:MATLAB中变量名是以字母...

Global site tag (gtag.js) - Google Analytics