# Sword finger offer JAVA full code multi implementation [11 ~ 20]

## 11. Title Description

Given a floating-point base of type double and an integer of type int, exponent. Find the exponent power of base.

Ensure that the base and exponent are not the same as 0

Train of thought 1: direct violent running. Just pay attention to the fact that the index may be negative. The time complexity is O (N), although it is O (N), if it is a very large exponential level, it still needs to run for a long time.

```public class Solution {
public double Power(double base, int exponent) {
if(base==0) return 0;
if(exponent==0) return 1;
double res=1;
if(exponent<0){
base=1/base;
exponent=-exponent;
}
while(exponent>0){
exponent--;
res*=base;
}
return res;
}
}```

```public class Solution {
public double Power(double base, int exponent) {
double res=1;
if(exponent<0){
base=1/base;
exponent=-exponent;
}
while(exponent!=0){
if(exponent%2==1){

res*=base;
}
exponent=exponent>>1;
base*=base;
}
return res;
}
}```

## 12. Title Description

Input an integer array, and implement a function to adjust the order of the numbers in the array, so that all the odd numbers are in the first half of the array, all the even numbers are in the second half of the array, and ensure the relative positions between the odd numbers and odd numbers, even numbers and even numbers are unchanged.

Idea 1: use extra space. Store in two queues. Time complexity O (N) space complexity O (N)

```import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
Deque<Integer> deque1=new ArrayDeque();//Odd number
Deque<Integer> deque2=new ArrayDeque();//Even number
for(int i:array){
if(i%2==1){
deque1.offer(i);
}else{
deque2.offer(i);
}
}
int i=0;
while(!deque1.isEmpty()){
array[i++]=deque1.poll();
}
while(!deque2.isEmpty()){
array[i++]=deque2.poll();
}
}
}```

Idea 2: similar to bubble sorting, the first even number found is swapped to the last one, and then traversed forward. Time complexity O (N^2), space complexity O (1)

```import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
int temp=0;
int count=0;//Record the even number
for(int i=array.length-1;i>=0;i--){
if(array[i]%2==0){
for(int j=i;j<array.length-1-count;j++){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
count++;
}

}
}
}```

## 13. Title Description

Input a list and output the k last node in the list.

Train of thought 1: the first reaction. It's also the idea of comparing rubbish. Traverse o twice

```/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
int count=0;
while(cur!=null){
cur=cur.next;
count++;
}
if(count<k) return null;
while(count>k){
count--;
node=node.next;
}
return node;

}
}```

Train of thought 2: other people's ideas. It only needs to traverse once, using two pointers, one takes K-1 first, and then when the first goes to the end, the last one is the last 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) {
int count=0;

while(k>0){
k--;
if(fast!=null){
fast=fast.next;
}else{
return null;
}

}
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
return slow;

}
}```

daixu

Published 8 original articles, won praise 1, visited 1772

Keywords: Java

Added by Think Pink on Thu, 23 Jan 2020 13:31:05 +0200