0719学习

agile Posted on Jul 19 2023

面试 leetcode学习

-   输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]限制：
1 <= s 的长度 <= 8

---

而全排列刚好可以使用试探的方法去枚举所有中可能性。一个长度为n的序列或者集合。它的所有排列组合的可能性共有n！种。具体的试探策略如下：

从待选集合中选取第一个元素(共有n种情况)，并标记该元素已经被使用不能再使用。
在步骤1的基础上进行递归到下一层，从剩余n-1个元素中按照1的方法找到一个元素并标记，继续向下递归。
当所有元素被标记后，顺序收集被标记的元素存储到结果中，当前层递归结束，回到上一层(同时将当前层标记的元素清除标记)。这样一直执行到最后。

---

回溯剪枝法 因为回溯完整的比直接递归慢，所以刚开始并没有考虑使用回溯算法，但是这里用回溯剪枝相比递归邻里互换方法更好一些，对于不使用哈希去重的方法，首先进行排序预处理是没有悬念的，而回溯法去重的关键就是避免相同的数字因为相对次序问题造成重复，所以在这里相同数字在使用上相对位置必须不变，而具体剪枝条的规则如下：

先对序列进行排序
试探性将数据放到当前位置
如果当前位置数字已经被使用，那么不可使用
如果当前数字和前一个相等但是前一个没有被使用，那么当前不能使用，需要使用前一个数字。

---

邻里互换的方法虽然是也是递归实现的，但是他是一种基于交换的策略和思路。而理解起来也是非常简单，邻里互换的思路是从左向右进行考虑。

因为序列是没有重复的，我们开始将数组分成两个部分：暂时确定部分和未确定部分。开始的时候均是未确定部分，我们需要妥善处理的就是未确定部分。在未确定部分的序列中，我们需要让后面未确定的每一位都有机会处在未确定的首位，所以未确定部分的第一个元素就要和每一个依次进行交换(包括自己)，交换完成之后再向下进行递归求解其他的可能性，求解完毕之后要交换回来(还原)再和后面的进行交换。这样当递归进行到最后一层的时候就将数组的值添加到结果集中。如果不理解可以参考下图进行理解：

---

![68747470733a2f2f6269677361692e6f73732d636e2d7368616e676861692e616c6979756e63732e636f6d2f696d672f696d6167652d32303231303132383230303232363136342e706e67.png](https://tools.nxcloud.club:12500/images/2023/07/19/68747470733a2f2f6269677361692e6f73732d636e2d7368616e676861692e616c6979756e63732e636f6d2f696d672f696d6167652d32303231303132383230303232363136342e706e67.png)

---

```C#
private List<string> _list = new List<string>();
private HashSet<string> _hashList = new HashSet<string>();
private bool[] _visited;

public string[] Permutation(string s)
{
    var chars = s.ToCharArray();
    Array.Sort(chars);
    _visited = new bool[chars.Length];
    __Help(chars, 0, new StringBuilder());
    return _list.ToArray();
}

private void __Help(char[] chars, int index, StringBuilder sb)
{
    if (index == chars.Length)
    {
        _list.Add(sb.ToString());
        return;
    }

for (var i = 0; i < chars.Length; i++)
    {
        if (_visited[i] || i > 0 && chars[i] == chars[i - 1] && !_visited[i - 1])
        {
            continue;
        }

_visited[i] = true;
        sb.Append(chars[i]);
        var length = sb.Length;
        __Help(chars, index + 1, sb);
        _visited[i] = false;
        sb.Remove(length - 1, 1);
    }
}

public string[] Permutation2(string s)
{
    var chars = s.ToCharArray();
    _hashList.Clear();
    __Help2(chars, 0);
    return _hashList.ToArray();
}

private void __Help2(char[] chars, int start)
{
    if (start == chars.Length - 1)
    {
        _hashList.Add(new string(chars));
        return;
    }

for (int i = start; i < chars.Length; i++)
    {
      
        __Swap(chars, i, start);
        __Help2(chars, start + 1);
        __Swap(chars, start, i);
    }
}

private void __Swap(char[] chars, int i, int j)
{
    (chars[i], chars[j]) = (chars[j], chars[i]);
}
```

---

-   剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

---

![WX20230719-1758132x.png](https://tools.nxcloud.club:12500/images/2023/07/19/WX20230719-1758132x.png)

---

```C#
public bool IsMatch(string s, string p)
{
    var m = s.Length + 1;
    var n = p.Length + 1;
    var dp = new bool[m][];
    for (var i = 0; i < m; i++)
    {
        dp[i] = new bool[n];
    }

dp[0][0] = true;
    for (int i = 2; i < n; i += 2)
    {
        dp[0][i] = dp[0][i - 2] && p[i - 1] == '*';
    }

for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (p[j - 1] == '*')
            {
                if (j < 2) continue;
                if (dp[i][j - 2]) //前i-1个字符匹配j-3个字符，此时就不需要看j-2字符，只需要j-1字符为*,因为可以为0，去除j-2字符
                {
                    dp[i][j] = true;
                }
                else if (dp[i - 1][j - 1]) //当前i-2字符，匹配j-2字符
                {
                    if (s[i - 1] == p[j - 2]) //此时只需要保证s[i-1]字符和p[j-2]字符相等 因为p[j-1]=*
                    {
                        dp[i][j] = true;
                    }
                    else if (p[j - 2] == '.') //也可以让p[j-2]字符为任意字符
                    {
                        dp[i][j] = true;
                    }
                }
            } //当p第j-1字符为 *时候
            else
            {
                if (dp[i - 1][j - 1]) //s 中前i-2字符 和p前j-2个字符匹配
                {
                    if (s[i - 1] == p[j - 1]) //
                    {
                        dp[i][j] = true;
                    }
                    else if (p[j - 1] == '.')
                    {
                        dp[i][j] = true;
                    }
                }
            }
        }
    }

return dp[m - 1][n - 1];
}
```

---