【Java】String类OJ题

梦里梦外; 2023-09-28 15:50 15阅读 0赞

> **题目来自力扣和牛客网，为了大家方便找，链接放在下面了**  
> **传送门：**  
> [字符串的第一个唯一字符][Link 1]  
> [字符串最后一个单词的长度][Link 2]  
> [验证回文串][Link 3]

#### 文章目录 ####

*  字符串的第一个唯一字符
 *  字符串最后一个单词的长度
 *  验证回文串

## 字符串的第一个唯一字符 ##

> 题目描述：  
> 给定一个字符串 s ，找到 它的**第一个不重复的字符**，并返回它的索引 。如果不存在，则返回 -1

> **示例 1**：  
> 输入: s = “leetcode”  
> 输出: 0  
> **示例 2**:  
> 输入: s = “loveleetcode”  
> 输出: 2  
> **示例 3**:  
> 输入: s = “aabb”  
> 输出: -1

> 提示:  
> 1 <= s.length <= 105  
> **s 只包含小写字母**

**方法1**：  
**程序实现的思想**：将字符串转为字符数组，使用两层循环遍历查找。  
具体代码如下：

public static int firstUniqChar(String s){
        
            char[] ch = s.toCharArray();
            for (int i = 0; i < ch.length;i++){
        
                int count = 0;
                for (int j = 0; j < ch.length; j++) {
        
                    if(ch[i]==ch[j]){
        
                        count++;
                    }
                }
                if(count == 1)
                {
        
                    return i;
                }
            }
            return -1;
        }

外面的循环是确定以哪个字符作为**比较的基准**，里面的循环是以外面循环确定的字符与整个字符数组进行比较，因为比较时会和自身进行比较一次，所以count会自增，遍历完如果count等于1，它就是第一个唯一的字符，直接返回下标。

> **注意：**  
> 1.toCharArray可以帮助我们把字符串转化为数组。  
> 2.在Java中，**字符串不是以’\\0’作为结束的标志的**。因此数组名.length就是字符串的长度。  
> 3.**在处理比较长的字符串时会很慢，不推荐使用。**

**方法2**：  
**代码实现思想**：遍历字符串，对数组进行计数，如果数组为1就是唯一字符。  
具体代码如下：

public static int firstUniqChar(String s) {
        
            int[] arr = new int[26];
            for (int i = 0; i < s.length(); i++) {
        
                char ch = s.charAt(i);
                arr[ch - 'a']++;
            }
            for (int i = 0; i < s.length(); i++) {
        
                char ch = s.charAt(i);
                if (arr[ch - 'a'] == 1) {
        
                    return i;
                }
            }
            return -1;
        }

> 1.charAt(int index) 返回index位置上字符  
> 2.因为题目说了，只有小写字母，字母有26个。所以我就设置了整型数组的大小就设置了26个长度，字符在内存中存储实际上是ASCII码值，第一次循环用charAt来获得字符串的每一个字符，然后都减去’a’,范围就是0~25.让对应位置的值自增。  
> 第二次循环是**遍历的字符串，而不是数组**，毕竟是要返回字符串的下标，**数组的数值就是字符的数量**。

**方法3**：  
**代码实现的思想**：双向遍历字符串，从前往后和从后往前一起查找同一个字符，然后返回对应位置，如果位置相同，就是唯一的字符。  
具体代码如下：

public static int firstUniqChar(String s) {
        
            for (int i = 0; i < s.length(); i++) {
        
                int front = s.indexOf(s.charAt(i));
                int last = s.lastIndexOf(s.charAt(i));
                if (front == last) {
        
                    return i;
                }
            }
            return -1;
        }

> indexOf(int ch) 返回ch第一次出现的位置  
> lastIndexOf(int ch) 从后往前找，返回ch第一次出现的位置  
> 用charAt来获取字符串的每个字符，作为参数。

## 字符串最后一个单词的长度 ##

> 描述:  
> 计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）  
> 输入描述：  
> 输入一行，代表要计算的字符串，非空，长度小于5000。

> 输出描述：  
> 输出一个整数，表示输入字符串最后一个单词的长度。

> 示例1  
> 输入：  
> hello nowcoder  
> 输出：  
> 8  
> 说明：  
> 最后一个单词为nowcoder，长度为8

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

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

