第一題
鏈接：https://leetcode-cn.com/problems/number-of-good-pairs
1.給你一個整數(shù)數(shù)組 nums 阅签。如果一組數(shù)字 (i,j) 滿足 nums[i] == nums[j] 且 i < j 佑女，就可以認(rèn)為這是一組 好數(shù)對 仗扬。返回好數(shù)對的數(shù)目。
示例1：
輸入：nums = [1,2,3,1,1,3]
輸出：4
解釋：有 4 組好數(shù)對宽闲，分別是 (0,3), (0,4), (3,4), (2,5) ，下標(biāo)從 0 開始。
示例2：
輸入：nums = [1,1,1,1]
輸出：6
解釋：數(shù)組中的每組數(shù)字都是好數(shù)對
提示：
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
看見題目第一反應(yīng)兩次遍歷缀程，但是看著測試數(shù)據(jù)的大小和數(shù)量，所以最好可以O(shè)(n)解決蜡坊。以時間換取空間杠输。申請一個數(shù)組tem[]，用來記錄遍歷到數(shù)字的個數(shù)秕衙，每當(dāng)遍歷到數(shù)字num蠢甲，那么tem[num]存儲的就是遍歷到num,之前nums數(shù)組里面有都少個相同的num，然后將tem[num]加到結(jié)果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/
給你一個二進(jìn)制字符串 s（僅由 '0' 和 '1' 組成的字符串）勇吊。返回所有字符都為 1 的子字符串的數(shù)目曼追。
由于答案可能很大，請你將它對 10^9 + 7 取模后返回汉规。
示例 1：
輸入：nums = [1,2,3,1,1,3]
輸出：4
解釋：有 4 組好數(shù)對礼殊，分別是 (0,3), (0,4), (3,4), (2,5) 驹吮，下標(biāo)從 0 開始。
提示：
- s[i] == '0' 或 s[i] == '1'
- 1 <= s.length <= 10^5
動態(tài)規(guī)劃
動態(tài)轉(zhuǎn)移方程為：
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 個節(jié)點(diǎn)（下標(biāo)從 0 開始）組成的無向加權(quán)圖碟狞，該圖由一個描述邊的列表組成，其中 edges[i] = [a, b] 表示連接節(jié)點(diǎn) a 和 b 的一條無向邊婚陪，且該邊遍歷成功的概率為 succProb[i] 族沃。
指定兩個節(jié)點(diǎn)分別作為起點(diǎn) start 和終點(diǎn) end ，請你找出從起點(diǎn)到終點(diǎn)成功概率最大的路徑泌参，并返回其成功概率脆淹。
如果不存在從 start 到 end 的路徑，請 返回 0 沽一。只要答案與標(biāo)準(zhǔn)答案的誤差不超過 1e-5 盖溺，就會被視作正確答案。
題目讀完第一感覺就是 單源最短路徑锯玛，可以使用的是Dijkstra算法或者Bellman-Ford算法咐柜，我先用的Dijkstra算法，雖然通過了但是時間較長攘残，于是改用了Bellman-Ford算法拙友，通過循環(huán)對每條邊進(jìn)行松弛操作。時間復(fù)雜度為O(N * E)歼郭，空間復(fù)雜度為O(N)遗契，其中N為點(diǎn)的個數(shù)，E為邊的個數(shù)病曾。
示例 1：
輸入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
輸出：0.25000
解釋：從起點(diǎn)到終點(diǎn)有兩條路徑牍蜂，其中一條的成功概率為 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];
//起點(diǎn),反正是相乘泰涂，所以設(shè)置為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];
}
第四題 是數(shù)學(xué)題，不會逼蒙，有待加強(qiáng)啊从绘。
