題目描述 LeetCode 728

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.

中文描述

• 給出 left,right, 然后在 1 <= left <= right <= 10000. 這個范圍內(nèi)，找到 self dividing number。
• self dividing number：
  • 這個數(shù)能被這個數(shù)包含的其他位整除，如數(shù) 128，能有128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0 。
  • 再有就是該數(shù)各個位不能包含 0，如 10，102，105，500，507 ，所有數(shù)值位只要有一位為0，則不是 self dividing number 。

解題思路

• 兩層 for 循環(huán)，第一層，從 left 到 right，讀出各個數(shù)。
• 調(diào)用 DividingNumber 子函數(shù)，將該數(shù)的 各個位存入 temp 臨時數(shù)組中，并將尺寸存入 size。
• 第二層 for 循環(huán)，循環(huán)讀出該 temp 中的每個數(shù)字（即該數(shù)的各個位），用該數(shù)對各個位取模，如果該位為 0，則什么也不做，如果不為0，就取?？纯词欠駷?，用flag判別標志，如果 flag == size，則證明，該數(shù)取模自己的各個數(shù)值位均為 0，即為 self dividing number 。如果 flag != size，則證明，該數(shù)取模自己的各個數(shù)值位有不為 0，又或者數(shù)值位有 0 的存在，即該數(shù)為 self dividing number 。

C語言代碼

# include <stdio.h>

// 將一個數(shù)值各位存入數(shù)組 a 中，如 128，將 8, 2, 1分別存入 a[0], a[1], a[2] 中
void DividingNumber(int k, int a[], int *size)
{
    int i = 0;

    while(k > 9)
    {
        a[i++] = k%10;
        k = k / 10;
    }
    a[i] = k;
    *size = i + 1;
}

// 主要實現(xiàn)的子函數(shù)
int* selfDividingNumbers(int left, int right, int* returnSize) 
{
    // 注意這里必須加 static，因為，最終返回的是 a 的首地址，如果不加static，a數(shù)組將會作為臨時變量，
    // 執(zhí)行完這個函數(shù)，a馬上就會清除內(nèi)存，加上static，就為全局變量，等程序完全執(zhí)行完，a才會消失。
    static int a[10000];
    int temp[4];
    int i, j;
    int size = 0;
    int flag = 0;

    for(i = left; i <= right; i ++)
    {
        DividingNumber(i, temp, &size);
        flag = 0;
        for (j = 0; j < size; j ++)
        {
            if ( temp[j] == 0) 
            {
                
            }
            else
            {
                if (i % temp[j] == 0)
                {
                    flag ++;
                }
            }
        }

        if(flag == size)
        {
            a[(*returnSize) ++] = i;
        }
    }

    return a;
}

main()
{   
    int *a;
    int size = 0;
    int i = 0;

    a = selfDividingNumbers(1, 22, &size);
    for (i = 0; i < size; i ++)
    {
        printf("%d ", *(a + i));
    }
    printf("\n\n");

/*  用于測試 DividingNumber 子函數(shù)的正確性
    int a[4];
    int size;
    int i;

    DividingNumber(128, a, &size);
    for (i = 0; i < size; i ++)
    {
        printf("%d -> %d \n", i, *(a + i));
    }
*/

}

運行結(jié)果

思考

• 查看討論區(qū)，沒看到用 C 的優(yōu)秀答案，用 java 的比較多
• runtime 打敗 59.16% ，結(jié)果差強人意。