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.报数

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

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:
输入: 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;
    }
};