Leedcode刷题——2 字符串

注：以下代码均为c++

1. 反转字符串

void reverseString(vector<char>& s) {int n = s.size();int i, j;for(i = 0, j = n - 1; i < j; i++, j--){swap(s[i], s[j]);}}

2. 整数反转

int reverse(int x) {int rev = 0;while(x != 0){if(rev < INT_MIN / 10 || rev > INT_MAX / 10)return 0;int digit = x % 10;x = x / 10;rev = rev * 10 + digit;}return rev;
}

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

思想：哈希表

int firstUniqChar(string s) {unordered_map<char, int> hash;int i;/*for(i = 0; i < s.size(); i++){if(hash.count(s[i]) == 0)hash[s[i]] = 1;elsehash[s[i]]++;}*/for(i = 0; i < s.size(); i++) {hash[s[i]]++;  //哈希表默认value值为0，可以直接++，不用像上面一样先赋值再加。}for(i = 0; i < s.size(); i++){if(hash[s[i]] == 1)return i;}return -1;
}

4. 有效的字母异位词

思路：哈希表

bool isAnagram(string s, string t) {unordered_map<char, int> maps, mapt;int i;if(s.size() != t.size())return false;for(i = 0; i < s.size(); i++){maps[s[i]]++;mapt[t[i]]++;}if(maps == mapt)return true;elsereturn false;
}

5. 验证回文串

bool isPalindrome(string s) {int i, j;int n = s.size();for(i = 0, j = n - 1; i < j; i++, j--){  //注意for循环内部需要判断i < j//找到下一个字母或数字while(i < j && isalnum(s[i]) == 0)  //isalnum()判断是否为字母和数字i++;//找到前一个字母或数字while(i < j && isalnum(s[j]) == 0)j--;if(i < j && tolower(s[i]) != tolower(s[j]))return false;}return true;
}

6. 字符串转换整数

int myAtoi(string s) {int i = 0, n = s.size();int symbol = 1;  // +int num = 0;//1 判断空格while(i < n && s[i] == ' ')i++;//2 判断正负if(i < n && s[i] == '-'){symbol = -1;  // -i++;}else if(i < n && s[i] == '+')i++;//3 若非数字返回0if(i < n && !isdigit(s[i]))return 0;//4 若为数字，越界处理要注意，这个地方好坑啊。。。while(i < n && isdigit(s[i])){if(num > INT_MAX/10  || (num == INT_MAX/10 && s[i]-'0' > INT_MAX % 10))return symbol == 1 ? INT_MAX: INT_MIN;elsenum = num * 10 + (s[i] - '0');i++;}return symbol * num;
}

7. 实现strStr()

思路：
字符串匹配问题
法1：暴力法

int strStr(string haystack, string needle){int i = 0, j = 0;int n = haystack.size(), m = needle.size();while(i < n && j < m){if(haystack[i] == needle[j]){i++;j++;}else{  //若不匹配，退回，从上一次匹配的下一个开始i = i - j + 1;j = 0;}if(j == m)return i - j;}return -1;
}

法2：kmp算法

vector<int> build_next(string needle){int m = needle.size();vector<int> next;next.push_back(0);int prefix_len = 0;  //当前共同前后缀的长度int i = 1;while(i < m){if(needle[prefix_len] == needle[i]){prefix_len++;next.push_back(prefix_len);i++;}else{if(prefix_len == 0){next.push_back(0);i++;}elseprefix_len = next[prefix_len - 1];}}return next;
}
int strStr1(string haystack, string needle){int n = haystack.size(), m = needle.size();vector<int> next = build_next(needle);int i = 0, j = 0;while(i < n){if(haystack[i] == needle[j]){  //若匹配，指针后移i++;j++;}else if(j > 0)  //若不匹配，根据next跳过子串前面一些字符j = next[j-1];else  //若第一个字符就不匹配i++;if(j == m)return i-j;}return -1;
}

8. 外观数列

string countAndSay(int n) {int i, j, k;  //i为索引，j为计数器//每一次计算只需要知道它的前一个字符串即可，不需要知道每一项，所以用两个字符串分别记录当前项和前一项。string str1 = "1", str2;for(k = 0; k < n - 1; k++){i = 0;while(i < str1.size()){j = 0;while(i+1 < str1.size()  && str1[i] == str1[i+1]){j++;i++;}//法1//str2.push_back(j+1+'0');  //int转char +'0'//str2.push_back(str1[i]);//法2str2 += to_string(j+1);str2 += str1[i];i++;}str1 = str2;str2.clear();}return str1;
}

9. 最长公共前缀

string longestCommonPrefix(vector<string>& strs) {int i, j;string prefix = strs[0];  //假设一个字符串为最长公共前缀//遍历后面的每一个字符串for(i = 1; i < strs.size(); i++){for(j = 0; j < strs[i].size(); j++){if(strs[i][j] != prefix[j]){prefix = prefix.substr(0, j);  //截取字符串，注意需要赋值操作。从下标0开始取j个break;}}if(j < prefix.size())prefix = prefix.substr(0, j);}return prefix;
}