代码片段10-12-白红宇

代码片段10-12

阅读量：6381 次

发布时间：2019-06-23

本文共 11631 字，大约阅读时间需要 38 分钟。

1. 并查集

/*-1  -1  -1   -1  -1  -1  -1  -1{1,  2} {2,  3} {4,  5} {1,  2}*/#include
    
     using namespace std;class UnionSet{public:    UnionSet(int n) :_size(n + 1)    {        _a = new int[n + 1];        memset(_a, -1, sizeof(int)*(n + 1));    }    void merge(int x1, int x2)    {        int root1 = _getRoot(x1);        int root2 = _getRoot(x2);        if (root1 != root2)        {            _a[root1] += _a[root2];            _a[root2] = root1;        }    }    int getSize()    {        return _getSize();    }protected:    int _getSize()    {        int count=0;        for (int i = 0; i < _size; i++)        {            if (_a[i] < 0)                count++;        }        return count-1;    }    int _getRoot(int x)    {        int root = x;        while (_a[root] >= 0)            root = _a[root];        return root;    }private:    int *_a;    size_t _size;};int main(){    const int cols = 2;    const int rows = 6;    UnionSet s(5);    int arr[rows][cols] = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 1, 3 }, { 5, 4 }, { 2, 5 } };    for (int i = 0; i < rows; i++)    {        s.merge(arr[i][0], arr[i][1]);    }    cout << s.getSize() << endl;    system("pause");}

2. 打印大数1-n

#include
    
     using namespace std;void PrintNumber(char *arr){    bool flag = true;    int len = strlen(arr);    for (int i = 0; i < len; i++)    {        if (flag&&arr[i] != '0')            flag = false;        if (!flag)            cout << arr[i];    }}void PrintNum(char *arr, int index, int len){    if (index == len - 1)    {        PrintNumber(arr);        return;    }    for(int i = 0; i < 10; i++)    {        arr[index+1] = i + '0';        PrintNum(arr, index + 1, len);    }}void Print(int n){    char *arr = new char[n + 1];        memset(arr, 0, sizeof(char)*(n + 1));    arr[n] = '\0';    for (int i = 0; i < 10; i++)    {        arr[0] = i + '0';        PrintNum(arr, 0, n);    }    delete[]arr;}int main(){    int n;    while (cin >> n)    {        Print(n);        cout << endl;    }    system("pause");}

3. 奇数在前偶数在后

#include
    
     using namespace std;bool func(int *arr, int key){    if (arr[key] & 0x1)        return true;    return false;}void ReOrder(int *arr, int len,bool (*func)(int *arr,int key)){    int begin = 0;    int end = len - 1;    while (begin < end)    {        while (begin < end&&func(arr,begin))            ++begin;        while (begin < end&&!func(arr, end))            --end;        swap(arr[begin], arr[end]);    }}int main(){    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };    int len = sizeof(arr) / sizeof(arr[0]);    ReOrder(arr, len,func);    for (int i = 0; i < len; i++)        cout << arr[i] << " ";    cout << endl;    system("pause");    return 0;}

4. 正则表达式匹配

