因为leetcode的题号会变动，所以先记录一下每一题对应的内容。
| 10 | 21.6% | Hard | ||
| 9 | 30.9% | Easy | ||
| 8 | 13.3% | Easy | ||
| 7 | 23.6% | Easy | ||
| 6 | 23.3% | Easy | ||
| 5 | 22.5% | Medium | ||
| 4 | 18.2% | Hard | ||
| 3 | 21.6% | Medium | ||
| 2 | 22.3% | Medium | ||
| 1 | 21.4% | Medium |
第一题，寻找给定数组中，相加等于目标数的两个数字的下标。
这道题其实很简单，它限定死了每个测试用例都只有一对符合的，那样只要找到合适的就可以跳出循环结束，同时也方便了第二种算法hashmap时一个key对应一个value。用最暴力的方法两重循环，i从0到length，j从i+1到length算，这样时间复杂度是O(n2)。那么为了减少时间复杂度，牺牲空间复杂度，使用hashmap这个数据结构即可，从头遍历数组，首先使用target number减去当前位置的数字，得到另一个加数的值，在hashmap中查找这一值即可，如果hashmap中不含有当前位置的数字，将当前位置的数字加入hashmap，代码如下：
public class Solution { public int[] twoSum(int[] nums, int target) { HashMap map =new HashMap(); for(int i=0;i 第二题，将两个像链表一样的结构相加。这道题的逻辑很简单，注意特殊情况的处理即可，比如相加后的进位问题，两个链表长度不一样的问题等。
public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int flag=0; ListNode result=null; ListNode tail=null; while(true){ if(l1==null&l2==null&flag==0) break; int val1=(l1==null)?0:l1.val; int val2=(l2==null)?0:l2.val; int val=val1+val2+flag; flag=val/10; val=val%10; ListNode node=new ListNode(val); if(result==null){ result=node; tail=node; } else{ tail.next=node; tail=node; } l1=(l1==null)?null:l1.next; l2=(l2==null)?null:l2.next; } return result; }} 第三题，查找最长的无重复的子串长度。
当然可以两重循环暴力求解，这里选择时间复杂度较低的方法。无重复的子串必定在两个相同字母之间，从头开始遍历字符串，如果遇到前面出现过的字母，则计算当前子串的长度是否超过了记录的最大值，如果超过了则替换，否则从上一次出现的字母+1的位置开始重新查找最长子串。这里需要一个数组来记录某个字母是否出现过了。
这道题中不只是26个字母，因为这里设定的数组长度为256。
public class Solution { public int lengthOfLongestSubstring(String s) { boolean[] exist=new boolean[256]; int i=0,j=0; int maxLen=0; for(int n=0;n 第四题，查找两个已经排好序的数组中的中位数，时间复杂度为O(log(m+n))。
类似算法在英文的算法教程中出现过，本题中我们是要查找这两个数组中第(m+n)/2和第(m+n)/2+1大的数字，实质上为查找第K大的数字。需要注意的一点，数组长度可能小于k/2，此时该数组直接取最大值比较，而另一个数组的比较位置也不是k/2，即分裂点并不一定都是k/2，要考虑全面情况。具体的方法可以见其他专门讲这一部分的blog吧。主要java不像C/C++用指针操作数组方便，因为比起C/C++的实现多了两个参数用来记录当前数组的起始下标。
public class Solution { public double findK(int[] nums1, int[] nums2, int k, int n1, int n2,int n1_l,int n2_l){ //System.out.println(n1+" "+n2+" "+k); if(n1_l>n2_l){ return findK(nums2,nums1,k,n2,n1,n2_l,n1_l); } if(n1_l==0){ return nums2[n2+k-1]; } if(k==1){ return Math.min(nums1[n1], nums2[n2]); } int point1=Math.min(k/2,n1_l); int point2=k-point1; if(nums1[n1+point1-1] nums2[n2+point2-1]){ return findK(nums1,nums2,k-point2,n1,n2+point2,n1_l,n2_l-point2); } else{ return nums1[n1+point1-1]; } } public double findMedianSortedArrays(int[] nums1, int[] nums2) { int k=nums1.length+nums2.length; if(k%2==1){ return findK(nums1,nums2,k/2+1,0,0,nums1.length,nums2.length); } else return (findK(nums1,nums2,k/2,0,0,nums1.length,nums2.length)+findK(nums1,nums2,k/2+1,0,0,nums1.length,nums2.length))/2; }} 第五题，最长的回文字符串。
这里我用的动态规划，主要原理为，如果i到j是回文的，那么只需要判断i-1和j+1是否相同，若相同，则表明i-1到j+1也是回文的。那么建立一个[i][j]的数组记录即可，当j<i时，本不应该出现这种情况，但是这里默认设置为true，以方便计算其他部分。这里的循环是从j先开始的，并且j=1（循环中i的值需要i+1给出，因此要先计算j）。
public class Solution { public String longestPalindrome(String s) { int len=s.length(); int ss=0,tt=0,max=0; boolean[][] flag=new boolean [len][len]; for(int i=0;i =j) flag[i][j]=true; else flag[i][j]=false; } } for(int j=1;j max)){ ss=i; tt=j; max=j-i+1; } } else flag[i][j]=false; } } return s.substring(ss,tt+1); }} 第六题，zigzag。
最无脑并且时间高效的方法就是开辟数组，怎么摆的怎么存，最后把数组一个个输出即可。
当然这道题也有一定的规律，比如说第一行和最末行的间距是2*(numRows-1)，而其他行的间距是2*(numRows-1)-2*i变化的（i为行号）。
public class Solution { public String convert(String s, int numRows) { if(s.length()==0||numRows<2) return s; int m=2*(numRows-1); String result=""; for(int i=0;i 0&&i 第七题，数字逆序。
看代码即懂，注意点在于①正负 ②溢出
public class Solution { public int reverse(int x) { int temp=Math.abs(x); int result=0; while(temp!=0){ if (result > (Integer.MAX_VALUE - temp % 10) / 10) { return 0; } int number=temp%10; result=result*10+number; temp=temp/10; } int flag=x>0?1:-1; return result*flag; }} 第八题，从string转换成int数。
这一题主要是需要考虑多种情况，比如空格、不该出现的字母、溢出等。
public class Solution { public int myAtoi(String str) { int i=0,sign=1; int result=0; int MAX=2147483647; while(i ='0'&&str.charAt(i)<='9'){ if(sign==1&&result>=(MAX-(str.charAt(i)-'0'))/10){ return MAX; } if(sign==-1&&result>(MAX-(str.charAt(i)-'0'))/10){ return -2147483648; } result=result*10+(str.charAt(i)-'0'); } else{ break; } } return result*sign; }} 第九题，判断回文数字，不能用多余的空间。
既然对空间复杂度有要求，那么只能从两边的数字一对对的算出来比较。例如12321，用12321/1000%10得到最高位1,12321/1%10得到最低位，然后使用12321/100%10得到次高位，12321/10%10得到次低位，以此类推。
public class Solution { public boolean isPalindrome(int x) { if(x==0) return true; if(x<0) return false; int bit=0; int temp=Math.abs(x); while(temp!=0){ bit++; temp/=10; } int point1=1; int point2=(int) Math.pow(10, bit-1); while(point1 第十题，正则表达式。虽然写出来行数不多，但是这个题目本身还是有些难度的，要考虑的特殊情况比较多。此处有两种方法。
第一种是采用纯递归的方法，在没有*的情况下都很简单，一旦存在了*，需要考虑全面，比如说（aaab a*ab），这里a*匹配几个都需要尝试，那么递归时需要尝试（aab ab）（ab ab）（b ab）是否能有匹配的，如果有再继续匹配后面的，一直到字符串结束。这个方法时间复杂度极高。
public class Solution { public boolean isMatch(String s, String p) { if(p.length()==0){ return s.length()==0; } if((p.length()>1&&p.charAt(1)!='*')||p.length()==1){ if(s.length()!=0&&(s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')) return isMatch(s.substring(1),p.substring(1)); else return false; } else{ int i=0; while(s.length()-i>0&&(s.charAt(i)==p.charAt(0)||p.charAt(0)=='.')){ if(isMatch(s.substring(i),p.substring(2))) return true; i++; } return (isMatch(s.substring(i),p.substring(2))); } }} 第二种方法还是动态规划，采用一个二维数组记录，f[i][j]表示s[0...i-1]和p[0...j-1]匹配，那么当p[j-1]不为*时，f[i][j]=f[i-1][j-1]&&s[i-1]==p[j-1]；当p[j-1]为*时，设p[j-2]为x，f[i][j]在满足以下条件时为true：①x重复了0次并且f[i][j-2]为true；②x重复了至少一次，满足了x*x的模式，即s[i-1]==x并且f[i-1][j]为true。该方法时间复杂度较低。
public class Solution { public boolean isMatch(String s, String p) { int m=s.length(),n=p.length(); boolean[][] f=new boolean[m+1][n+1]; f[0][0]=true; for(int i=1;i<=m;i++){ f[i][0]=false; } for(int j=1;j<=n;j++){ f[0][j]=j>1&&p.charAt(j-1)=='*'&&f[0][j-2]; } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(p.charAt(j-1)!='*') f[i][j] = f[i - 1][j - 1] && (s.charAt(i-1)== p.charAt(j-1)|| p.charAt(j-1)=='.'); else f[i][j] = f[i][j - 2] || (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2)=='.') && f[i - 1][j]; } } return f[m][n]; }}