1.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路，遍历从0到n/2，对应位置进行交换
class Solution {
public:
void reverseString(vector<char>& s) {
if (s.size()==1)return;
for(int i =0;i<(s.size()/2);i++)swap(s[i],s[s.size()-i-1]);//相当于做了一次对称变换
}
};
2.整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3
输入: 120
输出: 21
注意：假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
思路：
不断取模运算，生成新的数字。注意C++中取模运算的细节，先做除法，用除法结果乘以除数再用被除数减去
(-7/3) => -2
-2 * 3 => -6
so a%b => -1
同时为了解决int的溢出，计算使用long类型
static const int iMIN = 0X80000000;
static const int iMAX = 0X7FFFFFFF;
class Solution {
public:
int reverse(int x) {
long L = 0;
while(x != 0) {
L = L * 10 + x % 10;
x = x / 10;
}
if(L > iMAX || L < iMIN)
return 0;
return L;//这手秒啊，遇到int类型的溢出问题可以用long来处理。
}
};
3.字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
思路：维护一个26大小的int数组，记录每个单词出现的个数，两次遍历，第一次记录各个字母的个数，第二个找出第一个出现次数为1的
class Solution {
public:
int firstUniqChar(string s) {
vector<int> record(26,0);
if(s.length()==0)return -1;
for (int i = 0; i < s.length(); ++i) {
record[s[i]-'a']++;//统计字母个数
}
for (int k = 0; k < s.length(); ++k) {
if(record[s[k]-'a']==1)return k;//找到第一个只出现一次的字母
}
return -1;
}
};
4.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
思路：和上一题类似，用一个数组维护，遍历数组完成判断。
第一次遍历第一个数组s，统计数字++
第二次遍历第二个数组t，统计数字--
第三次遍历维护的数组，看看是否都为0；
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size()!=t.size())return false;
vector<int> alpha(26,0);
for(int i = 0;i<s.length();i++)alpha[s[i]-'a']++;//第一个字符串来说，找到字母对应位置++
for(int i = 0;i<t.length();i++)alpha[t[i]-'a']--;//第二个字符串来说，找到字母对应位置--
for(int i = 0;i<alpha.size();i++)if(alpha[i]!=0)return false;//判断是否全为0；
return true;
}
};
5.验证回文字符串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
思路：
1.先对字符串进行处理：只保留数组字母的小写
2.判断是否对称，for循环和倒转字符串类似，遍历从0到n/2
class Solution {
public:
bool isPalindrome(string s) {
vector<char> result;
for(int i = 0;i<s.length();i++){
if(s[i]>='a'&&s[i]<='z'){//小写字母的情况
result.push_back(s[i]);
}else if(s[i]>='A'&&s[i]<='Z'){//大写字母的情况
result.push_back(s[i]-'A'+'a');
} else if(s[i]>='0'&&s[i]<='9'){//数字的情况
result.push_back(s[i]);
}
}
for(int i = 0;i<(result.size()/2);i++){
if(result[i]!=result[result.size()-1-i])return false;
}
return true;
}
};
6.字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:输入: "42"
输出: 42
示例 2:输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。因此返回 INT_MIN (−231)
思路
就按照给的要求写就行
处理int型溢出同样使用了long类型来确保精度不会丢失。
class Solution {
public:
int myAtoi(string str) {
long result = 0;
long temp = 0;
bool negative=false;//是否为负数
if(str.length() == 0)return 0;//特殊情况
int k = 0;
for(int i = 0;i<str.length();i++){//忽略前面的空格
if(str[i]!=' ')break;
k++;
}
if(k==str.length())return 0;//全是空格的情况
if(str[k]=='+'){//判断+-
k++;
}else if(str[k]=='-'){
k++;
negative = true;
}else if((str[k]>='0'&&str[k]<='9'));
else return 0;
while (k<str.length()){
if(str[k]>='0'&&str[k]<='9'){
result = result*10+str[k]-'0';
}else break;
k++;
if(negative)temp = -result;
else temp = result;
if(temp>=INT_MAX)return INT_MAX;
if(temp<=INT_MIN)return INT_MIN;
}
if(negative)result = -result;
if(result>=INT_MAX)return INT_MAX;
if(result<=INT_MIN)return INT_MIN;
return result;
}
};
7.实现strStr()
实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
思路
遍历第一个数组，再遍历第二个数组判断，需要两个r循环嵌套。但是需要注意几个细节：
字符串大小，两个字符串长度差值，各层循环次数
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.length()==0)return 0;
auto count = haystack.length()-needle.length()+1;//计算字符串长度差值，确定外层循环次数
if(count<1)return -1;
for(int i = 0;i<count;i++){//外层循环，遍历haystack
int j = 0;
while (j<needle.length()){//内层循环，遍历needle，不用for循环。需要利用j最后的值来判断是否相同
if(haystack[i+j]!=needle[j])break;
j++;
}
if(j==needle.length())return i;
}
return -1;
}
};
8.报数
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
111211211111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s"("两个一"）, 即 21。
21 被读作 "one 2", "one 1"（"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。注意：整数顺序将表示为一个字符串。
示例 1:
输入: 1
输出: "1"
示例 2:
输入: 4
输出: "1211"
3.思路
有点像DP的题目，因为当前答案需要之前的结果
那么维护一个二维数组来存放之前的结果，进行循环计算就好了。空间没优化(其实不用二维数组，只保留上一次的就可以)
class Solution {
public:
string countAndSay(int n) {
vector<vector<int >> results;//存放1-n的式子
//第一个式子 first 只有一个1
vector<int> first;
first.push_back(1);
results.push_back(first);
for(int i = 1;i < n; i++){//n次循环，构造结果
vector<int> temp;//要构造的数组
for(int j = 0;j<results[i-1].size();){
int count=1;
int target=results[i-1][j];
for(int k = j+1;k<results[i-1].size();k++){
if(results[i-1][k]!=target)break;
else{
count++;
}
}
j=j+count;
temp.push_back(count);
temp.push_back(target);
}
results.push_back(temp);
}
vector<int> result = results.back();//取最后一个
string answer;
for(int i = 0;i<result.size();i++){
char c = '0'+result[i];
answer.append(1,c);
}
//cout<<"the answer of "<<n<<"is:"<<answer<<endl;
return answer;
}
};
9.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
思路
还好是找前缀，不是字串问题
挨个遍历就行了，不是很难
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string result="";
if(strs.size()<1)return result;
for(int i = 0;i<strs[0].size();i++){//从下标0开始找
char c = strs[0][i];
for(int j = 1;j<strs.size();j++){//遍历每一个数组
if(i>=strs[j].size()||c!=strs[j][i])return result;//注意判断其他字符串大小，防止越界访问
}
result.push_back(c);
}
return result;
}
};
网友评论