1、题干​

布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：

• 't'，运算结果为 true
• 'f'，运算结果为 false
• '!(subExpr)'，运算过程为对内部表达式 subExpr 进行 逻辑非（NOT）运算
• '&(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑与（AND）运算
• '|(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑或（OR）运算

给你一个以字符串形式表述的 布尔表达式 expression，返回该式的运算结果。

题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。

示例 1：

输入：expression = "&(|(f))"
输出：false
解释：
首先，计算 |(f) --> f ，表达式变为 "&(f)" 。
接着，计算 &(f) --> f ，表达式变为 "f" 。
最后，返回 false 。

示例 2：

输入：expression = "|(f,f,f,t)"
输出：true
解释：计算 (false OR false OR false OR true) ，结果为 true 。

示例 3：

输入：expression = "!(&(f,t))"
输出：true
解释：
首先，计算 &(f,t) --> (false AND true) --> false --> f ，表达式变为 "!(f)" 。
接着，计算 !(f) --> NOT false --> true ，返回 true 。

提示：

• 1 <= expression.length <= 2 * 104
• expression[i] 为 '('、')'、'&'、'|'、'!'、't'、'f' 和 ',' 之一

Problem: 1106. 解析布尔表达式

[TOC]

思路

使用正则不断提取最小表达式进行计算，再将该表达式替换为计算结果。其中最小表达式就是题干中给出的3种情况："!(expr)"，"&(expr1,expr2,...)"，"|(expr1,expr2,...)"

代码

function parseBoolExpr(exp: string): boolean {
    const T = "t", F = "f", reg = /.\([^()]+\)/g;
    while (reg.test(exp)) {
        exp = exp.replace(reg, (m) => {
            if (m[0] === "&") return m.includes(F) ? F : T;
            if (m[0] === "|") return m.includes(T) ? T : F;
            return m.includes(T) ? F : T;
        });
    }
    return exp.includes(T);
}

结果

1、题干​

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

• 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
• 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
• 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

示例 1：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 109

2、解题思路​

根据题意可知，消除的总轮次为Math.log2(n)，每轮消除后剩下的数字都构成等差数列。

\ 因此可以借助最小值min、最大值max、步长step3个变量来维护等差数列，每轮都更新等差数列的3个变量；最后一轮只剩一个数字，即min与max相等，任取一个返回即可。

\ 需要注意的是奇数轮次是从左到右消除，即最小值必定改变，最大值只在等差数列个数为奇数时改变；偶数轮次则相反，最大值必定改变，最小值只在等差数列个数为奇数时改变。

3、代码​

var lastRemaining = function (n) {
    let min = 1, max = n, step = 1;
    for (let i = 1; i <= Math.log2(n); i++) {
        if (i % 2) {
            if (((max - min) / step + 1) % 2) max -= step;
            min += step;
        } else {
            if (((max - min) / step + 1) % 2) min += step;
            max -= step;
        }
        step *= 2;
    }
    return max;
};

4、执行结果​