牛客網——Java刷題篇

作者：敲代碼の流川楓

部落格首頁：​​流川楓的部落格​​

專欄：​​和我一起學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.重新周遊字元數組

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