字典树简单运用--》去亿万条城市三字码数据中Check是否存在某个城市三字码

前言:不知不觉来C***P半年了,过得也算是不好不坏。遇到过出问题只会推给开发,一直抱怨却提不出方案的业务;也遇到过大V开头(可以问度娘)的水的冒泡的开发。

有两件小事和大家分享一下:

1)我们组的接口调用某个外部接口,有些条件下该外部接口会直接把exception(堆栈信息,代码物理路径也有。。)抛给我们,我邮件给相关的测试和开发,

不出意外,没有回复;后来不知道他们搞什么鬼,想让我们把这个exception也Log下来。。。

2)说起这个大V开头的,也是我们要调用的某个外部接口的开发。简单描述一下:一次做一个紧急的变更,我这把在特定的条件下,要传一个string类型的Code给他们,

特定条件不满足就不传递(也就是null),他们要和数据库存储的Code做相等比较,然后告诉我某个产品是不是某家航司定投产品(有点智商的人都知道要返一个bool     值)。

这个大V开头的,不用string.Equals(不区分大小写),而是使用Contains。。我无所谓,我要的就是一个bool值。  结果这X把Code原样返回给我,要我自己再做一次字符串比较。不想跟这种水货说太多,我忍了,自己比就比吧。

不要以为这样就完了,在某个郁闷的下午,他和他们的测试,在lync上说我们调用他们的接口时,会抛异常。于是我给他们要异常的详细信息,大体是:“System.Argumentexception        NullReferenceException   in    String.Contains(String A, String B, StringCompare.*****)”,想必大家都明白怎么回事了,

我就在lync上问有没有做字符串的String.IsNullOrEmpty的Check,这X一口咬定说做了,并且坚持说是我们传参的问题。。。好吧,僵持了好长一会,毕竟本人级别不高,就去把事情给我师父说了,我师父去找他当面交涉,回来给我说:这件事你不用管了,不是我们的问题。看得出来,搞得我师父心情也不是很好。

算了,生活和工作难免会遇到各种问题和渣渣,但是我很幸运来这边,是我师父和我leader面试的我,并且来到了我在的team,去做好每一个变更和项目,去把O(N^2)

优化成O(Log N),乃至O(N),去把简单重复的事情做到极致!

订好元旦去西安玩的往返机票,打算这段时间把数据结构和常规的算法复习整理一下。想起来我来面试时,师父考的我第一个算法,就是该文章的题目;

特从这个开始做起,与大家共享:(刚才废话有点多,请大家勿怪)

至于字典树的理论,就很简单了,不罗嗦了,贴代码:

    class TrieNode
    {
        public TrieNode[] SonTrieNodes { get; set; }
        public char Value { get; set; }
        public int Num { get; set; }
        public bool IsLastNode { get; set; }

        public TrieNode()
        {
            Num = 1;
            SonTrieNodes = new TrieNode[26];
        }
    }
    public class TrieTree
    {
        private TrieNode _root;

        public TrieTree()
        {
            _root = new TrieNode();
        }

        public void InsertStr(string str)
        {
            if (string.IsNullOrEmpty(str)) return;

            var node = _root;
            var letters = str.ToUpper().ToCharArray();
            foreach (var letter in letters)
            {
                var position = letter - ‘A‘;
                if (node.SonTrieNodes[position] == null)
                {
                    node.SonTrieNodes[position] = new TrieNode()
                    {
                        Value = letter
                    };
                }
                else
                {
                    node.SonTrieNodes[position].Num++;
                }
                node = node.SonTrieNodes[position];
            }
            node.IsLastNode = true;
        }

        public bool isExistStr(string str)
        {
            if (string.IsNullOrEmpty(str)) return false;

            var node = _root;
            var letters = str.ToUpper().ToCharArray();

            foreach (var letter in letters)
            {
                var position = letter - ‘A‘;
                if (node.SonTrieNodes[position] == null)
                {
                    return false;
                }
                node = node.SonTrieNodes[position];
            }
            return node.IsLastNode;
        }

    }
    class Program
    {
        static void Main(string[] args)
        {
            var trieTree = new TrieTree();
            string[] cities = {"HKG","SEL","NYC","SHA",
                              "BJS","SIN","BKK"};
            foreach (var city in cities)
            {
                trieTree.InsertStr(city);
            }
            Console.WriteLine("是否存在SEL:");
            Console.WriteLine(trieTree.isExistStr("SEL"));

            Console.WriteLine("是否存在TYO:");
            Console.WriteLine(trieTree.isExistStr("TYO"));
            Console.Read();
        }
    }

