当前位置 : 首页 » 文章分类 :  开发  »  LeetCode.728.Self Dividing Numbers

LeetCode.728.Self Dividing Numbers


题目描述

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.

Example 1:

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.

解题过程

找出可以被所有位数整除的整数。
用顺序搜索的话,是很简单的一道数学题,但就怕超过时间限制,但也没想到什么优化的搜索方法,试着顺序搜索写了一个,一提交就AC了。
处理的时候得注意下中间位数有0的情况,有可能出现模为0的错误。

package _728_SelfDividingNumbers;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i=left; i<=right; i++){
            //System.out.println(i);
            int remain = i;
            int mod = i % 10;
            if(mod==0)//直接跳过10的倍数
                continue;
            while(i % mod == 0){
                remain = remain / 10;
                if(remain % 10 == 0){//remain为0或10的倍数时停止
                    break;
                }else {
                    mod = remain % 10;
                }
            }
            if(remain==0) {//所有位数都能整除i
                arrayList.add(i);
            }
        }
        return arrayList;
    }
}

public class SelfDividingNumbers {
    public static void main(String[] args){
        Solution solution = new Solution();
        List<Integer> list = solution.selfDividingNumbers(100, 1000);
        System.out.println(list);
    }
}

AC后看了看,基本都是顺序搜索,没啥新颖的方法。
最快的3ms代码如下,直接把所有可能的解提前算出来存好,然后根据要求组合成结果,奇葩,但也是一种思路

class Solution {
  private static int[] DividingNumbers = {1,2,3,4,5,6,7,8,9,11,12,15,22,24,33,36,44,48,55,66,77,88,99,111,112,115,122,124,126,128,132,135,144,155,162,168,175,184,212,216,222,224,244,248,264,288,312,315,324,333,336,366,384,396,412,424,432,444,448,488,515,555,612,624,636,648,666,672,728,735,777,784,816,824,848,864,888,936,999,1111,1112,1113,1115,1116,1122,1124,1128,1131,1144,1155,1164,1176,1184,1197,1212,1222,1224,1236,1244,1248,1266,1288,1296,1311,1326,1332,1335,1344,1362,1368,1395,1412,1416,1424,1444,1448,1464,1488,1515,1555,1575,1626,1632,1644,1662,1692,1715,1722,1764,1771,1824,1848,1888,1926,1935,1944,1962,2112,2122,2124,2128,2136,2144,2166,2184,2196,2212,2222,2224,2226,2232,2244,2248,2262,2288,2316,2322,2328,2364,2412,2424,2436,2444,2448,2488,2616,2622,2664,2688,2744,2772,2824,2832,2848,2888,2916,3111,3126,3132,3135,3144,3162,3168,3171,3195,3216,3222,3264,3276,3288,3312,3315,3324,3333,3336,3339,3366,3384,3393,3432,3444,3492,3555,3612,3624,3636,3648,3666,3717,3816,3864,3888,3915,3924,3933,3996,4112,4116,4124,4128,4144,4164,4172,4184,4212,4224,4236,4244,4248,4288,4332,4344,4368,4392,4412,4416,4424,4444,4448,4464,4488,4632,4644,4824,4848,4872,4888,4896,4932,4968,5115,5155,5355,5515,5535,5555,5775,6126,6132,6144,6162,6168,6192,6216,6222,6264,6288,6312,6324,6336,6366,6384,6432,6444,6612,6624,6636,6648,6666,6696,6762,6816,6864,6888,6912,6966,6984,7112,7119,7175,7224,7266,7371,7448,7476,7644,7728,7777,7784,8112,8128,8136,8144,8184,8224,8232,8248,8288,8328,8424,8448,8488,8496,8616,8664,8688,8736,8824,8832,8848,8888,8928,9126,9135,9144,9162,9216,9288,9315,9324,9333,9396,9432,9612,9648,9666,9864,9936,9999};

    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list = new ArrayList<>();

        for(int i=0; i<DividingNumbers.length; i++) {
            int num = DividingNumbers[i];
            if(num >= left && num <= right)
                list.add(num);
            if(num > right)
                break;
        }

        return list;
    }

}

GitHub代码


上一篇 LeetCode.561.Array Partition I

下一篇 LeetCode.537.Complex Number Multiplication

阅读
807
阅读预计4分钟
创建日期 2018-01-10
修改日期 2018-01-11
类别
百度推荐