leetcode

lc1 & lc15& lc 16 & lc 18

多数之和问题

//www.greatytc.com/p/0b91c4b3a135

lc 3 & lc11 &lc 42 &lc19 & lc26-双指针

//www.greatytc.com/p/a69766441eb8

4.找两个数组的中位数

有一种解法是vector直接放在一起，然后排序得到中位数。

我过去的解法：用归并排序做的。归并排序也是用一个新的vector<int>放结果。

还有一种方法，双指针，↓，双指针一个一直移动。

不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第一种思路的时间复杂度是 O(m+n)，空间复杂度是 O(m+n)。第二种思路虽然可以将空间复杂度降到 O(1)，但是时间复杂度仍是 O(m+n)。

也可以用二分查找方法，

（二分查找方法，我试了一下，然后被边界和情况绕晕了。）（见LeetCode题解）

二分查找的时间复杂度是O(log(m+n))

6.z字形变换

计算格子差（模拟）

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==0)
            return "";
        if(numRows==1||s.length()==0)
            return s;
        
        if(numRows==2){
            string s1="";
            string s2="";
            for(int i=0;i<s.length();i++){
                // cout<<s1<<" "<<s2<<endl;
                if(i%2==0){
                    s1+=s[i];
                }else{
                    s2+=s[i];
                }
                
            }
            return s1+s2;
        }
        string res = "";
        // vector<string> resarr(5);
        string resarr[numRows];//用vector初始化貌似有问题，vector合适的初始化方式
        fill(resarr,resarr+numRows,"");
        // fill(resarr.begin(),resarr.end(),"");//vector这样不可，但是数组可。

        for(int i=0;i<numRows;i++){
            int index = i;
            int op=0;
            int lastindex=-1;
            while(index<s.length()){
                if(lastindex!=index){
                    resarr[i]+=s[index];
                    lastindex=index;
                }
                if(op==0){
                    index += 2*numRows-2*i-2;
                    op=1;
                }else if(op==1){
                    index += 2*i;
                    op=0;
                }
            }
        }
        for(int i=0;i<numRows;i++){
            res+=resarr[i];
            // cout<<res<<endl;
        }
        
        return res;

    }
};

7.整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。
 

示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0
 

提示：

-231 <= x <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于大数的运用。用了取余和连乘。

#include<cmath>
class Solution {
public:
    int reverse(int x) {
        long a=INT_MAX;
        long b=INT_MIN;
        long long result=0;
        long long y=(long long)abs((long)x);
        long z=y;
        while(y>0){
            int x=y%10;
            result=(result*10+x);
            y=y/10;
        }
        if(result>a || result<b){
            return 0;
        }
        // int a[wei];
        // int index=0;
        // while(z>0){
            
        // }
        if(x>0)
        return result;
        else
        return -result;
        

        
    }
};

8.字符串转换整数（atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
 

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
示例 4：

输入：s = "words and 987"
输出：0
解释：
第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
         ^
解析得到整数 0 ，因为没有读入任何数字。
由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
示例 5：

输入：s = "-91283472332"
输出：-2147483648
解释：
第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
          ^
第 3 步："-91283472332"（读入 "91283472332"）
                     ^
解析得到整数 -91283472332 。
由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

完全按照要求写下来，可能需要注意很多细节。

这里需要使用long。

C++里最大最小 INT_MIN,INT_MAX

class Solution {
public:
    int myAtoi(string str) {
        int index=0;
        while(str[index]==' '&&index<str.length()){//去掉空格
            index++;
        }
        if(index==str.length())
             return 0;
        if (!(str[index]>='0'&&str[index]<='9')&&str[index]!='-'&&str[index]!='+')//非正常字符
            return 0;

        int abss=1;//判断符合的正负
        long count=0;
        int nowindex=index;
        while(index<str.length()){
            //cout<<str[nowindex]<<endl;
            if(nowindex!=-1&&str[nowindex]=='-'){//判断符号
                abss=-1;
                index++;
                nowindex=-1;
                continue;
            }
            if(nowindex!=-1&&str[nowindex]=='+'){
                abss=1;
                index++;
                nowindex=-1;
                continue;
            }
            if(!(str[index]>='0'&&str[index]<='9'))
                break;
            count=count*10;
            count+=(str[index]-'0');
           // cout<<count<<endl;
            index++;

            if(abss==1&&count>INT_MAX)//注意截断，考虑绝对值要注意最大最小值不同
                return INT_MAX;
            if((abss==-1) &&-count<INT_MIN){
               // cout<<count<<endl;
                return INT_MIN;}
            


        }
        if(abss==1)
            return count;
        else
            return -count;
        
    }
};

9.回文数

判断数字是否是回文数字。

1.121 回文数字 1200001不是回文数字，-121不是，因为有负号

这道题转为字符串很好做。

另一个思路是把数字倒过来，然后看看是不是相等。

class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0){
            return false;
        }
        //会做字符串版的
        //int 转字符串
        //但是另一种思路是：数字反转后 数字和原数大小相同
        // res=res*10+x%10 x/=10 比较res==temp(原数字)
        // string xx=to_string(x);
        // for(int i=0;i<xx.length()/2;i++){
        //     if(xx[i]!=xx[xx.length()-1-i])
        //         return false;
        // }

        int tmp=x;
        int res=0;
        while(x>0&&res<=(INT_MAX-x%10)/10){//要考虑溢出
            res=res*10+x%10;
            x=x/10;
        }
        return res==tmp;
        
    }
};

