分享一道狗家onsite题目

给一个string,用\n分隔,给定index,返回该index在第几行

Follow up:
给一个string,用\n分隔,给多个index,分别返回该index在第几行

1 Like
def findLine_iterate(article, keyword):
    lines = article.split('\n')

    for idx,line in enumerate(lines, 1):
        idxof = line.indexOf(keyword)
        if idxof != -1:
            return idx
    return -1

解释一下思路?

其实可以binary search 的

我只写了第一部分的简单思路,binary search 是如何实现的呢?

至于indexOf部分的话,就可以用KMP等算法了.

这个有点过了吧

这个应该很容易想到,而且应该是正解,你再想想

你是指遍历行的时候用 binary search 吗? 没有顺序的行排列用 binary search 有优势吗?

举个例子,每一行的ending index 分别是 10, 23, 45, 80
你搜index 50 的话,不就是binary search这个数组么