10-数学问题

分治法-巧解数学问题

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;
    }
};

剑指 Offer 51. 数组中的逆序对

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> all(nums.size());
        //归并排序交换次数
        function<int(int,int)> func = [&](int start,int end)
        {
            if(start >= end - 1) return 0;
            int mid = (start + end) / 2;
            int res = func(start,mid) + func(mid,end);

            //两个有序数组的合并
            int l = start, r = mid , cnt = start;
            //拷贝
            for (int k = start; k < end; k++)
                all[k] = nums[k];

            while(l < mid && r < end)
            {
                if(all[l] <= all[r]) nums[cnt++] = all[l++];
                else{
                    nums[cnt++] = all[r++];
                    res +=  mid - l;
                }
            }
            while(l < mid) nums[cnt++] = all[l++];
            while(r < end) nums[cnt++] = all[r++];
            return res;
        };
        return func(0,nums.size());;
    }
};

395. 至少有 K 个重复字符的最长子串***

class Solution {
public:
    int longestSubstring(string s, int k) {
        //分治法
        if(k == 1) return s.size();
        if(k > s.size()) return 0;
        int nums[26] = {0};
        for(char x : s)  nums[x - 'a']++;
        int pre = 0;
        int res = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(nums[s[i] - 'a'] < k)
            {
                if(pre < s.size() && i - pre > 0)
                {
                    string r = s.substr(pre,i - pre);
                    res = max(longestSubstring(r,  k) , res);
                }
                pre = i + 1;
            }
        }
        if(pre != 0 && pre < s.size()&& nums[s.back() - 'a'] >= k) 
        {
            res = max(longestSubstring(s.substr(pre),  k) , res);
        }

        return pre == 0 ?  s.size() : res;
    }
};

836. 矩形重叠

class Solution {
    /*
    二维矩阵的重叠判断可以看成两个一维线段重叠的判断，因此我们可以将矩形投影到坐标轴上，进行线段重叠判断。

假设有两个线段分别为[a, b]和[c, d]，则两个线段重叠的充要条件为：a < b && c < d && b > c && d > a。

时间复杂度分析： 两个判断，因此时间复杂度为O(1)。*/

public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        return check(rec1[0], rec1[2], rec2[0], rec2[2]) &&
               check(rec1[1], rec1[3], rec2[1], rec2[3]); 
    }
    bool check(int a, int b, int c, int d){
        return a < b && c < d && b > c && d > a;
    }
};

223. 矩形面积

class Solution {
    /*
        面积相交，投影到线段 ， 计算线段交集
    */
    int check(int a, int b, int c, int d){
        //计算投影之后的线段相交的长度
        if(a < b && c < d && b > c && d > a) return min({b - c,d - a,b - a,d - c});
        return 0;
    }
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        return (ax2 - ax1) * (ay2 - ay1) +(bx2 - bx1) * (by2 - by1) - check(ax1,ax2,bx1,bx2) * check(ay1,ay2,by1,by2);
    }
};

公倍数与公因数

利用辗转相除法，我们可以很方便地求得两个数的最大公因数（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);
    }
};

365. 水壶问题

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        //求 ax + by = z ，a，b有无整数解
        if (x + y < z) {
            return false;
        }
        if (x == 0 || y == 0) {
            return z == 0 || x + y == z;
        }
        return z % gcd(x, y) == 0; //gcd是求x，y最大公因数
    }
};

随机与取样

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;
    }
};

我们可以先使用 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;
    }
};

剑指 Offer 14- II. 剪绳子 II

class Solution {
public:
    int cuttingRope(int n) {
        if(n < 4) return n - 1;
        const int MOD = 1e9+7;
        int res = 1;
        while(n > 4)
        {
            res = ((long long)res * 3) % MOD;
            n -= 3;
        }
        return ((long long)res * n) % MOD;
    }
};

剑指 Offer 44. 数字序列中某一位的数字

