- 浏览: 169492 次
- 性别:
- 来自: 广州
博客专栏
-
TCP/IP详解卷一>阅读...
浏览量:12549
文章分类
最新评论
-
master11:
你好,博主看完你的解释,好厉害啊!!佩服。如果想运行看一下效果 ...
数独人工解法的一些技巧及其python实现 -
evasiu:
chenxun1012033254 写道lz这么辛苦我也是醉了 ...
数独人工解法的一些技巧及其python实现 -
chenxun1012033254:
lz这么辛苦我也是醉了作为一名oier我说有一个算法叫做dan ...
数独人工解法的一些技巧及其python实现 -
xuyfiei:
lz很厉害,现在该是毕业了吧
恨毕业--读研一年总结 -
nphoenix:
呵呵 肯踏實的學東西已經很不錯了。畢業了工作之後,你就會發現個 ...
恨毕业--读研一年总结
前段日子又看了编程之美,后来闲着无聊学python去了,想着书将要送人,还是先总结一下,不然怕又要忘了,呵呵。
主要看的章节是第二、第三章,因为对数独有特别的感情,所以还顺带看了一四章关于数独的那两节。
1. 对于一个字节的无符号整形变量,求其二进制表示中“1”的个数。
最简单的莫过于用/跟%一个位一个位地测试:
算法的复杂度为O(n),但是操作符/跟%的代价都比较高。我比较喜欢的解法是这个:
把复杂的/跟%转换成&和-,循环的次数是1的个数。
1.1 给定两个正数A和B,问把A改变为B需要改变多少位(bit):我觉得就是对A、B先做一次异或,再计算有多少个1,即count(A^B).
1.2 给定一个整个n,判断它是否为2的方幂:n>0 && ((n&(n-1))==0)
2. 给定一个整数N,那么N的阶乘N!末尾有多少个0呢?N!的二进制表示中最低位1的位置又是在哪里呢?
其实这两道题的做法基本是一样的。对于十进制的N!,其末尾的0是由2*5取得的,2出现的次数很多,任何一个偶数都能提供一个因数2,而对于5,只有5,10,15这些能提供,25将提供两次5,125将贡献3个5,因此,只要计算N!中提供的5的个数,便可以计算出末尾有多少个0了,每个5决定一个末尾的0.
那么N!二进制表示最低位1呢?全是由*2造成的。从1乘起,只要每*2一次,0x1就会被左移一次,带来一个0,因此,只要计算N!提供的2的个数,例如2,6,10等提供一个2, 4提供两个,8提供3个....
不过,第二个问题有另一个更好的解法,就是N-(N二进制表示中1的个数)
3. 海量ID号中,其中有一个ID号超过了半数,找出这个ID。
解决的思路是每次取出两个不同的ID号来,然后把它们剔除。最后剩下的相同的ID号就是这个超过半数的ID。如下:
3.1 如果是有三个ID,它们的数量都超过了ID总数的1/4呢?
原本我们只需要一个nTimes来标识与当前candidate重复的ID的数量,现在有了3个ID,虽然我们同样也是每次取出4个不同的ID删掉,直到最后不再有4个不同的ID可以删除了之后,肯定最后剩下的ID号就是这3个ID号的重复,但是这次需要多个nTimes来维护4个不同的ID了:
4. 求两个正整数的最大公约数
辗转相除法:假设用f(x,y)表示x,y的最大公约数,取k=x/y,b=x%y,则x=ky+b,如果一个数能同时整除x和y,那么它必能同时整除y和b,而能够同时整除y和b的数也必能同时整除x和y,即x和y的最大公约数和y和b的最大公约数是相等的,即f(x,y)=f(y,x%y),如此便把原问题转换为求两个更小数的最大公约数,直到其中一个为0,剩下的另外一个就是两者最大的公约数。
假如x,y很大,取模运算的开销会很大,可以用减号运算来代替取模运算:
因为用了减号来替换原先的取模运算,循环的次数增加了,最不幸的是,gcd2(100000,1)将会走100000个循环!
深入辗转相除法,如果y=k*y', x=k*x',那么f(x,y)=k*f(x', y')。另外,如果x=p*x'且p是素数,并且y%p!=0(即y不能被p整除),那么f(x,y)=f(p*x', y)=f(x',y),这里,2无疑是p的最佳人选。
5. 给定两个字符串s1和s2,要求判定s2是否能够被通过s1做循环移位得到的字符串包含,例如,s1='aabcd'和s2='cdaa'返回true而s1='abcd',s2='acbd'返回false。
最直接的办法是通过对s1做len(s1)次循环并依次判断s2是否是该次循环得到的字符串的子字符串。当然,这样算法的复杂度约为O(n1*n2),其中n1为len(s1)而n2为len(s2)。
其实可以直接对s1做一次复制,得到一个新的字符串s3=s1s1,如果s2是s3的子串的话,那么通过循环移位s1可以包含s2。不过在这之前,要先判断len(s1)>len(s2)。
5.1 插播:strstr的实现
6. 字符串的距离
对于两个不相同的字符串,可以通过以下的方法将其变得相同:
(1)修改一个字符
(2)增加一个字符
(3)替换一个字符
例如,对于"abcdefg"和"abcdef",我们可以通过增加/减少一个"g"的方式来达到目的,它们的距离为1。给定两个字符串,计算它们的距离。
应该考虑如何将这个问题转化成规模较小的同样的问题。如果有两个串A="xabcdae"和B="xfdfa",它们的第一个字符是相同的,只要计算A[2,..7]和B[2,5]的距离就可以了。对于两个第一个字符不同的串,可以进行如下操作:
(1)一步操作后,再计算A[2,...,]和B[1,...,]的距离
(2)一步操作后,再计算A[1,...,]和B[2,...,]的距离
(3)一步操作后,再计算A[2,...,]和B[2,...,]的距离
可以用动态规则来做。
假设strA,strB的长度分别为lenA,lenB,result[i][j]表示strA[i,lenA]跟strB[j,lenB]的距离:
7. 重建二叉树:给出二叉树的前序、中序,要求重建二叉树。
8. 判断链表是否有环,如果有,返回指向环入口结点的指针,否则返回NULL
Note:这是3.11的程序改错,因为要求保持程序的基本框架,所以使用了下面的方法(其实是从网上看过来的),如果是我自己写,我估计就拿LinkList的结点地址去哈希了,一旦找到相同地址的结点,即可判断环的入口,或者遇到NULL,说明没有环。
遵循原先程序的框架,要判断是否有环,必须有两个指针以不同的步长来遍历链表,如果哪天他们相遇了,说明这个链表肯定有环,但是至于环的入口,得重头再找(在知道有环的情况下找入口)。
主要看的章节是第二、第三章,因为对数独有特别的感情,所以还顺带看了一四章关于数独的那两节。
1. 对于一个字节的无符号整形变量,求其二进制表示中“1”的个数。
最简单的莫过于用/跟%一个位一个位地测试:
int count( unsigned char n ) { int num = 0; while( n ) { if ( n%2 == 1 ) num++; n >>= 1; } return num; }
算法的复杂度为O(n),但是操作符/跟%的代价都比较高。我比较喜欢的解法是这个:
int count( unsigned char n ) { int num = 0; while( n ) { n &= (n-1); num++; } return num; }
把复杂的/跟%转换成&和-,循环的次数是1的个数。
1.1 给定两个正数A和B,问把A改变为B需要改变多少位(bit):我觉得就是对A、B先做一次异或,再计算有多少个1,即count(A^B).
1.2 给定一个整个n,判断它是否为2的方幂:n>0 && ((n&(n-1))==0)
2. 给定一个整数N,那么N的阶乘N!末尾有多少个0呢?N!的二进制表示中最低位1的位置又是在哪里呢?
其实这两道题的做法基本是一样的。对于十进制的N!,其末尾的0是由2*5取得的,2出现的次数很多,任何一个偶数都能提供一个因数2,而对于5,只有5,10,15这些能提供,25将提供两次5,125将贡献3个5,因此,只要计算N!中提供的5的个数,便可以计算出末尾有多少个0了,每个5决定一个末尾的0.
那么N!二进制表示最低位1呢?全是由*2造成的。从1乘起,只要每*2一次,0x1就会被左移一次,带来一个0,因此,只要计算N!提供的2的个数,例如2,6,10等提供一个2, 4提供两个,8提供3个....
//N!的十进制表示末尾有多少个0 int decCountLastZero( int n ) { int ret = 0; while( n ) { n /= 5; ret += n; } } //N!的二进制表示末尾有多少个0 int binCountLastZero( int n ) { int ret = 0; while( n ) { n >>= 1; ret += n; } return ret; }
不过,第二个问题有另一个更好的解法,就是N-(N二进制表示中1的个数)
3. 海量ID号中,其中有一个ID号超过了半数,找出这个ID。
解决的思路是每次取出两个不同的ID号来,然后把它们剔除。最后剩下的相同的ID号就是这个超过半数的ID。如下:
//假设以int来做ID typedef int ID; ID find( ID* ids, int N ) { ID candidate; int nTimes; //对所有ID进行一次遍历,nTimes用于标识两个不相等的ID号。 for ( int i=nTimes=0; i<N; i++ ) { if( nTimes == 0 ) { candidate = ids[i]; nTimes = 1; } else { if( candidate == ids[i] ) nTimes ++; else nTimes --; } } return candidate; }
3.1 如果是有三个ID,它们的数量都超过了ID总数的1/4呢?
原本我们只需要一个nTimes来标识与当前candidate重复的ID的数量,现在有了3个ID,虽然我们同样也是每次取出4个不同的ID删掉,直到最后不再有4个不同的ID可以删除了之后,肯定最后剩下的ID号就是这3个ID号的重复,但是这次需要多个nTimes来维护4个不同的ID了:
typedef int ID; struct Record { ID rId; int count; Record( int c = 0 ){ count = c; } }; void printTop3ID( ID* ids, int n ) { Record rec[4]; int i=0; while( i<n ) { for( int j=0; j<4; j++ ) { while( rec[j].count == 0 ) { ID cand = ids[i++]; int k=0; for( k=0; k<4; k++ ) { if( rec[k].count>0 && rec[k].rId == cand ) { rec[k].count++; break; } } if( k == 4 ) { rec[j].count ++; rec[j].rId = cand; } } } for( int j=0; j<4; j++ ) rec[j].count --; } for( int j=0; j<4; j++ ) { if( rec[j].count > 0 ) cout<<rec[j].rId<<endl; } }
4. 求两个正整数的最大公约数
辗转相除法:假设用f(x,y)表示x,y的最大公约数,取k=x/y,b=x%y,则x=ky+b,如果一个数能同时整除x和y,那么它必能同时整除y和b,而能够同时整除y和b的数也必能同时整除x和y,即x和y的最大公约数和y和b的最大公约数是相等的,即f(x,y)=f(y,x%y),如此便把原问题转换为求两个更小数的最大公约数,直到其中一个为0,剩下的另外一个就是两者最大的公约数。
int gcd1( int x, int y ) { assert( x>0 && y>0 ); while( y ) { int t = x; x = y; y = t%y; } return x; }
假如x,y很大,取模运算的开销会很大,可以用减号运算来代替取模运算:
int gcd2( int x, int y ) { assert( x>0 && y>0 ); while( x!=y ) { if( x>y ) x -= y; else y -= x; } return x; }
因为用了减号来替换原先的取模运算,循环的次数增加了,最不幸的是,gcd2(100000,1)将会走100000个循环!
深入辗转相除法,如果y=k*y', x=k*x',那么f(x,y)=k*f(x', y')。另外,如果x=p*x'且p是素数,并且y%p!=0(即y不能被p整除),那么f(x,y)=f(p*x', y)=f(x',y),这里,2无疑是p的最佳人选。
int gcd3( int x, int y ) { assert( x>0 && y>0 ); int base = 1; while( x!=y ) { if( x&0x1 == 0 ) { if( y&0x1 == 0 ) { base <<= 1; x >>= 1; y >>= 1; } else x >>= 1; } else { if( y&0x1 == 0 ) y >>= 1; else { if( x>y ) x -= y; else y -= x; } } } return base*x; }
5. 给定两个字符串s1和s2,要求判定s2是否能够被通过s1做循环移位得到的字符串包含,例如,s1='aabcd'和s2='cdaa'返回true而s1='abcd',s2='acbd'返回false。
最直接的办法是通过对s1做len(s1)次循环并依次判断s2是否是该次循环得到的字符串的子字符串。当然,这样算法的复杂度约为O(n1*n2),其中n1为len(s1)而n2为len(s2)。
其实可以直接对s1做一次复制,得到一个新的字符串s3=s1s1,如果s2是s3的子串的话,那么通过循环移位s1可以包含s2。不过在这之前,要先判断len(s1)>len(s2)。
bool isSubRotate( char* s1, char* s2 ) { if( strlen(s1) < strlen(s2) ) return false; int len = strlen(s1); char* s3 = new char[len*2+1]; strncpy( s3, s1, len ); strncpy( s3+len, s1, len ); bool res = !(strstr(s3, s2) == NULL ); delete s3; return res; }
5.1 插播:strstr的实现
char* my_strstr( const char* str1, const char* str2 ) { const char* buf, *sub; if( !*str2 ) return const_cast<char*>(str1); while( *str1 ) { buf = str1; sub = str2; do { if( !*buf ) return const_cast<char*>(str1); }while( *buf++ == *sub++ ); str1 ++; } return NULL; }
6. 字符串的距离
对于两个不相同的字符串,可以通过以下的方法将其变得相同:
(1)修改一个字符
(2)增加一个字符
(3)替换一个字符
例如,对于"abcdefg"和"abcdef",我们可以通过增加/减少一个"g"的方式来达到目的,它们的距离为1。给定两个字符串,计算它们的距离。
应该考虑如何将这个问题转化成规模较小的同样的问题。如果有两个串A="xabcdae"和B="xfdfa",它们的第一个字符是相同的,只要计算A[2,..7]和B[2,5]的距离就可以了。对于两个第一个字符不同的串,可以进行如下操作:
(1)一步操作后,再计算A[2,...,]和B[1,...,]的距离
(2)一步操作后,再计算A[1,...,]和B[2,...,]的距离
(3)一步操作后,再计算A[2,...,]和B[2,...,]的距离
可以用动态规则来做。
假设strA,strB的长度分别为lenA,lenB,result[i][j]表示strA[i,lenA]跟strB[j,lenB]的距离:
int strdist( const char* strA, const char* strB ) { int lenA = strlen(strA), lenB = strlen(strB); int** result = new int*[lenA+1]; for( int i=0; i<lenA+1; i++ ) result[i] = new int[lenB+1]; //初始化边界 for( int i=0; i<=lenA; i++ ) result[i][lenB] = lenA-i; for( int i=0; i<=lenB; i++ ) result[lenA][i] = lenB-i; for( int i=lenA-1; i>=0; i-- ) for( int j=lenB-1; j>=0; j-- ) { if( strA[i] == strB[j] ) result[i][j] = result[i+1][j+1]; else result[i][j] = minOfThree( result[i+1][j+1], result[i][j+1], result[i+1][j] )+1; } int ret = result[0][0]; for( int i=0; i<lenA+1; i++ ) delete[] result[i]; delete[] result; return ret; }
7. 重建二叉树:给出二叉树的前序、中序,要求重建二叉树。
template<typename T> struct Node { T value; Node *left, *right; Node( T v, Node* l=NULL, Node* r=NULL ): value(v), left(l), right(r){} }; template<typename n> Node<T>* rebuild( T* pPreOrder, T* pInOrder, int len ) { //pPreOrder是前序遍历的数组 //pInOrder是后序遍历的数组 //len是数组的长度,其实就是树结点的个数 if( pPreOrder==NULL || pInOrder==NULL || len<1 ) return NULL; Node<T>* subroot = new Node<T>(pPreOrder[0]); if( len == 1 ) return subroot; //如果len=1,该树只有一个叶子结点 T* rightInOrder=pInOrder; while( *rightInOrder != *pPreOrder ) rightInOrder ++; int leftLen = rightInOrder-pInOrder; int rightLen = len-leftLen-1; subroot->left = rebuild( pPreOrder+1, pInOrder, leftLen ); subroot->right = rebuild( pPreOrder+1+leftLen, rightInOrder+1, rightLen ); return subroot; }
8. 判断链表是否有环,如果有,返回指向环入口结点的指针,否则返回NULL
Note:这是3.11的程序改错,因为要求保持程序的基本框架,所以使用了下面的方法(其实是从网上看过来的),如果是我自己写,我估计就拿LinkList的结点地址去哈希了,一旦找到相同地址的结点,即可判断环的入口,或者遇到NULL,说明没有环。
遵循原先程序的框架,要判断是否有环,必须有两个指针以不同的步长来遍历链表,如果哪天他们相遇了,说明这个链表肯定有环,但是至于环的入口,得重头再找(在知道有环的情况下找入口)。
LinkList* IsCyclicLinkList( LinkList* pHead ) { //pCur走一步,pStart走两步,pCycle指向pCur和pStart重合的地方,如果有的话 LinkList* pCur, *pStart, *pCycle; pCur = pStart = pHead; pCycle = NULL; while( pCur != NULL && pStart != NULL ) { if( pStart->next == NULL ) return NULL; pStart = pStart->next->next; pCur = pCur->next; if( pStart == pCur ) { pCycle = pStart; break; } }//测试是否有环 if( pCycle != NULL ) //有环,接下来将找环的入口点 { //pCur从头找起,pStart则从重合的地方开始,如果pStart和pCur遇上了,说明pCur就是环的入口了 //不然环的入口就是pCycle pCur = pHead; while( pCur != pCycle ) { pStart = pCycle; while( pStart != pCur && pStart != pCycle ) pStart = pStart->next; if( pStart == pCur ) return pCur; pCur = pCur->next; } return pCycle; } return NULL; }
发表评论
-
我对KM算法的理解
2012-12-26 15:47 25848一般对KM算法的描述, ... -
正则表达式的一些笔记
2012-08-16 23:30 01. 文字符号 1.1 特殊字符:[ ] \ ^ $ . | ... -
一个小题目(单词统计)
2012-08-14 23:12 1316今天休息的时候看到一个关于单词统计的小题目: 统计一段由字符 ... -
数独人工解法的一些技巧及其python实现
2012-06-13 16:31 6602这段日子实现了十几种 ... -
Eva'Sudoku-0.1新鲜出炉啦~~
2012-05-27 21:06 1327呵呵,经过将近一个星期的对pygame的了解与熟悉,我终于磕磕 ... -
产生数独迷题
2012-05-24 18:13 1957随着数独解题算法DLX的 ... -
解数独——dancing link X
2012-05-21 22:59 7961折腾了一个星期,发现 ... -
总共有多少个数独?
2012-05-12 15:31 12741憋屈地看了一个星期的 ... -
《算法引论》之算法分析
2012-04-26 14:01 1571上次写博客,已经是半个月之前了。我也不知道我这段日子在干嘛了, ... -
编程之美续
2012-04-06 15:37 1115看完编程之美后看很多题,都会发现原来只是里面一些题目的变种(也 ... -
stl中的几个精美算法
2012-03-17 18:35 1161关于STL中的算法,我印象比较深刻的主要有用于list的sor ... -
STL和内存管理技术
2012-03-17 16:46 9717前段日子读了STL的源码 ... -
数据结构——2-3树
2012-02-10 14:25 7143年前实现了一个2-3树, ... -
数据结构 -- 二叉树(BST, AVLTree, RBTree, SplayTree)
2012-01-17 21:31 2760在《基于树的索引结构介绍》(http://philoscien ... -
编程珠玑--关于查找(二分法、自组织链、哈希)
2011-12-31 19:36 2103查找是我们现实生活中 ... -
编程珠玑 -- 关于堆
2011-12-28 15:31 1132堆是这样一种数据结构,它首先是一棵二叉树,而且还是一棵完全二叉 ... -
编程珠玑 -- 关于排序
2011-12-27 20:12 976《编程珠玑》主要提到 ... -
编程珠玑 -- 数据结构?
2011-12-21 21:15 658又开始看《编程珠玑》,发现之前看的也许不是很认真吧,再看一遍的 ... -
基于树的索引结构介绍
2011-07-01 17:59 2643转眼又七月份了。6月份后来就变成考试月了。因为图论要求写阅读报 ... -
Moment in Peking
2011-06-05 17:01 1027"Moment in Peking" wa ...
相关推荐
《编程之美:微软技术面试心得》是一本专为准备技术面试的程序员量身打造的书籍。这本书集结了微软公司在招聘过程中遇到的经典编程题目和解决思路,旨在帮助读者提升编程技能,增强解决实际问题的能力,同时也为面试...
Python编程之美在于其简洁、高效和可读性强的语法,以及丰富的库支持,使得它成为数据科学、Web开发、自动化脚本等多个领域的首选语言。"There should be one and preferably only one obvious way to do it." 这是...
Java并发编程之美_部分81 本篇文章主要讨论Java并发编程中的定时器功能,特别是使用ScheduledThreadPoolExecutor来实现定时任务的执行。同时,本篇文章还讨论了在并发编程中对需要复用但是会被下游修改的参数进行深...
"Python编程之美——带你进入Python语言世界"课程设计大纲参考 Python语言是一种高级、解释型的编程语言,它具有简洁、易学、强大等特点,广泛应用于数据科学、人工智能、网络爬虫、自动化操作等领域。本课程设计...
2012"编程之美"全国挑战赛题目 Ocean Scream
"编程之美微软技术面试心得" 编程之美微软技术面试心得是《编程之美微软技术面试心得.doc》的一份总结,该文档主要介绍了微软技术面试的心得体会和经验。下面是从该文档中所提取的知识点: 1. 微软技术面试的特点...
"编程之美"这个主题涵盖了各种有趣的算法,这些算法不仅能够帮助我们理解计算机科学的本质,还能激发我们的创新思维和逻辑能力。下面我们将深入探讨一些常见的有趣算法。 1. **排序算法**:排序是最基础也是最广泛...
《Java并发编程之美》是专为Java开发者设计的一本指南,旨在帮助读者克服并发编程的高门槛,从而在职场面试和高并发、高流量系统开发中得心应手。本书由瞿陆续和薛宾田合著,由中国工信出版集团旗下的电子工业出版社...
Java并发编程之美_部分31 本篇章节主要讲解了 Java 中的并发编程相关知识,包括乐观锁、公平锁、非公平锁、独占锁和共享锁等概念。 首先,介绍了乐观锁的概念,乐观锁是一种无锁机制,通过在表中添加版本号或业务...
《编程之美——微软技术面试心得》是一本深受程序员喜爱的书籍,它主要涵盖了微软公司在面试过程中经常考察的技术问题和解题思路。这本书不仅适合正在准备技术面试的求职者,也适合想要提升编程技能和思维能力的...
《Java并发编程之美》第7章中,我们深入探讨了Java并发包中的并发队列原理,特别是从尾节点进行插入这一关键操作。在Java并发队列中,offer()方法用于在队列尾部添加元素,它是线程安全的,主要依赖于CAS(Compare ...
8. **编程之美**:这可能指的是优雅、高效的代码编写,强调代码的可读性、可维护性和性能优化。Python鼓励使用简洁明了的语法,遵循PEP 8编码规范,可以提高代码质量。 9. **大数相加**:在Python中,可以使用内置...
《Python编程之美——带你进入Python语言世界》课程设计大纲详细解析 这门课程旨在引导学习者进入Python的世界,体验其语法简洁、类库丰富的魅力。无论是对于有C/C++或Java背景的程序员,还是对系统维护人员,...
读书笔记:Java 并发编程之美
读书笔记:Java并发编程之美
编程之美1的数目.pdf
Java并发编程之美(基础知识) Java并发编程是一个门槛较高的知识点,但是它在实际开发中非常重要。并发编程可以提高程序的效率和性能,但同时也会引入一些复杂的问题,如线程安全问题。因此,学习并发编程的基础...
读书笔记:Java并发编程之美笔记