当前位置:网站首页>Brush questions record----string
Brush questions record----string
2022-07-30 19:40:00 【HandsomeDog_L】
目录
next数组----Storage pattern string equals the longest suffix before
刷题记录----字符串
反转字符串
class Solution { public void reverseString(char[] s) { int l = 0; int r = s.length - 1; while (l < r) { s[l] ^= s[r]; //构造 a ^ b 的结果,并放在 a 中 s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b ,存入b中,此时 b = a, a = a ^ b s[l] ^= s[r]; //a ^ b 的结果再 ^ a ,存入 a 中,此时 b = a, a = b 完成交换 l++; r--; } } }
反转字符串||
给定一个字符串 s 和一个整数 k,你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转.
如果剩余字符少于 k 个,则将剩余字符全部反转.
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样.
class Solution { public String reverseStr(String s, int k) { char[] ch = s.toCharArray(); // 1. 每隔 2k 个字符的前 k 个字符进行反转 for (int i = 0; i< ch.length; i += 2 * k) { // 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符 if (i + k <= ch.length) { reverse(ch, i, i + k -1); continue; } // 3. 剩余字符少于 k 个,则将剩余字符全部反转 reverse(ch, i, ch.length - 1); } return new String(ch); } // 定义翻转函数 public void reverse(char[] ch, int i, int j) { for (; i < j; i++, j--) { char temp = ch[i]; ch[i] = ch[j]; ch[j] = temp; } } }
替换空格
class Solution { public: string replaceSpace(string s) { int count = 0; // 统计空格的个数 int sOldSize = s.size(); for (int i = 0; i < s.size(); i++) { if (s[i] == ' ') { count++; } } // 扩充字符串s的大小,也就是每个空格替换成"%20"之后的大小 s.resize(s.size() + count * 2); int sNewSize = s.size(); // 从后先前将空格替换为"%20" for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) { if (s[j] != ' ') { s[i] = s[j]; } else { s[i] = '0'; s[i - 1] = '2'; s[i - 2] = '%'; i -= 2; } } return s; } };
翻转字符串里的单词
左旋字符串
把字符串前nTurn to the end
反转区间为前n的子串
反转区间为n到末尾的子串
反转整个字符串
class Solution { public String reverseLeftWords(String s, int n) { int len=s.length(); StringBuilder sb=new StringBuilder(s); reverseString(sb,0,n-1); reverseString(sb,n,len-1); return sb.reverse().toString(); } public void reverseString(StringBuilder sb, int start, int end) { while (start < end) { char temp = sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start++; end--; } } }
KMPAlgorithm classic topic
实现strStr()
文本串 aabaabaaf
模式串 aabaaf
前缀:String contains initials excluding last letter
后缀:......
next数组----Storage pattern string equals the longest suffix before
a | 0 |
---|---|
aa | 1 |
aab | 0 |
aaba | 1 |
aabaa | 2 |
aabaaf | 0 |
Can be found that does not match the location of thef,那么就跳转到fBefore a subscript corresponds to the value of the place,也就是2We'll go on with the match
时间复杂度O(n+m)
构造next数组
初始化
定义两个指针i和j,j指向前缀末尾位置,i指向后缀末尾位置.
处理前后缀不相同的情况
j回退----j = next[j-1];
处理前后缀相同的情况
j++
class Solution { public int strStr(String haystack, String needle) { if (needle.length() == 0) return 0; int[] next = new int[needle.length()]; getNext(next, needle); int j = 0; for (int i = 0; i < haystack.length(); i++) { while (j > 0 && needle.charAt(j) != haystack.charAt(i)) j = next[j - 1]; if (needle.charAt(j) == haystack.charAt(i)) j++; if (j == needle.length()) return i - needle.length() + 1; } return -1; } private void getNext(int[] next, String s) { int j = 0; next[0] = 0; for (int i = 1; i < s.length(); i++) { while (j > 0 && s.charAt(j) != s.charAt(i)) j = next[j - 1]; if (s.charAt(j) == s.charAt(i)) j++; next[i] = j; } } }
重复的子字符串
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成.给定的字符串只含有小写英文字母,并且长度不超过10000.
如果len % (len - next[len - 1] ) == 0 ,则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除,说明有该字符串有重复的子字符串.
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环.
class Solution { public: void getNext (int* next, const string& s){ next[0] = 0; int j = 0; for(int i = 1;i < s.size(); i++){ while(j > 0 && s[i] != s[j]) { j = next[j - 1]; } if(s[i] == s[j]) { j++; } next[i] = j; } } bool repeatedSubstringPattern (string s) { if (s.size() == 0) { return false; } int next[s.size()]; getNext(next, s); int len = s.size(); if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) { return true; } return false; } };
边栏推荐
- MySQL数据库————视图和索引
- LeetCode 0952. Calculate Maximum Component Size by Common Factor: Mapping / Union Search
- 【hbuilder】运行不了部分项目 , 打开终端 无法输入指令
- - daily a LeetCode 】 【 191. A number of 1
- 【MindSpore1.2.0-rc1产品】num_workers问题
- MongoDB打破了原则引入SQL?
- MindSpore:【模型训练】【mindinsight】timeline的时间和实际用时相差很远
- VBA 连接Access数据库和Excle
- 云数据库和本地数据库有什么区别?
- [hbuilder] cannot run some projects, open the terminal and cannot enter commands
猜你喜欢
The JDBC programming of the MySQL database
第十七届“振兴杯”全国青年 职业技能大赛——计算机程序设计员(云计算平台与运维)参赛回顾与总结
Google's AlphaFold claims to have predicted almost every protein structure on Earth
Golang logging library zerolog use record
SimpleOSS third-party library libcurl and engine libcurl error solution
部分分类网络性能对比
云数据库和本地数据库有什么区别?
SimpleOSS第三方库libcurl与引擎libcurl错误解决方法
来了!东方甄选为龙江农产品直播带货
MindSpore:【Resolve node failed】解析节点失败的问题
随机推荐
MindSpore:【JupyterLab】按照新手教程训练时报错
MySQL分库分表
【MindSpore】用coco2017训练Model_zoo上的 yolov4,迭代了两千多batch_size之后报错,大佬们帮忙看看。
Trial writing C language sanbang
数据库索引:索引并不是万能药
跨进程启动后台服务
MySQl数据库————DQL数据查询语言
Linux下安装MySQL教程
Scala学习:类和对象
055 c# print
NXP IMX8QXP replacement DDR model operation process
来了!东方甄选为龙江农产品直播带货
Download and installation of the latest version of MySQL 8.0 under Linux (detailed steps)
C# wpf borderless window add shadow effect
深入浅出边缘云 | 3. 资源配置
MindSpore: CV.Rescale(rescale,shift)中参数rescale和shift的含义?
Witness the magical awakening of the mini world in HUAWEI CLOUD
技术很牛逼,还需要“向上管理”吗?
Zabbix 5.0 Monitoring Tutorial (1)
What is a RESTful API?