牛客网——Java刷题篇

迈不过友情╰ 2023-10-10 14:46 17阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

![4634d3e9514841e5ba541625c536e129.png][]

**文章目录**

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

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

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[4634d3e9514841e5ba541625c536e129.png]: https://img-blog.csdnimg.cn/4634d3e9514841e5ba541625c536e129.png