📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2897| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 这道题不用KMP怎么才能做到O(N)

全局:

2017(7-9月)-CS本科+3个月-1年 | 内推| 码农类General全职@

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Given a list of keywords and a list of search words, return a list of indices that indicate the beginning of sequences of adjacent keywords.

Examples:
-baidu 1point3acres
Search list: ['hello', 'hi', 'welcome', 'greetings', 'hi', 'greetings', 'hey', 'hello']. Waral dи,
Keywords: ['hi', 'hey', 'greetings']
Output: [4]

Search list: ['i', 'saw', 'susie', 'sitting', 'in', 'a', 'shoe', 'shine', 'shop', 'where', 'she', 'sits', 'she', 'shines', 'and', 'where', 'she', 'shines', 'she', 'sits']
Keywords: ['she', 'sits', 'shines']
Output: [11, 17]. 1point 3 acres
. Waral dи,
Search list: ['peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', 'peppers', 'a', 'peck', 'of', 'pickled', 'peppers', 'peter', 'piper',’ 'picked', 'if', 'peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', 'peppers', 'wheres', 'the', 'peck', 'of', 'pickled', 'peppers', 'peter', 'piper', 'picked']
Keywords: ['peter', 'picked', 'piper']
Output: [0, 13, 17, 31]


上一篇:感觉亚麻no longer的真的可以Move on 了
下一篇:亚麻实习no longer基本确定是简历拒了
推荐
cai_lw 2017-11-1 01:22:32 | 只看该作者
全局:
这比字符串匹配trivial得多啊,跟KMP没什么关系
用一个sliding window扫一遍,记录window内各个keyword的出现次数,当所有keyword的出现次数都为1时输出对应index
每slide一格至多有两个keyword的出现次数会变化,故维护这个记录和判断是否输出index都可以在O(1)内完成,总复杂度为O(N)
回复

使用道具 举报

🔗
LukeDong 2017-11-1 00:44:29 | 只看该作者
全局:
N 是什么? 以及 Search List, Keyword 的长度 都影响到复杂度吧。
以及。。indices that indicate the beginning of sequences of adjacent keywords 指的是找到所有的不重复子序列开始的 index 在满足这个子序列的单词全部是 key word 下 这个意思嘛?
回复

使用道具 举报

🔗
 楼主| reddatecookies 2017-11-1 12:06:12 | 只看该作者
全局:
多谢楼上指点。写了写代码如下:

import java.util.*;

public class SolutionTwo {.--
    public List<Integer> findIndices(List<String> search, List<String> keys) {

        if (search == null || search.size() == 0 || keys == null || keys.size() == 0)
            return Collections.emptyList(); // empty keys as invalid (assumption)

        List<Integer> res = new ArrayList<>();

        Map<String, Integer> target = new HashMap<>();


        for (String word : keys) {
            int cnt = target.getOrDefault(word, 0);
            target.put(word, cnt + 1);
        } ..

        int m = search.size(), n = keys.size();
        if (m < n) return res;.google  и

        Map<String, Integer> window = new HashMap<>();

        int i = 0;.google  и
        while (i < m) {
            // constructing initial window
            while (i < n && i < m) {. check 1point3acres for more.
                System.out.println(String.format("Inner: i=%d, window=%s", i, window));
                int cnt = window.getOrDefault(search.get(i), 0);
                window.put(search.get(i), cnt + 1);
                i++;
            }.

            System.out.println(String.format("Outer: i=%d, window=%s", i, window));

.--
            // chk should be done b4 any sliding
            if (Objects.equals(window, target)) {
                res.add(i - n);. From 1point 3acres bbs
            }
. Waral dи,

            // window sliding
            String toRemove = search.get(i - n);
            decrementWithCleaning(window, toRemove);
. 1point 3acres
            String toAdd = search.get(i);
            window.put(toAdd, window.getOrDefault(toAdd, 0) + 1);

. 1point 3 acres
            i++;
        }

        return res;
    }.

    private void decrementWithCleaning(Map<String, Integer> map, String key) {
        if (map.containsKey(key)) {
            int cnt = map.getOrDefault(key, 0);. Waral dи,
            if (cnt <= 1) {
                map.remove(key);
            } else {
                map.put(key, cnt - 1);
            }
        }.1point3acres
    }

    public static void main(String[] args) {
        SolutionTwo solution = new SolutionTwo();

        String[] searchArray = {"hello", "hi", "welcome", "greetings", "hi", "greetings", "hey", "hello"};
        List<String> searchList = Arrays.asList(searchArray);

. 1point3acres
        String[] keyArray = {"hi", "hey", "greetings"};
        List<String> keyList = Arrays.asList(keyArray);

        List<Integer> res = solution.findIndices(searchList, keyList);
        System.out.println("result is " + res);
    }
. Waral dи,
}
回复

使用道具 举报

🔗
 楼主| reddatecookies 2017-11-1 21:35:45 | 只看该作者
全局:
cai_lw 发表于 2017-11-1 01:22
这比字符串匹配trivial得多啊,跟KMP没什么关系
用一个sliding window扫一遍,记录window内各个keyword的 ...

如何有效比较两个map的内容?map.equals居然是O(N)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表