欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C/C++練習題之合并k個已排序的鏈表

 更新時間:2023年06月19日 10:46:00   作者:春人.  
這篇文章主要給大家介紹了關于C/C++練習題之合并k個已排序的鏈表的相關資料,文中通過圖文以及實例代碼介紹的非常詳細,對大家學習或者使用C/C++具有一定的參考學習價值,需要的朋友可以參考下

前言:

今天給大家分享一道面試中常見的題目——合并K個升序鏈表,我會用暴力和分治兩鐘方法去求解這道題目,通過動圖展示問題求解的全過程。這里提醒大家,畫圖是我們求解復雜問題的有效手段,有時可以起到事半功倍的效果,各位小伙伴在做題的過程中如果遇到麻煩,不妨動手畫畫圖喲。

題目描述:

合并K個升序的鏈表并將結果作為一個升序的鏈表返回其頭節(jié)點。例如:

  • 輸入:[{1,2},{1,4,5},{6},{2,3,5}]
  • 輸出:{1,1,2,2,3,4,5,5,6}

思路一:暴力求解法

首先根據(jù)題目的描述,畫出如下模擬圖。

第一步:確定合并后鏈表的頭節(jié)點rhead

從上圖中可以看出:lists中存放是每個鏈表的頭節(jié)點,那合并后鏈表的頭節(jié)點一定是這四個頭結點中最小的那個,因此我們只需要遍歷lists就可以找到最小的頭節(jié)點,然后把它賦值給rhead,執(zhí)行完第一步得到的結果如下圖,用黃色標注已經(jīng)排好序的節(jié)點:

第二步:選擇次小的進行尾插

如上圖,接下來我們需要在所有藍色節(jié)點中選出最小的一個尾插到rhead指向的鏈表,因此我們再定義一個rtail指向合并后鏈表的最后一個節(jié)點。但是我們發(fā)現(xiàn)如果按照上圖的結構,直接從四個藍色節(jié)點里面選出最小的,顯然十分困難, 因為第一個鏈表中待比較的節(jié)點不再數(shù)組中。如果向第一步那樣,所有的節(jié)點都在數(shù)組中,那選出最小的節(jié)點簡直是易如反掌,只需要遍歷一遍數(shù)組即可。因為lists數(shù)組中存的永遠都是頭節(jié)點,所以這里我們直接修改第一個鏈表的頭節(jié)點即可,通過lists[0] = lists[0]->next就可以實現(xiàn)。修改后的結構如下圖所示:

此時所有待比較的節(jié)點都來到了數(shù)組中,和第一步的邏輯一樣,只需要遍歷一遍數(shù)組就可以找到最小的節(jié)點,找到后尾插到rhead指向的鏈表。如下圖,其中黃色節(jié)點是已排好序的節(jié)點,藍色節(jié)點是待比較的節(jié)點。

總體邏輯就是這樣,接下來循環(huán)執(zhí)行第二步,找到次小的進行尾插,直到數(shù)組中的所有節(jié)點都為空,此時說明數(shù)組中的所有鏈表都已經(jīng)排好序了,返回rhead即可??偟倪^程動圖如下:

??代碼實現(xiàn):

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* rhead = nullptr;//定義合并后鏈表的頭節(jié)點
        ListNode* rtail = nullptr;//定義合并后鏈表的尾結點
        while (true)
        {
            int minIndex = -1;//定義lists數(shù)組中最小節(jié)點下標,最初等于-1,(下簡稱最小位置)
            int i = lists.size();//
            while (i--)
            {
                if (lists[i] != nullptr)//首先判斷數(shù)組當前位置的節(jié)點是否為空
                {
                    //當前節(jié)點不為空再進來
                    if (minIndex == -1)//判斷最小位置是否是-1,如果是就直接把當前位置賦值給minIndex
                    {
                        minIndex = i;
                    }
                    else if (lists[i]->val < lists[minIndex]->val)//如果minIndex不為-1,則用數(shù)組當前位置節(jié)點的val與記錄的最小位置上節(jié)點的val進行比較
                    {
                        minIndex = i;//如果當前節(jié)點的val值更小,那就更新minIndex
                    }
                }
            }
            if (minIndex == -1)//遍歷完一遍數(shù)組如果minIndex的值還是-1,說明當前數(shù)組中的所有節(jié)點全是空
            {
                return rhead;//此時說明所有鏈表已經(jīng)合并完成,可以返回頭節(jié)點
            }
            if (rhead == nullptr)//確定新鏈表的頭節(jié)點
            {
                rhead = rtail = lists[minIndex];
            }
            else//之后每找出一個最小的節(jié)點,進行尾插即可
            {
                rtail->next = lists[minIndex];
                rtail = rtail->next;
            }
            lists[minIndex] = lists[minIndex]->next;//最小的節(jié)點已經(jīng)尾插到新鏈表,因此要對最小位置上的節(jié)點更新
        }
    }
};

