1512. 好数对的数目

直接算每个数即可

class Solution {
public:int numIdenticalPairs(vector<int>& nums) {int mp[110]={0};memset(mp,0,sizeof(0));for(int i=0;i<nums.size();i++){mp[nums[i]]++;}long long ans=0;for(int i=0;i<=100;i++){ans+=(long long)mp[i]*(mp[i]-1)/2;}return ans;}
};

1513. 仅含 1 的子串数

扫一遍找出1最长串，然后算出1字串数即可

class Solution {
public:int numSub(string s) {int n=s.length();int num = 0;long long ans = 0;int mod = 1e9+7;for(int i=0;i<=n;i++){if(s[i]=='0'||i==n){ans += (long long )num * (num + 1) / 2 % mod;num = 0;}else num++;}return ans;}
};

1514. 概率最大的路径

dij求最短路 的变形题。

只要满足无后效性即可（每个点的值当前最优，后面不会经过其他点使得这个点再次变最优）

class Solution {
public:vector<pair<int,double> >G[10007];double dp[10007];int vs[10007];double eps  = 1e-6;priority_queue<pair<double,int> >q;double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {for(auto x:G)x.clear();memset(dp,0,sizeof(dp));memset(vs,0,sizeof(vs));for(int i=0;i<edges.size();i++){int u=edges[i][0],v=edges[i][1];G[u].push_back({v,succProb[i]});G[v].push_back({u,succProb[i]});}//dijdp[start]=1.0;q.push({1.0,start});while(!q.empty()){int x=q.top().second;q.pop();vs[x]=1;for(auto z : G[x]){int y = z.first;double w=z.second;if(vs[y])continue;if(dp[x] * w + eps> dp[y])dp[y] = dp[x] * w,q.push({dp[y],y});}}//cout<<dp[end]<< "  -  "<<endl;return dp[end];};
};