[java刷算法]牛客—剑指offer插入排序、双指针解题

简介: ✨今日三剑JZ20 表示数值的字符串JZ21 调整数组顺序使奇数位于偶数前面(一)JZ22 链表中倒数最后k个结点

文章目录


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

相关文章
|
8天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
34 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
10天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
30 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
14天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
34 2
|
6天前
|
算法 Java 程序员
【算法每日一练及解题思路】有n级台阶,一次只能上1级或2级,共有多少种走法?
本文深入解析了“爬楼梯问题”,探讨了递归与迭代两种解法,并提供了Java代码实现。通过分析问题本质,帮助读者理解动态规划技巧,提高解决实际编程问题的能力。关键词:Java, 算法, 动态规划, 爬楼梯问题, 递归, 迭代。
17 0
|
10天前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
28 0
|
18天前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索(C/C++)
【算法解题思想】动态规划+深度优先搜索(C/C++)
|
18天前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
18天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
12 0
|
2月前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
56 2
|
13天前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
15 0