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种算法的时间复杂度均为： 。