leetcode 197 场周赛解析

第一题

链接：https://leetcode-cn.com/problems/number-of-good-pairs

1.给你一个整数数组 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
解释：数组中的每组数字都是好数对

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

看见题目第一反应两次遍历，但是看着测试数据的大小和数量，所以最好可以O(n)解决。以时间换取空间。申请一个数组tem[]，用来记录遍历到数字的个数，每当遍历到数字num，那么tem[num]存储的就是遍历到num,之前nums数组里面有都少个相同的num，然后将tem[num]加到结果count，以后记得记录下此次遍历到的num，也就是tem[num]++。

//代码
class Solution {
    public int numIdenticalPairs(int[] nums) {
        int count = 0;
        int tem[] = new int[101];
        for(int num : nums){
            count += tem[num];
            tem[num]++;
        }
        return count;
    }
}

第二题

链接：https://leetcode-cn.com/problems/number-of-substrings-with-only-1s/
给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例 1：

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

提示：

s[i] == '0' 或 s[i] == '1'
1 <= s.length <= 10^5

动态规划
动态转移方程为：

dp[i] = s.charAt(i) == '1' ? dp[i] = dp[i-1] + 1 : 0
//但是要记得边界条件，需要初始化dp[0]
dp[0] = s.charAt(0) == '1'? 1:0;

代码为：

class Solution {
    public int numSub(String s) {
        int len = s.length() , count = 0;;
        int dp[] = new int[len];
        //初始化边界值
        dp[0] = s.charAt(0) == '1'? 1:0;
        //记得加上边界值
        count += dp[0];
        for(int i = 1;i < len ; i++){
            dp[i] = s.charAt(i) == '1' ? dp[i] = dp[i-1] + 1 : 0 ;
           
            count += dp[i];
            count = count % 1000000007;
        }
        return count;
    }
}

第三题

链接：https://leetcode-cn.com/problems/path-with-maximum-probability/
给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

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

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

示例1

题目读完第一感觉就是单源最短路径，可以使用的是Dijkstra算法或者Bellman-Ford算法，我先用的Dijkstra算法，虽然通过了但是时间较长，于是改用了Bellman-Ford算法，通过循环对每条边进行松弛操作。时间复杂度为O(N * E)，空间复杂度为O(N)，其中N为点的个数，E为边的个数。
示例 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

 public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        double dic[] = new double[n];
        //起点,反正是相乘，所以设置为1
        dic[start] = 1;

        while(n-- > 0){
            boolean flag = false;
            for (int j = 0; j < edges.length; j++) {
                if (dic[edges[j][0]] * succProb[j] > dic[edges[j][1]]) {
                    dic[edges[j][1]] = dic[edges[j][0]] * succProb[j];
                    flag = true;
                }
                //无向图，需要反向遍历一次才行
                if (dic[edges[j][1]] * succProb[j] > dic[edges[j][0]]) {
                    dic[edges[j][0]] = dic[edges[j][1]] * succProb[j];
                    flag = true;
                }
            }           
            if(flag == false) break;
        }
        return dic[end];
    }

第四题是数学题，不会，有待加强啊。

最后编辑于：2020.07.19 09:52:28