算法設(shè)計(jì)思想之“分而治之”

• 分而治之是是什么
• 場景一：歸并排序
• 場景二：快速排序
• LeetCode：374.猜數(shù)字大小
• LeetCode：226.翻轉(zhuǎn)二叉樹
• LeetCode：100.相同的樹
• LeetCode：101.對稱二叉樹
• 思考題

分而治之是是什么

分而治之是算法設(shè)計(jì)中的一種方法
它將一個(gè)問題分成多個(gè)和原問題相似的小問題，遞歸解決小問題，再將結(jié)果合并以解決原來的問題
應(yīng)用場景：歸并排序、快速排序、二分搜索、翻轉(zhuǎn)二叉樹…

場景一：歸并排序

分：把數(shù)組從中間一分為二
解：遞歸地對兩個(gè)子數(shù)組進(jìn)行歸并排序
合：合并有序子數(shù)組

場景二：快速排序

分：選基準(zhǔn)，按基準(zhǔn)把數(shù)組分成兩個(gè)子數(shù)組
解：遞歸地對兩個(gè)子數(shù)組進(jìn)行快速排序
合：對兩個(gè)子數(shù)組進(jìn)行合并

LeetCode：374.猜數(shù)字大小

解題思路
二分搜索，同樣具備“分、解、合”的特性
考慮選擇分而治之

解題步驟
分：計(jì)算中間元素，分割數(shù)組
解：遞歸地在較大或者較小子組件進(jìn)行二分搜索
合：不需要此步，因?yàn)樵谧訑?shù)組中搜到就返回了

時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度是O(logn)

LeetCode：226.翻轉(zhuǎn)二叉樹

解題思路
先翻轉(zhuǎn)左右子樹，再將子樹換個(gè)位置
符合“分、解、合”特性
考慮選擇分而治之
解題步驟
分：獲取左右子樹
解：遞歸地翻轉(zhuǎn)左右子樹
合：將翻轉(zhuǎn)后的左右子樹換個(gè)位置放在根節(jié)點(diǎn)上

時(shí)間復(fù)雜度O（n），n是樹的節(jié)點(diǎn)數(shù)，空O（樹的高度），最壞的情況是O（n）

LeetCode：100.相同的樹

解題思路
兩個(gè)樹：根節(jié)點(diǎn)的值相同，左子樹相同，右子樹相同
符合“分、解、合”特性
考慮選擇分而治之
解題步驟
分：獲取兩個(gè)樹的左子樹和右子樹
解：遞歸地判斷兩個(gè)樹的左子樹是否相同，右子樹是否相同
合：將上述結(jié)果合并，如果根節(jié)點(diǎn)的值也相同，樹就相同

時(shí)間復(fù)雜度O(n),n是樹的節(jié)點(diǎn)數(shù)，空間復(fù)雜度最壞情況是O（n），好的情況是O(logN)

LeetCode：101.對稱二叉樹

解題思路
轉(zhuǎn)化為：左右子樹是否鏡像
分解為：樹1的左子樹和樹2的右子樹是否鏡像，樹1的右子樹和樹2的左子樹是否鏡像
符合“分、解、和”特性，考慮選擇分而治之
解題步驟
分：獲取兩個(gè)樹的左子樹和右子樹
解：遞歸地判斷樹1的左子樹和樹2的右子樹是否鏡像，樹1的右子樹和樹2的左子樹是否鏡像
合：如果上述都成立，且根節(jié)點(diǎn)值也相同，兩個(gè)樹就鏡像

時(shí)間復(fù)雜度O(n),n是樹的節(jié)點(diǎn)數(shù)，空間復(fù)雜度最壞情況是O（n），好的情況是O(logN)

思考題

1、說出分而治之算法的套路步驟
2、用分而治之的套路步驟，描述切西瓜的過程，無需Coding

總結(jié)

以上是生活随笔為你收集整理的（十二）算法设计思想之“分而治之”的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。