- 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
題目要求：
實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整數(shù)組中的數(shù)字，使得所有奇數(shù)位于數(shù)組的前半部分，偶數(shù)位于后半部分。
解題思路：
其實(shí)我想到的第一個(gè)思路就是用雙指針從兩端向中間掃描，處理過程與快排很相似，時(shí)間復(fù)雜度o(n)
，這應(yīng)該是最快的解法了。思路簡單，就當(dāng)復(fù)習(xí)下快排吧。至于復(fù)雜度更高的解法，我就不再寫了。
書中提到了一點(diǎn)，是將判斷部分寫成函數(shù)，這樣能夠提升代碼的可擴(kuò)展性，這的確是很好的一個(gè)提醒。
那樣處理之后，這一類問題（非負(fù)數(shù)在前，負(fù)數(shù)在后；能被3整除的在前，不能的在后；）都只需修改
下判斷函數(shù)即可解決。
package chapter3;
/**
* Created by ryder on 2017/7/14.
* 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
*/
public class P129_ReorderArray {
public static void reorder(int[] data){
if(data==null||data.length<2)
return;
int left=0,right=data.length-1;
while(left<right){
while (left<right&&!isEven(data[left]))
left++;
while (left<right&&isEven(data[right]))
right--;
//分別找到奇數(shù)和偶數(shù)進(jìn)行交換
if(left<right){
int temp=data[left];
data[left]=data[right];
data[right]=temp;
}
}
}
public static boolean isEven(int n){
return (n&1)==0;
}
public static void main(String[] args){
int[] data = {1,2,3,4,5,7,7};
reorder(data);
for(int i=0;i<data.length;i++) {
System.out.print(data[i]);
System.out.print('\t');
}
System.out.println();
}
}
- 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
題目要求：
求鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。鏈表的尾節(jié)點(diǎn)定義為倒數(shù)第1個(gè)節(jié)點(diǎn)。
解題思路：
如果先求鏈表的長度，計(jì)算后再從頭遍歷，雖然時(shí)間復(fù)雜度是o(n),但需要兩遍
掃描。更好的方式是使用兩個(gè)距離為k的指針向右移動(dòng)，這種方式只需掃描一遍。
chapter3主要考察細(xì)節(jié)，這道題也不例外。需要注意鏈表是否為空，鏈表長度
是否達(dá)到k，k是否是個(gè)正數(shù)。
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/14.
* 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
*/
public class P134_KthNodeFromEnd {
public static ListNode<Integer> findKthToTail(ListNode<Integer> head,int k){
if(head==null||k<=0)
return null;
ListNode<Integer> slow=head,fast=head;
for(int i=0;i<k;i++){
//i==k-1,第三個(gè)測試?yán)ú贿^
if(fast.next!=null || i==k-1)
fast = fast.next;
else
return null;
}
while(fast!=null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
public static void main(String[] args){
ListNode<Integer> head = new ListNode<>(1);
head.next= new ListNode<>(2);
head.next.next = new ListNode<>(3);
System.out.println(findKthToTail(head,1).val);
System.out.println(findKthToTail(head,2).val);
System.out.println(findKthToTail(head,3).val);
System.out.println(findKthToTail(head,4));
}
}
- 鏈表中環(huán)的入口節(jié)點(diǎn)
題目要求：
假設(shè)一個(gè)鏈表中包含環(huán)，請(qǐng)找出入口節(jié)點(diǎn)。若沒有環(huán)則返回null。
解題思路：
當(dāng)然可以使用遍歷。順序訪問，當(dāng)?shù)诙卧L問同一個(gè)節(jié)點(diǎn)時(shí)，
那么那個(gè)節(jié)點(diǎn)就是入口節(jié)點(diǎn)。不過這種解法需要o(n)的空間。
能不能把空間降為o(1)，時(shí)間依舊為o(n)。當(dāng)然可以。這種
解法的思路是：首先申請(qǐng)兩個(gè)指針，快指針一次前進(jìn)兩步，
慢指針一次前進(jìn)一步，初始化都再鏈表頭部。然后開始移動(dòng)，
如果他們指向了同一個(gè)節(jié)點(diǎn)，則證明有環(huán)，否則沒環(huán)。當(dāng)他
們指向了同一個(gè)節(jié)點(diǎn)時(shí)，慢指針再次初始化，指向頭結(jié)點(diǎn)。
快慢指針前進(jìn)步數(shù)都改為1，當(dāng)他們?cè)俅沃赶蛲粋€(gè)節(jié)點(diǎn)，
這個(gè)節(jié)點(diǎn)就是環(huán)的入口節(jié)點(diǎn)。不明白的話請(qǐng)先看證明過程鏈
接,然后再看我說的思路總結(jié)。
#include <stdio.h>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
ListNode *meet = NULL;
while(fast){
slow = slow->next; //先各走一步
fast = fast->next;
if (!fast){ //fast到鏈表尾，就說明沒有環(huán)，結(jié)點(diǎn)為奇數(shù)個(gè)
return NULL;
}
fast = fast->next; //fast再走一步
if (fast == slow){ //記錄相遇位置
meet = fast;
break;
}
}
while(head && meet){ //head和meet相遇就是環(huán)起點(diǎn)
if (head == meet){
return head;
}
head = head->next;
meet = meet->next;
}
return NULL;
}
};
int main(){
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
ListNode f(6);
ListNode g(7);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
g.next = &c;
Solution solve;
ListNode *node = solve.detectCycle(&a);
if (node){
printf("%d\n", node->val);
}
else{
printf("NULL\n");
}
return 0;
}
- 反轉(zhuǎn)鏈表
解題思路：
想要鏈表反轉(zhuǎn)時(shí)不斷裂，至少需要3個(gè)變量記錄，pre，cur，post。與前面的題目類似，
初始化pre為null，cur為head，post為head.next。初始化之前要注意檢查鏈表的長度。
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/14.
* 反轉(zhuǎn)鏈表
*/
public class P142_ReverseList {
public static ListNode<Integer> reverseList(ListNode<Integer> head){
if(head==null || head.next==null)
return head;
ListNode<Integer> pre = null;
ListNode<Integer> cur = head;
ListNode<Integer> post = head.next;
while(true){
cur.next = pre;
pre = cur;
cur = post;
if(post!=null)
post = post.next;
else
return pre;
}
}
//寫法更簡單
public static ListNode<Integer> reverseList(ListNode<Integer> head) {
if (head == null || head.next == null)
return head;
ListNode<Integer> newHead = null;
while (head != null) {
ListNode<Integer> next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
public static void main(String[] args){
ListNode<Integer> head = new ListNode<>(1);
head.next= new ListNode<>(2);
head.next.next = new ListNode<>(3);
System.out.println(head);
head = reverseList(head);
System.out.println(head);
}
}
- 合并兩個(gè)排序的鏈表
題目要求：
輸入兩個(gè)遞增排序的鏈表，要求合并后保持遞增。
解題思路：
這個(gè)題目是二路鏈表歸并排序的一部分，或者說是最關(guān)鍵的歸并函數(shù)部分。熟悉歸并排序
的話做這個(gè)題應(yīng)該很容易。思路很簡單，注意鏈表的next指針，初始條件，結(jié)束條件即可。
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/14.
* 合并兩個(gè)排序的鏈表
*/
public class P145_MergeSortedLists {
public static ListNode<Integer> merge(ListNode<Integer> head1,ListNode<Integer> head2){
if(head1==null)
return head2;
if(head2==null)
return head1;
ListNode<Integer> index1 = head1;
ListNode<Integer> index2 = head2;
ListNode<Integer> index = null;
if(index1.val<index2.val) {
index = index1;
index1 = index1.next;
}
else {
index = index2;
index2 = index2.next;
}
while(index1!=null && index2!=null){
if(index1.val<index2.val) {
index.next = index1;
index = index.next;
index1 = index1.next;
}
else {
index.next = index2;
index = index.next;
index2 = index2.next;
}
}
if(index1!=null)
index.next = index1;
else
index.next = index2;
return head1.val<head2.val?head1:head2;
}
public static void main(String[] args){
ListNode<Integer> head1 = new ListNode<>(1);
head1.next= new ListNode<>(3);
head1.next.next = new ListNode<>(5);
head1.next.next.next = new ListNode<>(7);
ListNode<Integer> head2 = new ListNode<>(2);
head2.next= new ListNode<>(4);
head2.next.next = new ListNode<>(6);
head2.next.next.next = new ListNode<>(8);
System.out.println(head1);
System.out.println(head2);
ListNode<Integer> head =merge(head1,head2);
System.out.println(head);
}
}
- 樹的子結(jié)構(gòu)
題目要求：
輸入兩棵二叉樹A和B，判斷B是不是A的子結(jié)構(gòu)。
解題思路：
當(dāng)A有一個(gè)節(jié)點(diǎn)與B的根節(jié)點(diǎn)值相同時(shí)，則需要從A的那個(gè)節(jié)點(diǎn)開始嚴(yán)格匹配，對(duì)應(yīng)于下面的
tree1HasTree2FromRoot函數(shù)。如果匹配不成功，則返回到開始匹配的那個(gè)節(jié)點(diǎn)，對(duì)它的
左右子樹繼續(xù)判斷是否與B的根節(jié)點(diǎn)值相同，重復(fù)上述過程。
package structure;
/**
* Created by ryder on 2017/6/12.
* 樹節(jié)點(diǎn)
*/
public class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T val){
this.val = val;
this.left = null;
this.right = null;
}
}
package chapter3;
import structure.TreeNode;
/**
* Created by ryder on 2017/7/14.
* 樹的子結(jié)構(gòu)
*/
public class P148_SubstructureInTree {
public static boolean hasSubtree(TreeNode<Integer> root1, TreeNode<Integer> root2){
if(root2==null)
return true;
if(root1==null)
return false;
if(root1.val.equals(root2.val)){
if(tree1HasTree2FromRoot(root1,root2))
return true;
}
return hasSubtree(root1.left,root2) || hasSubtree(root1.right,root2);
}
public static boolean tree1HasTree2FromRoot(TreeNode<Integer> root1, TreeNode<Integer> root2){
if(root2==null)
return true;
if(root1==null)
return false;
if(root1.val.equals(root2.val) && tree1HasTree2FromRoot(root1.left,root2.left) && tree1HasTree2FromRoot(root1.right,root2.right))
return true;
else
return false;
}
public static void main(String[] args){
TreeNode<Integer> root1 = new TreeNode<>(8);
root1.left = new TreeNode<>(8);
root1.right = new TreeNode<>(7);
root1.left.left = new TreeNode<>(9);
root1.left.right = new TreeNode<>(2);
root1.left.right.left = new TreeNode<>(4);
root1.left.right.right = new TreeNode<>(7);
TreeNode<Integer> root2 = new TreeNode<>(8);
root2.left = new TreeNode<>(9);
root2.right = new TreeNode<>(2);
TreeNode<Integer> root3 = new TreeNode<>(2);
root3.left = new TreeNode<>(4);
root3.right = new TreeNode<>(3);
System.out.println(hasSubtree(root1,root2));
System.out.println(hasSubtree(root1,root3));
}
}
- 二叉樹的鏡像
題目要求：
求一棵二叉樹的鏡像。
解題思路：
二叉樹的鏡像，即左右子樹調(diào)換。從上到下，遞歸完成即可。
package structure;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/6/12.
* 樹節(jié)點(diǎn)
*/
public class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T val){
this.val = val;
this.left = null;
this.right = null;
}
//層序遍歷
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("[");
Queue<TreeNode<T>> queue = new LinkedList<>();
queue.offer(this);
TreeNode<T> temp;
while(!queue.isEmpty()){
temp = queue.poll();
stringBuilder.append(temp.val);
stringBuilder.append(",");
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
}
stringBuilder.deleteCharAt(stringBuilder.lastIndexOf(","));
stringBuilder.append("]");
return stringBuilder.toString();
}
}
package chapter4;
import structure.TreeNode;
/**
* Created by ryder on 2017/7/15.
* 二叉樹的鏡像
*/
public class P151_MirrorOfBinaryTree {
public static void mirrorRecursively(TreeNode<Integer> root){
if(root==null)
return;
if(root.left==null&&root.right==null)
return;
TreeNode<Integer> temp = root.left;
root.left = root.right;
root.right = temp;
mirrorRecursively(root.left);
mirrorRecursively(root.right);
}
public static void main(String[] args){
TreeNode<Integer> root = new TreeNode<>(8);
root.left = new TreeNode<>(6);
root.right = new TreeNode<>(10);
root.left.left = new TreeNode<>(5);
root.left.right = new TreeNode<>(7);
root.right.left = new TreeNode<>(9);
root.right.right = new TreeNode<>(11);
System.out.println(root);
mirrorRecursively(root);
System.out.println(root);
}
}
- 對(duì)稱的二叉樹
題目要求：
判斷一棵二叉樹是不是對(duì)稱的。如果某二叉樹與它的鏡像一樣，稱它是對(duì)稱的。
解題思路：
比較直接的思路是比較原樹與它的鏡像是否一樣。書中就是用的這種方式
（比較二叉樹的前序遍歷和對(duì)稱前序遍歷）。但這種思路下，樹的每個(gè)節(jié)
點(diǎn)都要讀兩次，也就是遍歷兩遍。
其實(shí)可以只遍歷一次完成判斷：我們可以通過判斷待判斷二叉樹的左子樹
與右子樹是不是對(duì)稱的來得知該二叉樹是否是對(duì)稱的。
package structure;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/6/12.
* 樹節(jié)點(diǎn)
*/
public class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T val){
this.val = val;
this.left = null;
this.right = null;
}
//層序遍歷
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("[");
Queue<TreeNode<T>> queue = new LinkedList<>();
queue.offer(this);
TreeNode<T> temp;
while(!queue.isEmpty()){
temp = queue.poll();
stringBuilder.append(temp.val);
stringBuilder.append(",");
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
}
stringBuilder.deleteCharAt(stringBuilder.lastIndexOf(","));
stringBuilder.append("]");
return stringBuilder.toString();
}
}
package chapter4;
import structure.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/7/15.
* 對(duì)稱的二叉樹
*/
public class P159_SymmetricalBinaryTree {
//遞歸實(shí)現(xiàn)
public static boolean isSymmetrical(TreeNode<Integer> root){
if(root==null)
return true;
if(root.left==null && root.right==null)
return true;
if(root.left==null || root.right==null)
return false;
return isSymmetrical(root.left,root.right);
}
public static boolean isSymmetrical(TreeNode<Integer> root1,TreeNode<Integer> root2){
if(root1==null && root2==null)
return true;
if(root1==null || root2==null)
return false;
if(!root1.val.equals(root2.val))
return false;
return isSymmetrical(root1.left,root2.right) && isSymmetrical(root1.right,root2.left);
}
//迭代實(shí)現(xiàn)
public static boolean isSymmetrical2(TreeNode<Integer> root){
if(root==null)
return true;
if(root.left==null && root.right==null)
return true;
if(root.left==null || root.right==null)
return false;
Queue<TreeNode<Integer>> queueLeft = new LinkedList<>();
Queue<TreeNode<Integer>> queueRight = new LinkedList<>();
queueLeft.offer(root.left);
queueRight.offer(root.right);
TreeNode<Integer> tempLeft,tempRight;
while(!queueLeft.isEmpty()|| !queueRight.isEmpty()){
tempLeft = queueLeft.poll();
tempRight = queueRight.poll();
if(tempLeft.val.equals(tempRight.val)){
if(tempLeft.left!=null)
queueLeft.offer(tempLeft.left);
if(tempLeft.right!=null)
queueLeft.offer(tempLeft.right);
if(tempRight.right!=null)
queueRight.offer(tempRight.right);
if(tempRight.left!=null)
queueRight.offer(tempRight.left);
}
else
return false;
}
if(queueLeft.isEmpty() && queueRight.isEmpty())
return true;
else
return false;
}
public static void main(String[] args){
TreeNode<Integer> root = new TreeNode<>(8);
root.left = new TreeNode<>(6);
root.right = new TreeNode<>(6);
root.left.left = new TreeNode<>(5);
root.left.right = new TreeNode<>(7);
root.right.left = new TreeNode<>(7);
root.right.right = new TreeNode<>(5);
System.out.println(isSymmetrical(root));
System.out.println(isSymmetrical2(root));
}
}
- 順時(shí)針打印矩陣
題目要求：
輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序一次打印出每一個(gè)數(shù)字。
如果輸入如下矩陣：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
則依次打印出1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10。
解題思路：
此題的任務(wù)清晰明了，需要小心的是要考慮清楚邊界情況。
上例中，環(huán)繞一次后，剩下的矩陣行數(shù)為2，列數(shù)為2，可以看成一個(gè)新的矩陣，
繼續(xù)環(huán)繞打印?？梢姡祟}可以用遞歸解決。
示例中行數(shù)與列數(shù)是相等的，所以能夠組成完整的環(huán)（完整指能夠環(huán)繞一圈）；
其實(shí)，只要行數(shù)和列數(shù)中，比較小的那個(gè)是偶數(shù)，就能夠組成完整的環(huán)。
如果行數(shù)和列數(shù)中比較小的那個(gè)是奇數(shù)，則遞歸到終止前的剩余元素?zé)o法成環(huán)。
如果較小的是行數(shù)，則剩余元素的組成的形狀類似于“|”；如果較小的是列數(shù)，
則剩余元素的組成的形狀類似于“—”。
重點(diǎn)：
因此，當(dāng)未訪問行數(shù)和未訪問列數(shù)都大于等于2時(shí)，按照完整環(huán)的邏輯遞歸訪問
即可。當(dāng)不滿足上述條件，判斷剩余元素是“|”型還是“—”型，然后按照不完整環(huán)
的邏輯訪問即可。
package chapter4;
/**
* Created by ryder on 2017/7/16.
*
*/
public class P161_PrintMatrix {
public static void printMatrix(int[][] data){
if(data==null)
return ;
if(data.length==0||data[0].length==0)
return ;
int rowMax = data.length-1,rowLen = data.length;
int colMax =data[0].length-1,colLen = data[0].length;
int row=0,col=0,round=0;
while(rowLen-2*row>1 && colLen-2*col>1){
for(;col<=colMax-round;col++){
System.out.print(data[row][col]);
System.out.print("\t");
}
for(col=col-1,row=row+1;row<rowMax-round;row++){
System.out.print(data[row][col]);
System.out.print("\t");
}
for(;col>=round;col--){
System.out.print(data[row][col]);
System.out.print("\t");
}
for(col=col+1,row=row-1;row>round;row--){
System.out.print(data[row][col]);
System.out.print("\t");
}
row=row+1;
col=col+1;
round++;
}
//如果行數(shù)與列數(shù)中較小的那個(gè)是偶數(shù)，則能組成完整的環(huán)，在while中就完成了遍歷
if(rowLen-2*row==0 || colLen-2*col==0){
System.out.println();
}
//如果行數(shù)與列數(shù)中較小的是行數(shù)，且是奇數(shù)，則還需補(bǔ)充訪問一行
if(rowLen-2*row==1){
for(;col<=colMax-round;col++){
System.out.print(data[row][col]);
System.out.print("\t");
}
System.out.println();
}
//如果行數(shù)與列數(shù)中較小的是列數(shù)，且是奇數(shù)，則還需補(bǔ)充訪問一列
if(colLen-2*col==1){
for(;row<=rowMax-round;row++){
System.out.print(data[row][col]);
System.out.print("\t");
}
System.out.println();
}
}
public static void main(String[] args){
int[][] data1={
{1,2,3,4},
{12,13,14,5},
{11,16,15,6},
{10,9,8,7},
};
int[][] data2={
{1,2,3,4},
{10,11,12,5},
{9,8,7,6},
};
int[][] data3={
{1,2,3},
{10,11,4},
{9,12,5},
{8,7,6},
};
int[][] data4={
{1,2,3},
{8,9,4},
{7,6,5},
};
printMatrix(data1);
printMatrix(data2);
printMatrix(data3);
printMatrix(data4);
}
}
- 包含min函數(shù)的棧
題目要求：
定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的min函數(shù)。
要求在該棧中，調(diào)用min，push及pop的時(shí)間復(fù)雜度都是o(1)。
解題思路：
期望獲知當(dāng)前棧的最小值，最直接的方法是全部彈出求最小值，然后再全部壓入。
這種方式時(shí)間消耗較大。另一種思路，可以用空間換時(shí)間：自己實(shí)現(xiàn)一個(gè)棧，棧中
有記錄數(shù)據(jù)的數(shù)據(jù)棧，同時(shí)也有記錄最小值的min棧，本帖就是采用的此方法。記
得曾經(jīng)看過一個(gè)更巧妙地方法，用一個(gè)變量來記錄最小值，壓入與彈出都會(huì)因一定
的規(guī)則修改該變量，思路比較精奇，可遇不可求，有興趣的可以去搜搜看,比如:
http://www.cnblogs.com/javawebsoa/archive/2013/05/21/3091727.html
package chapter4;
import java.util.Stack;
/**
* Created by ryder on 2017/7/16.
* 包含min函數(shù)的棧
*/
public class P165_StackWithMin {
public static void main(String[] args){
StackWithMin<Integer> stack = new StackWithMin<>();
stack.push(3);
stack.push(4);
stack.push(2);
stack.push(1);
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
}
}
class StackWithMin<T extends Comparable>{
private Stack<T> stackData = new Stack<>();
private Stack<T> stackMin = new Stack<>();
public void push(T data){
stackData.push(data);
if(stackMin.isEmpty())
stackMin.push(data);
else{
T temp = stackMin.peek();
if(temp.compareTo(data)<0)
stackMin.push(temp);
else
stackMin.push(data);
}
}
public T pop(){
if(stackData.isEmpty())
return null;
stackMin.pop();
return stackData.pop();
}
public T min(){
if(stackMin.isEmpty())
return null;
return stackMin.peek();
}
}
- 棧的壓入彈出序列
題目要求：
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，判斷第二個(gè)序列是否為該棧的彈出序序列。
假設(shè)壓入棧的所有數(shù)字均不相等。例如，壓入序列為(1,2,3,4,5)，序列(4,5,3,2,1)是它的
彈出序列，而(4,3,5,1,2)不是。
解題思路：
對(duì)于一個(gè)給定的壓入序列，由于彈出的時(shí)機(jī)不同，會(huì)出現(xiàn)多種彈出序列。如果是選擇題，依照后
進(jìn)先出的原則，復(fù)現(xiàn)一下棧的壓入彈出過程就很容易判斷了。寫成程序同樣如此，主要步驟如下：
步驟1：棧壓入序列第一個(gè)元素，彈出序列指針指彈出序列的第一個(gè)；
步驟2：判斷棧頂元素是否等于彈出序列的第一個(gè)元素：
步驟2.1：如果不是，壓入另一個(gè)元素，進(jìn)行結(jié)束判斷，未結(jié)束則繼續(xù)執(zhí)行步驟2；
步驟2.2：如果是，棧彈出一個(gè)元素，彈出序列指針向后移動(dòng)一位，進(jìn)行結(jié)束判斷，
未結(jié)束則繼續(xù)執(zhí)行步驟2；
結(jié)束條件：如果彈出序列指針還沒到結(jié)尾但已經(jīng)無元素可壓入，則被測序列不是彈出序列。
如果彈出序列指針以判斷完最后一個(gè)元素，則被測序列是彈出序列。
當(dāng)然，進(jìn)行判斷前需要進(jìn)行一些檢查，比如傳入?yún)?shù)是否為null，壓入序列與彈出序列長度是否一致。
package chapter4;
import java.util.Stack;
/**
* Created by ryder on 2017/7/17.
* 棧的壓入彈出序列
*/
public class P168_StackPushPopOrder {
public static boolean isPopOrder(int[] pushSeq,int[] popSeq){
if(pushSeq==null||popSeq==null||pushSeq.length!=popSeq.length)
return false;
Stack<Integer> stack = new Stack<>();
int pushSeqIndex=0,popSeqIndex=0;
//出棧序列全部出棧跳出，或者返回false跳出
while (popSeqIndex<popSeq.length){
//當(dāng)為空或者棧頂不是出棧序列指向的當(dāng)前元素就入棧
if(stack.isEmpty()||stack.peek()!=popSeq[popSeqIndex]) {
if(pushSeqIndex<pushSeq.length)
stack.push(pushSeq[pushSeqIndex++]);
//指針指向push入棧序列沒有數(shù)據(jù)的位置了
else
return false;
}
else{
stack.pop();
popSeqIndex++;
}
}
return true;
}
public static void main(String[] args){
int[] push = {1,2,3,4,5};
int[] pop1 = {4,5,3,2,1};
int[] pop2 = {4,3,5,1,2};
System.out.println(isPopOrder(push,pop1));
System.out.println(isPopOrder(push,pop2));
}
}
- 32-1 從上到下打印二叉樹
//層序遍歷
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;
}
- 32-2 分行從上到下打印二叉樹
題目要求：
從上到下按層打印二叉樹，同一層的節(jié)點(diǎn)按從左到右的順序打印 ，每一層打印一行。
解題思路：
同樣是層序遍歷，與上一題不同的是，此處要記錄每層的節(jié)點(diǎn)個(gè)數(shù)，在每層打印結(jié)束后多打印一個(gè)回車符。
package structure;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/6/12.
* 樹節(jié)點(diǎn)
*/
public class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T val){
this.val = val;
this.left = null;
this.right = null;
}
}
package chapter4;
import structure.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/7/18.
* 分行從上到下打印二叉樹
*/
public class P174_printTreeInLine {
public static void printTreeInLine(TreeNode<Integer> root){
if(root==null)
return;
Queue<TreeNode<Integer>> queue = new LinkedList<>();
queue.offer(root);
TreeNode<Integer> temp;
while (!queue.isEmpty()){
for(int size=queue.size();size>0;size--){
temp = queue.poll();
System.out.print(temp.val);
System.out.print("\t");
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
}
System.out.println();
}
}
public static void main(String[] args){
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.left = new TreeNode<Integer>(2);
root.right = new TreeNode<Integer>(3);
root.left.left = new TreeNode<Integer>(4);
root.left.right = new TreeNode<Integer>(5);
root.right.left = new TreeNode<Integer>(6);
root.right.right = new TreeNode<Integer>(7);
printTreeInLine(root);
}
}
- 32-3 之字形打印二叉樹
題目要求：
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹。即第一層從左到右打印，第二層從右到左打印，
第三層繼續(xù)從左到右，以此類推。
解題思路：
第k行從左到右打印，第k+1行從右到左打印，可以比較容易想到用兩個(gè)棧來實(shí)現(xiàn)。
另外要注意，根據(jù)是從左到右還是從右到左訪問的不同，壓入左右子節(jié)點(diǎn)的順序也有所不同。
package structure;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/6/12.
* 樹節(jié)點(diǎn)
*/
public class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T val){
this.val = val;
this.left = null;
this.right = null;
}
}
package chapter4;
import structure.TreeNode;
import java.util.Stack;
/**
* Created by ryder on 2017/7/18.
* 之字形打印二叉樹
*/
public class P176_printTreeInSpecial {
public static void printTreeInSpeical(TreeNode<Integer> root){
if(root==null)
return;
Stack<TreeNode<Integer>> stack1 = new Stack<>();
Stack<TreeNode<Integer>> stack2 = new Stack<>();
TreeNode<Integer> temp;
stack1.push(root);
while(!stack1.isEmpty() || !stack2.isEmpty()){
if(!stack1.isEmpty()) {
while (!stack1.isEmpty()) {
temp = stack1.pop();
System.out.print(temp.val);
System.out.print('\t');
if (temp.left != null)
stack2.push(temp.left);
if (temp.right != null)
stack2.push(temp.right);
}
}
else {
while (!stack2.isEmpty()) {
temp = stack2.pop();
System.out.print(temp.val);
System.out.print('\t');
if (temp.right != null)
stack1.push(temp.right);
if (temp.left != null)
stack1.push(temp.left);
}
}
System.out.println();
}
}
public static void main(String[] args){
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.left = new TreeNode<Integer>(2);
root.right = new TreeNode<Integer>(3);
root.left.left = new TreeNode<Integer>(4);
root.left.right = new TreeNode<Integer>(5);
root.right.left = new TreeNode<Integer>(6);
root.right.right = new TreeNode<Integer>(7);
printTreeInSpeical(root);
}
}
- 二叉搜索樹的后序遍歷
題目要求：
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷結(jié)果，假設(shè)輸入數(shù)組的任意兩個(gè)數(shù)都互不相同。
解題思路：
二叉搜索樹的中序遍歷是有序的，而此題是后序遍歷。
后序遍歷可以很容易找到根節(jié)點(diǎn)，然后根據(jù)二叉搜索樹的性質(zhì)（左子樹小于根節(jié)點(diǎn)，右子樹大于根節(jié)點(diǎn)），
可以將序列分為根節(jié)點(diǎn)的左子樹部分與右子樹部分，而后遞歸判斷兩個(gè)子樹。
package chapter4;
/**
* Created by ryder on 2017/7/18.
* 二叉搜索樹的后序遍歷序列
*/
public class P179_SequenceOfBST {
public static boolean verifySquenceOfBST(int[] data){
//空樹
if(data==null||data.length==0)
return false;
return verifySquenceOfBST(data,0,data.length-1);
}
public static boolean verifySquenceOfBST(int[] data,int start,int end){
//數(shù)組長度為2，一定能夠組成BST
if(end-start<=1)
return true;
int root = data[end];
int rightStart =0;
for(int i=0;i<end;i++){
if(data[i]>root){
rightStart = i;
break;
}
}
for(int i=rightStart;i<end;i++){
if(data[i]<root)
return false;
}
return verifySquenceOfBST(data,start,rightStart-1)&&verifySquenceOfBST(data,rightStart,end-1);
}
public static void main(String[] args){
// 8
// / \
// 6 10
// / \ / \
// 5 7 9 11
int[] data = {5,7,6,9,4,10,8};
int[] data1 = {5,7,6,9,11,10,8};
System.out.println(verifySquenceOfBST(data));
System.out.println(verifySquenceOfBST(data1));
}
}
- 二叉樹中和為某一值的路徑
題目要求：
輸入一棵二叉樹和一個(gè)整數(shù)，打印出二叉樹中節(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。
從樹的根節(jié)點(diǎn)開始往下一直到葉節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)形成一條路徑。
解題思路：
需要得到所有從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑，判斷和是否為給定值。自己寫一個(gè)小的二叉樹，
通過模擬上述過程，發(fā)現(xiàn)獲取所有路徑的過程與前序遍歷類似。
因此，可以對(duì)給定二叉樹進(jìn)行前序遍歷。當(dāng)被訪問節(jié)點(diǎn)時(shí)葉節(jié)點(diǎn)時(shí)，判斷路徑和是否為
給定值。此外，為了記錄路徑上的節(jié)點(diǎn)，需要一個(gè)數(shù)組。
package chapter4;
import structure.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
* Created by ryder on 2017/7/18.
* 二叉樹中和為某一值的路徑
*/
public class P182_FindPath {
//用類似于前序遍歷的思路解決
public static void findPath(TreeNode<Integer> root,int exceptedSum){
if(root==null)
return;
List<Integer> path = new ArrayList<>();
findPath(root,path,exceptedSum,0);
}
//curNode為將要被訪問的節(jié)點(diǎn)，還未被加入到path中
public static void findPath(TreeNode<Integer> curNode,List<Integer> path,int exceptedSum,int currentSum){
path.add(curNode.val);
currentSum+=curNode.val;
if(curNode.left!=null)
findPath(curNode.left,path,exceptedSum,currentSum);
if(curNode.right!=null)
findPath(curNode.right,path,exceptedSum,currentSum);
//從右子樹返回當(dāng)前結(jié)點(diǎn)，先判斷是否path和為exceptedSum，是就打印path
if(curNode.left==null && curNode.right==null && currentSum==exceptedSum)
System.out.println(path);
//不是就把當(dāng)前結(jié)點(diǎn)移除
path.remove(path.size()-1) ;
}
public static void main(String[] args) {
// 10
// / \
// 5 12
// / \
// 4 7
TreeNode<Integer> root = new TreeNode<Integer>(10);
root.left = new TreeNode<Integer>(5);
root.right = new TreeNode<Integer>(12);
root.left.left = new TreeNode<Integer>(4);
root.left.right = new TreeNode<Integer>(7);
findPath(root,22);
findPath2(root,22);
}
}
如果二叉樹的所有節(jié)點(diǎn)值都是大于0的（原題中并沒有這個(gè)條件），可以進(jìn)行剪枝。
//如果所有節(jié)點(diǎn)值均大于0，可進(jìn)行剪枝
public static void findPath2(TreeNode<Integer> root,int exceptedSum){
if(root==null)
return;
List<Integer> path = new ArrayList<>();
findPath2(root,path,exceptedSum,0);
}
//curNode為將要被訪問的節(jié)點(diǎn)，還未被加入到path中
public static void findPath2(TreeNode<Integer> curNode,List<Integer> path,int exceptedSum,int currentSum){
path.add(curNode.val);
currentSum+=curNode.val;
//只有當(dāng)currentSum小于exceptedSum時(shí)需要繼續(xù)當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的遍歷
if(currentSum<exceptedSum){
if(curNode.left!=null)
findPath2(curNode.left,path,exceptedSum,currentSum);
if(curNode.right!=null)
findPath2(curNode.right,path,exceptedSum,currentSum);
}
//currentSum大于等于exceptedSum時(shí)可以直接停止當(dāng)前分支的遍歷，因?yàn)楫?dāng)前分支下currentSum只會(huì)越來越大，不會(huì)再有符合要求的解
else if(currentSum==exceptedSum && curNode.left==null && curNode.right==null)
System.out.println(path);
path.remove(path.size()-1) ;
}
- 復(fù)雜鏈表的復(fù)制
題目要求：在復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè)next指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè)random
指針指向鏈表中的任意節(jié)點(diǎn)或null，請(qǐng)完成一個(gè)能夠復(fù)制復(fù)雜鏈表的函數(shù)。
解題思路：
此題定義了一種新的數(shù)據(jù)結(jié)構(gòu)，復(fù)雜鏈表。與傳統(tǒng)鏈表的區(qū)別是多了一個(gè)random指針。本題的
關(guān)鍵點(diǎn)也就在如何高效地完成random指針的復(fù)制。
解法 時(shí)間復(fù)雜度 空間復(fù)雜度
解法一 o(n^2) o(1)
解法二 o(n) o(n)
解法三 o(n) o(1)
/*解法一比較直接：
先把這個(gè)復(fù)雜鏈表當(dāng)做傳統(tǒng)鏈表對(duì)待，只復(fù)制val域與next域（時(shí)間o(n)），再從新鏈表的頭部開始，
對(duì)random域賦值（時(shí)間o(n^2)）。*/
package chapter4;
import java.util.HashMap;
/**
* Created by ryder on 2017/7/18.
* 復(fù)制復(fù)雜鏈表
*/
public class P187_CopyComplexList {
public static class ComplexListNode{
int val;
ComplexListNode next;
ComplexListNode random;
public ComplexListNode(int val) {
this.val = val;
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ComplexListNode cur = this;
while(cur!=null) {
ret.append(cur.val);
if(cur.random!=null)
ret.append("("+cur.random.val+")");
else{
ret.append("(_)");
}
ret.append('\t');
cur = cur.next;
}
return ret.toString();
}
}
//解法一
//time:o(n^2) space:o(1) 新鏈表使用的n個(gè)長度的空間不算入
//先復(fù)制val與next（時(shí)間o(n)），再復(fù)制random域（時(shí)間o(n^2)）
public static ComplexListNode clone1(ComplexListNode head){
if(head==null)
return null;
//需要newHead作為頭，需要newCurPrev去指向newCur
ComplexListNode newHead = new ComplexListNode(head.val);
ComplexListNode cur = head.next;
ComplexListNode newCur = null;
ComplexListNode newCurPrev = newHead;
while (cur!=null){
newCur = new ComplexListNode(cur.val);
newCurPrev.next = newCur;
newCurPrev = newCurPrev.next;
cur = cur.next;
}
cur = head;
newCur = newHead;
ComplexListNode temp = head;
ComplexListNode newTemp = newHead;
while(cur!=null){
if(cur.random!=null){
temp = head;
newTemp = newHead;
//重點(diǎn)在這，temp和newTemp一直往后面找，找到cur的random指向結(jié)點(diǎn)
while (temp!=cur.random){
temp = temp.next;
newTemp = newTemp.next;
}
newCur.random = newTemp;
}
cur = cur.next;
newCur = newCur.next;
}
return newHead;
}
public static void main(String[] args){
ComplexListNode head = new ComplexListNode(1);
ComplexListNode c2 = new ComplexListNode(2);
ComplexListNode c3 = new ComplexListNode(3);
ComplexListNode c4 = new ComplexListNode(4);
ComplexListNode c5 = new ComplexListNode(5);
head.next = c2;
head.random = c3;
head.next.next = c3;
head.next.random = c5;
head.next.next.next = c4;
head.next.next.next.next = c5;
head.next.next.next.random = c2;
System.out.println("original:"+'\t'+head);
System.out.println("clone1: "+'\t'+clone1(head));
System.out.println("clone2: "+'\t'+clone2(head));
System.out.println("clone3: "+'\t'+clone3(head));
}
}
/*解法二是用空間換時(shí)間:
解法一時(shí)間復(fù)雜度高的原因在于確定random域的費(fèi)時(shí)，即假設(shè)原鏈表第m個(gè)節(jié)點(diǎn)指向第k個(gè)節(jié)點(diǎn)，
而在新鏈表的第m個(gè)節(jié)點(diǎn)處無法直接得到第k個(gè)節(jié)點(diǎn)，需從頭遍歷。很自然的想法是用一個(gè)哈希表
記錄舊鏈表每個(gè)節(jié)點(diǎn)到新鏈表對(duì)應(yīng)節(jié)點(diǎn)的映射，從而可以將時(shí)間復(fù)雜度降低為o(n)。
*/
//解法二
//time:o(n) space:o(n)
//使用o(n)的空間，換取了時(shí)間復(fù)雜度的降低
public static ComplexListNode clone2(ComplexListNode head) {
if(head==null)
return null;
HashMap<ComplexListNode,ComplexListNode> oldToNew = new HashMap<>();
ComplexListNode newHead = new ComplexListNode(head.val);
oldToNew.put(head,newHead);
ComplexListNode cur = head.next;
ComplexListNode newCur = null;
ComplexListNode newCurPrev = newHead;
while (cur!=null){
newCur = new ComplexListNode(cur.val);
//保存新舊鏈表結(jié)點(diǎn)對(duì)應(yīng)關(guān)系
oldToNew.put(cur,newCur);
newCurPrev.next = newCur;
newCurPrev = newCurPrev.next;
cur = cur.next;
}
cur = head;
newCur = newHead;
while(cur!=null){
if(cur.random!=null){
newCur.random = oldToNew.get(cur.random);
}
cur = cur.next;
newCur = newCur.next;
}
return newHead;
}
/*解法三：
思路很巧妙。將復(fù)制的任務(wù)分為如下三個(gè)部分：
1）cloneNodes完成新鏈表節(jié)點(diǎn)的創(chuàng)建，僅對(duì)val域賦值，且每個(gè)新節(jié)點(diǎn)接在原鏈表對(duì)應(yīng)節(jié)點(diǎn)的后面。
如A->B->C,處理完后為A->A'->B->B'->C->C'，時(shí)間復(fù)雜度o(n)。
2）connectRandomNode完成random域的賦值。假設(shè)A.random=C,我們需要設(shè)置A'.random=C'，此處
獲取C'可以在o(1)的時(shí)間復(fù)雜度完成，全部賦值完畢時(shí)間復(fù)雜度為o(n)。
3）reconnectNodes就是將上述鏈表重組，使A->A'->B->B'->C->C'變?yōu)锳->B->C，A'->B'->C'。
此處需要注意尾部null的處理。*/
//解法三
//time:o(n) space:o(1)
public static ComplexListNode clone3(ComplexListNode head) {
if(head==null)
return null;
cloneNodes(head);
connectRandomNodes(head);
return reconnectNodes(head);
}
public static void cloneNodes(ComplexListNode head){
ComplexListNode cur = head;
ComplexListNode temp = null;
while (cur!=null){
temp = new ComplexListNode(cur.val);
temp.next = cur.next;
cur.next = temp;
cur = cur.next.next;
}
}
public static void connectRandomNodes(ComplexListNode head){
ComplexListNode cur = head;
ComplexListNode curNext = head.next;
while (true){
if(cur.random!=null)
curNext.random = cur.random.next;
cur = cur.next.next;
if(cur == null)
break;
curNext = curNext.next.next;
}
}
public static ComplexListNode reconnectNodes(ComplexListNode head){
ComplexListNode newHead = head.next;
ComplexListNode cur = head;
ComplexListNode newCur = newHead;
while (true){
cur.next = cur.next.next;
cur = cur.next;
if(cur==null){
newCur.next = null;
break;
}
newCur.next = newCur.next.next;
newCur = newCur.next;
}
return newHead;
}
