leetcode · 每日一题

2021.1.11

189. 旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

进阶:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
 

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k, res = []) {
    // res = nums.splice(nums.length-k,k)
    // nums = res.concat(nums)
    // return nums
    res = nums.slice()
    if(k > nums.length){
        k = k % nums.length
    }
    for(let i = 0; i< res.length; i++){
        if(i < res.length - k){
            nums[i + k] = res[i]
        } else {
            nums[i + k - res.length] = res[i]
        }
    }
    return res
};

2020.1.12

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
当前最优解:
相比较暴力枚举,通过Map对象来哈希target-nums[i]可以将时间复杂度从
o(n^2) 降至 o(n). 具体的实现细节如下:
创建一个map对象
遍历nums数组,map.get(target-nums[i])如果是 undefined 说明map对象中尚未缓存相对应对应和数的坐标,
继续遍历,直到对应的和数被cached到map对象中。
最终返回对应的坐标
var twoSum = function(nums, target) {
    const map = new Map()
    for(let i = 0; i < nums.length; i++){
        if(map.get(target - nums[i]) !== undefined){
            return [i, map.get(target - nums[i])]
        }
        map.set(nums[i], i)
    }
};
我的解决方案:
var twoSum = function(nums, target) {
    let arr = []
    for (let i = 0; i < nums.length; i++){
        let _nums = nums.slice();
        _nums.splice(i,1)
        for (let j = 0; j < _nums.length; j++){
            if(nums[i] + _nums[j] === target){
                arr = [j,i];
            }
        }
    }
    return arr
};
改良:
var twoSum = function (nums, target) {
  for (let i = 0; i <= nums.length - 1; i++) {
    for (let j = 1; j <= nums.length; j++) {
      if (nums[i] + nums[j] === target && i !== j) {
        return [i, j]
      }
    }
  }
};

暂停一下,需要补充理论知识再继续前行。

测试

    还没有任何评论,你来说两句吧

  • 降雪
  • 引力
%d 博主赞过: