Monthly Archives: July 2020

LeetCode Coin Change 2

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Note:

You can assume that

  • 0 <= amount <= 5000
  • 1 <= coin <= 5000
  • the number of coins is less than 500
  • the answer is guaranteed to fit into signed 32-bit integer

给定一堆不同面值的硬币,问凑齐amount块钱,有多少种不同的凑齐方案。

LeetCode Coin Change类似,也用动态规划。假设dp[i][j]表示用前i硬币,凑齐j块钱的方案数。则有两种情况,一是不用第i类硬币,有dp[i-1][j]种情况;二是用第i类硬币,则还需要凑齐j-coins[i]块钱,因为每类硬币无穷个,所以还是用前i类硬币凑齐j-coins[i]块钱,即有dp[i][j-coins[i]]种情况。两种情况数相加即可。完整代码如下:LeetCode Coin Change与

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        if(amount == 0) return 1;
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for(int i = 0; i <= n; ++i) dp[i][0] = 1;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= amount; ++j) {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
};

本代码提交AC,用时60MS。

LeetCode Number of Good Leaf Nodes Pairs

5474. Number of Good Leaf Nodes Pairs

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4:

Input: root = [100], distance = 1
Output: 0

Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [1, 2^10].
  • Each node’s value is between [1, 100].
  • 1 <= distance <= 10

这一题第一眼看上去还是有难度的,后来观察数据量,发现总节点数才1024,则叶子节点数会更少,所以首先尝试了暴力方法。

暴力方法分为两个阶段,第一阶段是找到所有的叶子节点,第二阶段是求任意两个叶子节点的最短距离。

第一阶段在递归查找所有叶子节点时,保留了从根到该叶子的路径,以便后续求任意两个叶子的距离。第二阶段求距离时,思路比较简单,比如第一个样例,节点4的路径是1-2-4,节点3的路径是1-3,则两条路径都从根节点开始,看看两者的最长的公共前缀,直到找到它们的最后一个公共节点,相当于它们的最近公共祖先,然后假设最近公共祖先为两个叶子的子树的根节点,算两个叶子的高度,高度相加就是它们的最短距离。完整代码如下:

class Solution {
private:
	void CollectLeaves(TreeNode *root, unordered_map<TreeNode*, vector<TreeNode*>> &all_paths, vector<TreeNode*> &one_path) {
		if (root == NULL)return;
		one_path.push_back(root);
		if (root->left == NULL && root->right == NULL) {
			all_paths[root] = one_path;
		}
		else {
			CollectLeaves(root->left, all_paths, one_path);
			CollectLeaves(root->right, all_paths, one_path);
		}
		one_path.pop_back();
	}
	int CalDist(vector<TreeNode*> &path1, vector<TreeNode*> &path2) {
		int m = path1.size(), n = path2.size();
		int i = 0;
		while (i < m&&i < n) {
			if (path1[i] != path2[i])break;
			++i;
		}
		return (m - i) + (n - i);
	}

public:
	int countPairs(TreeNode* root, int distance) {
		unordered_map<TreeNode*, vector<TreeNode*>> all_paths;
		vector<TreeNode*> one_path;
		CollectLeaves(root, all_paths, one_path);
		vector<TreeNode*> leaves;
		for (unordered_map<TreeNode*, vector<TreeNode*>>::iterator it = all_paths.begin(); it != all_paths.end(); ++it) {
			leaves.push_back(it->first);
		}

		int ans = 0;
		for (int i = 0; i < leaves.size(); ++i) {
			for (int j = i + 1; j < leaves.size(); ++j) {
				int d = CalDist(all_paths[leaves[i]], all_paths[leaves[j]]);
				if (d <= distance)++ans;
			}
		}

		return ans;
	}
};

本代码提交AC。

LeetCode Bulb Switcher IV

5473. Bulb Switcher IV

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

  • Choose any bulb (index i) of your current configuration.
  • Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

  • 1 <= target.length <= 10^5
  • target[i] == '0' or target[i] == '1'

给一排灯泡,初始时都是灭的,每次可以选第i个灯泡,然后把第i个到最后的所有灯泡的状态翻转。问最少需要多少次操作才能得到目标状态序列。

很有意思的题,观察数据发现数据规模在1e5,数据量比较大,估计只有O(n)算法能过。接着,观察样例,不要被样例的解答给迷惑了。比如第一个例子10111,除了样例的解法,还可以谈心的做,序列变化如下:

0. 00000
1. 11111
2. 10000
3. 10111

