第 12 关 | 刷题模板之字符串:2.白银挑战——字符串经典基础面试题

本章介绍了大量的字符串基础算法题，这些题目本身难度并不大，请扎实学习

1. 反转的问题

我们知道反转是链表的一个重要考点，反转同样是字符串的重要问题。常见问题也就是在LeetCode中列举的相关题目：
【1】LeetCode344. 反转字符串：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。【2】LeetCode541. K个一组反转：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
【3】LeetCode.917. 仅仅反转字母：·给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
【4】LeetCode151. 反转字符串里的单词：给你一个字符串 s ，逐个反转字符串中的所有 单词 。【5】LeetCode.557. 反转字符串中的单词 III：给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
这几个题目你是否发现前三道就是要么反转字符，要么反转里面的单词。针对字符的反转又可以变换条件造出多问题。我们就从基本问题出发，各个击破。

1.1. 反转字符串

LeetCode344. 题目要求：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

这是最基本的反转题，也是最简单的问题，使用双指针方法最直接。具体做法是:
对于长度为 N 的待被反转的字符数组，我们可以观察反转前后下标的变化，假设反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] ... s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律，因此我们可以得出如下双指针的解法：

• 将 left 指向字符数组首元素，right 指向字符数组尾元素。
• 当 left < right：

• • 交换 s[left] 和 s[right]；
  • left 指针右移一位，即 left = left + 1；
  • right 指针左移一位，即 right = right - 1

• 当 left >= right，反转结束，返回字符数组即可

class Solution {

    public void reverseString(char[] s) {

        if(s == null || s.length == 0){

            return ;

        }

        int n = s.length;

        for(int i = 0,j = n -1; i