LeetCode学习-第二十九天
2022/2/3 23:44:36
本文主要是介绍LeetCode学习-第二十九天,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第二十九天
我使用的C++,错误的地方请见谅,文章初衷仅用来督促本人学习,如果恰巧能够给你带来帮助,我会十分开心。
文章目录
- 第二十九天
- 一、39. 组合总和
- 二、40. 组合总和 II
- 三、17. 电话号码的字母组合
一、39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { public: vector<vector<int>> ans; vector<int> stk; void dfs (vector<int>& candidates, int cur, int target){ if (cur == candidates.size()){ return; } if (target == 0){ ans.push_back(stk); return; } dfs(candidates, cur + 1, target);//不选择 if (target - candidates[cur] >= 0){//判断选择 stk.push_back(candidates[cur]); dfs(candidates, cur, target - candidates[cur]); stk.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { //和之前排列组合一样,每个数都有选与不选两种选择,选取的数做和与target做比较 //sort(candidates.begin(), candidates.end()); //stk.resize(candidates.size()); dfs(candidates, 0, target); return ans; } };
二、40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { public: vector<vector<int>> ans; vector<pair<int, int>> freq;//hash来记录键值与个数 vector<int> stk; void dfs (int cur, int target){ if (target == 0){ ans.push_back(stk); return; } if (cur == freq.size() || target < freq[cur].first){ return; } dfs(cur + 1, target);//不选取 int most = min(target / freq[cur].first, freq[cur].second);//这一步来取出个数,因为要具有一般性,所以加了min,很值得学习 for (int i = 1; i <= most; ++i){ stk.push_back(freq[cur].first);//多个相同的数一次性操作 dfs(cur + 1, target - i * freq[cur].first); } for (int i = 1; i <= most; ++i){ stk.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { //这里每一个数字智能用一次,这一题里有很多值得学习的地方 sort(candidates.begin(), candidates.end()); for (int num : candidates){ if (freq.empty() || num != freq.back().first){ freq.emplace_back(num, 1); } else { ++freq.back().second; } } dfs(0, target); return ans; } };
三、17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { public: vector<string> ans; string stk; vector<string> letterCombinations(string digits) { if (digits.empty()){ return ans; } unordered_map <char, string> Map = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; back(0, Map, digits); return ans; } void back (int cur, const unordered_map<char, string>& Map, string& digits){ if (cur == digits.size()){ ans.push_back(stk); return; } else { char digit = digits[cur]; const string& letters = Map.at(digit); for (auto letter : letters){ stk.push_back(letter); back(cur + 1, Map, digits); stk.pop_back(); } } } };
要注意数组和字符串的递归变量的定义
这篇关于LeetCode学习-第二十九天的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升