C#.NET 算法题 高级篇

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

查看代码

public bool IsMatch(string s, string p)
{
    if (string.IsNullOrEmpty(p)) return string.IsNullOrEmpty(s);
    bool firstMatch = !string.IsNullOrEmpty(s) && (s[0] == p[0] || p[0] == '.');
    if (p.Length >= 2 && p[1] == '*')
    {
        return IsMatch(s, p.Substring(2)) || (firstMatch && IsMatch(s.Substring(1), p));
    }
    else
    {
        return firstMatch && IsMatch(s.Substring(1), p.Substring(1));
    }
}

解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

• 1、数字  1-9  在每一行只能出现一次。
• 2、数字  1-9  在每一列只能出现一次。
• 3、数字  1-9  在每一个以粗实线分隔的  3x3  宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用  '.'  表示。

查看代码

char[][] board = new char[9][]
{
    new char[9] { '5', '3', '.', '.', '7', '.', '.', '.', '.' },
    new char[9] { '6', '.', '.', '1', '9', '5', '.', '.', '.' },
    new char[9] { '.', '9', '8', '.', '.', '.', '.', '6', '.' },
    new char[9] { '8', '.', '.', '.', '6', '.', '.', '.', '3' },
    new char[9] { '4', '.', '.', '8', '.', '3', '.', '.', '1' },
    new char[9] { '7', '.', '.', '.', '2', '.', '.', '.', '6' },
    new char[9] { '.', '6', '.', '.', '.', '.', '2', '8', '.' },
    new char[9] { '.', '.', '.', '4', '1', '9', '.', '.', '5' },
    new char[9] { '.', '.', '.', '.', '8', '.', '.', '7', '9' }
};

if (SolveSudoku(board))
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
            Console.Write(board[i][j] + " ");
        Console.WriteLine();
    }
}

Console.ReadKey();

bool SolveSudoku(char[][] board)
{
    if (board == null || board.Length == 0) return false;
    Solve(board);
    return true;
}

bool Solve(char[][] board)
{
    for (int i = 0; i < board.Length; i++)
    {
        for (int j = 0; j < board[0].Length; j++)
        {
            if (board[i][j] == '.')
            {
                for (char c = '1'; c <= '9'; c++)
                {
                    if (IsValid(board, i, j, c))
                    {
                        board[i][j] = c;
                        if (Solve(board))
                        {
                            return true;
                        }
                        else
                        {
                            board[i][j] = '.';
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}

bool IsValid(char[][] board, int row, int col, char c)
{
    for (int i = 0; i < 9; i++)
    {
        if (board[i][col] != '.' && board[i][col] == c) return false;
        if (board[row][i] != '.' && board[row][i] == c) return false;
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
    }
    return true;
}