分类： 算法

9. 回文数

public class Solution {
    public bool IsPalindrome(int x) {
        if (x < 0)
            return false;
        var y = x;
        var z = 0L;
        while (x != 0)
        {
            z *= 10;
            z += x % 10;
            x /= 10;
        }
        return y == z;
    }
}

1052. 爱生气的书店老板

public class Solution {
    public int MaxSatisfied(int[] customers, int[] grumpy, int X) {
        var ret = 0;
        for (var i = 0; i < customers.Length; i++)
            if (grumpy[i] == 0)
                ret += customers[i];
        var sum = 0;
        for (var i = 0; i < X; i++)
            if (grumpy[i] == 1)
                sum += customers[i];
        var max = sum;
        for (var i = X; i < customers.Length; i++)
        {
            if (grumpy[i - X] == 1)
                sum -= customers[i - X];
            if (grumpy[i] == 1)
                sum += customers[i];
            if (sum > max)
                max = sum;
        }
        return ret + max;
    }
}

766. 托普利茨矩阵

public class Solution {
    public bool IsToeplitzMatrix(int[][] matrix) {
        for (var i = 1; i < matrix.Length; i++)
            for(var j = 1; j < matrix[i].Length; j++)
                if (matrix[i][j] != matrix[i - 1][j - 1])
                    return false;
        return true;
    }
}

374. 猜数字大小

public class Solution : GuessGame {
    public int GuessNumber(int right) {
        var left = 1;
        while (left < right)
        {
            int mid = (int)(((long)left + right) / 2);
            var ret = guess(mid);
            if (ret == 0) return mid;
            if (ret < 0) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
}

1004. 最大连续1的个数 III

public class Solution {
    public int LongestOnes(int[] A, int K) {
        int max = 0;
        int zero = 0;
        int from = 0, to = 0;
        while (to < A.Length)
        {
            if (A[to] == 0)
            {
                zero++;
                while (zero > K)
                {
                    if (A[from] == 0)
                    {
                        zero--;
                    }
                    from++;
                }
            }
            to++;
            if (to - from > max)
            {
                max = to - from;
            }
        }
        return max;
    }
}

796. 旋转字符串

public class Solution {
    public bool RotateString(string A, string B)
        => A.Length == B.Length && (A + A).Contains(B);
}

367. 有效的完全平方数

public class Solution {
    public bool IsPerfectSquare(int num) {
        var min = 1;
        var max = 46340;
        while (min < max)
        {
            var mid = (min + max) / 2;
            if (num == mid * mid)
                return true;
            if (num > mid * mid)
                min = mid + 1;
            else
                max = mid - 1;
        }
        return num == min * max;
    }
}

1456. 定长子串中元音的最大数目

public class Solution {
    public int MaxVowels(string s, int k)
    {
        var cnts = new Counts();
        foreach (var ch in s.AsSpan(0, k)) cnts.Add(ch);
        var max = cnts.vowel;
        for(var i = k; max < k && i < s.Length; i++)
        {
            cnts.Remove(s[i - k]);
            cnts.Add(s[i]);
            if (cnts.vowel > max) max = cnts.vowel;
        }
        return max;
    }

    class Counts
    {
        public int vowel;
        HashSet<char> set = new HashSet<char>() { 'a', 'e', 'i', 'o', 'u' };
        public void Add(char c)
        {
            if (set.Contains(c))
                vowel++;
        }
        public void Remove(char c)
        {
            if (set.Contains(c))
                vowel--;
        }
    }
}

393. UTF-8 编码验证

public class Solution
{
    public bool ValidUtf8(int[] data)
    {
        var itor = new IntArrItor(data);
        while (itor.MoveNext())
        {
            var type = Foo(itor);
            if (type < 0) return false;
            for (var i = 0; i < type; i++)
                if (!itor.MoveNext() || (itor >> 6 ^ 0b10) != 0) return false;
        }
        return true;
    }

    static int Foo(int num)
    {
        if ((num >> 3 ^ 0b11110) == 0) return 3;
        if ((num >> 4 ^ 0b1110) == 0) return 2;
        if ((num >> 5 ^ 0b110) == 0) return 1;
        if ((num >> 7 ^ 0b0) == 0) return 0;
        return -1;
    }

    class IntArrItor : IEnumerator<int>
    {
        int[] arr;
        int curr = -1;
        public IntArrItor(int[] arr) => this.arr = arr;

        public int Current => arr[curr];

        object IEnumerator.Current => Current;

        public void Dispose() { }

        public bool MoveNext() => ++curr < arr.Length;

        public void Reset() => curr = -1;
        public static implicit operator int(IntArrItor itor) => itor.Current;
    }
}

566. 重塑矩阵

public class Solution {
    public int[][] MatrixReshape(int[][] nums, int r, int c) {
        if (nums.Length * nums[0].Length != r * c) return nums;
        var ret = new int[r][];
        for (var i = 0; i < r; i++)
            ret[i] = new int[c];
        for (int i = 0, m = 0, n = 0; i < nums.Length; i++)
            for (var j = 0; j < nums[0].Length; j++, n++, m += n / c, n %= c)
                ret[m][n] = nums[i][j];
        return ret;
    }
}