Skip to main content

分治法-巧解数学问题

241. 为运算表达式设计优先级​

class Solution {
    //分治
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        bool flag = true; //判断是否有运算符
        for (int i = 0; i < expression.size(); ++i) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*')
            {
                flag = false;
                vector<int>left = diffWaysToCompute(expression.substr(0,i));//右边
                vector<int>right =diffWaysToCompute(expression.substr(i+1));//左边边
                for (int j = 0; j < left.size(); ++j) {
                    for (int k = 0; k < right.size(); ++k) {
                        if (c=='+') res.push_back(left[j]+right[k]);
                        if (c=='-') res.push_back(left[j]-right[k]);
                        if (c=='*') res.push_back(left[j]*right[k]);
                    }
                }
            }
        }
        if (flag) return {stoi(expression)};
        return res;
    }
};


公倍数与公因数​

​ 利用辗转相除法，我们可以很方便地求得两个数的最大公因数（greatest common divisor，gcd）； 将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, lcm）。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a% b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

进一步地，我们也可以通过扩展欧几里得算法（extended gcd）在求得 a 和 b 最大公因数的同 时，也得到它们的系数 x 和 y，从而使 ax + by = gcd(a, b)。

int xGCD(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
        }
    int x1, y1, gcd = xGCD(b, a % b, x1, y1);
        x = y1, y = x1 - (a / b) * y1;
        return gcd;
    }

204. 计数质数（未完成）​

埃拉托斯特尼筛法（Sieve of Eratosthenes，简称埃氏筛法）是非常常用的，判断一个整数是 否是质数的方法。并且它可以在判断一个整数 n 时，同时判断所小于 n 的整数，因此非常适合这 道题。其原理也十分易懂：从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍 数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> isPrime(n, true); // 假设所有的都为质数
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) { // 遇到质数 + 1
                ans += 1;
                if ((long long)i * i < n) { // 剪枝操作 防止溢出
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
        }
        return ans;
    }
};

504. 七进制数​

class Solution {
public:
    string convertToBase7(int num) {
        if(num==0) return "0";
        string res;
        if (num < 0)
        {
            num = -num;
            res = "-";
        }
        while (num)
        {
            res.push_back(num % 7 + '0');
            num = num / 7;
        }

        if (res[0] != '-')std::reverse(res.begin(), res.end());
        else std::reverse(res.begin()+1, res.end());
        return res;
    }
};

168. Excel表列名称​

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string res;
        while (columnNumber > 0)
        {
            res = string(1,'A' + (columnNumber-1) % 26 )+res;
            columnNumber= (columnNumber-1) / 26;
        }
        return res;
    }
};

172. 阶乘后的零​

class Solution {
    int countfive(int n)
    {
        if (n % 5 !=0) return 0;
        return 1 + countfive(n / 5);
    }
public:
    int trailingZeroes(int n) {
        if (n < 5) return 0;
        int count = 0;
        for (int i = 5; i <=n ; i+=5) count+=countfive(i);
        return count;
    }
};

//方法二
class Solution {
public:
    int trailingZeroes(int n) {
        return n == 0? 0: n / 5 + trailingZeroes(n / 5);
    }
};

415. 字符串相加​

class Solution {
public:
    string addStrings(string num1, string num2) {
        string res;
        //对齐
        if (num1.size() > num2.size()) num2 = string(num1.size() - num2.size(),'0')+num2;
        if (num1.size() < num2.size()) num1 = string(num2.size() - num1.size(),'0')+num1;
        int n = num2.size() , fd = 0;
        while (n--)
        {

            res = string(1,((num1[n] + num2[n]  - 2 * '0' + fd) % 10)+'0') + res;
            if (num1[n] + num2[n]  - 2 * '0' + fd >= 10)  fd = 1;
            else fd = 0;
        }
        if(fd) res = "1"+ res;
        return res;
    }
};

326. 3 的幂​

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n == 0) return false;
        if(n == 1) return true;
        if(n % 3 != 0) return false;
        return isPowerOfThree(n / 3);
    }
};

随机与取样​

384. 打乱数组​

class Solution {
    vector<int> res;
public:
    Solution(vector<int>& nums) {
        res.assign(nums.begin(),nums.end());
    }

    vector<int> reset() {
        return res;
    }

    vector<int> shuffle() {
        vector<int> nums(res);
        for (int i = nums.size() - 1; i>=0 ; --i) {
            swap(nums[i],nums[rand() % (i+1)]);
        }
        return nums;
    }
};

528. 按权重随机选择​

我们可以先使用 partial_sum 求前缀和（即到每个位置为止之前所有数字的和），这个结果 对于正整数数组是单调递增的。每当需要采样时，我们可以先随机产生一个数字，然后使用二分 法查找其在前缀和中的位置，以模拟加权采样的过程。这里的二分法可以用 lower_bound 实现。 以样例为例，权重数组[1,3]的前缀和为[1,4]。如果我们随机生成的数字为1，那么 lower_bound 返回的位置为 0；如果我们随机生成的数字是 2、3、4，那么 lower_bound 返回的位置为 1。

class Solution {
    vector<int> part_sum;
public:
    Solution(vector<int>& w):part_sum(w) {
        std::partial_sum(part_sum.begin(), part_sum.end(),part_sum.begin());
    }

    int pickIndex() {
        int pos = (rand() % part_sum.back()) + 1 ;
        return lower_bound(part_sum.begin(), part_sum.end(),pos) -part_sum.begin();
    }
};

382. 链表随机节点​

不同于数组，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采 样：遍历一次链表，在遍历到第 m 个节点时，有 1 /m 的概率选择这个节点覆盖掉之前的节点选择。

