Open ghostbody opened 8 years ago
int gcd(int a, int b) {
if(a > b) {
return gcd(a - b, b);
}
else if(a < b){
return gcd(b - a, a);
}
else {
return a;
}
}
int main() {
int m, n, k;
while(scanf("%d%d", &m, &n) != EOF) {
k = gcd(m, n);
printf("%d\n", k);
}
return 0;
}
那道最大公约数的问题为什么我问题runtime error
求大神帮忙解决
@obrcnh 递归函数不对,请参考西西里hint里面的那个函数。
是只能用辗转相除法吗
不一定,不过你需要用数学的知识,证明一下你的式子是对的。 ┗|`O′|┛
也许你就发明了更好的算法了,hhhh
万能的TA告诉我为什么这个循环开始进行之后list2[0]就变成了111,……然后一开始判断出来的111就不见了,好懵逼啊
@inkblack ???请你将问题描述清楚,不知道你说啥。
就是这个题不是排序吗……然后我像这样循环之后,本来111应该是最大的,但是出现在了第二个,我一步步调试之后就看到是list2[0]本来应该是2,但是变成了111.然而我并不知道为什么……于是我每次循环都输出了一次list2[0],只看到它输出了一次2.后面全都是111QAQ
@inkblack 1.题目并没有告诉你说最大的数字是111 2.如果你真的想解决问题,请用简单的方法告诉别人的问题是什么,你这个描述真的不知道在说什么。
……简单讲,就是循环之后list2[0]的值发生了改变…………
@inkblack List2并没有进行赋值操作,看不出问题。也许你的list3和list2用的同样地址。
String 操作的后三个函数
From: The Art of Programming link
1.1 旋转字符串
题目描述
给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部,使得原字符串变成字符串“cdefab”。请写一个函数完成此功能,要求对长度为n的字符串操作的时间复杂度为 O(n),空间复杂度为 O(1)。
分析与解法
解法一:暴力移位法
初看此题,可能最先想到的方法是按照题目所要求的,把需要移动的字符一个一个地移动到字符串的尾部,如此我们可以实现一个函数
LeftShiftOne(char* s, int n)
,以完成移动一个字符到字符串尾部的功能,代码如下所示:因此,若要把字符串开头的m个字符移动到字符串的尾部,则可以如下操作:
下面,我们来分析一下这种方法的时间复杂度和空间复杂度。
针对长度为n的字符串来说,假设需要移动m个字符到字符串的尾部,那么总共需要 mn 次操作,同时设立一个变量保存第一个字符,如此,时间复杂度为O(m \ n),空间复杂度为O(1),空间复杂度符合题目要求,但时间复杂度不符合,所以,我们得需要寻找其他更好的办法来降低时间复杂度。
解法二:三步反转法
对于这个问题,换一个角度思考一下。
将一个字符串分成X和Y两个部分,在每部分字符串上定义反转操作,如X^T,即把X的所有字符反转(如,X="abc",那么X^T="cba"),那么就得到下面的结论:(X^TY^T)^T=YX,显然就解决了字符串的反转问题。
例如,字符串 abcdef ,若要让def翻转到abc的前头,只要按照下述3个步骤操作即可:
如下图所示:
代码则可以这么写:
这就是把字符串分为两个部分,先各自反转再整体反转的方法,时间复杂度为O(n),空间复杂度为O(1),达到了题目的要求。
举一反三
1、链表翻转。给出一个链表和一个数k,比如,链表为1→2→3→4→5→6,k=2,则翻转后2→1→6→5→4→3,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→6→5,用程序实现。
2、编写程序,在原字符串中把字符串尾部的m个字符移动到字符串的头部,要求:长度为n的字符串操作时间复杂度为O(n),空间复杂度为O(1)。 例如,原字符串为”Ilovebaofeng”,m=7,输出结果为:”baofengIlove”。
3、单词翻转。输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变,句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如,输入“I am a student.”,则输出“student. a am I”。
字符串包含
题目描述
给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短。请问,如何最快地判断字符串B中所有字母是否都在字符串A里?
为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数bool StringContains(string &A, string &B)
比如,如果是下面两个字符串:
String 1:ABCD
String 2:BAD
答案是true,即String2里的字母在String1里也都有,或者说String2是String1的真子集。
如果是下面两个字符串:
String 1:ABCD
String 2:BCE
答案是false,因为字符串String2里的E字母不在字符串String1里。
同时,如果string1:ABCD,string 2:AA,同样返回true。
分析与解法
题目描述虽长,但题意很明了,就是给定一长一短的两个字符串A,B,假设A长B短,要求判断B是否包含在字符串A中。
初看似乎简单,但实现起来并不轻松,且如果面试官步步紧逼,一个一个否决你能想到的方法,要你给出更好、最好的方案时,恐怕就要伤不少脑筋了。
解法一
判断string2中的字符是否在string1中?最直观也是最简单的思路是,针对string2中每一个字符,逐个与string1中每个字符比较,看它是否在String1中。
代码可如下编写:
假设n是字符串String1的长度,m是字符串String2的长度,那么此算法,需要O(n*m)次操作。显然,时间开销太大,应该找到一种更好的办法。
解法二
如果允许排序的话,我们可以考虑下排序。比如可先对这两个字符串的字母进行排序,然后再同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作,之后的线性扫描需要O(m+n)次操作。
关于排序方法,可采用最常用的快速排序,参考代码如下:
解法三
有没有比快速排序更好的方法呢?
我们换一种角度思考本问题:
假设有一个仅由字母组成字串,让每个字母与一个素数对应,从2开始,往后类推,A对应2,B对应3,C对应5,......。遍历第一个字串,把每个字母对应素数相乘。最终会得到一个整数。
利用上面字母和素数的对应关系,对应第二个字符串中的字母,然后轮询,用每个字母对应的素数除前面得到的整数。如果结果有余数,说明结果为false。如果整个过程中没有余数,则说明第二个字符串是第一个的子集了(判断是不是真子集,可以比较两个字符串对应的素数乘积,若相等则不是真子集)。
思路总结如下:
如前所述,算法的时间复杂度为O(m+n)的最好的情况为O(n)(遍历短的字符串的第一个数,与长字符串素数的乘积相除,即出现余数,便可退出程序,返回false),n为长字串的长度,空间复杂度为O(1)。
此种素数相乘的方法看似完美,但缺点是素数相乘的结果容易导致整数溢出。
解法四
如果面试官继续追问,还有没有更好的办法呢?计数排序?除了计数排序呢?
事实上,可以先把长字符串a中的所有字符都放入一个Hashtable里,然后轮询短字符串b,看短字符串b的每个字符是否都在Hashtable里,如果都存在,说明长字符串a包含短字符串b,否则,说明不包含。
再进一步,我们可以对字符串A,用位运算(26bit整数表示)计算出一个“签名”,再用B中的字符到A里面进行查找。
这个方法的实质是用一个整数代替了hashtable,空间复杂度为O(1),时间复杂度还是O(n + m)。
举一反三
1、变位词
字符串转换成整数
题目描述
输入一个由数字组成的字符串,把它转换成整数并输出。例如:输入字符串"123",输出整数123。
给定函数原型
int StrToInt(const char *str)
,实现字符串转换成整数的功能,不能使用库函数atoi。分析与解法
本题考查的实际上就是字符串转换成整数的问题,或者说是要你自行实现atoi函数。那如何实现把表示整数的字符串正确地转换成整数呢?以"123"作为例子:
因此,此题的基本思路便是:从左至右扫描字符串,把之前得到的数字乘以10,再加上当前字符表示的数字。
思路有了,你可能不假思索,写下如下代码:
显然,上述代码忽略了以下细节:
上述其它问题比较好处理,但溢出问题比较麻烦,所以咱们来重点看下溢出问题。
一般说来,当发生溢出时,取最大或最小的int值。即大于正整数能表示的范围时返回MAX_INT:2147483647;小于负整数能表示的范围时返回MIN_INT:-2147483648。
我们先设置一些变量:
而后,你可能会编写如下代码段处理溢出问题:
但当上述代码转换" 10522545459"会出错,因为正常的话理应得到MAX_INT:2147483647,但程序运行结果将会是:1932610867。
为什么呢?因为当给定字符串" 10522545459"时,而MAX_INT是2147483647,即MAX_INT(2147483647) < n_10(1052254545_10),所以当扫描到最后一个字符‘9’的时候,执行上面的这行代码:
已无意义,因为此时(MAX_INT - n * 10)已经小于0,程序已经出错。
针对这种由于输入了一个很大的数字转换之后会超过能够表示的最大的整数而导致的溢出情况,我们有两种处理方式可以选择:
对于上面第一种方式,虽然我们把n定义了长整型,但最后返回时系统会自动转换成整型。咱们下面主要来看第二种处理方式。
对于上面第二种方式,先举两个例子说明下:
一直以来,我们努力的目的归根结底是为了更好的处理溢出,但上述第二种处理方式考虑到直接计算n * 10 + c 可能会大于MAX_INT导致溢出,那么便两边同时除以10,只比较n和MAX_INT / 10的大小,从而巧妙的规避了计算n*10这一乘法步骤,转换成计算除法MAX_INT/10代替,不能不说此法颇妙。
如此我们可以写出正确的处理溢出的代码:
从而,字符串转换成整数,完整的参考代码为:
举一反三
分析:此题虽然类似于atoi函数,但毕竟double为64位,而且支持小数,因而边界条件更加严格,写代码时需要更加注意。