首页 热点专区 义务教育 高等教育 出国留学 考研考公

我想知道 蓝桥杯 力扣 牛客网还有公司的算法面试的上机都是怎样形式的...

发布网友

我来回答

2个回答

懂视网

class Solution { 2 public: 3 unordered_map<string, vector<string>>map; 4 vector<string> wordBreak(string s, unordered_set<string> &dict) { 5 if (map.find(s) != map.end())return map[s]; 6 if (s.empty())return { "" }; 7 vector<string>res; 8 for (auto word : dict) 9 { 10 if (s.substr(0, word.size()) != word)continue; 11 vector<string>rem = wordBreak(s.substr(word.size()), dict); 12 for (auto str : rem) 13 res.push_back(word + (str.empty() ? "" : " ") + str); 14 } 15 return map[s] = res; 16 } 17 };

 




  方法二:使用动态规划
 1 //使用动态规划
 2 
 3 class Solution {
 4 public:
 5 vector<string> wordBreak(string s, unordered_set<string> &dict) {
 6  int len = s.length();
 7  dp = new vector<bool>[len];
 8  for (int pos = 0; pos < len; pos++) {
 9  for (int i = 1; i < len - pos + 1; i++) {
10   if (dict.find(s.substr(pos, i)) != dict.end())
11   dp[pos].push_back(true);
12   else
13   dp[pos].push_back(false);
14   }
15  }
16  dfs(s, len - 1);
17  return res;
18  }
19 void dfs(string s, int n) {
20  if (n >= 0) {
21  for (int i = n; i >= 0; i--) {
22   if (dp[i][n - i]) {
23   mid.push_back(s.substr(i, n - i + 1));
24   dfs(s, i - 1);
25    mid.pop_back();
26   }
27   }
28  }
29  else {
30  string r;
31  for (int j = mid.size() - 1; j >= 0; j--) {
32   r += mid[j];
33   if (j > 0)
34   r += " ";
35   }
36   res.push_back(r);
37  }
38  }
39 vector<bool> *dp;
40 vector<string> res;
41 vector<string> mid;
42 };

 



力扣算法——140WordBreakII【H】

标签:red   The   tor   nat   方法   使用   void   lis   NPU   

热心网友

类人家的后台有,你在自己这里运行就自己写主类,你提交就提交那个方法的就行

声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com