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;}
};
