Leetcode-字符串刷题记录

520. 检测大写字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean detectCapitalUse(String word) {
int i = 0;
char[] arr = word.toCharArray();
int up = 0, low = 0;
while(i < arr.length){
if(arr[i] >= 'a'){
low++;
}else{
up++;
}
i++;
}
if(up == arr.length) return true;
if(low == arr.length) return true;
if(up == 1 && arr[0] < 'a') return true;
return false;
}

125. 验证回文串

经典问题,需要过滤非字符非数字。

1
2
3
4
5
6
7
8
9
10
11
public boolean isPalindrome(String s) {
if(s == null) return true;
s = s.toLowerCase();
StringBuilder str = new StringBuilder(s.length());
for (char c : s.toCharArray()) {
if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
str.append(c);
}
}
return str.toString().equals(str.reverse().toString());
}

14. 最长公共前缀

  • 首先计算出最短字符串的长度,这个长度就是外层循环的遍历次数。
  • 内层逐个比较字符串的指定位置的值。
  • 通过StringBuilder拼接公共前缀。
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
26
27
28
29
30
31
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0)
return "";
StringBuilder sb = new StringBuilder();
int minLength = 1000;
//计算最短字符串长度
for(String str : strs){
if(str.length() < minLength){
minLength = str.length();
}
}
String demo = strs[0];
for(int i = 0; i< minLength; i++){
boolean flag = true;
char c = demo.charAt(i);
for(int j = 1; j < strs.length; j++){
if(strs[j].charAt(i) != c){
//不等于
flag = false;
break;
}
}
if(flag){
sb.append(c);
flag = true;
}else{
break;
}
}
return sb.toString();
}

434. 字符串中的单词数

一轮遍历即可,判断依据是:当前值是空格,前一位非空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int countSegments(String s) {
if (s == null) {
return 0;
}
s = s.trim();
if (s.length() == 0) {
return 0;
}
int count = 1;
for (int i = 1; i < s.length(); i++) {
// 当前值是空格,前一位非空格
if (s.charAt(i) == 32 && s.charAt(i - 1) != 32) {
count++;
}
}
return count;
}

58. 最后一个单词的长度

1
2
3
4
5
public int lengthOfLastWord(String s) {
String[] s1 = s.split(" ");
if(s1.length == 0) return 0;
return s1[s1.length -1].length() == 0 ? 0 : s1[s1.length -1].length();
}

344. 反转字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void reverseString(char[] s) {
int left = 0, right = s.length -1;
while(left < right){
swap(s , left, right);
left++;
right--;
}
}

public void swap(char[] s, int i, int j){
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}

541 反转字符串Ⅱ

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
26
27
28
29
30
31
32
public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i+= 2*k){
//每隔2k反转一次
//判断剩余字符
int rest = arr.length - i;
if(rest < k){
reverse(arr,i, arr.length - 1);
}else if(rest < 2 * k && rest >= k){
reverse(arr,i, i + k - 1);
}else{
reverse(arr,i, i+k - 1);
}
}
return String.valueOf(arr);
}


public void reverse(char[] s,int i, int j) {
int left = i, right = j;
while(left < right){
swap(s , left, right);
left++;
right--;
}
}

public void swap(char[] s, int i, int j){
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}

557. 反转字符串中的单词Ⅲ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String reverseWords(String s) {
String[] strs = s.split(" ");
String[] reverseString = new String [strs.length];
int index = 0;
for(String str : strs){
reverseString[index++] = new StringBuffer(str).reverse().toString();
}
StringBuilder sb = new StringBuilder();
for(int i =0; i < strs.length; i++){
sb.append(reverseString[i]);
if(i != reverseString.length - 1) sb.append(" ");
}
return sb.toString();
}

151. 反转字符串中的单词

1
2
3
4
5
6
public String reverseWords(String s) {
s = s.trim();
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}

387. 字符串中的第一个唯一字符

1
2
3
4
5
6
7
8
9
10
11
12
public static int firstUniqChar(String s) {
int[] letter=new int[26];
for (char c:s.toCharArray()) {
letter[c-'a']++;
}
for (int i = 0; i <s.length() ; i++) {
if(letter[s.charAt(i)-'a']==1) {
return i;
}
}
return -1;
}

389. 找不同

1
2
3
4
5
6
7
8
9
10
11
char findTheDifference(string s, string t) {
vector<int> count(26,0);
for(char ch : s){
count[ch - 'a']++;
}
for(char ch : t){
count[ch - 'a']--;
if(count[ch - 'a'] < 0) return ch;
}
return ' ';
}

383. 赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
bool canConstruct(string ransomNote, string magazine) {
vector<int> count(26, 0);
for(char ch : magazine){
count[ch - 'a']++;
}
for(char ch : ransomNote){
count[ch - 'a']--;
if(count[ch - 'a'] < 0){
return false;
}
}
return true;
}

242. 有效的字母异位词

1
2
3
4
5
6
7
bool isAnagram(string s, string t) {
vector<int> cnt(26,0);
for(char ch : s) cnt[ch - 'a']++;
for(char ch : t) cnt[ch - 'a']--;
for(int count : cnt) if(count != 0) return false;
return true;
}

49. 字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
map<string, vector<string>> map;
for(int i =0; i < strs.size(); i++){
string key = strs[i];
sort(key.begin(), key.end());
map[key].push_back(strs[i]);
}
for(auto ite = map.begin(); ite != map.end(); ite++) res.push_back(ite->second);
return res;
}

451. 根据字符出现频率排序

1
2
3
4
5
6
7
8
9
10
11
12
string frequencySort(string s) {
map<char,int> map;
for(char c : s) map[c]++;
//sort
vector<pair<char, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), [](auto & a, auto & b){
return a.second > b.second;
});
string res;
for(auto v : vec) res += string(v.second,v.first);
return res;
}

