找了一段時間的實習，總結一下LeetCode上面試出現頻率比較高的題，只總結一部分，後續還會繼續更新。
題意是給出一個數組，輸出和為k的兩個數。數組為無序的。
這道題的解題思路是先把數組排序，再用兩個指針，分別指向頭和尾，並算出頭和尾的和s，再把s與k比較，如果s小於k，頭指針往後移，如果s大小k，尾指針往前移。直到找到為止。如果頭尾指針相遇還沒找到，則證明不存在。
代碼如下：
public class Main {
public static void main(String[] args){
int[] a = {1,3,2,1,4,5};
printK(a,5);
}
public static void printK(int[] array,int k){
if(array == null||array.length<=0){
return ;
}
int length = array.length;
Arrays.sort(array);
int start = 0;
int end = length - 1;
while(start < end){
while(array[start] == array[start+1]){
start++;
}
while(array[end] == array[end-1]){
end--;
}
if(array[start] + array[end] == k){
System.out.println(start+" "+end);
start ++;
}
if(array[start]+array[end] < k){
start++;
}
if(array[start]+array[end] > k){
end--;
}
}
//System.out.println("can't find");
}
}
題意：從給定的數組中找三個數，讓它們的和為0。輸出所有可能。
如[1,3,-1,0,-3],那麼輸出[1,-1,0],[3,0,-3]。
思路：這個其實是以第一個題目為基礎，首先進行排序。然後從數組第一位開始遍歷，如第一位為1，在剩余後面的數組[3,-1,0,-3]中找出和為-1的兩個數。用的就是第一題的思路。
代碼：
public class Main {
public static void main(String[] args){
int[] array = {-1, 0,1,2,-1,-4};
print3Num(array, 0);
}
public static void print3Num(int[] array,int k){
Arrays.sort(array);
int length = array.length;
if(array == null||array.length<=0){
return ;
}
for(int i = 0;i < length;i++){
if(i k){
end--;
}
}
}
}
題意：有n級樓梯，你一次可以爬一級或兩級，問爬上n級樓梯有多少種爬法。這是我一個同學面騰訊時被問到的問題。典型的斐波那契數列。
思路：因為一次你能爬一級或兩級，所以除去第一次，n級的爬法f(n)可以等於f(n-1)+f(n-2)。求的就是斐波那契數列。
代碼：
public class Main {
public static void main(String[] args){
System.out.print(climbStair(5));
}
//遞歸
public static int climbStairs(int n) {
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return climbStairs(n-1)+climbStairs(n-2);
}
//非遞歸
public static int climbStair(int n) {
int num1 = 1;
int num2 = 2;
int sum = 0;
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
for(int i = 2;i < n;i++){
sum = num1+num2;
num1 = num2;
num2 = sum;
}
return sum;
}
}
分別實現了遞歸和非遞歸兩種方式。
題意：合並兩個排序的鏈表
思路：先選出頭小的節點作為新鏈表的起點，然後開始比較兩個鏈表，那個值小就把鏈表指向它，被指向的鏈表往下移一位，新鏈表也要指向當前最後一個節點。當有一個鏈表遍歷完了，就把另一個鏈表剩余部分全部賦到新鏈表的尾部，直接看代碼更清晰。
public static ListNode merge(ListNode head1,ListNode head2){
if(head1 == null&& head2 == null){
return null;
}
if(head1 == null){
return head2;
}
if(head2 == null){
return head1 ;
}
ListNode head = null;
if(head1.val
五、Merge Sorted Array題意：給兩個數組n1[1,2,3],n2[3,4,5],把n2合並到n1中去，n1長度>=n1.length+m.length。
思路：這道題是不允許多用空間的。最後我想出的方法是從尾部開始比較，大的放到n1數組的最後一位。並把大數所在的數組尾部指針往前移，直到比較結束後，所有數就自然的在n1中排序了。
代碼如下：
public class Main {
public static void main(String[] args){
int[] a = {0};
int[] b = {1};
merge(a,0,b,1);
for(int i = 0;i < a.length;i++)
System.out.print(a[i]+" ");
}
public static void merge(int[] nums1, int m, int[] nums2, int n) {
if(nums1==null||nums2==null||m<0||n<0){
return;
}
int index = m+n-1;
int index1 = m-1;
int index2 = n-1;
while(index1>=0&&index2>=0){
if(nums1[index1]=0){
nums1[index--] = nums1[index1--];
}
while(index2>=0){
nums1[index--] = nums2[index2--];
}
}
}
六、Valid Palindrome題意：驗證一個字符串是否為回文，只看字母（忽略其它字符），不分大小寫。如“A man, a plan, a canal: Panama”就是一個回文，從頭讀和從尾往前讀讀出來是一樣的。
思路：這道題思路其實很直接，就是兩個指針，一個指向頭部一個指向尾部，頭部依次往後走，尾部依次往前走，一個個比，如果有不同就不是回文，否則如果兩指針相遇了還沒有不同的，就是回文。
代碼：
public class Main {
public static void main(String[] args){
System.out.println(isPalindrome("......a....."));
System.out.println(isPalindrome("09"));
}
public static boolean isPalindrome(String s) {
s = s.toLowerCase();
if(s.length()<=1){
return true;
}
int length = s.length();
int start = 0;
int end = length-1;
while(start < end){
while(start='a'&&s<'z'||s>='0'&&s<='9'){
// s=(char)(s-'a'+'A');
return true;
}
else{
return false;
}
}
}
七 Valid Parentheses題意：驗證括號是否能正常閉合，如“()[]{}”是可以正常閉合的，但“(]”就是不正常的。
思路：用一個棧，如果是左括號入棧，如果是右括號，則出棧與右括號比，如果最後棧空了，也沒的右括號了，則證明正確。
代碼寫得有點傻，可以繼續優化：
public class Main {
public static void main(String[] args){
System.out.println(valid("["));
}
public static boolean valid(String str){
if(str.length() <= 0){
return false;
}
Stack stack = new Stack();
int length = str.length();
for(int i = 0;i < length;i++){
if(str.charAt(i) == '{'||str.charAt(i) == '['||str.charAt(i)=='('){
stack.push(str.charAt(i));
}
if(str.charAt(i)==')'){
if(!stack.isEmpty()){
char c = stack.pop();
if(c != '('){
return false;
}
}else{
return false;
}
}
if(str.charAt(i)=='}'){
if(!stack.isEmpty()){
char c = stack.pop();
if(c != '{'){
return false;
}
}else{
return false;
}
}
if(str.charAt(i)==']'){
if(!stack.isEmpty()){
char c = stack.pop();
if(c != '['){
return false;
}
}else{
return false;
}
}
}
if(stack.isEmpty())
return true;
else{
return false;
}
}
}
八 Pow(x, n)題意：就是實現一個Pow(x,n)乘方函數。
思路：首先要注意負數和倒數的問題。其次就是要合理的利用己經算出來的值來算下一個，如計算2^4，我們計算了2*2=4之後，就可以用4*4來計算2^4，減少計算的次數。
代碼說話：
public class Main {
public static void main(String[] args){
System.out.println(pow(2,2));
}
public static double pow(double d,int n){
boolean flag = false;
boolean zhisuFlag = false;
int e = n;
if(n<0){
e = -n;
zhisuFlag = true;
if(d == 0.0){
return 0;
}
}
if(n%2==1&&d<0){
flag = true;//負數
}
double result = power(d, e);
if(zhisuFlag){
result = 1/result;
}
if(flag){
result = -result;
}
return result;
}
public static double power(double d,int n){
if(n == 1){
return d;
}
if(n == 0){
return 1;
}
double result = d;
int k = 1;
int pn = n;
while (n/2>0) {
n = n/2;
result = result*result;
k = k*2;
}
result =result * power(pn, n-k);
return result;
}
}
九 Generate Parentheses題意：給一個整數n，輸出n對小括號所能組成的所有正常閉合的組合。如給出整數3，則輸出 “((()))”, “(()())”, “(())()”, “()(())”, “()()()”。
思路：用遞歸實現所有情況，先定義left存左括號的個數，right存右括號數，首先輸出一個“（”，如果剩余右括號多於左括號，可以輸出右括號，否則只能輸出左括號。
代碼如下：
public class Main {
public static void main(String[] args){
generateParenthesis(1);
}
public static List generateParenthesis(int n) {
ArrayList aList = new ArrayList();
if(n <= 0){
return null;
}
getList(n,n,"",aList);
return aList;
}
public static void getList(int left,int right,String curStr,List aList){
if(left > right){
return;
}
if(left == 0&&right == 0){
aList.add(curStr);
}
if(left > 0){
getList(left-1, right, curStr+"(", aList);
}
if(right > 0){
getList(left, right-1, curStr+")", aList);
}
}
}
十、Validate Binary Search Tree題意：判斷一棵樹是不是BST樹。即判斷一棵樹的左節點是否全比根節點小，所有右節點是否全比根節點大。
思路一：最直接的方法是用中序遍歷，發現不是有序的就不是BST，如果是有序那就是BST。
代碼如下：
public static boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
boolean a = isValidBST(root.left);
pre = cur;
cur = root;
if(pre!=null&&pre.val>=cur.val){//要考慮到與子節點相同的情況
return false;
}
boolean b = isValidBST(root.right);
return a&&b;
}
思路二：遞歸遍歷子節點，在遍歷過程中分別給左子樹和右子樹設置左屏障和右屏障，什麼意思呢？就是保證左子樹的右屏障為根節點，也就是最大值小於等於根節點。右子樹左屏障為根節點的值，即最小值大小等於根節點的值。
代碼如下：
public static boolean isValidBST(TreeNode root) {
int left = Integer.MIN_VALUE;
int right = Integer.MAX_VALUE;
if(root == null){
return true;
}
if(root.left == null&&root.right==null){
return true;
}
return validBinary(root, left, right);
}
public static boolean validBinary(TreeNode head,int left,int right){
if(head == null){
return true;
}
if(head.val<=left)
{
return false;
}
if(head.val>=right)
{
return false;
}
return validBinary(head.left,left,head.val)&&validBinary(head.right,head.val,right);
}
就到這吧，整理的好累，其實LeetCode刷了有一些了，但常見的筆試面試題也就那麼幾類，個人覺得應該不會出太難。
