[java刷算法]剑指offer插入排序、双指针解题
- 🧛♂️个人主页：杯咖啡
- 💡进步是今天的活动，明天的保证！
- ✨目前正在学习：SSM框架,算法刷题
- 👉本文收录专栏 ： java刷算法牛客—剑指offer
- 🙌牛客网，刷算法过面试的神级网站，用牛客你也牛。 👉免费注册和我一起学习刷题👈
- 🐳希望大家多多支持🥰一起进步呀！
- 😎The man who fears losing has already lost.
怕输的人已经输了。 - 《权力的游戏》
✨今日三剑
JZ20 表示数值的字符串
JZ21 调整数组顺序使奇数位于偶数前面(一)
JZ22 链表中倒数最后k个结点
@[TOC]
JZ20 表示数值的字符串
题目描述
思路详解
看到是个字符串，那么我们就使用一个遍历字符串的全局变量作为下标，然后遍历字符串依次检查每个字符，根据字符属于的类型进行判断。
- step 1：先判断空串的情况。
- step 2：遍历字符前面的空格，将下标移到第一个不是空格的位置。遍历字符串后面的空格，将长度限制在最后一个空格。若是长度小于下标，说明全是空格。
- step 3：剩余部分判断，开始找数字，判断是不是一个有符号的整数，优先判断符号，直到遇到非数字停止。
- step 4：如果有小数点，那么开始判断小数点后是不是一个无符号的整数，也是遍历直到遇到非数字为止，出现小数点的话，小数点前和小数点后的数字任意有一即可。
- step 5：若是出现字母e或者E，那么需要判断后面是不是一个有符号的整数，，也是遍历直到遇到非数字为止，e前后都要数字。
- step 6：最后检查下标是不是遍历到了刚刚限制的长度，若是没有，说明后面还有非空格，不符合要求。
代码与结果
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return bool布尔型
*/
//遍历字符串的下标
private int index = 0;
//有符号判断
private boolean integer(String s){
if(index < s.length() && (s.charAt(index) == '-' || s.charAt(index) == '+'))
index++;
return unsigned_integer(s);
}
//无符号数判断
private boolean unsigned_integer(String s){
int temp = index;
while(index < s.length() && (s.charAt(index) >= '0' && s.charAt(index) <= '9'))
index++;
return index > temp;
}
public boolean isNumeric (String str) {
//先判断空串
if(str == null || str.length() == 0)
return false;
//去除前面的空格
while(index < str.length() && str.charAt(index) == ' ')
index++;
int n = str.length() - 1;
//去除字符串后面的空格
while(n >= 0 && str.charAt(n) == ' ')
n--;
//限制的长度比下标1
n++;
//全是空格情况
if(n < index)
return false;
//判断前面的字符是否是有符号的整数
boolean flag = integer(str);
//如果有小数点
if(index < n && str.charAt(index) == '.'){
index++;
//小数点前后有无数字可选
flag = unsigned_integer(str) || flag;
}
//如果有e
if(index < n && (str.charAt(index) == 'e' || str.charAt(index) == 'E')){
index++;
//e后面必须全是整数
flag = flag && integer(str);
}
//是否字符串遍历结束
return flag && (index == n);
}
} 
JZ21 调整数组顺序使奇数位于偶数前面(一)
题目描述
思路详解
这里我们可以使用插入排序的思想进行解题，我们只需关注奇数就好，每次遇到奇数就进行移位。这里加入插入排序的动画。
代码与实现
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
//使用插入排序的思想
public int[] reOrderArray (int[] array) {
// 首先是对数值长度进行特判
if(array==null||array.length==0) return array;
//记录已经是奇数的位置
int j=0;
int temp = 0;
for(int i =0;i<array.length;i++){
temp = array[i];
//如果该值为偶数
if(array[i]%2==0){
continue;
}else{//该值为奇数
int k =i;
while(k>j){
//这区间整体向后移动一位
array[k] = array[k-1];
k--;
}
//移位之后将对应的值赋值
array[k] = temp;
j++;
}
}
//返回结果数数组
return array;
}
} 
JZ22 链表中倒数最后k个结点
题目描述
思路详解
本题的思路使用双指针进行解题。
第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。注意，如果第一个指针还没走k步的时候链表就为空了，我们直接返回null即可。
代码与结果
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail(ListNode pHead, int k) {
if (pHead == null)
return pHead;
ListNode first = pHead;
ListNode second = pHead;
//第一个指针先走k步
while (k-- > 0) {
if (first == null)
return null;
first = first.next;
}
//然后两个指针在同时前进
while (first != null) {
first = first.next;
second = second.next;
}
return second;
}
} 
