概述
1.找到K个最接近的元素
题目：
给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
思路：按照与x的距离排序，然后取前k个。也可以用二分法找到最接近x的数，然后双指针往两边扩张，不过写起来麻烦
时间复杂度O(nlogn)，空间复杂度O(nlogn)
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function(arr, k, x) {
return arr
.sort((a, b) => {
if (Math.abs(a - x) === Math.abs(b - x)) {
return a - b;
} else {
return Math.abs(a - x) - Math.abs(b - x);
}
})
.slice(0, k)
.sort((a, b) => a - b);
};2.分割数组为连续子序列
题目：
给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。
如果可以完成上述分割，则返回 true ；否则，返回 false 。
思路：贪心获取数字。先统计数字出现的次数，如果遇到出现的次数降序且当前长度不小于3，就不往后取，否则往后取
时间复杂度O(n)，空间复杂度O(n)
/**
* @param {number[]} nums
* @return {boolean}
*/
var isPossible = function(nums) {
const l = nums.length;
if (l < 3) return false;
const map = new Map();
for (const n of nums) {
map.set(n, (map.get(n) || 0) + 1);
}
while ( map.size ){
let len = 0 , max = 0 , last
for( let [key,value] of map ){
if ( max > value || ( len && key - last > 1 )) break
( max = value , last = key , len++ )
value - 1 ? map.set( key , value - 1 ) : map.delete(key)
}
if ( len && len < 3 ) return false
}
return true
return true;
};3.二叉树最大宽度
题目：
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
思路：记录每个节点的下标，加入当前节点是n，左节点是2*n，右节点是2*n+1，然后没一层取最小值和最大值之差。为了方便计算，每一层的左节点默认取0，其他依次减去
时间复杂度O(n)，空间复杂度O(h)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var widthOfBinaryTree = function (root) {
if (!root) return 0;
const height = [];
const search = (root, pre = 0, level = 0) => {
if (!root) return;
if (!height[level]) {
height[level] = [pre, 0, 0];
} else {
height[level][1] = Math.min(pre - height[level][0], height[level][1]);
height[level][2] = Math.max(pre - height[level][0], height[level][2]);
}
search(root.left, (pre - height[level][0]) * 2, level + 1);
search(root.right, (pre - height[level][0]) * 2 + 1, level + 1);
};
search(root);
return Math.max(...height.map((item) => item[2] - item[1])) + 1;
};4.优美的排列
题目：
给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：
① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.
② 如果存在多种答案，你只需实现并返回其中任意一种.
思路：要形成差有k种的数列，最少的数字数量是k+1，所以先确定[0,k]区间内的数，剩下的保持差为1即可
[0,k]区间，可以这么排列：偶数下标[1,2,3..]，奇数下标[k+1,k...]，这样，差值依次是k,k-1...1.
时间复杂度O(n)，空间复杂度O(n)
/**
* @param {number} n
* @param {number} k
* @return {number[]}
*/
var constructArray = function(n, k) {
const list = new Array(n);
for (let i = 0; i <= k; i++) {
if (!(i % 2)) {
list[i] = i / 2 + 1;
} else {
list[i] = k + 1 - (i - 1) / 2;
}
}
for (let i = k + 1; i < n; i++) {
list[i] = i + 1;
}
return list;
};5.最大交换
题目：给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
思路：动态规划。什么时候交换呢？尽可能交换前面的数字，且与后面的最大数交换。所以从后往前，记录每一个数右侧最大的数的下标，然后从前往后遍历，判断当前数是否大于右侧最大的数。如果右侧最大的数不止一个，那么取最后一个的下标(因为小的数尽可能放在后面)
时间复杂度O(n)，空间复杂度O(n)
/**
* @param {number} num
* @return {number}
*/
var maximumSwap = function(num) {
num = `${num}`.split("");
const l = num.length;
if (l < 2) return Number(num.join(""));
const dp = new Array(l).fill(0);
dp[l - 1] = l - 1;
for (let i = l - 2; i >= 0; i--) {
dp[i] = Number(num[i + 1]) > Number(num[dp[i + 1]]) ? i + 1 : dp[i + 1];
}
for (let i = 0; i < l - 1; i++) {
if (Number(num[i]) < Number(num[dp[i]])) {
[num[i], num[dp[i]]] = [num[dp[i]], num[i]];
break;
}
}
return Number(num.join(""));
};
最后
以上就是俊秀小懒猪为你收集整理的js解leetcode(48)-中等的全部内容，希望文章能够帮你解决js解leetcode(48)-中等所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复