Javascript:检查数组是否是几乎递增的序列
我正在研究代码信号上的Javascript挑战，并遇到了以下问题：
将整数序列作为数组，通过从数组中删除不超过一个元素来确定是否有可能获得严格递增的序列。
注意:如果序列a0 < a1 <.<.< an，则认为a0 <.只包含一个元素的序列也被认为是严格递增的。
例如，序列= 1，3，2，1的输出应该是almostIncreasingSequence(序列)= false。
这个数组中没有一个元素可以被移除以获得严格递增的序列。对于序列= 1、3、2，输出应该是almostIncreasingSequence(序列)= true。
您可以从数组中删除3以获得严格递增的序列1、2，或者删除2以获得严格递增的序列1、3。
我的方法是迭代序列数组，检查当前元素是否大于下一个元素，如果是，请删除当前元素。然后，增加一个计数器，如果计数器小于2返回true，则返回false。
这是我的代码：
function almostIncreasingSequence(sequence) {
// If array has 1 or 2 elements it passes
if(sequence.length <= 2) {
return true;
}
// Keeps track of numbers removed
let numberRemoved = 0;
// Iterate through array, check if current element is greater than next element
// If so, increment numberRemoved and remove current element
for(let i = 0; i < sequence.length; i++) {
if(sequence[i] >= sequence[i + 1]) {
numberRemoved++;
// Removed element if it's greater than next element
let removed = sequence.splice([i], 1);
i = 0;
console.log(sequence);
}
}
// Second pass through the array checks if there are 2 or more out of order
// elements. Inefficient and sloppy, need to find a better approach
for(let j = 0; j < sequence.length; j++) {
if(sequence[j] >= sequence[j + 1]) {
numberRemoved++;
}
}
// If number is less than 2, the sequence passes
if(numberRemoved < 2) {
return true;
}
else {
return false;
}
}该解决方案解决了17/19测试用例。我遇到了一个边缘情况，有时如果i >= i+ 1，正确的方法是删除i + 1，而不是i。例如：
对于序列: 3，5，67，98，3
- 循环检查如果98是>= 3
- 删除98
- 序列失败，因为3，5，67，3失败
H 118在这种情况下，我们不应该删除98，我们应该删除3<代码>H 219<
- >H 120序列，然后通过: 3，5，67，98返回真<<代码>H 221<代码>H 122对于这种我们不想做的边缘情况：
E 123/code>let= sequence.splice(i，1)； We想要做的事情：让删除= sequence.splice(i + 1，1);，这将删除33，5，67，98返回真正的
我怎么处理这个边缘的案子？在某些情况下，如果sequencei >= i+ 1，则需要删除sequencei，而在其他情况下，则需要删除i + 1。如何在不使用第二个for循环并第二次遍历数组的情况下解决这个问题？
回答 6
Stack Overflow用户
发布于 2019-12-23 23:48:22
无论何时发现一个递减的数字，我们都需要确定两个连续的数字中哪一个应该被删除。它可以是：
- 最后一个数字太大了
- 当前的数字太小
如果两者都不能修复减少，数组已经不是一个“几乎增加的序列”，因为这意味着至少还需要另一个删除。
function almostIncreasingSequence(sequence) {
let removed = 0;
let i = 0;
let prev = -Infinity;
// as long as removed less than 2 times, and i is under arrays length
while(removed < 2 && i < sequence.length) {
if(sequence[i] > prev) { // if current is bigger the previous
prev = sequence[i]; // assign current to previous
// remove the latter number, if it fixes the decrease
} else if (i === sequence.length - 1 || sequence[i+1] > sequence[i-1]) {
removed++; // increment removed
} else if (i < 2 || sequence[i] > sequence[i-2]) {
// remove the former number, if it fixes the decrease
removed++;
prev = sequence[i];
} else {
// neither option fixes the decrease, so at least 2 removal is needed
return false;
}
i++;
}
return removed < 2; // true if removed are under 2
}
console.log(almostIncreasingSequence([1, 3, 2, 1])); // false
console.log(almostIncreasingSequence([1, 3, 2])); // true
console.log(almostIncreasingSequence([3, 5, 67, 98, 3])); // true
console.log(almostIncreasingSequence([4, 3, 5, 67, 98, 3])); // false
console.log(almostIncreasingSequence([1, 4, 2, 3])); // true
console.log(almostIncreasingSequence([10, 13, 2, 9])); // false
Stack Overflow用户
发布于 2019-12-23 22:36:52
问题主要是“我们是否需要删除一个或更少的项目才能得到一个增加的顺序？”因此，您实际上不需要删除任何东西，只需计算需要删除的项的数量。
此外，您还需要继续检查，而不需要不进行下一次检查。在这种情况下，将当前和prev之间的较低的数字分配给prev。
function almostIncreasingSequence(sequence) {
let removed = 0;
let i = 0;
let prev = -Infinity;
// as long as removed less than 2 times, and i is under arrays length
while(removed < 2 && i < sequence.length) {
if(sequence[i] > prev) { // if current is bigger the previous
prev = sequence[i]; // assign current to previous
} else {
prev = Math.min(prev, sequence[i]); // take the lowest
removed++; // increment removed
}
i++;
}
return removed < 2; // true if removed are under 2
}
console.log(almostIncreasingSequence([1, 3, 2, 1])); // false
console.log(almostIncreasingSequence([1, 3, 2])); // true
console.log(almostIncreasingSequence([3, 5, 67, 98, 3])); // true
console.log(almostIncreasingSequence([4, 3, 5, 67, 98, 3])); // false
console.log(almostIncreasingSequence([1, 4, 2, 3])); // true
Stack Overflow用户
发布于 2019-12-23 23:20:44
我不确定能真正理解这个问题，但我想这个问题可能是你的答案.
function testSequence(arraySequence)
{
let prev = -Infinity
, ret = true
, out = false
;
for(let val of arraySequence)
{
if (val<=prev)
{
if (out) { ret=false; break }
else { out=true }
}
prev=val
}
return ret
}
console.log(testSequence([1, 3, 2, 1])); // false
console.log(testSequence([1, 3, 2])); // true
console.log(testSequence([3, 5, 67, 98, 3])); // true
console.log(testSequence([4, 3, 5, 67, 98, 3])); // false
https://stackoverflow.com/questions/59461894
复制相似问题
腾讯云开发者
