最近开始在Leetcode上刷点题，新手来的，也是第一次接触，分享一下自己的代码，不足之处还有很多。
1.Two Sum
<span style="font-size:14px;">Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution.</span> 要求是给定一个数组和一个数找出数组中和等于给定数的下标，这个是比较简单的问题，最懒得方式是使用循环，由于笔者是第一次写，就直接上了个循环，测试通过，时间复杂度是O（n^2）,显示通过测试的时间是85ms。这个自然是要改进的，后来使用HashTable，键是数组值，值是下标，由于HashTable底层还是基于hashcode的数组，所以速度回很快，代码同样简单，如下：
import java.util.Hashtable; public class Solution { public int[] twoSum(int[] nums, int target) { Hashtable ht=new Hashtable(); for(int i=0;i<nums.length;i++){ int complent=target-nums[i]; if(ht.get(complent)!=null){ return new int[] { (int)ht.get(complent), i }; } ht.put(nums[i],i); } throw new IllegalArgumentException("No two sum solution"); } }2.Write a function to find the longest common prefix string amongst an array of strings.
找出一个字符串数组的最长公共前缀。
难度也属于简单，但相对会复杂一点，因为要考虑的情况要多些。我的思路是使用trie树，这个查的速度很快，构建会稍微麻烦一点，关于trie树的实现我在以前的博客中做了实现，这次依据具体情况并不需要全部。还有一个比较重要的是要对字符串数组做一些预处理，最重要的是剔除""。具体实现代码如下，leetcode上117个测试用时7ms，速度还行。
import java.util.ArrayList; import java.util.List; /** * Created by lenovo on 2016/9/13. */ public class LongestCommonPrefix { private Trie t=new Trie(); public String longestCommonPrefix(String[] strs) { String re=""; if(strs==null){ return ""; } if(strs.length<1){ return ""; } if(strs.length==1){ return strs[0]; } String []noNull=trimNull(strs); if(noNull.length!=strs.length){ return ""; } for(String s:strs){ t.insertWords(s); } if(t.getRoot().childNum>=2){ return ""; } re=t.getLongestPrefix(); return re.trim(); } /** * 去除数组中的"" * @param s * @return */ private String [] trimNull(String []s){ List<String> list=new ArrayList<>(); for(String ss:s){ if(ss!=null&&!ss.trim().equals("")){ list.add(ss); } } String [] re=(String [])list.toArray(new String[list.size()]); return re; } class Trie{ private TrieNode root; public Trie(){ this.root=new TrieNode(); } public void insertWords(String words){ char[] chars=words.trim().toLowerCase().toCharArray(); TrieNode tr=root; for(int i=0;i<chars.length;i++){ char c=chars[i]; int pos=c-'a'; if(tr.children[pos]==null){ TrieNode node=new TrieNode(); node.setVal(c); tr.children[pos]=node; tr.childNum++; } tr=tr.children[pos]; } tr.isend=true; } public String getLongestPrefix(){ String prefix=""; TrieNode t=root; while (t!=null&&t.childNum==1&&!t.isend){ prefix+=t.getVal(); for(TrieNode tt:t.getChildren()){ if(tt!=null){ t=tt; break; } } } prefix+=t.getVal(); return prefix; } public TrieNode getRoot() { return root; } public void setRoot(TrieNode root) { this.root = root; } } class TrieNode{ private char val; private boolean isend; private TrieNode[] children; private int childNum; public TrieNode(){ children=new TrieNode[26]; isend=false; childNum=0; } public char getVal() { return val; } public void setVal(char val) { this.val = val; } public boolean isend() { return isend; } public void setIsend(boolean isend) { this.isend = isend; } public TrieNode[] getChildren() { return children; } public void setChildren(TrieNode[] children) { this.children = children; } } }