/*******************************************************************Copyright(c) 2016, Harry HeAll rights reserved.Distributed under the BSD license.(See accompanying file LICENSE.txt athttps://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)*******************************************************************///==================================================================// 《剑指Offer——名企面试官精讲典型编程题》代码// 作者：何海涛//==================================================================// 面试题19：正则表达式匹配// 题目：请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'// 表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题// 中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"// 和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。#include 
    
     #include
     
      using namespace std;bool matchCore(const char* str, const char* pattern);bool match(const char* str, const char* pattern){    if (str == nullptr || pattern == nullptr)        return false;    return matchCore(str, pattern);}bool matchCore(const char* str, const char* pattern){    if (*str == '\0' && *pattern == '\0')        return true;    if (*str != '\0' && *pattern == '\0')        return false;    if (*(pattern + 1) == '*')    {        if (*pattern == *str || (*pattern == '.' && *str != '\0'))            // 进入有限状态机的下一个状态            return matchCore(str + 1, pattern + 2)            // 继续留在有限状态机的当前状态             || matchCore(str + 1, pattern)            // 略过一个'*'             || matchCore(str, pattern + 2);        else            // 略过一个'*'            return matchCore(str, pattern + 2);    }    if (*str == *pattern || (*pattern == '.' && *str != '\0'))        return matchCore(str + 1, pattern + 1);    return false;}// ====================测试代码====================void Test(const char* testName, const char* string, const char* pattern, bool expected){    if (testName != nullptr)        printf("%s begins: ", testName);    if (match(string, pattern) == expected)        printf("Passed.\n");    else        printf("FAILED.\n");}int main(int argc, char* argv[]){    Test("Test01", "", "", true);    Test("Test02", "", ".*", true);    Test("Test03", "", ".", false);    Test("Test04", "", "c*", true);    Test("Test05", "a", ".*", true);    Test("Test06", "a", "a.", false);    Test("Test07", "a", "", false);    Test("Test08", "a", ".", true);    Test("Test09", "a", "ab*", true);    Test("Test10", "a", "ab*a", false);    Test("Test11", "aa", "aa", true);    Test("Test12", "aa", "a*", true);    Test("Test13", "aa", ".*", true);    Test("Test14", "aa", ".", false);    Test("Test15", "ab", ".*", true);    Test("Test16", "ab", ".*", true);    Test("Test17", "aaa", "aa*", true);    Test("Test18", "aaa", "aa.a", false);    Test("Test19", "aaa", "a.a", true);    Test("Test20", "aaa", ".a", false);    Test("Test21", "aaa", "a*a", true);    Test("Test22", "aaa", "ab*a", false);    Test("Test23", "aaa", "ab*ac*a", true);    Test("Test24", "aaa", "ab*a*c*a", true);    Test("Test25", "aaa", ".*", true);    Test("Test26", "aab", "c*a*b", true);    Test("Test27", "aaca", "ab*a*c*a", true);    Test("Test28", "aaba", "ab*a*c*a", false);    Test("Test29", "bbbba", ".*a*a", true);    Test("Test30", "bcbbabab", ".*a*a", false);    system("pause");    return 0;}

链表问题总结

#include
    
     #include
     
      using namespace std;struct ListNode{    int _data;    ListNode *_pNext;    ListNode(int data)        :_pNext(nullptr),        _data(data)    {}};void PushFront(ListNode *&pNode,int data){    if (pNode == NULL)    {        pNode = new ListNode(data);    }    else    {        ListNode *pNew = new ListNode(data);        pNew->_pNext = pNode;        pNode = pNew;    }}void PushBack(ListNode *&pNode, int data){    if (pNode == NULL)    {        pNode = new ListNode(data);    }    else    {        ListNode *pCur = pNode;        ListNode *pNew = new ListNode(data);        while (pCur->_pNext)        {            pCur = pCur->_pNext;        }        pCur->_pNext = pNew;    }}ListNode *FindNode(ListNode *&pHead, int data){    assert(pHead);    ListNode*pCur = pHead;    while (pCur)    {        if (pCur->_data == data)            return pCur;        pCur = pCur->_pNext;    }    return nullptr;}void PopBack(ListNode *&pHead){    if (pHead == nullptr)        return;    ListNode *pCur = pHead;    ListNode *pPre = pCur;    if (pHead->_pNext == nullptr)    {        delete pHead;        pHead == nullptr;        return;    }    while (pCur->_pNext)    {        pPre = pCur;        pCur = pCur->_pNext;    }    pPre->_pNext = nullptr;    delete pCur;    pCur = nullptr;}void Reverse(ListNode *&pHead){    assert(pHead);    /*ListNode *pCur = pHead;    ListNode *pNew = nullptr;    ListNode *pNext = pCur->_pNext;    while (pNext)    {        pCur->_pNext = pNew;        pNew = pCur;        pCur = pNext;        pNext = pNext->_pNext;    }    pCur->_pNext = pNew;    pHead = pCur;*/    ListNode *pNewHead = nullptr;    ListNode *pTemp = nullptr;    ListNode *pCur = pHead;    while (pCur)    {        pTemp = pCur->_pNext;        pCur->_pNext = pNewHead;        pNewHead = pCur;        pCur = pTemp;    }    pHead = pNewHead;}ListNode *MeetingNode(ListNode *&pHead){    assert(pHead);    ListNode *pSlow = pHead->_pNext;    if (nullptr == pSlow)        return nullptr;    ListNode *pFast = pSlow->_pNext;    while (pFast&&pSlow)    {        if (pFast == pSlow)            return pSlow;        pSlow = pSlow->_pNext;        pFast = pFast->_pNext;        //注意快指针有可能为空        if (pFast)            pFast = pFast->_pNext;    }    return nullptr;}void Merge(ListNode *&pHead1,ListNode *&pHead2){    assert(pHead1&&pHead2);    ListNode *head = pHead1->_data > pHead2->_data ? pHead2 : pHead1;    ListNode *head1 = head;    ListNode *head2 = head == pHead1 ? pHead2 : pHead1;    ListNode *pNext = nullptr;    ListNode *pPre = nullptr;    while (head1&&head2)    {        if (head1->_data <= head2->_data)        {            pPre = head1;            head1 = head1->_pNext;        }        else        {            pNext = head2->_pNext;            pPre->_pNext = head2;            head2->_pNext = head1;            pPre = head2;            head2 = pNext;        }    }    pPre->_pNext = head1 == nullptr ? head2 : head1; }void SelectSort(ListNode *&pHead){    assert(pHead);    ListNode *pCur = pHead;    if (pHead->_pNext == nullptr)        return;    while (pCur)    {        ListNode *p = pCur->_pNext;        ListNode *min = pCur;        while (p)        {            if (min->_data > p->_data)                min = p;            p = p->_pNext;        }        if (min != p)            swap(min->_data, p->_data);        pCur = pCur->_pNext;    }}ListNode *EntryNodeOfLoop(ListNode *pHead){    ListNode *meetingNode = MeetingNode(pHead);    if (nullptr == meetingNode)        return nullptr;    ListNode *pCur = pHead;    while (pCur!=meetingNode)    {        pCur = pCur->_pNext;        meetingNode = meetingNode->_pNext;    }    return  pCur;}void RemoveRepeate(ListNode *&pHead){    if (pHead == nullptr || pHead->_pNext == nullptr)        return;    ListNode *pCur = pHead;    ListNode *pPre = nullptr;    while (pCur)    {        ListNode *pNext = pCur->_pNext;        bool needDelete = false;        if (pNext&&pNext->_data == pCur->_data)            needDelete = true;        if (!needDelete)        {            pPre = pCur;            pCur = pCur->_pNext;        }        else        {            int data = pCur->_data;            ListNode *pDel = pCur;            while (pDel&&pDel->_data == data)            {                pNext = pDel->_pNext;                delete pDel;                pDel = nullptr;                pDel = pNext;            }            if (nullptr == pPre)                pHead = pNext;            else                pPre->_pNext = pNext;            pCur = pNext;        }    }}void RemoveListNode(ListNode *&pHead,ListNode *&pNode){    if (pNode == nullptr)        return;    if (pNode->_pNext != nullptr)    {        pNode->_data = pNode->_pNext->_data;        ListNode *pTemp=pNode->_pNext;        pNode->_pNext = pTemp->_pNext;        delete pTemp;        pTemp = nullptr;    }    else    {        if (pNode == pHead)        {            delete pHead;            pHead = nullptr;        }        else        {            PopBack(pHead);        }    }}void ReversePrintList(ListNode *&pNode){    if (pNode&&pNode->_pNext)        ReversePrintList(pNode->_pNext);    if (pNode)        cout << pNode->_data<<" ";}int main(){    ListNode* pHead = nullptr;    PushBack(pHead, 1);    //PushBack(pHead, 1);    //PushBack(pHead, 1);    PushBack(pHead, 2);    PushBack(pHead, 3);//  PushBack(pHead, 4);//  PushBack(pHead, 4);    PushBack(pHead, 4);    PushBack(pHead, 5);    PushBack(pHead, 6);    PushBack(pHead, 7);    RemoveRepeate(pHead);//  ListNode *pDel = FindNode(pHead,1);    Reverse(pHead);//  RemoveListNode(pHead, pDel);    ReversePrintList(pHead);    system("pause");}

转载于:https://www.cnblogs.com/readlearn/p/10806440.html

你可能感兴趣的文章

SQL语句调优-基础知识准备

查看>>

[ACM_模拟][ACM_数学] LA 2995 Image Is Everything [由6个视图计算立方体最大体积]

查看>>

《GK101任意波发生器》升级固件发布（版本：1.0.2.build124）