给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
这个题我们使用的是递归,再写一个backgoing函数去递归,每次更改总和,小于target继续递归,等于时退出递归。
class Solution { public: vector> combinationSum(vector & candidates, int target) { vector >res; vector tmp; sort(candidates.begin(),candidates.end()); backgoing(res,candidates,tmp,target,0,0); return res; } void backgoing(vector >&res,vector &candidates,vector &tmp,int target,int begin,int sum) { if(sum==target) { res.push_back(tmp);//等于时,把当前用于统计的tmp插入res } else { for(int i=begin;i 2.最长回文子串(力扣第五题): 给你一个字符串 s,找到 s 中最长的回文子串。
这个题我一看到时候就是暴力解法,两层for循环,遍历区间起始位置和终止位置,然后判断这个区间是不是回文。
但是这个题也是经典的动态规划题,一些回文串,公共子序列,递增子序列这些都是动态规划问题。
1.首先动态规划问题要先知道dp代表什么,本体bp为布尔类型的dp[i][j]:表示区间范围[i,j] 的子串是否是回文子串,如果是dp[i][j]为true,否则为false。
2.整体上是两种,就是s[i]与s[j]相等,s[i]与s[j]不相等这两种。
当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。
当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况
情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
情况二:下标i 与 j相差为1,例如aa,也是文子串
情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看 i 到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j- 1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
3.回文子串可能是从字符串s中截取,所以要确定边界。
class Solution { public: string longestPalindrome(string s) { vector>dp(s.size(),(vector (s.size(),0))); int maxl=0; int left=0,right=0; for(int i=s.size()-1;i>=0;i--) { for(int j=i;j maxl)//确定边界 { maxl=j-i+1; left=i; right=j; } } } return s.substr(left,right-left+1); } };