上面代碼中需要注意的有:minIndex 是用來記錄lists中最小節(jié)點的位置,它的初始值必須是-1,不能是0或其他數(shù)字,因為我們不知道0或其他位置上的節(jié)點是否為空。還有需要注意的地方是,每當遍歷到一個節(jié)點,首先要判斷是否為nullptr,當不為空的時候再進行比較,避免出現(xiàn)空指針問題,其次要判斷minIndex當前是否為-1,如果是-1,就不用比較,直接把當前位置賦值給minIndex 即可,因為如果當minIndex == -1 的時候進行比較,會導致數(shù)組越界。

思路二:分治歸并法

分治即“分而治之”,“分”指的是將一個大而復雜的問題劃分成多個性質(zhì)相同但是規(guī)模更小的問題,子問題繼續(xù)按照這樣劃分,直到問題可以被輕易解決;“治”指的是將子問題單獨進行處理。經(jīng)過分治后的子問題,需要將解進行合并,也就是所謂的“歸并”,這樣才能得到原問題的解,因此整個分支過程經(jīng)常采用遞歸來實現(xiàn)。

針對這道題目來說,我們比較熟悉的是合并兩個有序鏈表,因此我們就可以把合并K個有序鏈表的問題,劃分成合并兩個有序鏈表的問題,具體過程我通過動圖來給大家演示,其中相同的顏色代表一個子問題

通過上面的動圖我們可以發(fā)現(xiàn),當子問題被分解到只剩一個鏈表的時候,就無法再進行分解,此時就需要返回了,其實這就是遞歸的終止條件,也就是當left == right的時候就只剩一個鏈表,此時就應該返回了,返回的結果就是這一個鏈表。等左右區(qū)間各返回一個鏈表,此時就要開始對這兩個鏈表進行合并,從而得到一個新的有序鏈表,再把這個鏈表作為子問題的處理結果進行返回。這其實很像二叉樹的后序遍歷,如此循環(huán)往復,直到最終的大問題被解決。

??代碼實現(xiàn):

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return dividemerge(lists, 0, lists.size() - 1);
    }
private:
    ListNode* dividemerge(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right)
        {
            return nullptr;
        }
        else if (left == right)
        {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        //分治
        ListNode* head1 = dividemerge(lists, left, mid);
        ListNode* head2 = dividemerge(lists, mid + 1, right);
        //對子問題處理
        return Merge(head1, head2);
    }
private:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并兩個有序鏈表
    {
        if (pHead1 == nullptr)
        {
            return pHead2;
        }
        if (pHead2 == nullptr)
        {
            return pHead1;
        }
        ListNode* pHeadret, * tail;
        if (pHead1->val < pHead2->val)
        {
            pHeadret = tail = pHead1;
            pHead1 = pHead1->next;
        }
        else
        {
            pHeadret = tail = pHead2;
            pHead2 = pHead2->next;
        }
        while (pHead1 != nullptr && pHead2 != nullptr)
        {
            if (pHead1->val < pHead2->val)
            {
                tail->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                tail->next = pHead2;
                pHead2 = pHead2->next;
            }
            tail = tail->next;
        }
        if (pHead2 != nullptr)
        {
            tail->next = pHead2;
        }
        if (pHead1 != nullptr)
        {
            tail->next = pHead1;
        }
        return pHeadret;
    }
};

