C#LeetCode刷题之#728-自除数(Self Dividing Numbers)

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)

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3889

发表评论

登录后才能评论