[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;
}
}

在这里插入图片描述