分治的大思想,其實就體現(xiàn)在下面三行代碼中:

//分治
ListNode* head1 = dividemerge(lists, left, mid);        
ListNode* head2 = dividemerge(lists, mid + 1, right);

//對子問題處理        
return Merge(head1, head2);

我們只需要知道,前兩行代碼將一個大問題進行分解,得到的兩個子問題,并且經(jīng)過dividemerge函數(shù)把這兩個子問題都處理好了,并且得到了兩個結果,針對本題,就是得到了兩個有序的鏈表,分別是head1head2,然后我們只需要對這兩個鏈表進行合并就可以完成題目的要求,也就是第三行代碼實現(xiàn)的功能。這就是分治的思想

總結

到此這篇關于C/C++練習題之合并k個已排序的鏈表的文章就介紹到這了,更多相關C/C++合并k個已排序的鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • 使用ShellClass獲取文件屬性詳細信息的實現(xiàn)方法

    使用ShellClass獲取文件屬性詳細信息的實現(xiàn)方法

    本篇文章是對ShellClass獲取文件屬性詳細信息的實現(xiàn)方法進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • opencv?C++模板匹配的簡單實現(xiàn)

    opencv?C++模板匹配的簡單實現(xiàn)

    這篇文章主要介紹了opencv?C++模板匹配的簡單實現(xiàn),本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-02-02
  • C++字符串輸入緩沖區(qū)機制詳解

    C++字符串輸入緩沖區(qū)機制詳解

    緩沖區(qū)是用來存放流中的數(shù)據(jù),本文詳細的介紹了C++字符串輸入緩沖區(qū)機制,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2021-10-10
  • C++詳解如何實現(xiàn)動態(tài)數(shù)組

    C++詳解如何實現(xiàn)動態(tài)數(shù)組

    這篇文章主要為大家詳細介紹了C++實現(xiàn)動態(tài)數(shù)組的方法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • C++指針與數(shù)組:指針詳解

    C++指針與數(shù)組:指針詳解

    本文從初學者的角度,深入淺出地講解C++中的指針、數(shù)組指針,對最常混淆的引用傳遞、值傳遞和指針傳遞做了區(qū)處,需要的朋友可以參考下
    2021-09-09
  • C++深淺拷貝及簡易string類實現(xiàn)方式

    C++深淺拷貝及簡易string類實現(xiàn)方式

    這篇文章主要介紹了C++深淺拷貝及簡易string類實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • 在C++中高效使用和處理Json格式數(shù)據(jù)的示例代碼

    在C++中高效使用和處理Json格式數(shù)據(jù)的示例代碼

    最近的項目在用c處理后臺的數(shù)據(jù)時,因為好多外部接口都在使用Json格式作為返回的數(shù)據(jù)結構和數(shù)據(jù)描述,如何在c中高效使用和處理Json格式的數(shù)據(jù)就成為了必須要解決的問題,需要的朋友可以參考下
    2023-11-11
  • C++的類型轉(zhuǎn)換詳細介紹

    C++的類型轉(zhuǎn)換詳細介紹

    這篇文章主要介紹了C++的類型轉(zhuǎn)換詳細介紹的相關資料,需要的朋友可以參考下
    2017-06-06
  • C++ 如何實現(xiàn)一個日期類

    C++ 如何實現(xiàn)一個日期類

    通過對類和對象的學習,理解了類是對象的抽象描述,實現(xiàn)日期類涉及定義年月日屬性及成員函數(shù)如打印日期、日期加減,重點介紹了運算符重載的概念和作用,通過代碼示例展示了如何實現(xiàn)一個日期類,包括頭文件和源文件的分離編寫
    2024-10-10
  • opencv3/C++實現(xiàn)霍夫圓/直線檢測

    opencv3/C++實現(xiàn)霍夫圓/直線檢測

    今天小編就為大家分享一篇opencv3/C++實現(xiàn)霍夫圓/直線檢測,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12

最新評論