做视频网站需要什么手续,手机制作视频软件app,菏泽炫佑网站建设,无法连接网站关卡名 字符串经典基础面试题 我会了✔️ 内容 1.理解字符串反转的处理方法 ✔️ 2.熟练掌握回文串的判断方法 ✔️ 3.掌握字符串中搜索第一个唯一字符的方法 ✔️ 4.掌握判断是否互为字符串重排的处理技巧 ✔️
1 反转的问题
我们知道反转是链表的一个重要考点#xf… 关卡名 字符串经典基础面试题 我会了✔️ 内容 1.理解字符串反转的处理方法 ✔️ 2.熟练掌握回文串的判断方法 ✔️ 3.掌握字符串中搜索第一个唯一字符的方法 ✔️ 4.掌握判断是否互为字符串重排的处理技巧 ✔️
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反转结束返回字符数组即可。
public void reverseString(char[] s) {if (s null || s.length() 0) {return ;}int n s.length;for (int left 0, right n - 1; left right; left, --right) {char tmp s[left];s[left] s[right];s[right] tmp;}
}
1.2 K个一组反转
LeetCode541 这个题我感觉有点没事找事先看一下要求 给定一个字符串 s 和一个整数 k从字符串开头算起每计数至 2k 个字符就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。 输入s abcdefg, k 2 输出bacdfeg 示例2 输入s abcd, k 2 输出bacd 我们直接按题意进行模拟就可以反转每个下标从 2k的倍数开始的长度为 k的子串。若该子串长度不足 k则反转整个子串。
public String reverseStr(String s, int k) {if (s null || s.length() 0) {return s;}int n s.length();char[] arr s.toCharArray();for (int i 0; i n; i 2 * k) {reverse(arr, i, Math.min(i k, n) - 1);}return new String(arr);}public void reverse(char[] arr, int left, int right) {while (left right) {char temp arr[left];arr[left] arr[right];arr[right] temp;left;right--;}}
1.3 仅仅反转字母
LeetCode.917 这个题有点难度我们来看一下 给定一个字符串 S返回 “反转后的” 字符串其中不是字母的字符都保留在原地而所有字母的位置发生反转。 示例1 输入ab-cd 输出dc-ba 示例2 输入a-bC-dEf-ghIj 输出j-Ih-gfE-dCba 示例3 输入Test1ng-Leetcode-Q! 输出Qedo1ct-eeLgntse-T! 这里第一眼感觉不是特别复杂同样从两头向中间即可但问题是-不是均匀的有些划分的段长有的短这就增加了处理的难度。
方法1使用栈
将 s 中的所有字母单独存入栈中所以出栈等价于对字母反序操作。或者可以用数组存储字母并反序数组。 然后遍历 s 的所有字符如果是字母我们就选择栈顶元素输出。
class Solution {public String reverseOnlyLetters(String S) {StackCharacter letters new Stack();for (char c: S.toCharArray())if (Character.isLetter(c))letters.push(c);StringBuilder ans new StringBuilder();for (char c: S.toCharArray()) {if (Character.isLetter(c))ans.append(letters.pop());elseans.append(c);}return ans.toString();}
} 方法2拓展 双转指针
一个接一个输出 s 的所有字符。当遇到一个字母时我们希望找到逆序遍历字符串的下一个字母。 所以我们这么做维护一个指针 j 从后往前遍历字符串当需要字母时就使用它。
class Solution {public String reverseOnlyLetters(String S) {if (S null || S.length() 0) {return S;}StringBuilder ans new StringBuilder();int j S.length() - 1;for(int i0;iS.length();i){if(Character.lsLetter(S.charAt(i)){while(!Character.isLetter(S.charAt(j))){j--;}ans.append(S.charAt(j--));} else {ans.append(S.charAt(i));}}return ans.toString();}
} 1.4 .反转字符串里的单词
LeetCode151 给你一个字符串 s 逐个反转字符串中的所有 单词 。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 请你返回一个反转 s 中单词顺序并用单个空格相连的字符串。 说明
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。反转后单词间应当仅用一个空格分隔。反转后的字符串中不应包含额外的空格。 示例1 输入s the sky is blue 输出blue is sky the 示例2 输入s hello world 输出world hello 解释输入字符串可以在前面或者后面包含多余的空格但是反转后的字符不能包括。 这个题也经常出现在很多面试题中我记得曾经见过有个题是这样出的要你按照同样的方式反转“ I love youzan”。这个题的关键在于如何处理单词。 本题难度并不大 所以我们的重点就是从多种角度来分析该问题
方法1使用语言提供的方法来解决
Java、Python、C等很多语言提供了相关的特性因此我们可以首先使用语言的特性来实现 很多语言对字符串提供了 split拆分reverse反转和 join连接等方法因此我们可以简单的调用内置的 API 完成操作
使用 split 将字符串按空格分割成字符串数组使用 reverse 将字符串数组进行反转使用 join 方法将字符串数组拼成一个字符串。
如图 public String reverseWords(String s) {if (s null || s.length() 0) {return s;}// 除去开头和末尾的空白字符记住这个操作s s.trim();// 正则匹配连续的空白字符作为分隔符分割ListString wordList Arrays.asList(s.split(\\s));Collections.reverse(wordList);return String.join( ,wordList);
}C里没有提供类似的函数来调用我们就不写了。 上面这种方式在面试的时候一般也不会让用所以我们还是看下面的方式
方法2自己实现上述功能
对于字符串可变的语言就不需要再额外开辟空间了直接在字符串上原地实现。在这种情况下反转字符和去除空格可以一起完成。 实现方法
class Solution {public String reverseWords(String s) {StringBuilder sb trimSpaces(s);// 翻转字符串reverse(sb, 0, sb.length() - 1);// 翻转每个单词reverseEachWord(sb);return sb.toString();}public StringBuilder trimSpaces(String s) {int left 0, right s.length() - 1;// 去掉字符串开头的空白字符while (left right s.charAt(left) ) {left;}// 去掉字符串末尾的空白字符while (left right s.charAt(right) ) {--right;}// 将字符串间多余的空白字符去除StringBuilder sb new StringBuilder();while (left right) {char c s.charAt(left);if (c ! ) {sb.append(c);} else if (sb.charAt(sb.length() - 1) ! ) {sb.append(c);}left;}return sb;}public void reverse(StringBuilder sb, int left, int right) {while (left right) {char tmp sb.charAt(left);sb.setCharAt(left, sb.charAt(right));sb.setCharAt(right--, tmp);}}public void reverseEachWord(StringBuilder sb) {int n sb.length();int start 0, end 0;while (start n) {// 循环至单词的末尾while (end n sb.charAt(end) ! ) {end;}// 翻转单词reverse(sb, start, end - 1);// 更新start去找下一个单词start end 1;end;}}
}
2 验证回文串
LeetCode.125. 给定一个字符串验证它是否是回文串只考虑字母和数字字符可以忽略字母的大小写。说明本题中我们将空字符串定义为有效的回文串。 回文问题在链表中是重点在字符串中同样是个重点。当初我去美团面试第一轮技术面的第一个算法题就是让写判断字符串回文的问题。这个本身还是比较简单的只要先转换成字符数组然后使用双指针方法从两头到中间比较就行了。也许是过于简单了吧面试时经常被加餐例如LeetCode里的两道题。 一个是普通的验证回文串第二个是找最长的子回文串。第二个问题需要动态规划等技术有点难度我们到高级算法里再看这里先看一下基本的。 示例1 输入: A man, a plan, a canal: Panama 输出: true 解释amanaplanacanalpanama 是回文串 示例2 输入: race a car 输出: false 解释raceacar 不是回文串 这个题我们可以有多种思路最简单的方法是对字符串 s 进行一次遍历并将其中的字母和数字字符进行保留放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。 如果不使用语言的特性我们可以使用双指针思想来处理。 初始时左右指针分别指向 sgood 的两侧随后我们不断地将这两个指针相向移动每次移动一步并判断这两个指针指向的字符是否相同。当这两个指针相遇时就说明 sgood 时回文串。
public boolean isPalindrome(String s) {if (s null || s.length() 0) {return s;}StringBuffer sgood new StringBuffer();int length s.length();for (int i 0; i length; i) {char ch s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}int n sgood.length();int left 0, right n - 1;while (left right) {if (sgood.charAt(left) ! sgood.charAt(right)) {return false;}left;--right;}return true;
}
3 字符串中的第一个唯一字符
LeetCode387. 给定一个字符串找到它的第一个不重复的字符并返回它的索引。如果不存在则返回 -1。 示例 s leetcode 返回 0 s loveleetcode 返回 2 提示你可以假定该字符串只包含小写字母。 我们可以对字符串进行两次遍历在第一次遍历时我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时我们只要遍历到了一个只出现一次的字符那么就返回它的索引否则在遍历结束后返回 -1。
public int firstUniqChar(String s) {if (s null || s.length() 0) {return 0;}MapCharacter,Integer map new HashMap();for(int i0;is.length();i){char ch s.charAt(i);map.put(ch,map.getOrDefault(ch,0)1);}for (int i 0; i s.length(); i) {if (map.get(s.charAt(i)) 1) {return i;}}return -1;
}
4 判定是否互为字符重排 这是一道典型的看似吓人 其实很简单的问题。 LeetCode242 给定两个字符串 s1 和 s2请编写一个程序确定其中一个字符串的字符重新排列后能否变成另一个字符串。 示例1 输入: s1 abcadfhg, s2 bcafdagh 输出: true 示例2 输入: s1 abc, s2 bad 输出: false 这个题第一眼看感觉是个排列组合的题目然后如果使用排列的算法来处理 难度会非常大而且效果还不一定好。用简单的方式就能解决。 第一种方法将两个字符串全部从小到大或者从大到小排列然后再逐个位置比较这时候不管两个原始字符串是什么都可以判断出来。 代码也不复杂
public boolean checkPermutation(String s1, String s2) {// 将字符串转换成字符数组char[] s1Chars s1.toCharArray();char[] s2Chars s2.toCharArray();// 对字符数组进行排序Arrays.sort(s1Chars);Arrays.sort(s2Chars);// 再将字符数组转换成字符串比较是否相等return new String(s1Chars).equals(new String(s2Chars));
}
注意这里我们使用了不同语言的排序函数你是否记得我们在数组一章提到过这个方法必须牢记。 第二种方法使用Hash注意这里我们不能简单的存是否已经存在因为字符可能在某个串里重复存在例如abac。我们可以记录出现的次数如果一个字符串经过重新排列后能够变成另外一个字符串那么它们的每个不同字符的出现次数是相同的。如果出现次数不同那么表示两个字符串不能够经过重新排列得到。 这个代码逻辑不复杂但是写起来稍微长一点
public boolean checkPermutation(String s1, String s2) {if (s1.length() ! s2.length()) {return false;}char[] s1Chars s1.toCharArray();MapCharacter, Integer s1Map getMap(s1);MapCharacter, Integer s2Map getMap(s2);for (char s1Char : s1Chars) {if (!s2Map.containsKey(s1Char) || (int)s2Map.get(s1Char) ! (int)s1Map.get(s1Char)) {return false;}}return true;}// 统计指定字符串str中各字符的出现次数并以Map的形式返回private MapCharacter, Integer getMap(String str) {MapCharacter, Integer map new HashMap();char[] chars str.toCharArray();for (char aChar : chars) {map.put(aChar, map.getOrDefault(aChar, 0) 1);}return map;}
