前言
前文传送门:
C# 刷遍 Leetcode 面试题系列连载(1) - 入门与工具简介
C#刷遍Leetcode面试题系列连载(2): No.38 - 报数
上篇文章中我们分析了一个递归描述的字符串问题,今天我们来分析一个数学问题,一道除法相关的面试题。
今天要给大家分析的面试题是 LeetCode 上第 728 号问题,
LeetCode - 728. 自除数
https://leetcode-cn.com/problems/self-dividing-numbers/
自除数 是指可以被它包含的每一位数除尽的数。
例如,128 是一个自除数,因为 128%1==0
, 128%2==0
, 128%8==0
。
还有,自除数不允许包含 0 。
给定上边界和下边界数字,输出一个列表,列表的元素是边界(含边界)内所有的自除数。
示例 1:
输入:
上边界left = 1, 下边界right = 22
输出: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
注意:
1<=left<=right<=10000
。70.20%
相关话题
相似题目
解题思路:
已 AC
的代码为:
public class Solution
{
public IList<int> SelfDividingNumbers(int left, int right)
{
List<int> list = new List<int>();
for (int i = left; i <= right; ++i)
{
if (isSelfDiv(i))
list.Add(i);
}
return list;
}
bool isSelfDiv(int n)
{
if (n < 10)
return true;
if (n % 10 == 0)
return false;
int t = n;
while (t != 0)
{
int rem = t % 10;
if (rem == 0)
return false;
if (rem > 1 && n % rem != 0) // 原数不是末位数字倍数的数需要排除
return false;
t /= 10;
}
return true;
}
}
运行结果:
执行用时: 244ms
, 在所有 csharp 提交中击败了 100.00%
的用户
相应的,如需测试,本地可执行的代码为:
using System;
using System.Collections.Generic;
namespace leetcode728
{
public class Solution
{
public IList<int> SelfDividingNumbers(int left, int right)
{
List<int> list = new List<int>();
for (int i = left; i <= right; ++i)
{
if (isSelfDiv(i))
list.Add(i);
}
return list;
}
bool isSelfDiv(int n)
{
if (n < 10)
return true;
if (n % 10 == 0)
return false;
int t = n;
while (t != 0)
{
int rem = t % 10;
if (rem == 0)
return false;
if (rem > 1 && n % rem != 0) // 原数不是末位数字倍数的数需要排除
return false;
t /= 10;
}
return true;
}
static void Main(string[] args)
{
var sol = new Solution();
var res = sol.SelfDividingNumbers(5, 50);
foreach (var item in res)
Console.WriteLine(item);
}
}
}
相应代码已经上传到github:
https://github.com/yanglr/Leetcode-CSharp/tree/master/leetcode728
End
作者简介:Bravo Yeung,计算机硕士,知乎干货答主(获81K 赞同, 37K 感谢, 234K 收藏)。曾在国内 Top3互联网视频直播公司短暂工作过,后加入一家外企做软件开发至今。