面试碰到的一个算法问题，懂的请指教

micfox001

最近找工作做的技术测试里有这么一道题：

看下图截图。



要求写一个Java 程序。

大意是输入是一个graph 里的每个点的neighbour ID 列表 （一个节点一行）。按照这个neighbor的列表输出要求是一个N * N的矩阵， 任意两个点如果是neighbor， 对应的矩阵元素就为1，否则为0. 行与列是指代同一个节点的矩阵元素值则为0.

我的问题是，看上面机考的截图， 读入的neighbor ID 列表是 system.in 。 那如何知道这个graph的总节点数？ 也就是上面输出的 N*N矩阵里的N的值？

我想到的是数输入的行数，但是问题是input 不是通过文件输入，而是system.in. 这种情况如会知道input 总共会有多少行？ system.in 不会有EOF， 怎么统计总共会有多少行输入？ 如果不通过统计input 有多少行， 如何得知节点数？

求大神指教？

jfding

do you have the question in English?

micfox001

jfding 发表于 2022-2-17 18:11
do you have the question in English?

see  the screenshot on the left.. it was the  problem in English. part of it.

jfding

micfox001 发表于 2022-2-17 18:13
see  the screenshot on the left.. it was the  problem in English. part of it.

只有一半啊

micfox001

jfding 发表于 2022-2-17 18:18
只有一半啊

看它截图里的那个例子（输入 的列表和输出的矩阵）， 整个问题描述太长， 一个截图放不下，要滚屏的。

BOLANGSHA

换行符数量？

nineyes

in.readline（）不就只有一行吗

dytmajia2014

不懂Java。每个顶点的neighbour list是token的集合？那么，只需 考虑所有token的集合，或着考虑所有token的最大值，再加上1，就是行数。

micfox001

BOLANGSHA 发表于 2022-2-17 18:25
换行符数量？

没有EOF，怎么知道system.in 的换行符总共会有多少个？

System.in 是指键盘输入吧？ 键盘输入如何得知什么时候输完呢？

右边的代码前面2-3 行是自带的。我当时就蒙了。

micfox001

nineyes 发表于 2022-2-17 18:29
in.readline（）不就只有一行吗

左边的输入例子应该不止一行吧。

nineyes

micfox001 发表于 2022-2-17 18:45
左边的输入例子应该不止一行吧。

所以用的是while loop

micfox001

nineyes 发表于 2022-2-17 18:49
所以用的是while loop

那要先走一次while loop 统计总共有多少行， 然后再走一次loop 逐行处理？

20分钟做这题，连写的时间都不够。不要说测试和构思。

xxxxyyyy

一行一行扫描就行，扫描完，找到最大的数就是总节点数。

clarkli

看题目只需要输出一次，只要读完所有行就知道最大的节点是多少了。

如果真的是无限输入，并且可能多次输出的话，考虑用hash map存储关系，另外一个单独变量存储最大的数。

llee

首先System.in就是个输入流，所以肯定有EOF。

输入每行代表一个节点的邻接表，第一个数字是节点id，接下来是和这个节点有边相连的节点列表。既然没有预先读节点数，基本上把输入流读完才能知道总节点数。

这种输入一般用Scanner最方便。

micfox001

llee 发表于 2022-2-17 19:04
首先System.in就是个输入流，所以肯定有EOF。

输入每行代表一个节点的邻接表，第一个数字是节点id，接下来 ...

我开始以为那个buffer reader 或者 stream reader会有行数，结果没有。

如果要读完那个system.in 才能知道行数，那是否要再走一次loop来挨个处理那个矩阵里的值？

那个readline会到达所谓的EOF？如果再走一次loop， 如何重置那个buffer reader的指针？让他重新指向头？怎么做？

micfox001

llee 发表于 2022-2-17 19:04
首先System.in就是个输入流，所以肯定有EOF。

输入每行代表一个节点的邻接表，第一个数字是节点id，接下来 ...

出题的人一开始就规定了function开始的三行，压根没用scanner。

闲人看海

能不能把附件里的图也发上来?

micfox001

dytmajia2014 发表于 2022-2-17 18:42
不懂Java。每个顶点的neighbour list是token的集合？那么，只需 考虑所有token的集合，或着考虑所有token的 ...

这和编程语言无关。

比如说， node ID 为0 的 邻居是node 1， 2， 3，4。 那就是一行：

0 1 2 3 4

第一个数字为参考节点的id （0），后面的数字为其邻居的id。 他的邻居有node 1， 2， 3， 4。 所以就是

0 1 2 3 4

node id 为1 的邻居是node 0 和 3。那就是输入的第二行：
1 0 3
。。。
如此类推。

dytmajia2014

micfox001 发表于 2022-2-17 18:34
这和编程语言无关。

比如说， node ID 为0 的 邻居是node 1， 2， 3，4。 那就是一行：

那定义一个集合S，把每次出现的node id，以及它的邻居id都放进S，最后得到的S集合的成员数目不就是行数了吗？还是我什么地方理解错了？

shayy

