常见算法设计思想 分治法
动态规划法
贪心算法
回溯法
分支界限算法
…
分治与递归的关系 递归是一种结构；反复的调用自身
分治是一种思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解建立原问题的解。
分治模式在每层递归时都有三个步骤：
分解：原问题为若干子问题
解决：递归求解这些子问题；若子问题足够小，则直接求解
合并：合并这些子问题的解，成原来的问题
适用条件 1、原问题可以分解为若干子问题
2、问题小到一定程度可以很方便求出解
3、子问题解可以合并得到原问题
举例： 1、求阶乘 f(n+1) = n * f(n)
2、斐波那契数列 f(n) = f(n-1) + f(n-2)
2、归并排序 sort_merge(a, b) = merge(sort_merge(a, b/2), sort_merge(b/2, b));
2、汉诺塔 …
优点与缺点 【分治】代码
#include
#include struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* merge(struct ListNode* a, struct ListNode* b){
if (a == NULL && b != NULL) {
return b;
}
else if (a != NULL && b == NULL) {
return a;
}else if (a != NULL && b != NULL) {
struct ListNode* s = (struct ListNode*)malloc(sizeof(struct ListNode));
if (a->val > b->val) {
s->val = b->val;
b = b->next;
}else {
s->val = a->val;
a = a->next;
}
s->next = merge(a, b);
return s;
}
else {
return NULL;
}
}struct ListNode* sortList(struct ListNode* head){
struct ListNode* fast = head;
struct ListNode* slow = head;
struct ListNode* tmp = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
tmp = slow;
slow = slow->next;
}tmp->next = NULL;
printf("val = %d\n", tmp->val);
sortList(head);
sortList(slow);
return merge(head, slow);
}int main()
{
struct ListNode a;
struct ListNode b;
struct ListNode c;
struct ListNode d;
a.next = &b;
a.val = 3;
b.next = &c;
b.val = 4;
c.next = &d;
c.val = 5;
d.next = NULL;
d.val = 6;
sortList(&a);
while (1);
} 
