On the shoulders of giants.

weekly-contest-191

数组中两元素的最大乘积

给你一个整数数组 nums,请你选择数组的两个不同下标 ij使 (nums[i]-1)*(nums[j]-1) 取得最大值。

请你计算并返回该式的最大值。

示例 1:

输入:nums = [3,4,5,2]
输出:12 
解释:如果选择下标 i=1 和 j=2(下标从 0 开始),则可以获得最大值,(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。 

示例 2:

输入:nums = [1,5,4,5]
输出:16
解释:选择下标 i=1 和 j=3(下标从 0 开始),则可以获得最大值 (5-1)*(5-1) = 16 。

示例 3:

输入:nums = [3,7]
输出:12

提示:

  • 2 <= nums.length <= 500
  • 1 <= nums[i] <= 10^3
题解

枚举所有可能,更新最大值。

时间复杂度:\(O(n)\)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int result = -1E9, n = nums.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                result = max(result, (nums[i] - 1) * (nums[j] - 1));
            }
        }
        return result;
    }
};

切割后面积最大的蛋糕

矩形蛋糕的高度为 h 且宽度为 w,给你两个整数数组 horizontalCutsverticalCuts,其中 horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离,类似地, verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。

请你按数组 horizontalCuts verticalCuts 中提供的水平和竖直位置切割后,请你找出 面积最大 的那份蛋糕,并返回其 面积 。由于答案可能是一个很大的数字,因此需要将结果对 10^9 + 7 取余后返回。

示例 1:

输入:h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出:4 
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色的那份蛋糕面积最大。

示例 2:

输入:h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
输出:6
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色和黄色的两份蛋糕面积最大。

示例 3:

输入:h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出:9

提示:

  • 2 <= h, w <= 10^9
  • 1 <= horizontalCuts.length < min(h, 10^5)
  • 1 <= verticalCuts.length < min(w, 10^5)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • 题目数据保证 horizontalCuts 中的所有元素各不相同
  • 题目数据保证 verticalCuts 中的所有元素各不相同
题解

先找到一行中的最大间隔,然后再找一列中的最大间隔,两者相乘即为答案。

为了处理方便,添加边缘线为分割线。

时间复杂度:\(O(n)\)

const int MOD = 1E9 + 7;
class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        horizontalCuts.push_back(h);
        verticalCuts.push_back(w);
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        int n = horizontalCuts.size(), m = verticalCuts.size(), result = 0;
        int max_row = horizontalCuts[0];
        for(int i = 1; i < n; i++) {
            max_row = max(max_row, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        int max_col = verticalCuts[0];
        for(int i = 1; i < m; i++) {
            max_col = max(max_col, verticalCuts[i] - verticalCuts[i - 1]);
        }
        return 1ll * max_row * max_col % MOD;
    }
};

重新规划路线

n 座城市,从 0n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。

路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 ab 的一条有向路线。

今年,城市 0 将会举办一场大型比赛,很多游客都想前往城市 0 。

请你帮助重新规划路线方向,使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。

示例 1:

输入:n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
输出:3
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。

示例 2:

输入:n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
输出:2
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。

示例 3:

输入:n = 3, connections = [[1,0],[2,0]]
输出:0

提示:

  • 2 <= n <= 5 * 10^4
  • connections.length == n-1
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] <= n-1
  • connections[i][0] != connections[i][1]
题解

n 个节点,n – 1 条边,可以当做无向图,然后选定根节点,在当做有根树遍历,遍历过程如果与原边有冲突,则记录。

时间复杂度:\(O(n\log n)\)

const int N = 5E4 + 10;
class Solution {
public:
    map<pair<int, int>, bool> vis;
    vector<int> g[N];
    int total = 0;
    void DFS(int u, int p) {
        for(auto v : g[u]) {
            if(v == p) continue;
            if(vis.find(make_pair(v, u)) == vis.end()) total++;
            DFS(v, u);
        }
    }
    int minReorder(int n, vector<vector<int>>& connections) {
        for(auto edge : connections) {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
            vis[make_pair(edge[0], edge[1])] = true;
        }
        DFS(0, -1);
        return total;
    }
};

