当前位置:首页 > 技术 > 后端 > 正文内容

牛客网——Java刷题篇

anan3个月前 (09-03)后端257

作者:敲代码の流川枫

博客主页:流川枫的博客

专栏:和我一起学java

语录:Stay hungry stay foolish

工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧   

 

文章目录

1. 检测字符串是否为回文

2. 最后一个单词的长度

3. 第一个只出现一次的字符

1. 检测字符串是否为回文

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释:"amanaplanacanalpanama" 是回文串
示例 2:

输入: "race a car"
输出: false
解释:"raceacar" 不是回文串

提示:

1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成

解题思路

验证回文串一般解法都是双指针,而且是使用头尾指针,头指针指向字符串的第一个元素,尾指针指向字符串的最后一个元素,从字符串两端往中间遍历和比较。本题的关键在于字符串是由 ASCII 字符组成,而我们验证时只需要考虑字母和数字字符,因此要把其他字符过滤掉

题解: 

class Solution {
    public boolean isPalindrome(String s) {
        // 左指针
        int left = 0;
        // 右指针
        int right = s.length() - 1;

        // 左右指针分别从前和从后往中间移动
        while (left < right) {
            char c1 = s.charAt(left);
            char c2 = s.charAt(right);
            if (!Character.isLetterOrDigit(c1)) {
                // 过滤掉非字母和数字字符
                left++;
                continue;
            }
            if (!Character.isLetterOrDigit(c2)) {
                // 过滤掉非字母和数字字符
                right--;
                continue;
            }
            // 忽略字母大小写
            if (Character.toLowerCase(c1) != Character.toLowerCase(c2)) {
                return false;
            }
            // 挪动指针
            left++;
            right--;
        }
        return true;
    }
}

2. 最后一个单词的长度

计算字符串最后一个单词的长度,单词以空格隔开,字符串长度小于5000。(注:字符串末尾不以空格为结尾)

输入描述:

输入一行,代表要计算的字符串,非空,长度小于5000。

输出描述:

输出一个整数,表示输入字符串最后一个单词的长度。

示例1

输入:hello nowcoder

输出:8

说明:最后一个单词为nowcoder,长度为8

方法一(指针)

解题思路

定义一个指针变量。

从后往前遍历字符串,当遇到空格时,用指针记录位置信息,并终止循环。

总长度减去指针到开头一段的长度,即得到最后一个单词的长度。

题解: 

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        //标准输入
        Scanner sc=new Scanner(System.in);
        //键盘输入字符串
        String s=sc.nextLine();
        //定义指针变量
        int index=-1;
        for(int i=s.length()-1;i>=0;i--){
            //从后往前第一个空格的位置
            if(s.charAt(i)==' '){
                index=i;
                break;
            }
        }
        //总长度减去指针到开头一段的长度,即得到最后一个单词的长度
        System.out.println(s.length()-index-1);
    }
}

时间复杂度:最坏情况下遍历整个字符串,所以时间复杂度为O(n)O(n)O(n)。

空间复杂度:需要额外常数级别的空间,所以空间复杂度为O(1)O(1)O(1)。

方法二(字符串分割)

解题思路

通过split函数将原字符串分割为字符串数组。

字符串数组最后一个元素即是原字符串的最后一个单词,直接输出其长度。

题解: 

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        //标准输入
        Scanner sc=new Scanner(System.in);
        //键盘输入字符串
        String s=sc.nextLine();
        //以空格分割为字符串数组
        String[] arr=s.split(" ");
        //字符串数组最后一个元素即是原字符串的最后一个单词,直接输出其长度
        System.out.println(arr[arr.length-1].length());
    }
}

时间复杂度:字符串分割需要遍历整个字符串,所以时间复杂度为O(n)O(n)O(n)

空间复杂度:最坏情况下需要大小为n-1的字符串数组存储所有的单词,所以空间复杂度为O(n)O(n)O(n)

3. 第一个只出现一次的字符

给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1 。

示例 1:

输入: s = "leetcode"
输出: 0
示例 2:

输入: s = "loveleetcode"
输出: 2
示例 3:

输入: s = "aabb"
输出: -1

提示:

  • 1 <= s.length <= 105
  • s 只包含小写字母

解题思路

1.统计各个字符出现次数

定义一个计数数组count[],遍历字符数组,如果字符出现多次,则count++

2.重新遍历字符数组

重新遍历一次 字符数组,如果发现「它」只出现一次,直接返回对应的下标,否则循环终止之后返回 -1

题解:

public int firstUniqChar(String s){
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);
            count[ch-'a'] ++;

        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(count[ch-'a'] == 1){
                return i;
            }
        }
        return -1;
}

“ 本期的分享就到这里了, 记得给博主一个三连哈,你的支持是我创作的最大动力!

,https://blog.csdn.net/chenchenchencl/article/details/126388369
打赏
版权声明:所有来源为第三方内容,若本站收录的文章无意侵犯了贵司版权,请给下面邮箱地址来信,我们会及时处理和回复,谢谢。

管理员邮箱:42004990@qq.com

微信公众号

分享给朋友:

相关文章

【每日蓝桥】50、一七年省赛Java组真题“包子凑数”

【每日蓝桥】50、一七年省赛Java组真题“包子凑数”

你好呀,我是灰小猿,一个超会写bug的程序猿! 欢迎大家关注我的专栏“每日蓝桥”,该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题,解析其中存在的算法思想、数据结构等内容,帮助大家学习到更多...

CGBTN2108-总结复习

CGBTN2108-总结复习

DAY06 复习 1. 面向过程 面向过程也是一种编程思想,这种思想,强调凡事要亲力亲为,每一步都是自己来做 2.面向对象 Java是一门面向对象的语言 面向对象OOP也是一种编程思想,这种思...

阿里四面:kafka何时、如何删除Topic?

阿里四面:kafka何时、如何删除Topic?

Topic是怎么被删除的? Kafka有很多状态机和管理器,如Controller通道管理器ControllerChannelManager、处理Controller事件的ControllerEve...

Java-Jackson使用详解

Java-Jackson使用详解

    Java-Jackson使用详解 序列化 Json是什么? 1.基本规则 2.获取数据 3.用途 Jackson 1.导入Jar包 2.Json注解...

Spring ioc和aop (一)

Spring ioc和aop (一)

Ioc 控制反转 -> 依赖 DI (依赖注入) + 容器container Aop 切面编程 -> 依赖 proxy (动态代理) 以上两个哥们儿就构成了 Spring 框架的核心功能...

Java-----多线程【死锁、案例 与 Lock锁】

Java-----多线程【死锁、案例 与 Lock锁】

死锁 多个线程各自占有一些共享资源,并且互相等待其他线程占有的资源才能运行,而导致两个或者多个线程都在等待对方释放资源,都停止执行的情形。某一个同步块同时拥有“两个以上对象的锁”时,就可能会发...