LeetCode11-20

发表于 | 更新于: | 分类于 ， | | 阅读次数:
字数统计: 1.9k 字 | 阅读时长 ≈ 9 分钟

11、盛最多水的容器

双指针，算法中一个很重要的技巧，之前的三数求和就用到了双指针的技巧。

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxArea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxArea，并将指向较短线段的指针向较长线段那端移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int frontPoint = 0, endPoint = height.size()-1;
        while( frontPoint<endPoint ){
            maxArea = max( maxArea, (endPoint-frontPoint)*min(height[frontPoint], height[endPoint]) );
            if( height[frontPoint]<height[endPoint] )
                frontPoint++;
            else
                endPoint--;
        }
        return maxArea;
    }
};

12、整数转罗马数字

水题一个，模拟一下即可。

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:
    string intToRoman(int num) {
        vector< pair<int,string> > mp;
        mp.push_back( make_pair(1000,"M") );
        mp.push_back( make_pair(900,"CM") );
        mp.push_back( make_pair(500,"D") );
        mp.push_back( make_pair(400,"CD") );
        mp.push_back( make_pair(100,"C") );
        mp.push_back( make_pair(90,"XC") );
        mp.push_back( make_pair(50,"L") );
        mp.push_back( make_pair(40,"XL") );
        mp.push_back( make_pair(10,"X") );
        mp.push_back( make_pair(9,"IX") );
        mp.push_back( make_pair(5,"V") );
        mp.push_back( make_pair(4,"IV") );
        mp.push_back( make_pair(1,"I") );
        string ans = "";
        for( vector< pair<int,string> >:: iterator it = mp.begin(); it!=mp.end(); it++ ){
            while( num>=(*it).first ){
                ans += (*it).second;
                num -= (*it).first;
            }
        }
        return ans;
    }
};

13、罗马数字转整数

水题，直接模拟

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 romanToInt(string s) {
        map<char, int> mp;
        mp['I'] = 1, mp['V'] = 5, mp['X'] = 10, mp['L'] = 50;
        mp['C'] = 100, mp['D'] = 500, mp['M'] = 1000;
        vector<int> nums;
        for( int i=0; i<s.length(); i++ )
            nums.push_back( mp[s[i]] );
        nums.push_back(0);
        int ans = 0;
        for( int i=0; i<nums.size()-1; i++ ){
            if( nums[i]<nums[i+1] ){
                ans += nums[i+1]-nums[i];
                i++;
            }
            else
                ans += nums[i];
        }
        return ans;
    }
};

14、最长公共前缀

没啥好方案，直接暴力即可。暴力的方式有多种，一种像这里直接每次一个字符一个字符的得出 ans ，也可以挨个字符串直接与 ans（初值为字符串strs[0]） 比较，逐渐缩小 ans 的长度，直到最后得出结果。

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:
    string longestCommonPrefix(vector<string>& strs) {
        if( strs.size()==0 )
            return "";
        int lens = 0, i = 0;
        string ans = "";
        char ch;
        while(1){
            if( strs[0].length() > lens )
                ch = strs[0][lens];
            else
                return ans;
            for( i=1; i<strs.size(); i++ ){
                if( strs[i][lens]!=ch )
                    return ans;
            }
            ans += ch;
            lens++;
        }
    }
};

15、三数之和

三数之和其实和前面的两数之和原理一样，都是使用的双指针。这里的三数，其实可以直接固定一数，然后调用前面写的两数之和的代码。唯一的一点 trick 可能就是在去重上。

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector< vector<int> > ans;
        if( nums.size()<3 )
            return ans;
        //对 nums 进行排序并去重(此处去重不合适)
        sort( nums.begin(), nums.end() );
        //vector<int>:: iterator it = unique( nums.begin(), nums.end() );
        //nums.erase( it, nums.end() );
        for( int i=0; i<nums.size()-2; i++ ){
            if( i>0 && nums[i-1]==nums[i] )
                continue;
            findTwoSum( nums, i+1, nums.size()-1, i, ans );
        }
        return ans;
    }
    void findTwoSum( vector<int>& nums, int s, int e, int target, vector< vector<int> >& ans ){
        vector<int> step_ans;
        while( s<e ){
            if( nums[s]+nums[e] == -nums[target] ){
                step_ans.clear();
                step_ans.push_back(nums[target]);
                step_ans.push_back(nums[s]);
                step_ans.push_back(nums[e]);
                ans.push_back(step_ans);
                s++;
                e--;
                while( s < e && nums[s]==nums[s-1] )
                    s++;
                while( e > s && nums[e]==nums[e+1] )
                    e--;
            }
            else if( nums[s]+nums[e] > -nums[target] )
                e--;
            else
                s++;
        }
    }
};

16、最接近的三数之和

