31 栈的压入、弹出序列
题目：输入两个整数序列。第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列｛1，2，3，4，5｝是某栈的压栈序列，序列｛4，5，3，2，1｝是该压栈序列对应的一个弹出序列，但｛4，3，5，1，2｝就不可能是该压栈序列的弹出序列。
思路：
先将一下我自己的思路，入栈序列有多少个数就循环多少次，然后每次先入栈一个数，之后循环出栈（只要栈顶和出栈序列相等就可以出栈），成功出栈一次，出栈序列就加一。跳出循环后看出栈序列的地址减出栈序列初始地址是不是等于元素数就可以判断成功和失败。
答案的思路是，进来先判断能不能满足出栈条件，不能出栈就循环进栈，如果没有东西可以进栈了 就循环结束。
两种思路都可以，我也都写了，但是结束循环的条件不太一样，自己写一下感受感受。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 #define INITLENGTH 40 #define INCREMENT 20 typedef struct stack { int *top; int *base; int stackSize; }stack; /************栈的辅助代码*******************/ bool Push(stack* stack1,int data) { int* temp; //栈满 if(stack1->top - stack1->base >=stack1->stackSize) { temp = (int*)realloc(stack1->base,sizeof(int)*(stack1->stackSize+INCREMENT)); if(temp == NULL)return false; stack1->base = temp; stack1->top = stack1->base + stack1->stackSize; stack1->stackSize+=INCREMENT; } *stack1->top++ = data; return true; } int Pop(stack* stack1) { if(stack1->stackSize<=0) return 0; stack1->stackSize-=1; return *--stack1->top; } stack* InitStack() { stack* stack1= (stack*)malloc(sizeof(stack)); stack1->base = (int*)malloc(sizeof(int)*INITLENGTH); if(stack1->base!=NULL) { stack1->top = stack1->base; stack1->stackSize = INITLENGTH; return stack1; } return NULL; } /************************************************/ bool IsPopOrder(const int* pPush, const int* pPop, int nLength) { stack* stack1 = InitStack(); const int* pPushStart = pPush; const int* pPopStart = pPop; if(pPush == NULL || pPop == NULL || nLength<=0) return false; while(pPop-pPopStart<nLength) { while(*(stack1->top-1)!=*pPop && pPush-pPushStart<nLength) { Push(stack1,*pPush++); } if(*(stack1->top-1)==*pPop) { *pPop++; Pop(stack1); } else break; } if(pPop-pPopStart == nLength ) return true; else return false; /* stack* stack1 = InitStack(); const int* pPushStart = pPush; const int* pPopStart = pPop; if(pPush == NULL || pPop == NULL || nLength<=0) return false; while((pPush - pPushStart <nLength)) { Push(stack1,*pPush++); while(*(stack1->top-1)== *pPop) { Pop(stack1); pPop++; } } if(pPop-pPopStart==nLength) return true; else return false;*/ } void main() { const int nLength = 5; int push[] = {1,2,3,4,5}; int pop[] = {4,5,3,2,1}; printf("%d",IsPopOrder(push,pop,nLength)); }
32 从上到下打印二叉树
题目一：不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如，输入图中的二叉树，则依次打印出8，6，10，5，7，9，11.
在这里插入图片描述思路：
这是二叉树的遍历，但是和我们熟悉的前序中序后序遍历不一样，他是每层遍历。捋一下，是怎么一个过程。先判断8不是空，把8打印出来，然后再打印8的左孩子，再打印8的右孩子；再打印8的左孩子的左孩子。。。。。。会发现规律，可以设置一个打印序列，最开始序列中只有8，打印完8加入6和10；打印完6再加入5和7.。。。。由于是FIFO，所以可以用队列的方式。
备注：
苦逼的C语言不自带队列函数，所以还要自己写。队列因为是FIFO，所以最好写成环形的，这样不会浪费。但是如果初次分配空间不足之后，如何开辟新的空间，没想好。所以只是自己写了一个不太完善的环形队列先用着。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 #define INITLENGTH 40 #define INCREMENT 20 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; typedef struct { BinaryTreeNode** treeNode; int head; int tail; int queueSize; }seqQueue; /***************环形队列辅助代码*******************/ seqQueue* InitSeqQueue() { seqQueue* queue = (seqQueue*)malloc(sizeof(seqQueue)); queue->treeNode = (BinaryTreeNode**)malloc(sizeof(BinaryTreeNode*)*INITLENGTH); queue->tail = 0; queue->head = 0; if(!queue->treeNode) return NULL; queue->queueSize = INITLENGTH; return queue; } bool SeqQueuePush(seqQueue* queue,BinaryTreeNode* treeNode) { if(queue->tail % queue->queueSize == queue->head-1) return false; queue->treeNode[queue->tail] = treeNode; queue->tail = (queue->tail+1)%queue->queueSize; return true; } BinaryTreeNode* SeqQueuePop(seqQueue* queue) { BinaryTreeNode* temp; if(queue->tail==queue->head) return NULL; temp = queue->treeNode[queue->head]; queue->treeNode[queue->head] = NULL; queue->head = (queue->head+1)%queue->queueSize; return temp; } bool IsEmptySeqQueue(seqQueue* queue) { if(queue->tail==queue->head) return true; else return false; } /**************************************************/ /**************二叉树辅助代码*********************/ BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } void PrintPreorder(BinaryTreeNode* head) { BinaryTreeNode* temp; seqQueue* treeQueue = InitSeqQueue(); if(head == NULL) return; SeqQueuePush(treeQueue,head); while(!IsEmptySeqQueue(treeQueue)) { temp = SeqQueuePop(treeQueue); printf("%d ",temp->value); if(temp->left) SeqQueuePush(treeQueue,temp->left); if(temp->right) SeqQueuePush(treeQueue,temp->right); } } /**************************************************/ void main() { BinaryTreeNode* node1 = CreateBinaryTreeNode(8); BinaryTreeNode* node2 = CreateBinaryTreeNode(6); BinaryTreeNode* node3 = CreateBinaryTreeNode(10); BinaryTreeNode* node4 = CreateBinaryTreeNode(5); BinaryTreeNode* node5 = CreateBinaryTreeNode(7); BinaryTreeNode* node6 = CreateBinaryTreeNode(9); BinaryTreeNode* node7 = CreateBinaryTreeNode(11); ConnectTreeNodes(node1,node2,node3); ConnectTreeNodes(node2,node4,node5); ConnectTreeNodes(node3,node6,node7); PrintPreorder(node1); }
题目2：从上到下按层打印二叉树，同一层的节点按从左到右的舒徐打印，每一层打印到一行。
在这里插入图片描述
思路：就是在上一道题的基础上，在每行结束的时候打印一个换行。怎么实现呢。队列中的每个节点都是按顺序添加的，首先只需要一个量thisLineCount，去知道当前行还剩多少个，打印一次，thisLineCount-1，到0的时候就打印换行。
看似解决了，但是还不行，因为不知道下一行有多少，所以还需要一个变量来记录下一行有多少。
8进队列，thisLineCount+1；
8出列，thisLineCount-1；6进队列，nextLineCount+1,10进队列，nextLineCount+1.检查thisLineCount = 0，打印换行，然后thisLineCount = nextLineCount，nextLineCount = 0.一定要想好顺序。
void PrintPreorder(BinaryTreeNode* head) { int thisLineCount = 1; int nextLineCount = 0; BinaryTreeNode* temp; seqQueue* treeQueue = InitSeqQueue(); if(head == NULL) return; SeqQueuePush(treeQueue,head); while(!IsEmptySeqQueue(treeQueue)) { temp = SeqQueuePop(treeQueue); printf("%d ",temp->value); thisLineCount--; if(temp->left) { SeqQueuePush(treeQueue,temp->left); nextLineCount++; } if(temp->right) { SeqQueuePush(treeQueue,temp->right); nextLineCount++; } if(!thisLineCount) { printf("\n"); thisLineCount = nextLineCount; nextLineCount = 0; } } }
33 二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某 二叉搜索树的后序遍历结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字 都互不相同。例如，输入数组｛5，7，6，9，11，10，8｝则返回true.因为这个整数序列是下图中的后序遍历结果。如果输入的数组是｛7，4，6，5｝，则由于没有哪一棵二叉搜索树的后序遍历结果是这个序列，因此返回false.
思路：
先明确二叉搜索树的概念：二叉搜索树就是所有左子树都比根节点小，所有右子树都比根节点大。
再看这道题，后序遍历就是左右根的顺序遍历二叉树，所以输入数组的最后一个值就是该树的根节点，如果是二叉搜索树，应该前面会有一个分界点，前面的都比根小，后面的都比根大。
用语言描述过程：输入数组，数组的最后一个值为根节点，从数组的第一个值开始查找，查找到第一个比根大的值分界，前面为这个树的左子树；之后遍历剩下的，如果所以都比根小则把他判定为右子树，否则直接返回失败。有了左右子树之后，再分别按上述过程递归，最后截止条件是子树中只有1个值（两个也行）。
注意：
1.右子树传入长度的时候要记得把根节点减掉，不然死循环了
2.截止条件是该子树长度个数<=2,1,0,都可以。0个1个就不说了，2个也可以因为剩两个的话可以一个是另一个的右子树，也可以另一个是这个的左子树，都可以。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 #define INITLENGTH 40 #define INCREMENT 20 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; /**************二叉树辅助代码*********************/ BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } bool VerifySequenceOfBST(int* sequence,int length) { int root; int i; int endLeft; int statusLeft,statusRight; if(sequence == NULL || length <= 0) return false; root = sequence[length-1]; for(i=0;i<length-1;i++) { if(sequence[i]>root) break; } endLeft = i;//记录左子树的个数 for(;i<length-1;i++) { if(sequence[i]<root) return false; } if(endLeft<=2)//0或者1或者2 statusLeft = true; else statusLeft = VerifySequenceOfBST(sequence,endLeft); if(length-1-endLeft<=2)//或者2 statusRight = true; else statusRight = VerifySequenceOfBST(&sequence[endLeft+1],length-1-endLeft); return statusLeft && statusRight; } void main() { //int sequence[] = {5,7,6,9,11,10,8}; int sequence[]= {7,4,6,5}; //int sequence[]= {1,2,3,4}; if(VerifySequenceOfBST(sequence,sizeof(sequence)/sizeof(int))) printf("YES"); else printf("NO"); }
34 二叉树中和为某一值的路径
题目:输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点一条路径。
思路：先明确路径的概念，路径是从根节点到叶子节点的所有节点的集合。一定是叶子节点。
这道问题是二叉树的遍历问题，只不过遍历要从根节点开始，也就是先序遍历，用递归。而且在遍历的过程中要不断的判断两件事：1.当前路径的和是否等于目标和；2.现在到没到叶子。这个很好实现，叶子的判断只要看有没有孩子就好了，目标和可以在函数传入一个变量，每次路径新加值的时候更新这个变量就好了。
下一个问题：如何打印路径，只有指向孩子的节点，没有指向父母的节点啊，所以需要借助一个队列，把当前路径的所有节点值都入队列，判断成功后从队列头打印到队列尾就可以了。
还有一个问题，如果判断这条路径不行了怎么办？要把这个节点从队列中删掉，也就是后入先出，所以我们可以用栈，到叶子后，是就打印，不是就不打印，之后把这个叶子节点出栈，把现在的和减去这个叶子节点。
所以递归函数要做下面几件事：
1.把节点入栈，currentSum加
2.判断是否是叶子，并且值是否相等，相等就打印
3.如果有左孩子，递归左孩子
4.如果有右孩子，递归右孩子
5.把节点出栈，currentSum减
备注：2页可以放在34的后面，没什么关系。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 #define INITLENGTH 40 #define INCREMENT 20 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; typedef struct stack { int *top; int *base; int stackSize; }stack; /************栈的辅助代码*******************/ bool Push(stack* stack1,int data) { int* temp; //栈满 if(stack1->top - stack1->base >=stack1->stackSize) { temp = (int*)realloc(stack1->base,sizeof(int)*(stack1->stackSize+INCREMENT)); if(temp == NULL)return false; stack1->base = temp; stack1->top = stack1->base + stack1->stackSize; stack1->stackSize+=INCREMENT; } *stack1->top++ = data; return true; } int Pop(stack* stack1) { if(stack1->stackSize<=0) return 0; stack1->stackSize-=1; return *--stack1->top; } stack* InitStack() { stack* stack1= (stack*)malloc(sizeof(stack)); stack1->base = (int*)malloc(sizeof(int)*INITLENGTH); if(stack1->base!=NULL) { stack1->top = stack1->base; stack1->stackSize = INITLENGTH; return stack1; } return NULL; } /*************************************************/ /**************二叉树辅助代码*********************/ BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } void FindPathCore(BinaryTreeNode* pRoot,int expectedSum,int currentSum,stack *stack1) { bool isLeaf = false; int *temp = NULL; isLeaf = pRoot->left == NULL && pRoot->right == NULL; currentSum+=pRoot->value; Push(stack1,pRoot->value); if(isLeaf && expectedSum == currentSum) { for(temp = stack1->base;temp<stack1->top;temp++) printf("%d ",*temp); printf("\n"); } if(pRoot->left) FindPathCore(pRoot->left,expectedSum,currentSum,stack1); if(pRoot->right) FindPathCore(pRoot->right,expectedSum,currentSum,stack1); currentSum-=pRoot->value; Pop(stack1); } void FindPath(BinaryTreeNode* pRoot,int expectedSum) { int currentSum = 0; stack *stack1 = InitStack(); if(pRoot == NULL) return; FindPathCore(pRoot,expectedSum,currentSum,stack1); } void main() { BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10); BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5); BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7); ConnectTreeNodes(pNode10, pNode5, pNode12); ConnectTreeNodes(pNode5, pNode4, pNode7); FindPath(pNode10,19); }
35 复杂链表的复制
题目：请实现函数ComplexListNode Clone(ComplexListNode pHead)复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针还有一个sibling指针指向链表中的任意节点或者NULL。
思路：
先说说没看解析之前的想法：
1.先遍历链表，把整条链表复制出来
2.再遍历链表，如果有sibling，就再遍历原链表查出指向第n个，然后去新链表找到有sibling的那个节点，然后指向第n个。这样时间复杂度有点高，O(N2)
解析给的第一个新思路：
在第一次遍历的之后建立一个哈希表，把链表中的节点value都放到哈希表中。找sibling的时候，直接根据值取哈希表里就能找到该节点在哪个位置了。
第二个思路：
这个思路很巧妙，复制的时候不是新复制一个链表，而是在原链表的原节点后面复制出一个。然后找sibling的之后，直接把该节点后面的节点的sibling指向原sibling后面的节点就可以了。然后再把偶数的链表拎出来就是新链表了。一共三步：
1.在原链表上每个节点的后面复制新节点
2.遍历链表，把sibling全部指好
3.遍历链表，把偶数节点拎出来连到一起
每一步写一个函数，思路更清晰。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 typedef struct ComplexListNode { int value; struct ComplexListNode* next; struct ComplexListNode* sibling; }ComplexListNode; /***********************复杂链表辅助代码************************/ ComplexListNode* CreateNode(int value) { ComplexListNode* node = (ComplexListNode*)malloc(sizeof(ComplexListNode)); if(node == NULL)return NULL; node->next = NULL; node->sibling = NULL; node->value = value; return node; } void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling) { if(pNode == NULL)return; pNode->next = pNext; pNode->sibling = pSibling; } /******************************************************************/ void CloneNodes(ComplexListNode* pHead) { ComplexListNode* pCloned; ComplexListNode* pNode = pHead; while(pNode) { pCloned = (ComplexListNode*)malloc(sizeof(ComplexListNode)); pCloned->value = pNode->value; pCloned->next = pNode->next; pCloned->sibling = NULL; pNode->next = pCloned; pNode = pCloned->next; } } void ConnectSiblingNodes(ComplexListNode* pHead) { ComplexListNode* pNode = pHead; while(pNode!=NULL) { if(pNode->sibling!=NULL) { pNode->next->sibling = pNode->sibling->next; } pNode = pNode->next->next; } } ComplexListNode* ReconnectNodes(ComplexListNode* pHead) { ComplexListNode* pClonedHead = NULL; ComplexListNode* pClonedNode = NULL; ComplexListNode* pNode = NULL; if(pHead == NULL)return ; pNode = pHead; pClonedHead = pHead->next; pClonedNode = pHead->next; while(pClonedNode!=NULL && pNode!=NULL) { if(pClonedNode!=NULL) { pNode->next = pClonedNode->next; pNode = pClonedNode->next; } if(pNode!=NULL) { pClonedNode->next = pNode->next; pClonedNode = pNode->next; } } return pClonedHead; } ComplexListNode* Clone(ComplexListNode* pHead) { if(pHead == NULL)return NULL; CloneNodes(pHead); ConnectSiblingNodes(pHead); return ReconnectNodes(pHead); } void main() { ComplexListNode* pCloneHead = NULL; ComplexListNode* pNode1 = CreateNode(1); ComplexListNode* pNode2 = CreateNode(2); ComplexListNode* pNode3 = CreateNode(3); ComplexListNode* pNode4 = CreateNode(4); ComplexListNode* pNode5 = CreateNode(5); BuildNodes(pNode1, pNode2, pNode3); BuildNodes(pNode2, pNode3, pNode5); BuildNodes(pNode3, pNode4, NULL); BuildNodes(pNode4, pNode5, pNode2); pCloneHead = Clone(pNode1); }
36 二叉搜索树与双向链表
题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。比如输入下图中左边的二叉搜索树，则输出转换以后的排序双向链表。
在这里插入图片描述思路：这道题有点不好想，确实把我绕进去了。第一步很明确，左孩子替代成双向链表中的前向指针，右孩子代替成双向链表中的后向指针，而且也很容易想到这是二叉树的中序遍历，剩下就不知道怎么做了。画画图，推导几步就找到规律了。
在这里插入图片描述
红色指针代表函数传的指针，蓝色指针代表函数递归到哪个节点，绿色指针代表新建立的双向链表节点
中序遍历最开始肯定可以找到最左的子树，也就是双向链表中的最小的一项,啥也不用做。递归函数返回到6，6和4建立双指针。递归再回到8，8和6建立双指针。最后按照右下角的顺序遍历，每次和前面的一项建立双指针就好了。所以这道题就简化成了，在中序遍历的前提下，加一个指针pLastNode ，指向前一个被递归的节点，两个指针间建立双向链表。因为这个指针是不断改指向位置的，所以必须使用二级指针。
最后返回的时候，pLastNode 不断向左寻找，找到头的时候把它返回。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; /******************二叉树辅助代码**********************/ BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } /**********************************************/ void ConvertNode(BinaryTreeNode* pNode,BinaryTreeNode** pLastNode) { if(pNode->left) ConvertNode(pNode->left,pLastNode); if(*pLastNode) { pNode->left = *pLastNode; (*pLastNode)->right = pNode; } *pLastNode = pNode; if(pNode->right) ConvertNode(pNode->right,pLastNode); } BinaryTreeNode* Convert(BinaryTreeNode* pRoot) { BinaryTreeNode* pLastNode = NULL; if(pRoot == NULL)return; ConvertNode(pRoot,&pLastNode); while(pLastNode->left) pLastNode = pLastNode->left; return pLastNode; } void main() { BinaryTreeNode* convert = NULL; BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12); BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16); ConnectTreeNodes(pNode10,pNode6,pNode14); ConnectTreeNodes(pNode6,pNode4,pNode8); ConnectTreeNodes(pNode14,pNode12,pNode16); convert = Convert(pNode10); }
37 序列化二叉树
题目：请实现两个函数，分别用来序列化和反序列化二叉树。
思路：可以根据前序遍历的顺序来序列化二叉树，在碰到NULL指针是，用特殊字符$,节点的数值之间用，隔开。
备注：C语言char的递归太麻烦了。因为传入char指针，所以不希望他被更改，应该用一级指针，但是在递归的过程中又需要这个指针指向下一个值，试了好久，最后 通过两个函数实现，第一个函数传入一级指针，然后直接取一级指针的地址作为二级指针函数的递归输入。
这道题能很好地考验对二级指针的掌握，我写的只是满足了基本要求，有很多不完善的地方，实在是心态搞崩了。大家参考一下就好。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 #define INITLENGTH 40 #define INCREMENT 20 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; /**************二叉树辅助代码*********************/ BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } /*****************************************************/ void DeserializeCore(BinaryTreeNode** pRoot,char** str) { if(**str>='0' &&**str<='9') { *pRoot = CreateBinaryTreeNode(**str-'0'); *str+=2; DeserializeCore(&(*pRoot)->left,str); *str+=2; DeserializeCore(&(*pRoot)->right,str); } } void Deserialize(BinaryTreeNode** pRoot,char* str) { DeserializeCore(pRoot,&str); } void SerializeCore(BinaryTreeNode* pRoot,char** str) { if(pRoot == NULL) { **str = '$'; (*str)++; **str = ','; (*str)++; return; } else { **str = '0'+pRoot->value; (*str)++; **str = ','; (*str)++; } SerializeCore(pRoot->left,str); SerializeCore(pRoot->right,str); } void Serialize(BinaryTreeNode* pRoot,char* p) { SerializeCore(pRoot,&p); } void main() { int i =0; char* str = (char*)malloc(sizeof(char)*INITLENGTH); BinaryTreeNode* pRoot; BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1); BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2); BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); ConnectTreeNodes(pNode1, pNode2, pNode3); ConnectTreeNodes(pNode2, pNode4, NULL); ConnectTreeNodes(pNode3, pNode5, pNode6); for(i=0;i<INITLENGTH;i++) str[i] = '\0'; Serialize(pNode1,str); Deserialize(&pRoot,str); }
38 字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如，输入字符串abc，则打印出：abc，acb，bac，bca，cab和cba。
思路：用人的思维去思考这个打印的过程：第一个字母有abc三种选择，然后确定了第一个之后（比如a），第二个字母有bc两种选择，然后确定了第二个之后（比如b），第三个字母就只有c一个选择了，这时候就可以打印abc了。打印完之后返回，再把第二个字母换成另一个，再往下走，打印出acb。然后再往回回。
这是很明显的递归类问题，设定一个指针指向第一个节点，把这个节点和后面的所有节点都换，换完一次就继续这个指针往后移。当这个指针指向‘\0’的时候说明结束了，打印。由于打印的时候需要头指针，所以传递参数的时候把头指针也传进去。
注意：还是要注意下char[] str 和char str的区别。像这道题需要改变字符串，就只能用char[] str，用char str时就会出错。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 void PermutationCore(char* pStr,char* pBigin) { char* p = pBigin; char temp; if(*pBigin=='\0') printf("%s\n",pStr); for(;*p!='\0';p++) { temp = *pBigin; *pBigin = *p; *p = temp; PermutationCore(pStr,pBigin+1); temp = *pBigin; *pBigin = *p; *p = temp; } } void Permutation(char* pStr) { if(pStr == NULL)return; PermutationCore(pStr,pStr); } void main() { char str[]= "abcd"; Permutation(str); }
39 数组中超过一半的数字
题目：数组中一个数字出现的次数出现的次数超过数组长度的一半。请找出这个数字。例如，输入一个长度为9的数组｛1，2，3，2，2，2，5，4，2｝。由于2在数组中出现了5次，超过数组的一半，因此输出2.
思路：最好想的就是先排序，再找中位数，时间复杂度是O(nlogn).书上提出了一种时间复杂度为n的方法。按照快拍的思路，找到分界点，如果分界点比n/2小，那说明中位数在右边，大就在左边，正好就结束了。（找到这个数最好判断出现的次数大于一半在输出，懒得写了）
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 #define INITLENGTH 40 #define INCREMENT 20 int Partition(int numbers[],int length,int start,int end) { int key = numbers[start]; while(start<end) { while(start<end && numbers[end]>=key) end--; numbers[start] = numbers[end]; while(start<end && numbers[start]<=key) start++; numbers[end] = numbers[start]; } numbers[start] = key; return start; } int MoreThanHalfNum(int* numbers,int length) { int middle = length>>2-1; int end = length-1; int start = 0; int index; if(numbers == NULL || length<0)return false; index = Partition(numbers,length,start,end); while(index!=middle) { if(index>middle) { end = index - 1; index = Partition(numbers,length,start,end); } else { start = index + 1; index = Partition(numbers,length,start,end); } } return numbers[index]; } void main() { int a[] = {1,2,3,2,2,2,5,4,2}; printf("%d",MoreThanHalfNum(a,sizeof(a)/sizeof(int))); }
思路二：
根据这个数组的特点，这个数字出现的次数别其他所有数字出现的和还多。所以可以遍历数组，保存数字和次数，如果下一个与该数字相同，次数加一；不同，次数减一；当次数为0的时候，换数。所以最后剩下的肯定是要找的数。
你可以想象这个数是你的兵，不相同的是你的敌人，他们一对一肉搏，你的人多，最后肯定会剩下来的，当然对面还可能自相残杀，所以最后剩下的肯定是你的人。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int MoreThanHalfNum(int* numbers,int length) { int result = 0; int count = 0; int i; if(numbers == NULL || length<0)return false; result = numbers[0]; for(i=0;i<length;i++) { if(count == 0) { result = numbers[i]; } if(numbers[i]==result) count++; else count--; } return result; } void main() { int a[] = {1,2,3,2,2,2,5,4,2}; printf("%d",MoreThanHalfNum(a,sizeof(a)/sizeof(int))); }
40 最小的k个数
题目：输入n个数，找出其中最小的k个数。
思路：最好想的是排序，排序最快的是快排，时间复杂度是Nlog(N),书上提出两种新思路。
还是利用快排，但是不用把所有都排好。快排是把比一个数大的所有数放右，小的所有数放左边，如果这个数正好等于k，那左边的k个数就是排好了。比k大，就继续快排左边的，比k小，就排右边的。
（第二种太麻烦了 就不写了）
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int Partition(int* numbers,int start,int end) { int startIndex = start; int key = numbers[start]; while(start<end) { while(start<end && numbers[end]>=key)end--; numbers[start] = numbers[end]; while(start<end && numbers[start]<=key)start++; numbers[end] = numbers[start]; } numbers[start] = key; return start; } void GetLeastNumbers(int* input,int n,int* output,int k) { int start; int end; int index; int i; if(input == NULL||output == NULL||k>n||n<=0||k<=0) return; start = 0; end = n-1; index = Partition(input,start,end); while(index!=k-1) { if(index>k-1) { end = index-1; index = Partition(input,start,end); } else { start = index+1; index = Partition(input,start,end); } } for(i=0;i<k;i++) { output[i] = input[i]; printf("%d",input[i]); } } void main() { int a[] = {8,7,6,5,4,3,2,1}; int b[8]; GetLeastNumbers(a,sizeof(a)/sizeof(int),b,sizeof(b)/sizeof(int)); }
41 数组流中的中位数
题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路：最直观的就是排序，排序的时间复杂度是O(nlogN)，寻找复杂度是O(1).插入时时间复杂度为O(N)
优化一：其实不用完全排列好，只要保证左边比他小，右边比他大就好了。使用前面的Partition寻找中位数（采用快排的思路），可以将时间复杂度降为O(N),插入要排序，所以时间复杂度是O(N).
优化二：使用二叉搜索树，可以把插入新数据的时间复杂度降到O(log(n))，找中位数的复杂度也是O(log(n))。这个时间复杂度是平均时间复杂度，当二叉树严重失衡时，两个时间复杂度都可能降为O(N)
优化三：二叉树不好就用AVL（平衡二叉树），保证树的左右子树高度差不高于1，有了这个改动，可以花O(log(n))时间往书中添加一个新节点，这样寻找中位数的时间为O(1).(AVL树不好写，不推荐)
优化四：既然是中位数，可以把数据平均分成两部分，保证左边部分都比右边部分小。然后左边能随时得到最大值，右边能随时得到最小值，这可以用堆的数据结构。注意一些细节：1.如何实现平均分配：可以第奇数个往左分，第偶数个往右分。2.如何保证新插入的数据不打乱左边部分比右边部分小：插完之后将左右堆顶的数据比较，如果反了就交换一下。小顶堆没问题，大顶堆重构一下。
42 连续子数组的最大和
题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(N)
思路：最好想的思路是枚举中所有种可能，排列组合，n×(n-1)/2,不满足。
优化一：从第一个数开始，每增加一个数就有可能引起当前最大和的变化，变化的情况主要有这么几种：1.新加入的值比之前的最大值大 2.新加入的值比加上之前最大的累加值，比最大值大。所以我们需要记录两个数，一个是当前的最大值，一个是当前的累加最大值（因为是连续的，所以只有累加值才能加上新的值）有点小细节，如果数组中的数都是负数，如果按普通逻辑把初始值设为0，那么最后算出的最大值就是0了。所以有两种方法，一种是初始化为最小的负数，而是初始化为第一个数。
其实上面的做法就是动态规划的思想，使用f(i)表示以第i个数字结尾的子数组的最大和，我们要求的是max(f(i))，可以用以下递归公式求f(i):
在这里插入图片描述
这个公式得到的f(i)就是curSum ，然后greatSum就是max(f(i))，两种思路异曲同工。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int FindGreatSum(int* data,int length) { int curSum; int greatSum; int i; if(data==NULL || length<=0)return; curSum = data[0]; greatSum = data[0]; for(i=1;i<length;i++) { if(curSum<=0) curSum = data[i]; else curSum+=data[i]; greatSum = (greatSum>curSum?greatSum:curSum); } return greatSum; } void main() { int data[] = {1,-2,3,10,-4,7,2,-5}; //int data[] = {-1,-2,-3,-5,-4}; printf("%d",FindGreatSum(data,sizeof(data)/sizeof(int))); }
43 1-n整数中1出现的次数
题目：输入一个整数n,求1-n这n个整数的十进制表示中1出现的次数。例如，输入12，1-12这些整数中包含1的数字有1、10、11和12，1一共出现了5次
思路：
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int NumberOf1(unsigned int n) { int count=0; while(n) { if((n%10)==1) count++; n = n/10; } return count; } int NumberOf1Between1AndN(unsigned int n) { int i = 0; int count = 0; for(i=1;i<=n;i++) { count+=NumberOf1(i); } return count; } int main() { int count = NumberOf1Between1AndN(100); printf("%d",c) }
7 礼物的最大价值
题目：在一个m×n的棋盘的每一格斗放有一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物
思路：动态规划类问题，每一个格子的礼物，只跟他左边和上边的数值有关，所以从左上角开始遍历，新建一个二维数组用来存储当前位置的最大礼物。最大礼物是左边和上边的最大值加上该位置的值。
#include <stdio.h> #include <stdlib.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int FindGreatSum(int* values,int rows,int cols) { int i,j; int left,up; int max; int **maxValues = (int**)malloc(sizeof(int*)*rows); if(values == NULL||rows<0||cols<0)return; for(i=0;i<rows;i++) maxValues[i] = (int*)malloc(sizeof(int)*cols); for(i=0;i<rows;i++) { for(j=0;j<cols;j++) { left = 0; up = 0; if(i>0) up = maxValues[i-1][j]; if(j>0) left = maxValues[i][j-1]; if(up>left) maxValues[i][j]=up + values[i*cols+j]; else maxValues[i][j]=left + values[i*cols+j]; } } max = maxValues[rows-1][cols-1]; for(i=0;i<rows;i++) free(maxValues[i]); free(maxValues); return max; } void main() { int max; int values[] = {1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5}; max = FindGreatSum(values,4,4); printf("%d",max); }
48 最长不含重复字符的子字符串
题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长字符串的长度。假设字符串中只包含a-z的字符。例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是“acfr”，长度为4
思路：
暴力法：一个长度为n的字符串中有n×(n-1)/2个子字符串，把所有字符串遍历一遍，然后先判断有无重复字符，如果没有再更新当前最长长度。
优化：
动态规划:找到字符串长度从1到n的包含最后一个字符的最长长度，一定要注意不是最长长度，是包含最后一个字符的最长长度。因为最长长度一定是某种情况中包含最后一个字符的长度，而且只有包含最后一个字符，才能建立起新加一个字符后的最长长度。
所以这道题就变成了这样的步骤：
1.判断前面是否有该字符
2.如果有该字符，判断该字符与当前字符之间的距离d与当前长度之间的关系，也就是判断当前长度有没有包含这个重复字符。比如abcdaeb，当查到第二个b时，当前最长长度为2.向前查找两个数，没找到b，所以可以把b加进来
2.1 另一种思路就是从当前位置向前查到当前长度个数，看看有没有，比如abcdaeb，数组中第二个存的位置为1，当前位置为6，
2.2 还有一种优化，建立一个数组，存放最近的一个字符出现的位置，每次去查位置就好了。比如abcdaeb，数组中第二个存的位置为1，当前位置为6，差为5，但是长度只为2，所以没影响。
3.如果发现该字符在之前的当前长度包含中，那么要重新更新当前长度，长度为该字符两个位置的差值。比如abcdaeb，找到第二个a时，当前长度更新为4-0为4，也就是bcda
4.过程中不断更新最大长度，让他成为所有当前长度中的最大值。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int LontestSubstring(char* str) { int i; int curLength = 0; int maxLength = 0; int position[26]; int preIndex; if(str==NULL)return false; for(i=0;i<26;i++)position[i]=-1; for(i=0;i<strlen(str);i++) { preIndex = position[str[i]-'a']; if(preIndex<0 || i-preIndex>curLength) curLength++; else curLength = i-preIndex; position[str[i]-'a'] = i; if(curLength>maxLength)maxLength = curLength; } return maxLength; } void main() { char str[] = "abcacfrar"; printf("%d",LontestSubstring(str)); }
49 丑数
题目：我们把只保函因子2 3 5 的数成为丑数。求按从小到的的顺序的第1500个丑数。例如，6 8 都是丑数，但14不是，因为它包含因子7.习惯上我们把1当作第一个丑数
思路：把i从1开始增长，每个数都判断是不是丑数，也就是不断的除以2 3 5 ，看最后是不是1.是丑数就把Index加1，等于第n个丑数时结束。这首思路很直观，但是缺点就是当n太大的时候，计算时间非常长，当n=1500时程序要运行30S
优化：之所以费时间是因为把所有数都要判断是不是丑数，可以换一种思路，所有丑数都是前面的某个丑数×2或者3或者5得到的，所以我们可以拿一个数组存储所有丑数。但是怎么保证这个数组时有序的呢。可以存储每一个×2大于当前最大的丑数，×3大于当前最大的丑数，×5大于当前最大丑数的值，然后取这三个数分别×2 3 5 中最小的那个。比如说现在丑数是1，×2 3 5 比当前丑数大的都是1，取三个里面最小的那个是2，第二个丑数为2；现在1×2不比2大了，所以把乘2的这个数更新为2，然后比较3（1×3），4（2×2），5（1×5）这三个谁最小，3最小，第三个丑数为3.再把乘三的这个数更新为2，这样一直往下找就能按顺序找出所有的丑数了，以空间换时间。
两种方法得到的结果一致在这里插入图片描述
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 bool IsUgly(int number) { while(number%2==0)number/=2; while(number%3==0)number/=3; while(number%5==0)number/=5; return (number==1)?true:false; } int GetUglyNumber1(int index) { int number = 0; int uglyFound = 0; if(index<1)return 0; while(uglyFound<index) { number++; if(IsUgly(number)) uglyFound++; } return number; } int GetUglyNumber2(int index) { int *pUglyNumbers = (int*)malloc(sizeof(int)*index); int uglyIndex = 1; int* pMultiply2 = pUglyNumbers; int* pMultiply3 = pUglyNumbers; int* pMultiply5 = pUglyNumbers; int ugly; if(index<1)return 0; pUglyNumbers[0] = 1; while(uglyIndex<index) { pUglyNumbers[uglyIndex] = *pMultiply2*2; if(*pMultiply3*3<pUglyNumbers[uglyIndex])pUglyNumbers[uglyIndex] = *pMultiply3*3; if(*pMultiply5*5<pUglyNumbers[uglyIndex])pUglyNumbers[uglyIndex] = *pMultiply5*5; while(*pMultiply2*2<=pUglyNumbers[uglyIndex]) pMultiply2++; while(*pMultiply3*3<=pUglyNumbers[uglyIndex]) pMultiply3++; while(*pMultiply5*5<=pUglyNumbers[uglyIndex]) pMultiply5++; uglyIndex++; } ugly = pUglyNumbers[index-1]; free(pUglyNumbers); return ugly; } void main() { printf("%d\n",GetUglyNumber1(1500)); printf("%d",GetUglyNumber2(1500)); }
50-1 第一个只出现一次的字符
题目：在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出b思路：从头到尾遍历字符串，然后锁定该字符，再从头到尾遍历，如果在除了该位置的所有位置都没出现这个字符，就把他输出。时间复杂度是O(N2)优化：建立哈希表，由于char只有256个字符，所以可以建立256大小的简单哈希表。第一次遍历时，用哈希表存储每个字符出现的次数，第二次遍历时区查表，要是次数为1，就输出。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 char FindNotRepeatingChar2(char* str) { int length = strlen(str); int i; int hash[256]; if(str == NULL)return '\0'; for(i=0;i<256;i++)hash[i]=0; for(i=0;i<length;i++) { hash[str[i]]++; } for(i=0;i<length;i++) { if(hash[str[i]]==1)return str[i]; } return '\0'; } char FindNotRepeatingChar1(char* str) { int length = strlen(str); int i; int j; char temp; if(str == NULL)return '\0'; for(i=0;i<length;i++) { temp = str[i]; for(j=0;j<length;j++) { if(str[j]==temp && j!=i)break; } if(j==length)return temp; } return '\0'; } void main() { char* str = "abaccdeff"; printf("%c\n",FindNotRepeatingChar1(str)); printf("%c\n",FindNotRepeatingChar2(str)); }
51 数组中的逆序对（暂略）
题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如，在数组{7，5，6，4}中，一共存在5个逆序对，分别是(7，6)(7，5)(7，4)(6，4)和(5，4)
思路：没想明白
52 两个链表的第一个公共节点
题目：输入两个链表，找出它们的第一个公共节点。
思路：暴力法，遍历A链表，从第一个节点开始，每个节点都去B链表中遍历寻找有没有相同的节点，时间复杂度为O(N2)
优化一：注意，这里的节点相同，不只是节点中的数值相同，节点的next指向的地址也要相同，这也就是说只会是下面的Y型，不会是X型。所以从尾开始找，第一个不一样的下一个节点就是第一个公共节点了。但是链表只有从前向后的指针，没有从后向前的，所以可以加两个栈，先从头到后遍历一遍，把两个链表每个节点分别放在栈里面。然后不断出栈，比较。
优化二：如果不加入栈也可以，因为最后几个节点是公共的，所以不同的都在前面的节点里面。先比较两个链表的长度，然后从长的链表中先走长度差步，之后再和优化一一样，不断比较就好了。就向下图里面的，上面的离岸边比下面的长1个节点，就让他先走一步，走到2，然后开始比较。
在这里插入图片描述
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 typedef struct ListNode { int data; struct ListNode* next; }listNode; void PrintList(listNode* head) { listNode* p = head; while(p!=NULL) { printf("%d ",p->data); p = p->next; } } listNode* CreateListNode(int data) { listNode* newListNode = (listNode*)malloc(sizeof(listNode)); if(!newListNode)return false; newListNode->data = data; newListNode->next = NULL; return newListNode; } void ConnectListNodes(listNode* node1,listNode* node2) { node1->next = node2; } listNode* FindFirstCommonNode(listNode* pHead1,listNode* pHead2) { listNode* p; listNode* shortList = pHead1; listNode* longList = pHead2; int length1 = 0; int length2 = 0; int lengthDif = 0; p = pHead1; while(p!=NULL) { length1++; p = p->next; } p = pHead2; while(p!=NULL) { length2++; p = p->next; } lengthDif = length2 - length1; if(lengthDif<0) { shortList = pHead2; longList = pHead1; lengthDif = -lengthDif; } while(lengthDif!=0) { longList = longList->next; lengthDif--; } while(shortList!=NULL && longList!=NULL) { if(shortList == longList)break; shortList = shortList->next; longList = longList->next; } return shortList; } void main() { int k=1; listNode* pNode1 = CreateListNode(1); listNode* pNode2 = CreateListNode(2); listNode* pNode3 = CreateListNode(3); listNode* pNode4 = CreateListNode(4); listNode* pNode5 = CreateListNode(5); listNode* pNode6 = CreateListNode(6); listNode* pNode7 = CreateListNode(7); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode6); ConnectListNodes(pNode6, pNode7); ConnectListNodes(pNode4, pNode5); ConnectListNodes(pNode5, pNode6); printf("%d",FindFirstCommonNode(pNode1,pNode4)->data); }
53-1 数字在排序数组中出现的次数
题目：数字在排序数组中出现的次数。例如，输入排序数组｛1，2，3，3，3，3，4，5｝和数字3，由于3在这个数组中出现了4次，因此输出4思路：暴力法，从头到尾查，时间复杂度是O(N).也可以使用二分法找到3，然后向前向后查，可以省点时间，但还是O(N)优化：使用二分法分别查第一个3和最后一个3，然后两个值做差就好了。只不过这个二分法要做点特殊处理，在找头的时候，还要保证找到是3的那个数的前一个不是3，否则在左半区域继续找；在找尾的时候，要保证找到是3的那个数的后一个不是3，否则在后半区域继续找。两个二分查找的时间复杂度都是O(logN),所以总的时间复杂度也是O(log(N))
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int GetFirstK(int* data,int length,int k,int start,int end) { int middle = (start+end)>>1; if(start>end)return NULL; if(data[middle]==k) { if(middle==0||(middle>0 && data[middle-1]!=k)) return middle; else return GetFirstK(data,length,k,start,middle-1); } else if(data[middle]>k) return GetFirstK(data,length,k,start,middle-1); else return GetFirstK(data,length,k,middle+1,end); } int GetLastK(int* data,int length,int k,int start,int end) { int middle = (start+end)>>1; if(start>end)return NULL; if(data[middle]==k) { if(middle==length-1||(middle<length-1 && data[middle+1]!=k)) return middle; else return GetLastK(data,length,k,middle+1,end); } else if(data[middle]>k) return GetLastK(data,length,k,start,middle-1); else return GetLastK(data,length,k,middle+1,end); } int GetNumberOfK(int* data,int length,int k) { int first,end; if(data==NULL || length<0)return NULL; first = GetFirstK(data,length,k,0,length-1); end = GetLastK(data,length,k,0,length-1); return end-first+1; } void main() { int data[] = {1,2,3,3,3,3,4,5}; int number; number = GetNumberOfK(data,sizeof(data)/sizeof(int),3); printf("%d",number); }
53-2 0-n-1中缺失的数字
题目：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0-n-1之内，在范围0-n-1内的n个数字有且只有一个数字不在该数组内，请找出这个数字
思路：这个数组的特点就是如果没有缺失数字，应该下标和数组里面的内容相等，这时候缺的是最后一个数字。否则会从某一个位置开始，下标比该数组中的数小。所以这道题就变成了，寻找第一个下标和数不对应的数。使用二分法，很好实现。
注意：特殊情况就是缺失的是最后一个数的时候，这种情况下应该是right不变，left不断向right靠，最后比right大的时候就结束循环了，这时候返回最大的那个数就好了，不然就是错了。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false 0 #define none 2 int GetMissingNumber(int* numbers,int length) { int left = 0; int right = length-1; int middle = left+right>>1; if(numbers==NULL || length<=0)return NULL; while(left<=right) { if(numbers[middle]==middle) left = middle+1; else { if(middle==0 || numbers[middle-1]==middle-1) return middle; else right = middle-1; } middle = left+right>>1; } if(left==length)return length; return false; } void main() { int data[] = { 0 }; int number; number = GetMissingNumber(data,sizeof(data)/sizeof(int)); printf("%d",number); }
53-3 数组中数值和下标相等的元素
题目：假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组｛-3，-1，1，3，5｝中，数字3和他的下标相等。思路：还是二分法，不谈了
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 int GetNumberSameAsIndex(int* numbers,int length) { int left = 0; int right = length-1; int middle = left+right>>1; if(numbers==NULL || length<=0)return false; while(left<=right) { if(numbers[middle]==middle)return numbers[middle]; else if(numbers[middle]<middle) left = middle+1; else right = middle-1; middle = left+right>>1; } return false; } void main() { int data[] = { -3, -1, 1, 3, 5 }; int number; number = GetNumberSameAsIndex(data,sizeof(data)/sizeof(int)); printf("%d",number); }
54 二叉搜索树的第k大节点
题目：给定一棵二叉搜索树，请找出其中第k大的节点。例如，在图6.1中的二叉搜索树里，按节点数值大小顺序，第三大节点的值是4
在这里插入图片描述思路：这就是链表中序遍历的演变，但是只要一跟递归联系上就有点麻烦。先把中序遍历递归的框架写出来，然后在递归左子树和递归右子树之间加东西。因为是第k个节点，所以需要传入k，所以要再写个传入指针的函数。然后初始化一个指针，当这个指针指向NULL的时候说明还没找到，这时候去判断k，如果k等于1，就返回当前节点，如果不等于1继续返回NULL，然后把k-1.
注意：在右子树的递归条件上要加上限制，因为如果之前k已经满足条件了，那就会一直返回，就错了。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } BinaryTreeNode* KthNodeCore(BinaryTreeNode* pRoot,unsigned int* k) { BinaryTreeNode* target = NULL; if(pRoot->left!=NULL)target = KthNodeCore(pRoot->left,k); if(target==NULL) { if(*k==1)target = pRoot; else (*k)--; } if(pRoot->right!=NULL && target == NULL)target = KthNodeCore(pRoot->right,k); return target; } BinaryTreeNode* KthNode(BinaryTreeNode* pRoot,unsigned int k) { if(pRoot == NULL || k==0)return NULL; return KthNodeCore(pRoot,&k); } void main() { BinaryTreeNode* node; BinaryTreeNode* node5 = CreateBinaryTreeNode(5); BinaryTreeNode* node3 = CreateBinaryTreeNode(3); BinaryTreeNode* node7 = CreateBinaryTreeNode(7); BinaryTreeNode* node2 = CreateBinaryTreeNode(2); BinaryTreeNode* node4 = CreateBinaryTreeNode(4); BinaryTreeNode* node6 = CreateBinaryTreeNode(6); BinaryTreeNode* node8 = CreateBinaryTreeNode(8); ConnectTreeNodes(node5,node3,node7); ConnectTreeNodes(node3,node2,node4); ConnectTreeNodes(node7,node6,node8); node = KthNode(node5,3); printf("%d",node->value); }
55-1 二叉树的深度
题目：输入一课二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根节点和叶节点）形成树的一条路径，最长路径的长度为树的深度。思路：深度就是左右子树中比较深的深度加一，递归就行了。从叶子节点开始往回递归，叶子节点的深度为1.
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } BinaryTreeNode* KthNodeCore(BinaryTreeNode* pRoot,unsigned int* k) { BinaryTreeNode* temp = NULL; if(pRoot->left!=NULL)temp = KthNodeCore(pRoot->left,k); if(temp==NULL) { if(*k!=1) (*k)--; else temp = pRoot; } if(pRoot->right!=NULL && temp==NULL)temp = KthNodeCore(pRoot->right,k); return temp; } BinaryTreeNode* KthNode(BinaryTreeNode* pRoot,unsigned int k) { if(pRoot == NULL || k==0)return NULL; return KthNodeCore(pRoot,&k); } int TreeDepth(BinaryTreeNode* pRoot) { int nLeft =0; int nRight = 0; if(pRoot==NULL)return 0; nLeft = TreeDepth(pRoot->left); nRight = TreeDepth(pRoot->right); if(nLeft>nRight)return nLeft+1; else return nRight+1; } void main() { BinaryTreeNode* node; BinaryTreeNode* node5 = CreateBinaryTreeNode(5); BinaryTreeNode* node3 = CreateBinaryTreeNode(3); BinaryTreeNode* node7 = CreateBinaryTreeNode(7); BinaryTreeNode* node2 = CreateBinaryTreeNode(2); BinaryTreeNode* node4 = CreateBinaryTreeNode(4); BinaryTreeNode* node6 = CreateBinaryTreeNode(6); BinaryTreeNode* node8 = CreateBinaryTreeNode(8); ConnectTreeNodes(node5,node3,node7); ConnectTreeNodes(node3,node2,node4); ConnectTreeNodes(node7,node6,node8); printf("%d",TreeDepth(node5)); }
55-2 平衡二叉树
题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1.那么他就是一颗平衡二叉树。例如，图中的二叉树就是一颗平衡二叉树。
在这里插入图片描述
思路：可以根据上面求深度的程序，从根节点开始，比较左右子树深度，如果相差不大于一就证明这个节点是平衡的，继续判断他的左右子树是不是平衡的，一直递归下去，到叶子节点结束。这种思路的缺点是重复计算深度。因为是从根节点开始的。
优化：对于上述情况，我们可以把深度作为函数成员传递，当指针指向NULL时把depth赋值0，之后先判断左子树和右子树是不是都是平衡树，判断成功后再判断左子树和右子树的深度是不是相差一，又判断成功后再将当前节点的深度更改为左右子树更大的那个深度加一，然后返回true,否则返回false
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 typedef struct BinaryTreeNode { int value; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BinaryTreeNode; BinaryTreeNode* CreateBinaryTreeNode(double value) { BinaryTreeNode* pNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); pNode->value = value; pNode->left = NULL; pNode->right = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* left,BinaryTreeNode* right) { if(parent!=NULL) { parent->left = left; parent->right = right; } } void DestroyTree(BinaryTreeNode** pRoot) { BinaryTreeNode* left = NULL; BinaryTreeNode* right = NULL; if(*pRoot!=NULL) { left = (*pRoot)->left; right = (*pRoot)->right; free(*pRoot); pRoot = NULL; DestroyTree(&left); DestroyTree(&right); } } int TreeDepth(BinaryTreeNode* pRoot) { int left,right; if(pRoot==NULL)return 0; left = TreeDepth(pRoot->left); right = TreeDepth(pRoot->right); return left>right?left+1:right+1; } bool IsBalancedCore(BinaryTreeNode* pRoot,int* depth) { int left,right; int diff; if(pRoot == NULL) { *depth = 0; return true; } if(IsBalancedCore(pRoot->left,&left) && IsBalancedCore(pRoot->right,&right)) { diff = left-right; if(diff<=1 && diff>=-1) { *depth = 1+(left>right?left:right); return true; } } return false; } bool IsBalanced(BinaryTreeNode* pRoot) { int depth=0; if(pRoot==NULL)return true; return IsBalancedCore(pRoot,&depth); } bool IsBalanced2(BinaryTreeNode* pRoot) { int left,right; if(pRoot==NULL)return true; left = TreeDepth(pRoot->left); right = TreeDepth(pRoot->right); if(left-right>=-1 && left-right<=1) return IsBalanced2(pRoot->left) && IsBalanced2(pRoot->right); else return false; } void main() { BinaryTreeNode* node; BinaryTreeNode* node1 = CreateBinaryTreeNode(1); BinaryTreeNode* node2 = CreateBinaryTreeNode(2); BinaryTreeNode* node3 = CreateBinaryTreeNode(3); BinaryTreeNode* node4 = CreateBinaryTreeNode(4); BinaryTreeNode* node5 = CreateBinaryTreeNode(5); BinaryTreeNode* node6 = CreateBinaryTreeNode(6); BinaryTreeNode* node7 = CreateBinaryTreeNode(7); BinaryTreeNode* node8 = CreateBinaryTreeNode(8); ConnectTreeNodes(node1,node2,node3); ConnectTreeNodes(node2,node4,node5); ConnectTreeNodes(node3,NULL,node6); ConnectTreeNodes(node5,node7,NULL); ConnectTreeNodes(node7,node8,NULL); printf("%d",IsBalanced(node1)); printf("%d",IsBalanced2(node1)); }
56 数组中只出现一次的两个数字
题目：一个整型数组里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(N),空间复杂度是O(1)
思路：先抛开时间复杂度和空间复杂度的要求，可以从头遍历数组，然后找除了他以外的数组，看有没有一样的，时间复杂度是O(N2).也可以引入一个建在哈希表，遍历一次数组然后再从哈希表中找出次数为1的数字，时间复杂度是O(N),空间复杂度为O(N).但是同时满足时间复杂度和空间复杂度要怎么实现呢？
如果只有一个出现一次的数字，可以通过同一数异或自己的特性，从头到尾异或全部，最后剩下的就是只出现一次的那个数字了。
再回到这道题，有两个出现一次的数字，从头到尾异或完之后是这两个只出现过一次的数字的异或值。至少有一个位是1，我们可以通过这个位，把整个数组分成两部分，确保每部分中各有一个出现一次的数字。然后再用异或的方式就可以得到这两个数字了。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 // 找到num从右边数起第一个是1的位 unsigned int FindFirstBitIs1(int num) { int indexBit = 0; while(((num & 1) == 0)) { num = num >> 1; ++indexBit; } return indexBit; } // 判断数字num的第indexBit位是不是1 bool IsBit1(int num, unsigned int indexBit) { return (num>>indexBit & 1); } void FindNumsAppearOnce(int data[], int length, int* num1, int* num2) { int i,j; int resultExclusiveOR = 0; unsigned int indexOf1; if(data == NULL || length < 2) return; for(i = 0; i < length; ++i) resultExclusiveOR ^= data[i]; indexOf1 = FindFirstBitIs1(resultExclusiveOR); *num1 = *num2 = 0; for(j = 0; j < length; ++j) { if(IsBit1(data[j], indexOf1)) *num1 ^= data[j]; else *num2 ^= data[j]; } } void main() { int data[] = { 2, 4, 3, 6, 3, 2, 5, 5 }; int result1, result2; FindNumsAppearOnce(data, sizeof(data)/sizeof(int), &result1, &result2); printf("%d %d",result1,result2); }
57-1 和为S的数字
题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得他们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。例如输入数组{1，2，4，7，11，15}和15，输出4和11.
思路：最直观的做法，每一个数都与其他数相加，看看是否等于S，双重循环，时间复杂度为O(N2)
优化：由于数组已经是有序的，所以可以设置两个指针分别指向头尾，用他俩的和与S比较，如果比S小，就让前面的指针加加，指向一个大点的数；如果比S大，就让后面那个指针减减，指向一个小点的数。如果到最后两个指针相遇还未找到，那就是找不到了，返回失败。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 bool FindNumbersWithSum(int data[],int length,int sum,int* sum1,int*sum2) { int* big; int* small; if(data==NULL ||length<=0)return false; big = &data[length-1]; small = data; while(small<big) { if(*small+*big<sum) small++; else if(*small+*big>sum) big--; else { *sum1 = *small; *sum2 = *big; return true; } } return false; } void main() { int data[] = {1,2,4,7,11,15}; int sum1 = 0; int sum2 = 0; int sum = 15; FindNumbersWithSum(data, sizeof(data)/sizeof(int), sum,&sum1, &sum2); printf("%d %d",sum1,sum2); }
57-2 和为S的连续正数序列
题目：输入一个整数S，打印出所有和为S的连续正数序列（至少含有两个数）。例如，输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以打印出三个连续序列1-5 4-6 7-8思路：设置两个指针，分别指向1和2，判断他们的和与S的关系。如果小于S，那就让big++,然后和加上新的big；如果大于S，就让small++，和减去原来的small；如果等于S，先打印，之后再big++（small–也可以），更新当前和。因为是连续的，所以当small大于middle之后，姐结束循环（比如15，当small=8就结束）
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 void FindContinuous(int sum) { int small = 1; int big = 2; int currentSum = 3; int middle = (sum+1)/2; int i; while(small<middle) { if(currentSum<sum) { big+=1; currentSum+=big; } else if(currentSum>sum) { currentSum-=small; small+=1; } else { for(i=small;i<=big;i++) printf("%d ",i); printf("\n"); big+=1; currentSum+=big; } } return; } void main() { FindContinuous(100); }
58-1 翻转单词顺序
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串“I am a student.”，则输出“student. a I”
思路：字符串整个倒置的题目很好做，两个指针一个指向头，一个指向尾，然后不断交换，不断向对方靠拢就好了。但是这道题还要求字符的顺序不变，所以还需要以空格为分界点，进行局部交换。
以I am a student为例，第一次整体交换得到tneduts a ma I.然后end指针不断寻找空格，找到后就从start到end再次交换，第一次局部交换后为student a ma I.此时end指向第一个空格，所以交换完再把end++,start=end.
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 void Reverse(char* start,char* end) { char temp; char* record = end; while(start<end) { temp = *start; *start = *end; *end = temp; start++; end--; } } void ReverseSentence(char* str) { char* start; char* end; char temp; if(str == NULL)return; start = str; end = str+strlen(str)-1; Reverse(start,end); start = end = str; while(*end!='\0') { while(*end!=' '&&*end!='\0') end++; Reverse(start,end-1); start = ++end; } return; } void main() { char str[] = "i am a student. "; ReverseSentence(str); printf("%s",str); }
58-2 左旋字符串
题目：字符串的左旋操作是把字符串前面的若干字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串“abcdefg”和数字2，该函数将返回左旋两位得到的结果“cdefgab”
思路：我的第一个想法就是先建立一个临时数组，从头数n个，放进临时数组，剩下的从第n+1个开始每个向前移动n个，之后再把临时数组中的放到后面。比如abcdefg，左旋三个，就是先建立一个数组，把abc存放进去，然后defg依次向前移动三位，之后再把abc放到最后面，defgabc.
优化：书上提出一种不用临时数组的方法，其实仔细看会发现，这个左旋的过程就是先把整体旋转，然后把前n个旋转，再把剩下的再旋转。比如abcdefg，第一次旋转是gfedcba，假如左旋三个，就把前三个旋转defgcba,再把剩下的旋转，defgabc.
两种代码都写了
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 void Reverse(char* start,char* end) { char temp; char* record = end; while(start<end) { temp = *start; *start = *end; *end = temp; start++; end--; } } void LeftRotateString2(char* str,int n) { int length = strlen(str); char* start1; char* end1; char* start2; char* end2; if(str==NULL||length<=0||n<=0||n>length)return; start1 = str; end1 = str+n-1; start2 = str+n; end2 = str+length-1; Reverse(start1,end1); Reverse(start2,end2); Reverse(start1,end2); } void LeftRotateString1(char* str,int n) { char *temp = (char*)malloc(sizeof(char)*n); int i; if(str ==NULL || n<=0)return; for(i=0;i<n;i++) temp[i] = str[i]; for(i=0;i<strlen(str)-n;i++) str[i] = str[i+n]; for(;i<strlen(str);i++) str[i] = temp[i-(strlen(str)-n)]; free(temp); } void main() { char str1[] = "abcdefg"; char str2[] = "abcdefg"; LeftRotateString1(str1,3); LeftRotateString2(str2,3); printf("%s\n%s",str1,str2); }
59-1 滑动窗口的最大值（暂略）
题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组{2，3，4，2，6，2，5，1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4，4，6，6，6，5}
暂时略过
60 n个骰子的点数
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
思路：书上的两个方法都太难懂了，看了点别人的文章，自己做了一遍。这是一道动态规划的题，可以建立一个二维数组dp[][],前面的标号表明现在是有几个骰子，后面的标号表明值为多少，数组中的值为值为该数的情况个数。最开始是dp[1][1]到dp[1][6]都是1，因为一个骰子有六种可能，每种可能都是1.下一步开始dp[2][2]到dp[2][12]因为两个骰子最小是2最大是12。然后出现多少次与dp[1]有关，如果dp[2][n]的n-1到n-6有再dp[1]中的，就把那个值加上。用公式表达就是f(n,k)=f(n−1,k−1)+f(n−1,k−2)+f(n−1,k−3)+f(n−1,k−4)+f(n−1,k−5)+f(n−1,k−6)
不断往后循环就好了。
做动态规划的题一般需要以下几个步骤：
1.表示状态
2.找出状态转移方程
3.边界处理
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 void PrintProbability(int num) { int** dp = (int**)malloc(sizeof(int*)*(num+1)); int i=0; int j=0; int k=0; int sum=0; if(num<1)return; for(i=0;i<=num;i++) dp[i] = (int*)malloc(sizeof(int)*(6*num+1)); for(i=1;i<=num;i++) for(j=0;j<=6*num;j++) dp[i][j]=0; for(i=1;i<=6;i++) dp[1][i] = 1; for(i=2;i<=num;i++) { for(j=1*i;j<=i*6;j++) { sum=0; for(k=1;k<=6;k++) { if(j-k>0) sum+=dp[i-1][j-k]; } dp[i][j]=sum; } } for(i=num;i<=6*num;i++) sum+=dp[num][i]; for(i=num;i<=6*num;i++) { printf("%f ",dp[num][i]/(float)sum); } for(i=0;i<=num;i++)free(dp[i]); free(dp); printf("\n"); } void main() { PrintProbability(1); PrintProbability(2); PrintProbability(3); }
61 扑克牌中的顺子
题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
思路：抛开扑克牌，就是五个1-13的数字，判断是否连续。可以把大小王看成0.先把数字排序，可以采用C语言库中的快排。之后遍历数组，分别统计0的个数，和间距的大小。最后判断0个个数是不是比间距小就行了。当数组中两个数相等的时候可以直接返回失败。
注意：使用快排的时候还需要传汝一个函数指针，用来判定是从小到大排序还是从大到小排序。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 int compare(const void* arg1,const void* arg2) { return *(int*)arg1-*(int*)arg2;//从小到大排序 //return *(int*)arg2-*(int*)arg1;//从大到小排序 } bool IsContinuous(int* numbers,int length) { int i = 0; int numberOf0 = 0; int numberOfUncontinuous = 0; if(numbers==NULL || length<1)return false; qsort(numbers,length,sizeof(int),compare); for(i=0;i<length;i++) { if(numbers[i]==0)numberOf0++; else if(i>0) { if(numbers[i-1]!=0 && numbers[i]==numbers[i-1]) return false; if(numbers[i-1]!=0 && numbers[i]-numbers[i-1]!=1) numberOfUncontinuous+=(numbers[i]-numbers[i-1]-1); } } if(numberOf0<numberOfUncontinuous) return false; else return true; } void main() { int numbers[] = {0,0,3,3,6}; int i; bool status; status = IsContinuous(numbers,sizeof(numbers)/sizeof(int)); printf("%d",status); }
62 圆圈中最后剩下的数字
题目：0，1，…，n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
思路：建立一个环形链表，建立一个指针指向头，每次循环m-1次，删除该指针指向的节点，然后再把链表接起来。最后当链表中只剩一个的时候把该节点的数值返回。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 typedef struct ListNode { int data; struct ListNode* next; }ListNode; void ConnectListNodes(ListNode* node1,ListNode* node2) { node1->next = node2; } ListNode* CreateListNode(int data) { ListNode* newListNode = (ListNode*)malloc(sizeof(ListNode)); if(!newListNode)return NULL; newListNode->data = data; newListNode->next = NULL; return newListNode; } int LastRemaining(unsigned int n,unsigned int m) { int i=0; int data = 0; ListNode* p = NULL; ListNode* preNode = NULL; ListNode** node = (ListNode**)malloc(sizeof(ListNode*)*n); if(n<1 || m<1)return false; for(i=0;i<n;i++) { node[i] = CreateListNode(i); if(i>0) ConnectListNodes(node[i-1],node[i]); } ConnectListNodes(node[n-1],node[0]); p=node[0]; preNode = node[0]; while(p->next != p) { for(i=0;i<m-1;i++) { p = p->next; } while(preNode->next!=p) preNode = preNode->next; if(preNode!=p) { preNode->next = p->next; free(p); p = preNode->next; } } data = p->data; free(p); free(node); return data; } void main() { int data =LastRemaining(4000,997);//1027 printf("%d",data); }
63 股票的最大利润
题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？例如，一只股票某些时间节点的价格为｛9，11，8，5，7，12，16，14｝。如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获的最大利润为11.思路：因为是买卖一次，所以就是选一个最小的，然后在他后面选一个最大的卖出去。可以使用蛮力法，求出每个值与他后面的值的差值，时间复杂度为O(N2)。之后找出所有差值中的最大值优化：可以使用动态规划的想法，从第二个数开始，假设在该数卖出，在前面最小的时候买入。每次更新最小值就可以了。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 int MaxDiff(int* numbers,unsigned int length) { int minCost; int maxDiff; int i; if(numbers==NULL ||length<2)return 0; minCost = numbers[0]; maxDiff = numbers[1]- numbers[0]; for(i=2;i<length;i++) { if(numbers[i-1]<minCost) minCost = numbers[i-1]; if(numbers[i]-minCost>maxDiff) maxDiff = numbers[i]-minCost; } return maxDiff; } void main() { int numbers[] = {9,11,8,5,7,12,16,14}; int maxDiff; maxDiff = MaxDiff(numbers,sizeof(numbers)/sizeof(int)); printf("%d",maxDiff); }
64 求1+2+…+n
题目：求1+2+…+n,要求不能使用乘除法，for,while,if,else,switch,case等关键字以及条件判断语句（A?B:C）思路：不能用乘法不能用循环，那就只能用递归了，递归有一个问题就是最后返回时必须需要判断一下是不是到0了。不能通过判断来停止递归，那可以写两个函数，其中一个函数是正常的递归函数，另外一个是返回的函数，然后用函数指针指向这两个函数。当n等于0时调用返回的函数。通过函数指针数组来决定调用哪个函数，只有0和1两个选择，把N进行两次取反就可以了return n+f!!n;当n>0时两次取反得到1，当n=0时就是0
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 typedef unsigned int (*fun)(unsigned int); unsigned int Solution_Teminator(unsigned int n) { return 0; } unsigned int Solution(unsigned int n) { fun f[2] = {Solution_Teminator,Solution}; return n+f[!!n](n-1); } void main() { int data = Solution(5); printf("%d",data); }
65 不用加减乘除做加法
题目：写一个函数，求两个整数之和，要求在函数体内不得使用加减乘除四则运算符号
思路：加法的过程主要分两步，第一步是不进位的把两个数按位相加，第二步是把进位加上去。在二进制里面，按位相加其实就是异或，都是0都是1最后都是0.进位的数其实就是两个数做与运算然后左移一位，只有都是1的时候才会是1.然后把这两个数在做同样的运算，知道没有进位的数。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 int Add(int num1,int num2) { int sum; int carry; while(num2) { sum = num1^num2; carry = (num1 & num2)<<1; num1 = sum; num2 = carry; } return num1; } void main() { int data = Add(5,6); printf("%d",data); }
66 构建乘积数组（暂过）
题目：给定一个数组A[0,1,…,n-1]，请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1].不能使用乘除法。
67 把字符串转换成整数
题目:写一个函数，实现把字符串转换成整数这个功能。
思路：不考虑任何边界条件，那就不断乘10加本身就好了
#include <stdio.h> #include <stdlib.h> #include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 int StringToInt(char* str) { int result = 0; if(str==NULL)return false; while(*str!='\0') { result = *str++ -'0'+result*10; //str++; } return result; } void main() { char* str = "123"; int a = StringToInt(str); printf("%d",a); }
优化：实际上在输入字符串的过程中，会有很多非法输入，要对这些非法输入进行很好的判断。并且当错误输入时用一个标志位来标志一下。
1.输入NULL或者‘\0’
2.输入符号±
3.输入字符比0x7fff ffff还大或者比0x80000000还小
4.输入不在‘0’到‘9’范围内的数
#include <string.h> #define bool unsigned int #define true 1 #define false -1 #define none 2 enum Status{kValid=0,kInvalid}; int states = kInvalid; long long StrToIntCore(char* digit,int minus) { long long num = 0; int flag = minus?-1:1; while(*digit!='\0') { if(*digit>='0'&&*digit<='9') { num = num*10 + flag*(*digit-'0'); if((!minus && num>0x7fffffff) || (minus && num<(signed int)0x80000000)) { num = 0; break; } } else { num = 0; break; } digit++; } if(*digit == '\0') states = kValid; return num; } int StrToInt(char* str) { long long num = 0; int minus = 0; if(str == NULL || *str == '\0')return 0; if(*str == '+')str++; else if(*str == '-') { str++; minus = 1; } num = StrToIntCore(str,minus); return (int)num; } void main() { char str[] = "-123"; //int data = atoi("132"); int data = StrToInt(str); printf("%d",data); }
