- String、StringBuilder的基本用法
- 16. 替换空格 - AcWing题库">16. 替换空格 - AcWing题库
- 31. 表示数值的字符串 - AcWing题库">各种逻辑判断31. 表示数值的字符串 - AcWing题库
- 87. 把字符串转换成整数">逻辑判断87. 把字符串转换成整数
- 165. 比较版本号 - 力扣">线性扫描+判断 165. 比较版本号 - 力扣
- 56. 从1到n整数中1出现的次数 ">多情况讨论 56. 从1到n整数中1出现的次数
- 63. 字符串中第一个只出现一次的字符">HashMap的使用63. 字符串中第一个只出现一次的字符
- 64. 字符流中第一个只出现一次的字符">队列+哈希表 64. 字符流中第一个只出现一次的字符
- 77. 翻转单词顺序">旋转字符串 77. 翻转单词顺序
- 78. 左旋转字符串 - AcWing题库">旋转字符串 78. 左旋转字符串 - AcWing题库
- KMP
String、StringBuilder的基本用法
StringBuilder
增 ：append(e)//e表示各种数据类型的参数insert(int offset, e)删： StringBuilder delete(int start, int end)删除此序列的子字符串中的字符。StringBuilder deleteCharAt(int index)删除 char在这个序列中的指定位置。改： StringBuilder replace(int start, int end, String str)用指定的String中的字符替换此序列的子字符串中的 String 。setCharAt(int index, char ch)///指定索引处的字符设置为 ch 。查 ：charAt(int index)indexOf(String str)indexOf(String str, int fromIndex)lastIndexOf(String str)lastIndexOf(String str, int fromIndex)//返回指定子字符串最后一次出现的字符串中的索引。其他用法：StringBuilder reverse()String substring(int start, int end)toString()//返回表示此顺序中的数据的字符串。
String
增 ：无删： 无查：int indexOf(int ch)indexOf(String str)//返回指定子字符串第一次出现的字符串内的索引。indexOf(String str, int fromIndex)lastIndexOf(int ch)startsWith(String prefix)endsWith(String suffix)trim()startWith()endsWith()toLowerCase()toUpperCase()改：String replace(char oldChar, char newChar)String replace(CharSequence target, CharSequence replacement)replaceAll(String regex, String replacement)其他：compareTo()concat(String str)contentEquals(StringBuffer sb)
16. 替换空格 - AcWing题库
熟悉基本的语法
增 append, insert
删 deleteCharAt, delete(int start, int end)
改 replace(int start, int end, String str), setCharAt()
查 length(), indexOf, charAt(), lastIndexOf(), subString(), toString()
class Solution {
public String replaceSpaces(StringBuffer str) {
for (int i = 0; i < str.length(); i ++){
if (str.charAt(i) == ' '){
str.deleteCharAt(i);
str.insert(i, "%20");
}
}
return str.toString();
}
}
各种逻辑判断31. 表示数值的字符串 - AcWing题库
class Solution {
public boolean isNumber(String s) {
if (s.length() == 0) return false;
//取出字符串两端的空格（有空格不是数值）" ."
for (;s.length() > 0 && s.charAt(0) == ' ';)
s = s.substring(1);
for (int i = s.length() - 1;i >= 0 && s.charAt(i) == ' '; i --)
s = s.substring(0, i);
if (s.length() == 0) return false; // ""
if (s.charAt(0) == '+' || s.charAt(0) == '-') s = s.substring(1, s.length());
if (s.length() == 0) return false; // "+" "-"
int hasE = 0, hasDot = 0;
for (int i = 0; i < s.length(); i ++){
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') ;
else if (s.charAt(i) == 'e' || s.charAt(i) == 'E'){
hasE ++;
// "123e" "e123" "12e132e" ".e1"
if (hasE > 1 || i == 0 || i == s.length() - 1 || i - 1 == 0 && s.charAt(i - 1) == '.') return false;
}
else if (s.charAt(i) == '.'){
hasDot++;
// "123.213.3" "1e123.3" "."
if (hasE > 0 || hasDot > 1 || s.length() == 1) return false;
}
//"1e+"
else if (i > 0 && (s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E') &&
(s.charAt(i) == '+' || s.charAt(i) == '-') ){
if (i == s.length() - 1) return false;
}
else return false;//其他字符
}
return true;
}
}
逻辑判断87. 把字符串转换成整数
class Solution {
public int strToInt(String str) {
//忽略行首空格
// i扫描下标
int len = str.length();
int i = 0;
while (i < len && str.charAt(i) == ' '){i++;}
//跳过+-
boolean isNeg = false;
if(i < len && str.charAt(i) == '+')i++;
if(i < len && str.charAt(i) == '-'){i++;isNeg = true;}
//"+" "-" ""
if (i == len) return 0;
//开始整数的读取
long res = 0;
while (i < len && str.charAt(i) >= '0' && str.charAt(i) < '9'){
res = res * 10 + (str.charAt(i++) - '0');
}
//">2^31" "<-2^31-1"
if (!isNeg && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
if (-res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
return isNeg ? -(int)res : (int) res;
}
}
线性扫描+判断 165. 比较版本号 - 力扣
class Solution {
public int compareVersion(String version1, String version2) {
// 遍历每一个版本号，版本号中去除前导零，比较大小
int i = 0, j = 0, m = version1.length(), n = version2.length();
while (i < m || j < n){
int res1 = 0, res2 = 0, idx1 = i, idx2 = j, im = i, in = j;
while (im != m && version1.charAt(im) != '.') im++;
while (in != n && version2.charAt(in) != '.') in++;
while (idx1 < im && version1.charAt(idx1) == '0') idx1++;
while (idx1 < im) res1 = res1 * 10 + version1.charAt(idx1++) - '0';
while (idx2 < in && version2.charAt(idx2) == '0') idx2++;
while (idx2 < in) res2 = res2 * 10 + version2.charAt(idx2++) - '0';
// System.out.println(res1 + " " + res2 + ' ' + im + " " + in);
if (res1 > res2) return 1;
else if (res1 < res2) return -1;
if (im == m) i = im; else i = im + 1;
if (in == n) j = in; else j = in + 1;
}
return 0;
}
}
多情况讨论 56. 从1到n整数中1出现的次数
思路1
从前到后遍历每个数，把其转换为字符串，再遍历字符串，如果遇到字符’1’,res++
这种方法显然是TLE的
class Solution {
public int numberOf1Between1AndN_Solution(int n) {
//从前到后遍历每个数，把其转换为字符串，再遍历字符串，如果遇到字符'1',res++
int res = 0;
for (int i = 1; i <= n; i ++){
String s = String.valueOf(i);
for (int j = 0; j < s.length(); j++ ){
if (s.charAt(j) == '1')
res++;
}
}
return res;
}
}
思路2
按照位数来枚举，假设当前位数是 c的数位 ,数为 abcdef：
计算c数位上1的个数
- c前面的位数是
00 ~ ab-1，有ab * 1000个1 c前面的位数是
ab或者c是第一位- c == 0， 有0个1
- c == 1, 有
def+1个1 - c >1, 有 1000个1
class Solution {
public int numberOf1Between1AndN_Solution(int n) {
//先把数字转换成字符串，用于枚举位数
String s = String.valueOf(n);
int res = 0;
for (int i = 0; i < s.length(); i++ ){
//计算当前数位左边,右边的字符数字和10^(右边数位)
int left = 0, right = 0, t = 1;
int j = 0;
while (j < i) {left = left * 10 + s.charAt(j)-'0'; j++;}
j = i + 1;
while (j < s.length()){right = right * 10 + s.charAt(j) - '0';t = 10*t; j++; }
// 001def~ab1def +ab*1
res += left * t;
// c == 1, 0~def 有def+1个1
if (s.charAt(i) == '1')res += right + 1;
// c >1, 1000~1999 有t个1
if (s.charAt(i) > '1') res += t;
//System.out.println(i + " " + left + " " + right + " " + t + " " + res);
}
return res;
}
}
HashMap的使用63. 字符串中第一个只出现一次的字符
hashmap存放出现的字符和字符次数。
第一次将每个字符串都加入到HashMap中。然后再扫描一遍，如果有value > 1，则赋值给res，否则输出#
class Solution {
public char firstNotRepeatingChar(String s) {
HashMap<Character, Integer> hash = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++ ){
char c = s.charAt(i);
hash.put(c, hash.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < s.length(); i++ ){
if (hash.get(s.charAt(i)) == 1) return s.charAt(i);
}
return '#';
}
}
队列+哈希表 64. 字符流中第一个只出现一次的字符
定义双指针i，j。 队列中：i代表起始位置，j代表中止位置。
遍历一个字符串的每一个字符。
插入操作：
插入队列中，j++
如果当前字符不存在于哈希表中，加入哈希表，统计个数。
如果存在哈希表中，个数+1
查询：
- 判断队首的哈希值，如果 > 1,i++
- 返回i指向的元素
判断队列中存在特定值的复杂度o(n)
class Solution {
List<Character> list = new ArrayList<Character>();
HashMap<Character, Integer> hash = new HashMap<Character, Integer>();
int i = 0, j = -1;
//Insert one char from stringstream
public void insert(char ch){
list.add(ch); j++;
hash.put(ch, hash.getOrDefault(ch, 0) + 1);
}
//return the first appearence once char in current stringstream
public char firstAppearingOnce(){
while (i <= j && hash.get(list.get(i)) > 1){
i++;
}
return i > j ? '#' : list.get(i);
}
}
旋转字符串 77. 翻转单词顺序
- 翻转整个句子
- 翻转每个单词
class Solution {
public String reverseWords(String s) {
//翻转两次
StringBuffer s1 = new StringBuffer(s).reverse();
//System.out.println(s1);
int i = 0, j = 0;
for (j = 0; j < s1.length(); j++){
if (s1.charAt(j) == ' ' || j == s1.length() - 1) {
int k = j;
if (s1.charAt(j) == ' ')j--;
while (i < j){
// System.out.println(s1.substring(i, i + 1) +" " +s1.substring(j, j +1));
String t = s1.substring(i, i + 1);
s1.replace(i, i + 1, s1.substring(j, j+1));
s1.replace(j, j + 1, t);
i++;j--;
}
j = k +1; i = k +1;
}
}
return s1.toString();
}
}
旋转字符串 78. 左旋转字符串 - AcWing题库
- 翻转整个句子
- 翻转指定单词
class Solution {
public String leftRotateString(String str,int n) {
//把字符串翻转
//再从制定位置[0, len-n-1],[len-n,len-1]翻转字符串
int len = str.length();
StringBuffer sb = new StringBuffer(str).reverse();
int i = 0, j = len - n - 1;
while (i < j){
String t = sb.substring(i,i + 1);
sb.replace(i, i + 1,sb.substring(j, j +1));
sb.replace(j, j +1, t);
i++; j--;
}
i = len - n; j = len-1;
while (i < j){
String t = sb.substring(i,i + 1);
sb.replace(i, i + 1,sb.substring(j, j +1));
sb.replace(j, j +1, t);
i++; j--;
}
return sb.toString();
}
}
KMP
求子字符串P在字符串S中出现的次数
next[i]数组的定义是p数组中前缀p[1~j+1]和后缀p[xx~i]相等的最大长度（前缀末尾下标）。
在字符串s中，p[1~j+1]代表S的子串，p[xx~i]代表S
每次移动p的前缀，如果和p的后缀相等，记录下前缀的末尾坐标。这样当需要移动前缀字符串的时候，直接从前缀的末尾匹配（不需要再匹配前缀的中的字符了，因为前缀的字符串中后缀也有）。
如果p[i] == p[j + 1]
以i为结尾的子字符串中前缀字符串p[1 ~ j +1] 和后缀字符串p[XXXX~i]是相等的
赋值 next[i] = ++j
如果p[i] ！= p[j + 1]，说明就要把前缀字符串移动一定距离，直到重新匹配上p的后缀
因此j = next[j]
- 为什么是
p[i]和p[j + 1]比较？
因为建立p的next数组的时候，将p的第一个和第二个字符作为起始点开始比较
class Solution {
public int strStr(String haystack, String needle) {
//KMP
// 首先计算子串的前缀1和后缀2匹配上的最长下标
// 如果子串的前缀和后缀没有匹配上，此时仍然要计算后缀对应的前缀下标
//我们不需要把前缀1末尾下标每次前移一位来匹配2,
// 直接把前缀1中的前缀3（这个前缀3和前缀1的后缀4匹配）， 这个新的前缀3一定是和2匹配的
// 中间的步骤都是可以节省的，因为前缀3 = 4 = 以2末尾字符结尾的后缀子串。
int m = haystack.length(), n = needle.length();
// 每次把后缀坐标i和前缀的下一个坐标j+1匹配， 如果没有匹配上就把前缀j缩小到前缀的前缀，缩小后再进行比较
if (n == 0) return 0;
haystack = " " + haystack; needle = " " + needle;
int[] next = new int[n + 1];
// 后缀坐标i从第二个字符开始
for (int i = 2, j = 0; i <= n; i ++){
while (j > 0 && needle.charAt(i) != needle.charAt(j + 1)) j = next[j];
// 如果i和j+1匹配，增加前缀长度
if (needle.charAt(i) == needle.charAt(j + 1)) j ++;
// 更新后缀的next数组为新的前缀下标
next[i] = j;
}
// 进行父串和子串的匹配
for (int i = 1, j = 0; i <= m; i ++){
// j > 0 -> 如果第一个字符就不匹配, i++移动父子符
while (j > 0 && needle.charAt(j + 1) != haystack.charAt(i)) j = next[j];
if (haystack.charAt(i) == needle.charAt(j + 1)) j++;
if (j == n)return i - j;
}
return -1;
}
}
KMP 28. 实现 strStr()
class Solution {
public int strStr(String p, String s) {
//记录s 的 next数组
int m = p.length(), n = s.length();
if (n == 0) return 0;
p = " " + p; s = " " + s;
int[] next = new int[n + 1];
for (int i = 2, j = 0; i <= n; i ++){
//如果不相同，将s的前缀字符串移动，直到和后缀字符串匹配上
while (j > 0 && s.charAt(i) != s.charAt(j + 1)) j = next[j];
//如果匹配上，j++代表前缀字符串长度增加
if (s.charAt(i) == s.charAt(j + 1)) j++;
//后缀s[xx~i] 匹配上前缀s[1~j+1]
next[i] = j;
}
//进行p和s的匹配
for (int i = 1, j =0; i <= m; i ++){
while (j > 0 && p.charAt(i) != s.charAt(j + 1)) j = next[j];
if (p.charAt(i) == s.charAt(j + 1)) j++;
//如果最终子串匹配上了,此时p的子串下标是i， s是j
if (j == n) return i - j;
}
return -1;
}
}
若有收获，就点个赞吧
0 人点赞
