12、字符串处理算法总结：
理解常用字符串匹配算法的原理、实现、设计意图和应用场景，搞清楚能解决什么问题。
12.1、用Java写一个递归遍历目录下面的所有文件
思路：利用File类中的一个listFiles将该文件路径下所有的文件全部列出来，然后通过循环遍历
public static void showDirectory(File file){ File[] files = file.listFiles(); for(File a:files){ System.out.println(a.getAbsolutePath()); if(a.isDirectory()){ showDirectory(a); } } }
12.2、给定一个txt文件，如何得到某字符串出现的次数
File file = new File("E://test.txt"); InputStream is = new FileInputStream(file); byte b[] = new byte[1024]; int a = is.read(b); String str[] = new String(b,0,a).split(""); int count = 0; for(int i = 0;i<str.length;i++){ if("a".equals(str[i])) count++; } System.out.println(count);
12.3、实现一个字符集，只包含a～z这26个英文字母的Trie树（也称为字典树/键树）
- 暂时在项目中找不到使用场景。
public class TrieNode { public char data; public TrieNode[] children = new TrieNode[26]; public boolean isEndingChar = false; public TrieNode(char data) { this.data = data; } } public class Trie树 { private TrieNode root = new TrieNode('/'); //存储无意义字符 // 往Trie树中插入一个字符串 public void insert(char[] text) { TrieNode p = root; for (int i = 0; i < text.length; ++i) { int index = text[i] - 'a'; if (p.children[index] == null) { TrieNode newNode = new TrieNode(text[i]); p.children[index] = newNode; } p = p.children[index]; } p.isEndingChar = true; } // 在Trie树中查找一个字符串 public boolean find(char[] pattern){ TrieNode p = root; for (int i = 0; i < pattern.length; ++i){ int index = pattern[i] - 'a'; if (p.children[index] == null){ return false; // 不存在pattern } p = p.children[index]; } if (p.isEndingChar == false) return false; // 不能完全匹配，只能匹配前缀 else return true; // 找到pattern } }
12.4、实现朴素的字符串匹配算法(暴力匹配算法/BF算法)
- 思路：我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串 我们把主串的长度记作n，模式串的长度记作m。因为我们是在主串中查找模式串，所以n>m
- 我们在主串中，检查起始位置分别是0、1、2…n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。
JDK提供的Utils方法：
// 时间复杂度：O(n*m) public static bool contains(String a) { String aa = 'jd.com'; if(a.contains(aa)) { return true; } return false; }
// 暴力匹配算法 时间复杂度是O(n*m) public static int bF(String a, String b) { int m = a.length(), n = b.length(), k; char[] a1 = a.toCharArray();//主串 char[] b1 = b.toCharArray();//模式串 for(int i = 0; i <= m - n; i++){ k = 0; for(int j = 0; j < n; j++){//n为模式串的长度 if(a1[i + j] == b1[j]){ k++;//k的值表示匹配的长度 }else break; } if(k == n){ return i; } } return -1; }
思路：我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了，效率取决于哈希算法的设计方法。
public static int rK(String a, String b){ int m = a.length(), n = b.length(), s, j; int[] hash = new int[m - n + 1];//主串可以分解为子串的个数 int[] table = new int[26]; char[] a1 = a.toCharArray(); char[] b1 = b.toCharArray(); s = 1; //将26的次方存储在一个表里，取的时候直接用,虽然溢出，但没啥问题 for (j = 0; j < 26; j++) { table[j] = s; s *= 26; } for (int i = 0; i <= m - n; i++) {//主串 s = 0; for (j = 0; j < n; j++) { s += (a1[i + j] - 'a') * table[n - 1 - j];//table为倒序 } hash[i] = s; } s = 0; for (j = 0; j < n; j++) {//模式串 s += (b1[j] - 'a') * table[n - 1 - j]; } for (j = 0; j < m - n + 1; j++) {//两者的hash值比较 if (hash[j] == s) { return j; } } return -1; }
// sunday算法 时间复杂度 O(n) /** * 判断子串中是否存在末尾下一个位置对应的父串的字符 * 每次从后往前匹配，为了不遗漏可能的匹配，应该是跳到使得子串中最右一个字符与父串中的该字符对应， * 这样跳过的距离最小，且是安全的。 */ private static int contains(char[] sonArray, char ch) { for (int i = sonArray.length - 1; i >= 0; i--) { if (sonArray[i] == ch) { return i; } } return -1; } private static int search(String source, String target) { //这里转为char数组要更方便些 char[] fatherArray = source.toCharArray(); char[] sonArray = target.toCharArray(); int fatherLength = fatherArray.length; int sonLength = sonArray.length; int i = 0, j = 0; //+ j是可能会出现最后一次移动father剩余长度与son长度不一致的情况 while (i <= fatherLength - sonLength + j) { if (fatherArray[i] != sonArray[j]) { //如果父串与子串当前字符不相等 if (i == fatherLength - sonLength + j) { //这里说明子串已经是在和父串中最后可能想等的字符比较过了，并且后面也没有可比较的了，所以返回 return -1; } //如果父串的中间部分与子串匹配，且结果不相等 //就从子串最后面开始，找出子串最后一位的下一位对应父串的字符在子串中是否存在 int pos = contains(sonArray, fatherArray[i - j + sonLength]); if (pos == -1) { //不存在则直接跳到再下一位，子串从头开始 i = i - j + sonLength + 1; j = 0; } else { //存在则将这个字符与子串最右边与它相同的字符对其,并再次从头开始比较 i = i + sonLength - pos - j; j = 0; } } else { //如果父串与子串当前字符相等 if (j == sonLength - 1) { //如果比较到了子串的最后一位，说明已经存在 return i - j; } else { //不是子串最后一位，则进行下一个字符的对比 i++; j++; } } } return -1; } // 测试 public static void main(String[] args) { String source = "http://www.cg.yixiubao.tv.com?itemId=1111"; String target = "cg.yixiubao.tv"; System.out.println(search(source, target)); }
算法思想：编程中一定会出现的问题：变种非常多(反转/反转单词/子串/最长子串/最长子序列)
- 1、用固定支付替换字符串中的空格
使用stringbuffer的append（） - 2、验证是否是回文串
只考虑字母和数字字符，先用isletterOrDigit来跳过其他字符，第一个字符与最后一个字符依次比较，然后I++，J– - 3、数组的最长公共前缀
先用数组的sort方法升序排列，找出数组第一个字符串和最后一个的长度，按小的计算，比较字符串的元素，若相等就
保存在Stringbuffer中 - 4、最长回文串 区分大小写
字符出现次数为双+一个只出现一次的字符，遍历数组，字符在hashset中就移除，count++，否则，添加进去
5、反转字符串，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题 输入：[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]
public void reverseString(char[] s){ int l = 0; int r = s.length-1; int mid = (s.length)/2; while(l != mid ){ char temp = s[l]; s[l] = s[r]; s[r] = temp; l++; r--; } }//时间复杂度O(n)
StringTokenizer详解：(允许应用程序将字符串分解为标记)
1、int countTokens() 计算在生成异常之前可以调用此 tokenizer 的 nextToken 方法的次数；
2、boolean hasMoreElements() 返回与 hasMoreTokens 方法相同的值；
3、String nextToken(String delim) 返回此 string tokenizer 的字符串中的下一个标记。
下面是一个使用 tokenizer 的实例。代码如下：
StringTokenizer st = new StringTokenizer("this is a test"); while (st.hasMoreTokens()) { System.out.println(st.nextToken()); }
输出以下字符串： this is a test
StringTokenizer出于兼容性的原因而被保留，建议使用String的split方法或java.util.regex包。建议
String[] result = "this is a test".split("\\s"); for (int x=0; x<result.length; x++) System.out.println(result[x]);
输出以下字符串： this is a test
6、 翻转字符串里的单词 输入: “the sky is blue” 输出: “blue is sky the”
public String reverseWords(String s) { String[] strArr = s.split("\\s+"); //正则匹配空格 StringBuilder sb = new StringBuilder(); for(int i=strArr.length-1;i>=0;i--){ //倒序遍历，添加空格 sb.append(strArr[i]); sb.append(" "); } return sb.toString().trim();//去除首尾多余空格，toString返回 }
7、字符串转换整数 请你来实现一个 atoi 函数，使其能将字符串转换成整数
该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数
例如：输入: " -42" 输出: -42 第一个非空白字符为 ‘-’, 它是一个负号
输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字
public int myAtoi(String str) { int i = 0; int len = str.length(); boolean flag = true;//使用flag指定数值正负 while (i < len && str.charAt(i) == ' ') { i++; } if (i < len) { if (i == len || !Character.isDigit(str.charAt(i))) { if (str.charAt(i) == '+') { i++; } else if (str.charAt(i) == '-') { flag = false; i++; } else { return 0; } } } else { return 0; } StringBuilder sb = new StringBuilder(); if (i < len && Character.isDigit(str.charAt(i))) { while (i < len && Character.isDigit(str.charAt(i))) { sb.append(str.charAt(i)); i++; } } else return 0; String string = sb.toString(); int parseInt = 0; try { parseInt = Integer.parseInt(string); } catch (Exception e) { if (flag == true) { parseInt = Integer.MAX_VALUE; } else { parseInt = Integer.MIN_VALUE; } } if (flag == true) return parseInt; else return -parseInt; }
13、海量数据的处理思路问题
13.1、大数据量的问题：
10w个id，怎么去100亿个id里找数据，怎么做能更快，分库分表？
13.2、有10G大小的文件，每行记录一条运单信息，机器大小是500M，求出出现次数最多的前1000条运单号，给出思路。
典型的Top K算法(分治思想)
1、先对这批海量数据预处理，在O(N)的时间内用Hash表完成分组(相同单号被分配到Hash桶中的同一条链表中) %20 20个文件，每个文件500M 堆的大小取决于机器的内存值500M;
2、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK
3、对每个堆中的TOPk，计算出前k个数（归并排序）
13.3、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
方案1：可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M
遍历文件b，采取和a相同的hash函数将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，
不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可
求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
13.4、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
方案1：用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存内存，还可以接受。
然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素
13.5、怎么在海量数据中找出重复次数最多的一个？
方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求100w个数中找出最大的100个数
用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)
13.6、如果你所在的省有50万考生，如何通过成绩快速排序得出名次呢？
13.7、假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
13.8、假设我们有1000万个整型数据，每个数据占8个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这1000万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过100MB，你会怎么做呢？
13.9、如何在海量数据中快速查找某个数据？(索引)(在计算机组成中称为寻址)
MySQL底层依赖的是B+树这种数据结构，Redis这样的Key-Value数据库中的索引，又是怎么实现的呢？底层依赖的又是什么数据结构呢？
- 索引存储位置：在内存还是硬盘
- 单值查找还是区间查找？
单关键词查找还是多关键词组合查找？对于结构化数据的查询需求(MYSQL)，针对多个关键词的组合，建立索引；对于非结构数据的查询需求(搜索引擎)，以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。
索引的维护成本。因为在原始数据动态增删改的同时，也需要动态的更新索引。 - 构建索引常用的数据结构？
对动态数据建立索引：散列表、红黑树、跳表、B+树；位图、布隆过滤器可以作为辅助索引；有序数组可以用来对静态数据构建索引。 - 散列表：一些键值数据库，比如Redis、Memcache，就是使用散列表来构建索引的，增删改查的性能非常好，时间复杂度为O(1)，这类索引，一般都构建在内存中；
- 红黑树：作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是O(logn)，也非常适合用来构建内存索引。Ext文件系统中，对磁盘块的索引，使用的是红黑树；
- B+树：比起红黑树来说，更加适合构建存储在磁盘中的索引，B+树是一个多叉树，所以，对相同个数的数据构建索引，B+树的高度要低于红黑树。当借助索引查询数据的时候，
读取B+树索引，需要的磁盘IO次数非常更少，关系型数据库的索引：如Mysql、oracle，使用的是B+树建立索引 - 跳表：支持快速添加、删除、查找数据。而且通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis中的有序集合，就是用跳表来构建的
布隆过滤器：对于判定存在的数据，有可能并不存在，但是对于判定不存在的数据，那肯定就不存在。内存占用非常少
有序数组：如果数据是静态的，也就是不会有插入、删除、更新操作，那我们可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据 - 你知道基础系统、中间件、开源软件等系统中，有哪些用到了索引吗？这些系统的索引是如何实现的呢？
1、区块链拿以太坊来说，存储用的leveldb，数据存储用的数据结构是帕特利夏树，是一种高级的trie树，很好的做了数据的压缩；
2、消息中间件像kafka这种，会去做持久化，每个partition都会有很多数据，会有大量数据存储在磁盘中，所以每个partition也会有个索引，方便去做快速访问。
3、ES中的倒排索引用了trie树(一种专门处理字符串匹配的数据结构),对每个需要索引的key维护了一个trie树,用于定位到这个key在文件中的位置,然后直接用有序列表直接去访问对应的documents
trie树(两个操作：一个将字符串插入到Trie树的过程。另一个是在Trie树中查询一个字符串)
Q:Trie树：如何实现搜索引擎的搜索关键词提示功能？(为了方便快速输入，当你在搜索引擎的搜索框中，输入要搜索的文字的某一部分的时候，搜索引擎就会自动弹出下拉框，里面是各种关键词提示)
A:‘字典树’。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题.
Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起（感觉有点像霍夫曼编码：左0右1）
时间复杂度：O(k) k为字符串长度
应用场景：自动输入补全，比如输入法自动补全功能、IDE代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等
Q:Trie树应用场合对数据要求比较苛刻，比如字符串的字符集不能太大，前缀重合比较多等。如果现在给你一个很大的字符串集合，比如包含1万条记录，如何
通过编程量化分析这组字符串集合是否比较适合用Trie树解决呢？也就是如何统计字符串的字符集大小，以及前缀重合的程度呢？
A:依次读取每个字符串的字符构建 Trie 树，用散列表来存储每一个节点。每一层树的所有散列表的元素用一个链表串联起来，求某一长度的前缀重合，在对应树层级上遍历该层链表，
求链表长度，除以字符集大小，值越小前缀重合率越高。遍历所有树层级的链表，存入散列表，最后散列表包含元素的个数，就代表字符集的大小
如何存储一个Trie树？
public class Trie { private TrieNode root = new TrieNode('/'); //存储无意义字符 //往Trie树中插入一个字符串 public void insert(char[] text) { TrieNode p = root; for (int i = 0; i < text.length; ++i) { int index = text[i] - 'a'; if (p.children[index] == null) { TrieNode newNode = new TrieNode(text[i]); p.children[index] = newNode; } p = p.children[index]; } p.isEndingChar = true; } //在Trie树中查找一个字符串 public boolean find(char[] pattern) { TrieNode p = root; for(int i = 0; i < pattern.length; ++i) { int index = pattern[i] - 'a'; if (p.children[index] == null) { return false; //不存在pattern } p = p.children[index]; } if(p.isEndingChar == false) return false; //不能完全匹配，只是前缀 else return true; //找到pattern } public class TrieNode { public char data; public TrieNode[] children = new TrieNode[26]; public boolean isEndingChar = false; public TrieNode(char data) { this.data = data; } } }
13.10、并行计算：利用并行处理提高算法的执行效率(分治的思想)
算法无法再继续优化的情况下，如何来进一步提高执行效率呢？可以使用一种简单但好用的优化方法，那就是并行计算。
- 1、并行排序 对时间复杂度为O(nlgn)的三种排序算法：归并/快排/堆排进行并行化处理
如：归并排序时，将8G的数据先划分为16个小的数据集合，然后多线程处理，最后将这16个有序集合合并；快速排序中，先扫描一遍数据，遭到数据所处的范围区间，
同样划分为16个小区间，并行进行排序，等到16个线程都执行借宿之后，得到的数据就是有序数据了。 - 2、并行查找 散列表，给动态数据构建索引，在数据不断加入的时候，散列表的装载因子就会越来越大。为了保证散列表性能不下降，我们就需要对散列表进行动态扩容，
可以将数据随机分割成k份（比如16份），每份中的数据只有原来的1/k，然后我们针对这k个小数据集合分别构建散列表，增加存储空间的利用率。
13.11、断点续传思路和算法
在http头文件里面保存了 content 和 content-type 标签，用于记录传输文件的字节段。
