分类： 算法

304. 二维区域和检索 – 矩阵不可变

public class NumMatrix
{
    readonly int[,] arr;
    public NumMatrix(int[][] matrix)
    {
        var rows = matrix?.Length ?? 0;
        var cols = rows == 0 ? 0 : (matrix.First()?.Length ?? 0);
        arr = new int[rows + 1, cols + 1];
        for (var i = 0; i < rows; i++)
            for (var j = 0; j < cols; j++)
                arr[i + 1, j + 1] = matrix[i][j] + arr[i, j + 1] + arr[i + 1, j] - arr[i, j];
    }
    public int SumRegion(int row1, int col1, int row2, int col2)
    {
        row1++; col1++;
        row2++; col2++;
        return arr[row2, col2] - arr[row1 - 1, col2] - arr[row2, col1 - 1] + arr[row1 - 1, col1 - 1];
    }
}

303. 区域和检索 – 数组不可变

public class NumArray {
    readonly int[] sum;
    public NumArray(int[] nums)
    {
        if (nums != null)
        {
            sum = new int[nums.Length];
            if (nums.Length > 0)
                sum[0] = nums[0];
            for (var i = 1; i < sum.Length; i++)
                sum[i] += sum[i - 1] + nums[i];
        }
    }
    public int SumRange(int i, int j) => sum[j] - (i == 0 ? 0 : sum[i - 1]);
}

896. 单调数列

public class Solution {
    public bool IsMonotonic(int[] A) {
        if (A.Length > 1)
        {
            var cmp = 0;
            for (var i = 1; i < A.Length; i++)
            {
                var nextCmp = A[i - 1].CompareTo(A[i]);
                if ((cmp ^ nextCmp) == -2)
                    return false;
                cmp = cmp == 0 ? nextCmp : cmp;
            }
        }
        return true;
    }
}

1178. 猜字谜

继续阅读[力扣] 算法 1178 (C#)

12. 整数转罗马数字

继续阅读[力扣] 算法 12 (C#)

1175. 质数排列

public class Solution {
    const int MOD = 1_000_000_007;
    public int NumPrimeArrangements(int n)
    {
        var cnt = PrimeCount(n);
        var f = Factorial(Math.Max(cnt, n - cnt));
        return (int)(f[cnt] * f[n - cnt] % MOD);
    }

    int PrimeCount(int n)
    {
        var ba = new BitArray(n + 1);
        var ret = 0;
        for (var i = 2; i <= n; i++)
        {
            if (!ba[i])
            {
                ret++;
                for (var j = 2 * i; j <= n; j += i)
                    ba[j] = true;
            }
        }
        return ret;
    }

    long[] Factorial(int max)
    {
        var ret = new long[max + 1];
        ret[0] = 1;
        for (var i = 1; i < ret.Length; i++)
            ret[i] = ret[i - 1] * i % MOD;
        return ret;
    }
}

867. 转置矩阵

public class Solution
{
    public int[][] Transpose(int[][] matrix)
    {
        var rows = matrix.Length;
        var cols = matrix[0].Length;
        var ret = new int[cols][];
        for (var i = 0; i < cols; i++)
        {
            ret[i] = new int[rows];
            for (var j = 0; j < rows; j++)
                ret[i][j] = matrix[j][i];
        }
        return ret;
    }
}

832. 翻转图像

public class Solution
{
    public int[][] FlipAndInvertImage(int[][] A)
    {
        for (var i = 0; i < A.Length; i++)
        {
            var left = 0;
            var right = A[0].Length - 1;
            while(left < right)
            {
                if ((A[i][left] ^ A[i][right]) == 0)
                {
                    A[i][left] ^= 1;
                    A[i][right] ^= 1;
                }
                left++;
                right--;
            }
        }
        if (A[0].Length % 2 == 1)
        {
            var mid = A[0].Length / 2;
            for (var i = 0; i < A.Length; i++)
            {
                A[i][mid] ^= 1;
            }
        }
        return A;
    }
}

1431. 拥有最多糖果的孩子

public class Solution {
    public IList<bool> KidsWithCandies(int[] candies, int extraCandies) {
        var max = candies[0];
        foreach (var candy in candies.AsSpan(1))
            if (candy > max) max = candy;
        var ret = new bool[candies.Length];
        for(var i = 0; i < candies.Length; i++)
            ret[i] = candies[i] + extraCandies >= max;
        return ret;
    }
}

1758. 生成交替二进制字符串的最少操作数

public class Solution {
    public int MinOperations(string s) {
        var (turn0, turn1) = (0, 0);
        (s[0] == '1' ? ref turn0 : ref turn1) = 1;
        foreach (var ch in s.AsSpan(1))
        {
            (turn0, turn1) = (turn1, turn0);
            (ch == '1' ? ref turn0 : ref turn1)++;
        }
        return Math.Min(turn0, turn1);
    }
}