C/C++每日一练(20230303)

目录

1. 字符串相乘

2. 单词拆分 II

3. 串联所有单词的子串

---

1. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

1. num1 和 num2 的长度小于110。
2. num1 和 num2 只包含数字 0-9。
3. num1 和 num2 均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

代码：

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:string multiply(string num1, string num2){string res(num1.length() + num2.length(), '0');for (int i = num2.length() - 1; i >= 0; i--){int j, carry = 0;for (j = num1.length() - 1; j >= 0; j--){carry += (num1[j] - '0') * (num2[i] - '0') + (res[i + j + 1] - '0');res[i + j + 1] = carry % 10 + '0';carry /= 10;}res[i + j + 1] = carry + '0';}int i;for (i = 0; i < res.length() - 1; i++){if (res[i] != '0'){break;}}return res.substr(i);}
};int main()
{Solution s;cout << s.multiply("2", "3") << endl;cout << s.multiply("123", "456") << endl;return 0;
} 

输出：

6
56088 

---

2. 单词拆分 II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出: ["cats and dog", "cat sand dog"]

示例 2：

输入: s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出: ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: []

代码：

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:vector<string> res;unordered_set<string> wordset;unordered_set<int> lenset;vector<string> wordBreak(string s, vector<string> &wordDict){for (const auto &w : wordDict){wordset.insert(w);lenset.insert(w.size());}vector<int> dp(s.size() + 1, 0);dp[0] = 1;for (int i = 1; i <= s.size(); ++i){for (const auto &j : lenset){if (i >= j && dp[i - j] && wordset.count(s.substr(i - j, j)))dp[i] = 1;}}if (dp.back() == 0)return res;backtrack(dp, 0, s, "");return res;}void backtrack(vector<int> &dp, int idx, string &s, string tmp){if (idx == s.size()){tmp.pop_back();res.push_back(tmp);return;}for (int i = idx + 1; i < dp.size(); ++i){if (dp[i] == 1 && wordset.count(s.substr(idx, i - idx))){backtrack(dp, i, s, tmp + s.substr(idx, i - idx) + " ");}}}
};int main()
{Solution sol1;string s = "catsanddog";vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};for (auto word:sol1.wordBreak(s, wordDict))cout << word << endl;Solution sol2;s = "pineapplepenapple";wordDict = {"apple", "pen", "applepen", "pine", "pineapple"};for (auto word:sol2.wordBreak(s, wordDict))cout << word << endl;Solution sol3;	s = "catsandog";wordDict = {"cats", "dog", "sand", "and", "cat"};for (auto word:sol3.wordBreak(s, wordDict))cout << word << endl;return 0;
} 

输出：

cats and dog
cat sand dog
pine apple pen apple
pineapple pen apple
pine applepen apple
   # 此行空

---

3. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：  s = "barfoothefoobarman",  words = ["foo","bar"]
输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：  s = "wordgoodgoodgoodbestword",  words = ["word","good","best","word"]
输出：[]

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:vector<int> findSubstring(string s, vector<string> &words){vector<int> res;if (s.empty() || words.empty()){return res;}unordered_map<string, int> ht;for (const auto &w : words){ht[w]++;}int len = words[0].length();for (int i = 0, j = 0; i < s.length() - words.size() * len + 1; i++){unordered_map<string, int> counting;for (j = 0; j < words.size(); j++){string word = s.substr(i + j * len, len);if (++counting[word] > ht[word]){break;}}if (j == words.size()){res.push_back(i);}}return res;}
};int main()
{Solution sol1;string s = "barfoothefoobarman";vector<string> words = {"foo","bar"};for (auto word:sol1.findSubstring(s, words))cout << word << " ";cout << endl; Solution sol2;s = "wordgoodgoodgoodbestword";words = {"word","good","best","word"};for (auto word:sol2.findSubstring(s, words))cout << word << " ";return 0;
} 

输出：

0 9
  //空

---