LeetCode 刷题【16. 最接近的三数之和、17. 电话号码的字母组合】

16. 最接近的三数之和

自己做

解1：三重for循环

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int sum = nums[0] + nums[1] + nums[2];
        int len = nums.size();

        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                for(int k = j + 1; k < len; k++){
                    if(abs(nums[i] + nums[j] + nums[k] - target) < abs(sum - target))     //差值更小
                        sum = nums[i] + nums[j] + nums[k];
                }   
            }
        }

        return sum;

    }
};

解2：双指针

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        sort(nums.begin(),nums.end());                          //双指针前排序

        int len = nums.size();
        int sum = nums[0] + nums[1] + nums[len - 1];

        for(int i = 0; i < len; i++){
            int j = i + 1;
            int k = len - 1;

            //双指针
            while(j < k){              
                if(sum - target== 0)                                                    //找到差值最小，后面不用看了
                    return sum;
                    
                if(j < k && nums[i] + nums[j] + nums[k] - target > 0){                  //z大了
                    if(abs(nums[i] + nums[j] + nums[k] - target) < abs(sum - target))  //差值小了
                        sum = nums[i] + nums[j] + nums[k];
                    k--;
                }
                else if(j < k){                  //j小了
                    if(abs(nums[i] + nums[j] + nums[k] - target) < abs(sum - target))  //差值小了
                        sum = nums[i] + nums[j] + nums[k];
                    j++;
                }
            }
                
        }

        return sum;

    }
};

17. 电话号码的字母组合

自己做

解：找规律，拼组合

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        int len = digits.size();                    //总共有多少数字

        if(len == 0)                                //空字符串单独处理
            return vector<string>();

        //组合列表
        map<int, string> m;
        m.insert(make_pair(2, "abc"));
        m.insert(make_pair(3, "def"));
        m.insert(make_pair(4, "ghi"));
        m.insert(make_pair(5, "jkl"));
        m.insert(make_pair(6, "mno"));
        m.insert(make_pair(7, "pqrs"));
        m.insert(make_pair(8, "tuv"));
        m.insert(make_pair(9, "wxyz"));

        int combine = 1;

        //统计组合数
        for (int i = 0; i < len; i++) {
            combine *= m[digits[i] - 48].size();
        }

        vector<string> res(combine);

        int repeat = combine;                                           //每个字母的重复次数(连续重复)

        for (int i = 0; i < len; i++) {                               //遍历所有数字
            int number = digits[i] - 48;                            //数字
            int numchar_len = m[number].size();                     //该数字对应的字母数量
            repeat /= numchar_len;                                  //一轮字母输出中每个字母的重复次数

            //逐步赋值
            int begin = 0;                                          //目前输出的位置
            while(begin < combine)
                for(int get_char = 0; get_char < numchar_len; get_char++)      //一轮字母输出
                    for(int r = 0; r < repeat; r++){                            //重复次数
                        res[begin] += m[number][get_char];
                        begin++;                                                //更新位置
                    }
        }

        return res;
    }
};