657. 机器人能否返回原点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool judgeCircle(string moves) {
int index = 0;
int updown = 0, rightleft = 0;
while(index <= moves.length()){
switch(moves[index]){
case 'R':
rightleft++;
break;
case 'L':
rightleft--;
break;
case 'U':
updown++;
break;
case 'D':
updown--;
break;
}
index++;
}
if(updown == 0 && rightleft == 0) return true;
return false;
}

551. 学生出勤记录Ⅰ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool checkRecord(string s) {
int late = 0, absent = 0;
for(int i = 0; i < s.length(); i++){
if(s[i] == 'A'){
//absent
absent++;
late = 0;
if(absent > 1) return false;
}else if(s[i] == 'L'){
late++;
if(late > 2) return false;
}else {
//P
late = 0;
}
}
return true;
}

28. 实现strStr()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int strStr(string haystack, string needle) {
if ( needle == "" )
return 0;
int hlen = haystack.length();
int nlen = needle.length();
int i,j;
for(i=0;i<hlen;i++){
for(j=0;j<nlen;j++)
if(haystack[i+j]!=needle[j])
break; //不符合就结束本轮匹配
if(j==nlen)
return i;
}
return -1;
}

8. 字符串转换整数

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
int myAtoi(string s) {
int i=0; // 遍历的游标
while(i<s.size()&&s[i]==' ') i++; // 去掉空白字符
if(i==s.size()) return 0; // 如果s为全空

// 处理第一个非空字符
int sign=1;
if(s[i]=='-'){
sign=-1;
i++;
}
else if(s[i]=='+')
i++;
else if(!isdigit(s[i]))
return 0;

// 处理第一个数字字符
int n=0;
while(isdigit(s[i])&&i<s.size()){
if((INT_MAX-(s[i]-'0'))/10.0<n) return sign==-1?sign*INT_MAX-1:INT_MAX; // 如果溢出
n=10*n+(s[i]-'0');
i++;
}
return sign*n;
}

67. 二进制求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string addBinary(string a, string b) {
string result;
const int n = a.size() > b.size() ? a.size() : b.size();
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int carry = 0;
for(int i = 0; i < n; i++){
int ai = i < a.size() ? a[i] - '0' : 0;
int bi = i < b.size() ? b[i] - '0' : 0;
int val = (ai + bi + carry) % 2;
carry = (ai + bi + carry) / 2;
result.insert(result.begin(), val + '0');
}
if(carry == 1) result.insert(result.begin(), '1');
return result;
}

412. Fizz Buzz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<string> fizzBuzz(int n) {
vector<string> res;
for(int i = 1; i <= n; i++){
string tmp;
if(i % 15 == 0){
res.push_back("FizzBuzz");
}else if(i % 5 == 0){
res.push_back("Buzz");
}else if(i % 3 == 0){
res.push_back("Fizz");
}else{
res.push_back(to_string(i));
}

}
return res;
}

299. 猜数字游戏

需要注意数字出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string getHint(string secret, string guess) {
int bull = 0, cow = 0;
vector<int> num(10,0);
for(int i = 0; i < guess.size(); i++){
if(guess[i] == secret[i]){
bull++;
}else {
//当前位置不一致,需要判断当前字符是否出现在secret里面
//通过vector存储数字出现次数
if(num[secret[i] - '0']++ < 0) cow++;
if(num[guess[i] - '0']-- > 0) cow++;
}
}
return to_string(bull) + 'A' + to_string(cow) + 'B';
}

506. 相对名次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<string> findRelativeRanks(vector<int>& score) {
vector<int> org = score;
sort(score.rbegin(), score.rend());
unordered_map<int, string> order;
for(int i = 0; i < score.size(); i++){
if(i >= 3) order[score[i]] = to_string(i+ 1);
if(i == 0) order[score[i]] = "Gold Medal";
if (i == 1) order[score[i]] = "Silver Medal";
if (i == 2) order[score[i]] = "Bronze Medal";
}
vector<string> res(score.size(), "");
for(int i = 0; i < res.size(); i++){
res[i] = order[org[i]];
}
return res;
}

539. 最小时间差

  • 将时间转换成分钟。
  • 注意钟表是模运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findMinDifference(vector<string>& timePoints) {
vector<int> q;
int res = INT_MAX;
for(string t : timePoints){
int hour = 10 * (t[0] - '0') + t[1] - '0';
int min = 10 * (t[3] - '0') + t[4] - '0';
q.push_back(60 * hour + min);
}
sort(q.begin(), q.end());
q.push_back(q[0] + 24 * 60);
for(int i = 1; i < q.size(); i++){
res = min(res, q[i] - q[i - 1]);
}
return res;
}

553. 最优除法

题解:被除数不变,除数最小,如果能理解这个数学知识,那么就是一道easy难度的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
string optimalDivision(vector<int>& nums) {
if(nums.size() == 1){
return to_string(nums[0]);
}else if(nums.size() == 2){
return to_string(nums[0]) + "/" + to_string(nums[1]);
}
string res(to_string(nums[0]) + "/(");
for(int i = 1; i < nums.size() - 1; i++){
res += to_string(nums[i]) + "/";
}
res += to_string(nums.back()) + ")";
return res;
}

38. 外观数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String countAndSay(int n) {
String res = "1";
for(int i = 2; i <= n; i++){
StringBuilder temp = new StringBuilder();
for(int j = 0; j < res.length(); j++){
int count = 1;
while(j + 1 < res.length() && res.charAt(j) == res.charAt(j + 1)){
j++;
count++;
}
temp.append(count).append(res.charAt(j));
}
res = temp.toString();
}
return res;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!