编码嵌套算法测试性能

Question

我正在尝试在Javascript中进行Codility'Nested'测试。

测试如下：

A string S consisting of N characters is called properly nested if:
S is empty;
S has the form "(U)" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.
Write a function:
function solution(S);
that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.
For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..1,000,000];
string S consists only of the characters "(" and/or ")".

我的解决方案如下：

function solution(S) {
const elements = S.split('')
const stack = []
if (elements.length > 1000000) return 0
if (elements[0] == ')') return 0
if (elements[0] == '(') stack.push('(')
for (i=0; i < elements.length; i++){
const currentElement = elements[i]
if (currentElement !== '(' && currentElement !== ')') return 0
if (i>0){
if (stack[stack.length-1] == '(' && currentElement == ')') stack.pop()
else stack.push(currentElement)
}
}
if (stack.length) return 0
else return 1
}

这是正确的，但性能仅返回 75%，我看不出如何进一步提高效率，有人有什么建议吗？

Answer 1

我认为你这样做太复杂了。拆分不一定。问题语句还说字符串只包含(和)。所以解决方案可以像这样简单(通过所有测试(：

function solution(S) {
let count = 0
for (const c of S) {
if (c == '(')
count++
else if (--count < 0)
return 0
}
return count == 0 ? 1 : 0
}

顺便说一句，代码中的这句话是错误的：

if (currentElement == ')' && openCount > 0)  openCount = openCount - 1
else openCount = openCount + 1

如果计数因)过多而变为负数，则将增加计数器。所以也许这毕竟不是性能问题。堆栈的解决方案也是如此：如果堆栈为空，则查找 stack[-1]，这是未定义的，因此您推送下一个元素(尽管它不会失败，因为您将推送)并且永远不会被消耗(。此外，将左大括号的索引推到堆栈上更有意义，这样您就可以(如果需要(显示大括号的配对，哪个(属于哪个)。如果您只是在堆栈上推送(，您也可以使用计数器。

Answer 2

按照评论中的建议，我尝试使用计数器。

不过，这仍然无法提高效率，在路径较深的宽树上受到惩罚。

function solution(S) {
// write your code in JavaScript (Node.js 8.9.4)
const elements = S.split('')
let openCount = 0
if (elements.length > 1000000) return 0
if (elements[0] == ')') return 0
if (elements[0] == '(') openCount = 1
for (i=0; i < elements.length; i++){
const currentElement = elements[i]
if (currentElement !== '(' && currentElement !== ')') return 0
if (i>0){
if (currentElement == ')' && openCount > 0)  openCount = openCount - 1
else openCount = openCount + 1
}
}
if (openCount !== 0) return 0
else return 1
}

Answer 3

您的解决方案中有太多的"如果"。试着理解马拉卡的答案。或者，在下面检查我的解决方案(99% 相同(

function solution(S) {
let stack = 0;
for (let i=0; i<S.length; i++) {
S[i] === '(' ? stack++ : stack--; 

if (S[i] === '(') {
stack++
} else {
stack--;
if (stack < 0) return 0;
}
}
return stack === 0 ? 1 : 0;
}

Answer 4

function solution(S) {
let stack=[];
if(!S){
return 1;
}
for(let i=0;i<S.length;i++){
if(S[i]==='('){
stack.push(S[i]);
}else if(stack.length){
stack.pop();
}else{
return 0;
}
}
return stack.length ? 0: 1;
}

Answer 5

100% 关于编码

const nesting = (s) => {
if (!s.length) {
return 1;
}
if (s.indexOf('(') === -1 && s.indexOf(')') === -1) {
return 1;
}
const arr = [];
const map = {
'(': ')'
};
for (let i = 0; i < s.length; i++) {
if (s[i] === '(' || s[i] === ')') {
if (!arr.length || map[arr[arr.length - 1]] !== s[i]) {
arr.push(s[i]);
continue;
}
if (map[arr[arr.length - 1]] === s[i]) arr.pop();
}
}
return arr.length > 0 ? 0 : 1;
}