首页 > 代码库 > Chap3: question: 11 - 18

Chap3: question: 11 - 18

2024-07-02 02:51:11   226人阅读

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 }
Code

  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 }
Code

 

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 }
Code

 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 }
Code

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;
}

 

 

 

 

 

 


联系
我们