谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 833|回复: 4
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
reddatecookies 发表于 2017-11-1 00:22:20 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

您需要 登录 才可以下载或查看,没有帐号?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']. From 1point 3acres bbs
Output: [11, 17]

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]


上一篇:明天就11月了还没面试
下一篇:亚麻实习no longer基本确定是简历拒了
我的人缘0
cai_lw 发表于 2017-11-1 01:22:32 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这比字符串匹配trivial得多啊,跟KMP没什么关系
用一个sliding window扫一遍,记录window内各个keyword的出现次数,当所有keyword的出现次数都为1时输出对应index
每slide一格至多有两个keyword的出现次数会变化,故维护这个记录和判断是否输出index都可以在O(1)内完成,总复杂度为O(N)
回复 支持 2 反对 0

使用道具 举报

我的人缘0
LukeDong 发表于 2017-11-1 00:44:29 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
N 是什么? 以及 Search List, Keyword 的长度 都影响到复杂度吧。
以及。。indices that indicate the beginning of sequences of adjacent keywords 指的是找到所有的不重复子序列开始的 index 在满足这个子序列的单词全部是 key word 下 这个意思嘛?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| reddatecookies 发表于 2017-11-1 12:06:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
多谢楼上指点。写了写代码如下:. from: 1point3acres

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<>();. Waral 博客有更多文章,
. 1point3acres

        for (String word : keys) {
            int cnt = target.getOrDefault(word, 0);
            target.put(word, cnt + 1);.本文原创自1point3acres论坛
        }
. from: 1point3acres
        int m = search.size(), n = keys.size();
        if (m < n) return res;

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

        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));


            // chk should be done b4 any sliding
            if (Objects.equals(window, target)) {
                res.add(i - n);
            }


            // window sliding
            String toRemove = search.get(i - n);
            decrementWithCleaning(window, toRemove);. more info on 1point3acres

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


            i++;
        }
. 围观我们@1point 3 acres
        return res;. Waral 博客有更多文章,
    }

    private void decrementWithCleaning(Map<String, Integer> map, String key) {
        if (map.containsKey(key)) {
            int cnt = map.getOrDefault(key, 0);
            if (cnt <= 1) {
                map.remove(key);
            } else {
                map.put(key, cnt - 1);
            }
        }
    }. From 1point 3acres bbs

    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网
. visit 1point3acres for more.

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

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

}
. 围观我们@1point 3 acres
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| reddatecookies 发表于 2017-11-1 21:35:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
cai_lw 发表于 2017-11-1 01:22
这比字符串匹配trivial得多啊,跟KMP没什么关系
用一个sliding window扫一遍,记录window内各个keyword的 ...
.1point3acres网
如何有效比较两个map的内容?map.equals居然是O(N). 1point3acres
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-6-24 03:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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