leetcode轮回计划20180905

1. 11 Container With Most Water
   int maxArea(vector<int>& height) {}
   题意：每个数字是一个隔板高度，数字的下标是隔板的位置，求哪两块隔板之间能够盛放最多的水。
   思路：双指针法，哪个指针低哪个移动。
2. 12 Integer to Roman
   string intToRoman(int num) {}
   将数字转化为罗马数字
   思路：对于这种情况不多的，可以将所有情况全部罗列出来。
3. 13 Roman to Integer
4. 14 Longest Common Prefix
   string longestCommonPrefix(vector<string>& strs) {}
   思路：strs[0].find(tmp)
   其实使用最朴素的想法就可以了
5. 15 3Sum（3）
   vector<vector<int>> threeSum(vector<int>& nums) {}
   题意：找到所有和恰好等于零的三元组
   思路：双指针法。注意可能存在相等的数字。
   教训：这个题目看似简单，其中有许多耐人寻味的地方。双指针发的应用方式也是需要记住的东西。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int size = nums.size();
        for(int i = 0;i < size;){
            int begin = i + 1, end = size - 1;
            while(begin < end){
                if(nums[begin] + nums[end] + nums[i] == 0){
                    ret.push_back({nums[begin++], nums[i], nums[end--]});
                    while(begin < end && nums[begin] == nums[begin - 1]) begin ++;
                    while(begin < end && nums[end] == nums[end + 1]) end --;
                }else if(nums[begin] + nums[end] + nums[i] < 0){
                    begin ++;
                    while(begin < end && nums[begin] == nums[begin - 1]) begin ++;
                }else{
                    end --;
                    while(begin < end && nums[end] == nums[end + 1]) end --;
                }
            }
            ++ i;
            while(i < size && nums[i - 1] == nums[i]) ++i;
        }
        return ret;
    }
};

6. 16 3Sum Closest
   int threeSumClosest(vector<int>& nums, int target) {}
   题意：和最接近target的三元组
   思路：双指针法。不用考虑相等的数字。
7. 17 Letter Combinations of a Phone Number
   vector<string> letterCombinations(string digits) {}
   题意：给出数字组合，返回这个数字组合可能想要表达的字母组合（手机按键）
   思路：回溯
8. 18 4Sum
   vector<vector<int>> fourSum(vector<int>& nums, int target) {}
   思路：四指针法（将两个指针固定的双指针法）
9. 19 Remove Nth Node From End of List
   ListNode* removeNthFromEnd(ListNode* head, int n) {}
   题意：删除倒数第n个节点
   思路：双指针法
10. 20 Valid Parentheses
    bool isValid(string s) {}
    思路：左括号压栈右括号，右括号出栈来比较