分治
分治,即“分而治之”
就是把原问题划分成若千个同类子问题,分别解决后，再把结果合并起来
关键点:
原问题和各个子问题都是重复的(同类的)一递归定义
除了向下递归“问题”,还要向上合并“结果”
分治算法- -般用递归实现
分治算法的"递归状态树”
实战
50.Pow(x, n)
https://leetcode.cn/problems/powx-n/
class Solution { public: double myPow(double x, int n) { if(n==0) return 1; if(n == -(1ll << 31)) return 1.0/(myPow(x,-(n+1))*x); if(n < 0) return 1.0/myPow(x,-n); double temp = myPow(x,n/2); double ans = temp*temp; if(n%2==1) ans *=x; return ans; } };
class Solution { public: double myPow(double x, long long n) { if(n==0) return 1; //if(n==-(1ll<<31)) return 1.0/myPow(x,-(n+1)*x); if(n<0) return 1.0/myPow(x,-n); double temp=myPow(x,n/2); double ans = temp*temp; if(n%2 == 1) ans*=x; return ans; } };
22.括号生成
https://leetcode.cn/problems/generate-parentheses/
分治划分子问题的标准:不重不漏
class Solution { public: vector<string> generateParenthesis(int n) { if(n == 0) return {""}; if(store.find(n) != store.end()) return store[n]; vector<string> ans; for(int k=1;k<=n;k++) { vector<string> A = generateParenthesis(k-1); vector<string> B = generateParenthesis(n-k); for(string & a:A) { for(string & b:B) { ans.push_back("(" + a + ")" +b); } } } store[n]=ans; return ans; } private: unordered_map<int ,vector<string>> store; };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
