970. Powerful Integers 平方数

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0. Return a list of all powerful integers that have value less than or equal to bound. You may return the answer in any order. In your answer, each value should occur at most once.

第一次解法

思路：事先将 x 和 y 小于 bound 的平方数都事先算好，然后迭代哈希查表，将等式移项，用和依次减去 x 的平方数，然后拿结果去查 y 的表

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vector<int> res;
        if (bound < 2) {
            return res;
        }
        res.push_back(2);
        
        if (bound < x || bound <y) {
            return res;
        }
        
        vector<int> xs;
        xs.push_back(1);
        if (x > 1) {
          int p = x;
          while(p<bound) {
            xs.push_back(p);
            p*=x;
          }
        }

        
        set<int> ys;
        ys.insert(1);
        if (y > 1) {
            int p = y;
            while(p<bound) {
                ys.insert(p);
                p*=y;
            }
        }

        
        for(int b=3;b<=bound;b++) {
            for(int j=0;j<xs.size();j++) {
                if (xs[j] >= b) {
                    break;
                }
                
                if (ys.find(b-xs[j]) != ys.end()) {
                    res.push_back(b);
                    break;
                }
            }
        }
        return res;
    }
};

更好的解法，暴力枚举

因为答案需要直接返回平方和的值的集合，应该直接枚举次方而不是和，相比于一开始的解法减少了大量的计算量

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> s;
        for (int i = 1; i < bound; i *= x) {
            for (int j = 1; i + j <= bound; j *= y) {
                s.insert(i + j);
		// y 是 1 只需要枚举一次就可以换下一个 x
                if (y == 1) break;
            }
	    //  x 是 1 也只需要枚举完一遍 y 即可退出循环
            if (x == 1) break;
        }
        return vector<int>(s.begin(), s.end());
    }
};

收获

暴力枚举的对象中，要挑那些小的来枚举，可以大大减少解空间，使用 c++ 的 HashSet unordered_set 的好处是可以进行 O(1) 的插入，就避免了 vector 的扩容复制带来的性能损耗

#暴力 #HashSet

96. Unique Binary Search Trees 971. Flip Binary Tree To Match Preorder Traversal