本文介绍了LeetCode中涉及的多种算法问题，如组合总和系列、回文串判断、递增子序列、全排列以及子集问题，重点讲解了递归、剪枝和去重技巧的应用。
二十五天
组合总和|||
public class Solution {
public IList<IList<int>> result = new List<IList<int>>();
public IList<int> path = new List<int>();
public IList<IList<int>> CombinationSum3(int k, int n) {
backtracking(n,k,0,1);
return result;
}
private void backtracking(int targetsum,int k,int sum,int startindex){
if (path.Count == k) {
if (sum == targetsum) result.Add(new List<int>(path));
return; // 如果path.Count == k 但sum != targetSum 直接返回
}
//剪枝版本（for(int i=startindex;i<=9-(k-path.Count)+1;i++)）道理和组合那道题一样，都
//是为了把k值后面的给删除掉
for (int i = startindex; i <= 9; i++) {
sum += i; // 处理
path.Add(i); // 处理
backtracking(targetsum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.RemoveAt(path.Count - 1); // 回溯
}
}
}电话号码的字母组合
public class Solution {
收集数字对应的字符串
private readonly string[] letterMap = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
public List<string> result = new List<string>();
public string s;
public void Backtracking(string digits, int index) {
长度相同就退出，index是记录长度
if (index == digits.Length) {
result.Add(s);
return;
}
字符转数字
int digit = digits[index] - '0';
得到的数字找对应的字符串
string letters = letterMap[digit];
for (int i = 0; i < letters.Length; i++) {
s += letters[i];
Backtracking(digits, index + 1);
s = s.Remove(s.Length - 1); 回溯
}
}
public List<string> LetterCombinations(string digits) {
s = "";
result.Clear();
if (digits.Length == 0) {
return result;
}
Backtracking(digits, 0);
return result;
}
}二十六天
组合总和
这题道理和组合、组合总和|||一样，只是没有深度限制和元素重复利用限制
public class Solution {
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
backtracking(candidates,target,0,0);
return result;
}
private void backtracking(int[] candidates,int target,int sum,int startindex)
{
if(sum > target){return ;}
if(sum == target){
result.Add(new List<int>(path));
return;
}
//for(int i=startindex;i<candidates.Length && sum+candidates[i]<=target;i++)剪枝版本
//因为只要sum比target大，后面的for循环没意义
for(int i = startindex;i < candidates.Length;i++){
sum+=candidates[i];
path.Add(candidates[i]);
backtracking(candidates,target,sum,i);
sum-=candidates[i];
path.RemoveAt(path.Count-1);
}
}
}组合总和||
要点：两个定义，树层去重（横向）、树枝去重（纵向）。这题要树层去重，纵向无所谓，题目没限制。
假如提供数组{1，2，2，3，6，9}，因为有两个元素2，为了结果不重复，得对第二次出现的元素2去重。先说明，for循环是横向循环，backtracking函数是纵向循环。贴上代码随想录的图片
这题去重主要就在数组中的每个元素贴上bool，以此做标记，能方便判断是否排除（也可以不用used数组，毕竟直接把相同元素的for循环下的分支结果剪枝。）
tips：used数组可以不用，if(i > startindex && candidates[i] == candidates[i-1])这样就行了。
public class Solution {
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
backtracking(candidates,target,0,0,new List<bool>(new bool[candidates.Length]));
return result;
}
private void backtracking(int[] candidates,int target,int sum ,int startindex,List<bool> used){
if(sum == target){
result.Add(new List<int>(path));
return;
}
for(int i=startindex;i<candidates.Length && sum + candidates[i] <=target;i++){
//这里判断的条件有：i比下标的值大，提供的数组的i元素和i-1元素值相同，used数组i-1元素等于false。
if(i > startindex && candidates[i] == candidates[i-1] && used[i-1] == false){
continue;
}
sum+=candidates[i];
path.Add(candidates[i]);
used[i] = true;
backtracking(candidates,target,sum,i+1,used);
used[i] = false;
sum-=candidates[i];
path.RemoveAt(path.Count-1);
}
}
}分割回文串
要点：回文串(例如："aa","b","acca") 。判断逻辑：双指针，一头一尾滑动。有不一样直接false，否则true。
这题主要是每次循环都要判断从startindex到for循环的i值之间的字符元素是否符合回文串。不符合，直接跳过然后递归函数backtracking（注意下标要加1，因为是纵向循环），以此类推，直到符合回文串了，加入result。之后继续递归直到for循环（横向循环）结束。
public class Solution {
private IList<IList<string>> result = new List<IList<string>>();
private IList<string> path = new List<string>();
public IList<IList<string>> Partition(string s) {
Backtracking(s,0);
return result;
}
private void Backtracking(string s, int startIndex) {
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
if (startIndex >= s.Length) {
result.Add(new List<string>(path));
return;
}
for (int i = startIndex; i < s.Length; i++) {
if (IsPalindrome(s, startIndex, i)) { // 是回文子串
// 获取[startIndex,i]在s中的子串
string str = s.Substring(startIndex, i - startIndex + 1);
path.Add(str);
} else { // 不是回文，跳过
continue;
}
Backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.RemoveAt(path.Count - 1); // 回溯过程，弹出本次已经添加的子串
}
}
private bool IsPalindrome(string s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
}二十七天
复原IP地址
要点：和分割回文串一样的思路，不过就是得加上"."和计数（"."出现次数），还有一些IP地址条件的判断，递归时startindex要加2，因为有"."。
public class Solution {
private IList<string> result = new List<string>();
public IList<string> RestoreIpAddresses(string s) {
if(s.Length < 4 || s.Length > 12){return result;}
backtracking(s,0,0);
return result;
}
private void backtracking(string s,int startindex,int pointNum){
if(pointNum==3){
if(IsVaild(s,startindex,s.Length-1)){
result.Add(s);
}
return;
}
for(int i=startindex;i<s.Length;i++){
if(IsVaild(s,startindex,i)){
s = s.Insert(i+1,".");
pointNum++;
backtracking(s,i+2,pointNum);
pointNum--;
s = s.Remove(i+1,1);
}else break;
}
}
private bool IsVaild(string s,int start,int end){
if(start > end){return false;}
if(s[start] == '0' && start != end){return false;}
int num = 0;
for(int i = start;i<=end;i++){
if(s[i] > '9' || s[i] < '0'){
return false;
}
num = num*10+(s[i]-'0');
if(num > 255){return false;}
}
return true;
}
}子集
要点：子集问题，就是收集树形结构的所有节点结果，不用考虑剪枝，把每一个结果加到result就是了
public class Solution {
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
public IList<IList<int>> Subsets(int[] nums) {
backtracking(nums,0);
return result;
}
private void backtracking(int[] nums,int startindex){
result.Add(new List<int>(path));
if(startindex >= nums.Length){return;}
for(int i=startindex;i<nums.Length;i++){
path.Add(nums[i]);
backtracking(nums,i+1);
path.RemoveAt(path.Count-1);
}
}
}子集||
思路：其实就是在原有子集问题上加个组合问题||中的剪枝条件（if(i>startindex && nums[i] == nums[i-1])）就解决了。
public class Solution {
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
backtracking(nums,0);
return result;
}
private void backtracking(int[] nums,int startindex){
result.Add(new List<int>(path));
if(startindex >= nums.Length){return;}
for(int i=startindex;i<nums.Length;i++){
if(i>startindex && nums[i] == nums[i-1]){
continue;
}
path.Add(nums[i]);
backtracking(nums,i+1);
path.RemoveAt(path.Count-1);
}
}
}二十八天
递增子序列
要点：这题不用考虑到排序，题目已经提供递增序列了。其他的和子集||相似，只有递归逻辑不同，题目说了可以重复，但是只能由前向后，不能后面的元素找到前面一样的元素，然后就是记录方式，可以字典或者直接数组记录，题目已经提供的范围在[-100,100]之间，所以创建新二维数组201。
说明一下判断压入条件if(path.Count > 0 && nums[i] < path[path.Count-1] || used[nums[i]+100] == 1)，path是有压入元素的；nums[i]<path[path.Count-1]，保证是递增的序列；used[nums[i]+100] == 1，验证之前收集的元素是否存在。具备则continue，不具备则能添加进序列。
public class Solution {
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
public IList<IList<int>> FindSubsequences(int[] nums) {
backtracking(nums,0);
return result;
}
private void backtracking(int[] nums,int startindex){
if(path.Count > 1){
result.Add(new List<int>(path));
}
int[] used = new int[201];
for(int i=startindex;i<nums.Length;i++){
if(path.Count > 0 && nums[i] < path[path.Count-1] || used[nums[i]+100] == 1){continue;}
used[nums[i] + 100] = 1;
path.Add(nums[i]);
backtracking(nums,i+1);
path.RemoveAt(path.Count-1);
}
}
}全排列
要点：这里的全排列，是把所有的排列组合收集，例如{1，2，3}，结果是[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]，但是要求集合里的元素不重复。
所以，这次单层逻辑就不能用startindex去标记了，因为每一次收集都要重头到尾遍历收集，然后加个bool数组给nums数组做标记哪个被用到，用到的跳过，没有就收集。
public class Solution {
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
public IList<IList<int>> Permute(int[] nums) {
bool[] used = new bool[nums.Length];
backtracking(nums,used);
return result;
}
private void backtracking(int[] nums,bool[] used){
if(path.Count == nums.Length){
result.Add(new List<int>(path));
return;
}
for(int i=0;i<nums.Length;i++){
if(used[i]==true){continue;}
used[i] = true;
path.Add(nums[i]);
backtracking(nums,used);
path.RemoveAt(path.Count-1);
used[i] = false;
}
}
}全排列||
要点：在排列问题上多加上组合总和中的去重逻辑就行
public class Solution {
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
public IList<IList<int>> PermuteUnique(int[] nums) {
Array.Sort(nums);
bool[] used = new bool[nums.Length];
backtracking(nums,used);
return result;
}
private void backtracking(int[] nums,bool[] used){
if(path.Count == nums.Length){
result.Add(new List<int>(path));
return;
}
for(int i=0;i<nums.Length;i++){
//去重
if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}
if(used[i] == false){
used[i] = true;
path.Add(nums[i]);
backtracking(nums,used);
path.RemoveAt(path.Count-1);
used[i] = false;
}
}
}
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
