网站核心推广思路,运维工程师一月多少钱,最好的网站开发平台,高级网站开发工程师证书目录
基础递归问题#xff1a;
1. 斐波那契数#xff08;简单#xff09;
1.1 递归求解
1.2 迭代求解
2. 爬楼梯#xff08;简单#xff09;
2.1 递归求解
2.2 迭代求解
3. 汉诺塔问题#xff08;简单#xff09;
3.1 递归求解
4. Pow(x, n)#xff08;中等
1. 斐波那契数简单
1.1 递归求解
1.2 迭代求解
2. 爬楼梯简单
2.1 递归求解
2.2 迭代求解
3. 汉诺塔问题简单
3.1 递归求解
4. Pow(x, n)中等
4.1 递归求解
4.2 迭代求解
链表递归问题
1. 合并两个有序链表简单
1.1 递归求解
1.2 迭代求解
2. 反转链表简单
2.1 递归求解
2.2 迭代求解
3. 两两交换链表中的节点中等
3.1 递归求解
3.2 迭代求解
4. 合并 K 个升序链表困难
4.1 递归求解
4.2 迭代求解 在解决一个规模为n的问题时如果满足以下条件我们可以使用递归来解决
问题可以被划分为规模更小的子问题并且这些子问题具有与原问题相同的解决方法。当我们知道规模更小的子问题规模为n-1的解时我们可以直接计算出规模为n的问题的解。存在一种简单情况或者说当问题的规模足够小时我们可以直接求解问题。
一般的递归求解过程如下
验证是否满足简单情况。假设较小规模的问题已经解决解决当前问题。
上述步骤可以通过数学归纳法来证明。
基础递归问题
1. 斐波那契数简单
1.1 递归求解
重复的子问题——函数头设计
int fib(int n)
子问题在做什么——函数体设计
fib(n - 1) fib(n - 2)
递归出口
fib(0) 0
fib(1) 1
class Solution {
public:int fib(int n) {if (n 1)return n;return fib(n - 1) fib(n - 2);}
};
1.2 迭代求解
递归算法在计算时存在着大量的重复计算执行效率低n值稍大时非常耗费时间。斐波那契数列用迭代算法更高效。
class Solution {
public:int fib(int n) {if (n 1)return n;int a 0;int b 1;int c 0;for (int i 2; i n; i){c a b;a b;b c;}return c;}
};
2. 爬楼梯简单
2.1 递归求解
重复的子问题——函数头设计
int climbStairs(int n)
子问题在做什么——函数体设计
如果先走1级台阶还剩n - 1级台阶有climbStairs(n - 1)种走法如果先走2级台阶还剩n - 2级台阶有climbStairs(n - 2)种走法。一共的走法
climbStairs(n - 1) climbStairs(n - 2)
递归出口
当n 1时只有1种走法。
当n 2时可以一次走1级台阶走两次也可以一次走2级台阶走一次。所以一共有2种走法。
climbStairs(1) 1
climbStairs(2) 2
class Solution {
public:int climbStairs(int n) {if (n 2)return n;return climbStairs(n - 1) climbStairs(n - 2);}
};
But这题在LeetCode上用递归会超时o(´^)o
可以看出爬楼梯是斐波那契数的应用。
2.2 迭代求解
class Solution {
public:int climbStairs(int n) {if (n 2)return n;int a 1;int b 2;int c 0;for (int i 3; i n; i){c a b;a b;b c;}return c;}
};
3. 汉诺塔问题简单
3.1 递归求解
重复的子问题——函数头设计
有三根柱子A、B、CA柱上有n个盘子将所有盘子从A柱经B柱全部移到C柱上。
void dfs(int n, vectorint A, vectorint B, vectorint C)
子问题在做什么——函数体设计
该问题可划分成2个自相似问题和1次移动
将n-1个盘子从A柱经C柱全部移到B柱上dfs(n - 1, A, C, B);将第n个盘子从A柱移到C柱上C.push_back(A.back()); A.pop_back();将n-1个盘子从B柱经A柱全部移到C柱上dfs(n - 1, B, A, C);
递归出口
当A柱只剩1个盘子时即n 1时将其从A柱移到C柱上。
C.push_back(A.back());
A.pop_back();
class Solution {
public:void hanota(vectorint A, vectorint B, vectorint C) {if (A.empty())return;dfs(A.size(), A, B, C);}private:// n个盘子从A经B移到Cvoid dfs(int n, vectorint A, vectorint B, vectorint C){if (n 1){C.push_back(A.back());A.pop_back();return;}dfs(n - 1, A, C, B);C.push_back(A.back());A.pop_back();dfs(n - 1, B, A, C);}
};
4. Pow(x, n)中等
4.1 递归求解
快速幂算法的核心思想就是每一步都把指数分成两半而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小所需要执行的循环次数也变小而最后表示的结果却一直不会变。其时间复杂度为 O(log₂N) 与朴素的O(N)相比效率有了极大的提高。 如果n是负数所以只需考虑n是自然数的情况
假设n/2向下取整则需要分奇偶两种情况
当n是偶数时当n是奇数时
重复的子问题——函数头设计
double dfs(double x, long long n) n是非负数
用long long接收n防止-2^31转换成2^31越界。
子问题在做什么——函数体设计
判断n的奇偶性带入不同的公式。
偶数return dfs(x * x, n / 2); 偶数return dfs(x * x, n / 2) * x;
递归出口
当 n 0 时任何数的0次幂都等于1返回1.0
class Solution {
public:double myPow(double x, int n) {return n 0 ? 1.0 / dfs(x, -(long long)n) : dfs(x, n);}private:double dfs(double x, long long n){if (n 0)return 1.0;return n % 2 0 ? dfs(x * x, n / 2) : dfs(x * x, n / 2) * x;}
};
4.2 迭代求解
二进制角度的快速幂算法
假设n的二进制为bk .….. b2 b1 b0则 当bi 0时
当bi 1时
我们从x开始不断地进行平方如果bi 1就将对应的计入答案。
举个例子
计算ans初始值为1.011的二进制表示为1011
将计入答案
将计入答案
将不计入答案
将计入答案
即
class Solution {
public:double myPow(double x, int n) {return n 0 ? 1.0 / quickPower(x, -(long long)n) : quickPower(x, n);}private:double quickPower(double x, long long n){double ans 1.0;while (n){// 如果最低位为1将对应的x的幂值计入答案if ((n 1) 1){ans * x;}x * x;// 舍弃n的二进制的最低位这样每次只要判断最低位即可n 1;}return ans;}
};
链表递归问题
1. 合并两个有序链表简单
1.1 递归求解
重复的子问题——函数头设计
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
子问题在做什么——函数体设计
选择两个链表的头节点中值较小的那一个作为最终合并的新链表的头节点然后将剩下的链表交给递归函数去处理。
比较list1-val和list2-val的大小假设list1-val较小list1-next mergeTwoLists(list1-next, list2);return list1;
递归出口
当某一个链表为空的时候返回另外一个链表。
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 nullptr)return list2;if (list2 nullptr)return list1;if (list1-val list2-val){list1-next mergeTwoLists(list1-next, list2);return list1;}else{list2-next mergeTwoLists(list1, list2-next);return list2;}}
};
1.2 迭代求解
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* preHead new ListNode; // 哨兵节点ListNode* tail preHead;// 取小的尾插while (list1 list2){if (list1-val list2-val){tail-next list1;tail tail-next;list1 list1-next;}else{tail-next list2;tail tail-next;list2 list2-next;}}if (list1){tail-next list1;}if (list2){tail-next list2;}return preHead-next;}
};
2. 反转链表简单
2.1 递归求解
重复的子问题——函数头设计
ListNode* reverseList(ListNode* head)
子问题在做什么——函数体设计
将当前结点之后的链表反转然后把当前结点添加到反转后的链表后面即可返回反转后的头节点。
ListNode* newHead reverseList(head-next);head-next-next head; head-next nullptr;return newHead;
递归出口
当前结点为空或者当前只有一个结点的时候不用反转直接返回。
class Solution {
public:ListNode* reverseList(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* newHead reverseList(head-next);head-next-next head;head-next nullptr;return newHead;}
};
2.2 迭代求解
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre nullptr;ListNode* cur head;while (cur){ListNode* next cur-next;cur-next pre;pre cur;cur next;}return pre;}
};
3. 两两交换链表中的节点中等
3.1 递归求解
重复的子问题——函数头设计
ListNode* swapPairs(ListNode* head)
子问题在做什么——函数体设计
将从第三个节点开始的链表两两交换节点然后再把前两个节点交换一下链接上刚才处理过的链表并返回。
ListNode* tmp swapPairs(head-next-next);ListNode* newHead head-next; newHead-next head;head-next tmp;return newHead;
递归出口
当前结点为空或者当前只有一个结点的时候不用两两交换直接返回。
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* tmp swapPairs(head-next-next);ListNode* newHead head-next;newHead-next head;head-next tmp;return newHead;}
};
3.2 迭代求解
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* preHead new ListNode(0, head); // 哨兵节点ListNode* cur preHead;// cur后面的两个节点交换while (cur-next cur-next-next){ListNode* node1 cur-next;ListNode* node2 cur-next-next;cur-next node2;node1-next node2-next;node2-next node1;cur node1;}return preHead-next;}
};
4. 合并 K 个升序链表困难
4.1 递归求解
分治的思想类似归并排序 划分两个子区间 分别对两个子区间的链表进行合并形成两个有序链表 合并两个有序链表
重复的子问题——函数头设计
ListNode* merge(vectorListNode* lists, int begin, int end)
子问题在做什么——函数体设计
划分两个子区间int mid (begin end) / 2;递归合并两个子区间 ListNode* l1 merge(lists, begin, mid); ListNode* l2 merge(lists, mid 1, end);合并两个有序链表return mergeTowList(l1, l2);
递归出口
当区间只有一个链表时不合并。另外当题目给出空链表时不合并。
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {return merge(lists, 0, lists.size() - 1);}private:ListNode* merge(vectorListNode* lists, int begin, int end){if (begin end)return nullptr;if (begin end)return lists[begin];int mid (begin end) / 2;ListNode* l1 merge(lists, begin, mid);ListNode* l2 merge(lists, mid 1, end);return mergeTwoLists(l1, l2);}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){ListNode* preHead new ListNode; // 哨兵节点ListNode* tail preHead;// 取小的尾插while (list1 list2){if (list1-val list2-val){tail-next list1;tail tail-next;list1 list1-next;}else{tail-next list2;tail tail-next;list2 list2-next;}}if (list1){tail-next list1;}if (list2){tail-next list2;}return preHead-next;}
};
4.2 迭代求解
和“合并两个有序链表”类似就是取小的尾插。怎么判断K个链表未合并的头节点中最小的那个利用堆这个数据结构即可。把K个链表未合并的头节点放进一个小根堆堆顶就是最小的那个。
class Solution {struct cmp{bool operator()(ListNode* n1, ListNode* n2){return n1-val n2-val;}};public:ListNode* mergeKLists(vectorListNode* lists) {// 创建小根堆priority_queueListNode*, vectorListNode*, cmp heap;// 将所有头节点放进小根堆for (auto l : lists){if (l){heap.push(l);}}// 合并链表ListNode* preHead new ListNode; // 哨兵节点ListNode* tail preHead;while (!heap.empty()){// 取堆顶节点尾插tail-next heap.top();heap.pop();tail tail-next;// 将刚才合并的节点的下一个节点补充进堆if (tail-next){heap.push(tail-next);}}return preHead-next;}
};
