C#LeetCode刷题之#728-自除数（Self Dividing Numbers）

问题

自除数是指可以被它包含的每一位数除尽的数。

例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

还有，自除数不允许包含 0 。

给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。

输入： 上边界left = 1, 下边界right = 22

输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

注意：每个输入参数的边界满足 1 <= left <= right <= 10000。

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Input: left = 1, right = 22

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:The boundaries of each input argument are 1 <= left <= right <= 10000.

示例

public class Program {

    public static void Main(string[] args) {

        var left = 1;

        var right = 21;

        var res = SelfDividingNumbers(left, right);

        ShowArray(res);

        left = 3;

        right = 36;

        res = SelfDividingNumbers2(left, right);

        ShowArray(res);

        Console.ReadKey();

    }

    private static void ShowArray(IList<int> array) {

        foreach(var num in array) {

            Console.Write($"{num} ");

        }

        Console.WriteLine();

    }

    private static IList<int> SelfDividingNumbers(int left, int right) {

        var res = new List<int>();

        for(var i = left; i <= right; i++) {

            if(IsSelfDividingNumber(i)) res.Add(i);

        }

        return res;

    }

    private static bool IsSelfDividingNumber(int num) {

        //用字符串索引取位

        var length = num.ToString().Length;

        for(var i = 0; i < length; i++) {

            var bit = int.Parse(num.ToString()[length - i - 1].ToString());

            if(bit == 0 || num % bit != 0) return false;

        }

        return true;

    }

    private static IList<int> SelfDividingNumbers2(int left, int right) {

        var res = new List<int>();

        for(var i = left; i <= right; i++) {

            if(IsSelfDividingNumber2(i)) res.Add(i);

        }

        return res;

    }

    private static bool IsSelfDividingNumber2(int num) {

        //用传统取余式取位

        var number = num;

        while(number > 0) {

            var bit = number % 10;

            if(bit == 0 || num % bit != 0) return false;

            number /= 10;

        }

        return true;

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

1 2 3 4 5 6 7 8 9 11 12 15

3 4 5 6 7 8 9 11 12 15 22 24 33 36

分析：

显而易见，以上2种算法的时间复杂度均为： $O(n)$ 。

巴特西

C#LeetCode刷题之#728-自除数（Self Dividing Numbers）

最新文章

热门文章