即每次从左往右,把第一个不符合target状态的灯及往后的灯都flip,这种方法已经是最优的了。所以对于任意一个灯泡,它至少被翻转的次数就是它前面有多少种连续不同状态的灯泡。比如对于10111的后三个111,它前面有1和0,因为最原始是00,要变成10,则在满足第一个灯泡时有个0->1的翻转,导致第2个灯泡也变了;第二个灯泡也要flip一次;等到111时,它需要翻转的次数就是前面10共有2种特异状态。

所以问题转换为求字符串中有多少个连续相同状态的片段,所有片段数就是需要翻转的次数。另外要注意如果开头是0的话,则开头可以少翻转一次。代码如下:

class Solution {
public:
	int minFlips(string target) {
		int n = target.size();
		int ans = 0;
		int  i = 0;
		while (i < n) {
			int j = i + 1;
			while (j < n&&target[j] == target[i])++j;
			++ans;
			i = j;
		}
		if (target[0] == '0')return ans - 1;
		else return ans;
	}
};

本代码提交AC。

LeetCode Shuffle String

5472. Shuffle String

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

  • s.length == indices.length == n
  • 1 <= n <= 100
  • s contains only lower-case English letters.
  • 0 <= indices[i] < n
  • All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

给定一个字符串,根据给定规则进行shuffle,直接照做。代码如下:

class Solution {
public:
	string restoreString(string s, vector<int>& indices) {
		int n = s.size();
		string ans = s;
		for (int i = 0; i < n; ++i)ans[indices[i]] = s[i];
		return ans;
	}
};

本代码提交AC。

LeetCode Minimum Window Substring

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

给两个字符串S和T,问S中是否存在一个子串,包括T中的所有字符,如果存在,输出最短的那个子串。

hard题,用双指针+滑动窗口。核心思想是找到滑动窗口[i,j),首先++j,加入右边界的字符;然后检查[i,j)是否能覆盖t;再然后++i,丢掉左边界的字符。

首先设置一个required数组,存储t中每个字符出现的次数,表示滑动窗口[i,j)需要覆盖的每个字符的次数。found表示需要找到的字符总数,如果found==t.size()表示滑动窗口能覆盖t。

首先检查右边界j,如果s[j]在t中,则++found。然后看看found==n?,如果是,则检查左边界,如果左边界s[i]在t中,则i++之后要–found。在窗口滑动过程中记录窗口最小长度。完整代码如下:

class Solution {
public:
	string minWindow(string s, string t) {
		int m = s.size(), n = t.size();
		vector<int> required(128, 0);
		for (int i = 0; i < n; ++i) {
			++required[t[i]];
		}

		int min_len = m + 1, start_id = 0, found = 0;
		int i = 0, j = 0;
		while (j < m) {
			--required[s[j]];
			if (required[s[j]] >= 0) { // s[j]在t中
				++found;
			}
			++j;

			while (found == n) {
				int cur_len = j - i;
				if (cur_len < min_len) {
					min_len = cur_len;
					start_id = i;
				}
				++required[s[i]];
				if (required[s[i]] > 0) --found;
				++i;
			}
		}
		if (min_len == m + 1) return "";
		else return s.substr(start_id, min_len);
	}
};

本代码提交AC,用时16MS。

今晚字节跳动三面,面试官问了一个此题的变种,即只给定了字符串s,要找s的一个子串,使得该子串能覆盖s中所有特异的字符,且子串越短越好。可以把面试问题转换为这个问题,即先遍历s,把s中的特异字符拼成一个字符串t,然后调用本题的解法。

LeetCode Number of Nodes in the Sub-Tree With the Same Label

5465. Number of Nodes in the Sub-Tree With the Same Label

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
Output: [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

  • 1 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • labels.length == n
  • labels is consisting of only of lower-case English letters.

给定一棵多叉树(无向图),有n个顶点n-1条边。每个顶点上标了一个字母,问对于每个顶点,在它的子树中,与其字母相同的点有多少个。

每个节点维护一个26长的数组,记录该子树包含所有字母的频数。然后DFS,记录每个节点的这个数组,父节点的数组的值要累加上其直接孩子的这个数组的值。最后查表得到结果。代码如下:

class Solution {
private:
	void DFS(int parid, int curid, vector<vector<int>> &children_string, unordered_map<int, vector<int>> &graph, const string &labels) {
		int mylabel = labels[curid] - 'a';
		++children_string[curid][mylabel];

		for (int i = 0; i < graph[curid].size(); ++i) {
			int childid = graph[curid][i];
			if (childid == parid)continue;
			DFS(curid, childid, children_string, graph, labels);
			for (int j = 0; j < 26; ++j) {
				children_string[curid][j] += children_string[childid][j];
			}
		}
	}
public:
	vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
		unordered_map<int, vector<int>> graph;
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]].push_back(edges[i][1]);
			graph[edges[i][1]].push_back(edges[i][0]);
		}
		vector<vector<int>> children_string(n, vector<int>(26, 0));
		
		DFS(-1, 0, children_string, graph, labels);

		vector<int> ans;
		for (int i = 0; i < n; ++i) {
			int mylabel = labels[i] - 'a';
			ans.push_back(children_string[i][mylabel]);
		}
		return ans;
	}
};

