leetcode字符串算法练习，不定期更新

有效的字母异位词

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

说明：
你可以假设字符串只包含小写字母。

思路

字母异位词的字符串长度和相对应的字母数量是相等的，因此可以借鉴桶排序的思想来统计每个字母的数量是否是相等的，如果不相等则就不是字母异位词

实现

bool isAnagram(string s, string t)
{
    if (s.size() != t.size()) {
        return false;
    }

    int sArr[256] = { 0 };
    int tArr[256] = { 0 };

    for (int i = 0; i < s.size(); ++i) {
        sArr[s[i]]++;
        tArr[t[i]]++;
    }

    for (int i = 0; i < 256; ++i) {
        if (sArr[i] != tArr[i]) {
            return false;
        }
    }
    return true;
}

验证回文字符串

题目

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明： 本题中，我们将空字符串定义为有效的回文串。
示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

思路

使用两个游标，一个在字符串头，一个在字符串尾，两个游标同时向中间靠拢，遇到非字母和数字就跳过

实现

bool isLetterOrNum(char c)
{
    if ((c >= 'A' && c <= 'Z') 
        || (c >= 'a' && c <= 'z')
        || (c >= '0' && c <= '9')) {
        return true;
    }
    return false;
}

bool compareLetter(char c, char c1)
{
    if (c == c1) {
        return true;
    } else if (c >= 'A' && c <= 'Z') {
        return c + 32 == c1;
    } else if (c >= 'a' && c <= 'z') {
        return c - 32 == c1;
    } else {
        return false;
    }
}

bool isPalindrome(string s)
{
    if (s.empty() || s.size() == 1) {
        return true;
    }
    
    int l = 0;               // 字符串第一个字符
    int r = s.size() - 1; // 字符串最后一个字符

    while (l < r) {
        // 从前往后找到字母或数字, 保证l不越界
        while (l < s.size() && !isLetterOrNum(s[l])) {
            l++;
        } 

        // 从后往前找到字母或数字， 保证r不越界
        while(r >= 0 && !isLetterOrNum(s[r])) {
            r--;
        }

        // 如果字符串没有字母或数字则返回真
        if (l == s.size() || r < 0) {
            return true;
        }

        if(!compareLetter(s[l], s[r])){
            return false;
        }
        ++l;
        --r;
    }
    return true;
}

字符串转换整数(atoi)

题目

请你来实现一个 atoi 函数，使其能将字符串转换成整数.首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明： 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。

思路

根据题干分为几个步骤

1. 跳开字符串前面的空格
2. 判断正负号
3. 判断是否是数字，如果是就计算数值
4. 判断该数字是否溢出，因此需要4个字节以上的存储空间，这里选用double类型（在leetcode的环境中，long或者long long存储num都会溢出）

实现

int myAtoi(string str)
{
    if (str.empty()) {
        return 0;
    }

    int i = 0;
    double num = 0;
    int negative = 1;
    // 忽略前面的空格
    while (str[i] == ' ')++i;
    // 判断正负号
    if (str[i] == '-') {
        negative = -1;
        i++;
    } else if (str[i] == '+') {
        i++;
    }
    // 计算数字
    while (str[i] >= '0' && str[i] <= '9') {
        num = str[i] - '0' + num * 10;
        ++i;
    }
    // 恢复数字的符号
    num *= negative;

    if (num < INT_MIN) {
        num = INT_MIN;
    } else if (num > INT_MAX) {
        num = INT_MAX;
    }

    return num;
}

实现strStr()

题目

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明： 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr()以及 Java的 indexOf() 定义相符。

思路

在haystack字符串中找出needle字符串意味着haystack的字符长度大于等于needle的字符长度，而且只需要执行haystack.length()-needle.length()次比较

实现

int strStr(string haystack, string needle)
{
    if (needle.empty()) {
        return 0;
    }

#if 0
    return haystack.find(needle);
#else
    int j;
    int hlen = haystack.length(), nlen = needle.length();
    for (int i = 0; i <= hlen - nlen; ++i) {
        for (j = 0; j < nlen; ++j) {
            if (haystack[i + j] != needle[j]) {
                break;
            }
        }
        if (j == nlen) {
            return i;
        }
    }
    return -1;
#endif
}

最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明： 所有输入只包含小写字母 a-z 。

思路

以数组中的第一个字符串作为基准，遍历比较字符串相应下标的字符，相等则放入vector中，如果其中一个不相等则直接返回

实现

string longestCommonPrefix(vector<string>& strs)
{    
    string res="";
    if(strs.empty())
        return res;
    for(int i=0; i<strs[0].size(); ++i)
    {
        for(int j=1; j<strs.size(); ++j)
        {
            if(strs[j][i]!=strs[0][i])
                return res;
        }
        res.push_back(strs[0][i]);
    }
    return res;
}