leetcode 1032. Stream of Characters

更新日期: 2020-01-10阅读: 1.8k标签: 数据
LeetCode 1032. Stream of Characters

题意:如果你稍微了解关于大数据/视频/音频流(Stream)处理的背景的话,你会觉得这道题非常棒。简单介绍下流处理,举个简单的例子,你在Youtobe上观看电影的时候不需要事先下载整个电影文件,而是进行缓存加载,来一点播放一点。前端视频代码需要对最近收到的视频文件进行检测,就要用到这个StreamChecker。

用字典树即可解决。首先在init的时候,把words中所有word逆置后存入字典树中;在query的时候,也有逆序的方式记录所有历史query过的值,同时判断其前缀是否存在于字典树中即可。


    function Node() {
      this.children = {}
    }
    class StreamChecker {
      constructor(words) {
        this.history = ''
        this.root = new Node;
        for (let word of words) {
          this.insert(word.split('').reverse().join(''))
        }
      }
      insert(word) {
        var node = this.root;
        for (let c of word) {
          var next = node.children[c]
          if (!next) {
            node.children[c] = next = new Node
          }
          node = next;
        }
        node.word = word;
      }
      search(word) {

        var current = this.root;
        for (var i = this.history.length - 1; i >= 0; i--) {
          var ch = this.history[i]
          if (current.children[ch] == null) {
            return false;
          }
          current = current.children[ch];
          if (current.word) {
            return true;
          }
        }
        return false

      }
      query(q) {
        this.history += q
        var val = this.search()
        console.log(val)
        return val
      }

    }

    var streamChecker = new StreamChecker(["cd", "f", "kl"]); // init the dictionary.
    streamChecker.query('a');          // return false
    streamChecker.query('b');          // return false
    streamChecker.query('c');          // return false
    streamChecker.query('d');          // return true, because 'cd' is in the wordlist
    streamChecker.query('e');          // return false
    streamChecker.query('f');          // return true, because 'f' is in the wordlist
    streamChecker.query('g');          // return false
    streamChecker.query('h');          // return false
    streamChecker.query('i');          // return false
    streamChecker.query('j');          // return false
    streamChecker.query('k');          // return false
    streamChecker.query('l');          // return true, because 'kl' is in the wordlist


链接: https://www.fly63.com/article/detial/8562

双向数据绑定与单向数据绑定的各自优势和关系

在react中是单向数据绑定,而在vue和augular中的特色是双向数据绑定。为什么会选择两种不同的机制呢?我猜测是两种不同的机制有不同的适应场景,查了一些资料后,总结一下。

原生JS数据绑定的实现

双向数据绑定是非常重要的特性 —— 将JS模型与HTML视图对应,能减少模板编译时间同时提高用户体验。我们将学习在不使用框架的情况下,使用原生JS实现双向绑定 —— 一种为Object.observe

JavaScript判断数据类型的多种方法【 js判断一个变量的类型】

js判断数据类型的多种方法,主要包括:typeof、instanceof、 constructor、 prototype.toString.call()等,下面就逐一介绍它们的异同。

javascript中的typeof返回的数据类型_以及强制/隐式类型转换

由于js为弱类型语言拥有动态类型,这意味着相同的变量可用作不同的类型。 typeof 运算符返回一个用来表示表达式的数据类型的字符串,目前typeof返回的字符串有以下这些: undefined、boolean、string、number、object、function、“symbol

使用typeof obj===‘object’潜在的问题,并不能确定obj是否是一个对象?

在js中我们直接这样写typeof obj===‘object’有什么问题呢?发现Array, Object,null都被认为是一个对象了。如何解决这种情况,能保证判断obj是否为一个对象

js进制数之间以及和字符之间的转换

js要处理十六进制,十进制,字符之间的转换,发现有很多差不多且书写不正确的方法.一个一个实践才真正清楚如何转换,现在来记录一下它们之间转换的方法。

js判断数字是奇数还是偶数的2种方法实现

奇数和偶数的判断是数学运算中经常碰到的问题,这篇文章主要讲解通过JavaScript来实现奇偶数的判断。2种判断方法:求余% 、&1

js算法_判断数字是否为素数/质数

质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。比如100以内共25个,js实现代码如下。

Js数据类型转换_JavaScript 那些不经意间发生的数据类型自动转换

JavaScript自动类型转换真的非常常见,常用的一些便捷的转类型的方式,都是依靠自动转换产生的。比如 转数字 : + x 、 x - 0 , 转字符串 : \\\"\\\" + x 等等。现在总算知道为什么可以这样便捷转换。

Js中实现XML和String相互转化

XML是标准通用标记语言 (SGML) 的子集,非常适合 Web 传输。XML 提供统一的方法来描述和交换独立于应用程序或供应商的结构化数据。 这篇文章主要介绍Js中实现XML和String相互转化

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!