乐趣区

关于leetcode:LeetCode-Hot1001620

16. 最靠近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最靠近。返回这三个数的和。
假设每组输出只存在恰好一个解。

示例 1:
输出:nums = [-1,2,1,-4], target = 1
输入:2
解释:与 target 最靠近的和是 2 (-1 + 2 + 1 = 2)。

示例 2:
输出:nums = [0,0,0], target = 1
输入:0
 
提醒:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

My Answer:


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
/**
 * 应用三个指针指向这三个数。* 将数组排序后能够更快地找到指标三个数。* 第一个指针遍历一遍,下标为 i
 * 第二个指针 j 初始值为 i +1, 可右移(++)* 第三个指针 k 初始值为 n, 可左移(--)* 当三个数的和小于目标值时,j++
 * 当三个数的和大于目标值时,k--
 * 当三个数的和等于目标值时,返回
 */
var threeSumClosest = function(nums, target) {
  const n = nums.length;
  const ascArr = nums.sort((a,b)=> a-b);
  console.log(ascArr);
  let minDist = Math.abs(ascArr[0]+ascArr[1]+ascArr[2] - target);
  let res = ascArr[0]+ascArr[1]+ascArr[2];

  // i 记录第一个数地位
  // j 记录第二个数地位
  // k 记录第三个数地位
  for (let i = 0; i < n-2; i++) {
    let j = i+1;
    let k = n-1; 
    while(j<k) {
      // 三数之和与目标值更靠近的话,替换
      if(Math.abs(ascArr[i]+ascArr[j]+ascArr[k] - target) < minDist){res = ascArr[i]+ascArr[j]+ascArr[k];
        minDist = Math.abs(ascArr[i]+ascArr[j]+ascArr[k] - target);
      }
      if(ascArr[i]+ascArr[j]+ascArr[k] < target) {j++;} else if(ascArr[i]+ascArr[j]+ascArr[k] > target){k--;} else {return target;}
    }
  }
  return res;
};

17. 电话号码的字母组合

给定一个仅蕴含数字 2-9 的字符串,返回所有它能示意的字母组合。答案能够按 任意程序 返回。
给出数字到字母的映射如下(与电话按键雷同)。留神 1 不对应任何字母。

示例 1:
输出:digits = “23”
输入:[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

示例 2:
输出:digits = “”
输入:[]

示例 3:
输出:digits = “2”
输入:[“a”,”b”,”c”]
 
提醒:
0 <= digits.length <= 4
digits[i] 是范畴 [‘2’, ‘9’] 的一个数字。

My Answer:

/**
 * @param {string} digits
 * @return {string[]}
 */
/**
 * 应用递归回溯的办法,遍历每一个数字对应的字母数组
 */
var letterCombinations = function(digits) {
  const rel = {'2': ['a','b','c'],
    '3': ['d','e','f'],
    '4': ['g','h','i'],
    '5': ['j','k','l'],
    '6': ['m','n','o'],
    '7': ['p','q','r', 's'],
    '8': ['t','u','v'],
    '9': ['w','x','y', 'z'],
  }
  const res = [];
  let str = '';
  const arr = digits.split('');

  // 递归回溯办法
  function combination(digits, n){
    // 加到最初一位,放入数组,回去或退出
    if(n===digits.length) {res.push(str);
        return;
    }
    for(let i= 0; i<rel[digits[n]].length; i++){str+=rel[digits[n]][i];
        combination(digits,n+1);
        str = str.substr(0,str.length-1);
    }
  }

  if(arr.length){combination(arr,0);
  }
  return res;
};
退出移动版