本代码提交AC。

LeetCode Water Bottles

5464. Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:

  • 1 <= numBottles <= 100
  • 2 <= numExchange <= 100

很贴近生活的一个题。初始有n瓶满饮料,喝完之后,可以每m个空瓶子换一瓶新饮料,问最终能喝多少瓶饮料。

直接模拟,代码如下:

class Solution {
public:
	int numWaterBottles(int numBottles, int numExchange) {
		int full = numBottles, empty = 0, div = numExchange;
		int ans = 0;
		while (full + empty >= div) {
			ans += full;
			empty += full;
			full = empty / div;
			empty = empty % div;
		}
		return ans + full;
	}
};

本代码提交AC。

LeetCode Number of Substrings With Only 1s

1513. Number of Substrings With Only 1s

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Example 4:

Input: s = "000"
Output: 0

Constraints:

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

给定一个字符串,问有多少个连续为1的子串。

简单题,先找出最长连续的1,假设长度为n,则这个n长的串能形成(n+1)n/2个1的子串,累加所有这样的子串和即可。代码如下:

const long long kMOD = 1e9 + 7;

class Solution {
	long long CalAccSum(long long l) {
		return (l %kMOD)* ((l + 1) % kMOD) / 2;
	}
public:
	int numSub(string s) {

		long long ans = 0;
		int i = 0, j = 0, n = s.size();
		while (i < n) {
			while (i < n&&s[i] == '0')++i;
			if (i >= n)break;
			j = i + 1;
			while (j < n&&s[j] == '1')++j;
			int m = j - i;
			ans += CalAccSum(m) % kMOD;
			i = j;
		}
		return ans % kMOD;
	}
};

本代码提交AC,用时36MS。

LeetCode Number of Good Pairs

1512. Number of Good Pairs

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

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

直接按题意做就行:

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

本代码提交AC,用时8MS。

LeetCode Path with Maximum Probability

1514. Path with Maximum Probability

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to endreturn 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

  • 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
  • There is at most one edge between every two nodes.

给定一个无向图,边表示概率,问从start到end的最大概率是多少。

借此题复习一下若干最短路径算法吧。

首先朴素的DFS,代码如下:

class Solution {
private:
	void DFS(const vector<vector<double>> &graph, vector<int> &visited, int start, int end, double curprob, double &maxprob) {
		
		if (start == end) {
			maxprob = max(maxprob, curprob);
			return;
		}

		int n = graph.size();
		for (int i = 0; i < n; ++i) {
			if (visited[i] == 0 && graph[start][i] >= 0) {
				visited[i] = 1;
				DFS(graph, visited, i, end, curprob*graph[start][i], maxprob);
				visited[i] = 0;
			}
		}

	}
public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<vector<double>> graph(n, vector<double>(n, -1.0));
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}
		vector<int> visited(n, 0);
		visited[start] = 1;
		double maxprob = 0;
		DFS(graph, visited, start, end, 1, maxprob);
		return maxprob;
	}
};

本代码提交TLE。

其次, 朴素的迪杰斯特拉算法。迪杰斯特拉算法思路很简单,维护两个集合,一个集合S是已经找到最短路径的,另一个集合U是还未找到最短路径的。每次,从U选一个距离最小的节点u,这个节点已经是最短路径了,加入到S中。然后更新与u相连的其他节点的最短路径。如此循环往复。代码如下:

