Celery's Blog

0%

LeetCode-Day46

发表于 Valine：

裴蜀定理

对于任何整数a, b和他们的最大公约数d，关于未知数x, y的线性不定方程（裴蜀等式）。若a, b是整数，且gcd(a, b) = d，那么对于任意的整数x,y，ax+by都一定是d的倍数，特别的，一定存在整数x,y，使ax+by=d成立

水壶问题

372 超级次方

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 :

1
2
3
4
5
输入: a = 2, b = [3]
输出: 8

输入: a = 2, b = [1,0]
输出: 1024

问题本身并不难，一下就能想到快速幂。但是就是那个位上的权值一下子没想清楚…

res=a10kb0+10k−1b1+10k−2b2+...+100bkres = a^{10^kb_0+10^{k-1}b_1+10^{k-2}b_2+...+10^0b_k}

res=ab0res = a^{b_0}

res=res10∗ab1=a10b0+b1res = res^{10} * a^{b_1} = a^{10b_0 + b_1}

res=res10∗ab2=(a10b0+b1)10∗ab2=a102b0+10b1+b2res = res^{10} * a^{b_2} = (a^{10b_0 + b_1})^{10} * a^{b_2} = a^{10^{2}b_0 + 10b_1+b_2}

…

res=a10kb0+10k−1b1+10k−2b2+...+100bkres = a^{10^kb_0+10^{k-1}b_1+10^{k-2}b_2+...+10^0b_k}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ll binaryPow(ll a, ll b, ll m) {
    ll ans = 1;
    while(b > 0) {
        if(b & 1) {
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

int superPow(int a, vector<int>& b) {
    int n = b.size();
    ll check[10] = {0};
    ll res = 1;
    a = a % N;
    // cout << "a = " << a << endl;
    for(int i = 0; i < 10; i++) {
        check[i] = binaryPow(a, i, N);
    }
    for(int i = 0; i < n; i++) {
        res = (binaryPow(res, 10, N) * check[b[i]]) % N;
    }
    return int(res);
}

PS: 划重点，上面的快速幂！

373 查找和最小的K对数字

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。

找到和最小的 k 对数字 (u1,v1), (u2,v2) … (uk,vk)。

示例 :

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

输入: nums1 = [1,2], nums2 = [3], k = 3 
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

思路：使用优先队列和位置指针快速求解

首先，在遇到这种求前k个最大（最小）的问题时候，很自然的想到使用堆来减少时间复杂度。这里，使用优先级队列priority_queue来达到堆的效果。

第二，由于 nums1 和 nums2都是有序的，求前k个最小的则和类似一个指针从左到右不断滑动的过程，我们可以让数组1作为base，用另一个数组（长度和num1相等,，即代码中的check[]）来记录和从小到大过程中num1中每个元素 的另一半现在在num2数组中的位置。 每次循环找出是和最小的那一对，然后让那一对num2数组中的位置往前走一步，然后再次比较选出最小（使用优先级队列）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef pair<int, int> pp;
vector<vector<int> > kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<vector<int> > res;
    priority_queue<pp, vector<pp>, greater<pp> > q;
    int i = 0, j = 0, n1 = nums1.size(), n2 = nums2.size();
    if(!n1 || !n2) {
        return res;
    }
    int check[n1] = {0};
    for(int m = 0; m < n1; m++) {
        q.push(make_pair(nums1[m] + nums2[0], m));
    }
    k = min(k, n1 * n2);
    while(k--) {
        pair<int, int> p = q.top();
        int index = p.second;
        q.pop();
        vector<int> temp;
        temp.push_back(nums1[index]);
        temp.push_back(nums2[check[index]++]);
        if(index < n1 && check[index] < n2) {
            q.push(make_pair(nums1[index] + nums2[check[index]], index));
        }
        res.push_back(temp);
    }
    return res;
}

378 有序矩阵中第k小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。

示例:

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

思路：

想明白之后觉得难度还行~~

这边采用二分法。首先左上角的值为最小值(记为left)，右下角的值为最大值(记为right)。然后取他们的中间值(mid)，然后判断mid是第几小的元素，如果小于k，则令right = mid，如果比k大，则令left = mid + 1。不断更新，直到找到第k小的元素位置。

然后search_less_equal函数就是用来查找mid是第几小的元素。

如下图：

1580713527175

首先假设该点位于左下角，然后不断地右移（说明当前元素过大）或者上移（说明当前元素过小），然后在右移之前需要先加上这一列的比当前元素小的个数。

这样直到走到上边界或者右边界的时候就说明已经求出了比当前小的元素的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int search_less_equal(vector<vector<int> >& matrix, int target) {
    int n = matrix.size();
    int i = n - 1, j = 0, res = 0;
    while(i >= 0 && j < n) {
        if(matrix[i][j] <= target) {
            res += (i + 1);
            ++j;
        } else {
            --i;
        }
    }
    return res;
}

int kthSmallest(vector<vector<int> >& matrix, int k) {
    int left = matrix[0][0], right = matrix.back().back();
    while(left < right) {
        int mid = left + (right - left) / 2;
        int cnt = search_less_equal(matrix, mid);
        if(cnt < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

386 字典序排序

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

思路：

第一种是按照把数字转换成string类型，然后入优先队列，然后再转换成int

第二种就比较巧妙了！

按照10叉树的前序遍历即可得到结果，如下图，n = 145

1580720369480

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(vector<int>& res, int num, int n) {
    for(int i = 0; i < 10 && num <= n && res.size() < n; i++, num++) {
        res.push_back(num);
        // cout << "size = " << res.size() << endl;
        dfs(res, num * 10, n);
    }
}

vector<int> lexicalOrder(int n) {
    vector<int> res;
    dfs(res, 1, n);
    for(int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    return res;
}

390 消除游戏

给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

示例：

1
2
3
4
5
6
7
8
9
输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

输出:
6

思路：

  • 设n个数时，从左到右开始执行剩下的数为f1(n)，将n个数反转后(即：n,n-1,…,1)，从左到右执行剩下的数为f2(n)
  • 则，f1(n)和f2(n)剩下的数，在他们在各自原数组中的下标一定一样，即两者剩余的数都是下标i位置处的元素。1,…,n和n,…,1两个相同下标的元素相加为n+1
  • 那么f2(n)的元素怎么得到？对于2n个元素，执行一次从左到右之后，剩余的元素除以2，可以得到1,…,n的元素。
  • 如果继续执行，相当于对1,…,n的元素从右到左开始执行(因为第一次已经从左到右执行了)，等价于：对于1,…,n元素从右到左执行的结果*2，即：f1(2n)=2∗f2(n)f1(2n) = 2 * f2(n)
  • 所有得到递推式：$f1(n) + f2(n) = n + 1 又由于又由于f2(n) * 2 = f1(2n) 所以：所以：f1(n) + f1(2n) / 2 = n + 1$;
  • 用n/2替换n得到：f1(n/2)+f1(n)/2=n/2+1→f1(n)=2∗(n/2+1−f1(n/2))f1(n/2) + f1(n) / 2 = n / 2 + 1 \rightarrow f1(n) = 2 * (n / 2 + 1 - f1(n / 2))
1
2
3
4
int lastRemaining(int n) {
    if (n == 1) return 1;
        return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}