> 示例 1:  
> 输入: “A man, a plan, a canal: Panama”  
> 输出: true  
> 解释：“amanaplanacanalpanama” 是回文串  
> 示例 2:  
> 输入: “race a car”  
> 输出: false  
> 解释：“raceacar” 不是回文串

> 提示：  
> 1 <= s.length <= 2 \* 105  
> 字符串 s 由 ASCII 字符组成

**方法1：**  
**程设实现的思想**：它要求是在字符串中找最后一个单词，找空格，并记录后面字符串的长度。  
代码实现如下：

public static void main(String[] args) {
        
                Scanner in = new Scanner(System.in);
                // 注意 hasNext 和 hasNextLine 的区别
                while (in.hasNextLine()) {
         // 注意 while 处理多个 case
                    String str = in.nextLine();
                    int count = 0;
                    for (int i = 0; i < str.length(); i++) {
        
                        char ch = str.charAt(i);
                        if(ch == ' '){
        
                            count = 0;
                    }else{
        
                            count++;
                        }
                }
                    System.out.println(count);
            }
        }

> **用charAt来获取str的每一个字符，进行判断，并用count进行计数，如果遇到空格，count就会变成0，如果不是空格，count就会自增，直至循环结束并输出。**

**方法二：**

> 使用库函数lastIndexOf(int ch) 从后往前找返回ch第一次出现的位置

**程序实现的思想**：和上一题一样，也是找空格的位置，然后使用字符串的整体长度减去空格的位置，再减一得到的就是最后一个单词的长度。

> **再减一是因为lastIndexOf在查找时默认第一个数是从0开始的，会比真实的位置小1。**  
> 具体代码如下：

public static void main(String[] args) {
        
               Scanner in = new Scanner(System.in);
               while(in.hasNextLine()){
        
                   String str = in.nextLine();
                   int count = str.lastIndexOf(' ');
                   System.out.println(str.length()-count-1);
               }
           }

## 验证回文串 ##

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

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

> 提示：  
> 1 <= s.length <= 2 \* 105  
> 字符串 s 由 ASCII 字符组成

这一题还是比较有难度的，先看代码后面会具体进行讲解。  
具体代码如下：

public boolean LegitChar(char ch){
        
                if(ch >='a'&&ch <= 'z'|| ch>='0'&&ch<='9'){
        
                    return true;
                }else{
        
                    return false;
                }
            }
            public  boolean isPalindrome(String s){
        
                s = s.toLowerCase();//将字母转为小写
                int left = 0;
                int right = s.length()-1;
                while(left<right){
        
                	//从左边找有效字符
                    while(left<right && !LegitChar(s.charAt(left))){
        
                        left++;
                    }
                    //从右边找有效字符
                    while(left<right && !LegitChar(s.charAt(right))){
        
                        right--;
                    }
                    if(s.charAt(left)!=s.charAt(right)){
        
                        return false;
                    }else{
        
                        left++;
                        right--;
                    }
                }
                return true;
            }

> **注意**：  
> 题目中说了：**只考虑字母和数字字符，可以忽略字母的大小写。**  
> 为了解决这个问题，我们可以先用**toLowerCase**将字符串的**字母全部进行小写**，并用**LegitChar**这个方法**判断每个字符是否合法**。  
> **用left和right依次从两端进行比较**，如果不和法就向前或向右移一个字符，在判断直到找到有效的字符。**注意在移动的过程中left可能会比right大**，所以也要对left和right进行判断。  
> 找到有效字符时再进行比较，如果相等循环继续，直到left大于right，返回true。如果不相等，就直接返回flase。

题目的做法有很多，有好的方法也有坏的方法，我写的这些都不一定是最优解。大家学习一下做题技巧或方法就可以了，毕竟题是会变的，就到这里吧.  
![在这里插入图片描述][887eb7270b4d495e838aec17f53e2fae.gif_pic_center]

[Link 1]: https://leetcode.cn/problems/first-unique-character-in-a-string/
[Link 2]: https://www.nowcoder.com/practice/8c949ea5f36f422594b306a2300315da?tpId=37&&tqId=21224&rp=5&ru=/activity/oj&qru=/ta/huawei/question-ranking
[Link 3]: https://leetcode.cn/problems/valid-palindrome/
[887eb7270b4d495e838aec17f53e2fae.gif_pic_center]: https://img-blog.csdnimg.cn/887eb7270b4d495e838aec17f53e2fae.gif#pic_center