class Solution {
    ListNode* head;
public:
    Solution(ListNode* head) {
        this->head = head;
    }

    int getRandom() {
        int ans = head->val;
        ListNode* node = head->next;
        int i = 2;
        while (node) {
            if ((rand() % i) == 0) {
                ans = node->val;
            }
            ++i;
            node = node->next;
        }
        return ans;
    }
};

470. 用 Rand7() 实现 Rand10()​

class Solution {
public:
    int rand10() {
        int res = 0;
        while (true)
        {
            res = (rand7()-1)*7 + rand7();//构造1~49的均匀分布
            if(res <= 40) break;//剔除大于40的值，1-40等概率出现。
        }
        return (res % 10) + 1;
    }
};

其他​

462. 最小操作次数使数组元素相等 II​

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            res+= fabs(nums[nums.size() / 2] - nums[i]);
        }
        return res;
    }
};

169. 多数元素​

摩尔投票法：核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。

从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //摩尔投票法
        //一般方法：排序取中位数，哈希表
        int count = 1 ,now = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != now) count--;
            else count++;
            if (count == 0)
            {
                now = nums[i];
                count=1;
            }

        }
        return now;
    }
};

位运算​

461. 汉明距离​

class Solution {
public:
    int hammingDistance(int x, int y) {
        int sum = 0;
        while (x || y)
        {
            sum+=(x % 2 != y % 2);
            x = x / 2;
            y = y / 2;
        }
        return sum;
    }
};

190. 颠倒二进制位​

class Solution {
public:
uint32_t reverseBits(uint32_t n) {
    uint32_t ans = 0;
    for (int i = 0; i < 32; ++i) {
        ans = ans << 1;
        ans += n % 2;
        n = n >> 1;
    }
    return ans;
}
};

136. 只出现一次的数字​

我们可以利用 x ∧ x = 0 和 x ∧ 0 = x 的特点，将数组内所有的数字进行按位异或。出现两次 的所有数字按位异或的结果是 0，0 与出现一次的数字异或可以得到这个数字本身。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            nums[i] ^= nums[i - 1];
        }
        return nums.back();
    }
};

342. 4的幂​

class Solution {
public:
    bool isPowerOfFour(int n) {
        //从左到右只有偶数位上有 1 且仅有一个1就是
        if (n < 1) return false;
        int count = 0;
        bool isyes = false;
        while (n)
        {
            if (isyes || n % 2 == 1 && count % 2 == 1) return false;
            if (count % 2 == 0 && n % 2 == 1) isyes = true;
            n = n >> 1;
            count++;
        }
        return true;
    }
};

318. 最大单词长度乘积​

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<string,int> umap;
        int maxlen = 0;
        for (int i = 0; i < words.size(); ++i) {
            int c = 0;
            for (int j = 0; j < 26; ++j) {
                c = c << 1;
                c  |= (words[i].find('a' + j) != -1);
            }
 
            umap[words[i]] = c;
            for (auto  x :umap) {
                if (!(c & x.second))
                {
                    maxlen = max(maxlen,(int)(words[i].size() * (x.first).size()));
                }
            }
        }
        return maxlen;

    }
};

338. 比特位计数​

class Solution {
    int co(int n)
    {
        int count = 0;
        while (n)
        {
            count++;
            n &= n-1;
        }
        return count;
    }
public:
    vector<int> countBits(int n) {
        vector<int> res;
        for (int i = 0; i <= n; ++i) {
            res.push_back(co(i));
        }
        return res;
    }
};

268. 丢失的数字​

好像和以前的一道题（只出现一次的数字）有异曲同工之处。看了大家的题解，异或操作（^）是一种很好的方式，不用考虑sum越界问题。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = nums.size();
        for (int i = 0; i < nums.size(); ++i) {
            res ^= nums[i] ^ i;
        }
        return res;
    }
};

693. 交替位二进制数​

class Solution {
public:
    bool hasAlternatingBits(int n) {
        bool last = n % 2;
        n = n >> 1;
        while (n)
        {
            if (!(last ^ (n % 2))) return false;
            last = n % 2;
            n = n >> 1;
            
        }
        return true;
    }
};

476. 数字的补数​

此数与其不超过他的最大1111异或就是结果

class Solution {
public:
    int findComplement(int num) {
        int temp = num, c = 0;
        while(temp > 0){
            temp >>= 1;
            c =  (c << 1) + 1;
        }
        return num ^ c;
    }
};

260. 只出现一次的数字 III​

思路, 先全部异或一次, 得到的结果, 考察其的某个非0位(比如最高非0位), 那么只出现一次的两个数中, 在这个位上一个为0, 一个为1, 由此可以将数组中的元素分成两部分,重新遍历, 求两个异或值

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int r = 0;
        for (int i = 0; i < nums.size(); ++i) {
            r ^= nums[i];
        }

        int t1 = 0 ,t2 = 0 ,ls = (r == INT_MIN ? r : r & (-r));;
        for (int i = 0; i < nums.size(); ++i) {
            if ((nums[i] & ls) != 0) t1 ^= nums[i];
            else t2 ^= nums[i];
        }
        return {t1,t2};
    }
};

1318. 或运算的最小翻转次数​

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int res = 0;
        for(int i = 0 ; i < 32; i++)
        {
            bool cbool = c % 2 , bbool = b % 2, abool = a % 2;
            c >>= 1;
            b >>= 1;
            a >>= 1;
            res += (abool || bbool) != cbool;
            res += abool && bbool && (!cbool);
        }
        return res;
    }
};