首页 > 代码库 > Chap3: question: 11 - 18
Chap3: question: 11 - 18
11. double 数值的整数次方
note: 浮点数表示时有误差,判等时必须自己根据精度要求实现。
+ View Code?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include <iostream> #include <ctime> using namespace std; bool Power_Input_Invalid = false ; // set a Global variant to check the input. bool equal( double num1, double num2) // key 1 { if (num1 - num2 >= -0.0000001 && num1 - num2 <= 0.0000001) return true ; return false ; } double Power( double base, int exponent) { Power_Input_Invalid = false ; if (equal(base,0.0) && exponent <= 0) /* 无意义 */ { Power_Input_Invalid = true ; return 0.0; } if (exponent == 0) return 1.0; bool sigmal = false ; // 0 denote positive exp if (exponent < 0) { exponent *= -1; sigmal = true ; // 1 denote negative exp } double result = base, tem = 1.0; while (exponent - 1 != 0) // key 2 { if (exponent & 1) tem *= result; result *= result; exponent >>= 1; } result *= tem; if (sigmal) result = 1.0 / result; return result; } int main() { double d; int v; clock_t start; int k = 0; while (cin >> d >> v) { start = clock (); double result = Power(d, v); if (!Power_Input_Invalid) cout << "Case " << k++ << ": " << Power(d, v) << " time:" << ( clock ()-start) << "ms" << endl; else cout << "Invalid input." << endl; } return 0; } |
12.打印 1 到最大的 n 位数
note: n 可能很大,如 100,就容易溢出
a. 字符串模拟法
1 #include <stdio.h> 2 #include <string.h> 3 bool Increment(char *); 4 void printNumber(char *); 5 6 void print1ToMax(int n) 7 { 8 if(n <= 0) return; 9 char *number = new char[n+1]; 10 memset(number, ‘0‘, n); 11 number[n] = ‘\0‘; 12 while(!Increment(number)) // Increment() return true denote overflow 13 { 14 printNumber(number); 15 } 16 delete[] number; 17 } 18 19 bool Increment(char *number) 20 { 21 bool overflow = false; 22 int carry = 0, len = strlen(number); 23 for(int i = len -1; i >= 0; --i) /* note: 从最右端开始增 is more easy */ 24 { 25 number[i] += carry; 26 if(i == len -1) ++number[i]; 27 if(number[i] > ‘9‘) 28 { 29 if(i == 0) 30 overflow = true; 31 else 32 { 33 number[i] -= 10; 34 carry = 1; 35 } 36 } 37 else break; 38 } 39 return overflow; 40 } 41 42 void printNumber(char *number) 43 { 44 if(number == NULL) return; 45 bool begin = false; 46 for(int i = 0; number[i] != ‘\0‘; ++i) 47 { 48 if(begin) 49 { 50 printf("%c", number[i]); 51 } 52 else if(number[i] != ‘0‘) 53 { 54 begin = true; 55 printf("%c", number[i]); 56 } 57 } 58 printf("\t"); 59 } 60 61 62 int main() 63 { 64 int N; 65 while(scanf("%d", &N) == 1) 66 { 67 print1ToMax(N); 68 } 69 return 0; 70 }
b. 数字排列法(由后到前,递归增加)
+ View Code?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | void printNumber( char *); void AddRecursively( char *, int , int ); void print1ToMax( int n) { if (n <= 0) return ; char *number = new char [n +1]; memset (number, ‘0‘ , n); number[n] = 0; AddRecursively(number, n, 0); delete [] number; } void AddRecursively( char *number, int length, int begin) { if (begin == length) { printNumber(number); return ; } for ( int i = ‘0‘ ; i <= ‘9‘ ; ++i) { number[begin] = i; AddRecursively(number, length, begin +1); } } void printNumber( char *number) { if (number == NULL) return ; bool begin = false ; for ( int i = 0; number[i] != ‘\0‘ ; ++i) { if (begin) { printf ( "%c" , number[i]); } else if (number[i] != ‘0‘ ) { begin = true ; printf ( "%c" , number[i]); } } if (!begin) return ; printf ( "\t" ); } |
运行结果如上。
13. O(1) 时间删除链表结点
其值赋为后继的值,删除后继结点。时间:[O(1) * (n-1) + O(n)] / n ≈ O(1). // 若检测欲删除结点是否在链表内,则 O(n) .
1 #include <stdio.h> 2 struct ListNode{ 3 int v; 4 ListNode * next; 5 }; 6 enum{ N = 5}; // set the number of Node in ListNode 7 /*************************************************************************/ 8 /******** Basic function which were needed ******************************/ 9 /* creat a List with the value of Node is 1, 2, …,N-1. */ 10 ListNode* creatList(){ 11 ListNode * pHead = NULL, *p; 12 for(int i = 1; i < N; ++i){ 13 ListNode *s = new ListNode; 14 s->v = i; 15 s->next = NULL; 16 if(pHead != NULL){ 17 p->next = s; 18 p = p->next; 19 }else{ 20 pHead = s; 21 p = pHead; 22 } 23 } 24 return pHead; 25 } 26 void printList(ListNode *pHead){ 27 if(pHead == NULL) { printf("NULL"); return; } 28 printf("%d —> ", pHead->v); 29 printList(pHead->next); 30 } 31 void release(ListNode *pHead) { 32 if(pHead == NULL) return; 33 release(pHead->next); 34 delete[] pHead; 35 pHead = NULL; 36 } 37 /****************************************************************************************/ 38 void deleteNode(ListNode *pHead, ListNode * pToBeDeleted){ 39 if(pHead == NULL || pToBeDeleted == NULL) return; 40 /* not the last one */ 41 if(pToBeDeleted->next != NULL){ 42 ListNode *pNext = pToBeDeleted->next; 43 pToBeDeleted->v = pToBeDeleted->next->v; 44 pToBeDeleted->next = pToBeDeleted->next->next; 45 delete[] pNext; 46 pNext = NULL; 47 }else{ 48 if(pToBeDeleted == pHead) { // List only has one Node 49 delete [] pHead; 50 pHead = NULL; 51 return; 52 }else { // the last one && not the head 53 ListNode *p = pHead; 54 while(p->next != pToBeDeleted && p->next != NULL) p = p->next; 55 if(p->next == NULL) return; 56 else{ 57 ListNode *s = p->next; 58 p->next = NULL; 59 delete[] s; 60 } 61 } 62 } 63 } 64 65 int main() 66 { 67 ListNode *pHead = creatList(); 68 printList(pHead); 69 printf("\ndelete 3: \n"); 70 71 deleteNode(pHead, pHead->next->next); // delete 3 (among) 72 printList(pHead); 73 printf("\ndelete 1: \n"); 74 75 deleteNode(pHead, pHead); // delete 1 (head) 76 printList(pHead); 77 printf("\ndelete 4: \n"); 78 79 deleteNode(pHead, pHead->next); // delete 4 (tail) 80 printList(pHead); 81 printf("\n"); 82 /* 83 ListNode *s = new ListNode; // not in the list, if wanted more robust , need check before deleteNode 84 deleteNode(pHead, s); 85 printList(pHead); 86 printf("\n"); 87 delete[] s; 88 */ 89 release(pHead); 90 return 0; 91 }
14. 使整数数组中奇数位于前部分,偶数位于后部分。
解耦合,使 Reorder函数可以复用。如代码:
1 #include <stdio.h> 2 3 bool isEven(int v) 4 { 5 return (v & 1) == 1; 6 } 7 8 bool isPositive(int v) 9 { 10 return v > 0; 11 } 12 13 void Reorder(int data[], int length, bool (*fcn)(int)) 14 { 15 if(length <= 1) return; 16 int low = 0, high = length - 1; 17 while(low < high) 18 { 19 while(low < high && fcn(data[low])) ++low; 20 while(low < high && !fcn(data[high])) --high; 21 if(low < high) 22 { 23 int tem = data[low]; 24 data[low] = data[high]; 25 data[high] = tem; 26 } 27 } 28 } 29 30 void printf(int data[], int length) 31 { 32 for(int i = 0; i < length; ++i) 33 { 34 printf("%-3d", data[i]); 35 } 36 printf("\n"); 37 } 38 int main() 39 { 40 printf("Test 1: odd element before even element. \n"); 41 int test1[] = {1, 2, 3, 4, 5, 6, 7}; 42 printf(test1, sizeof(test1)/sizeof(int)); 43 Reorder(test1,sizeof(test1)/4, isEven); /* 奇数放前面 */ 44 printf(test1, sizeof(test1)/4); 45 46 printf("Test 2: positive before Non-positive. \n"); 47 int test2[] = {-3, 3, -2, 2, 0, -1, 1}; 48 printf(test2, sizeof(test2)/sizeof(int)); 49 Reorder(test2,sizeof(test2)/4, isPositive); /* 正数放前面 */ 50 printf(test2, sizeof(test2)/4); 51 52 return 0; 53 }
15. 链表中倒数第 k 个结点
note: k = 0 或 k > LinkList.length().
+ View Code?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include <stdio.h> struct ListNode{ int v; ListNode * next; }; enum { N = 5}; // set the number of Node in ListNode /*************************************************************************/ /******** Basic function which were needed ******************************/ /* creat a List with the value of Node is 1, 2, …,N-1. */ ListNode* creatList(){ ListNode * pHead = NULL, *p; for ( int i = 1; i < N; ++i){ ListNode *s = new ListNode; s->v = i; s->next = NULL; if (pHead != NULL){ p->next = s; p = p->next; } else { pHead = s; p = pHead; } } return pHead; } void printList(ListNode *pHead){ if (pHead == NULL) { printf ( "NULL" ); return ; } printf ( "%d —> " , pHead->v); printList(pHead->next); } void release(ListNode *pHead) { if (pHead == NULL) return ; release(pHead->next); delete [] pHead; pHead = NULL; } /****************************************************************************************/ ListNode* FindKthTOTail(ListNode *pListHead, unsigned int k) { if (pListHead == NULL || k == 0) return NULL; // Note 1: for robust ListNode *pA, *pB; pA = pB = pListHead; for (unsigned int i = 0; i < k-1; ++i) // go ahead k-1 steps { if (pB->next == NULL) return NULL; // Note 2: the length of LinkList if less than k else pB = pB->next; } while (pB->next != NULL) { pA = pA->next; pB = pB->next; } return pA; } int main() { ListNode *pHead = creatList(); printf ( "LinkList: " ); printList(pHead); printf ( "\nTest: \n" ); ListNode *p; for ( int k = 0; k <= N; ++k) { p = FindKthTOTail(pHead, k); if (p != NULL) printf ( "倒数第 %d 个数: %d\n" , k, p->v); else printf ( "倒数第 %d 个数: Not Exist.\n" , k); } release(pHead); return 0; } |
16. 反转链表
+ View Code?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include <stdio.h> struct ListNode{ int v; ListNode * next; }; enum { N = 10}; // set the number of Node in ListNode /*************************************************************************/ /******** Basic function which were needed ******************************/ /* creat a List with the value of Node is 1, 2, …,N. */ ListNode* creatList(){ ListNode * pHead = NULL, *p; for ( int i = 1; i < N; ++i){ ListNode *s = new ListNode; s->v = i; s->next = NULL; if (pHead != NULL){ p->next = s; p = p->next; } else { pHead = s; p = pHead; } } return pHead; } void printList(ListNode *pHead){ if (pHead == NULL) { printf ( "NULL" ); return ; } printf ( "%d —> " , pHead->v); printList(pHead->next); } void release(ListNode *pHead) { if (pHead == NULL) return ; release(pHead->next); delete [] pHead; pHead = NULL; } /******************************************************/ ListNode* ReverseList(ListNode *pListHead) { ListNode *pPre, *pCur, *pPost; pPre = NULL, pCur = pListHead; while (pCur != NULL) { pPost = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pPost; } /* pCur == pPost == NULL, pPre point to the new ListHead */ return pPre; } int main() { ListNode *pHead = creatList(); printf ( "LinkList: " ); printList(pHead); printf ( "\n" ); pHead = ReverseList(pHead); printf ( "Reverse1: " ); printList(pHead); printf ( "\n" ); pHead = ReverseList(pHead); printf ( "Reverse2: " ); printList(pHead); printf ( "\n" ); release(pHead); return 0; } |
a. b. c.
17.合并两个排序的链表(递归)
1 #include <stdio.h> 2 struct ListNode{ 3 int v; 4 ListNode * next; 5 }; 6 /*************************************************************************/ 7 /******** Basic functions which were needed ******************************/ 8 /* creat a List with the value of Node is 1, 2, …,N. */ 9 ListNode* creatList(int begin, int N){ 10 ListNode * pHead = NULL, *p; 11 for(int i = begin; i <= N; ++i){ 12 ListNode *s = new ListNode; 13 s->v = i; 14 s->next = NULL; 15 if(pHead != NULL){ 16 p->next = s; 17 p = p->next; 18 }else { 19 pHead = s; 20 p = pHead; 21 } 22 } 23 return pHead; 24 } 25 void printList(ListNode *pHead){ 26 if(pHead == NULL) { printf("NULL"); return; } 27 printf("%d —> ", pHead->v); 28 printList(pHead->next); 29 } 30 void release(ListNode *pHead) { 31 if(pHead == NULL) return; 32 release(pHead->next); 33 delete[] pHead; 34 pHead = NULL; 35 } 36 /********************************************************************************/ 37 38 ListNode* Merge(ListNode *pHead1, ListNode *pHead2) //not create any new Node again 39 { 40 if(pHead1 == NULL) return pHead2; 41 if(pHead2 == NULL) return pHead1; 42 ListNode *pMergedHead = NULL; 43 if(pHead1->v <= pHead2->v) 44 { 45 pMergedHead = pHead1; 46 pMergedHead->next = Merge(pHead1->next, pHead2); 47 } 48 else 49 { 50 pMergedHead = pHead2; 51 pMergedHead->next = Merge(pHead1, pHead2->next); 52 } 53 return pMergedHead; // key point 54 } 55 56 int main() 57 { 58 ListNode *pHead1 = creatList(1, 5); 59 printf("LinkList1: "); 60 printList(pHead1); 61 printf("\n"); 62 ListNode *pHead2 = creatList(2, 6); 63 printf("LinkList1: "); 64 printList(pHead2); 65 printf("\n"); 66 67 ListNode *pHead3 = Merge(pHead1, pHead2); 68 printf("MergeList: "); 69 printList(pHead3); 70 printf("\n"); 71 72 release(pHead3); 73 return 0; 74 }
18. 判断树 B 是否为树 A 的子结构(递归)
+ View Code?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include <iostream> using namespace std; struct BTNode{ int v; // default positive Integer. BTNode *pLeft; BTNode *pRight; BTNode( int x) : v(x), pLeft(NULL), pRight(NULL) {} }; /********************************************************/ /***** Basic functions ***********/ BTNode* createBinaryTree( int r) { BTNode *pRoot = new BTNode(r); int u, v; cin >> u >> v; if (u != 0) pRoot->pLeft = createBinaryTree(u); if (v != 0) pRoot->pRight = createBinaryTree(v); return pRoot; } void release(BTNode *root){ if (root == NULL) return ; release(root->pLeft); release(root->pRight); delete [] root; root = NULL; } /******************************************************************/ bool treeAHasTreeB(BTNode *pRootA, BTNode *pRootB){ /* check from every node in the BinaryTeee pRoot1 */ if (pRootB == NULL) return true ; if (pRootA == NULL) return false ; if (pRootA->v != pRootB->v) return false ; return treeAHasTreeB(pRootA->pLeft, pRootB->pLeft) && treeAHasTreeB(pRootA->pRight, pRootB->pRight); } bool isSubTree(BTNode *pRoot1, BTNode *pRoot2){ bool result = false ; /* define the output when A or B is NULL */ if (pRoot2 == NULL) return true ; if (pRoot1 == NULL) return false ; result = treeAHasTreeB(pRoot1, pRoot2); if (!result) result = treeAHasTreeB(pRoot1->pLeft, pRoot2); if (!result) result = treeAHasTreeB(pRoot1->pLeft, pRoot2); return result; } int main(){ int TestTime = 3, k = 1; while (k <= TestTime) { cout << "Test " << k++ << ":" << endl; cout << "Create Tree A: " << endl; BTNode *pRoot1 = createBinaryTree(8); cout << "Create Tree B: " << endl; BTNode *pRoor2 = createBinaryTree(8); if (isSubTree(pRoot1, pRoor2)) cout << "Tree A has Tree B." << endl; else cout << "Tree A has not Tree B." << endl; release(pRoot1); release(pRoor2); } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。