970-強(qiáng)整數(shù)

Rindia 發(fā)布于2019-08-16 14:11 / 653人閱讀

摘要：前言的強(qiáng)整數(shù)給定兩個(gè)非負(fù)整數(shù)和，如果某一整數(shù)等于，其中整數(shù)且，那么我們認(rèn)為該整數(shù)是一個(gè)強(qiáng)整數(shù)。返回值小于或等于的所有強(qiáng)整數(shù)組成的列表。

前言

Weekly Contest 118的強(qiáng)整數(shù)：

給定兩個(gè)非負(fù)整數(shù) x 和 y，如果某一整數(shù)等于 x^i + y^j，其中整數(shù) i >= 0 且 j >= 0，那么我們認(rèn)為該整數(shù)是一個(gè)強(qiáng)整數(shù)。
返回值小于或等于 bound 的所有強(qiáng)整數(shù)組成的列表。
你可以按任何順序返回答案。在你的回答中，每個(gè)值最多出現(xiàn)一次。
示例1：
輸入：x = 2, y = 3, bound = 10
輸出：[2,3,4,5,7,9,10]
解釋： 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2
示例2：
輸入：x = 3, y = 5, bound = 15
輸出：[2,4,6,8,10,14]
提示：

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

解題思路

本題只需要找出正整數(shù)中滿足x^i + y^j且<=bound的數(shù)即可，所以只需要用兩重for循環(huán)找出滿足條件的數(shù)字即可。

注意事項(xiàng)：

循環(huán)中會(huì)出現(xiàn)重復(fù)的值，例如

輸入：x = 2, y = 3, bound = 10
輸出：[2,3,4,5,7,9,10]
解釋： 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
5 = 2^2 + 3^0
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

其中重復(fù)的情況為

5 = 2^1 + 3^1
5 = 2^2 + 3^0

可以選擇先使用Set進(jìn)行結(jié)果去重

執(zhí)行超時(shí)的情況，例如輸入：x = 1, y = 3, bound = 100。所以可以選擇循環(huán)次數(shù)為bound(x^bound>bound恒成立)，而不是Integer.MAX_VALUE。

實(shí)現(xiàn)代碼

    /**
     * 970. 強(qiáng)整數(shù)
     * @param x
     * @param y
     * @param bound
     * @return
     */
    public List powerfulIntegers(int x, int y, int bound) {
        //選擇使用Set是因?yàn)榻Y(jié)果中會(huì)出現(xiàn)重復(fù)值
        Set set = new HashSet<>();
        //循環(huán)次數(shù)為bound，而不是Integer.MAX_VALUE，防止執(zhí)行超時(shí)
        for (int i = 0; i < bound; i++) {
            int tmp1 = (int) Math.pow(x, i);
            //如果第一個(gè)數(shù)就大于bound，直接中斷循環(huán)，防止執(zhí)行超時(shí)
            if (tmp1 > bound) {
                break;
            }
            //循環(huán)次數(shù)為bound，而不是Integer.MAX_VALUE，防止執(zhí)行超時(shí)
            for (int j = 0; j < bound; j++) {
                int tmp2 = (int) (Math.pow(y, j));
                int tmp = tmp1 + tmp2;
                //判斷是否超出bound
                if (tmp <= bound) {
                    set.add(tmp);
                } else {//超出bound直接中斷循環(huán)，因?yàn)楹罄m(xù)的數(shù)字都會(huì)超出bound
                    break;
                }
            }
        }