给定一个string数组article和数组大小n及一个待统计单词word，请返回该单词在文章中的出现频数。
保证文章的词数小于等于1000。
//法1 ：常规对比做法（我的做法）
//也想过 用map等集合来统计 ，但是这个查找数据量不大，没必要
import java.util.*;
public class Frequency{
public int getFrequency (String [] article,int n,String word){
int count=0;
for(int i=0;i<n;i++){
if(article[i].equals(word)) //字符串比较值相等时用equals.
count++;
}
return count;
}
}
//法2 //为了节省时间，首先比较目标词和文章中的词汇长度是否相同，若相同，再进一步比较是否是同一个词，//从string数组第一个遍历，就可以检查出来了，因为比较是逐个字母比较，所以长度不同直接排除，//可以节省不少时间。 public int getFrequency(String [] article,int n,String word){ int i=0,num=0; while(i<n){ if(article[i].length()==word.length()) if(article[i].equals(word)){ num++; } i++; } return num; }法3 ：
注意：这个方法只适用于字符串，不适用于结构体这种对象，这种方法也比较消耗内存，字符串上的效率是极高的，比map、手写红黑树等好多了，还容易实现。
查询次数只有一次，让这个方法看着太呆萌了——复杂度是O(n*length+length)，在这种情况下和暴力没什么区别。
但是如果是查询q次，这种方法的复杂度是O(n*length+q*length)，比暴力的O(n*q*length)好多了。
这里选用的数据结构，叫字典树(Trie)。插入和查找的时间复杂度只取决于你的当前单词的长度O(length)。
但是Trie比较消耗内存，怎么办？
搜索引擎实现的时候，一种变通方法是，借用二叉搜索树的思路实现一个三叉Trie——其中查询串中当前字符比指向的节点字符小的时候，去左儿子，大的时候去右儿子，相等的时候则向下走一层。
统计一个单词出现的次数？这个在Trie上很简单。插入的时候，每个节点新增一个count域，记录以这个节点为结尾的单词数有几个，就好了。
代码如下：
import java.util.*;
public class Frequency {
public int getFrequency(String[] article, int n, String word) {
if(n <= 0 || word == null || word.length() == 0){
return 0;
}
TrieNode root = new TrieNode();
for(String str : article) {
root.insert(str, 0);
}
TrieNode ans = root.search(word, 0);
if(ans != null && ans.isWord == true) {
return ans.cnt;
}
return 0;
}
}
class TrieNode {
private TrieNode[] children;
public boolean isWord;
public int cnt;
public TrieNode() {
children = new TrieNode[52];
isWord = false;
cnt = 0;
}
public void insert(String word, int index) {
if(index == word.length()) {
isWord = true;
++cnt;
return;
}
int c = word.charAt(index) - 'a';
if(children[c] == null) {
children[c] = new TrieNode();
}
children[c].insert(word, index + 1);
}
public TrieNode search(String word, int index) {
if(index == word.length()) {
return this;
}
int c = word.charAt(index) - 'a';
if(children[c] == null) {
return null;
}
return children[c].search(word, index + 1);
}
}
2. 请设计一个高效算法，找出数组中两数之和为指定值的所有整数对。
给定一个int数组A和数组大小n以及需查找的和sum，请返回和为sum的整数对的个数。保证数组大小小于等于3000。
//法1 ：（我的方法）常规循环做法 时间复杂度为O(n*n);
import java.util.*;
public class FindPair{
public int countPairs(int [] A,int n,int sum){
//常规遍历数组求和
int num=0;
for(int i=0;i<n;i++){
for(intj=i+1; j<n;j++){
if(A[i]+A[j]==sum)
num++;
}
}
return num;
}
}
//法2 ：（我自己有思路，但是没有考虑到重复数字的情况，出现错误） //将数组排序之后 用前后两个指针去往中间夹 就是需要注意存在相同元素的情况 //往中间夹 begin和end不同时 若两边分别存在重复的数字 2 2 3 3 则两者数目相乘为配对数量2*2=4种//若begin和end指向的数字是相同的数 如2 2 2 2 则可能配对数量为C(4,2)=4*(4-1)/2; import java.util.*;public class FindPair{ public int countPairs(int [] A,int n,int sum){ int start=0,end=n-1,count=0; Arrays.sort(A); while(start<end){ if(A[start] +A[end]<sum) start++; else if(A[start]+A[end]>sum) end--; else{ if(A[start]==A[end]){ int t=end-start+1; count+=(t*(t-1)/2); break; }else{ int left=start+1; int right=end-1; int countLeft=1; int countRight=1; while(A[left]==A[start]){ countLeft++; left++; } while(A[right]==A[end]){ countRight++; end--; } count+=(countLeft*countRight); start=left; end=right; } } } return count; }}
//法3 ：看到其他博客里的思路 //用哈希表来解决import java.util.*;public class FindPair{ public int countPairs(int [] A, int n,int sum){ HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>(); //创建一个hash表 int count=0; for(int i=0;i<n;i++){ count+=getTimes(hm,sum-A[i]);hashMap.put(A[i], getTimes(hm, A[i]) +1);} return count; } private Integer getTimesCount(HashMap<Integer,Integer> hm,Integer word){ Integer time=hm.get(word); return time==null? 0:time; }}