0803学习

agile Posted on Aug 4 2023

面试排列组合回溯 leetcode学习

-   全排列-46-腾讯
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

---

```C#
private int[] __nums;
private List<IList<int>> __result;

public IList<IList<int>> Permute(int[] nums)
{
    __nums = nums;
    __result = new List<IList<int>>();
    __Help(0);
    return __result;
}

private void __Help(int index)
{
    if (index == __nums.Length - 1)
    {
        __result.Add(__nums.ToList());
        return;
    }

for (int i = index; i < __nums.Length; i++)
    {
        (__nums[i], __nums[index]) = (__nums[index], __nums[i]);
        __Help(index + 1);
        (__nums[i], __nums[index]) = (__nums[index], __nums[i]);
    }
}
```

---

回溯
```C#
private int[] __nums;
private List<IList<int>> __result;

public IList<IList<int>> Permute(int[] nums)
{
    __nums = nums;
    __result = new List<IList<int>>();
    var cache = new List<int>();
    __Help(0, cache);
    return __result;
}

private void __Help(int index, List<int> cache)
{
    if (index == __nums.Length)
    {
        __result.Add(new List<int>(cache));
        return;
    }

foreach (var t in __nums)
    {
        if (cache.Contains(t))
        {
            continue;
        }

cache.Add(t);
        __Help(index + 1, cache);
        cache.Remove(t);
    }
}
```

---

-   全排列 II-47
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
 
---

```C#
private int[] __nums;
private IList<IList<int>> __result;
private bool[] __visited;

public IList<IList<int>> PermuteUnique(int[] nums)
{
    Array.Sort(nums);
    __nums = nums;
    __result = new List<IList<int>>();
    __visited = new bool[__nums.Length];
    __Help(0, new List<int>());
    return __result;
}

private void __Help(int index, List<int> cache)
{
    if (index == __nums.Length)
    {
        __result.Add(new List<int>(cache));
        return;
    }

for (int i = 0; i < __nums.Length; i++)
    {
        if (__visited[i] || i > 0 && __nums[i] == __nums[i - 1] && !__visited[i - 1])
        {
            continue;
        }

__visited[i] = true;
        cache.Add(__nums[i]);
        var count = cache.Count;
        __Help(index + 1, cache);
        __visited[i] = false;
        cache.RemoveAt(count - 1);
    }
}
```

---

-  组合总和-39
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

---

```C#
private int[] __candidates;
private int __target;
private IList<IList<int>> __result;
private int __maxIndex;

public IList<IList<int>> CombinationSum(int[] candidates, int target)
{
    Array.Sort(candidates);
    __candidates = candidates;
    __target = target;
    __result = new List<IList<int>>();
    var min = __candidates[0];
    __maxIndex = __target / min;

__Help(0, 0, 0, new List<int>());

return __result;
}

private void __Help(int begin, int sum, int index, List<int> cache)
{
    if (sum == __target)
    {
        __result.Add(new List<int>(cache));
        return;
    }

if (index > __maxIndex)
    {
        return;
    }

for (var i = begin; i < __candidates.Length; i++)
    {
        var c = __candidates[i];
        if (sum + c > __target)
        {
            return;
        }

cache.Add(c);
        //这个i很妙
        __Help(i, sum + c, index + 1, cache);
        cache.Remove(c);
    }
}
```

---

-  组合总和 II-40
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。 
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

---

