一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 629|回复: 4
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
reddatecookies 发表于 2017-11-1 00:22:20 | 显示全部楼层 |阅读模式

2017(7-9月)-[]CS本科+3个月-1年 - 内推| 码农类其他@其他

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

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

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:

Search list: ['hello', 'hi', 'welcome', 'greetings', 'hi', 'greetings', 'hey', 'hello']
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]. visit 1point3acres.com for more.

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']. From 1point 3acres bbs
Output: [0, 13, 17, 31]

cai_lw 发表于 2017-11-1 01:22:32 | 显示全部楼层
这比字符串匹配trivial得多啊,跟KMP没什么关系
用一个sliding window扫一遍,记录window内各个keyword的出现次数,当所有keyword的出现次数都为1时输出对应index.鏈枃鍘熷垱鑷1point3acres璁哄潧
每slide一格至多有两个keyword的出现次数会变化,故维护这个记录和判断是否输出index都可以在O(1)内完成,总复杂度为O(N)
回复 支持 2 反对 0

使用道具 举报

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.*;
. 1point3acres.com/bbs
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<>();. 1point3acres.com/bbs
. 鍥磋鎴戜滑@1point 3 acres

        for (String word : keys) {
            int cnt = target.getOrDefault(word, 0);
            target.put(word, cnt + 1);
        }
. 1point3acres.com/bbs
        int m = search.size(), n = keys.size();
        if (m < n) return res;

        Map<String, Integer> window = new HashMap<>();.1point3acres缃

        int i = 0;
        while (i < m) {
            // constructing initial window
            while (i < n && i < m) {
                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));
-google 1point3acres

            // chk should be done b4 any sliding
            if (Objects.equals(window, target)) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                res.add(i - n);
            }

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            // window sliding
            String toRemove = search.get(i - n);
            decrementWithCleaning(window, toRemove);

            String toAdd = search.get(i);
            window.put(toAdd, window.getOrDefault(toAdd, 0) + 1);


            i++;
        }

        return res;
    }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    private void decrementWithCleaning(Map<String, Integer> map, String key) {
        if (map.containsKey(key)) {
            int cnt = map.getOrDefault(key, 0);. From 1point 3acres bbs
            if (cnt <= 1) {
                map.remove(key);. 鍥磋鎴戜滑@1point 3 acres
            } else {
                map.put(key, cnt - 1);
            }
        }
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

    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);
. Waral 鍗氬鏈夋洿澶氭枃绔,

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

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

}
回复 支持 反对

使用道具 举报

 楼主| 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)
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-24 08:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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