去掉数组中连续的数字,我又称之为「数组消消乐」
这是一道面试题,给大家分享一下:【去掉数组中连续的数字】,我又称之为「数组消消乐」。
数组中存储着多个 0-9 的数字,若存在连续大于等于 4 个相同的数字,则将其消除;若消除后,依然有连续个数大于等于 4 的数字,则继续消除。然后返回最终消除完毕后的数组。
实例:
/**
* @param {number[]} arr
* @return {number[]}
*/
function eliminate(arr) {}
console.log(eliminate([1, 1, 1, 1, 2]));
// [2]
console.log(eliminate([1, 1, 1, 1, 1, 2]));
// [2]
console.log(eliminate([2, 1, 1, 1, 1, 2, 2, 2]));
// []
console.log(eliminate([1, 1, 1, 0, 0, 0, 0, 0, 1, 2, 2, 3, 3, 3, 3]));
// [2, 2]
这题根据数组中的数据和数组的长度,有着几个不同的解法。
最简单暴力的,就是每次只清除当前连续的数字,等下次循环时,再重新清除新拼接的新数组,直到无法清除为止。
function eliminate(arr) {
while (true) {
let start = 0;
let end = 0;
for (end = start + 1; end < arr.length; end++) {
if (arr[end] !== arr[start]) {
break;
}
}
if (end - start >= 4) {
arr.splice(start, end);
} else {
return arr;
}
}
}
但这个时间复杂度太高了,每清除一次,就得从头开始循环。当然,也可以加一些优化措施,比如继续向后查找是否存在连续个数大于等于 4 的数字,但这里尤其要注意一个问题,不能光只删除后面的数字,不管前面的数字。
比如有这样的一个例子:[1,1,1,2,2,2,2,1,1,1,1],3 个连续的 1,4 个连续的 2,再跟着 4 个连续的 1。若删除了 4 个连续的 2 后,继续向后查找,只删除后续的连续的 4 个 1,是不对的。因为在删除 4 个 2 后,将数据前后拼接后,其实是连续 7 个 1。
我们可以看到题目中要求的是,数组的每项是 0-9 的数字,数据项不大,完全可以用数组来存储连续的数组个数。下标表示该数字,值表示该数字的连续个数。
function eliminate(arr) {
const counts = [];
counts[arr[0]] = {
start: 0,
num: 1,
};
let i = 1;
while (i < arr.length) {
if (arr[i] !== arr[i - 1]) {
// 当数字不一样时,就需要判断前面的数字的连续的个数
const { start, num } = counts[arr[i - 1]] || {};
if (num >= 4) {
counts[arr[i - 1]].num = 0;
arr.splice(start, num);
i = start - 1;
} else {
counts[arr[i]] = {
start: i,
num: 1,
};
}
} else {
counts[arr[i]].num++;
}
i++;
}
const { start, num } = counts[arr[arr.length - 1]];
if (num >= 4) {
arr.splice(start, num);
}
return arr;
}
这种题目天然适合栈结构,无论数组中是什么数据,均可以压到栈里,顶部的元素永远是当前正在连续计数的数字,当该数字被消除后,则从栈中弹出。
function eliminate(arr) {
const stack = []; // 每个元素存储的是该元素和连续的个数
let i = 0;
while (i < arr.length) {
const { length } = stack;
if (!length) {
// 栈中还没有元素,直接压入
stack.push({ item: arr[i], num: 1 });
i++;
} else if (stack[length - 1].item === arr[i]) {
// 栈顶的元素与当前元素相等
stack[length - 1].num++;
i++;
} else {
// 栈顶的元素与当前元素不相等
if (stack[length - 1].num >= 4) {
// 连续个数大于等于4,将该数字弹出
stack.pop();
// 而且,这里的i并没有加1,因为当前不一样的那个元素还要继续与下一个栈顶的元素进行比较
// 比如[1, 1, 1, 2, 2, 2, 2, 1],当栈顶元素2与最后一个1比较,栈弹出2后,最后一个1还得跟新栈顶元素1进行比较
} else {
stack.push({ item: arr[i], num: 1 });
i++;
}
}
}
if (stack.length && stack[stack.length - 1].num >= 4) {
stack.pop();
}
// 栈里留下来的数据,都是连续个数不够4个的,将栈中的数据拿出来,拼接成新的数组
let result = [];
for (let i = 0; i < stack.length; i++) {
result = result.concat(new Array(stack[i].num).fill(stack[i].item));
}
return result;
}
我们利用栈结构先进后出的特性,能很方便地解决这个问题。
这道题主要是考察我们对一些数据结构的使用,如果用不好的话,实现起来就麻烦很多,而且时间复杂度也会高很多。
原文来自:https://www.xiabingbao.com/post/algorithm/eliminate-digit-rq0xd1.html
avaScript数组同后端语言一样,具有它自己的数据结构,归根结底,这种数据结构,本质就是一种集合。在后端语言中(如java,.net等),数组是这样定义的:数组是用来存储相同数据类型的集合
单个数字转汉字的解决方法:利用数组存储0-9的汉字、 ary.length和str.length不用多说,这是指ary数组和str字符串的长度。这里我们需要注意的是str.charAt(j)和ary[i],分别指在str这个字符串中索引为j的元素,在ary中索引为i的元素。
在 Javascript 循环中使用 async/ await 循环遍历数组似乎很简单,但是在将两者结合使用时需要注意一些非直观的行为。让我们看看三个不同的例子,看看你应该注意什么,以及哪个循环最适合特定用例。
今天说的数组和字符串去重呢,主要用到es6新的数据结构 Set,它类似于数组,但是成员的值都是唯一的,没有重复的值,所以活用Set来进行数组和字符串的去重。
数组方法:1、Array.join([param]) 方法:将数组中所有的元素都转换为字符串并连接起来,通过字符 param 连接,默认使用逗号,返回最后生成的字符串2、Array.reverse() 方法:将数组中的元素颠倒顺序(在原数组中重新排列它们),返回逆序数组
falsy(虚值)是在 Boolean 上下文中已认定可转换为‘假‘的值.JavaScript 在需要用到布尔类型值的上下文中使用强制类型转换(Type Conversion )将值转换为布尔值,比如:在条件语句或者循环语句中。
JavaScript中我们经常会遇到拷贝数组的场景,但是都有哪些方式能够来实现呢,我们不妨来梳理一下。扩展运算符(浅拷贝)自从ES6出现以来,这已经成为最流行的方法。
本文主要来讲数组api的一些操作,如简单实现扁平化n维数组、数组去重、求数组最大值、数组求和、排序、对象和数组的转化等。扁平化嵌套数组/展平和阵列孔——flat()
vue无法监听数组变化的情况,但是数组在下面两种情况下无法监听:利用索引直接设置数组项时,例如arr[indexofitem]=newValue;修改数组的长度时,例如arr.length=newLength
使用 ES5 语法来实现虽然会麻烦些,但兼容性最好,不用考虑浏览器 JavaScript 版本,使用 ES5 语法来实现虽然会麻烦些,但兼容性最好,不用考虑浏览器 JavaScript 版本。也不用引入其他第三方库。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!