ShortestPathVisitingAllNodes [source code]
public class ShortestPathVisitingAllNodes {
static
/****************************************************************************/
class Solution {
boolean[] visited;
public int shortestPathLength(int[][] graph) {
int N = graph.length;
visited = new boolean[N];
int root = -1;
for (int i = 0; i < N; i++) {
int sum = 0;
for (int nei : graph[i])
sum += nei;
if (sum == 1) {
root = i;
break;
}
}
}
}
/****************************************************************************/
public static void main(String[] args) {
ShortestPathVisitingAllNodes.Solution tester = new ShortestPathVisitingAllNodes.Solution();
}
}
是undirected的; 不知道给的这个graph里面, 对称是不是已经帮我处理好了呢?
好像不是...
不过自己把一个matrix对称性处理一下, 也不难;
这个问题的定义, 感觉好像是一个学过的经典问题?
想不起来, 感觉这个题目要吃亏了; 他们那些竞赛选手肯定很熟悉这个题目;
是不是MST? 有点像的样子; 不过, 这题直接给的定义, 没说一定要是tree啊, 有没有可能一个不是tree的path, 比如说是一个cycle, 最后比tree好? 好像不可能哦, 如果仅仅是为了走遍所有的弄得而, 最后cycle肯定是多余了一个edge;
重新看了一下例子, 好像跟MST不一样, 这个是一个类似一笔画的问题, 并不是单纯的select subset of edges这样的定义;
妈耶, 突然感觉好难;
example2看来, 对称性在graph里面是给处理好了的;
example1里面给的这个, 最后实际上就有一个edge被选择了两次, 然后example2, 就是一个正常的MST算法可以解决的;
感觉这次contest的题目都是一个特点, 就是一个类似全涵盖的问题, 比如之前的分牌问题;
当时那几题因为意识到了这个特点, 都采取了greedy的思路, 那么这题是不是也可以这样呢?
好像直接DFS穷搜应该可以吧?
时间不多了, 感觉写不出来了; 乱写写看了;
一个小问题, 这个比如DFS, 你需不需要维护visited? 如果维护, 那么你看example1这里, 0这个node实际上害死被访问了两次的;
如果不维护visited, 那么就可能出现死循环爆栈; 比如cycle;
怎么办?
一个小优化, 这题肯定是要从sink出发, 或者说leaf, 而不是盲目的从0出发; 看看例子很明显;
这么一看, 好像可以这样, 只有你在leaf的时候, 允许不遵守visited?
好像仔细一想, 就是一个graph的遍历问题? 比如example1, 我们可以认为从1出发, 到了0, 然后0的两个child, 第一个被访问的child的path(实际上是subpath)最后被append到了最终结果的长度里面去?
感觉应该是可以转化为一个普通的DFS问题的;
那么visited应该是可以正常维护的;
然后意识到, 还是看example1这个例子, 比如你站在0的时候, 2和3额可以选择去走任意的一个, 那么选哪个?
这里就是这个算法greedy的地方了, 不是随便选的, 应该是选深度比较低的? 对, 这样backtrack上来的时候, subpath更短; 因为第一个被visited的child的subpath是需要被复制两次的, 所以尽量让他短一点;
更广义的, 比如如果0的child不止两个, 很多个, 那么最后实际上你只要保证最后一个visit的child是最深的一个就行了, 其他的那些child的subpath反正是要被复制的, 无所谓;
上面这个算法看起来可行, 那么有一个问题, 给的这个graph, 实际上本身未必是一个tree, 怎么解决?
well, 如果你维护一个visited, 那么就算有cycle, 也无所谓, 最后还是当场tree来处理是没有问题的; 看example2就行了;
时间不够了, 具体的算法没有写; 后面再说了;
UNFINISHED
discuss有一个大神妹子(Google中国的, 全球13名)的录屏, 去了解一下, 很有意思;
这帮人无论是写代码还是解题的速度简直是太快了;
uwi: 6min
class Solution {
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int[][] g = new int[n][n];
for(int i = 0;i < n;i++){
Arrays.fill(g[i], 9999999);
g[i][i] = 0;
}
for(int i = 0;i < n;i++){
for(int e : graph[i]){
g[i][e] = g[e][i] = 1;
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] > g[i][k] + g[k][j]) {
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
long[][] dp = new long[1<<n][n];
for(int i = 1;i < 1<<n;i++){
Arrays.fill(dp[i], 99999999);
if(Integer.bitCount(i) == 1){
dp[i][Integer.numberOfTrailingZeros(i)] = 0;
}else{
for(int j = 0;j < n;j++){
if(i<<~j<0){
for(int k = 0;k < n;k++){
if(i<<~k<0 && j != k){
// k -> j
dp[i][j] = Math.min(dp[i][j], dp[i^1<<j][k] + g[k][j]);
}
}
}
}
}
}
long ret = Long.MAX_VALUE;
for(int i = 0;i < n;i++){
ret = Math.min(ret, dp[(1<<n)-1][i]);
}
return (int)ret;
}
}
有点吓人的样子, 而且看命名, 他认为是需要用DP的解法的;
这么短的时间写这么快的代码, 这个人手速真的太快了;
xiaowuc1: 5min
应该是个中国人:
class Solution {
public int shortestPathLength(int[][] graph) {
int[][] dp = new int[graph.length][1 << graph.length];
LinkedList<State> q = new LinkedList<State>();
for(int i = 0; i < graph.length; i++) {
Arrays.fill(dp[i], 1 << 25);
dp[i][1<<i] = 0;
q.add(new State(1<<i, i));
}
while(!q.isEmpty()) {
State curr = q.removeFirst();
for(int j: graph[curr.d]) {
int nmask = curr.mask | (1 << j);
if(dp[j][nmask] > dp[curr.d][curr.mask] + 1) {
dp[j][nmask] = dp[curr.d][curr.mask] + 1;
q.add(new State(nmask, j));
}
}
}
int ret = Integer.MAX_VALUE;
for(int i = 0; i < graph.length; i++) {
ret = Math.min(ret, dp[i][dp[0].length-1]);
}
return ret;
}
class State {
public int mask, d;
public State(int a, int b) {
mask=a;
d=b;
}
}
}
好像正常很多;
Problem Description
An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.
graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.
Example 1:
Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
Note:
- 1 <= graph.length <= 12
- 0 <= graph[i].length < graph.length
Difficulty:Hard
Total Accepted:118
Total Submissions:720
Contributor:awice