1. 字符串

1.1LeetCode151 Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

解法:

public class Solution {public String reverseWords(String s) {String[] parts = s.trim().split("\\s+");             //注意题目：要去掉前后空格String out = "";
for (int i = parts.length - 1; i >0; i--) {            //因为parts=""也会让parts.length=1,因而把0位最后加上out += parts[i] + " ";                            
}
return out+parts[0];
}}

知识点:

• \s表示 空格,回车,换行等空白符,+号表示一个或多个的意思
• split("\s+") 按空格,制表符等进行拆分
• split(" +") 按空格进行拆分（也就是说只有按空格键流出来的空白才会是拆分的一句），这里用这个也可以

1.2LeetCode557 Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1: 
Input: "Let's take LeetCode contest" 
Output: "s'teL ekat edoCteeL tsetnoc" 

Note: In the string, each word is separated by single space and there will not be any extra space in the string.
解法:

public class Solution {  public String reverseWords(String s) {  String[] strs = s.split(" ");  StringBuilder sb = new   StringBuilder();  for(String str: strs){  StringBuilder temp = new StringBuilder(str);  sb.append(temp.reverse());  sb.append(" ");  }  return sb.toString().trim();  }  
}  

知识点:StringBuilder/StringBuffer 的reverse方法可以把字符串翻转,注意:String没这个方法

1.3统计字符串字母，数字，空格和其他字符个数

