分类： 计算机语言

263. 丑数

Plan A

public class Solution
{
    public bool IsUgly(int n)
    {
        if (n == 0)
            return false;
        if (n == 1)
            return true;
        if ((n % 2) == 0)
            return IsUgly(n / 2);
        if ((n % 3) == 0)
            return IsUgly(n / 3);
        if ((n % 5) == 0)
            return IsUgly(n / 5);
        return false;
    }
}

Plan B，易扩展

public class Solution
{
    public bool IsUgly(int n)
    {
        if (n == 0)// 这道题也可以判断 n < 1
            return false;
        Bar(ref n, 2, 3, 5);
        return n == 1;
    }

    void Foo(ref int n, int a)
    {
        while ((n % a) == 0)
            n /= a;
    }

    void Bar(ref int n, params int[] @as)
    {
        foreach (var a in @as)
            Foo(ref n, a);
    }
}

1047. 删除字符串中的所有相邻重复项

Plan A (这会超时是我万万没有想到的)

public class Solution
{
    public string RemoveDuplicates(string S)
    {
        var deque = new LinkedList<char>();
        foreach(var ch in S)
        {
            if(deque.Count > 0)
            {
                if (deque.Last() == ch) { 
                    deque.RemoveLast();
                    continue;
                }
            }
            deque.AddLast(ch);
        }
        return string.Concat(deque);
    }
}

Plan B

public class Solution
{
    public string RemoveDuplicates(string S)
    {
        var chs = new char[S.Length];
        var leng = 0;
        foreach(var ch in S)
        {
            if (leng > 0 && chs[leng - 1] == ch)
                leng--;
            else
                chs[leng++] = ch;
        }
        return new string(chs, 0, leng);
    }
}

132. 分割回文串 II

public class Solution
{
    public int MinCut(string s)
    {
        if (s.Length == 0)
            return 0;
        var part = new bool[s.Length, s.Length];
        part[0, 0] = true;
        for (var i = 1; i < s.Length; i++)
            part[i, i] = part[i, i - 1] = true;
        for (var i = 1; i < s.Length; i++)
            for (var j = 0; j < s.Length - i; j++)
                part[j, i + j] = part[j + 1, i + j - 1] && s[j] == s[i + j];

        // 这一段原本我是用131的的Foo()改的，结果超时了。按官方的解法写了如下代码
        var f = new int[s.Length];
        Array.Fill(f, s.Length);
        for (var i = 0; i < s.Length; i++)
            if (part[0, i])
                f[i] = 0;
            else
                for (var j = 0; j < i; j++)
                    if (part[j + 1, i])
                        f[i] = Math.Min(f[i], f[j] + 1);
        return f[^1];
    }
}

131. 分割回文串

public class Solution
{
    public IList<IList<string>> Partition(string s)
    {
        if (s.Length == 0)
            return new List<IList<string>>();
        var part = new bool[s.Length, s.Length];
        part[0, 0] = true;
        for (var i = 1; i < s.Length; i++)
            part[i, i] = part[i, i - 1] = true;
        for (var i = 1; i < s.Length; i++)
            for (var j = 0; j < s.Length - i; j++)
                part[j, i + j] = part[j + 1, i + j - 1] && s[j] == s[i + j];
        var ret = new List<IList<string>>();
        var temp = new List<string>(s.Length);
        Foo(ret, temp, 0, part, s);
        return ret;
    }

    void Foo(List<IList<string>> ret, IList<string> temp, int index, bool[,] part, string s)
    {
        if (index == s.Length)
        {
            ret.Add(new List<string>(temp));
        }
        else
        {
            for (var i = index; i < s.Length; i++)
            {
                if (!part[index, i])
                    continue;
                temp.Add(s[index..(i + 1)]);
                Foo(ret, temp, i + 1, part, s);
                temp.RemoveAt(temp.Count - 1);
            }
        }
    }
}

503. 下一个更大元素 II

public class Solution {
    const int NON_EXIST = -1;
    public int[] NextGreaterElements(int[] nums)
    {
        if (nums?.Length == 0)
            return Array.Empty<int>();
        if (nums.Length == 1)
            return new int[] { NON_EXIST };
        var ret = new int[nums.Length];
        Array.Fill(ret, NON_EXIST);
        for (var i = ret.Length - 2; i >= 0; i--)
        {
            if (nums[i] < nums[i + 1])
            {
                ret[i] = i + 1;
            }
            else
            {
                var curr = i + 1;
                while (ret[curr] != NON_EXIST)
                {
                    curr = ret[curr];
                    if (nums[i] < nums[curr])
                    {
                        ret[i] = curr;
                        break;
                    }
                }
            }
        }
        for(var i = ret.Length - 1; i >= 0; i--)
        {
            if (ret[i] != NON_EXIST)
                continue;
            var next = (i + 1) % ret.Length;
            while (next != NON_EXIST)
            {
                if(nums[i] < nums[next])
                {
                    ret[i] = next;
                    break;
                }
                next = ret[next];
            }
        }
        for (var i = 0; i < ret.Length; i++)
            if (ret[i] != NON_EXIST)
                ret[i] = nums[ret[i]];
        return ret;
    }
}

// 没想到用单调栈

1296. 划分数组为连续数字的集合

public class Solution
{
    public bool IsPossibleDivide(int[] nums, int k)
    {
        if (k > 1)
        {
            var map = new SortedDictionary<int, int>();
            foreach (var num in nums)
                if (map.ContainsKey(num))
                    map[num]++;
                else
                    map[num] = 1;
            while(map.Count > 0)
            {
                var (key,value) = map.First();
                for(var i = 0; i < k; i++)
                {
                    if (!map.ContainsKey(key + i) || (map[key + i] -= value) < 0)
                        return false;
                    if (map[key + i] == 0)
                        map.Remove(key + i);
                }
            }
        }
        return true;
    }
}

232. 用栈实现队列

public class MyQueue
{
    Stack<int> front = new Stack<int>();
    Stack<int> back = new Stack<int>();
    public MyQueue() { }
    public void Push(int x) => front.Push(x);
    public int Pop()
    {
        TryFront2Back();
        return back.Pop();
    }
    public int Peek()
    {
        TryFront2Back();
        return back.Peek();
    }
    void TryFront2Back()
    {
        if (back.Count == 0)
            while (front.Count > 0)
                back.Push(front.Pop());
    }
    public bool Empty() => front.Count + back.Count == 0;
}

338. 比特位计数

public class Solution
{
    public int[] CountBits(int num)
    {
        var ret = new int[num + 1];
        for (var i = 1; i < ret.Length; i++)
            ret[i] = ret[i >> 1] + (i & 1);
        return ret;
    }
}

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]);
}