```C#
private int[] __candidates;
private int __target;
private bool[] __visited;
private IList<IList<int>> __result;

public IList<IList<int>> CombinationSum2(int[] candidates, int target)
{
    Array.Sort(candidates);
    __candidates = candidates;
    __target = target;
    __visited = new bool[__candidates.Length];
    __result = new List<IList<int>>();
    __Help(0, 0, new List<int>());
    return __result;
}

private void __Help(int sum, int index, List<int> cache)
{
    if (sum == __target)
    {
        __result.Add(new List<int>(cache));
        return;
    }

if (index == __candidates.Length)
    {
        return;
    }

for (var i = index; i < __candidates.Length; i++)
    {
        var temp = __candidates[i];
        if (__visited[i] || (i > index && temp == __candidates[i - 1] && !__visited[i - 1]))
        {
            continue;
        }

if (sum + temp > __target)
        {
            return;
        }

__visited[i] = true;
        cache.Add(temp);
        var count = cache.Count;
        __Help(sum + temp, i + 1, cache);
        __visited[i] = false;
        cache.RemoveAt(count - 1);
    }
}
```

---

-   组合-77
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

---

```C#
private int __n;
private int __k;
private IList<IList<int>> __result;

public IList<IList<int>> Combine(int n, int k)
{
    __n = n;
    __k = k;
    __result = new List<IList<int>>();
    __Help(new List<int>(), 1);
    return __result;
}

private void __Help(List<int> cache, int index)
{
    if (__k == cache.Count)
    {
        __result.Add(new List<int>(cache));
        return;
    }

//如果当前cache的数量不能组成目标数量，直接返回
    if (cache.Count + __n - index + 1 < __k)
    {
        return;
    }

for (var i = index; i <= __n; i++)
    {
        cache.Add(i);
        __Help(cache, i + 1);
        cache.Remove(i);
    }
}
```

---

-   子集-78
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

---

```C#
private int[] __nums;
private IList<IList<int>> __result;

public IList<IList<int>> Subsets(int[] nums)
{
    __nums = nums;
    __result = new List<IList<int>>();
    __Help(0, new List<int>());
    return __result;
}

private void __Help(int index, List<int> cache)
{
    __result.Add(new List<int>(cache));
    if (__nums.Length == index)
    {
        return;
    }

for (var i = index; i < __nums.Length; i++)
    {
        var temp = __nums[i];
        cache.Add(temp);
        __Help(i + 1, cache);
        cache.Remove(temp);
    }
}
```
---

-   子集 II-90
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

---

```C#
private int[] __nums;
private IList<IList<int>> __result;

public IList<IList<int>> SubsetsWithDup(int[] nums)
{
    Array.Sort(nums);
    __nums = nums;
    __result = new List<IList<int>>();
    __Help(0, new List<int>());
    return __result;
}

private void __Help(int index, List<int> cache)
{
    __result.Add(new List<int>(cache));
    if (index == __nums.Length)
    {
        return;
    }

for (int i = index; i < __nums.Length; i++)
    {
        var temp = __nums[i];
        if (i > index && temp == __nums[i - 1])
        {
            continue;
        }

cache.Add(temp);
        var count = cache.Count;
        __Help(i + 1, cache);
        cache.RemoveAt(count - 1);
    }
}
```

---

-   复原 IP 地址-93
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20
s 仅由数字组成

---

```C#
private string __s;
private IList<string> __result;

public IList<string> RestoreIpAddresses(string s)
{
    __result = new List<string>();
    if (s.Length is > 12 or < 4)
    {
        return __result;
    }

__s = s;
    __Help(0, new List<int>());
    return __result;
}

private void __Help(int index, List<int> cache)
{
    if (cache.Count == 4)
    {
        if (index == __s.Length)
        {
            __result.Add(string.Join('.', cache));
        }

return;
    }

var lastNum = 4 - cache.Count;
    var lastLength = __s.Length - index;
    //当剩下的长度大于最大组成数字的长度 或者最小组成数字大长度大于剩下大长度 都需要return
    if (lastNum * 3 < lastLength || lastNum > lastLength)
    {
        return;
    }

var num = 0;
    for (var i = 0; i + index < __s.Length && i < 3; i++)
    {
        var temp = __s[i + index] - '0';
        num = num * 10 + temp;
        if (num > 255)
        {
            return;
        }

//1,01,0,23==>01有问题
        // 大于 1 位的时候，不能以 0 开头
        if (i > 0 && __s[index] == '0')
        {
            return;
        }
        
        //最后一组的情况，一定要求i+index = __s.length-1
        if (cache.Count == 3 && i + index < __s.Length - 1)
        {
            continue;
        }

cache.Add(num);
        var count = cache.Count;
        __Help(i + index + 1, cache);
        cache.RemoveAt(count - 1);
    }
}
```