package AOP2;  public class TestString {  public static void main(String[] args) {  String test="abc 123 ABC";  TestString(test);  }  private static void TestString(String s) {  // TODO Auto-generated method stub  char[] ch=s.toCharArray();    int digital=0;  int character=0;  int blank=0;  int other=0;  for(int i=0;i<ch.length;i++){    if(ch[i]>='0'&&ch[i]<='9'){    digital++;    }else if((ch[i]>='a'&&ch[i]<='z')||ch[i]>='A'&&ch[i]<='Z'){    character++;    }else if(ch[i]==' '){    blank++;    }else{    other++;    }    }    System.out.println("数字个数："+digital);    System.out.println("英文字母个数："+character);    System.out.println("空格个数："+blank);    System.out.println("其他字符个数："+other);      }  
} 

输出:

数字个数：3  
英文字母个数：6  
空格个数：2  
其他字符个数：0  

1.4把字符串转换成整数

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0

输入
+21474836471a33
输出
21474836470

解法:

public class Solution {public int StrToInt(String str) {if(str == null || str.length() == 0)return 0;int start;int tag ;if(str.charAt(0)=='+'){tag = 1;start = 1;}else if (str.charAt(0)=='-') {tag = 0;start =1;}else {tag = 1;start = 0;}long result = 0;for(int i=start;i<str.length();i++){char tmp = str.charAt(i);if(tmp >= '0'&& tmp<='9'){result = result*10 +(tmp-'0');if(tag == 1 && result>Integer.MAX_VALUE)throw new RuntimeException("上溢出");if(tag == 0 && result<Integer.MIN_VALUE)throw new RuntimeException("下溢出");}else {return 0;}}if(tag == 0)return (int) (-1*result);else {return (int) result;}}   
}

1.5回文字符串

 public static boolean isHuiWen(String text) {int length = text.length();for (int i = 0; i < length / 2; i++) {                  if (text.toCharArray()[i] != text.toCharArray()[length - i - 1]) {  //关键点return false;}}return true;}public static void main(String[] args) {String text = "abccba";System.out.println(isHuiWen(text));}

2.整数

2.1LeetCode7 Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.
解答:

public class Solution {public int reverse(int x) {              long result = 0;       // 注意这里要用long类型                        while (x != 0) {result = result * 10 + x%10;       if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {return 0;}x = x / 10;}return (int)result;
}
}

2.2判断一个数是不是质数

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数

//判断一个数是否是质数（素数）  
public boolean isPrimeNumber(int num){  if(num == 2) return true;//2特殊处理  if(num < 2 || num % 2 == 0) return false;//识别小于2的数和偶数  for(int i=3; i<=Math.sqrt(num); i+=2){  if(num % i == 0){//识别被奇数整除  return false;  }  }  return true;  
} 

为什么i<=Math.sqrt(num)呢？
假定一个数 17 ，那么i=4
3 4 5 6
如果5成立的话，那么和5相乘的这个数一定不比4大！明白了吧

2.3输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示

public class Solution {public int NumberOf1(int n) {int count=0;while(n!=0){n=n&(n-1);count++;}return count;}
}

2.4求一个数的平方根

class Solution {public int mySqrt(int x) {if (0 == x) return 0;int left = 1, right = x, ans=0;while (left <= right) {int mid = left + (right - left) / 2;if (mid <= x / mid) {  //这样写可以防止溢出危险left = mid + 1;ans = mid;         //必须找相乘小于X的才可以} else {right = mid - 1;}}return ans;}
}

3.数组

3.1和为S的两个数字

public class Solution {public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> test=new ArrayList<Integer>();if(array==null || array.length<2){return test;}int i=0;int j=array.length-1;while(i<j){if(array[i]+array[j]==sum){test.add(array[i]);test.add(array[j]);return test;}else if(array[i]+array[j]>sum){j--;   //大于sum说明要找个小点的树，所以j--}else{i++; }}return test;}
}

3.2合并两个排序的整数数组A和B变成一个新的数组

public int[] mergeSortedArray(int[] A, int[] B) {  int []C=new int[A.length+B.length];  int i=0;//A  int j=0;//B  int k=0;//C  while(i<A.length&&j<B.length){  if(A[i]>B[j]){  C[k++]=B[j++];  }else{  C[k++]=A[i++];  }  }  while(i<A.length){  C[k++]=A[i++];  }  while(j<B.length){  C[k++]=B[j++];  }  return C;  }  

3.3Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
  Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3Output: [1,2,2,3,5,6]

解答:

class Solution {public void merge(int[] A, int m, int[] B, int n) {int i=m-1, j=n-1, k=m+n-1;while (i>=0 && j>=0) A[k--]= (A[i]>B[j]) ? A[i--] : B[j--];while (j>=0)         A[k--]=B[j--];}
}

3.4LeetCode136 Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {  
public int singleNumber(int[] nums) {  int result = 0;  for(int i : nums) {  result ^= i;  }  return result;  
}  
} 

3.5数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

public class Solution {public int MoreThanHalfNum_Solution(int [] array) {int len=array.length;if(len<1)return 0;int count=0;Arrays.sort(array);int num=array[len/2];for(int i=0;i<array.length;i++){if(num==array[i])count++;}if(count>len/2)return num;return 0;}
}

4.链表

4.1LeetCode141 Linked List Cycle（判断链表是否带环）

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if((head==null)||(head.next==null))return false;ListNode fast=head,slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow) return true;}return false;}
}

4.2LeetCode142 Linked List Cycle II（判断带环链表起始位置）

/** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */  
public class Solution {  public ListNode detectCycle(ListNode head) {  ListNode slow = head;  ListNode fast = head;  while (fast!=null && fast.next!=null){  fast = fast.next.next;  slow = slow.next;  if (fast == slow){  ListNode slow2 = head;   while (slow2 != slow){  slow = slow.next;  slow2 = slow2.next;  }  return slow;  }  }  return null;  }  }  

正是在入口相遇。

4.3反转链表

public ListNode ReverseList(ListNode head) {ListNode pre = null;ListNode next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;
}

解析:
1.创建两个节点，pre和next;
pre保存已经反转的结点，即已反转链表头节点，next保存待反转的节点。
2.首先我们把head之后的保存起来，即next = head.next;
3.然后我们将head.next指向前面反转好的节点head.next = pre;
4.将反转好的部分保存起来pre = head;

4.4合并排序链表（剑指Offer）

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/* 
public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } 
}*/  
public class Solution {  public ListNode Merge(ListNode list1,ListNode list2) {  if(list1==null)  return list2;  if(list2==null)  return list1;  ListNode t=null;  if(list1.val<list2.val)  {  t=list1;  t.next=Merge(list1.next,list2);           }  else  {  t=list2;  t.next= Merge(list1,list2.next);  }  return t;  }  
}  

5.二叉树

5.1遍历

前序遍历：前序遍历的顺序为先到根节点，再到左节点，最后到右节点；
5 2 1 4 3 6 8 7 9 11 10
中序遍历：中序遍历就是先到左子树、再到根节点、最后到右子树；
1 2 3 4 5 6 7 8 9 10 11
后序遍历：对于后序遍历而言，其访问顺序是先访问左节点，再访问右节点，最后才访问根节点；
1 3 4 2 7 10 11 9 8 6 5
层序遍历：层序遍历就是按照二叉树的层次由上到下的进行遍历，每一层要求访问的顺序为从左到右；
5 2 6 1 4 8 3 7 9 11 10

①前序遍历

递归：

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: Preorder in ArrayList which contains node values.*/ArrayList<Integer> list = new ArrayList<Integer>();public ArrayList<Integer> preorderTraversal(TreeNode root) {if(root == null) return list;list.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return list;}
}

非递归：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<TreeNode>();List<Integer> traversal = new ArrayList<Integer>();if(root!=null){stack.push(root);while(!stack.isEmpty()){TreeNode curr = stack.pop();traversal.add(curr.val);if(curr.right!=null){ stack.push(curr.right); }if(curr.left!=null) { stack.push(curr.left);  }}}return traversal;}
}

②中序遍历

递归:

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: Inorder in ArrayList which contains node values.*/private ArrayList<Integer> List=new ArrayList<Integer>();public ArrayList<Integer> inorderTraversal(TreeNode root) {// write your code hif(root==null){return List;}inorderTraversal(root.left);List.add(root.val);inorderTraversal(root.right);return List;}
}

非递归:

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode cur = root;while(cur!=null || !stack.empty()){while(cur!=null){stack.push(cur);cur = cur.left;}                                     cur = stack.pop();list.add(cur.val);cur = cur.right;}return list;
}

③后序遍历

递归:

public class Solution {/*** @param root: The root of binary tree.* @return: Postorder in ArrayList which contains node values.*/private ArrayList<Integer> List=new ArrayList<Integer>();public ArrayList<Integer> postorderTraversal(TreeNode root) {if(root==null){return List;}postorderTraversal(root.left);postorderTraversal(root.right);List.add(root.val);return List;}
}

非递归:

class Solution {public List<Integer> postorderTraversal(TreeNode root) {LinkedList<Integer> ans = new LinkedList<Integer>();Stack<TreeNode> stack = new Stack<TreeNode>();if (root == null) return ans;stack.push(root);while (!stack.isEmpty()) {TreeNode cur = stack.pop();ans.addFirst(cur.val);if (cur.left != null) {stack.push(cur.left);}if (cur.right != null) {stack.push(cur.right);} }return ans;}
}

④层序遍历

   /** *  * @param root 树根节点 * 层序遍历二叉树，用队列实现，先将根节点入队列，只要队列不为空，然后出队列，并访问，接着讲访问节点的左右子树依次入队列 */  public static void levelTravel(Node root){  if(root==null)return;  Queue<Node> q=new LinkedList<Node>();  q.add(root);  while(!q.isEmpty()){  Node temp =  q.poll();  System.out.println(temp.value);  if(temp.left!=null)q.add(temp.left);  if(temp.right!=null)q.add(temp.right);  }  }  

5.2LeetCode226 Invert Binary Tree（反转二叉树）

     4/   \2     7/ \   / \
1   3 6   9  
to      4/   \7     2/ \   / \
9   6 3   1

解答:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return null;}TreeNode temp=root.left;root.left=root.right;root.right=temp;invertTree(root.left);invertTree(root.right);return root;}
}

