劍指offer例題分享--7

　　前言：繼續前面的分享...

　　面試題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: [email protected] 
    > 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;
}      

作者：

柳德維

出處：

https://www.cnblogs.com/liudw-0215/

-------------------------------------------

個性簽名：獨學而無友，則孤陋而寡聞。做一個靈魂有趣的人！

如果覺得這篇文章對你有小小的幫助的話，記得在右下角點個“推薦”哦，部落客在此感謝！

萬水千山總是情，打賞一分行不行，是以如果你心情還比較高興，也是可以掃碼打賞部落客，哈哈哈(っ•̀ω•́)っ⁾⁾！