不知道是不是我想简单了，每次读入一行，找出最大值nTemp，如果nTemp>tempMax，把矩阵扩大到nTemp*nTemp，把填上已知的点的值，update tempMax
如果想做的完善点，记个输入的行数，while loop结束后，比一下tempMax和你记的行数，行数小的情况下，搞个error msg?

micfox001

dytmajia2014 发表于 2022-2-17 19:41
那定义一个集合S，把每次出现的node id，以及它的邻居id都放进S，最后得到的S集合的成员数目不就是行数了 ...

主要是那個輸入是system.in. 那是表示那個鄰居列表是通過鍵盤來輸入的。而不是一個文件。鍵盤輸入沒有文件尾。無法知道鍵盤什麼時候會停止輸入。

micfox001

shayy 发表于 2022-2-17 20:06
不知道是不是我想简单了，每次读入一行，找出最大值nTemp，如果nTemp>tempMax，把矩阵扩大到nTemp*nTemp， ...

我不肯定你的nTemp是指参照节点的id还是邻居列表的id。

如果是参照节点的id，那就和找出有多少行输入一样。最大的参照节点id必然是最后一行第一个数字。

如果是邻居节点id，那就不对了。因为id最大的节点也许和任何其他节点都不是邻居。那它的id就不会出现在任何一行的邻居节点上。

而且你这个做法只能用 2D的list来做数据结构？因为随时会扩展。不固定的。

shayy

micfox001 发表于 2022-2-17 21:04
我不肯定你的nTemp是指参照节点的id还是邻居列表的id。

如果是参照节点的id，那就和找出有多少行输入一 ...

也是，应该是tempMax=max(nTemp,tempMax, currentTotalLine)
nTemp是邻居节id

至于数据，c++的话可以用vector或者pointer，java不懂，但应该有相近的数据结构吧

woshizhuang110

system.in 那些代码是本身这题就自带的对吗？ 这代表着输入的文件，一般算法题都是这样的，你只需要按行处理，放到一个2d list里，你就得到题目的input文件了，并不是无限输入的。类似c++ 的 cin 或者 或者Python的input。你看给你的例子的input output旁边有个小图标，应该是可以下载txt，就是叫你写好可以测一下的，直接复制到命令行跑就可以。算法比赛一般都会要求你处理这个input， LeetCode一般是直接叫你完成一个function。

615615

    public static void main(String[] args) {
        int[][] nums =   {{0, 1, 2, 3, 4},
                          {1, 0, 3},
                          {2, 0, 3, 4},
                          {3, 0, 1, 2},
                          {4, 0, 2}};
        int[][] res = solve(nums);
        for(int[] row : res){
            System.out.println(Arrays.toString(row));
        }
    }

    private static int[][] solve(int[][] nums) {
        int col = 0;
        for(int i=0;i<nums.length;i++){
            col = Math.max(col, nums[nums.length - 1]  + 1);
        }
        int[][] res = new int[nums.length][col];
        for(int i=0;i<nums.length;i++){
            for(int j=1;j<nums.length;j++){
                res[nums[0]][nums[j]] = 1;
            }
        }
        return res;
    }


---------------------------------------------
[0, 1, 1, 1, 1]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 1]
[1, 1, 1, 0, 0]
[1, 0, 1, 0, 0]

micfox001

woshizhuang110 发表于 2022-2-17 21:27
system.in 那些代码是本身这题就自带的对吗？ 这代表着输入的文件，一般算法题都是这样的，你只需要按行处 ...

对。 那些代码本身这题自己带的。

那个buffered reader如果走完一轮loop， 得到节点数。 那如何把指针重置到buffered reader的开头？ 也就是说readline的function会从buffered reader 的开头重新读？

micfox001

615615 发表于 2022-2-17 21:42
public static void main(String[] args) {
        int[][] nums =   {{0, 1, 2, 3, 4},
             ...

只要有总节点数我就会做了。


谢谢你的回复。

llee

micfox001 发表于 2022-2-17 19:17
出题的人一开始就规定了function开始的三行，压根没用scanner。

我只是说如果是我来写这个代码会怎么写，这个限制你截图里也看不出来。

现在一般都至少是Java 8吧，BufferedReader也可以写的很精简：


        Pattern spaces = Pattern.compile("\\s+");
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            // 按行读所有的标准输入
            // adj是这个图的邻接表，比如adj.get(0)就是和节点0有边相连的所有节点的集合。
            Map<Integer, Set<Integer>> adj = reader.lines()
                    .map(spaces::splitAsStream)
                    .map(vs -> vs.mapToInt(Integer::parseInt).toArray()) // 转换成int数组
                    .collect(Collectors.toMap(va -> va[0], // 第一个元素作为key，其他元素放到一个set里。
                            va -> IntStream.of(va).skip(1).boxed().collect(Collectors.toSet())));
            int n = adj.size(); // 总节点数
            // 接下来转换成邻接矩阵输出
        }

从输入格式上看，不需要重置reader或者输入流。

希望能帮到。

llee

micfox001 发表于 2022-2-17 18:44
没有EOF，怎么知道system.in 的换行符总共会有多少个？

System.in 是指键盘输入吧？ 键盘输入如何得知什 ...

System.in也可能是管道过来的。键盘好像是Ctrl+D或者Command+D，取决于你用的终端软件。