首页 > 代码库 > LeetCode: Combinations [077]
LeetCode: Combinations [077]
【题目】
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
【题意】
给定数字n和k, 返回所有由1,2,3...,n数组成k元组合【思路】
递归
【代码】
class Solution { public: void dfs(vector<vector<int> >&result, vector<int>combination, int kth, int k, int curVal, int n){ // combination 已经生成的前kth-1个数 // kth 本次将要生成组合中的第kth个数 // k 组合规模 // curVal 本次将加入组合中的数,即第kth个数 // n 候选数的总规模 combination.push_back(curVal); if(kth==k)result.push_back(combination); else{ for(int val=curVal+1; val+(k-kth-1)<=n; val++){ dfs(result, combination, kth+1, k, val, n); } } } vector<vector<int> > combine(int n, int k) { vector<vector<int> >result; if(k>n || n<0 || k<1)return result; vector<int> combination; for(int val=1; val<=n-(k-1); val++){ dfs(result, combination, 1, k, val, n); } return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。