首页 技术 正文

Chap3: question: 11 – 18

技术 2022年11月6日
0 收藏 954 点赞 802 浏览 10778 个字

11. double 数值的整数次方

note: 浮点数表示时有误差，判等时必须自己根据精度要求实现。

#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
bool overflow = false;
if(exponent < 0)
{
if(exponent == INT_MIN) { overflow = true; exponent++;}
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(overflow) result *= base;
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;
}

Chap3: question: 11 – 18

12.打印 1 到最大的 n 位数

note: n 可能很大，如 100，就容易溢出

a. 字符串模拟法

 #include <stdio.h>
 #include <string.h>
 bool Increment(char *);
 void printNumber(char *); void print1ToMax(int n)
 {
     if(n <= ) return;
     char *number = new char[n+];
     memset(number, '', n);
     number[n] = '\0';
     while(!Increment(number)) // Increment() return true denote overflow
     {
         printNumber(number);
     }
     delete[] number;
 } bool Increment(char *number)
 {
     bool overflow = false;
     int carry = , len = strlen(number);
     for(int i = len -; i >= ; --i)   /*   note: 从最右端开始增 is more easy    */
     {
         number[i] += carry;
         if(i == len -)  ++number[i];
         if(number[i] > '')
         {
             if(i == )
                 overflow = true;
             else
             {
                 number[i] -= ;
                 carry = ;
             }
         }
         else break;
     }
     return overflow;
 } void printNumber(char *number)
 {
     if(number == NULL) return;
     bool begin = false;
     for(int i = ; number[i] != '\0'; ++i)
     {
         if(begin)
         {
             printf("%c", number[i]);
         }
         else if(number[i] != '')
         {
             begin = true;
             printf("%c", number[i]);
         }
     }
     printf("\t");
 } int main()
 {
     int N;
     while(scanf("%d", &N) == )
     {
         print1ToMax(N);
     }
     return ;
 }

Code

Chap3: question: 11 – 18

b. 数字排列法（由后到前，递归增加）

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) .

 #include <stdio.h>
 struct ListNode{
     int v;
     ListNode * next;
 };
 enum{ N = }; // 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 = ; 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;
 }
 /****************************************************************************************/
 void deleteNode(ListNode *pHead, ListNode * pToBeDeleted){
     if(pHead == NULL || pToBeDeleted == NULL) return;
     /*   not the last one  */
     if(pToBeDeleted->next != NULL){
         ListNode *pNext = pToBeDeleted->next;
         pToBeDeleted->v = pToBeDeleted->next->v;
         pToBeDeleted->next = pToBeDeleted->next->next;
         delete[] pNext;
         pNext = NULL;
     }else{
         if(pToBeDeleted == pHead) {  // List only has one Node
             delete [] pHead;
             pHead = NULL;
             return;
         }else {                     // the last one && not the head
             ListNode *p = pHead;
             while(p->next != pToBeDeleted && p->next != NULL) p = p->next;
             if(p->next == NULL) return;
             else{
                 ListNode *s = p->next;
                 p->next = NULL;
                 delete[] s;
             }
         }
     }
 } int main()
 {
     ListNode *pHead = creatList();
     printList(pHead);
     printf("\ndelete 3: \n");     deleteNode(pHead, pHead->next->next); // delete 3 (among)
     printList(pHead);
     printf("\ndelete 1: \n");     deleteNode(pHead, pHead);      // delete 1 (head)
     printList(pHead);
     printf("\ndelete 4: \n");     deleteNode(pHead, pHead->next); // delete 4 (tail)
     printList(pHead);
     printf("\n");
 /*
     ListNode *s = new ListNode; // not in the list, if wanted more robust , need check before deleteNode
     deleteNode(pHead, s);
     printList(pHead);
     printf("\n");
     delete[] s;
 */
     release(pHead);
     return ;
 }

Code

Chap3: question: 11 – 18

14. 使整数数组中奇数位于前部分，偶数位于后部分。

