LeetCode面试热题150中19-22题学习笔记（用Java语言描述）

Day 04

19、最后一个单词的长度

需求：给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

代码表示

public class Q19_1 {public static int lengthOfLastWord(String s) {/*从字符串末尾开始去除空格*   从末尾开始，只要当前字符串是空格*   就end-1，直到遇到非空格字符串   */int end = s.length() - 1;   //记录最后一个字符的索引while (end >= 0 && s.charAt(end) == ' ') {end--;}/*计算最后一个单词的长度*   start初始化为end，也就是最后一个非空格字符的索引*   利用while循环，从end开始向前遍历*   只要当前字符不是空格，就把start-1*   直到遇到空格或者到达字符串的开头    */int start = end;    //start开始也指向最后一个单词的最后一个字符的索引while (start >= 0 && s.charAt(start) != ' ') {start--;}/*返回最后一个单词的长度*   start指向最后一个单词的前一个位置*   end指向最后一个单词的最后一个字符*   差值即为最后一个单词的长度*/return end - start;}
}

代码讲解

第7行：

• s 是一个 String 类型的对象，代表一个字符串。

• charAt(int index) 是 String 类的一个实例方法，它的作用是返回字符串中指定索引位置的字符。该方法的参数 index 是一个整数，表示要获取的字符在字符串中的位置。需要注意的是，Java 中字符串的索引是从 0 开始的，也就是说，第一个字符的索引是 0，第二个字符的索引是 1，依此类推。

  例：

  public class CharAtExample {public static void main(String[] args) {String s = "Hello";char firstChar = s.charAt(0);char secondChar = s.charAt(1);System.out.println("第一个字符: " + firstChar);System.out.println("第二个字符: " + secondChar);}
  }
  

  上述代码运行后，输出结果为：

  第一个字符: H
  第二个字符: e
  

  ---

20、最长公共前缀

需求：编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。

代码表示

public class Q20_1 {public static String longesCommonPrefixes(String[] strs) {/*边界条件检查*   如果输入的字符串是空或者长度为0*   直接返回    */if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];    //初始化公共前缀for (int i = 0; i < strs.length; i++) { //从数组的第二个字符串（索引为 1）开始遍历，直至遍历完整个数组。while (!strs[i].startsWith(prefix)) {//检查字符串 strs[i] 是否以当前的公共前缀 prefix 开头。若不是，则进入循环。if (prefix.length() == 0) { //若 prefix 的长度为 0，意味着不存在公共前缀，直接返回空字符串。return " ";}prefix = prefix.substring(prefix.length() - 1); //去掉 prefix 的最后一个字符，然后继续检查新的 prefix 是否为 strs[i] 的前缀，不断重复这个过程，直到 prefix 成为 strs[i] 的前缀。}}return prefix;  //返回公共前缀}
}

代码讲解

第13行：

• strs [i] : strs 是一个字符串数组，用于存储多个字符串。i 是索引。

• startsWith (String prefix) 方法：

  这是 Java 中 String 类的一个实例方法，用于检查当前字符串是否以指定的前缀开头。

  该方法接收一个字符串参数 prefix ，若当前字符串以 prefix 开头，返回 true，否则返回 false。

复杂度分析

时间复杂度为$O(S)$,S为字符串中元素的个数，最坏情况下需要遍历整个字符串。

---

21、反转字符串中的单词

需求：给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

思路

先去除字符串首尾空格，再按空格分割字符串得到单词数组，接着反转数组中单词的顺序，最后重新组合成字符串。

代码表示

public class Q21_1 {public static String reverseWords(String s) {/*去除首位空格并分割字符串*   trim() 是 String 类的方法，用于去除字符串 s 首尾的空格。* 例如，若 s 为 " hello world! "，调用 trim() 后得到 "hello world!"。*   split() 是 String 类的方法，用于根据指定的正则表达式分割字符串。*   \\s+ 是一个正则表达式，\\s 表示匹配任何空白字符（包括空格、制表符、换页符等）*   + 表示匹配前面的元素（即空白字符）一次或多次。*   所以 split("\\s+") 会将字符串按一个或多个空格分割成多个子字符串，并存入一个字符串数组 words 中。*   例如，对于 "hello world!"，分割后得到 ["hello","world!"] */String[] words = s.trim().split("\\s+");StringBuilder reversed = new StringBuilder();   //创建对象/*反转单词顺序并拼接字符串*   从数组的最后一个元素开始向前遍历单词数组    */for (int i = words.length - 1; i >= 0; i--) {reversed.append(words[i]);  //将当前单词添加到StringBuilder对象reversed中。if (i > 0) {  //如当前单词不是数组中的第一个单词，则在该单词后加一个空格。reversed.append(" ");}}/*toString() 是 StringBuilder 类的方法，用于将 StringBuilder 对象中的字符序列转换为字符串。*/return reversed.toString();}
}

---

22、找出字符串中第一个匹配项的下标

需求：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

代码展示

public class Q22_1 {public static int strStr(String haystack, String needle) {int hayLength = haystack.length();  //获取两个字符串的长度int needleLength = needle.length();if (needleLength == 0) {  //两个异常情况return 0;}if (hayLength < needleLength) {return -1;}/*外层for循环*   i是haystack中可能的起始下标，循环范围从0-hayLength - needleLength*/for (int i = 0; i < hayLength - needleLength; i++) {int j;//用于遍历needle字符串for (j = 0; j < needleLength; j++) {if (haystack.charAt(i + j) != needle.charAt(j)) {   //比较 haystack 从 i 开始的第 j 个字符和 needle 的第 j 个字符是否相等break;}}if (j == needleLength) {    //匹配成功return i;}}return -1;}
}