leetcode第197场周赛
最后一个题写了个梯度下降，迭代次数1e5超时了，1e4又精度不够，好气哦
T1：好数对的数目
给你一个整数数组 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-good-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。直接上代码吧。
class Solution {
public int numIdenticalPairs(int[] nums) {
int count = 0;
for(int i = 0; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
if(nums[i] == nums[j]){
count++;
}
}
}
return count;
}
}T2:仅含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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-substrings-with-only-1s
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案
依次获得以当前结点结尾的全为1的子串。
定义一整型数组dp，dp[i]表示以i结尾的全为1的子串数目，dp数组之和即为所求。
转移方程：
baseline:
实现代码如下：
class Solution {
public int numSub(String s) {
if(s.length() == 0){
return 0;
}
int N = s.length();
int[] counts = new int[N];
int ans = 0;
int mod = (int)Math.pow(10, 9) + 7;
if(s.charAt(0) == '1'){
counts[0] = 1;
ans++;
}
for(int i = 1; i < N; i++){
if(s.charAt(i) == '1'){
counts[i] = counts[i - 1] + 1;
ans += counts[i];
ans = ans % mod;
}
}
return ans;
}
}我们发现dp[i]的取值只与其前一个元素的取值有关，因此我们将O(N)的额外空间复杂度压缩到O(1)。代码如下：
class Solution {
public int numSub(String s) {
int dp = s.charAt(0) == '1' ? 1 : 0;
int count = 0;
count += dp;
int mod = (int)Math.pow(10,9) + 7;
for(int i = 1; i < s.length(); i++){
if(s.charAt(i) == '0'){
dp = 0;
}else{
dp += 1;
}
count += dp;
count %= mod;
}
return count;
}
}T3：概率最大的路径
给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 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
每两个节点之间最多有一条边
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-maximum-probability
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案
我们发现n取值范围为1e4，因此使用dfs找出所有路径一定会超时。由于又是带权图的最短路径问题直接迪杰斯特拉算法。
当前未访问的节点中距离原地概率最大的结点，其当前的概率值就是当前结点里到源点最大的概率值。
证明：
未访问的里源点概率最大的结点记做M记做P(M).假设还存在一未访问的结点N，从start到N,记做P(N)，从N到M的概率(记做P(N->M)).
假设P(N) * P(N->M) > P(M) 即通过N再到M的概率大于直接到M的概率。
由于是P(N->M) < 1,因此 P(N) > P(M).同给出的条件矛盾，因此当前未访问的节点中距离原地概率最大的结点，其当前的概率值就是当前结点里到源点最大的概率值成立。
代码实现如下：
class Solution {
public static class Node{
int next;
double p;
public Node(int next, double p){
this.next = next;
this.p = p;
}
}
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<List<Node>> nexts = new ArrayList<>(n);
boolean[] visted = new boolean[n];
double[] dist = new double[n]; // 出发点到该点的最大距离
for(int i = 0; i < n; i++){
nexts.add(new ArrayList<>());
}
for(int i = 0; i < edges.length; i++){
int s = edges[i][0];
int e = edges[i][1];
nexts.get(s).add(new Node(e, succProb[i]));
nexts.get(e).add(new Node(s, succProb[i]));
}
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visted[start] = true;
dist[start] = 1;
while(!queue.isEmpty()){
int cur = queue.remove();
if(cur == end){
return dist[end];
}
for(Node node : nexts.get(cur)){
if(visted[node.next]){
continue;
}
dist[node.next] = Math.max(dist[node.next], dist[cur] * node.p);
}
int maxindex = - 1;
double max = 0.0;
for(int i = 0; i < n; i++){
if(visted[i]){
continue;
}
if(dist[i] > max){
max = dist[i];
maxindex = i;
}
}
if(maxindex == -1){
return 0.0;
}
visted[maxindex] = true;
queue.add(maxindex);
}
return 0.0;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录