10.【动态规划-没有看完】正则匹配

开始想用分情况讨论讨论出来，后来发现居然是动态规划。

分情况没有通过↓，只能过280个例子

class Solution {
public:
    bool isMatch(string s, string p) {
        int i=0;
        int index2=0;
        while(i<s.length()&&index2<p.length()){
            // cout<<i<<'\t'<<index2<<endl;
            if(s[i]==p[index2]||p[index2]=='.'){//匹配成功
                i++;
                index2+=1;
                continue;
            }
            if(p[index2]=='*'){
                if(s[i]==p[index2-1]||p[index2-1]=='.')//前面匹配成功，就可以继续go on
                    i++;
                else{
                    index2+=1;
                }
                continue;
            }

//             
            //这次没有匹配成功，看是不是前面有*，有*无所谓
            if(index2-1>0&&p[index2-1]=='*'&&i>1&&p[index2]==s[i-1]){
                index2+=1;
                continue;
            }
            //没有匹配成功，后面有*也无所谓
            if(index2<p.length()-1&&p[index2+1]=='*'){
                index2+=2;
                continue;
            }
            return false;
        }
        // cout<<i<<index2<<endl;
        if(i<s.length())
            return false;

        if(index2<p.length()){//看看后面有没有*
            string nowstr = p.substr(index2+1);
            if(nowstr.find('*')==nowstr.npos){
            // cout<<s.substr(s.length()-nowstr.length())<<endl;
                if(nowstr.length()>s.length())
                    return false;
                return nowstr==s.substr(s.length()-nowstr.length());
            }
            
            if(p[p.length()-1]!='*')//p还有
            return false;
            if(p[index2]=='*'){
                while(index2<p.length()){
                    if(p[index2]!='*')
                        return false;
                    index2+=2;
                }
            }
            if(index2+1<p.length()&&p[index2+1]=='*'){
                index2=index2+1;
                while(index2<p.length()){
                    if(p[index2]!='*')
                        return false;
                    index2+=2;
                }
            }
        }
        return true;
    }
};

lc12 整数转罗马数字

1.特殊情况特殊考虑

2.除法和取余，从大到小，逐个计算。

class Solution {
public:
    string intToRoman(int num) {
        //考虑时间复杂度
        // int a[]={1,5,10,50,100,500,1000};
        // string s[]={"I","V","X","L","C","D","M"};
        int a[]={1,4,5,9,10,40,50,90,100,400,500,900,1000};
        string s[]={"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
        if(num==4)
            return "IV";
        if(num==9)
            return "IX";
        if(num==40)
            return "XL";
        if(num==90)
            return "XC";
        if(num==400)
            return "CD";
        if(num==900)
            return "CM";
        int i=12;
        for(;i>=0;i--){
            if(num>=a[i])
                break;
        }
        string res="";
        bool ex=true;
        //利用数组，实现一一对应（其实这里可以用map）
        //map是自带排序的
        while(ex){
            int tmp=num/a[i];//得到多少个
            int yu=num%a[i];//得到剩下的数字
            for(int j=tmp;j>0;j--){
                res+=s[i];
            }
            num=yu;
            i--;
            if(yu==0){//没有剩下的数字了
                ex=false;
            }
        }
        return res;
    }
};

lc13 罗马数字转整数

1.罗马数字有一些特殊的，需要提前写出来。

2.如果存在特殊的，则优先计算特殊的，否则就正常加数字。

class Solution {
public:
    int romanToInt(string s) {
        map<string,int> c2num={{"I",1},{"V",5},{"X",10},{"L",50},{"C",100},{"D",500},{"M",1000},{"IV",4},{"IX",9},{"XL",40},{"XL",40},{"XC",90},{"CD",400},{"CM",900}};
        if(c2num.find(s)!=c2num.end()){
            return c2num[s];
        }
        int res=0;
        for(int i=0;i<s.length();i++){
            if(i+1<s.length()&&c2num.find(s.substr(i,2))!=c2num.end()){
                res+=c2num[s.substr(i,2)];
                i=i+1;
            }else{
                string xx = s.substr(i,1);
                res+=c2num[xx];

            }

        }
    return res;
    }
};

lc14 最长公共子缀

横向比较，纵向比较

//www.greatytc.com/p/41a662d6127e

lc17 电话号码-dfs

//www.greatytc.com/p/1a6b37b15f42

lc20 括号

直接用栈，如果有就消掉一对括号。

class Solution {
public:
    bool isValid(string s) {
        stack<char> tmp;
        for(int i=0;i<s.length();i++){
            if(s[i]=='('||s[i]=='['||s[i]=='{'){
                tmp.push(s[i]);
            }else{
                if(tmp.empty())
                    return false;
                if(s[i]==')'){
                    if(tmp.top()!='('){
                        return false;
                    }
                    
                }else if(s[i]==']'&& tmp.top()!='[')
                    return false;
                else if(s[i]=='}'&& tmp.top()!='{')
                    return false;
                tmp.pop();
            }
        }
        if(!tmp.empty())
            return false;
        return true;

    }
};