On the shoulders of giants.

weekly-contest-197

好数对的数目

给你一个整数数组 nums

如果一组数字 (i,j) 满足 nums[i] == nums[j]i < j ,就可以认为这是一组 好数对

返回好数对的数目。

示例 1:

输入:nums = [1,2,3,1,1,3]
输出:4
解释:有 4 组好数对,分别是 (0,3), (0,4), (3,4), (2,5) ,下标从 0 开始

示例 2:

输入:nums = [1,1,1,1]
输出:6
解释:数组中的每组数字都是好数对

示例 3:

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

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
题解

遍历判断即可。

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

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int result = 0;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(nums[i] == nums[j]) result++;
            }
        }
        return result;
    }
};

仅含 1 的子串数

给你一个二进制字符串 s(仅由 ‘0’ 和 ‘1’ 组成的字符串)。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大,请你将它对 10^9 + 7 取模后返回。

示例 1:

输入:s = "0110111"
输出:9
解释:共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次

示例 2:

输入:s = "101"
输出:2
解释:子字符串 "1" 在 s 中共出现 2 次

示例 3:

输入:s = "111111"
输出:21
解释:每个子字符串都仅由 '1' 组成

示例 4:

输入:s = "000"
输出:0

提示:

  • s[i] == '0's[i] == '1'
  • 1 <= s.length <= 10^5
题解

连续 n 个 1 的方案数为:\(n(n+1)/2\) 。所以找出所有连续的 1 ,然后计算。

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

const int MOD = 1E9 + 7;
class Solution {
public:
    int numSub(string s) {
        int n = s.length(), result = 0;
        for(int i = 0; i < n; i++) {
            while(i < n && s[i] == '0') i++;
            int m = 0;
            while(i < n && s[i] == '1') i++, m++;
            result = (result + 1ll * m * (m + 1) / 2) % MOD;
        }
        return result;
    }
};

概率最大的路径

给你一个由 n 个节点(下标从 0 开始)组成的无向加权图,该图由一个描述边的列表组成,其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边,且该边遍历成功的概率为 succProb[i]

指定两个节点分别作为起点 start 和终点 end ,请你找出从起点到终点成功概率最大的路径,并返回其成功概率。

如果不存在从 startend 的路径,请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ,就会被视作正确答案。

示例 1:

输入:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出:0.25000
解释:从起点到终点有两条路径,其中一条的成功概率为 0.2 ,而另一条为 0.5 * 0.5 = 0.25

示例 2:

输入:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出:0.30000

示例 3:

输入:n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出:0.00000
解释:节点 0 和 节点 2 之间不存在路径

提示:

  • 2 <= n <= 10^4
  • 0 <= start, end < n
  • start != end
  • 0 <= a, b < n
  • a != b
  • 0 <= succProb.length == edges.length <= 2*10^4
  • 0 <= succProb[i] <= 1
  • 每两个节点之间最多有一条边
题解

直接跑最短路(优化)算法。

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

const int N = 1E4 + 10, M = 4E4 + 10;
class Solution {
public:
    int Head[N], Next[M], ver[M], m = 1;
    double val[M];
    void add_edge(int x, int y, double z) {
        ver[++m] = y, val[m] = z, Next[m] = Head[x], Head[x] = m;
    }
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        for(int i = 0; i < succProb.size(); i++) {
            vector<int> edge = edges[i];
            add_edge(edge[0], edge[1], succProb[i]);
            add_edge(edge[1], edge[0], succProb[i]);
        }
        vector<bool> vis(n);
        vector<double> dis(n, 0);
        dis[start] = 1.0;
        priority_queue<pair<double, int>> pq;
        pq.push(make_pair(1.0, start));
        while(!pq.empty()) {
            int x = pq.top().second; pq.pop();
            if(vis[x]) continue;
            vis[x] = true;
            for(int e = Head[x]; e; e = Next[e]) {
                if(!vis[ver[e]] && dis[ver[e]] < dis[x] * val[e]) {
                    dis[ver[e]] = dis[x] * val[e];
                    pq.push(make_pair(dis[ver[e]], ver[e]));
                }
            }
        }
        return dis[end];
    }
};

服务中心的最佳位置

一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标,并希望能够以此为依据为新的服务中心选址:使服务中心 到所有客户的欧几里得距离的总和最小

给你一个数组 positions ,其中 positions[i] = [xi, yi] 表示第 i 个客户在二维地图上的位置,返回到所有客户的 欧几里得距离的最小总和 。

换句话说,请你为服务中心选址,该位置的坐标 [xcentre, ycentre] 需要使下面的公式取到最小值:

与真实值误差在 10^-5 之内的答案将被视作正确答案。

示例 1:

输入:positions = [[0,1],[1,0],[1,2],[2,1]]
输出:4.00000
解释:如图所示,你可以选 [xcentre, ycentre] = [1, 1] 作为新中心的位置,这样一来到每个客户的距离就都是 1,所有距离之和为 4 ,这也是可以找到的最小值。

示例 2:

输入:positions = [[1,1],[3,3]]
输出:2.82843
解释:欧几里得距离可能的最小总和为 sqrt(2) + sqrt(2) = 2.82843

示例 3:

输入:positions = [[1,1]]
输出:0.00000

示例 4:

输入:positions = [[1,1],[0,0],[2,0]]
输出:2.73205
解释:乍一看,你可能会将中心定在 [1, 0] 并期待能够得到最小总和,但是如果选址在 [1, 0] 距离总和为 3
如果将位置选在 [1.0, 0.5773502711] ,距离总和将会变为 2.73205
当心精度问题!

示例 5:

输入:positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]]
输出:32.94036
解释:你可以用 [4.3460852395, 4.9813795505] 作为新中心的位置

提示:

  • 1 <= positions.length <= 50
  • positions[i].length == 2
  • 0 <= positions[i][0], positions[i][1] <= 100
题解

三分,在横轴上三分 x,然后在 x 上的竖轴三分 y,求最小值。

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

class Solution {
public:
    vector<vector<int>> pos;
    double cal(double x, double y) {
        double result = 0;
        for(int i = 0; i < pos.size(); i++) {
            double dx = x - pos[i][0];
            double dy = y - pos[i][1];
            result += sqrt(dx * dx + dy * dy);
        }
        return result;
    }
    double solve(double key) {
        double und = 0, top = 100;
        for(int i = 0; i < 100; i++) {
            double mid_und = und + (top - und) / 3;
            double mid_top = top - (top - und) / 3;
            double ans_und = cal(key, mid_und);
            double ans_top = cal(key, mid_top);
            if(ans_und > ans_top) und = mid_und;
            else top = mid_top;
        }
        return und;
    }
    double getMinDistSum(vector<vector<int>>& positions) {
        this->pos = positions;
        double lef = 0, rig = 100;
        for(int i = 0; i < 100; i++) {
            double mid_lef = lef + (rig - lef) / 3;
            double mid_rig = rig - (rig - lef) / 3;
            double ans_lef = cal(mid_lef, solve(mid_lef));
            double ans_rig = cal(mid_rig, solve(mid_rig));
            if(ans_lef > ans_rig) lef = mid_lef;
            else rig = mid_rig;
        }
        return cal(lef, solve(lef));
    }
};
Share

You may also like...

发表评论

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