两个盒子中球的颜色数相同的概率

桌面上有 2n 个颜色不完全相同的球,球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ,其中 balls[i] 是颜色为 i 的球的数量。

所有的球都已经 随机打乱顺序 ,前 n 个球放入第一个盒子,后 n 个球放入另一个盒子(请认真阅读示例 2 的解释部分)。

注意:这两个盒子是不同的。例如,两个球颜色分别为 ab,盒子分别为 [](),那么 [a] (b)[b] (a) 这两种分配方式是不同的(请认真阅读示例 1 的解释部分)。

请计算「两个盒子中球的颜色数相同」的情况的概率。

示例 1:

输入:balls = [1,1]
输出:1.00000
解释:球平均分配的方式只有两种:
- 颜色为 1 的球放入第一个盒子,颜色为 2 的球放入第二个盒子
- 颜色为 2 的球放入第一个盒子,颜色为 1 的球放入第二个盒子
这两种分配,两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。

示例 2:

输入:balls = [2,1,1]
输出:0.66667
解释:球的列表为 [1, 1, 2, 3]
随机打乱,得到 12 种等概率的不同打乱方案,每种方案概率为 1/12 :
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
然后,我们将前两个球放入第一个盒子,后两个球放入第二个盒子。
这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
概率 = 8/12 = 0.66667

示例 3:

输入:balls = [1,2,1,2]
输出:0.60000
解释:球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的,但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
概率 = 108 / 180 = 0.6 。

示例 4:

输入:balls = [3,2,1]
输出:0.30000
解释:球的列表为 [1, 1, 1, 2, 2, 3]。要想显示所有 60 种随机打乱方案是很难的,但只检查「两个盒子中球的颜色数相同」的 18 种情况是比较容易的。
概率 = 18 / 60 = 0.3 。

示例 5:

输入:balls = [6,6,6,6,6,6]
输出:0.90327

提示:

  • 1 <= balls.length <= 8
  • 1 <= balls[i] <= 6
  • sum(balls) 是偶数
  • 答案与真实值误差在 10^-5 以内,则被视为正确答案
题解

动态规划,设 $lates dp{k,i,x,y}$ 为选完前 k 种球,前一半 n 容量中有 i 个球且 x 种球,后一半 n 容量中有 \(\sum_{p=1}^{p=k}-i\) 个球且 y 种球,其两盒中颜色种数相同的概率为多少。

有动态转移方程:\(dp_{k,i+c,dx,dy}=\sum dp_{k-1,i,x,y} \cdot v\) ,其中 v 是选完第 k 种球后的概率,根据计数原理可以得到上示公式。

时间复杂度:\(O(knm^2 \max balls)\)

# define leq_(i, l, r) for(int i = (l); i <= (r); i++)
const int K = 10, N = 50;
class Solution {
public:
    double dp[K][N][N][N];
    double C(int n, int m) {
        if(n < m) return 0;
        double ret = 1;
        for(int i = n; m < i; i--) ret *= i;
        for(int i = 1; i <= n - m; i++) ret /= i;
        return ret;
    }
    double getProbability(vector<int>& balls) {
        int n = 0, m = balls.size(), sum = 0;
        for(auto num : balls) n += num;
        n /= 2;
        dp[0][0][0][0] = 1.0;
        leq_(k, 1, m) {
            int now = balls[k - 1];
            leq_(i, 0, n) leq_(p, 0, m) leq_(q, 0, m) {
                double tot = 0;
                leq_(x, 0, now) if(i + x <= n && sum - i + now - x <= n)
                    tot += C(n - i, x) * C(n - sum + i, now - x);
                leq_(x, 0, now) if(i + x <= n && sum - i + now - x <= n) {
                    int dtp = p + (0 < x ? 1 : 0);
                    int dtq = q + (0 < now - x ? 1 : 0);
                    double v = C(n - i, x) * C(n - sum + i, now - x) / tot;
                    dp[k][i + x][dtp][dtq] += dp[k - 1][i][p][q] * v;
                }
            }
            sum += now;
        }
        double ans = 0;
        leq_(i, 0, m) ans += dp[m][n][i][i];
        return ans;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注