至于,像输入一个字符,自动选择框提示该字符开头的城市、景点之类的,以及支持中文、拼音等;就可以利用字典树做变换,大家有兴趣可以自己玩玩。

祝大家周末愉快。

时间: 11-05

字典树简单运用--》去亿万条城市三字码数据中Check是否存在某个城市三字码的相关文章

HDU4825/5536 [01 字典树/简单字典树更新]

Xor Sum Time Limit: 1000 MS Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包含一个正整数 S ,之后 Zeus 需要在集合当中找出一个正整数 K ,使得 K 与 S 的异或结果最大.Prometheus 为了让 Zeus 看到人类的伟大,随即同意 Zeus 可以向人类求助.你能证明人类的智慧么? Input 输入包含若干组测试数

字典树简单知识及类实现

什么是trie树? ◇ trie树是一种用于快速检索的多叉树结构. ◇ 和二叉查找树不同,在trie树中,每个结点上并非存储一个元素. ◇ trie树把要查找的关键词看作一个字符序列.并根据构成关键词字符的先后顺序构造用于检索的树结构. ◇在trie树上进行检索类似于查阅英语词典. 一棵m度的trie树或者为空,或者由m棵m度的trie树构成. 例如,电子英文词典,为了方便用户快速检索英语单词,可以建立一棵trie树.例如词典由下面的单词构成:a.b.c.aa.ab.ac.ba.ca.aba.a

跳跃表,字典树(单词查找树,Trie树),后缀树,KMP算法,AC 自动机相关算法原理详细汇总

第一部分:跳跃表 本文将总结一种数据结构:跳跃表.前半部分跳跃表性质和操作的介绍直接摘自<让算法的效率跳起来--浅谈"跳跃表"的相关操作及其应用>上海市华东师范大学第二附属中学 魏冉.之后将附上跳跃表的源代码,以及本人对其的了解.难免有错误之处,希望指正,共同进步.谢谢. 跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找.插入.删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领.而且最重要的一点,就是它的编程复杂度较同类

poj 2513 Colored Sticks(欧拉回路 并查集 路径压缩 字典树)(困难)

Colored Sticks Time Limit: 5000MS   Memory Limit: 128000K Total Submissions: 32545   Accepted: 8585 Description You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a st

【数据结构】前缀树/字典树/Trie

[前缀树] 用来保存一个映射(通常情况下 key 为字符串  value 为字符串所代表的信息) 例如:一个单词集合 words = {  apple, cat,  water  }   其中 key 为单词      value 代表该单词是否存在 words[ 'apple' ] = 存在     而     word[ ' abc' ] = 不存在 图示:一个保存了8个键的trie结构,"A", "to", "tea", "ted

字符串hash与字典树

title: 字符串hash与字典树 date: 2018-08-01 22:05:29 tags: acm 算法 字符串 概述 这篇主要是关于字符串里的 字符串hash 和 字符串字典树,,两个都是简单的套模板的东西,,,理解基本思想就行了,,,对了,,还有一个字典树的的变形--01字典树: 字符串hash 如何求一个字符串的hash值 字符串hash的作用就是将 字符串有效的转化为一个整数 ,,这个转化过程利用的是一个 hash函数 例如,,我们选hash函数为 \(hash[i]=(has

Codeforces 241B Friends 字典树

Friends 首先确定第 m 大的是谁, 建出字典树之后二分去check, 找到第 m 大之后, 在跑一次字典树去统计总和. 为什么这个要取模啊, 卡了我半天. #include<bits/stdc++.h> #define LL long long #define LD long double #define ull unsigned long long #define fi first #define se second #define mk make_pair #define PLL

2014百度之星第三题Xor Sum(字典树+异或运算)

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 4445    Accepted Submission(s): 652 Problem Description Zeus 和 Prometheus 做了一个游戏.Prometheus 给 Zeus 一个集合,集合中包括了N个正整数.随后 Prometheus 将向 Ze

【统计难题】【HDU - 1251】【map打表或字典树】【字典树模板】

思路 题意:题目为中文题,这里不再过多阐述. 思路1:可以在读入单词表的过程中将单词分解,用map将它一 一记录 思路2:利用字典树,这个方法较快些,下面代码中会分别给出数组和结构体指针两种形式的字典树,指针形式的有时可能会因题目内存限制而导致Memory Limit Exceeded,这时就可选择数组形式的.不过对于本题来说不用担心. AC代码 代码1:map打表 #include<bits/stdc++.h> using namespace std; typedef long long L