python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据

797. 所有可能的路径

 

给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)

二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点,空就是没有下一个结点了。

译者注:有向图是有方向的,即规定了 a→b 你就不能从 b→a 。

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据

 

输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据

 

输入:graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出:[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

 

1、python:

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据
from typing import List
import json

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        ans = list()
        stk = list()

        def dfs(x: int):
            if x == len(graph) - 1:
                ans.append(stk[:])
                return

            for y in graph[x]:
                stk.append(y)
                dfs(y)
                stk.pop()

        stk.append(0)
        dfs(0)
        return ans

if __name__ == __main__:
    graph_input = json.loads(input().strip())
    print(Solution().allPathsSourceTarget(graph_input))
View Code

2、java:

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据
import com.alibaba.fastjson.JSON;

import java.nio.charset.StandardCharsets;
import java.util.*;

class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Deque<Integer> stack = new ArrayDeque<Integer>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        stack.offerLast(0);
        dfs(graph, 0, graph.length - 1);
        return ans;
    }

    public void dfs(int[][] graph, int x, int n) {
        if (x == n) {
            ans.add(new ArrayList<Integer>(stack));
            return;
        }
        for (int y : graph[x]) {
            stack.offerLast(y);
            dfs(graph, y, n);
            stack.pollLast();
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int[][] graph = JSON.parseObject(cin.nextLine(), int[][].class);
        System.out.println(new Solution().allPathsSourceTarget(graph));
    }
}
View Code

3、go:

待写

4、c++:

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据
#include "vector"
#include "iostream"
#include ".\lib\json-3.9.1\single_include\nlohmann\json.hpp"
using json = nlohmann::json;
using namespace std;

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> stk;

    void dfs(vector<vector<int>>& graph, int x, int n) {
        if (x == n) {
            ans.push_back(stk);
            return;
        }
        for (auto& y : graph[x]) {
            stk.push_back(y);
            dfs(graph, y, n);
            stk.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        stk.push_back(0);
        dfs(graph, 0, graph.size() - 1);
        return ans;
    }
};

int main() {
    string graphInput;
    getline(cin, graphInput);
    // nullptr空,就false // 数组字符串转数组
    auto graphJson = json::parse(graphInput, nullptr, false);
    vector<vector<int>> graph = graphJson;
    
    auto result = Solution().allPathsSourceTarget(graph);

    // 数组转数组字符串
    auto jsonArray = nlohmann::json::array();
    jsonArray = result;
    auto resultString = jsonArray.dump();
    cout << resultString << endl;
}
View Code

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据

 

 5、javascript:

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据
let allPathsSourceTarget = function(graph) {
    const stack = [], ans = [];

    const dfs = (graph, x, n) => {
        if (x === n) {
            ans.push(stack.slice());
            return;
        }
        for (const y of graph[x]) {
            stack.push(y);
            dfs(graph, y, n);
            stack.pop();
        }
    }

    stack.push(0);
    dfs(graph, 0, graph.length - 1);
    return ans;
};

let readLine = require("readline");
const rl = readLine.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on("line", function (line) {
    let graph = JSON.parse(line);
    console.log(allPathsSourceTarget(graph));
});
View Code

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据

 

python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据

上一篇:Java内存区域详解


下一篇:IntelliJ IDEA 新建spring boot 找不到@RestController 、@RequestMapping