tx精选50题

题单链接

1~10

2. 两数相加

链表版的高精

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 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* ans=new ListNode(0);
        ListNode* ha=ans;
        int c=0;
        while(l1&&l2)
        {
            ListNode* a=new ListNode((l1->val+l2->val+c)%10);
            c=(l1->val+l2->val+c)/10;
            l1=l1->next;
            l2=l2->next;
            ha->next=a;
            ha=ha->next;
        }
        while(l1)
        {
            ListNode* a=new ListNode((l1->val+c)%10);
            c=(l1->val+c)/10;
            l1=l1->next;
            ha->next=a;
            ha=ha->next;
        }

        while(l2)
        {
            ListNode* a=new ListNode((l2->val+c)%10);
            c=(l2->val+c)/10;
            l2=l2->next;
            ha->next=a;
            ha=ha->next;
        }
        //注意这里会有进位
        if(c)
        {
            ListNode* a=new ListNode(c);
            ha->next=a;
        }
        return ans->next;


    }
};

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
26
27
28
29
30
31
32
33
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int l1=nums1.size(),l2=nums2.size();
        int x=l1+l2;
        int a=0,b=0;
        double ans=0;
        int t=x/2;
        while(t--)
        {
            if(a<l1&&b<l2)
            {
                if(nums1[a]<nums2[b]) ans=nums1[a],a++;
                else ans=nums2[b],b++;
            }
            else if(a<l1) ans=nums1[a],a++;
            else if(b<l2) ans=nums2[b],b++;
        }

        double ans1=ans;
        if(a<l1&&b<l2)
        {
            if(nums1[a]<nums2[b]) ans=nums1[a],a++;
            else ans=nums2[b],b++;
        }
        else if(a<l1) ans=nums1[a],a++;
        else if(b<l2) ans=nums2[b],b++;

        if(x&1) return ans;
        else return (ans+ans1)/2;

    }
};

5. 最长回文子串

暴力

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
class Solution {
    string ss;
    bool ch(int l,int r)
    {
        while(l<r)
        {
            if(ss[l]!=ss[r]) return 0;
            l++;
            r--;
        }
        return 1;
    }
public:
    string longestPalindrome(string s) {
        ss=s;
        int l=s.size();
        for(int len=l;len>0;len--)
        {
            for(int i=0;i+len-1<l;i++)
            {
                int j=i+len-1;
                if(ch(i,j)) 
                return s.substr(i,len);
            }
        }
        return "";
    }
};

另一种暴力

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 {
    string ss;
    int ll;
    int ch(int l,int r)
    {
        if(l<0) return 0;
        while(l>=0&&r<ll)
        {
            if(ss[l]!=ss[r]) return r-l-1;
            l--;
            r++;
        }
        return r-l-1;
    }
public:
    string longestPalindrome(string s) {
        ss=s;
        int l=s.size();
        ll=l;

        string ans=s.substr(0,1);

        for(int i=0;i+1<l;i++)
        {
            int a=max(ch(i-1,i+1),ch(i,i+1));
            if(a>ans.size())
            ans=s.substr(i-(a+1)/2+1,a);

        }



        return ans;
    }
};

dp

注意由于转换中用到了dp[i-1][j+1],所以要按列遍历

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:
    string longestPalindrome(string s) {
        bool dp[1005][1005]={0};
        int l=s.size();

        int len=1;
        int st=0;


        for(int j=0;j<l;j++)
        {
            for(int i=0;i<j;i++)
            {
                if(s[i]==s[j])
                {
                    if(j-i<3) dp[i][j]=1; 
                    else if(dp[i+1][j-1]) dp[i][j]=1;
                    if(dp[i][j]&&j-i+1>len)
                    {
                        len=j-i+1;
                        st=i;
                    }
                }
            }
        }
        return s.substr(st,len);

    }
};

但不知道为什么跑出来居然比一二都丑

马拉车快乐算法

还没看先空着

7. 整数反转

