代码随想录刷题-字符串
2022/1/24 6:07:19
本文主要是介绍代码随想录刷题-字符串,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
本文是每天跟着代码随想录刷题时做的笔记,用来总结与复习。
目录
344.反转字符串
541.反转字符串Ⅱ
剑指offer 05.替换空格
151.反转字符串里的单词
剑指offer 58-Ⅱ.左旋转字符串
28.实现strStr()
459.重复的子字符串
今日总结
344.反转字符串
题目链接:344. 反转字符串 - 力扣(LeetCode) (leetcode-cn.com)
思路:思路很简单,就是一个双指针加元素交换
public void reverseString(char[] s) { int left = 0; int right = s.length - 1; while (left < right){ char temp = s[left]; s[left++] = s[right]; s[right--] = temp; } }
541.反转字符串Ⅱ
题目链接:541. 反转字符串 II - 力扣(LeetCode) (leetcode-cn.com)
思路:在字符串长度范围内反转 0 + (2 * k) * i ~ (k - 1) + (2 * k) * i 下标的字符串,i 取值为 0,1,2,3.....,其中注意判断超出字符串长度的情况即可。
public String reverseStr(String s, int k) { char[] chars = s.toCharArray(); int left = 0; int right = left + k - 1; if (right >= chars.length){ right = chars.length - 1; } while (right < chars.length){ int fLeft = left; int fRight = right; while (fLeft < fRight){ char temp = chars[fLeft]; chars[fLeft++] = chars[fRight]; chars[fRight--] = temp; } left += 2 * k; right += 2 * k; if (left >= chars.length){ break; } if (right >= chars.length){ right = chars.length - 1; } } return new String(chars); }
剑指offer 05.替换空格
题目链接:剑指 Offer 05. 替换空格 - 力扣(LeetCode) (leetcode-cn.com)
思路:
①:直接使用 String 中的 replace 方法
public String replaceSpace(String s) { String s1 = s.replace(" ", "%20"); return s1; }
②:不使用库函数的解法,使用 StringBuilder 来进行字符串的拼接,提高速度
public String replaceSpace(String s) { StringBuilder str = new StringBuilder(); for(int i = 0 ; i < s.length(); i++){ char ch = s.charAt(i); if(ch == ' '){ str.append("%20"); } else{ str.append(ch); } } return str.toString(); }
③:正规解法:先将字符串长度扩充到替换后的长度,这里要使用 StringBuilder 来进行扩充,因为 String 是不可变长的。设置两个指针,一个指向扩充前字符串末尾 (bf) ,一个指向扩充后的字符串末尾 (af) ,使用 bf 由前往后遍历字符串,若查找到空格,则使用 af 存入 "%20",若没有查找到空格,则使用 af 存入 bf 对应字符
public String replaceSpace(String s){ int count = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' '){ count++; } } StringBuilder stringBuilder = new StringBuilder(s); for (int i = 0; i < count; i++) { stringBuilder.append(" "); } String str = stringBuilder.toString(); char[] chars = str.toCharArray(); int bf = s.length() - 1; int af = stringBuilder.length() - 1; while (bf >= 0){ if (chars[bf] == ' '){ chars[af--] = '0'; chars[af--] = '2'; chars[af--] = '%'; bf--; }else { chars[af--] = chars[bf--]; } } return new String(chars); }
151.反转字符串里的单词
题目链接:151. 翻转字符串里的单词 - 力扣(LeetCode) (leetcode-cn.com)
思路:
①:使用 String 中的 split 函数来获取每一个单词,在将单词进行拼接
public String reverseWords(String s) { String[] s1 = s.split(" "); StringBuilder str = new StringBuilder(); int flag = 0; while (s1[flag].equals("")){ flag++; } for (int i = s1.length - 1; i > flag; i--) { if (!s1[i].equals("")){ str.append(s1[i]); str.append(" "); } } str.append(s1[flag]); return str.toString(); }
②:不使用库函数:先去除字符串头尾的空格,再将字符串反序并处理中间空格,如下
原字符串:
处理完后的字符串:
最后再通过空格作为标志获取每个单词,将每个单词反转即可
public String reverseWords(String s) { char[] chars = s.toCharArray(); int left = 0; int right = chars.length - 1; StringBuilder newStr = new StringBuilder(); //去除头尾的空格 while (left <= right){ if (chars[left] == ' '){ left++; } if (chars[right] == ' '){ right--; } if (chars[left] != ' ' && chars[right] != ' '){ break; } } //将字符串反序,并处理中间空格 int bfRight = right - 1; while (right > left){ if (chars[right] != ' ' || (chars[right] == ' ' && chars[bfRight] != ' ')){ newStr.append(chars[right]); } right--; bfRight--; } newStr.append(chars[left]); getAndReverse(newStr); return newStr.toString(); } //得到每个单词并将其反转 public void getAndReverse(StringBuilder stringBuilder){ int head = 0; int end = 0; while (end < stringBuilder.length()){ if (stringBuilder.charAt(end) == ' '){ reverse(stringBuilder, head, end - 1); head = end + 1; } end++; } reverse(stringBuilder, head, end - 1); } //反转每个单词 public void reverse(StringBuilder stringBuilder, int head, int end){ while (head < end){ char temp = stringBuilder.charAt(head); stringBuilder.setCharAt(head, stringBuilder.charAt(end)); stringBuilder.setCharAt(end, temp); head++; end--; } }
剑指offer 58-Ⅱ.左旋转字符串
题目链接:剑指 Offer 58 - II. 左旋转字符串 - 力扣(LeetCode) (leetcode-cn.com)
思路:
①:截取对应子串进行拼接
public String reverseLeftWords(String s, int n){ StringBuilder ansStr = new StringBuilder(); ansStr.append(s.substring(n, s.length())); ansStr.append(s.substring(0, n)); return ansStr.toString(); }
②:先反转整个字符串,再反转对应的对应子串
public String reverseLeftWords(String s, int n){ StringBuilder ansStr = new StringBuilder(s); int length = ansStr.length(); reverse(ansStr, 0, length - 1); reverse(ansStr, 0, length - n - 1); reverse(ansStr, length - n, length - 1); return ansStr.toString(); } public void reverse(StringBuilder stringBuilder, int head, int end){ while (head < end){ char temp = stringBuilder.charAt(head); stringBuilder.setCharAt(head, stringBuilder.charAt(end)); stringBuilder.setCharAt(end, temp); head++; end--; } }
28.实现strStr()
题目链接:28. 实现 strStr() - 力扣(LeetCode) (leetcode-cn.com)
思路:
①:Horspool算法:设置一个移动表,设置规则如下图所示,根据匹配不成功时 haystack 字符串与 needle 字符串末尾对应的字符 c 的不同情况来对照移动表进行移动。
public int strStr(String haystack, String needle) { if (needle.length() == 0){ return 0; } Map<Character, Integer> move = new HashMap<>(); int flag = needle.length() - 1; int count = 0; if (needle.length() > 1){ while (flag > 0){ flag--; count++; if (!move.containsKey(needle.charAt(flag))){ move.put(needle.charAt(flag), count); } } } int hayPo = needle.length() - 1; while (hayPo < haystack.length()){ int nePo = needle.length() - 1; int moveHayPo = hayPo; while (needle.charAt(nePo) == haystack.charAt(moveHayPo)){ nePo--; moveHayPo--; if (nePo < 0){ return moveHayPo + 1; } } if (move.containsKey(haystack.charAt(hayPo))){ hayPo += move.get(haystack.charAt(hayPo)); }else { hayPo += needle.length(); } } return -1; }
②:KMP 算法:直接学习卡哥的视频:
帮你把KMP算法学个通透!(理论篇)哔哩哔哩bilibili
帮你把KMP算法学个通透!(求next数组代码篇)哔哩哔哩bilibili
public int strStr(String haystack, String needle) { if (needle.length() == 0){ return 0; } int[] next = new int[needle.length()]; next[0] = 0; int j = 0; for (int i = 1; i < needle.length(); i++){ while (j > 0 && needle.charAt(j) != needle.charAt(i)){ j = next[j - 1]; } if (needle.charAt(j) == needle.charAt(i)){ j++; } next[i] = j; } int needPo = 0; for (int i = 0; i < haystack.length(); i++) { while (needPo > 0 && needle.charAt(needPo) != haystack.charAt(i)) needPo = next[needPo - 1]; if (needle.charAt(needPo) == haystack.charAt(i)) needPo++; if (needPo == needle.length()) return i - needle.length() + 1; } return -1; }
459.重复的子字符串
题目链接:459. 重复的子字符串 - 力扣(LeetCode) (leetcode-cn.com)
思路:同样使用 kmp 算法,通过分析 next 数组可以发现,如果用字符串的长度减去最长公共前后缀可以整除字符串的长度,那么则表示该字符串符合题意(当然是看的题解啦
这篇关于代码随想录刷题-字符串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23JAVA语音识别项目入门教程
- 2024-11-23Java云原生学习:从入门到实践
- 2024-11-22Java创业学习:初学者的全面指南
- 2024-11-22JAVA创业学习:零基础入门到实战应用教程
- 2024-11-22Java创业学习:从零开始的Java编程入门教程
- 2024-11-22Java对接阿里云智能语音服务学习教程
- 2024-11-22JAVA对接阿里云智能语音服务学习教程
- 2024-11-22Java对接阿里云智能语音服务学习教程
- 2024-11-22Java副业学习:零基础入门到实战项目
- 2024-11-22Java副业学习:零基础入门指南