---

-   排列序列
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3
输出："213"
示例 2：
输入：n = 4, k = 9
输出："2314"
示例 3：
输入：n = 3, k = 1
输出："123"
提示：
1 <= n <= 9
1 <= k <= n!

---

```C#
private int __n;
private int __k;
private string __result = "";
private int __num;

public string GetPermutation(int n, int k)
{
    __n = n;
    __k = k;
    __Help(new List<int>());
    return __result;
}

private void __Help(List<int> cache)
{
    if (cache.Count == __n)
    {
        __num++;
        if (__num == __k)
            __result = string.Join("", cache);
        return;
    }

for (var i = 1; i <= __n; i++)
    {
        if (__result != "")
        {
            return;
        }

if (cache.Contains(i))
        {
            continue;
        }

cache.Add(i);
        __Help(cache);
        cache.Remove(i);
    }
}
```

---

![20230803-061826-1.jpg](https://tools.nxcloud.club:12500/images/2023/08/03/20230803-061826-1.jpg)
![20230803-061930-1.jpg](https://tools.nxcloud.club:12500/images/2023/08/03/20230803-061930-1.jpg)

---

```C#
private int[] __factorial;
private List<int> __nums;

public string GetPermutation2(int n, int k)
{
    __n = n;
    __k = k;
    __factorial = new int[n + 1];
    __nums = new List<int>();
    __InitFactorial();

var sb = new StringBuilder();
    while (__nums.Count > 0)
    {
        var m = __nums.Count;
        // 把还剩的数构成的全排列分为 m 组，每组分别以不同的数开头
        var index = __k / __factorial[m - 1];
        // 根据余数判断落在哪一组
        if (__k % __factorial[m - 1] == 0)
        {
            index -= 1;
        }

sb.Append(__nums[index]);
        __nums.RemoveAt(index);
        __k -= index * __factorial[m - 1];
    }

return sb.ToString();
}

private void __InitFactorial()
{
    __factorial[0] = 1;
    for (int i = 1; i <= __n; i++)
    {
        __factorial[i] = i * __factorial[i - 1];
        __nums.Add(i);
    }
}
```
---
- 字母大小写全排列-784
给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1：
输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
示例 2:
输入: s = "3z4"
输出: ["3z4","3Z4"]
提示:
1 <= s.length <= 12
s 由小写英文字母、大写英文字母和数字组成

---

```C#
private IList<string> __result;
private string __s;

public IList<string> LetterCasePermutation(string s)
{
    __s = s;
    __result = new List<string>();
    __Help(0, new StringBuilder());
    return __result;
}

private void __Help(int index, StringBuilder cache)
{
    if (index == __s.Length)
    {
        __result.Add(cache.ToString());
        return;
    }

---

-   电话号码的字母组合-17
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
[![200px-telephone-keypad2svg.png](https://tools.nxcloud.club:12500/images/2023/08/03/200px-telephone-keypad2svg.png)](https://tools.nxcloud.club:12500/image/0qtZ)
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

---

```C#
private Dictionary<char, List<char>> __dictionary;
private string __digits;
private IList<string> __result;

public IList<string> LetterCombinations(string digits)
{
    __result = new List<string>();
    if (digits.Length <= 0)
    {
        return __result;
    }

__digits = digits;
    __dictionary = new Dictionary<char, List<char>>();
    var first = 'a';
    for (var i = '2'; i <= '9'; i++)
    {
        __dictionary[i] = new List<char>();
        var num = i is '7' or '9' ? 4 : 3;
        for (var j = 0; j < num; j++)
        {
            __dictionary[i].Add(first);
            first++;
        }
    }

__Help(0, new StringBuilder());
    return __result;
}

private void __Help(int index, StringBuilder cache)
{
    if (index == __digits.Length)
    {
        __result.Add(cache.ToString());
        return;
    }

var c = __digits[index];
    if (!__dictionary.TryGetValue(c, out var data)) return;
    foreach (var c1 in data)
    {
        cache.Append(c1);
        var count = cache.Length;
        __Help(index + 1, cache);
        cache.Remove(count - 1, 1);
    }
}
```
---

-   括号生成-22
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8

---

```C#
private IList<string> __result;
private int __n;

public IList<string> GenerateParenthesis(int n)
{
    __n = n;
    __result = new List<string>();
    __Help(0, 0, new StringBuilder());
    return __result;
}

private void __Help(int left, int right, StringBuilder cache)
{
    if (right > left || left > __n)
    {
        return;
    }

if (cache.Length == __n * 2)
    {
        //if (left == right)
        //{
            __result.Add(cache.ToString());
        //}

return;
    }

for (var i = 0; i < 2; i++)
    {
        char c;
        var l = left;
        var r = right;
        if (i == 0)
        {
            l++;
            c = '(';
        }
        else
        {
            r++;
            c = ')';
        }

cache.Append(c);

__Help(l, r, cache);
        cache.Remove(cache.Length - 1, 1);
    }
}
```
---

题型一：排列、组合、子集相关问题
提示：这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法。

-   全排列（中等）46
-   全排列 II（中等）：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；47
-   组合总和（中等）39
-   组合总和 II（中等）40
-   组合（中等）77
-   子集（中等）78
-   子集 II（中等）：剪枝技巧同 47 题、39 题、40 题；90
-   第 k 个排列（中等）：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；60
-   复原 IP 地址（中等）93

---

题型二：Flood Fill
提示：Flood 是「洪水」的意思，Flood Fill 直译是「泛洪填充」的意思，体现了洪水能够从一点开始，迅速填满当前位置附近的地势低的区域。类似的应用还有：PS 软件中的「点一下把这一片区域的颜色都替换掉」，扫雷游戏「点一下打开一大片没有雷的区域」。

下面这几个问题，思想不难，但是初学的时候代码很不容易写对，并且也很难调试。我们的建议是多写几遍，忘记了就再写一次，参考规范的编写实现（设置 visited 数组，设置方向数组，抽取私有方法），把代码写对。

-   图像渲染（Flood Fill，中等）733
-   岛屿数量（中等）200
-   被围绕的区域（中等）130
-   单词搜索（中等）79
说明：以上问题都不建议修改输入数据，设置 visited 数组是标准的做法。可能会遇到参数很多，是不是都可以写成成员变量的问题，面试中拿不准的记得问一下面试官

---

题型三：字符串中的回溯问题
提示：字符串的问题的特殊之处在于，字符串的拼接生成新对象，因此在这一类问题上没有显示「回溯」的过程，但是如果使用 StringBuilder 拼接字符串就另当别论。 在这里把它们单独作为一个题型，是希望朋友们能够注意到这个非常细节的地方。

-   电话号码的字母组合（中等），题解；17
-   字母大小写全排列（中等）；784
-   括号生成（中等）：这道题广度优先遍历也很好写，可以通过这个问题理解一下为什么回溯算法都是深度优先遍历，并且都用递归来写。 22

---

题型四：游戏问题
回溯算法是早期简单的人工智能，有些教程把回溯叫做暴力搜索，但回溯没有那么暴力，回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题，解决它们有一定的难度，大家可以尝试一下。

-   N 皇后（困难）：其实就是全排列问题，注意设计清楚状态变量，在遍历的时候需要记住一些信息，空间换时间；51
-   解数独（困难）：思路同「N 皇后问题」；37
-   祖玛游戏（困难）488
-   扫雷游戏（困难）529

---