【字符串专场】只会使用库函数？面试官气的让我出门左转（下）

2022-05-21 147

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【字符串专场】只会使用库函数？面试官气的让我出门左转

方法2：String的substring(效率高需掌握，常用API)

时间复杂度O(n):n为s的长度

空间复杂度O(n):n为s的长度

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

🍈6.最后一个单词的长度

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

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

题目链接：最后一个单词的长度力扣最后一个单词的长度https://leetcode-cn.com/problems/length-of-last-word/

分析：这道题可以看作为第四道题的子题，我们可以考虑同样的做法，反向遍历用指针去找到最后一个字母的起始索引和结尾索引，从而求得长度。

方法：反向遍历

时间复杂度O(n)：n为字符串的长度，最多反向遍历整个字符串一遍

空间复杂度O(1)：

class Solution {
    public int lengthOfLastWord(String s) {
      //从末尾开始遍历
      int index=s.length()-1;
      //结尾有空格有往左移动
      while(s.charAt(index)==' '){
          index--;
      }
      //此时index指向最后一个单词的最后一个字母,用a记录此时的位置
      int a=index;
      //index继续移动,保证index>0
      //这里要注意index指向的是最后一个单词前面的空格
      while(index>=0&&s.charAt(index)!=' '){
          index--;
      }
      //相减获得长度
      return a-index;
    }
}

🌽7.字符串中的第一个唯一字符

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

题目链接：字符串中的第一个唯一字符力扣字符串中的第一个唯一字符https://leetcode-cn.com/problems/first-unique-character-in-a-string/

题目分析：看到这个题目首先应该想到String的indexOf和lastindexOf两个API方法，其次应该想到暴力遍历的方法。效率高的方法，应该想到利用哈希，这里我们不采用map而采用数组来映射，因为数组也是哈希映射的一种体现。什么？你说你还不太会哈希或者不懂数组体现哈希？那你快看看这套哈希专题——【哈希系列】舍友担心期末考睡不着，我连夜准备了这套哈希全套专题

方法1：利用String的indexOf和lastIndexOf

时间复杂度O(n^2)：涉及到API的源码，内部也是循环实现，这个方法复杂度较高

空间复杂度O(1)

class Solution {
    public int firstUniqChar(String s) {
        for(int i=0;i<s.length();i++){
            //indexOf获得某个元素从头遍历第一次出现的位置
            //lastIndexOf获得某个元素从尾到头遍历第一次出现的位置
            //如果相等说明这个字母就一个
            if(s.indexOf(s.charAt(i))==s.lastIndexOf(s.charAt(i))){
                return i;
            }
        }
        //没找到返回-1
        return -1;
    }
}

方法2：利用数组哈希映射

时间复杂度O(n)：进行两次遍历，这里也可用哈希表来做，只不过使用数组的效率更好，推荐大家两种都要尝试。

空间复杂度O(1)：常数长度的数组消耗，看为O(1)的复杂度消耗

class Solution {
    public int firstUniqChar(String s) {
        //统计26个字母出现的频率
        int[] arr=new int[26];
        //遍历一次数组统计出现的每个字母出现的次数
        for(int i=0;i<s.length();i++){
            arr[s.charAt(i)-'a']++;
        }
        //再遍历一次,找到出现次数为1的字母
        for(int i=0;i<s.length();i++){
            if(arr[s.charAt(i)-'a']==1){
                return i;
            }
        }
        return -1;
    }
}

🍋3.基础字符串处理总结（题目总链接）

其实我们发现几乎关于字符串的每道题，都或多或少可以利用API直接或者间接求的答案，由此可见了解字符串相关API的重要性。但我们在会使用的过程中，也应该掌握其原理，如果没有这个API你也能自己用实现这个功能，这才是我们的基本功能力。在进阶的难题中，字符串的处理只是一部分，它还会搭配其他的算法，为了简化代码这时我们就应该使用API来处理。所以大家在打好基础的同时，也一定要会使用相关的API。

1.反转字符串 https://leetcode-cn.com/problems/reverse-string/

2.反转字符串ll https://leetcode-cn.com/problems/reverse-string-ii/

3.替换空格 https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

4.反转字符串里的单词 https://leetcode-cn.com/problems/reverse-words-in-a-string/

5.左选择字符串 https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

6.最后一个单词的长度 https://leetcode-cn.com/problems/length-of-last-word/

7.字符串里第一个唯一字符 https://leetcode-cn.com/problems/first-unique-character-in-a-string/