电脑网站转手机版,西部数码网站管理助手 mysql,重庆市有几个区,网站开发公司php工资文章目录 DP1 斐波那契数列法1#xff1a;递归法2#xff1a;动态规划法3#xff1a;优化空间复杂度 2.分割连接字符串3. 给定一个字符串s和一组单词dict#xff0c;在s中添加空格将s变成一个句子 DP1 斐波那契数列 法1#xff1a;递归
// 递归
#include iostream递归法2动态规划法3优化空间复杂度 2.分割连接字符串3. 给定一个字符串s和一组单词dict在s中添加空格将s变成一个句子 DP1 斐波那契数列 法1递归
// 递归
#include iostream
using namespace std;int Fibonacci(int n)
{if(n 0) return 0;if(n 1) return 1;return Fibonacci(n - 1) Fibonacci(n - 2);
}
int main() {int a;while (cin a) { // 注意 while 处理多个 caseint b Fibonacci(a);cout b endl;}
}法2动态规划
// DP
#include iostream
using namespace std;int Fibonacci(int n)
{//创建一个数组保存中间状态的解int* F new int[n 1];//初始化F[0] 0; F[1] 1;//状态公式F[i] F[i - 1] F[i - 2];for(int i 2; i n 1; i){F[i] F[i - 1] F[i - 2];}return F[n];
}
int main() {int a;while (cin a) { // 注意 while 处理多个 casecout Fibonacci(a) endl;}
}法3优化空间复杂度
#include iostream
using namespace std;int Fibonacci(int n)
{//状态公式F[i] F[i - 1] F[i - 2];//优化空间复杂度 O(n) - O(1)if(n 0) return 0;if(n 1) return 1;int fn 0, f0 0, f1 1;for(int i 2; i n 1; i){fn f0 f1;//更新中间状态f0 f1;f1 fn;}return fn;
}
int main() {int a;while (cin a) { // 注意 while 处理多个 casecout Fibonacci(a) endl;}
}2.分割连接字符串
1、给定一个字符串s和一组单词dict判断s是否可以用空格分割成一个单词序列使得单词序列中所有的单词都是dict中的单词序列可以包含一个或多个单词。
例如: 给定s“leetcode” dict[“leet”, “code”]. 返回true因为leetcode可以被分割成leet code.
#include vector
#include string
#include unordered_set
using namespace std;bool wordBreak(string s, unordered_setstring dict) {// 检查输入是否有效if (s.empty() || dict.empty()) {return false;}// 动态规划数组flag[i]表示s的前i个字符是否可以被拆分vectorbool flag(s.length() 1, false);flag[0] true; // 空字符串可以被拆分// 遍历字符串的每个位置for (int i 1; i s.length(); i) {// 从i-1向前遍历到0for (int j i - 1; j 0; j--) {// 如果前j个字符可以被拆分且从j到i的子字符串在字典中if (flag[j] dict.find(s.substr(j, i - j)) ! dict.end()) {flag[i] true;break; // 当前位置可以被拆分跳出内层循环}}}// 返回整个字符串是否可以被拆分return flag[s.length()];
}3. 给定一个字符串s和一组单词dict在s中添加空格将s变成一个句子
这段代码实现了回溯法深度优先搜索DFS来生成所有可能的单词拆分结果。 2、给定一个字符串s和一组单词dict在s中添加空格将s变成一个句子使得句子中的每一个单词都是dict中的单词
返回所有可能的结果
例如给定的字符串s “catsanddog”,
dict [“cat”, “cats”, “and”, “sand”, “dog”].
返回的结果为[“cats and dog”, “cat sand dog”].
#include vector
#include string
#include unordered_set
using namespace std;class Solution {
public:vectorstring wordBreak(string s, unordered_setstring dict) {vectorstring result;DFS(s, dict, s.length(), , result);return result;}private:void DFS(const string s, const unordered_setstring dict, int index, string str, vectorstring result) {// 如果索引小于等于0说明已经处理完整个字符串if (index 0) {if (!str.empty()) {// 去掉最后一个多余的空格并将结果加入到结果列表中result.push_back(str.substr(0, str.length() - 1));}return;}// 从当前索引向前遍历寻找可以拆分的单词for (int i index; i 0; i--) {// 检查从i到index的子字符串是否在字典中if (dict.find(s.substr(i, index - i)) ! dict.end()) {// 将当前单词加入到路径中并继续递归处理DFS(s, dict, i, s.substr(i, index - i) str, result);}}}
};