解耦合，使 Reorder函数可以复用。如代码：

 #include <stdio.h> bool isEven(int v)
 {
     return (v & ) == ;
 } bool isPositive(int v)
 {
     return v > ;
 } void Reorder(int data[], int length, bool (*fcn)(int))
 {
     if(length <= ) return;
     int low = , high = length - ;
     while(low < high)
     {
         while(low < high && fcn(data[low])) ++low;
         while(low < high && !fcn(data[high])) --high;
         if(low < high)
         {
             int tem = data[low];
             data[low] = data[high];
             data[high] = tem;
         }
     }
 } void printf(int data[], int length)
 {
     for(int i = ; i < length; ++i)
     {
         printf("%-3d", data[i]);
     }
     printf("\n");
 }
 int main()
 {
     printf("Test 1: odd element before even element. \n");
     int test1[] = {, , , , , , };
     printf(test1, sizeof(test1)/sizeof(int));
     Reorder(test1,sizeof(test1)/, isEven);   /*  奇数放前面    */
     printf(test1, sizeof(test1)/);     printf("Test 2: positive before Non-positive. \n");
     int test2[] = {-, , -, , , -, };
     printf(test2, sizeof(test2)/sizeof(int));
     Reorder(test2,sizeof(test2)/, isPositive); /*  正数放前面  */
     printf(test2, sizeof(test2)/);     return ;
 }

Code

Chap3: question: 11 – 18

 15. 链表中倒数第 k 个结点

note: k = 0 或 k > LinkList.length().

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

Chap3: question: 11 – 18

16. 反转链表

#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. Chap3: question: 11 – 18   b.Chap3: question: 11 – 18   c. Chap3: question: 11 – 18

17.合并两个排序的链表（递归）

 #include <stdio.h>
 struct ListNode{
     int v;
     ListNode * next;
 };
 /*************************************************************************/
 /********  Basic functions which were needed ******************************/
 /*  creat a List with the value of Node is 1, 2, …，N.  */
 ListNode* creatList(int begin, int N){
     ListNode * pHead = NULL, *p;
     for(int i = begin; 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* Merge(ListNode *pHead1, ListNode *pHead2) //not create any new Node again
 {
     if(pHead1 == NULL) return pHead2;
     if(pHead2 == NULL) return pHead1;
     ListNode *pMergedHead = NULL;
     if(pHead1->v <= pHead2->v)
     {
         pMergedHead = pHead1;
         pMergedHead->next = Merge(pHead1->next, pHead2);
     }
     else
     {
         pMergedHead = pHead2;
         pMergedHead->next = Merge(pHead1, pHead2->next);
     }
     return pMergedHead; // key point
 } int main()
 {
     ListNode *pHead1 = creatList(, );
     printf("LinkList1: ");
     printList(pHead1);
     printf("\n");
     ListNode *pHead2 = creatList(, );
     printf("LinkList1: ");
     printList(pHead2);
     printf("\n");     ListNode *pHead3 = Merge(pHead1, pHead2);
     printf("MergeList: ");
     printList(pHead3);
     printf("\n");     release(pHead3);
     return ;
 }

Code

Chap3: question: 11 – 18

18. 判断树 B 是否为树 A 的子结构（递归）

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

Chap3: question: 11 – 18Chap3: question: 11 – 18Chap3: question: 11 – 18

点赞 954

贡献者

上一篇： 压测 linux + jexus + mono + asp.net mvc
下一篇： js动画性能提升笔记
相关推荐
python开发_常用的python模块及安装方法
python开发_常用的python模块及安装方法
adodb：我们领导推荐的数据库连接组件bsddb3：BerkeleyDB的连接组件Cheetah-1.0：我比较喜欢这个版本的cheeta…
技术
日期：2022-11-24 点赞：878 阅读：8,965
Educational Codeforces Round 11 C. Hard Process 二分
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…
技术
日期：2022-11-24 点赞：807 阅读：5,486
下载Ubuntn 17.04 内核源代码
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
技术
日期：2022-11-24 点赞：569 阅读：6,331
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
技术
日期：2022-11-24 点赞：733 阅读：6,114
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…
技术
日期：2022-11-24 点赞：512 阅读：7,747
Struts的使用
Struts的使用
一、Struts2的获取　　Struts的官方网站为：http://struts.apache.org/　　下载完Struts2的jar包,…
技术
日期：2022-11-24 点赞：671 阅读：4,781
Lomu

贡献者

这家伙很懒，只想把你留下。

文章
42
收藏
0
人气
134,523
粉丝
进主页
文章展示
  • [ 技术 ] python开发_常用的python模块及安装方法
  • [ 技术 ] Educational Codeforces Round 11 C. Hard Process 二分
  • [ 技术 ] 下载Ubuntn 17.04 内核源代码
  • [ 技术 ] 可用Active Desktop Calendar V7.86 注册码序列号
  • [ 技术 ] Android调用系统相机、自定义相机、处理大图片
  • [ 技术 ] Struts的使用
    • 个人收藏笔记记录
    我的笔记
    首页 首页 菜单 首页 首页