5.3对称的二叉树（剑指Offer）

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}
*/
public class Solution {boolean isSymmetrical(TreeNode pRoot){return is(pRoot,pRoot);}boolean is(TreeNode t1,TreeNode t2){if(t1==null&&t2==null) return true;if(t1==null||t2==null) return false;                 //因为有上一个判断,这里说明t1 或 t2有一个为nullif(t1.val==t2.val)return is(t1.left,t2.right)&&is(t1.right,t2.left);  //注意这里，左节点的左孩子应该和右节点的右孩子比else return false;}
}

6.综合算法

6.1LeetCode70 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
解答：

public class Solution {public int climbStairs(int n) {if(n==0||n==1||n==2) return n;int[] m=new int[n];m[0]=1;m[1]=2;for(int i=2;i<n;i++){m[i]=m[i-1]+m[i-2];}return m[n-1];}
}

一次一步或一次两步，那么第M阶可能是由M-1或M-2爬上来的。

6.2变态跳台阶（剑指Offer）

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解法1:

public class Solution {public int JumpFloorII(int target) {if(target==0)return 0;if(target==1)return 1;elsereturn 2*JumpFloorII(target-1);}
}

这个题可以推导一下：
f(2)=f(0)+f(1);
f(3)=f(2)+f(1)+f(0)=2f(2);
…可推导 f(n)=2f(n-1);
解法2：

public class Solution {public int JumpFloorII(int target) {if(target==0) return 0;return (int)Math.pow(2,target-1);}
}

每个台阶都有跳或者不跳

6.3用两个栈实现队列（剑指Offer）

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
先知道一个最基本的：队列先进先出，栈先进后出

import java.util.Stack;public class Solution {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {stack1.push(node);}public int pop() {if(stack1.empty()&&stack2.empty())              throw new  RuntimeException("Queue is empty!");if(stack2.empty()){while(!stack1.empty())stack2.push(stack1.pop());}return stack2.pop();   }
}

6.4求1+2+3+…+n(剑指Offer)

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

public class Solution {public int Sum_Solution(int n) {int sum = n;boolean flag = (sum>0)&&((sum+=Sum_Solution(--n))>0);return sum;}
}

6.5(面试很容易问)二分查找算法

package collectionSort;public class TestSort {public static int binarySearch(int[] arr,int des){int low = 0;int high = arr.length-1;while(low<=high){int middle = (low+high)/2;if (arr[middle] == des) {return middle;}else if (arr[middle]<des) {low = middle+1;}else {high = middle-1;}}return -1;   //循环完如果}public static void main(String[] args){int[] arr = {1,2,3,4,5,6,7,8,11,15,17};int des = 15;System.out.println(binarySearch(arr, des));}
}

6.6斐波那契数列

public class Solution {public int Fibonacci(int n) {int a=1,b=1,c=0;if(n<0){return 0;}else if(n==1||n==2){return 1;}else{for (int i=3;i<=n;i++){c=a+b;b=a;a=c;}return c;}}
}