- 單例模式
public class No2 {
/**
* 設計一個類且蓬，我們只能生成該類的一個實例。
*/
public static void main(String[] args) {
}
}
//餓漢式 線程安全
class A {
private static final A a = new A();
private A() {
}
public static A getInstance() {
return a;
}
}
//懶漢式 線程安全寫法
class B {
private static B b = null;
private B() {
}
public static B getInstance() {
if (b == null) {
synchronized (B.class) {
if (b == null)
b = new B();
}
}
return b;
}
}
//真正的線程安全是加上volatile，防止初始化對象和instance指向內(nèi)存兩個步驟重排序
class C {
private volatile static C instance;
public static C getInstance() {
if (instance == null) {
synchronized (C.class) {
if (instance == null) instance = new C(); // instance為volatile死宣，現(xiàn)在沒問題了
}
}
return instance;
}
}
//靜態(tài)內(nèi)部類的方法
class InstanceFactory {
private static class InstanceHolder {
public static C instance = new C();
}
public static C getInstance() {
return InstanceHolder.instance;//這里將導致InstanceHolder類被初始化
}
}
- 數(shù)組中重復的數(shù)字
/**
* Created by ryder on 2017/6/11. * 一個長度為n的數(shù)組怎栽，值的范圍在0~n-1內(nèi)，有一個或多個數(shù)字重復，求其中任意一個
*/
public class P39_DuplicationInArray {
//方法一：暴力求解谋逻，不會修改原始數(shù)據(jù)殷绍，時間復雜度o(n^2)染苛，空間復雜度o(1)
public static int getDuplication(int[] data) {
if (data == null || data.length < 2) return -1;
for (int i = 0; i < data.length - 1; i++) {
for (int j = i + 1; j < data.length; j++) {
if (data[i] == data[j]) return data[i];
}
}
return -1;
}
//方法二：排序，會修改原始數(shù)據(jù)主到，時間復雜度o(nlogn)茶行，空間復雜度o(1)
public static int getDuplication2(int[] data) {
if (data == null || data.length < 2)
return -1; //Arrays.sort(data); //或者使用內(nèi)置函數(shù)進行排序
quickSort(data, 0, data.length - 1);
if (data.length < 2) return -1;
int prev = data[0];
for (int i = 1; i < data.length; i++) {
if (data[i] == prev) return prev;
else prev = data[i];
}
return -1;
}
public static void quickSort(int[] data, int start, int end) {
if (start >= end) return;
int bound = partion(data, start, end);
quickSort(data, start, bound - 1);
quickSort(data, bound + 1, end);
}
public static int partion(int[] data, int start, int end) {
if (start >= end) return end;
int pivot = data[start];
int left = start, right = end;
while (left < right) {
while (left < right && data[right] >= pivot) right--;
if (left < right) data[left++] = data[right];
while (left < right && data[left] < pivot) left++;
if (left < right) data[right--] = data[left];
}
data[left] = pivot;
return left;
}
//方法三：借助哈希表，不會修改原始數(shù)據(jù)登钥，時間復雜度o(n),空間復雜度o(n)
public static int getDuplication3(int[] data) {
if (data == null || data.length < 2) return -1;
int[] hashTable = new int[data.length];
for (int item : data) {
if (hashTable[item] >= 1) return item;
else {
hashTable[item] = 1;
}
}
return -1;
}
//方法四：根據(jù)數(shù)字特點排序畔师，會修改原始數(shù)據(jù)，時間復雜度o(n),空間復雜度o(1)
//數(shù)據(jù)特點就是范圍在0~n-1
//data[i] != i表示數(shù)據(jù)不在應該的位置
//while循環(huán)直到把當前位置替換成應該的數(shù)字
public static int getDuplication4(int[] data) {
if (data == null || data.length < 2) return -1;
for (int i = 0; i < data.length; i++) {
while (data[i] != i) {
if (data[i] == data[data[i]]) return data[i];
else {
int temp = data[i];
data[i] = data[temp];
data[temp] = temp;
}
}
}
return -1;
}
//方法五：類似于二路歸并牧牢，這個思路應該說是二路計數(shù)看锉，不修改原始數(shù)據(jù)，時間復雜度o(nlogn),空間復雜度o(1)
//數(shù)值在0~n-1塔鳍，也是在[start,end]間
//[start,middle]間的數(shù)字要是超過了middle-start+1,說明[start,middle]間肯定有重復數(shù)字
public static int getDuplication5(int[] data) {
if (data == null || data.length < 2)
return -1;
//數(shù)組值在[start,end]間
int start = 0;
int end = data.length - 2;
while (start <= end) {
int middle = (end - start) / 2 + start;
int count = countRange(data, start, middle);
if (start == end) {
if (count > 1) return start;
else return -1;
}
if (count > middle - start + 1) end = middle;
else start = middle + 1;
}
return -1;
}
//求在這范圍的數(shù)字有幾個
public static int countRange(int[] data, int start, int end) {
int count = 0;
for (int i = 0; i < data.length; i++) {
if (start <= data[i] && end >= data[i]) count++;
}
return count;
}
public static void main(String[] args) {
int[] data = {2, 3, 1, 0, 2, 5, 3};
System.out.println(getDuplication(data));
System.out.println(getDuplication2(data));
System.out.println(getDuplication3(data));
System.out.println(getDuplication4(data));
System.out.println(getDuplication5(data));
int[] data1 = {2, 3, 1, 0, 4, 5, 5};
System.out.println(getDuplication(data1));
System.out.println(getDuplication2(data1));
System.out.println(getDuplication3(data1));
System.out.println(getDuplication4(data1));
System.out.println(getDuplication5(data1));
}
}
- 二維數(shù)組中的查找
/**
* Created by ryder on 2017/6/12. * 二維數(shù)組伯铣，從左到右遞增，從上到下遞增轮纫，輸入一個整數(shù)腔寡，判斷數(shù)組中是否含有
*/
public class P44_FindInPartiallySortedMatrix {
public static boolean findInPartiallySortedMatrix(int[][] data, int target) {
if (data == null || data.length == 0 || data[0].length == 0) return false;
int rowMax = data.length - 1, colMax = data[0].length - 1;
int rowCur = data.length - 1, colCur = 0;
while (true) {
if (rowCur < 0 | rowCur > rowMax | colCur < 0 | colCur > colMax) return false;
if (data[rowCur][colCur] == target) return true;
else if (data[rowCur][colCur] > target) rowCur--;
else colCur++;
}
}
public static void main(String[] args) {
int[][] data = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
System.out.println(findInPartiallySortedMatrix(data, 10));
System.out.println(findInPartiallySortedMatrix(data, 5));
}
}
- 替換空格
public class P51_ReplaceSpaces {
//由于java的字符數(shù)組沒有結(jié)束符，所以需要多傳入個原始長度
// 先計算好替換后的位置掌唾，從后向前替換放前，時間復雜度o(n)
public static void replaceBlank(char[] data, int length) {
int newLength = length;
for (int i = 0; i < length; i++) {
if (data[i] == ' ') newLength += 2;
}
for (int indexOfOld = length - 1, indexOfNew = newLength - 1; indexOfOld >= 0 && indexOfOld != indexOfNew; indexOfOld--, indexOfNew--) {
if (data[indexOfOld] == ' ') {
data[indexOfNew--] = '0';
data[indexOfNew--] = '2';
data[indexOfNew] = '%';
} else {
data[indexOfNew] = data[indexOfOld];
}
}
}
public static void main(String[] args) {
char[] predata = "We are happy.".toCharArray();
char[] data = new char[20];
for (int i = 0; i < predata.length; i++) data[i] = predata[i];
System.out.println(data);
replaceBlank(data, 13);
System.out.println(data);
}
}
- 從尾到頭打印鏈表
public class ListNode<T> {
public T val;
public ListNode<T> next;
public ListNode(T val) {
this.val = val;
this.next = null;
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ret.append("[");
for (ListNode cur = this; ; cur = cur.next) {
if (cur == null) {
ret.deleteCharAt(ret.lastIndexOf(" "));
ret.deleteCharAt(ret.lastIndexOf(","));
break;
}
ret.append(cur.val);
ret.append(", ");
}
ret.append("]");
return ret.toString();
}
}
/**
* Created by ryder on 2017/6/13. * 從尾到頭打印鏈表
*/
public class P58_PrintListInReversedOrder {
//遞歸版
public static void printReversinglyRecursively(ListNode<Integer> node) {
if (node == null) return;
else {
printReversinglyRecursively(node.next);
System.out.println(node.val);
}
}
//非遞歸版
public static void printReversinglyIteratively(ListNode<Integer> node) {
Stack<Integer> stack = new Stack<>();
for (ListNode<Integer> temp = node; temp != null; temp = temp.next)
stack.add(temp.val);
while (!stack.isEmpty())
System.out.println(stack.pop());
}
public static void main(String[] args) {
ListNode<Integer> head = new ListNode<Integer>(1);
head.next = new ListNode<Integer>(2);
head.next.next = new ListNode<Integer>(3);
printReversinglyRecursively(head);
System.out.println();
printReversinglyIteratively(head);
}
}
二叉樹的遍歷
/**
* 二叉樹的遍歷：先序（遞歸忿磅，非遞歸），中序（遞歸凭语，非遞歸）葱她，后序（遞歸，非遞歸）似扔，層序
*/
public class P60_TraversalOfBinaryTree {
//先序遍歷遞歸自己寫
public static void preorderRecursively(TreeNode<Integer> node) {
System.out.println(node.val);
if (node.left != null)
preorderRecursively(node.left);
if (node.right != null)
preorderRecursively(node.right);
}
//先序遍歷遞歸版
public static List<Integer> preorderRecursively(TreeNode<Integer> node) {
List<Integer> list = new ArrayList<>();
if (node == null) return list;
list.add(node.val);
list.addAll(preorderRecursively(node.left));
list.addAll(preorderRecursively(node.right));
return list;
}
//中序遍歷遞歸版
public static List<Integer> inorderRecursively(TreeNode<Integer> node) {
List<Integer> list = new ArrayList<>();
if (node == null) return list;
list.addAll(inorderRecursively(node.left));
list.add(node.val);
list.addAll(inorderRecursively(node.right));
return list;
}
//后序遍歷遞歸版
public static List<Integer> postorderRecursively(TreeNode<Integer> node) {
List<Integer> list = new ArrayList<>();
if (node == null) return list;
list.addAll(postorderRecursively(node.left));
list.addAll(postorderRecursively(node.right));
list.add(node.val);
return list;
}
//非遞歸每次當前為空了吨些，就把棧頂出棧，當前結(jié)點變?yōu)槌鰲＝Y(jié)點右孩子
//先序是當前節(jié)點入棧前虫几，把結(jié)果放到list里面
//中序是出棧之前锤灿，把結(jié)果放到list里面
//先序遍歷非遞歸版
public static List<Integer> preorderIteratively(TreeNode<Integer> node) {
//stack棧頂元素永遠為cur的父節(jié)點
Stack<TreeNode<Integer>> stack = new Stack<>();
TreeNode<Integer> cur = node;
List<Integer> list = new LinkedList<>();
if (node == null) return list;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
list.add(cur.val);
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop().right;
}
}
return list;
}
//中序遍歷非遞歸版
public static List<Integer> inorderIteratively(TreeNode<Integer> node) {
//stack棧頂元素永遠為cur的父節(jié)點
Stack<TreeNode<Integer>> stack = new Stack<>();
TreeNode<Integer> cur = node;
List<Integer> list = new LinkedList<>();
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
list.add(stack.peek().val);
cur = stack.pop().right;
}
}
return list;
}
//后序遍歷非遞歸版
public static List<Integer> postorderIteratively(TreeNode<Integer> node) {
//stack棧頂元素永遠為cur的父節(jié)點
// prevVisted用于區(qū)分是從左子樹還是右子樹返回的
Stack<TreeNode<Integer>> stack = new Stack<>();
TreeNode<Integer> cur = node;
TreeNode<Integer> prevVisted = null;
List<Integer> list = new LinkedList<>();
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else { //當前為空了，把當前節(jié)點變成棧頂?shù)挠易咏Y(jié)點
cur = stack.peek().right;
if (cur != null && cur != prevVisted) { //不為空辆脸，且不是剛出棧
//需要判斷當前節(jié)點是否剛被彈出棧但校，否則會多次進棧
stack.push(cur);
cur = cur.left;
} else { //當前節(jié)點還是為空或者剛出過棧，棧頂出棧并放到結(jié)果數(shù)組
prevVisted = stack.pop();
list.add(prevVisted.val);
cur = null;
}
}
}
return list;
}
//層序遍歷
public static List<Integer> levelorder(TreeNode<Integer> node) {
Queue<TreeNode<Integer>> queue = new LinkedList<>();
List<Integer> list = new LinkedList<>();
TreeNode<Integer> temp = null;
if (node == null) return list;
queue.add(node);
while (!queue.isEmpty()) {
temp = queue.poll();
list.add(temp.val);
if (temp.left != null) queue.offer(temp.left);
if (temp.right != null) queue.offer(temp.right);
}
return list;
}
public static void main(String[] args) {
// 1
// \
// 2
// /
// 3
//pre->123 in->132 post->321 level->123
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.right = new TreeNode<Integer>(2);
root.right.left = new TreeNode<Integer>(3);
List<Integer> list_preorderRecursively = preorderRecursively(root);
System.out.print("preorderRecursively: " + '\t');
System.out.println(list_preorderRecursively.toString());
List<Integer> list_inorderRecursively = inorderRecursively(root);
System.out.print("inorderRecursively: " + '\t');
System.out.println(list_inorderRecursively.toString());
List<Integer> list_postorderRecursively = postorderRecursively(root);
System.out.print("postorderRecursively: " + '\t');
System.out.println(list_postorderRecursively.toString());
System.out.println();
List<Integer> list_preorderIteratively = preorderIteratively(root);
System.out.print("preorderIteratively: " + '\t');
System.out.println(list_preorderIteratively.toString());
List<Integer> list_inorderIteratively = inorderIteratively(root);
System.out.print("inorderIteratively: " + '\t');
System.out.println(list_inorderIteratively.toString());
List<Integer> list_postorderIteratively = postorderIteratively(root);
System.out.print("postorderIteratively: " + '\t');
System.out.println(list_postorderIteratively.toString());
System.out.println();
List<Integer> list_levelorder = levelorder(root);
System.out.print("levelorder: " + '\t');
System.out.println(list_levelorder.toString());
}
}
- 重建二叉樹
/**
* 重建二叉樹: 先序+中序啡氢，后續(xù)+中序可以完成重建状囱，而先序+后序無法完成
*/
public class P62_ConstructBinaryTree {
public static TreeNode construct(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length)
return null;
//遞歸時需要傳遞的，先序和中序的開始位置初始為0倘是，length是中序的長度
return constructCore(preorder, 0, inorder, 0, inorder.length);
}
public static TreeNode constructCore(int[] preorder, int preorder_start, int[] inorder, int inorder_start, int length) {
//length是先序的長度亭枷，為零是遞歸出口
if (length == 0) return null;
int inorder_index = -1;
//遍歷中序的序列
for (int i = inorder_start; i < inorder_start + length; i++) {
//找到當前的根節(jié)點位置，記錄到inorder_index
if (inorder[i] == preorder[preorder_start]) {
inorder_index = i;
break;
}
}
//左邊中序序列的長度搀崭，右邊序列長length-left_length-1
int left_length = inorder_index - inorder_start;
//根節(jié)點變成TreeNode叨粘，node的左右孩子是向下遞歸的結(jié)果
TreeNode node = new TreeNode(preorder[preorder_start]);
node.left = constructCore(preorder, preorder_start + 1, inorder, inorder_start, left_length);
node.right = constructCore(preorder, preorder_start + left_length + 1, inorder, inorder_index + 1, length - left_length - 1);
return node;
}
public static void main(String[] args) {
// 1
// / \
// 2 3
// / \
// 4 5
// pre->12453 in->42513 post->45231
int[] pre = {1, 2, 4, 5, 3};
int[] in = {4, 2, 5, 1, 3};
TreeNode root = construct(pre, in);
//對重建后的樹,進行前中后序遍歷，驗證是否重建正確
// 調(diào)用的重建函數(shù)見：http://www.reibang.com/p/362d4ff42ab2
List<Integer> preorder = P60_TraversalOfBinaryTree.preorderIteratively(root);
List<Integer> inorder = P60_TraversalOfBinaryTree.inorderIteratively(root);
List<Integer> postorder = P60_TraversalOfBinaryTree.postorderIteratively(root);
System.out.println(preorder);
System.out.println(inorder);
System.out.println(postorder);
}
}
- 二叉樹的下一個節(jié)點
/*
題目要求：
給定二叉樹和其中一個節(jié)點瘤睹，找到中序遍歷序列的下一個節(jié)點升敲。
樹中的節(jié)點除了有左右孩子指針，還有一個指向父節(jié)點的指針轰传。
*/
/*
思路：
（1）如果輸入的當前節(jié)點有右孩子驴党，則它的下一個節(jié)點即為該右孩子為根節(jié)點的子樹的最左邊的節(jié)點，比如2->5,1->3
（2）如果輸入的當前節(jié)點沒有右孩子获茬，就需要判斷其與自身父節(jié)點的關(guān)系：
（2.1）如果當前節(jié)點沒有父節(jié)點港庄，那所求的下一個節(jié)點不存在，返回null.
（2.2）如果輸入節(jié)點是他父節(jié)點的左孩子恕曲，那他的父節(jié)點就是所求的下一個節(jié)點,比如4->2
（2.3）如果輸入節(jié)點是他父節(jié)點的右孩子鹏氧，那就需要將輸入節(jié)點的父節(jié)點作為新的當前節(jié)點，
返回到（2）,判斷新的當前節(jié)點與他自身父節(jié)點的關(guān)系,比如5->1
*/
//帶有父指針的二叉樹節(jié)點
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode father;
public TreeNode(int val){
this.val = val;
this.left = null;
this.right = null;
this.father = null;
}
}
public class P65_NextNodeInBinaryTrees {
public static TreeNode getNext(TreeNode pNode){
if(pNode==null)
return null;
else if(pNode.right!=null){
pNode = pNode.right;
while(pNode.left!=null)
pNode = pNode.left;
return pNode;
}
while(pNode.father!=null){
if(pNode.father.left==pNode)
return pNode.father;
pNode = pNode.father;
}
return null;
}
public static void main(String[] args){
// 1
// // \\
// 2 3
// // \\
// 4 5
// inorder->42513
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.father = root;
root.right = new TreeNode(3);
root.right.father = root;
root.left.left = new TreeNode(4);
root.left.left.father = root.left;
root.left.right = new TreeNode(5);
root.left.right.father = root.left;
System.out.println(getNext(root.left.left).val);
System.out.println(getNext(root.left).val);
System.out.println(getNext(root.left.right).val);
System.out.println(getNext(root).val);
System.out.println(getNext(root.right));
}
}
- 用兩個棧實現(xiàn)隊列
/*
思路：
（1）對于插入操作佩谣，棧與隊列都是從隊尾進行度帮，因此一行代碼就可以完成offer()
（2）對于彈出操作，隊列先進先出從隊頭開始，而棧后進先出從隊尾開始笨篷，要想取到隊頭元素，
就得需要第二個棧stack2的協(xié)助：彈出時將stack1的元素依次取出放到stack2中瓣履，此時stack2
進行彈出的順序就是整個隊列的彈出順序率翅。而如果需要插入，放到stack1中即可袖迎。
*/
//stack2有值就2出棧冕臭，否則將1導入2，再出棧
class MyQueue<T>{
private Stack<T> stack1 = new Stack<>();
private Stack<T> stack2 = new Stack<>();
public void offer(T data){
stack1.push(data);
}
public T poll(){
if(!stack2.isEmpty()){
return stack2.pop();
}
else if(!stack1.isEmpty()){
while(!stack1.isEmpty())
stack2.push(stack1.pop());
return stack2.pop();
}
else
return null;
}
}
public class P68_QueueWithTwoStacks {
public static void main(String[] args){
MyQueue<Integer> myQueue = new MyQueue<>();
System.out.println(myQueue.poll());
myQueue.offer(1);
myQueue.offer(2);
myQueue.offer(3);
System.out.println(myQueue.poll());
System.out.println(myQueue.poll());
myQueue.offer(4);
System.out.println(myQueue.poll());
System.out.println(myQueue.poll());
System.out.println(myQueue.poll());
}
}
- 斐波那契數(shù)列
/**
* Created by ryder on 2017/6/21.
* 斐波那契數(shù)列
* f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2) n>1
*/
解法 解法介紹 時間復雜度 空間復雜度
解法1 依定義遞歸求解 o(n^2) o(1)
解法2 從0開始迭代求解 o(n) o(1)
解法3 借助等比數(shù)列公式 o(logn) o(1)
解法4 借助通項公式 o(1) o(1)
public class P74_Fibonacci {
// 依據(jù)原始概念的遞歸解法燕锥，時間復雜度o(n^2)
public static int fibonacci1(int n){
if(n<=0)
return 0;
if(n==1)
return 1;
return fibonacci1(n-1)+fibonacci1(n-2);
}
// 當前狀態(tài)只與前兩個狀態(tài)有關(guān)辜贵。存儲前兩個值，計算后一個归形，迭代進行托慨。時間復雜度o(n)
public static int fibonacci2(int n){
if(n<=0)
return 0;
if(n==1)
return 1;
int temp1 =0,temp2=1;
int result = temp1 + temp2,i=3;
while(i<=n){
//也可用一個隊列來完成下面三行的操作
temp1 = temp2;
temp2 = result;
result = temp1+temp2;
i++;
}
return result;
}
// 借助如下數(shù)學公式解決問題。矩陣乘法部分暇榴，可用遞歸解決厚棵，時間復雜度o(logn)
// [ f(n) f(n-1) ] = [ 1 1 ] ^ n-1 (當n>2)
// [f(n-1) f(n-2) ] [ 1 0 ]
// 證明:
// [ f(n) f(n-1) ] = [ f(n-1)+f(n-2) f(n-1)] = [ f(n-1) f(n-2)] * [1 1]
// [f(n-1) f(n-2) ] [ f(n-2)+f(n-3) f(n-2)] [ f(n-2) f(n-3)] [1 0]
// 得到如上遞推式，所以
// [ f(n) f(n-1) ] = [ f(2) f(1)] * [1 1]^n-2 = [1 1]^n-1
// [f(n-1) f(n-2) ] [ f(1) f(0)] [1 0] [1 0]
public static int fibonacci3(int n){
int[][] start = {{1,1},{1,0}};
return matrixPow(start,n-1)[0][0];
}
public static int[][] matrixPow(int[][] start,int n){
if((n&1)==0){
int[][] temp = matrixPow(start,n>>1);
return matrixMultiply(temp,temp);
}
else if(n==1){
return start;
}
else{
return matrixMultiply(start,matrixPow(start,n-1));
}
}
public static int[][] matrixMultiply(int[][] x,int[][] y){
int[][] result = new int[x.length][y[0].length];
for(int i=0;i<x.length;i++){
for(int j=0;j<y[0].length;j++){
int sum = 0;
for(int k=0;k<x[0].length;k++){
sum += x[i][k]*y[k][j];
}
result[i][j] = sum;
}
}
return result;
}
// 使用通項公式完成蔼紧，時間復雜度o(1)
// f(n) = (1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
// 推導過程可參考https://wenku.baidu.com/view/57333fe36bd97f192379e936.html
public static int fibonacci4(int n){
double gen5 = Math.sqrt(5);
return (int)((1/gen5)*(Math.pow((1+gen5)/2,n)- Math.pow((1-gen5)/2,n)));
}
public static void main(String[] args){
System.out.println(fibonacci1(13));
System.out.println(fibonacci2(13));
System.out.println(fibonacci3(13));
System.out.println(fibonacci4(13));
}
}
排序算法比較表格
http://www.reibang.com/p/6ae77d17170c
快排：
package chapter2;
public class P79_Sort {
//數(shù)組快排婆硬，時間o(nlogn)(最差n^2)，空間o(logn)(最差n)奸例，遞歸造成的棻蚍福空間的使用，不穩(wěn)定
public static void quickSort(int[] data){
if(data==null || data.length<=1) return;
quickSortCore(data,0,data.length-1);
}
public static void quickSortCore(int[] data,int start,int end){
if(end-start<=0)
return;
int index = quickSortPartition(data,start,end);
quickSortCore(data,start,index-1);
quickSortCore(data,index+1,end);
}
public static int quickSortPartition(int[] data,int start,int end){
//選擇第一個值作為基準
int pivot = data[start];
int left = start,right = end;
while(left<right){
while(left<right && data[right]>=pivot)
right--;
if(left<right)
data[left] = data[right];
while(left<right && data[left]<pivot)
left++;
if(left<right)
data[right] = data[left];
}
data[left] = pivot;
return left;
}
public static void testQuickSort(){
int[] data = {5,4,3,1,2};
quickSort(data);
System.out.print("數(shù)組快速排序：\t");
for(int item: data){
System.out.print(item);
System.out.print('\t');
}
System.out.println();
}
}
歸并排序：
package chapter2;
/**
* Created by ryder on 2017/6/25.
* 數(shù)組排序算法
*/
public class P79_Sort {
//數(shù)組二路歸并查吊，時間o(nlogn)谐区，空間o(n)，穩(wěn)定
public static int[] mergeSort(int[] data){
if(data==null || data.length<=1)
return data;
mergeSortCore(data,0,data.length-1);
return data;
}
//對data[start~mid]菩貌，data[mid+1~end]歸并
//典型的分治結(jié)構(gòu)：結(jié)束條件+分治+和
public static void mergeSortCore(int[] data,int start,int end){
if(start>=end)
return;
int mid = start + (end - start)/2;
mergeSortCore(data,start,mid);
mergeSortCore(data,mid+1,end);
mergeSortMerge(data,start,mid,end);
}
public static void mergeSortMerge(int[] data,int start,int mid,int end){
if(end==start)
return;
int[] temp = new int[end-start+1];
int left = start,right = mid+1,tempIndex = 0;
while(left<=mid && right<=end){
if(data[left]<data[right])
temp[tempIndex++] = data[left++];
else
temp[tempIndex++] = data[right++];
}
while(left<=mid)
temp[tempIndex++] = data[left++];
while(right<=end)
temp[tempIndex++] = data[right++];
for(int i=0;i<temp.length;i++)
data[start+i] = temp[i];
}
public static void testMergeSort(){
int[] data = {5,4,3,1,2};
mergeSort(data);
System.out.print("數(shù)組歸并排序：\t");
for(int item: data){
System.out.print(item);
System.out.print('\t');
}
System.out.println();
}
}
堆排序：
package chapter2;
/**
* Created by ryder on 2017/6/25.
* 數(shù)組排序算法
*/
import java.util.Arrays;
public class HeapSort {
public static void HeapAdjust(int[] num, int s, int l) {
int i, j;
//記錄調(diào)整結(jié)點的值
int temp = num[s];
i = s;
//j初始為i左子結(jié)點的位置
for (j = 2 * i + 1; j <= l; j = 2 * j + 1) {
//將j指向數(shù)值較大的子節(jié)點
if (j < l && num[j] < num[j + 1]) {
j = j + 1;
}
//如果調(diào)整節(jié)點大于其子節(jié)點最大的值則無需調(diào)整
if (temp > num[j]) {
break;
}
//如果小于則將子節(jié)點移動到父節(jié)點位置
num[i] = num[j];
//繼續(xù)向下調(diào)整
i = j;
}
//最后插入數(shù)據(jù)
num[i] = temp;
}
public static void HeapInit(int[] nums, int l) {
for (int i = (l - 1) / 2; i >= 0; i--) {
HeapAdjust(nums, i, l);
System.out.println(Arrays.toString(nums)+", i:"+i);
}
}
public static void HeapSort(int[] nums, int l) {
for (int i = l; i > 0; i--) {
//把大根堆的跟放到最后的位置也就是i
int temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
//然后每次都從根也就是0開始調(diào)堆卢佣，不調(diào)最后排好的位置
HeapAdjust(nums, 0, i - 1);
System.out.println(Arrays.toString(nums)+", l:"+i);
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8};
HeapInit(nums, 8);
HeapSort(nums, 8);
System.out.println(Arrays.toString(nums));
}
}
冒泡排序：
package chapter2;
/**
* Created by ryder on 2017/6/25.
* 數(shù)組排序算法
*/
public class P79_Sort {
//數(shù)組冒泡，時間o(n^2)箭阶，空間o(1)虚茶，穩(wěn)定
public static void bubbleSort(int[] data){
if(data==null || data.length<=1)
return;
for(int i=0;i<data.length-1;i++){
for(int j=1;j<data.length-i;j++){
if(data[j-1]>data[j]){
int temp = data[j-1];
data[j-1] = data[j];
data[j] = temp;
}
}
}
}
public static void testBubbleSort(){
int[] data = {5,4,3,1,2};
bubbleSort(data);
System.out.print("數(shù)組冒泡排序：\t");
for(int item: data){
System.out.print(item);
System.out.print('\t');
}
System.out.println();
}
}
選擇排序：
package chapter2;
/**
* Created by ryder on 2017/6/25.
* 數(shù)組排序算法
*/
public class P79_Sort {
//數(shù)組選擇排序，時間o(n^2)仇参，空間o(1)嘹叫，不穩(wěn)定
public static void selectionSort(int[] data){
if(data==null || data.length<=1)
return;
for(int i=0;i<data.length-1;i++){
int minIndex = i;
for(int j=i+1;j<data.length;j++){
if(data[j]<data[minIndex])
minIndex = j;
}
if(i!=minIndex) {
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
public static void testSelectionSort(){
int[] data = {5,4,3,1,2};
selectionSort(data);
System.out.print("數(shù)組選擇排序：\t");
for(int item: data){
System.out.print(item);
System.out.print('\t');
}
System.out.println();
}
}
插入排序：
package chapter2;
/**
* Created by ryder on 2017/6/25.
* 數(shù)組排序算法
*/
public class P79_Sort {
//數(shù)組插入排序，時間o(n^2)诈乒，空間o(1)罩扇，穩(wěn)定
public static void insertionSort(int[] data){
if(data==null || data.length<=1)
return;
for(int i=1;i<data.length;i++){
int j=i;
int temp = data[i];
while(j>0 && data[j-1]>temp) {
data[j] = data[j-1];
j--;
}
data[j] = temp;
}
}
public static void testInsertionSort(){
int[] data = {5,4,3,1,2};
insertionSort(data);
System.out.print("數(shù)組插入排序：\t");
for(int item: data){
System.out.print(item);
System.out.print('\t');
}
System.out.println();
}
}
希爾排序：
package chapter2;
/**
* Created by ryder on 2017/6/25.
* 數(shù)組排序算法
*/
public class P79_Sort {
//數(shù)組希爾排序(插入排序縮小增量)，時間o(n^1.3)，空間o(1)喂饥，不穩(wěn)定
//時間復雜度是模糊的消约，有人在大量的實驗后得出結(jié)論：
//當n在某個特定的范圍后希爾排序的比較和移動次數(shù)減少至n^1.3迁央。次數(shù)取值在1到2之間桅打。
public static void shellSort(int[] data){
if(data==null || data.length<=1)
return;
for(int d=data.length/2; d>0; d=d/2){
for(int i=d;i<data.length;i++){
int cur = i;
int temp = data[i];
while(cur>=d && data[cur-d]>temp){
data[cur] = data[cur-d];
cur = cur - d;
}
data[cur] = temp;
}
}
}
public static void testShellSort(){
int[] data = {5,4,3,1,2};
shellSort(data);
System.out.print("數(shù)組希爾排序：\t");
for(int item: data){
System.out.print(item);
System.out.print('\t');
}
System.out.println();
}
}
- 旋轉(zhuǎn)數(shù)組的最小數(shù)字
/**
* Created by ryder on 2017/6/28.
* 旋轉(zhuǎn)數(shù)組的最小數(shù)字
*/
//把一個數(shù)組的若干元素搬到數(shù)組末尾叫旋轉(zhuǎn)數(shù)組
public class P82_MinNumberInRotatedArray {
public static int min(int[] data){
if(data==null || data.length==0)
return -1;
int left = 0;
int right = data.length-1;
int mid;
while(left<right){
mid = left+(right-left)/2;
//left < right埃唯，這種是返回的情況
if(data[left]<data[right])
return data[left];
//left > right
else if(data[left]>data[right]){
//中間的大等左邊塞关，說明最小值在mid右邊
if(data[mid]>=data[left])
left = mid + 1;
//否則在mid左邊才菠，包含mid
else
right = mid;
}
//left = right
else{
//中間大于左邊谣辞，說明最小值在mid右邊
if(data[left]<data[mid])
left = mid + 1;
//否則在mid左邊兆沙，包含mid
else if(data[left]>data[mid])
right = mid;
//不確定诚些，只能縮小兩個位置的范圍
else{
left = left+1;
right = right-1;
}
}
}
return data[right];
}
public static void main(String[] args){
int[] data1 = {3,4,5,1,2};
int[] data2 = {1,0,1,1,1};
int[] data3 = {1,1,1,0,1};
System.out.println(min(data1));
System.out.println(min(data2));
System.out.println(min(data3));
}
}
- 矩陣中的路徑
題目要求：設計一個函數(shù)硝岗，用來判斷一個矩陣中是否存在一條包含某字符串的路徑氢哮。
（1）起點隨意；（2）路徑的移動只能是上下左右型檀；（3）訪問過的位置不能再訪問冗尤。
以下圖矩陣為例，包含“bfce”贱除，但是不包含“abfb”生闲。
a b t g
c f c s
j d e h
/**
* Created by ryder on 2017/7/2.
* 矩陣中的路徑
*/
public class P89_StringPathInMatrix {
//回溯法解決
public static boolean hasPath(char[][] data,String str){
if(data==null || data.length==0 || str==null || str.length()==0)
return false;
int rowLen = data.length;
int colLen = data[0].length;
boolean[][] visitFlag = new boolean[rowLen][colLen];
for(int row=0;row<rowLen;row++){
for(int col=0;col<colLen;col++){
visitFlag[row][col] = false;
}
}
for(int row=0;row<rowLen;row++){
for(int col=0;col<colLen;col++){
if(hasPathCore(data,row,col,visitFlag,str,0))
return true;
}
}
return false;
}
public static boolean hasPathCore(char[][] data,int rowIndex,int colIndex,
boolean[][] visitFlag,String str,int strIndex){
//結(jié)束條件
if(strIndex>=str.length()) return true;
if(rowIndex<0 || colIndex<0 || rowIndex>=data.length || colIndex>=data[0].length)
return false;
//遞歸
if(!visitFlag[rowIndex][colIndex]&&data[rowIndex][colIndex]==str.charAt(strIndex)){
//如果未被訪問，且匹配字符串月幌，標記當前位置為已訪問碍讯，分上下左右四個位置遞歸求解
visitFlag[rowIndex][colIndex] = true;
boolean result =
hasPathCore(data,rowIndex+1,colIndex,visitFlag,str,strIndex+1) ||
hasPathCore(data,rowIndex-1,colIndex,visitFlag,str,strIndex+1) ||
hasPathCore(data,rowIndex,colIndex+1,visitFlag,str,strIndex+1) ||
hasPathCore(data,rowIndex,colIndex-1,visitFlag,str,strIndex+1);
//已經(jīng)求的結(jié)果，無需修改標記了
if(result)
return true;
//當前遞歸的路線求解失敗扯躺，要把這條線路上的標記清除掉
//因為其他起點的路徑依舊可以訪問本路徑上的節(jié)點捉兴。
else{
visitFlag[rowIndex][colIndex] = false;
return false;
}
}
else
return false;
}
public static void main(String[] args){
char[][] data = {
{'a','b','t','g'},
{'c','f','c','s'},
{'j','d','e','h'}};
System.out.println(hasPath(data,"bfce")); //true
System.out.println(hasPath(data,"abfb")); //false,訪問過的位置不能再訪問
}
}
- 機器人的運動范圍
題目要求：
地上有一個m行n列的方格，一個機器人從坐標(0,0)的各自開始移動录语，它每次
可以向上下左右移動一格倍啥，但不能進入橫縱坐標數(shù)位之和大于k的格子。
例如澎埠，當k等于18時虽缕，機器人能進入(35,37)，因為3+5+3+7=18蒲稳；但卻不能進入
(35,38)氮趋，因為3+5+3+8=19>18。
請問該機器人能夠到達多少個格子江耀。
解題思路：
本題依舊考察回溯法剩胁。
每前進一步后，可選移動項為上下左右四個祥国；為了判斷某一個格子是否可以進入
從而進行計數(shù)昵观，不僅需要考慮邊界值，計算各位數(shù)字之和，更要判斷該格子是否
已經(jīng)被訪問過啊犬，灼擂。所以需要一個布爾矩陣，用來記錄各格子是否已被訪問觉至。整體思
路與12題類似缤至，具體請參考本系列的導航帖。
package chapter2;
/**
* Created by ryder on 2017/7/4.
* 機器人的運動范圍
*/
public class P92_RobotMove {
//依舊回溯
public static int movingCount(int threshold,int rowLen,int colLen){
if(rowLen<=0 || colLen<=0 || threshold<0)
return 0;
boolean[][] visitFlag = new boolean[rowLen][colLen];
for(int row=0;row<rowLen;row++){
for(int col=0;col<colLen;col++)
visitFlag[row][col] = false;
}
return movingCountCore(threshold,rowLen,colLen,0,0,visitFlag);
}
public static int movingCountCore(int threshold,int rowLen,int colLen,int row,int col,boolean[][] visitFlag){
int count = 0;
if(canGetIn(threshold,rowLen,colLen,row,col,visitFlag)){
visitFlag[row][col] = true;
count = 1+movingCountCore(threshold,rowLen,colLen,row-1,col,visitFlag)+
movingCountCore(threshold,rowLen,colLen,row+1,col,visitFlag)+
movingCountCore(threshold,rowLen,colLen,row,col-1,visitFlag)+
movingCountCore(threshold,rowLen,colLen,row,col+1,visitFlag);
}
return count;
}
public static boolean canGetIn(int threshold,int rowLen,int colLen,int row,int col,boolean[][] visitFlag){
return row>=0 && col>=0 && row<rowLen
&& col<colLen && !visitFlag[row][col]
&& getDigitSum(row)+getDigitSum(col)<=threshold;
}
public static int getDigitSum(int number){
int sum=0;
while (number>0){
sum += number%10;
number/=10;
}
return sum;
}
public static void main(String[] args){
System.out.println(movingCount(0,3,4)); //1
System.out.println(movingCount(1,3,4)); //3
System.out.println(movingCount(9,2,20)); //36
}
}
- 剪繩子
題目要求：
給你一根長度為n的繩子康谆，請把繩子剪成m段，記每段繩子長度為 k[0],k[1]...k[m-1],
求k[0]k[1]...k[m-1]的最大值嫉到。已知繩子長度n為整數(shù)沃暗，m>1(至少要剪一刀，不能不剪)何恶，
k[0],k[1]...k[m-1]均要求為整數(shù)孽锥。
例如，繩子長度為8時细层，把它剪成3-3-2惜辑，得到最大乘積18；繩子長度為3時疫赎，把它剪成2-1盛撑，
得到最大乘積2。
我們定義長度為n的繩子剪切后的最大乘積為f(n),剪了一刀后,f(n)=max(f(i)*f(n-i));
假設n為10捧搞，第一刀之后分為了4-6抵卫，而6也可能再分成2-4（6的最大是3-3，但過程中還是
要比較2-4這種情況的）胎撇，而上一步4-6中也需要求長度為4的問題的最大值介粘，可見，各個子
問題之間是有重疊的晚树，所以可以先計算小問題姻采，存儲下每個小問題的結(jié)果，逐步往上爵憎，求得
大問題的最優(yōu)解慨亲。
上述算法的時間復雜度為o(n^2);但其實，可以使用貪婪算法在o(1)時間內(nèi)得到答案：
n<5時纲堵，和動態(tài)規(guī)劃一樣特殊處理巡雨；n>=5時，盡可能多地剪長度為3的繩子席函，當剩下的繩子長
度為4時铐望，剪成2-2；比如長度為13的繩子， 剪成3-3-3-2-2正蛙；貪婪算法雖然快督弓，但一般都思
路奇特，可遇不可求乒验。且面試官一般都會要求證明愚隧，數(shù)學功底要好 。
/**
* Created by ryder on 2017/7/5.
* 剪繩子
*/
public class P96_CuttingRope {
public static int maxCutting(int length){
if(length<2) return 0;
if(length==2)return 1;
if(length==3)return 2;
int[] dp = new int[length+1];
dp[0]=0;
dp[1]=1;
dp[2]=2;
dp[3]=3;
int max = 0;
int temp = 0;
//i是繩子的長度锻全，j是最后一次減去的長度狂塘，到總長度的一半
for(int i=4;i<=length;i++){
max = 0;
for(int j=1;j<=i/2;j++){
temp = dp[j]*dp[i-j];
if(temp>max)
max = temp;
}
//dp[i]是temp里最大的
dp[i] = max;
}
return dp[length];
}
public static void main(String[] args){
for(int i=2;i<10;i++){
System.out.println("長度為"+i+"的最大值->"+maxCutting(i));
}
}
}
- 位運算
題目要求：
實現(xiàn)一個函數(shù)，輸入一個int型整數(shù)鳄厌，輸出該數(shù)字在計算機中二進制表示形式的1的個數(shù)荞胡。
例如9->1001,輸出2；-3->11111111111111111111111111111101,輸出31了嚎。
解題思路：
考查位運算泪漂，此題要注意負數(shù)的處理。首先要明確計算機中歪泳，數(shù)字是以補碼的形式存儲的萝勤，
原碼反碼補碼不清楚的話請自己谷歌百度。其次呐伞，明確位運算符敌卓，與&，或|荸哟，非~假哎，異或^,
<<左移位，>>帶符號右移位鞍历，>>>無符號右移位(java有此符號舵抹，c++沒有)
解法一：將數(shù)字無符號右移，直到為0劣砍。
解法二：使用一個標記惧蛹，初始為1，讓標記值與原輸入數(shù)字異或刑枝，然后標記值左移香嗓。解法一
是原數(shù)字右移，而解法二是標記左移装畅，從java來看思路類似但換了個角度靠娱；但這個思路在
C++就很關(guān)鍵，因為C++中沒有>>>運算符掠兄，只能用解法二像云。
解法三：沒接觸過的人應該會覺得比較新穎锌雀。對于二進制數(shù)有如下結(jié)論：【把一個整數(shù)減去1
之后再和原來的整數(shù)做位與運算，得到的結(jié)果相當于把原整數(shù)的二進制表示形式的最右邊的
1變成0】迅诬。比如1001腋逆，執(zhí)行一次上述結(jié)論，1001&1000=1000侈贷，將最右邊的1改為了0惩歉；再執(zhí)行
一次，1000&0111=0000俏蛮，第二個1也改成了0撑蚌。因此能執(zhí)行幾次該結(jié)論，就有幾個1搏屑。
對于解法一二锨并，都需要循環(huán)32次，判斷每一個比特位是否為1睬棚，而解法三，循環(huán)次數(shù)等于比特
位為1的個數(shù)解幼。時間上是有改進的抑党。
/**
* Created by ryder on 2017/7/6.
* 二進制中的1的個數(shù)
*/
public class P100_NumberOf1InBinary {
public static int numberOfOne1(int n){
int count=0;
while(n!=0){
if((n&1)!=0)
count++;
n>>>=1;
}
return count;
}
public static int numberOfOne2(int n){
int count=0;
int flag=1;
while(flag!=0){
if((n&flag)!=0)
count++;
flag<<=1;
}
return count;
}
public static int numberOfOne3(int n){
int count=0;
while(n!=0){
n = n&(n-1);
count++;
}
return count;
}
public static void main(String[] args){
System.out.println(numberOfOne1(3));
System.out.println(numberOfOne1(-3));
System.out.println(numberOfOne2(3));
System.out.println(numberOfOne2(-3));
System.out.println(numberOfOne3(3));
System.out.println(numberOfOne3(-3));
}
}
- 數(shù)值的整數(shù)次方
題目要求：
實現(xiàn)函數(shù)double power（double base，int exponent）撵摆，求base的exponent次方底靠。
不能使用庫函數(shù)，不需要考慮大數(shù)問題特铝。
解題思路：本題考查考慮問題的完整性暑中。如下幾個點要注意：
要考慮一些特殊情況，如指數(shù)為負鲫剿、指數(shù)為負且底數(shù)為0鳄逾、0的0次方要定義為多少。
底數(shù)為0的定義灵莲。對于一個double類型的數(shù)雕凹，判斷它與另一個數(shù)是否相等，不能用“==”政冻，
一般都需要一個精度枚抵，見下面的equal函數(shù)。
對于報錯的情況明场，比如0的負數(shù)次方汽摹，要如何處理。書中提了三種錯誤處理方法：用函數(shù)
返回值來提示錯誤苦锨；用一個全局變量來提示錯誤逼泣；拋出異常趴泌；三種方法優(yōu)缺點比較如下
錯誤處理方法 優(yōu)點 缺點
返回值 和相關(guān)函數(shù)的API一致 不能方便地使用計算結(jié)果
全局變量 能夠方便地使用計算結(jié)果 用戶可能忘記檢查全局變量
異常 可自定義異常類型，邏輯清晰明了 拋出異常時對性能有負面影響
/**
* Created by ryder on 2017/7/6.
* 數(shù)值的整數(shù)次方
*/
public class P110_Power {
static boolean invalidInput = false;
public static double power(double base,int exponent){
//0的0次方在數(shù)學上沒有意義圾旨，為了方便也返回1踱讨，也可特殊處理
if(exponent==0)
return 1;
if(exponent<0){
if(equal(base,0)){
//通過全局變量報錯
invalidInput = true;
return 0;
}
else
return 1.0/powerWithPositiveExponent(base,-1*exponent);
}
else
return powerWithPositiveExponent(base,exponent);
}
public static boolean equal(double x,double y){
return -0.00001<x-y && x-y<0.00001;
}
public static double powerWithPositiveExponent(double base,int exponent){
if(exponent==0)
return 1;
else if((exponent&1)==0){
//為偶數(shù),例如四次方，temp就是一個二次方的結(jié)果
double temp = powerWithPositiveExponent(base,exponent>>1);
return temp*temp;
}
else{
//為奇數(shù)砍的，例如五次方痹筛，就是兩個二次方再乘以一個base
double temp = powerWithPositiveExponent(base,exponent>>1);
return base*temp*temp;
}
}
public static void main(String[] args){
System.out.println("2^3="+power(2,3)+"\t是否報錯:"+invalidInput);
System.out.println("2^-3="+power(2,-3)+"\t是否報錯:"+invalidInput);
System.out.println("0^3="+power(0,3)+"\t是否報錯:"+invalidInput);
System.out.println("0^-3="+power(0,-3)+"\t是否報錯:"+invalidInput);
}
}
- 打印從1到最大的n位數(shù)
題目要求：
比如輸入2，打印1,2......98,99廓鞠；
解題思路：
此題需要考慮大數(shù)問題帚稠。本帖是使用字符串模擬數(shù)字的加法。
/**
* Created by ryder on 2017/7/6.
*
*/
public class P114_Print1ToMaxOfNDigits {
//在字符串上模擬加法
public static void print1ToMaxOfNDigits(int num){
if(num<=0)
return;
StringBuilder number = new StringBuilder(num);
for(int i=0;i<num;i++)
number.append('0');
while(increment(number)){
printNumber(number);
}
}
public static boolean increment(StringBuilder str){
//注意下面的return加過之后就返回了,要是進位了才繼續(xù)循環(huán)
for(int i=str.length()-1;i>=0;i--){
if(str.charAt(i)<'9' && str.charAt(i)>='0'){
str.setCharAt(i,(char)(str.charAt(i)+1));
return true;
}
else if(str.charAt(i)=='9'){
str.setCharAt(i,'0');
}
else{
return false;
}
}
return false;
}
//打印時從不為0的開始打印
public static void printNumber(StringBuilder number){
boolean flag = false;
for(int i=0;i<number.length();i++){
if(flag)
System.out.print(number.charAt(i));
else{
if(number.charAt(i)!='0'){
flag = true;
System.out.print(number.charAt(i));
}
}
}
System.out.println();
}
public static void main(String[] args){
print1ToMaxOfNDigits(2);
}
}
- 刪除鏈表的節(jié)點
題目要求：
在o(1)時間內(nèi)刪除單鏈表的節(jié)點床佳。
解題思路：
直接刪除單鏈表某一節(jié)點滋早，無法在o(1)時間得到該節(jié)點的前一個節(jié)點，
因此無法完成題目要求砌们「唆铮可以將欲刪節(jié)點的后一個節(jié)點的值拷貝到欲刪
節(jié)點之上，刪除欲刪節(jié)點的后一個節(jié)點浪感，從而可以在o(1)時間內(nèi)完成
刪除昔头。（對于尾節(jié)點，刪除仍然需要o(n),其他點為o(1)影兽，因此平均時
間復雜度為o(1)揭斧，滿足要求）
package structure;
/**
* Created by ryder on 2017/6/13.
*/
public class ListNode<T> {
public T val;
public ListNode<T> next;
public ListNode(T val){
this.val = val;
this.next = null;
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ret.append("[");
for(ListNode cur = this;;cur=cur.next){
if(cur==null){
ret.deleteCharAt(ret.lastIndexOf(" "));
ret.deleteCharAt(ret.lastIndexOf(","));
break;
}
ret.append(cur.val);
ret.append(", ");
}
ret.append("]");
return ret.toString();
}
}
package chapter3;
import structure.ListNode;
/**
* Created by ryder on 2017/7/7.
* o(1)時間刪除鏈表的節(jié)點
*/
public class P119_DeleteNodeInList {
public static ListNode<Integer> deleteNode(ListNode<Integer> head,ListNode<Integer> node){
if(node==head){
return head.next;
}
//考慮下一個為空和不為空的情況
else if(node.next!=null){
node.val = node.next.val;
node.next = node.next.next;
return head;
}
else{
ListNode<Integer> temp=head;
while(temp.next!=node)
temp = temp.next;
temp.next = null;
return head;
}
}
public static void main(String[] args){
ListNode<Integer> head = new ListNode<>(1);
ListNode<Integer> node2 = new ListNode<>(2);
ListNode<Integer> node3 = new ListNode<>(3);
head.next = node2;
node2.next = node3;
System.out.println(head);
head = deleteNode(head,node3);
System.out.println(head);
head = deleteNode(head,head);
System.out.println(head);
}
}
- 題目二：刪除排序鏈表中重復的節(jié)點
題目要求：
比如[1,2,2,3,3,3],刪除之后為[1];
解題思路：
由于是已經(jīng)排序好的鏈表，需要確定重復區(qū)域的長度峻堰，刪除后還需要將被刪去的前與后連接讹开，
所以需要三個節(jié)點pre,cur,post，cur-post為重復區(qū)域捐名，刪除后將pre與post.next連接即可旦万。
此外，要注意被刪結(jié)點區(qū)域處在鏈表頭部的情況镶蹋，因為需要修改head纸型。
package structure;
/**
* Created by ryder on 2017/6/13.
*/
public class ListNode<T> {
public T val;
public ListNode<T> next;
public ListNode(T val){
this.val = val;
this.next = null;
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ret.append("[");
for(ListNode cur = this;;cur=cur.next){
if(cur==null){
ret.deleteCharAt(ret.lastIndexOf(" "));
ret.deleteCharAt(ret.lastIndexOf(","));
break;
}
ret.append(cur.val);
ret.append(", ");
}
ret.append("]");
return ret.toString();
}
}
package chapter3;
import structure.ListNode;
/**
* Created by ryder on 2017/7/7.
* 刪除排序鏈表中的重復節(jié)點
*/
public class P122_deleteDuplicatedNode {
public static ListNode<Integer> deleteDuplication(ListNode<Integer> head){
if(head==null||head.next==null)
return head;
ListNode<Integer> pre = null;
ListNode<Integer> cur = head;
ListNode<Integer> post = head.next;
boolean needDelete = false;
while (post!=null){
if(cur.val.equals(post.val)){
needDelete = true;
post=post.next;
}
else if(needDelete && !cur.val.equals(post.val)){
if(pre==null)
head = post;
else
pre.next=post;
cur = post;
post = post.next;
needDelete = false;
}
else{
pre = cur;
cur = post;
post = post.next;
}
}
if(needDelete && pre!=null)
pre.next = null;
else if(needDelete && pre==null)
head = null;
return head;
}
public static void main(String[] args){
ListNode<Integer> head = new ListNode<>(1);
head.next= new ListNode<>(1);
head.next.next = new ListNode<>(2);
head.next.next.next = new ListNode<>(2);
head.next.next.next.next = new ListNode<>(2);
head.next.next.next.next.next = new ListNode<>(3);
System.out.println(head);
head = deleteDuplication(head);
System.out.println(head);
}
}
- 正則表達式匹配
題目要求：
實現(xiàn)正則表達式中.和*的功能。.表示任意一個字符梅忌，*表示他前面的字符的任意次（含0次）狰腌。
比如aaa與a.a和ab*ac*a匹配，但與aa.a和ab*a不匹配牧氮。
解題思路：
.就相當于一個萬能字符琼腔，正常匹配即可；但*的匹配會涉及到前一個字符踱葛。所以要分模式串后
一個字符不是*或沒有后一個字符丹莲，模式串后一個字符是*這幾個大的情況光坝，之再考慮.的問題。
package chapter3;
/**
* Created by ryder on 2017/7/13.
* 正則表達式匹配
* 完成.(任何一個字符)和*(前面字符的任意次數(shù))
*/
public class P124_RegularExpressionsMatching {
public static boolean match(String str,String pattern){
if(str==null || pattern==null)
return false;
return matchCore(new StringBuilder(str),0,new StringBuilder(pattern),0);
}
public static boolean matchCore(StringBuilder str,Integer strIndex,StringBuilder pattern, Integer patternIndex){
//如果匹配串和模式串都匹配結(jié)束
if(strIndex==str.length() && patternIndex==pattern.length())
return true;
if(strIndex!=str.length() && patternIndex==pattern.length())
return false;
if(strIndex==str.length() && patternIndex!=pattern.length()) {
if(patternIndex+1<pattern.length()&&pattern.charAt(patternIndex+1)=='*')
return matchCore(str,strIndex,pattern,patternIndex+2);
else
return false;
}
//如果模式串的第二個字符不是*或者已經(jīng)只剩一個字符了
if(patternIndex==pattern.length()-1|| pattern.charAt(patternIndex+1)!='*'){
if(pattern.charAt(patternIndex)=='.' || pattern.charAt(patternIndex)==str.charAt(strIndex))
return matchCore(str,strIndex+1,pattern,patternIndex+1);
else
return false;
}
//如果模式串的第二個字符是*
else{
//模式和當前字符匹配上
if(pattern.charAt(patternIndex)=='.'||pattern.charAt(patternIndex)==str.charAt(strIndex))
return matchCore(str,strIndex+1,pattern,patternIndex) //*匹配多個相同字符
||matchCore(str,strIndex+1,pattern,patternIndex+2)//*只匹配當前字符
||matchCore(str,strIndex,pattern,patternIndex+2); //*一個字符都不匹配
//模式和當前字符沒有匹配上
else
return matchCore(str,strIndex,pattern,patternIndex+2);
}
}
public static void main(String[] args){
System.out.println(match("aaa","a.a"));//true
System.out.println(match("aaa","ab*ac*a"));//true
System.out.println(match("aaa","aa.a"));//false
System.out.println(match("aaa","ab*a"));//false
}
}
- 表示數(shù)值的字符串
題目要求：
判斷一個字符串是否表示數(shù)值甥材，如+100,5e2盯另，-123，-1E-16都是洲赵，
12e鸳惯，1e3.14，+-5,1.2.3,12e+5.4都不是叠萍。
提示：表示數(shù)值的字符串遵循模式A[.[B]][e|EC] 或者 .B[e|EC];
A,B,C表示整數(shù)芝发，|表示或。[]表示可有可無苛谷。
解題思路：
此題也沒有沒什么特殊思路辅鲸，就按照A[.[B]][e|EC] 或者 .B[e|EC];
A,B,C這兩種模式匹配下即可。
package chapter3;
/**
* Created by ryder on 2017/7/13.
* 表示數(shù)值的字符串
*/
public class P127_NumberStrings {
public static boolean isNumeric(String str){
//正確的形式：A[.[B]][e|EC] 或者 .B[e|EC];
if(str==null||str.length()==0)
return false;
int index;
if(str.charAt(0)!='.'){
index = scanInteger(str,0);
if(index==-1)
return false;
if(index==str.length())
return true;
if(str.charAt(index)=='.'){
if(index==str.length()-1)
return true;
index = scanInteger(str,index+1);
if(index==str.length())
return true;
}
if(str.charAt(index)=='e'||str.charAt(index)=='E'){
index = scanInteger(str,index+1);
if(index==str.length())
return true;
else
return false;
}
return false;
}
else{
index = scanInteger(str,1);
if(index==-1)
return false;
if(index==str.length())
return true;
if(str.charAt(index)=='e'||str.charAt(index)=='E'){
index = scanInteger(str,index+1);
if(index==str.length())
return true;
}
return false;
}
}
public static int scanInteger(String str,Integer index){
if(index>=str.length())
return -1;
if(str.charAt(index)=='+'||str.charAt(index)=='-')
return scanUnsignedInteger(str,index+1);
else
return scanUnsignedInteger(str,index);
}
public static int scanUnsignedInteger(String str,Integer index){
int origin = index;
while(str.charAt(index)>='0'&&str.charAt(index)<='9'){
index++;
if(index==str.length())
return index;
}
if(origin==index)
index = -1;
return index;
}
public static void main(String[] args){
System.out.println(isNumeric("+100"));//true
System.out.println(isNumeric("5e2")); //true
System.out.println(isNumeric("-123"));//true
System.out.println(isNumeric("3.1416"));//true
System.out.println(isNumeric("-1E-16"));//true
System.out.println(isNumeric(".6"));//true
System.out.println(isNumeric("6."));//true
System.out.println(isNumeric("12e"));//false
System.out.println(isNumeric("1a3.14"));//false
System.out.println(isNumeric("1.2.3"));//false
System.out.println(isNumeric("+-5"));//false
System.out.println(isNumeric("12e+5.4"));//false
}
}
