前言：继续前面的分享...
面试题31：
代码如下：
#include<iostream> #include<limits.h> using namespace std; bool g_InvalidInput = false; int FindGreatestSumOfSubArray(int *data,int len) { if(data==NULL || len<=0) { g_InvalidInput = true; return 0; } int curnum = 0; //整型最小值 //int greatestnum = 0x80000000; int greatestnum = INT_MIN; for(int i=0;i<len;++i) { if(curnum <= 0) curnum = data[i]; else curnum += data[i]; if(curnum > greatestnum) greatestnum = curnum; } return greatestnum; } int main() { int data[]={1,-2,3,10,-4,7,2,-5}; cout << "max: " << FindGreatestSumOfSubArray(data,8) << endl; return 0; }
面试题37:
代码如下：
/************************************************************************* > File Name: 37.cpp > Author: ma6174 > Mail: ma6174@163.com > Created Time: Tue 14 Aug 2018 04:41:52 PM CST ************************************************************************/ #include<iostream> #include<algorithm> #include<iterator> #include<string> #include<list> #include<stdio.h> using namespace std; struct ListNode { int data; struct ListNode *next; } ; typedef struct ListNode linknode_t; typedef struct ListNode* linklist_t; linknode_t *CreateLink() // 创建空的链表 返回值 链表的首地址 { linknode_t *H; H = (linklist_t)malloc(sizeof(linknode_t)); H->next = NULL; return H; } void InitLink(linknode_t *H,int n) // 初始化一个空的链表 { linknode_t *r, *p; int i; r = H; // r 指向 队尾位置 for(i = 0; i < n; i++) { p = (linknode_t *)malloc(sizeof(linknode_t)); p->data = i+1; p->next = NULL; // 没有下一个节点 r->next = p; // 将p 放在 r 的后面 r = p; // r 指向新的队尾 } } void ShowLink(linknode_t* H) // 从队首->队尾 打印所有节点 { struct ListNode *p; p = H->next; while(p != NULL){ printf("%d --> ", p->data); p = p->next; } printf("\n"); } unsigned int GetListLength(ListNode *pHead) { unsigned int len = 0; ListNode *pNode = pHead; //pNode = pNode->next; while(pNode->next != NULL) { ++len; pNode = pNode->next; } return len; } ListNode *FindFirstCommonNode(ListNode *pHead1,ListNode *pHead2) { //得到链表长度 unsigned int len1 = GetListLength(pHead1); cout << "len1: " << len1 << endl; unsigned int len2 = GetListLength(pHead2); cout << "len2: " << len2 << endl; int nLengthDif = len1 - len2; ListNode *pListHeadLong = pHead1; ListNode *pListHeadShort = pHead2; if(len2 > len1) { pListHeadLong = pHead1; pListHeadShort = pHead2; nLengthDif = len2 - len1; } //现在长链表走几步,再同时在两个链表上同时遍历 for(int i=0;i<nLengthDif;++i) pListHeadLong = pListHeadLong->next; while((pListHeadLong!=NULL)&&(pListHeadShort!=NULL)&&(pListHeadLong!=pListHeadShort)) { pListHeadLong = pListHeadLong->next; pListHeadShort = pListHeadShort->next; } //得到第一个公共节点 ListNode *CommonNode = pListHeadLong; //cout << "data: " << CommonNode->data << endl; return CommonNode; } int main() { linknode_t *H = CreateLink(); InitLink(H,5); ShowLink(H); linknode_t *H1 = CreateLink(); InitLink(H1,3); ShowLink(H1); ListNode *node = FindFirstCommonNode(H,H1); if(node != NULL) cout << "data: " << node->data << endl; else cout << "no CommonNode!" << endl; return 0; }
作者：
柳德维
-------------------------------------------
个性签名：独学而无友，则孤陋而寡闻。做一个灵魂有趣的人！
如果觉得这篇文章对你有小小的帮助的话，记得在右下角点个“推荐”哦，博主在此感谢！
万水千山总是情，打赏一分行不行，所以如果你心情还比较高兴，也是可以扫码打赏博主，哈哈哈(っ•̀ω•́)っ⁾⁾！
