两数之和

1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力解法(O(n2)O(n^2))

先在这个数取出位置i的数字，然后选择j=i+1，判断两个数字相加是否为目标数字，是则返回，否则j++，j遍历完就i++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        for(int i = 0;i<nums.size();i++)
            for(int j = i+1;j<nums.size();j++){
                if(nums[i]+nums[j] == target)
                {
                    res.push_back(i);
                    res.push_back(j);
                    return res;
                }
            }
            return res;
    }
};

解法2：哈希表存储所有数字(O(n)O(n))

先用哈希表存入所有vector中的数字，以数字为键，下标为值。因为不存在的数字默认为0，所以存入下标的时候要+1

然后遍历每一个数字，看一下目标减去这个数字是否存在，存在则返回该值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int i = 1;i<=nums.size();i++){
            mp[nums[i-1]] = i;
        }
        for(int i = 0;i<nums.size();i++){
            if(mp[target-nums[i]]&&mp[target-nums[i]]!=i+1)
            {
                return {i,mp[target-nums[i]]-1};
            }
        }
        return {};
    }
};

两数相加

2. 两数相加 - 力扣（LeetCode） (leetcode-cn.com)

建议参考大数相加模板，有手就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode head = ListNode();
        ListNode* p = &head;
        int t = 0;
        while(l1 != nullptr || l2 != nullptr){
            if(l1){t+=l1->val;l1 = l1->next;}
            if(l2){t+=l2->val;l2 = l2->next;}
            p->next =  new ListNode(t%10);
            p = p->next;
            t/=10;
        }
        if(t)p->next = new ListNode(t);
        return head.next;
    }
};

无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode） (leetcode-cn.com)

子串：连在一起的叫子串

子序列：可以不连在一起的叫子序列

定义目标串的起点和终点都在最初的位置，然后开始向后遍历终点，终点位置如果没有出现在哈希表里，就将当前位置的字符作为key，value为end+1放到哈希表中，每次更新最长的距离为num = max(num,end-start+1)，如果当前字符已经出现过了，就确定是在start之前还是之后出现的，更细一下start的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> mp;
        int num = 0,start,end;
        for(start = 0,end = 0;end<s.size();end++){
            if(mp[s[end]]){
                start = max(start,mp[s[end]]);
            }
            num = max(num,end-start+1);
            mp[s[end]] = end+1;
        }
        return num;
    }
};

寻找两个正序数的中位数

4. 寻找两个正序数组的中位数 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力做法，将两个vector统合成一个vector，然后使用sort进行排序，根据数据的奇偶判断中位数（O((N+M)log(N+M))O((N+M)log(N+M))）

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for(int i = 0;i<nums2.size();i++)
            nums1.push_back(nums2[i]);
        sort(nums1.begin(),nums1.end());
        if(nums1.size()%2)return nums1[nums1.size()/2];
        else return (nums1[nums1.size()/2]+nums1[nums1.size()/2-1])/2.0;
    }
};

解法2：递归

假设两个数组的长度为n,m，那么只要找到k=n+m2k=\frac{n+m}2位置的数字就可以了，递归的做法就是每次看一下k2<k\frac k2<k在两个数组中的数字，如果nums1[k/2]>nums2[k/2]，说明nums2中前k2\frac k2个数字都不是答案，可以舍弃。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size()+nums2.size();
        if(tot%2==0){
            int left= find(nums1,0,nums2,0,tot/2);
            int right = find(nums1,0,nums2,0,tot/2+1);
            return (left+right)/2.0;
        }else return find(nums1,0,nums2,0,tot/2+1);
    }
    
    // 找出两个正向数组中的中第(n+m)/2位置的数
    int find(vector<int> &nums1,int i,vector<int>&nums2,int j,int k){
        //如果nums1中的数比nums2中的数多，就反过来找
        if(nums1.size()-i>nums2.size()-j)return find(nums2,j,nums1,i,k);
        // 如果要找的位置是1，即头部位置
        if(k==1){
            // 根据第一个if，nums1的数量会比nums2少
            // 所以如果nums1.size()==i，说明，nums1中的数据都不符合
            // 直接返回nums2的头
            if(nums1.size()==i)return nums2[j];
            // 否则，nums1中还有数据，则返回nums1[i]和nums2[j]中最小的那个
            else return min(nums1[i],nums2[j]);
        }
        // 如果不是要找头，但是nums1已经遍历完了，就是nums2中从j开始向后的第k个元素了
        if(nums1.size()==i)return nums2[j+k-1];
        // 分别计算nums1，nums2舍弃前k/2个数据后对应的起始边界
        // 根据之前的if，nums1中数的个数可能会比i+k/2要小，因此取个最小值
        int si = min((int)nums1.size(),i+k/2),sj = j+k/2;
        // 如果nums1对应的数字大于nums2对应的数字
        if(nums1[si-1]>nums2[sj-1]) 
            // 舍弃nums2对应位置之前的数字
            return find(nums1,i,nums2,sj,k-(sj-j));
        else 
            // 反之舍弃nums1对应位置之前的数字
            return find(nums1,si,nums2,j,k-(si-i));
    }
};

