LeetCode - 8 - (三数之和、Z字形变换、两数之和＜链表＞、盛最多水的容器、电话号码的字母组合)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        set<vector<int>> res; //去重
        int n = nums.size();
        for(int i = 0; i < n; i ++){
            int l = i+1, r = n-1; //双指针
            while(l<r){
                if(nums[i]+nums[l]+nums[r]==0){
                    res.insert({nums[i], nums[l], nums[r]});
                    l ++;
                    r --;
                }
                else if(nums[i]+nums[l]+nums[r]<0) l ++;
                else r --;
            }
        }
        vector<vector<int>> ans;
        for( auto x:res){
            ans.push_back(x);
        }
        return ans;
    }
};

class Solution {
public:
    string convert(string s, int numRows) {
        int n = numRows, sz = s.size();
        if(n==1||n>=sz) return s;
        vector<string> res(n);
        for(int i = 0, x = 0, t = n*2-2; i < sz; i ++){
            res[x] += s[i];
            i%t<n-1 ? x++ : x--;
        }
        string ans;
        for(auto x:res) ans += x;
        return ans;
    }
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = nullptr, *ed = nullptr;
        int sum = 0;
        while(l1||l2){
            int x = l1?l1->val:0;
            int y = l2?l2->val:0;
            int z = x+y+sum;
            if(!head) head = ed = new ListNode(z%10);
            else{
                ed->next = new ListNode(z%10);
                ed = ed->next;
            }
            sum = z/10;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        }
        if(sum>0){
            ed->next = new ListNode(sum);
        }
        return head;
    }
};

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

class Solution {
public:
    string tmp;
    vector<string> ans;
    vector<string> res = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void dfs(int pos, string digits){
        if(digits.size()==pos){
            ans.push_back(tmp);
            return;
        }
        int x = digits[pos]-'0';
        for(int i = 0; i < res[x].size(); i ++){
            tmp += res[x][i];
            dfs(pos+1, digits);
            tmp.erase(tmp.size()-1, 1);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return ans;
        dfs(0, digits);
        return ans;
    }
};