class Solution {
public:
    int findNthDigit(int n) {
        if(n < 10) return n;
        long long size = 1 , count = 10;
        while(count < n)
        {
            size++;
            count += size * 9 * pow(10,size - 1);
        }
        int num = pow(10,size - 1);
        count = n -  count + size * 9 * pow(10,size - 1); //偏移量
        num += count / size;
        // num 从左到右的第 count % size 位数
        string s = to_string(num);
        return s[(int)count % size] - '0';
    }
};

60. 排列序列

class Solution {
public:
    string getPermutation(int n, int k) {
        //计算阶乘
        int fac[10] = {0};
        fac[0] = 1;
        for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;

        string res;
        string s = string("123456789").substr(0,n);
        k--;

        while(k > 0)
        {
            int i = k / fac[n - 1];
            res.push_back(s[i]);
            s.erase(s.begin() + i);
            k = k % fac[n - 1];
            n--;
        }
        return res + s;
    }
};

781. 森林中的兔子

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        int res = 0;
        unordered_map<int,int> umap;
        for(int i :answers) umap[i]++;
        for(auto x: umap)
        {
            if(x.first != 0)
            {
                int p = (x.second / (x.first + 1) +  (x.second % (x.first + 1) != 0));
                res += (x.first + 1) * p;
            }
            else res += x.second;
        }
        return res;
    }
};

位运算

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, 由此可以将数组中的元素分成两部分,重新遍历, 求两个异或值

如果一个数与自身的负数相与可以得到最低位的1的位置的数，然后其余位补0：

比如有这么一个二进制数10001011，然后让他与自身负数相与，得到的结果是00000001；

再比如1001010，与自身负数相与后的结果是0000010；

r & (-r) 是一个位运算的操作，表示将 r 的二进制表示取反然后加一，然后与 r 进行按位与操作。

例如，假设 r = 5，它的二进制表示为 0101，则 -r = -5 的补码表示为 1011。进行按位与操作，即 0101 & 1011 = 0001，结果为 1。

这种操作对于找出一个整数的最低非零位（即最右边的 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;
    }
};

1356. 根据数字二进制下 1 的数目排序

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        function<int (int)> cnt = [&](int n)
        {
            int cnts = 0;
            while(n)
            {
                n = n & (n - 1);
                cnts++;
            }
            return cnts;
        };
        sort(arr.begin(),arr.end(),[&](const int &a, const int &b){
            int ca = cnt(a);
            int cb = cnt(b);
            if(ca == cb) return a < b;
            return ca < cb;
        });
        return arr;
    }
};

剑指 Offer 65. 不用加减乘除做加法

class Solution {
public:
    int add(int a, int b) {
        while(b != 0)
        {
            unsigned int c = (unsigned int)(a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c;
        }
        return a;
    }
};

面试题 16.01. 交换数字

class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        //异或
        numbers[0] = numbers[0] ^ numbers[1];
        numbers[1] = numbers[0] ^ numbers[1];
        numbers[0] = numbers[0] ^ numbers[1];
        return numbers;
    }
};

89. 格雷编码

class Solution {
public:
/*找规律的题，0，1开始，后面的00，01， 11，10，每往前多一位数字，后面部分和前k个反序
0,1
00,01,11,10
000 001 011 010 110 111 101 100 
等等
*/
    vector<int> grayCode(int n) {
        int k = 1;
        vector<int> res(pow(2,n),0);
        res[1] = 1;
        while(k < n)
        {
            //便利前后pow(2,k)次方元素
            for(int i = pow(2,k) ;i < pow(2, k + 1);i++)
            {
                res[i] = pow(2,k) + res[pow(2, k + 1) - i - 1];
            }
            k++;
        }
        return res;
    }
};

10-数学问题

分治法-巧解数学问题

公倍数与公因数​

随机与取样​

其他​

位运算​

公倍数与公因数

随机与取样

其他

位运算