最长回文子串

5. 最长回文子串 - 力扣（LeetCode） (leetcode-cn.com)

遍历每一个点，以他作为中心，然后向两边拓展，判断回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        // 以每一个起点为中心，向两边判断是否回文
        for(int i = 0;i<s.size();i++){
            // 回文序列为奇数的情况
            int l = i-1,r = i+1;
            // 满足回文就向外拓展
            while(l>=0&&r<s.size()&&s[l]==s[r])l--,r++;
            // 长度比目标大，就返回
            if(res.size()<r-l-1)res = s.substr(l+1,r-l-1);

            // 回文序列为偶数的情况
            l = i,r = i+1;
            while(l>=0&&r<s.size()&&s[l]==s[r])l--,r++;
            if(res.size()<r-l-1)res = s.substr(l+1,r-l-1);
        }
        return res;
    }
};

Z字形变换

6. Z 字形变换 - 力扣（LeetCode） (leetcode-cn.com)

解法一：我的解法

  1. 根据观察Z型结构坐标的数据，令当前位置为pos，当前行数为line，规定行数为num

  2. Z型的两个竖线之间的间隔cnt=2*(num-1)，

    比如字符串行为4时，0号为第一条竖线的第一个位置，那么第二条竖线要经过1,2,3,4,5后才能到达

    第二条竖线与第一条竖线的距离为6 = 2*(4-1)=cnt

  3. 当我们当前位置pos位于竖线上时，即(pos-line)%cnt==0时，并且他还不是最后一行line != num-1

    这时候他就要向下走到下一个竖线的对应位置，向下的计算公式为pos+(num-line-1)*2。(可以自己带数字进去试试)

    不然的话，就要向上走到达下一个位置，向上的计算公式为pos+2*line

  4. 遍历每一行，然后把对应的位置pos的位置添加到结果中就可以得到答案了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    // 向上走到下一个位置
    int up(int pos,int line){
        return pos+2*line;
    }
    // 向下走到下一个位置
    int down(int pos,int num,int line){
        return pos+(num-line-1)*2;
    }
    string convert(string s, int numRows)
    {
        // 如果只有一行就直接输出
        if(numRows==1)return s;
        string res;
        // 遍历Z形的每一行
        for (int i = 0; i < numRows; i++)
        {
            // 从Z型的第一列的第i个位置开始，计算下一列对应位置的间隔数
            int pos = i, cnt = (numRows - 1) * 2;
            // 在字符串长度内
            while (pos < s.size())
            {
                // 记录下来
                res += s[pos];
                // 判断是否在Z型的竖线上（竖线上的位置，除了最后一行都是向下走的）
                bool inlines = (pos - i) % cnt == 0;
                // 如果不在竖线上或者在竖线上且是最后一行就向上走，不然就向下走
                pos = !inlines || i == numRows - 1 ? up(pos, i) : down(pos, numRows, i);
            }
        }
        return res;
    }
};

解法2：别人的解法

  1. 第一行和最后一行都是公差为2n-2的等差数列
  2. 其他行在Z型的竖线上的数字都是公差为2n-2的等差数列，在Z型斜线上的数字也是公差为2n-2的数字
  3. Z型的第一列竖线与对应的行数匹配，在第i行中第一个斜线上的数a与改行第一个竖线上的数b有关系b = 2n-2-i
  4. 然后遍历每一行，根据不同的情况，分别计算每一行的等差数列即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string convert(string s, int numRows) {
        // 如果只有一行就直接输出
        if(numRows==1)return s;
        string res;
        int n = numRows;
        // 遍历每一行
        for(int i = 0 ;i<numRows;i++){
            // 第一行和最后一行
            if(i==0||i==numRows-1){
                // 计算等差数列
                for(int j = i;j<s.size();j+= 2*n-2)
                    res += s[j];
            }else{
                // 在其他行上，先求出第一个斜线上的数，然后计算两个等差数列
                for(int j = i,k = 2*n-2-i;j<s.size()||k<s.size();j+=2*n-2,k+=2*n-2){
                    if(j<s.size())res+=s[j];
                    if(k<s.size())res+=s[k];
                }
            }
        }
        return res;
    }
};