// 朴素迪杰斯特拉
class Solution {

public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}

		vector<int> visited(n, 0);
		visited[start] = 1;

		vector<double> ans(n, 0);
		for (int i = 0; i < n; ++i) {
			ans[i] = graph[start][i];
		}

		while (true) {
			int maxid = -1;
			double maxprob = 0;
			for (int i = 0; i < n; ++i) {
				if (visited[i] == 0 && ans[i] > maxprob) {
					maxid = i;
					maxprob = ans[i];
				}
			}
			if (maxid == -1 || maxid == end)break; // 遇到end提前结束

			visited[maxid] = 1;


			for (unordered_map<int, double>::iterator it = graph[maxid].begin(); it != graph[maxid].end(); ++it) {
				int next = it->first;
				double prob = it->second;

				if (visited[next] == 0 && (maxprob*prob > ans[next])) {
					ans[next] = maxprob * prob;
				}

			}
		}

		return ans[end];
	}
};

很遗憾,上述代码在最后一个样例上TLE了。

优化版本的迪杰斯特拉算法。朴素迪杰斯特拉算法最耗时的是while循环内的两个for循环,第二个for循环是对找到的u节点的边进行循环,这个无法再优化,主要优化第一个for循环,即在U集合中找距离最短的u节点的过程。这里可以用优先队列来存储U中的所有节点。但是需要注意的是去重,比如题目中的第一个图,对于节点2,节点0弹出pq时,会访问节点2并把节点2加入到pq中;当节点1弹出pq时,又会访问节点2并把节点2加入到pq中,此时pq中出现了两个节点2,只不过prob不一样。所以pq弹出时可能会出现相同的节点,不过由于pq的性质,同样是2,先弹出来的肯定是概率最大的路径(最短路径),所以每次pq弹出时,更新visited数组,后续如果弹出的节点已经visited了,则不需要做第二个for循环了,直接continue。比如题目中的第一个图,0访问2时,压pq的是(id=2,prob=0.2);1访问2时,压pq的是(id=2,prob=0.25)。所以(id=2,prob=0.25)先于(id=2,prob=0.2)弹出,并设置visited[2]=1。当(id=2,prob=0.2)弹出时,visited[2]已经==1了,此时continue。


// 优化的迪杰斯特拉
struct P {
	int id_;
	double prob_;
	P(int id, double prob) :id_(id), prob_(prob) {};

	// priority_queue默认是最大堆,即小于就是小于
	bool operator<(const P& p) const {
		return this->prob_ < p.prob_;
	}
};

class Solution {

public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}

		vector<int> visited(n, 0);

		vector<double> ans(n, 0);
		ans[start] = 1;

		priority_queue<P> pq;
		pq.push(P(start, 1));

		while (!pq.empty()) {
			P cur = pq.top();
			pq.pop();
			
			if (cur.id_ == end)break; // 提前结束

			if (visited[cur.id_] == 1)continue;
			visited[cur.id_] = 1;

			for (unordered_map<int, double>::iterator it = graph[cur.id_].begin(); it != graph[cur.id_].end(); ++it) {
				int next = it->first;
				double prob = it->second;
				if (cur.prob_*prob > ans[next]) {
					ans[next] = cur.prob_*prob;
					pq.push(P(next, ans[next]));
				}
			}

		}
		return ans[end];
	}
};

本代码提交AC,用时428MS。

SPFA算法。SPFA算法的思想可以参考之前的一道题: http://code.bitjoy.net/2014/12/28/hihocoder-1093/

简单来说,SPFA就是带剪枝的BFS。它和迪杰斯特拉算法非常像,迪杰斯特拉算法是每次找U中距离最小的一个节点u,此时u的最短距离已经确定了,后续不会再更新了。因为迪杰斯特拉算法每次加入S的节点都是最优的,所以必须要线性(朴素迪杰斯特拉算法)或者用优先队列的方法从U中找到最小距离节点u。而SPFA算法就更简单一点,该算法不要求每次找到最优的节点u,因为SPFA是渐进逼近最优解的过程,它不需要线性查找,也不需要优先队列,它只需要一个简单的队列即可,每次把可以更新的节点u加入到队列中,然后BFS更新与u相连的其他节点。之前更新过的节点,后续还有可能更新。代码如下:

// SPFA
class Solution {

public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}

		vector<int> visited(n, 0);
		visited[start] = 1;

		vector<double> ans(n, 0);
		ans[start] = 1;

		queue<int> q;
		q.push(start);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			visited[cur] = 0;

			for (unordered_map<int, double>::iterator it = graph[cur].begin(); it != graph[cur].end(); ++it) {
				int next = it->first;
				double prob = it->second;
				if (ans[cur] * prob > ans[next]) {
					ans[next] = ans[cur] * prob;
					if (visited[next] == 0) {
						visited[next] = 1;
						q.push(next);
					}
				}
			}
		}

		return ans[end];
	}
};

本代码提交AC,用时392MS。