递归和分治 Leetcode刷题集合

参考博文：
1、从零开始学递归与分治 （作者：houjingyi233）
2、leetcode–递归、回溯和分治 （作者：xiayto）
3、leetcode刷题总结之递归 （作者：algsup）

还可以看一下我之前写的关于DFS的博客，加深对递归的理解：
1、深度优先算法DFS入门 (超级简单的例题入门)
2、深度优先算法(二) 一些例题加深对DFS的理解

分治问题，由**“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子问题**，再将子问题进行处理合并，从而实现对原问题的求解。
归并排序就是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为 1 的子数组；“治”即为把已经排好序的两个小数组合成为一个排好序的大数组，从长度为 1 的子数组开始，最终合成一个大数组。

一、50. Pow(x, n)

原题链接：https://leetcode-cn.com/problems/powx-n/

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:
输入: 2.00000, 10
输出: 1024.00000

示例 2:
输入: 2.10000, 3
输出: 9.26100

示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解题思路：

主要是注意n的正负，这个题比较简单了，直接递归调用就行：
如果 n 是负数，那么相当于求 (1/x)^(-n)。
如果 n 是正数 且 奇数，那么结果需要单独乘以 x
如果 n 是正数 且 偶数，求(x²⁾(n/2)，一直递归下去即可。
时间复杂度是O(1)，空间复杂度是O(1)。
**个人觉得，这个代码是O(1)，因为n只有32位，循环次数是有上限的常数。

runtime error: negation of -2147483648 cannot be represented in type ‘int’; cast to an unsigned type to negate this value to itself (solution.cpp)

解决方法：把int改为long long

class Solution {
public:
double myPow(double x, long long n) {
if(n==0) return 1; // n=0直接返回1
if(n==1) return x;
if(n<0) return 1.0/myPow(x,-n); //n<0时 x的n次方等于1除以x的-n次方分
//return 1.0/myPow(x,-n);
if(n%2==1) return x*myPow(x,n-1); //n是奇数时 x的n次方 = x*(x的n-1次方)
//return myPow(x*x, n/2); //n是偶数，使用分治，一分为二，等于x*x的n/2次方
//上面那一句也可以，只不过需要4ms，而下面两句只需要0ms，我也不知道为什么
double cur=myPow(x, n/2);
return cur*cur;
}
};

二、169. 多数元素

原题链接：https://leetcode-cn.com/problems/majority-element/

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

解题思路：

1、将区间分为左右，分别找到左右区间中的众数mode
2、当区间内，只有一个数时，则返回这个数
3、如果左右区间的mode为同一个数，就返回左区间或右区间的mode
4、如果不为同一个数，则分别计算左右区间mode个数，返回个数更多的一个

class Solution {
public:
int majorityElement(vector<int>& nums) {
return majorityElement(nums, 0, nums.size()-1);
}
int majorityElement(vector<int>&nums, int left, int right)
{
if(left==right) return nums[left]; //当区间内，只有一个数时，则返回这个数
int mid=(left+right)/2;
int leftMode=majorityElement(nums, left, mid);
int rightMode=majorityElement(nums, mid+1, right);
//如果左右区间的mode为同一个数，就返回左区间或右区间的mode
if(leftMode== rightMode) return leftMode;
//如果不为同一个数，则分别计算左右区间mode个数，返回个数更多的一个
int leftCount=0, rightCount=0;
for(int i=left; i<=mid; i++) if(nums[i]==leftMode) leftCount++;
for(int i=mid+1; i<=right; i++) if(nums[i]==rightMode) rightCount++;
if(leftCount>rightCount) return leftMode;
return rightMode;
}
};

三、 22. 括号生成

原题链接：https://leetcode-cn.com/problems/generate-parentheses/

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：
输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

解题思路：

1、每次加一个 ‘(’ 或者‘ ) ’
2、加‘)’的条件是‘(’的数目比较多 [易错点]。
3、递归结束条件：当字符串长度达到2n
用left记录左扩号剩余数目
用right记录右括号剩余数目
每次递归left-1或者right-1，用条件过滤掉不满足条件的项。

class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string>results;
kuohao(results, "", n, n);
return results;
}
void kuohao(vector<string>&results, string cur, int leftNum, int rightNum)
{
if(leftNum==0 &&rightNum==0)
{
results.push_back(cur);
return;
}
//加入左括号的情况
if(leftNum>0)
{
kuohao(results, cur+'(', leftNum-1, rightNum);
}
//加入右括号的情况
if(leftNum<rightNum)
{
kuohao(results, cur+')', leftNum, rightNum-1);
}
}
};

最后

以上就是顺利凉面为你收集整理的递归和分治 Leetcode刷题集合的全部内容，希望文章能够帮你解决递归和分治 Leetcode刷题集合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。