week38

371 - 两整数之和

题里说的是不用加法完成加法运算，这里考的是位运算的应用

• 用异或来算不带进位的和(异或：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0)

• 用与 和 左移 来算进位

• 递归计算

举例来说，a=101, b=011

• 第一步: 异或，计算无需进位的部分，a^b=110，最右位的和2需要进位；

• 第二步: 与，a&b=001，结果表示的是需要进位的地方，将它左移一位得到010

第三步，递归调用，求进位前后的和，直到无需进位

class Solution {
public:
    int getSum(int a, int b) {
        if(!a) return b;
        int sum = a ^ b, carry = (unsigned)(a & b) << 1;
        return getSum(carry, sum);
    }
};

其中负数在计算机中存储是以补码的形式，左移有溢出可能，比如负数加负数（符号位都为1），用unsigned强转，在左移超过int位数之后自动丢弃，不会溢出

372 - 超级次方

提到次方就来狠狠回顾一下快速幂怎么写

int qmi(int m, int k, int p)
{
    int res = 1, t = m % p;
    while(k)
    {
        if(k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

这个题把快速幂和高精度结合在一起，对于本题而言， 把数字拆成个位和其他，递归求解

a ^ b3b2b1 % mod = (a ^ b3b2 % mod) ^ 10 * a ^ b1 % mod;

class Solution {
public:
    static const int mod = 1337;
    int qmi(int m, int k, int p)
    {
        int res = 1, t = m % p;
        while(k)
        {
            if(k & 1) res = res * t % p;
            t = t * t % p;
            k >>= 1;
        }
        return res;
    }
    int superPow(int a, vector<int>& b) {
        // 把这个问题转化
        // a ^ b3b2b1 % mod = (a ^ b3b2 % mod) ^ 10 * a ^ b1 % mod;
        if(b.empty()) return 1;
        int last_num = b.back();
        b.pop_back();
        return qmi(superPow(a, b), 10, mod) * qmi(a, last_num, mod) % mod; 
    }
};

373 - 查找和最小的k组数字

考察的是多路归并

class Solution {
public:
    struct Node{
        int sum;
        int aidx;
        int bidx;
        Node(){}
        Node(int _sum, int _aidx, int _bidx) : sum(_sum), aidx(_aidx), bidx(_bidx){}
    };
    struct cmp
    {
        bool operator()(const Node& a, const Node& b) const {
            return a.sum > b.sum;
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        // 这应该是归并排序的一种吧
        vector<vector<int>> res;
        priority_queue<Node, vector<Node>, cmp> heap;
        // 1. 初始化heapheap
        for(int i = 0; i < nums2.size(); i++)
            heap.push({nums1[0] + nums2[i], 0,  i});
        for(int i = 0; i < k && heap.size(); i++)
        {
            auto t = heap.top();
            heap.pop();
            res.push_back({nums1[t.aidx], nums2[t.bidx]});
            if(t.aidx + 1 < nums1.size())
            {
                int naidx = t.aidx + 1, nbidx = t.bidx;
                heap.emplace(nums1[naidx] + nums2[nbidx], naidx, nbidx);
            }
        }
        return res;
    }
};

374 - 猜数字大小

靠一些二分模板。。。

class Solution {
public:
    int guessNumber(int n) {
        int l = 1, r = n;
        while(l < r)
        {
            int mid = (long long)l + r >> 1;
            int res = guess(mid);
            if(res <= 0) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

376 - 摆动序列

本题是贪心算法，思路还挺难想的；

最优解就是在每个波动的波峰和波谷中选择顶点和底点，与开头结尾两个点组成的序列最长。

证明过程简要来说是反证法，如果存在非顶点或低点被选中的话，这个点的附近一定存在两个比他高or比他低的点，也就是新的局部极值点，与前面的假设矛盾（大概记一下就好了）

代码中的细节有两个，一个是相邻重复元素怎么去除;

nums.erase(unique(nums.begin(), nums.end()), nums.end())

原理是unique函数将重复元素交换到后面并返回迭代器，最后直接删除

另一个就是判断上升趋势与下降趋势是否与之前相同的逻辑怎么写 -> 异或运算，这里值得看一下

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        // 1. 去除所有相邻重复元素
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        if(nums.size() == 1) return 1;
        int res = 2;
        bool is_up = nums[0] < nums[1];
        // 2. 找到单调上升与下降区间并计数
        for(int i = 1; i + 1 < nums.size(); i++)
            if((nums[i] < nums[i + 1]) ^ is_up) //出现拐点
            {
                res++;
                is_up = !is_up;
            }
        return res;
    }
};

377 - 组合总和IV

回忆一下和组合问题三的区别，组合问题三中顺序不同的序列被视为相同的组合，对于这种有限制的组合问题可以用背包问题（这里是完全背包来解决）；

而对于本题，顺序不同的序列被视为不同的组合，这里也是动态规划的思想，具体如下：

• 状态定义： f[i]表示总和为i的所有排列组合可能性数量

• 状态转移： 枚举每个元素x 在原有序列后面拼上新的元素x的话，保证和之前所有的序列不重复，所以是f[i] += f[i - x]

class Solution {
public:
    vector<unsigned> f;
public:
    int combinationSum4(vector<int>& nums, int target) {
        // f[a]表示总和为a的方案数
        f = vector<unsigned>(target + 1, 0);
        f[0] = 1;
        for(int i = 1; i <= target; i++)
        {
            for(auto x : nums)
            {
                if(x <= i) f[i] += f[i - x]; 
            }
        }
        return f[target];
    }
};

378 - 有序矩阵中的第K小元素

每行元素均按升序排序 -> 多路归并，复杂度n^2logn

本题有额外的条件，每列元素按升序排序，且复杂度优于n^2 -> nlogn + 第K小元素，可以尝试下二分；

首先判断是否满足二分的性质，对于某个元素t:

• 小于等于t的元素数 < k: 则证明第K小元素 一定存在于[t + 1, matrix[n-1][n-1])

• 小于等于t的元素数 >= k: 第K小元素 index的区间[matrix[0][0], t]

matrix[n-1][n-1]为最大值，matrix[0][0]为最小值

接下来就是给定一个元素，如何计算小于等于他的元素个数：

对于第一行，可以直接线性扫描得到小于等于他的元素个数； 而对于第二行，由于按列递增，小于等于他的元素区间一定小于上一行；

这一性质对于接下来的每一行都成立，区间是越来越小的，我们可以利用这一性质，扫描下一行的时候，直接以上一行的终点向前扫描，直到列扫描结束，或者该行所有元素都满足大于；

因此，找到小于等于他元素个数的时间复杂度是o(n)

class Solution {
public:
    int n;
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        n = matrix.size();
        int l = matrix[0][0], r = matrix[n-1][n-1] + 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(matrix, mid, k)) r = mid;
            else l = mid + 1;
        }
        return l;

    }
    int  check(vector<vector<int>>& matrix, int x, int k)
    {
        int end = n - 1, res = 0;
        for(int i = 0; i < n; i++)
        {
            auto& line = matrix[i];
            while(end >= 0 && line[end] > x) end--;
            res += end + 1;
            if(res >= k || end < 0) break;
        }
        // cout << res << ' ' << x << endl;
        return res >= k;
    }
};

380 - O(1)时间插入，删除和获取随机元素

实现一个数据结构, 可以完成：

• O(1)插入 -> hash

• O(1)删除 -> hash

• O(1)随机返回一个值，保证等概率 -> vector

等概率返回可以通过数组实现，按照下标直接顺序返回就可以了，因此通过哈希+数组的双数据结构来实现，哈希表内存储元素->vector下标，问题是如何实现O(1)的删除；

对于vector pop_back()操作是o(1)的，那么对于想删除元素的话，只需要交换想删除元素 与最后一个就好；

注意下swap和rand()怎么用

class RandomizedSet {
public:
    vector<int> arr;
    unordered_map<int, int> h;
public:
    RandomizedSet() {
    }
    
    bool insert(int val) {
        if(h.count(val)) return false;
        else{
            h[val] = static_cast<int>(arr.size());
            arr.push_back(val);
        }
        return true;
    }
    
    bool remove(int x) {
        if(h.count(x)){
            int y = arr.back();
            int px = h[x], py = h[y]; // py 也可以等于 arr.size() - 1, 是一个道理
            swap(arr[px], arr[py]);
            swap(h[x], h[y]);
            h.erase(x);
            arr.pop_back();
            return true;
        }
        return false;

    }
    
    int getRandom() {
        return arr[rand() % arr.size()];
    }
};