leetcode 11-15题解 - dblank

leetcode 11-15题解

代码在我的github同步

11. Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

__Note__: You may not slant the container and n is at least 2.

题意:

给定n个非负整数a1,a2,...,an,其中每个代表一个点坐标(i,ai)。 n个垂直线段例如线段的两个端点在(i,ai)和(i,0)。 找到两个线段,与x轴形成一个容器,使其包含最多的水。

思路:

如果直接n*n暴力枚举的话肯定会超时的,我们开两个指针,一个l = 0, 一个r = nums.size() - 1.两边开始枚举,有这样的优化,如果一个l后面或者r前面比它大那么这个结果不会比原来l和r更优.所以对一对l和r来说,只有让小的前进才可能更优.

时间复杂度O(n).

代码:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0, l = 0, r = height.size()-1;
        while(l<r)
        {
            ans = max(ans, min(height[l] , height[r]) *(r - l));
            if(height[l] < height[r])
                l++;
            else r--;
        }
        return ans;
    }
};

12. Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

题意:

将阿拉伯数字转化为罗马数字

转换规则

思路:

先把每位上的表打出来,然后分解数位查表就可以了.

代码:


class Solution
{
public:
    string intToRoman(int num)
    {
        string roman[4][10] = {
            {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
            {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
            {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
            {"", "M", "MM", "MMM"}
        };
        string ans = "";
        int cnt = 3, div = 1000;
        while(cnt>=0)
        {
            ans.append(roman[cnt][num/div%10]);
            div /= 10;
            cnt--;
        }
        return ans;
    }
};

13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

题意:

将罗马数字转化为阿拉伯数字

转换规则

思路:

把对应的罗马数字符的权值建一个表,遍历字符串的时候如果小于后面的权值则说明进行了左减.

代码:

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char , int> umap
        {
            {'I', 1}, {'V', 5},
            {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500},
            {'M', 1000}
        };
        int ans = 0;
        for(int  i = 0; i<s.size(); i++)
        {
            if(i < s.size() - 1 && umap[ s[i] ] < umap[ s[i+1] ])
            {
                ans += umap[ s[i+1] ] - umap[ s[i] ];
                i++;
            }
            else ans += umap[ s[i] ];
        }
        return ans;
    }
};

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

题意:

找到n个字符串的最长公共前缀.

思路:

暴力枚举第一个字符串的前缀然后暴力判断就可以.

代码:


class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans ="";
        if(strs.size()<1)
        return "";
        for(int i = 0; i<strs[0].size(); i++)
        {
            if(check(i, strs))
                ans.push_back(strs[0][i]);
            else break;
        }
        return ans;
    }
    bool check(int id, vector<string>& strs)
    {
        for(int i = 1; i<strs.size(); i++)
        {
            if(id > strs[i].size() || strs[i][id] != strs[0][id])
                return false;
        }
        return true;
    }
};

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题意:

找到所有的不重复的三元组的和为target.

思路:

1.Two Sum一样,我们先枚举一个元素然后用找二元组的方法找target - nums[i].

代码:

class Solution
{
public:
    vector< vector<int> > ans;
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        if(nums.size()<3) return ans;
        for(int i = 0; i<nums.size(); i++)
        {
            if(i>0 && nums[i] == nums[i-1])
                continue;
            twoSum(i+1, nums.size()-1, i, nums);
        }
        return ans;
    }
    void twoSum(int l, int r, int target, vector<int>& nums)
    {
        vector<int> tmp;
        while(l<r)
        {
            if(nums[l] + nums[r] == -nums[target])
            {
                tmp.clear();
                tmp.push_back(nums[target]);
                tmp.push_back(nums[l]);
                tmp.push_back(nums[r]);
                ans.push_back(tmp);
                while(l<r && nums[l+1] == nums[l])
                    l++;
                while(l<r && nums[r-1] == nums[r])
                    r--;
                l++;
                r--;
            }
            else if(nums[l] + nums[r] < -nums[target])
                l++;
            else r--;
        }
    }
};

相关文章

发表新评论