打油诗一首:
一段破代码,总共20行,coding10分钟,调试一晚上。
字符串问题:(P61,面试题4,替换空格)
原题目:
解法1:最直观的做法是从头扫描到尾,一遇到空格我就做替换,如果在本字符串上做修改的话,字符串后面所有的字符都需要向后移动。否则的话会有两个字符被覆盖到。可以很明显的看出这个方法时间复杂度比较高,o(n^2),现在先来实现以下这个做法。o(n^2)的代码是拿不到offer的。。
/* **Coding Interviews P61 Replace Blank Character */ #include <iostream> using namespace std; void ReplaceBlankCharacter( char *); int main() { char example[100] = "we are happle."; ReplaceBlankCharacter( example ); return 0; } void ReplaceBlankCharacter( char *str ) { if( str != NULL ) { //给begin 和end 两个指针赋初始值 char * begin = str; char * end = NULL; while( ( *begin ) != '\0') { begin++; } end = begin; char *newEnd = end; begin = str; while( *begin != '\0' ) { if( *begin == ' ' )//如果遇到了空格 { begin ++; newEnd = end + 2; while( end >= begin ) { *( end + 2 ) = *end; end --; } end = newEnd; *( begin + 1 ) = '0'; *( begin ) = '2'; *( begin - 1 ) = '%'; begin += 2; } else //没有遇到空格则往后走 begin++; } cout << str << endl; } }
运行结果:
出的小错误:
1.判断指针的值的时候 一定不要忘记 *,2.小细节一定要考虑清楚,譬如说是大于等于还是单存的大于。
解法2:解法一无疑时间复杂度比较大,我们可以考虑从后面开始移动字符。首先遍历字符串,查找有几个空格,然后计算替换后总共需要的字符串长度,然后在移动字符。
/* **Coding Interviews P61 Replace Blank Character */ #include <iostream> using namespace std; void ReplaceBlankCharacter( char *); int main() { char example[100] = "Tao Tao is a stupid donkey."; ReplaceBlankCharacter( example ); return 0; } void ReplaceBlankCharacter( char *str ) { if( str != NULL ) //判断是否为空。 { char *start = str ; char *end = NULL; int blankNum = 0 ; char *firstBlank = NULL;// 记录第一个空格的位置 while( *start != '\0' )//计算字符串原先长度,并且查找字符串中包含几个空格 { if( *start == ' ' ) { if( blankNum == 0 ) firstBlank = start; blankNum++ ; } start++ ; } firstBlank--; end = start + 2 * blankNum ;//记录最后的位置 while( start >= firstBlank ) { if( *start != ' ' ) { *end-- = *start--; } else { start --; *end-- = '0' ; *end-- = '2' ; *end-- = '%' ; } } cout << str << endl; } }
从头到尾打印链表:
题目:
思想:我们能想到的最简单的是改变指针的指向,但是这会修改到原先输入的数据。如果我们打算修改输入的数据,最好询问下面试官是否可以做这些修改。其余的两种方法一个是递归,另外一种就是使用栈来帮助实现。
代码:
/* **Coding Interviews P61 */ #include <iostream> #include <stack> using namespace std; struct ListNode { int data; ListNode* next; }; void AddNode(ListNode *pHead,int data) { if( pHead != NULL ) { ListNode * current = pHead; while( current -> next != NULL ) { current = current -> next; } ListNode *s = new ListNode; s -> data = data; s -> next = NULL; current -> next = s; } } void InitList(ListNode *pHead) { AddNode( pHead, 1 ); AddNode( pHead, 2 ); AddNode( pHead, 3 ); AddNode( pHead, 4 ); AddNode( pHead, 5 ); AddNode( pHead, 6 ); AddNode( pHead, 7 ); } void PrintList(ListNode * pHead) { if( pHead != NULL ) { ListNode * current = pHead ; if( pHead -> next == NULL ) ; else { current = pHead -> next; while( current -> next != NULL ) { cout << current -> data << " "; current = current -> next; } cout << current -> data; } cout << endl; } } void PrintListReverse_UseStack(ListNode *pHead) { if( pHead != NULL ) { if( pHead -> next == NULL )//Do nothing if the list only have the head Node ; else { ListNode *current = pHead -> next; //The first Node stack< int > st; while( current != NULL ) { st.push( current -> data ); current = current -> next; } int s; while( !st.empty() ) { s = st.top(); st.pop(); cout << s << " "; } } cout << endl; } } void PrintListReverse( ListNode * pHead ) { if( pHead != NULL ) { if(pHead -> next != NULL ) { PrintListReverse( pHead -> next ); cout << pHead -> next -> data << " "; } } } int main() { ListNode *pHead = new ListNode; pHead -> next = NULL; InitList(pHead); PrintList(pHead); PrintListReverse_UseStack(pHead); PrintListReverse(pHead); return 0; }
写完可以测试几个特殊情况,只有一个节点和pHead 为空,记得在面试写代码的时候处理这种特殊情况。