帮别人做彩票网站,餐饮网站建设需求分析,电子信息工程移动互联网方向,哪个网站做图书广告好文章目录 前言1. 反转问题1.1 反转字符串1.2 k个一组反转1.3 仅仅反转字母1.3.1 采用栈实现操作1.3.2 采用双指针实现操作 1.4 反转字符串里面的单词1.4.1 使用语言提供的方法来解决(内置API)1.4.2 如何优雅自己实现上述功能 2. 验证回文串3. 字符串中的第一个唯一字符4. 判断是… 文章目录 前言1. 反转问题1.1 反转字符串1.2 k个一组反转1.3 仅仅反转字母1.3.1 采用栈实现操作1.3.2 采用双指针实现操作 1.4 反转字符串里面的单词1.4.1 使用语言提供的方法来解决(内置API)1.4.2 如何优雅自己实现上述功能 2. 验证回文串3. 字符串中的第一个唯一字符4. 判断是否互为字符重排4.1 排序重组4.2 采用Hash实现操作 总结 前言 提示越是在意的人越是绝口不提。我选择你做内心深处的秘密。来日有人剖开这颗心来里面除了你什么都没有。 --陶立夏《生活的比喻》 本章挑战的难度不大是大量字符串题目的基础。务必学扎实。 1. 反转问题
我们知道反转是链表的一个重要考点反转同样也是字符串的一个重要问题。常见的也就是如下这些
推荐题目⭐⭐⭐⭐⭐
344. 反转字符串 - 力扣LeetCode
541. 反转字符串 II - 力扣LeetCode
917. 仅仅反转字母 - 力扣LeetCode
151. 反转字符串中的单词 - 力扣LeetCode
557. 反转字符串中的单词 III - 力扣LeetCode
这些题目你是否看出一些规律在其中要么反转字符串要么反转里面的单词。针对字符的反转可以变换造出很多题目来。这里我们据从基本出发逐个击破。
1.1 反转字符串
参考题目介绍344. 反转字符串 - 力扣LeetCode 这是最基本的反转题也是最简单的问题。这里使用双指针最直接。具体的做法是
对于一个长度为N的待反转的字符串数组我们观察反转前后的下标的变化就可以知道结果
s[0] s[N - 1]
s[1] s[N - 2]
s[2] s[N - 3]
s[3] s[N - 4]
s[4] s[N - 5]
... ...s[n - 1] s[0]比较完之后我们可以发现规律即s[i] 与 s[N - 1 -i] 发生了交换。所以双指针我们就可以这样写
将left指向字符串数组的首元素right指向字符串数组的尾元素当left right: 交换s[left] 和 s[right]left 指针右移一位即left left 1right指针左移一位即right tight -1 当left right ,反转结束返回字符数组即可 /*** 反转字符串双指针* param s the string */public static void reverseString(char[] s) {int n s.length;for(int left 0,right n - 1; left right; left,right--){char c s[left];s[left] s[right];s[right] c;}}1.2 k个一组反转
参考题目介绍:541. 反转字符串 II - 力扣LeetCode 怎么感觉这题在找事呢确实是闲了。这里我们根据题意直接模拟结果
反转每个下标从2k的倍数开始长度为k的字串。如果字串长度不足k则反转整个字串。
/*** 反转k个字符串* param s* param k* return*/public static String reverseStr(String s, int k) {if(s null || s.length0){return new String();}int n s.length();char[] chars s.toCharArray();for(int i 0; i n; i 2*k){reverse(chars,i,Math.min(k i,n) -1);}return new String(chars);}public static void reverse(char[] arr, int left, int right) {while(left right){char c arr[left];arr[left] arr[right];arr[right] c;left;right--;}}1.3 仅仅反转字母
参考题目介绍917. 仅仅反转字母 - 力扣LeetCode 这里第一眼的感觉是不是很复杂但同样从两头向中间就可以了但是问题‘-’不是均匀的有些麻烦处理起来不容易就增加了难度。其实换一种思路就不同了栈这个工具对于反转来说非常好用。
1.3.1 采用栈实现操作
具体方法
将s中的所有字母单独存放在栈中所以出栈来说就是反序操作了当然也可以用数组存并反序的
然后遍历s的所有字符如果是字母就输出。 /*** 仅仅反转字母* param s the string to reverse* return*/public static String reverseOnlyLetters(String s) {// 校验参数if (s null || s.length() 0) {return s;}// 创建一个栈作存储单词StackCharacter letters new StackCharacter();for (Character c : s.toCharArray()){if (Character.isLetter(c)){letters.push(c);}}StringBuilder res new StringBuilder();for (Character c : s.toCharArray()){if (Character.isLetter(c)){res.append(letters.pop());}else{res.append(c);}}return res.toString();}1.3.2 采用双指针实现操作
一个接一个输出s的所有字符当遇到一个字母时我们希望找到逆序遍历字符串的下一个字母。
所以我们这么做维护一个指针j从后向前遍历字符串当需要字母的时候就使用它。 /*** 进反转字母双指针实现* param s the string to reverse* return*/public static String reverseOnlyLetters2(String s) {// 校验参数if (s null || s.length() 0) {return s;}StringBuilder res new StringBuilder();int j s.length() - 1;for(int i 0; i s.length(); i) {if (Character.isLetter(s.charAt(i))){// 可能不止一个while(!Character.isLetter(s.charAt(j))){j--;}res.append(s.charAt(j--));}else{res.append(s.charAt(i));}}return res.toString();}1.4 反转字符串里面的单词
参考题目介绍151. 反转字符串中的单词 - 力扣LeetCode 这个题目经常在很多面试题中见到这样的题目重点在如何处理单词其实难度并不大我们重点看下分析
1.4.1 使用语言提供的方法来解决(内置API)
比如JavaPythonC等很多语言提供了相关的特性因此我们可以首先使用语言的特性来解决
很多语言对字符串都有特殊的处理提供了split拆分reverse(反转) 和 join连续等方法。一次采用内置的API是可行的。
使用split将字符串按照空格分割成字符串数组使用reverse将字符串数组进行反转使用join方法将字符串重新拼接成一个字符串。
如图 public String reverseWords(String s) {if(s null || s.length() 0){return s;}// 去除开头和结尾的空白字符这个很重要s s.trim();// 正则匹配连续的字符空白字符作为分隔符// 正则表达式中\s匹配任何空白字符包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]ListString wordList Arrays.asList(s.split(\\s));Collections.reverse(wordList);return String.join( ,wordList);
}上面的方法在面试中式禁止使用的别想了怎么会这么优雅呢还是乖乖自己实现吧。
1.4.2 如何优雅自己实现上述功能
对于字符串可变的语言就不需要在额外开辟空间了直接在字符串上原地实现这种情况下反转字符和去除空格可以一起完成。 /*** 反转字符串中的单词* param s* return*/public static String reverseWords(String s) {// 校验参数if(s null || s.length() 0) {return s;}// 出去多余空白字符StringBuilder sb trimSpaces(s);// 反转字符串reverse(sb,0,sb.length() - 1);// 反转每个单词reverseWord(sb);return sb.toString();}private static void reverseWord(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;}}/*** 反转字符出可变* param sb* param left* param right*/private static void reverse(StringBuilder sb, int left, int right) {while (left right){char temp sb.charAt(left);sb.setCharAt(left,sb.charAt(right));sb.setCharAt(right--,temp);}}private static 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;}
2. 验证回文串
参考题目地址125. 验证回文串 - 力扣LeetCode 回文问题再链表中也是常见的再字符串中同样也是重点。这里记录一下骨头哥☠️的经历技术面式
第一就式写一个判断字符串回文的问题题目本身很简单双指针的典型问题。下面就会被加餐找最长的回文串这里就需要动态规划的思想了这里我们后面再说
说是话刷了这么多题目这个问题真的式手到擒来。有很多思路。最简单的方法就是对字符串进行一次遍历并保留其中的字母和数字放入另一个字符串sgood中。这样我们只需要判断sgood是不是一个普通的回文串了。
如果不是用语言的特性这里我们可以使用双指针的思想来处理。
初始左右指针分别指向sgood的两侧不断向中间移动判断是否相同如果相遇就说明是回文串 /*** 判断是否为回文字符串* param s* return*/public static boolean isPalindrome(String s) {if (s null || s.length() 0) {return true;}StringBuilder sgood new StringBuilder();int len s.length();for(int i 0; i len; i) {char c s.charAt(i);if (Character.isLetterOrDigit(c)) {sgood.append(Character.isLowerCase(c));}}int n sgood.length();int left 0,right n - 1;while(left right) {if (Character.toLowerCase(sgood.charAt(left)) ! Character.toLowerCase(sgood.charAt(right))) {return false;}left;--right;}return true;}3. 字符串中的第一个唯一字符
参考题目地址387. 字符串中的第一个唯一字符 - 力扣LeetCode 对于这个问题最直观的方法就是遍历两次就可以知道结果采用hash统计字符串中每个字符出现的次数。在第二次遍历时就可以遍历到只出现1次的字符直接返回他的索引即可没有的话返回-1。 /*** 找只出现一次的字符* param s* return*/public static int firstUniqChar(String s) {// 参数校验if(s null || s.length() 0){return 0;}MapCharacter,Integer frequency new HashMapCharacter,Integer();for(int i 0; i s.length(); i){char c s.charAt(i);frequency.put(c,frequency.getOrDefault(c,0) 1);}for(int i 0; i s.length(); i){if (frequency.get(s.charAt(i)) 1){return i;}}return -1;}4. 判断是否互为字符重排
参考题目介绍242. 有效的字母异位词 - 力扣LeetCode 这是一道简单题就不要想的特别复杂啦。当然这也是一道非常经典的题目
这个题目来说如果你觉得时排列组合的问题还解决了说明你排列组合学的很好。但是这里有更好的解法。
4.1 排序重组
将两个字符串全部从小到大或者从大到小排序然后再逐个比较不管原始字符串是什么都可以判断出来代码也不复杂。 /*** 判断字符串是否重排* param s1* param s2* return*/public static boolean checkPermutation1(String s1, String s2) {// 将字符串转成数组char[] chars1 s1.toCharArray();char[] chars2 s2.toCharArray();// 排序Arrays.sort(chars1);Arrays.sort(chars2);// 比较return new String(chars1).equals(new String(chars2));}这里需要注意我们使用了内置api面试是不允许的。
4.2 采用Hash实现操作
注意这里我们不能简单的判断是否已经存在因为字符串可能在某个串里面重复存在例如“abac”。所以我们可以记录出现的次数如果一个字符串经过重新排列后能变成另外一个字符串那么他们每个不同字符出现的次数是相同的。例如出现此处不同的那么便是两个字符串不能够经过重新排列得到。
所以写起来页不复杂但是长了些。 /*** 判断字符串是否重排* param s1* param s2* return*/public static boolean checkPermutation(String s1, String s2) {if(s1.length() ! s2.length()){return false;}char[] chars s1.toCharArray();MapCharacter, Integer s1Map getMap(s1);MapCharacter, Integer s2Map getMap(s2);for(Character c : chars){if(!s1Map.containsKey(c) || !s2Map.containsKey(c) || s1Map.get(c).intValue() ! s2Map.get(c).intValue() ){return false;}}return true;}/*** 统计指定字符串str中各字符的出现次数并以Map的形式返回* param str* return*/public static 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;} 总结
提示字符串常见问题双指针问题的回顾反转问题回文字符串重排序问题。 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
