# 剑指offerJava版（一）

### 数值的整数次方

```public class Solution {
public double Power(double base,int e1) {
int e = Math.abs(e1);
if(e==0)
return 1;
if(e==1)
return base;
double result = Power(base, e>>1);
result *= result;
if(e%2==1)
result *= base;
if(e1<0)
return 1.0/result;
return result;
}
}```

### 调整数组顺序使得奇数位于偶数的前面

```public class Solution {
public void reOrderArray(int [] array) {
int[] arr = new int[array.length];
int k = 0;
for(int i = 0 ; i<array.length;i++){
if(array[i]%2==1)
arr[k++] = array[i];
}
for(int i = 0 ; i<array.length;i++){
if(array[i]%2==0)
arr[k++] = array[i];
}
for(int j = 0 ; j<array.length;j++){
array[j] = arr[j];
}
}
}```

### 链表中倒数第K个节点

```/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null|| k == 0){
return null;
}
ListNode node = head;
for(int i = 0 ; i< k ; i++){
if(node!=null){
node = node.next;
}else{
return null;
}
}
while(node!=null){
node = node.next;
}
}
}```

### 反转链表

```/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pNode = head;
ListNode preNode = null;
ListNode newNode = null;
while(pNode!=null){
ListNode pnext = pNode.next;
if(pNode.next==null)
newNode = pNode;
pNode.next = preNode;
preNode = pNode;
pNode = pnext;
}
return newNode;
}
}```

### 合并两个排序的链表

```/*
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 && list2 == null){
return null;
}
if(list1 == null)
return list2;
if(list2 == null)
return list1;
ListNode list3 = null;
if(list1.val<list2.val){
list3 = list1;
list3.next = Merge(list1.next,list2);
}else{
list3 = list2;
list3.next = Merge(list1,list2.next);
}
return list3;
}
}```

### 树的子结构

```/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean DoesTree(TreeNode r1,TreeNode r2){
if(r2 == null){
return true;
}
if(r1 == null){
return false;
}
if(r1.val != r2.val){
return false;
}
return DoesTree(r1.left,r2.left)&&DoesTree(r1.right,r2.right);
}

public boolean HasSubtree(TreeNode r1,TreeNode r2) {
boolean flag = false;
if(r1 != null && r2 != null){
if(r1.val == r2.val){
flag = DoesTree(r1,r2);
}
if(flag == false){
flag = HasSubtree(r1.left,r2);
}
if(flag == false){
flag = HasSubtree(r1.right,r2);
}
}
return flag;
}
}```

### 二叉树的镜像

8

/

6 10

/ /

5 7 9 11

8

/

10 6

/ /

11 9 7 5

```/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public void Mirror(TreeNode root) {

if(root == null){
return;
}
if(root.left == null && root.right == null)
return;
TreeNode node = root.left;
root.left = root.right;
root.right = node;

if(root.left!=null){
Mirror(root.left);
}
if(root.right!=null){
Mirror(root.right);
}
}
}```

### 顺时针打印矩阵

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.

```import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> list = new ArrayList<>();
public void Print(int[][] matrix,int columns,int rows,int start){
int endX = columns - 1 -start;
int endY = rows -1 -start;
//从左到右打印一行
for (int i = start ; i<= endX;i++ ){
int num = matrix[start][i];
}
//从上到下打印一列
if(start < endY){
for (int j = start+1;j<=endY;j++){
int num = matrix[j][endX];
}
}
//从右到左打印一行
if( start < endX && start < endY){
for (int i = endX-1;i>=start;i--){
int num = matrix[endY][i];
}
}

//从下向上打印一行
if(start<endX && start<endY-1){
for (int j = endY-1;j>=start+1;j--){
int num = matrix[j][start];
}
}
}
public ArrayList<Integer> printMatrix(int [][] matrix) {
int columns = matrix[0].length;//矩阵列数
int rows = matrix.length;//矩行数
if (matrix == null || columns <= 0 || rows <= 0)
return null;
int start = 0;
while (start*2<columns && start*2<rows){
Print(matrix,columns,rows,start);
++start;
}
return list;
}
}```

### 包含min函数的栈

```import java.util.Stack;

public class Solution {

public static Stack<Integer> stack1 = new Stack<>();
public static Stack<Integer> stack2 = new Stack<>();

public void push(int node) {
if(stack2.isEmpty()){
stack2.push(node);
}
if(node <= stack2.peek()){
stack2.push(node);
}else{
stack2.push(stack2.peek());
}
stack1.push(node);
}

public void pop() {
if(stack2.isEmpty()){
throw new RuntimeException();
}
stack1.pop();
stack2.pop();
}
public int top() {
if(stack1.isEmpty()){
throw new RuntimeException();
}
return stack1.peek();
}
public int min() {
if(stack2.isEmpty()){
throw new RuntimeException();
}
return stack2.peek();
}
}```

### 栈的压入，弹出序列

```import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length==0||popA.length==0){
return false;
}
Stack<Integer> stack = new Stack<>();
int j = 0 ;
for (int i = 0 ; i < pushA.length ; i++){
stack.push(pushA[i]);
while (!stack.empty()&&stack.peek() == popA[j]){
stack.pop();
j++;
}
}
return stack.empty();
}
}```

qrcode_for_gh_bca5e6591047_258 (1).jpg