题目详情
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
查找有没相同的值,但是索引(i j不同)不同,且他们的索引距离小于k,有返回true
Example:
Input: matrix = [0, 1, 0, 1, 12], k = 3
Output: true
思路
- 跟数组去重一样,利用键值对,值存储索引值,键值存储值
具体代码
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
let obj = {}
for(let i = 0, len = nums.length; i < len; i++) {
if(obj[nums[i]] !== undefined) {
if(Math.abs(obj[nums[i]] - i) <= k) {
return true
}
obj[nums[i]] = i
} else {
obj[nums[i]] = i
}
}
return false
};
Array - 643. Maximum Average Subarray I
题目详情
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
在数组中找到长度为k的最大值除以k的值。其实就是找到长度为>k的最大值
Example:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
思路
- 先求前 k - 1长度数组的和
- 然后遍历数组,从k-1开始加,之后就加一个尾减个头,这样保证长度不变。
具体代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function(nums, k) {
if(nums.length === 1) return nums[0]
let currSum = 0
for(let i = 0; i < k - 1; i++) {
currSum += nums[i]
}
if(nums.length === k) return (currSum + nums[k - 1]) / k
let maxSum = -Infinity
for(let i = k - 1, len = nums.length; i < len; i++) {
currSum += nums[i]
if(i - k > -1) {
currSum -= nums[i - k]
}
maxSum = Math.max(currSum, maxSum)
}
return maxSum / 1.0 / k
};
Array - 605. Can Place Flowers
题目详情
Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
这道题给了我们一个01数组,其中1表示已经放了花,0表示可以放花的位置,但是有个限制条件是不能有相邻的花。
Example:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True
思路
- 遍历数组,在为0的元素,判断该元素前后是否为0
- 如果是,判断该位置前后是不是有花
- 没有花就在该位置种花,种花次数和n相等
具体代码
/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function(arr, n) {
let count = 0
for(let i = 0, len = arr.length; i < len && count < n; i++) {
if(arr[i] === 0) {
let prev = i === 0 ? 0 : arr[i - 1]
let next = i === len - 1 ? 0 : arr[i + 1]
if(prev === 0 && next === 0) {
arr[i] = 1
count ++
}
}
}
console.log(count)
return count === n
};