这题太ex了

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
class Solution {
public:
    int reverse(int x) {
        if(x==0) return 0;
        if(x==INT_MIN) return 0;


        int ans=0;
        int f=1;
        if(x<0) x=-x,f=-1;
        while(x%10==0) x/=10;
        if(x<1e9)
        {
            while(x)
            {
                ans=ans*10+x%10;
                x/=10;
            }
            return ans*f;
        }
       string a=to_string(INT_MAX);
       string b=to_string(x);
       for(int i=0;i<5;i++)
       swap(b[i],b[9-i]);
        if(b>a) return 0;
        for(int i=0;i<10;i++)
        ans=ans*10+(b[i]-'0');
        return ans*f;


    }
};

看了下题解，大概就是先反转前9位，在判断第十位

好有道理的样子

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 reverse(int x) {
        if(x==0) return 0;
        if(x==INT_MIN) return 0;


        int ans=0;
        int f=1;
        if(x<0) x=-x,f=-1;
        while(x%10==0) x/=10;
        if(x<1e9)
        {
            while(x)
            {
                ans=ans*10+x%10;
                x/=10;
            }
            return ans*f;
        }
       for(int i=0;i<9;i++)
       {
           ans=ans*10+x%10;
           x/=10;
       }
        if(ans<=INT_MAX/10&&x<=7) 
        {
            ans=ans*10+x;
            return ans*f;
        } 
        return 0;

    }
};

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

嘻，大模拟，面向数据编程

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    int myAtoi(string s) {
        int l=s.size();
        int ans=0;
        int i=0;
        while(i<l&&s[i]==' ') i++;
        int f=1;
        if(s[i]=='-') f=-1,i++;
        else if(s[i]=='+') i++;

        while(i<l&&s[i]=='0') i++;
        int cnt=9;
        while(cnt--&&i<l&&s[i]>='0'&&s[i]<='9')
        {
            ans=ans*10+(s[i]-'0');
            i++;
        }
        if(cnt>=0||i==l) return ans*f;
        if(!(s[i]>='0'&&s[i]<='9')) return ans*f;
        i++;


        if(i<l&&s[i]>='0'&&s[i]<='9')
        {
            if(f==1) return INT_MAX;
            return INT_MIN;
        }
        i--;
        if(i<l&&s[i]>='0'&&s[i]<='9')
        {
            if(ans>INT_MAX/10)
            {
                if(f==1) return INT_MAX;
                return INT_MIN;
            }
            if(ans<INT_MAX/10)
            {
                ans=ans*10+(s[i]-'0');
                return ans*f;
            }
            if(f==1)
            {
                if(s[i]<='7')
                ans=ans*10+(s[i]-'0');
                else ans=INT_MAX;
            }
            else
            {
                if(s[i]<='8')
                ans=ans*-10-(s[i]-'0');
                else ans=INT_MIN;
            }
            return ans;
        } 
    return ans*f;
    }
};

另一种思路

看起来比1好理解一点但没1快

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:
    int myAtoi(string s) {
        int l=s.size();
        int ans=0;
        int i=0;
        while(i<l&&s[i]==' ') i++;
        int f=1;
        if(s[i]=='-') f=-1,i++;
        else if(s[i]=='+') i++;

        while(i<l&&s[i]=='0') i++;
        
        string a="";
        while(i<l&&s[i]>='0'&&s[i]<='9') a+=s[i],i++;
        

        if(a.size()>10) 
        if(f==1) return INT_MAX;
        else return INT_MIN;


        if(a.size()<10)
        {
            for(int i=0;i<a.size();i++)
            ans=ans*10+(a[i]-'0');
            return ans*f;
        }

        string b=to_string(INT_MAX);
        if(a>b)
        if(f==1) return INT_MAX;
        else return INT_MIN;
        for(int i=0;i<a.size();i++)
            ans=ans*10+(a[i]-'0');
        return ans*f;
    }
};

题解居然是自动机

嘤当初队里没人学字符串

滚去学字符串

9. 回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return 0;
        string s=to_string(x);
        int r=s.size()-1;
        int l=0;
        while(l<r)
        {
            if(s[l]!=s[r]) return 0;
            l++;
            r--;
        }
        return 1;
    }
};