解法3：（建议忽略）暴力解法，直接模拟Z型排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    
    string convert(string s, int numRows) {
        if (1==numRows) return s;
        int cnt[1010][1010];
        // 1下0上
        int x=0,y=0,num=0,flag=1;
        for(int i = 0;i<s.size();i++){
            cnt[x][y] = i+1;
            num++;
            if(flag){
                if(num == numRows){ 
                    num = 1;
                    x -= 1,y+=1;
                    flag = 0;
                }else
                    x+=1;
            }else{
                if(num==numRows){
                    num = 1;
                    x+=1;
                    flag = 1;
                }else
                    x-=1,y+=1;
            }
        }
        string res;
        for(int i = 0;i<1010;i++)
            for(int j = 0;j<1010;j++)
                if(cnt[i][j])
                    res+=s[cnt[i][j]-1];
        return res;
    }
};

整数反转

7. 整数反转 - 力扣（LeetCode） (leetcode-cn.com)

有手就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while(x){
            // 因为题目不能用long long所以只能这样了
            // res大于0时
            // 10*res+x%10 > MAX -> res > (MAX-x%10)/10
            if(res>0&&res>(INT_MAX-x%10)/10)return 0;
            // res小于0时
            // 10*res+x%10 < MIN -> res > (MIN-x%10)/10
            if(res<0&&res<(INT_MIN-x%10)/10)return 0;
            res = res*10+(x%10);
            x/=10;
        }
        return res;
    }
};

字符串转换整数(atoi)

8. 字符串转换整数 (atoi) - 力扣（LeetCode） (leetcode-cn.com)

和上一题差不多的思路，就是要做一下字符串前处理而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int myAtoi(string s) {
        int pos = 0;
        while(pos<s.size()&&s[pos]==' ')pos++;
        if(pos==s.size())return 0;

        int flag = 1,res = 0;
        if(s[pos]=='-')flag = -1,pos++;
        else if(s[pos]=='+')pos++;

        while(pos<s.size()&&s[pos]>='0'&&s[pos]<='9'){
            int x = s[pos]-'0';
            if(flag==1&&res>(INT_MAX -x)/10)return INT_MAX;
            if(flag==-1&&-res<(INT_MIN+x)/10)return INT_MIN;
            if(-res*10-x==INT_MIN) return INT_MIN;
            res = res*10+x;
            pos++;
        }
        return res*flag;
    }
};

回文数

9. 回文数 - 力扣（LeetCode） (leetcode-cn.com)

解法1：我的方法：

想办法获取数字前后两头的数字，然后进行比较。获取方式见代码。

优化了一下，开了个数组存一下10的次方数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    long long pow10[11];

    bool isPalindrome(int x) {
        if(x<0)return false;
        pow10[0] = 1;
        for(int i = 1;i<11;i++)
            pow10[i] = pow10[i-1]*10;
        
        int cnt = 0,tmp = x;
        while(tmp){
            cnt++;
            tmp/=10;
        }
        int left = 0;
        for(int i = 1,j = cnt-1;i<=j;i++,j--){
            int l = x/pow10[j]-left,r = x%pow10[i]/pow10[i-1];
            if(l!=r)return false;
            left = (left+l)*10;
        }
        return true;
    }
};

解法2：转成字符串(虽然题中的进阶不能这么干)

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)return false;
        string s = to_string(x);
        return s == string(s.rbegin(),s.rend());
    }
};

解法3：直接从右向左取出每一位，然后把这一位和反转数变量乘10再相加，最后得到结果如果和目标相同就是回文数(是我笨比了)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)return false;
        int y = x;
        long long res = 0;
        while(x){
            res = res * 10 + x%10;
            x/=10; 
        }
        return res == y;
    }
};

正则表达式匹配

10. 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com)

