字符串模拟
# 字符串反转
# 344. 反转字符串 (opens new window)
class Solution {
public void reverseString(char[] s) {
int l=0,r=s.length-1;
while(l<r){
char tmp = s[l];
s[l] = s[r];
s[r] = tmp;
l++;r--;
}
return ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 541. 反转字符串 II (opens new window)
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i=0;i<ch.length;i+=2*k){
int l=i;
int r=Math.min(ch.length-1,l+k-1);
while(l<r){
char tmp = ch[l];
ch[l] = ch[r];
ch[r] = tmp;
l++;r--;
}
}
return new String(ch);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 557. 反转字符串中的单词 III (opens new window)
方法一：API
class Solution {
public String reverseWords(String s) {
String[] ss = s.split(" ");
for(int i=0;i<ss.length;i++){
ss[i] = new StringBuffer(ss[i]).reverse().toString();
}
return String.join(" ",ss);
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
方法二：模拟
class Solution {
public String reverseWords(String s) {
StringBuffer sb = new StringBuffer();
int n = s.length();
int i=0;
while(i<n){
int anchor = i;
while(i<n && s.charAt(i)!=' '){
i++;
}
for(int j=anchor;j<i;j++){
sb.append(s.charAt(anchor+i-1-j));
}
while(i<n && s.charAt(i)==' '){
i++;
sb.append(' ');
}
}
return sb.toString();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 151. 反转字符串中的单词 (opens new window)
方法一：API
class Solution {
public String reverseWords(String s) {
String[] words = s.trim().split(" +");//一个或多个空格
Collections.reverse(Arrays.asList(words));
return String.join(" ",words);
}
}
1
2
3
4
5
6
7
2
3
4
5
6
7
方法二：模拟
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 删除首位空格
int j = s.length()-1,i = j;
StringBuilder ret = new StringBuilder();
while(i>=0){
while(i>=0 && s.charAt(i)!=' ')
i--;
ret.append(s.substring(i+1,j+1)+" ");
while(i>=0 && s.charAt(i)==' ')
i--;
j = i;
}
return ret.toString().trim();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 回文字符串
# 9. 回文数 (opens new window)
class Solution {
public boolean isPalindrome(int x) {
if(x<0)
return false;
int tmp = x;
int rev = 0;
while(tmp>0){
int last_num = tmp%10;
tmp /= 10;
rev = rev*10+last_num;
}
return x==rev;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 125. 验证回文串 (opens new window)
class Solution {
public boolean isPalindrome(String s) {
StringBuilder sb = new StringBuilder();
int n = s.length();
for(int i=0;i<n;i++){
char c = s.charAt(i);
if(Character.isLetterOrDigit(c)){
sb.append(Character.toLowerCase(c));
}
}
StringBuilder sbRev = new StringBuilder(sb).reverse();
return sb.toString().equals(sbRev.toString());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 409. 最长回文串 (opens new window)
class Solution {
public int longestPalindrome(String s) {
Map<Character,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
map.put(c,map.getOrDefault(c,0)+1);
}
int ret = 0;
int odd = 0;
for(Map.Entry<Character,Integer> kv : map.entrySet()){
int cnt = kv.getValue();
int rem = cnt % 2;//如果是偶数全都要，如果是奇数要奇数-1个
ret += cnt-rem;
if(rem==1)
odd = 1;
}
return ret + odd;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 中心扩展法
# 5. 最长回文子串 (opens new window)
class Solution {
public String longestPalindrome(String s) {
String res = "";
for(int i =0;i<s.length();i++){
String s1 = palindrome(s,i,i);
String s2 = palindrome(s,i,i+1);
res = res.length()>s1.length()?res:s1;
res = res.length()>s2.length()?res:s2;
}
return res;
}
//从[l,r]向两边扩展寻找回文
public String palindrome(String s,int l,int r){
while(l>=0 && r<s.length()&&s.charAt(l)==s.charAt(r)){
l--;
r++;
}
return s.substring(l+1,r);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 647. 回文子串 (opens new window)
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int ret = 0;
for(int i=0;i<n;i++){
ret = ret + palindrome(s,i,i) + palindrome(s,i,i+1);
}
return ret;
}
int palindrome(String s,int l,int r){
int ans = 0;
while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){
ans++;
l--;
r++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 389. 找不同 (opens new window)
class Solution {
public char findTheDifference(String s, String t) {
char ret = t.charAt(t.length()-1);
for(int i=0;i<s.length();i++){
ret ^= s.charAt(i);
ret ^= t.charAt(i);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 551. 学生出勤记录 I (opens new window)
class Solution {
public boolean checkRecord(String s) {
int absents = 0,lates = 0;
int n = s.length();
for(int i=0;i<n;i++){
char c = s.charAt(i);
if(c=='A'){
absents++;
if(absents>=2){
return false;
}
}
if(c=='L'){
lates++;
if(lates>=3){
return false;
}
}else{
lates = 0;
}
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25