Leetcode算法（二）-探索初级算法-字符串

发表于 | 分类于 ，

1. 概述

2. 算法题

2.1 反转字符串

  • 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出
  • 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题
  • 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符
  • 解题思路
    • 直接利用STL中的reverse函数
    • 双指针思想
1
2
3
4
5
6
class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void reverseString(vector<char>& s) {
        if (s.size() <= 1) {
            return;
        }
        int i = 0;
        int j = s.size() - 1;
        while (i < j) {
            swap(s[i], s[j]);
            i ++;
            j --;
        }
    }
};

2.2 整数反转

  • 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转
  • 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0
  • 解题思路
    • 先转字符串，反转，再转整数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < -2e31 or x > 2e31 - 1:
            return 0
        xStr = str(int(math.fabs(x)))[::-1]
        if x < 0:
            if -int(xStr) < -2147483648 or -int(xStr) > 2147483647:
                return 0
            return -int(xStr)
        elif x > 0:
            if int(xStr) < -2147483648 or int(xStr) > 2147483647:
                return 0
            return int(xStr)
        else:
            return x

2.3 字符串中的第一个唯一字符

  • 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1

  • 解题思路

    • 构造一个26个字母的hash表，一次添加
    • 返回字符串字符在hash表中为1的字符索引
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int firstUniqChar(string s) {
        if s.size() == 0 return -1;
        if s.size() == 1 return 0
        int hash[26] = {0};   
        for(char n:s)
            hash[n-'a'] ++;
        for(int i = 0; i < s.size(); i ++)
            if(hash[s[i] - 'a'] == 1)
                return i;
        return -1;
    }
};

2.4 有效的字母异位词

  • 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词
  • 解题思路
    • 排序
    • Hash表方法，采用26个字母长度的vector设定初始数值为0，按照字母进行设置数值加1；再按照查询字符串进行数值相减，如果向量中所有字母的数值为0，那么就表示为字母异位词；否则，不是字母异位词
1
2
3
4
5
6
7
8
class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t ? true : false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;
        int hash[26] = {0};
        for(auto n : s)
            hash[n - 'a'] ++;
        for(auto n : t)
            hash[n - 'a'] --;
        for(int i = 0; i < 26; i ++)
            if(hash[i] != 0)   return false;
        return true;
    }
};

2.5 验证回文字符串

  • 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写
  • 我们将空字符串定义为有效的回文串
  • 解题思路
    • 采用双指针思想，前后指针分别进行移动和比较
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
class Solution {
    
    bool isValidChar(char c) {
        if ((tolower(c) >= 'a' && tolower(c) <= 'z') || (tolower(c) >= '0' && tolower(c) <= '9'))
            return true;
        return false;
    }
    
public:
    
    bool isPalindrome(string s) {
        if (s.size() == 0) {
            return true;
        }
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (!isValidChar(s[i])) i ++;
            if (!isValidChar(s[j])) j --;
            if (isValidChar(s[i]) && isValidChar(s[j])) {
                if (tolower(s[i]) == tolower(s[j])) {
                    i ++;
                    j --;
                } else return false;
            }
        }
        return true;
    }
};

2.6 字符串转换整数 (atoi)

  • 实现一个 atoi 函数，使其能将字符串转换成整数
  • 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下
    • 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
    • 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
    • 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响
    • 假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换
  • 在任何情况下，若函数不能进行有效的转换时，请返回 0
  • 本题中的空白字符只包括空格字符 ' '
  • 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231)
  • 解题思路 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int myAtoi(string str) {
        if (str.size() == 0) return 0;
        int i = 0, label = 1;
        long ans = 0;
        while (str[i] == ' ') i ++;
        if (str[i] == '-') label = -1;
        if (str[i] == '-' || str[i] == '+') i ++;
        for (; i < str.size() && isdigit(str[i]); i ++) {
            ans = ans * 10 + (str[i] - '0');
            if (ans > INT_MAX && label == 1) return INT_MAX;
            if (ans > INT_MAX && label == -1) return INT_MIN;
        }
        return label * ans;
    }
};

2.7 实现 strStr()

  • 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1
  • 解题思路
    • 遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == "") return 0;
        if (haystack.size() == 0 && needle.size() > 0) return -1;
        if (haystack.size() == 0 && needle.size() == 0) return 0;
        if (needle.size() > haystack.size()) return -1;
        int n = needle.size();
        for (int i = 0; i < haystack.size() - n + 1; i ++) {
            for (int j = i; j < i + n; j ++) {
                if (haystack[j] != needle[j - i]) {
                    break;
                }
                if (j == i + n - 1) return i;
            }
            
        }
        return -1;
    }
};

2.8 外观数列

  • 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

    • 1
      2
      3
      4
      5
      1.     1
      2.     11
      3.     21
      4.     1211
      5.     111221

    • 1 被读作 "one 1" ("一个一") , 即 11。
      11 被读作 "two 1s" ("两个一"）, 即 21。
      21 被读作 "one 2", “one 1" （"一个二" , "一个一") , 即 1211

    • 给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项

    • 整数序列中的每一项将表示为一个字符串

  • 解题思路

    • 递归+循环
    • 从第一层开始递归，循环遍历字符串并计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) return "1";
        string previous = countAndSay(n-1), result = "";
        int count = 1;
        for (int i = 0; i < previous.length(); i ++) {
            if (previous[i] == previous[i + 1]) {
                count ++;
            } else {
                result += to_string(count) + previous[i];
                count = 1;
            }
            
        }
        return result;
    }
};

2.9 最长公共前缀

  • 编写一个函数来查找字符串数组中的最长公共前缀
  • 如果不存在公共前缀，返回空字符串 ""
  • 解题思路
    • 循环遍历
    • 后续的最长公共前缀由之前的最长公共前缀决定
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string r = strs.size() ? strs[0] : "";
        for (auto s : strs) {
            while(s.substr(0, r.size()) != r) {
                r = r.substr(0, r.size() - 1);
                if (r == "") return r;
            }
        }
        return r;
    }
};