image-20220220123910442

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool isMatch(string s, string p) {
        // 记录两者长度
        int n=s.size(),m=p.size();
        // dp从1开始
        s = " "+s,p=" "+p;
        // 创建dp数组
        vector<vector<bool>> f(n+1,vector<bool>(m+1));
        // 当没有字符的时候就是匹配的
        f[0][0] = true;
        // 开始遍历s和p
        for(int i = 0;i<=n;i++)
            for(int j = 1;j<=m;j++){
                // 如果他后一个是*，那这个字母与*时一起用的，不用考虑这个字母的情况
                if(j+1<=m&&p[j+1]=='*')continue;
                // 如果这个不是s的前i个不是空字符串，且p[j]不为*
                if(i&&p[j]!='*'){
                    // 首先s的前i-1要和p的前j-1匹配
                    // 然后s[i]要与p[j]相同或者p[j]为'.'
                    f[i][j] = f[i-1][j-1]&&(s[i]==p[j]||p[j]=='.');
                }else if(p[j]=='*'){
                    // 首先s的前i个要与p的前j-2个匹配，这时表示*对应0个字符
                    // 后面这个看题解吧，有转化过程
                    f[i][j] = f[i][j-2] || (i && f[i-1][j]&&(s[i]==p[j-1]||p[j-1]=='.'));
                }
            }
        return f[n][m];
    }
};

盛最多水的容器

11. 盛最多水的容器 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        // 从两头开始
        for(int i = 0,j = height.size()-1;i<j;){
            // 计算当前选中区域的面积
            res = max(res,min(height[i],height[j])*(j-i));
            // 如果左边比右边大，右边向左移，反之，左边向右移
            if(height[i]>height[j])j--;
            else i++;
        }
        return res;
    }
};

转换罗马数字

12. 整数转罗马数字 - 力扣（LeetCode） (leetcode-cn.com)

这题要找规律，如图，从这里看到，我们个位十位百位千位的数字都能用下述字母表示，暴力一点就可以将下表全部存起来，然后通过查字典的方式就可以获取所有组合比如1234 = 1000+200+30+4=M+CC+XXX+IV=MCCXXXIV

但是这里可能不需要存这么多，存圈出来的数据，然后遍历字典中的值，如果目标数字大于当前选中的符号数字，就直接减去这个数字，然后将符号添加到结果中，否则，就选择更小的符号数字。

image-20220220212006740

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string intToRoman(int num) {
        int nums[] = {1,4,5,9,10,40,50,90,100,400,500,900,1000};
        string roman[] = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
        int cnt = 12;
        string res;
        while(num){
            if(num>=nums[cnt]){
                res += roman[cnt];
                num-=nums[cnt];
            }else{
                cnt--;
            }
        }
        return res;
    }
};

最长公共前缀

14. 最长公共前缀 - 力扣（LeetCode） (leetcode-cn.com)

同时遍历每一个字符串某个位置的字符，如果相等就继续遍历，不等直接返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        char now;
        bool flag = true;
        int k=0;
        while(flag){
            if(k>=strs[0].size()){flag = false;break;}
            now = strs[0][k];
            for(int i = 1;i<strs.size();i++){
                if(k>=strs[i].size()||strs[i][k]!=now){
                    flag = false;
                    break;
                }
            }
            if(flag)k++;
        }
        return strs[0].substr(0,k);
    }
};

三数之和

15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        // 使用二分的方法需要保证规律性
        sort(nums.begin(),nums.end());
        // 三个指针，i,k分别选择两端,j选中间
        for(int i=0;i<nums.size();i++){
            // 如果i不是第一个，并且i和上一个相等了
            // 说明这个位置的情况在上一个已经遍历过了，所以跳过
            if(i&&nums[i]==nums[i-1])continue;
            // 选择j和k
            for(int j = i+1,k=nums.size()-1;j<k;j++){
                // 如果j和上一个一样，也跳过
                if(j>i+1&&nums[j]==nums[j-1])continue;‘
               // 如果两个不相交
               // 选择k的前一个，三数相加的结果大于等于0就左移k
                while(j<k-1&&nums[i]+nums[j]+nums[k-1]>=0)k--;
                // 如果选出来的i,j,k相加得0，就加入结果中。
                if(nums[i]+nums[j]+nums[k]==0){
                    res.push_back({nums[i],nums[j],nums[k]});
                }
            }
        }
        return res;
    }
};

end