有效的括号、帕斯卡三角形和颠倒二进制位

有效的括号

给定一个只包括 '(',')','{','}','[',']'的字符串,判断字符串是否有效。

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。

  • 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: '()';
输出: true;

示例 2:

输入: '()[]{}';
输出: true;

示例 3:

输入: '(]';
输出: false;

示例 4:

输入: '([)]';
输出: false;

示例 5:

输入: '{[]}';
输出: true;

方法一

思路

遍历s,如果是左括号就压栈,如果是右括号就与栈顶元素进行匹配,匹配成功执行出栈操作 如果遍历完成后,栈中无元素,说明是有效字符串

详解

首先,左括号我们是无法判断是否合法的 因为所谓的不合法是当右括号与左括号不匹配的时候才发生的

  1. 那么我们遇到左括号的时候,先把他推入栈中

  2. 当我们遇到右括号的时候,刚好就可以与栈中的左括号进行匹配,如果正确,就把左括号出栈

  3. 如果最终栈为空,说明全部匹配成功

代码

/**
* @param {string} s
* @return {boolean}
*/
const isValid = function (s) {
const stack = [];
const map = {
')': '(',
'}': '{',
']': '['
};
for (const c of s) {
if (!(c in map)) {
stack.push(c);
} else if (!stack.length || map[c] !== stack.pop()) {
return false;
}
}
return !stack.length;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    遍历了 1 次含n个元素的空间

  • 空间复杂度:O(n)O(n)

方法二

思路

遇见匹配的问题,最好的解决方案就是Stack结构,但是JS本身是没有栈结构的,JS可以用数组来实现栈。

详解

  1. 碰到左括号,push右括号,

  2. 不是左括号,判断栈是否为空或栈顶元素是否等当前元素

  3. 最终数组是否有元素判断 s 是否有效的括号

代码

/**
* @param {string} s
* @return {boolean}
*/
const isValid = function (s) {
const rightSymbols = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
rightSymbols.push(')');
} else if (s[i] === '{') {
rightSymbols.push('}');
} else if (s[i] === '[') {
rightSymbols.push(']');
} else if (rightSymbols.pop() !== s[i]) {
return false;
}
}
return !rightSymbols.length;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    遍历了 1 次含 n 个元素的空间

  • 空间复杂度:O(n)O(n)

    遍历过程没有用到新的空间存储数据

方法三

思路

与方法一类似,方法三使用 Map 数据类型。让代码更具可读性

详解

首先,左括号我们是无法判断是否合法的 因为所谓的不合法是当右括号与左括号不匹配的时候才发生的

  1. 那么我们遇到左括号的时候,先把他推入栈中

  2. 当我们遇到右括号的时候,刚好就可以与栈中的左括号进行匹配,如果正确,就把左括号出栈

  3. 如果最终栈为空,说明全部匹配成功

代码

const isValid = function (s) {
const stack = [];
const map = new Map([
[')', '('],
['}', '{'],
[']', '[']
]);
for (const c of s) {
if (!map.has(c)) {
stack.push(c);
} else if (!stack.length || map.get(c) !== stack.pop()) {
return false;
}
}
return !stack.length;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    遍历了 1 次含 nn 个元素的空间

  • 空间复杂度:O(n)O(n)

    遍历过程没有用到新的空间存储数据

帕斯卡三角形

给定一个非负整数 numRows , 生成杨辉三角的前 numRows 行。

示例

输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

方法一 递归

思路

利用递归,除了第一个和最后一个元素之外,其他元素为它左上方的元素和正上方元素的和

详解

找出如何递归之后,我们需要找出递归终止的条件,当递归到 index === rowNum 或者 index === 0时,即为第一个、最后一个元素时,跳出递归

代码

function combination (rowNum, index) {
if (index === 0 || rowNum === index) { // 最后一个数与第一个数始终为 1
return 1;
}
return combination(rowNum - 1, index - 1) + combination(rowNum - 1, index);
}
const generate = function (numRows) {
const result = [];
for (let i = 0; i < numRows; i++) {
const row = [];
for (let j = 0; j <= i; j++) {
row.push(combination(i, j));
}
result.push(row);
}
return result;
};

复杂度分析

  • 时间复杂度:O(2n)O(2^n)

    递归的深度是 nn, O(n)=22...2=2nO(n) = 2 * 2 * ... * 2 = 2^n

  • 空间复杂度:O(2n)O(2^n)

    同理,每次需要额外申请 O(2n)O(2^n) 的堆栈内存,递归代码在紧凑易懂的同时,牺牲了执行速度,同时因为大量使用堆栈内存也牺牲了空间。

方法二 动态规划

思路

知道一行,就可以根据每对相邻的值,计算出下一行

详解

1 1
1 1 ---> 1 1
\|
1 X 1 1 2 1

每一列的头和尾都是 1,中间的每一个元素为上一列的当前索引和前一个索引之和

代码

const generate = function (numRows) {
if (numRows) {
const result = [[1]];
for (let i = 1; i < numRows; i++) {
// 第一个元素始终为 1
const row = [1];
const prevRow = result[i - 1];
for (let j = 1; j < i; j++) {
row.push(prevRow[j] + prevRow[j - 1]);
}
// 最后一个也为 1
row.push(1);
result.push(row);
}
return result;
};
return [];
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

    在最外层循环需要运行 nn 次,在里面一层需要循环 s=1+2+...+ns = 1 + 2 + ... + n,这里利用小学三年级的数学知识得到 s=n(n+1)/2=O(n2)s = n(n + 1)/2 = O(n^2)

  • 空间复杂度:O(n2)O(n^2)

    需要在 result 中保存每个数字,与时间复杂度相同

颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

示例

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。
输入:11111111111111111111111111111101
输出:10111111111111111111111111111111
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

方法一

思路

将十进制转为二进制,补齐32位,翻转,在转换成十进制数。

详解

  1. 换成 2 进制数字符串。

  2. 不足 32 位的,前面补零

  3. 转换成一位一位的数组

  4. 数组翻转

  5. 转换为字符串

  6. 转换为十进制数

很简单的方法,但是执行时间非常长。

将数字转换成 2 进制数,然后不足 32 位的,前面补零。转换成一位一位的数组,颠倒,再转回字符串,再由 2 进制数转为普通数字。

const reverseBits = function (n) {
const temp = n.toString(2).padStart(32, 0).split('').reverse().join('');
return Number.parseInt(temp, 2);
};

复杂度分析

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(1)O(1)

    并未申请额外空间,所以空间复杂度为 O(1)O(1)

方法二

思路

首先了解 10 进制数 转 2 进制数的算法。不断地 除 2 取余,然后倒序拼接就是 2 进制数。

我们要颠倒 2 进制数,不断取余正序拼接就是我们想要的结果了。

详解

  1. 在外面定义一个变量,接受结果。

  2. 循环32次,每次判断是否能被 2 整除

    1. 能被 2 整除,变量拼接 '0';然后 n = n / 2 继续循环;

    2. 不能被 2 整除,变量拼接 '1';然后 n = Math.floor(n / 2) 继续循环

const reverseBits = function (n) {
let str = '';
while (str.length < 32) {
if (n % 2 > 0) {
str += '1';
n = Math.floor(n / 2);
} else {
str += '0';
n = n / 2;
}
}
return parseInt(str, 2);
};

复杂度分析:

  • 时间复杂度:O(n)O(n)

    二进制数 32 位,所有位数循环一次时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

    并未申请额外空间,所以空间复杂度为 O(1)O(1)