和三数之和的原理一样，排序后使用双指针遍历找最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort( nums.begin(), nums.end() );
        int nearest = nums[0]+nums[1]+nums[2], tmpSum;
        for( int i=0; i<nums.size()-2; i++ ){
            int f = i+1, e = nums.size()-1;
            while( f<e ){
                tmpSum = nums[f] + nums[e] + nums[i];
                nearest = abs(target-nearest)>abs(target-tmpSum)? tmpSum:nearest;
                if( tmpSum==target )
                    return target;
                else if( tmpSum > target )
                    e--;
                else
                    f++;
            }
        }
        return nearest;
    }
};

17、电话号码的字母组合

一行深搜代码解决，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
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> mp,ans;
        string cur_ans;
        mp.push_back("");
        mp.push_back("");
        mp.push_back("abc");
        mp.push_back("def");
        mp.push_back("ghi");
        mp.push_back("jkl");
        mp.push_back("mno");
        mp.push_back("pqrs");
        mp.push_back("tuv");
        mp.push_back("wxyz");
        if( digits.length() )
            digitsToString( mp, digits, ans, cur_ans );
        return ans;
    }
    void digitsToString( vector<string>& mp, string digits, vector<string>& ans, string cur_ans ){
        if( digits.length()==0 ){
            ans.push_back( cur_ans );
            return ;
        }
        for( int i=0; i<mp[digits[0]-'0'].length(); i++ ){
            digitsToString( mp, digits.substr(1), ans, cur_ans+mp[digits[0]-'0'][i] );
        }
    }
};

18、四数之和

还是双指针操作（发现一个规律就是，前面这些和双指针操作相关的题目，一个典型的特点就是数组要先排个序），算法复杂度 $ O(n^3) $ ，其实有很多种解题方式。

第一种：双指针操作，先固定两个位置，然后 $ O(n) $ 的时间复杂度遍历剩下的元素，找解的过程中就去除可能存在的重复解，体现在代码中就是一片形式相同的while循环。

第二种：还是双指针操作，在求解的过程中，我不管解是否存在重复，一一加到ans里面，最后再进行一个去重处理。优点是编码简单，缺点是空间复杂度高，最坏情况下为$n^4$的空间复杂度（nums全为0，target也为0）。

第三种：以空间换时间，利用$ O(n^2) $的空间先求出两个数字的和，然后变成 两数之和 问题。

第四种：使用深搜操作，理论上来讲，此种方法可以求 m 数之和，时间复杂度为 $ O(n^{m-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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector< vector<int> > ans;
        if( nums.size()<4 )
            return ans;
        sort( nums.begin(), nums.end() );
        for( int i=0; i<nums.size()-3; i++ ){
            for( int j=i+1; j<nums.size()-2; j++ ){
                int f = j+1, e = nums.size()-1;
                while( f<e ){
                    int sum = nums[i]+nums[j]+nums[f]+nums[e];
                    if( sum==target ){
                        vector<int> tmp_ans;
                        tmp_ans.push_back(nums[i]);
                        tmp_ans.push_back(nums[j]);
                        tmp_ans.push_back(nums[f]);
                        tmp_ans.push_back(nums[e]);
                        ans.push_back( tmp_ans );
                        f++;
                        while( f<e && nums[f-1]==nums[f] ){
                            f++;
                        }
                        e--;
                        while( e>f && nums[e+1]==nums[e] ){
                            e--;
                        }
                    }
                    else if( sum>target ){
                        e--;
                        while( e>f && nums[e+1]==nums[e] ){
                            e--;
                        }
                    }
                    else{
                        f++;
                        while( f<e && nums[f-1]==nums[f] ){
                            f++;
                        }
                    }
                }
                while( j+1<nums.size()-2 && nums[j+1]==nums[j] ){
                    j++;
                }
            }
            while( i+1<nums.size()-3 && nums[i+1]==nums[i] ){
                i++;
            }
        }
        return ans;
    }
};

19、删除链表的倒数第N个节点

一遍遍历即可，其实也是双指针的思想.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
        dummy->next = head;
        ListNode *f = dummy, *e = dummy;
        for( int i=1; i<=n; i++ )
            e = e->next;
        while( e->next ){
            f = f->next;
            e = e->next;
        }
        f->next = f->next->next;
        return dummy->next;
    }
};

20、有效的括号

水题，使用栈匹配一下即可，遇到左括号进栈，遇见右括号出栈，最后判断栈是否为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isValid(string s) {
        stack<char> ans;
        ans.push('#'); //加栈底后期就不用判断空不空了
        for( int i=0; i<s.length(); i++ ){
            if( s[i]=='(' || s[i]=='[' || s[i]=='{' )
                ans.push(s[i]);
            else{
                if( (s[i]==')'&&ans.top()!='(') || (s[i]==']'&&ans.top()!='[') || (s[i]=='}'&&ans.top()!='{') )
                    return false;
                else
                    ans.pop();
            }
        }
        return ans.top()=='#';
    }
};
-------------本文结束感谢您的阅读-------------
您的鼓励就是我创作的动力，求打赏买面包~~
0%