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

有效的括号

给定一个只包括 '(',')','{','}','[',']'的字符串,判断字符串是否有效。
有效字符串需满足:
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
1
输入: '()';
2
输出: true;
Copied!
示例 2:
1
输入: '()[]{}';
2
输出: true;
Copied!
示例 3:
1
输入: '(]';
2
输出: false;
Copied!
示例 4:
1
输入: '([)]';
2
输出: false;
Copied!
示例 5:
1
输入: '{[]}';
2
输出: true;
Copied!

方法一

思路
遍历s,如果是左括号就压栈,如果是右括号就与栈顶元素进行匹配,匹配成功执行出栈操作 如果遍历完成后,栈中无元素,说明是有效字符串
详解
首先,左括号我们是无法判断是否合法的 因为所谓的不合法是当右括号与左括号不匹配的时候才发生的
    1.
    那么我们遇到左括号的时候,先把他推入栈中
    2.
    当我们遇到右括号的时候,刚好就可以与栈中的左括号进行匹配,如果正确,就把左括号出栈
    3.
    如果最终栈为空,说明全部匹配成功
代码
1
/**
2
* @param {string} s
3
* @return {boolean}
4
*/
5
const isValid = function (s) {
6
const stack = [];
7
const map = {
8
')': '(',
9
'}': '{',
10
']': '['
11
};
12
13
for (const c of s) {
14
if (!(c in map)) {
15
stack.push(c);
16
} else if (!stack.length || map[c] !== stack.pop()) {
17
return false;
18
}
19
}
20
return !stack.length;
21
};
Copied!
复杂度分析
    时间复杂度:
    O(n)O(n)
    遍历了 1 次含n个元素的空间
    空间复杂度:
    O(n)O(n)

方法二

思路
遇见匹配的问题,最好的解决方案就是Stack结构,但是JS本身是没有栈结构的,JS可以用数组来实现栈。
详解
    1.
    碰到左括号,push右括号,
    2.
    不是左括号,判断栈是否为空或栈顶元素是否等当前元素
    3.
    最终数组是否有元素判断 s 是否有效的括号
代码
1
/**
2
* @param {string} s
3
* @return {boolean}
4
*/
5
const isValid = function (s) {
6
const rightSymbols = [];
7
for (let i = 0; i < s.length; i++) {
8
if (s[i] === '(') {
9
rightSymbols.push(')');
10
} else if (s[i] === '{') {
11
rightSymbols.push('}');
12
} else if (s[i] === '[') {
13
rightSymbols.push(']');
14
} else if (rightSymbols.pop() !== s[i]) {
15
return false;
16
}
17
}
18
return !rightSymbols.length;
19
};
Copied!
复杂度分析
    时间复杂度:
    O(n)O(n)
    遍历了 1 次含 n 个元素的空间
    空间复杂度:
    O(n)O(n)
    遍历过程没有用到新的空间存储数据

方法三

思路
与方法一类似,方法三使用 Map 数据类型。让代码更具可读性
详解
首先,左括号我们是无法判断是否合法的 因为所谓的不合法是当右括号与左括号不匹配的时候才发生的
    1.
    那么我们遇到左括号的时候,先把他推入栈中
    2.
    当我们遇到右括号的时候,刚好就可以与栈中的左括号进行匹配,如果正确,就把左括号出栈
    3.
    如果最终栈为空,说明全部匹配成功
代码
1
const isValid = function (s) {
2
const stack = [];
3
const map = new Map([
4
[')', '('],
5
['}', '{'],
6
[']', '[']
7
]);
8
9
for (const c of s) {
10
if (!map.has(c)) {
11
stack.push(c);
12
} else if (!stack.length || map.get(c) !== stack.pop()) {
13
return false;
14
}
15
}
16
return !stack.length;
17
};
Copied!
复杂度分析
    时间复杂度:
    O(n)O(n)
    遍历了 1 次含
    nn
    个元素的空间
    空间复杂度:
    O(n)O(n)
    遍历过程没有用到新的空间存储数据

帕斯卡三角形

给定一个非负整数 numRows , 生成杨辉三角的前 numRows 行。
示例
1
输入: 5
2
输出:
3
[
4
[1],
5
[1,1],
6
[1,2,1],
7
[1,3,3,1],
8
[1,4,6,4,1]
9
]
Copied!

方法一 递归

思路
利用递归,除了第一个和最后一个元素之外,其他元素为它左上方的元素和正上方元素的和
详解
找出如何递归之后,我们需要找出递归终止的条件,当递归到 index === rowNum 或者 index === 0时,即为第一个、最后一个元素时,跳出递归
代码
1
function combination (rowNum, index) {
2
if (index === 0 || rowNum === index) { // 最后一个数与第一个数始终为 1
3
return 1;
4
}
5
return combination(rowNum - 1, index - 1) + combination(rowNum - 1, index);
6
}
7
8
const generate = function (numRows) {
9
const result = [];
10
for (let i = 0; i < numRows; i++) {
11
const row = [];
12
for (let j = 0; j <= i; j++) {
13
row.push(combination(i, j));
14
}
15
result.push(row);
16
}
17
return result;
18
};
Copied!
复杂度分析
    时间复杂度:
    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
2
1 1 ---> 1 1
3
\|
4
1 X 1 1 2 1
Copied!
每一列的头和尾都是 1,中间的每一个元素为上一列的当前索引和前一个索引之和
代码
1
const generate = function (numRows) {
2
if (numRows) {
3
const result = [[1]];
4
for (let i = 1; i < numRows; i++) {
5
// 第一个元素始终为 1
6
const row = [1];
7
const prevRow = result[i - 1];
8
9
for (let j = 1; j < i; j++) {
10
row.push(prevRow[j] + prevRow[j - 1]);
11
}
12
13
// 最后一个也为 1
14
row.push(1);
15
result.push(row);
16
}
17
return result;
18
};
19
return [];
20
};
Copied!
复杂度分析
    时间复杂度:
    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 位无符号整数的二进制位。
示例
1
输入: 00000010100101000001111010011100
2
输出: 00111001011110000010100101000000
3
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
4
因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。
5
6
输入:11111111111111111111111111111101
7
输出:10111111111111111111111111111111
8
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
9
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。
Copied!

方法一

思路
将十进制转为二进制,补齐32位,翻转,在转换成十进制数。
详解
    1.
    换成 2 进制数字符串。
    2.
    不足 32 位的,前面补零
    3.
    转换成一位一位的数组
    4.
    数组翻转
    5.
    转换为字符串
    6.
    转换为十进制数
很简单的方法,但是执行时间非常长。
将数字转换成 2 进制数,然后不足 32 位的,前面补零。转换成一位一位的数组,颠倒,再转回字符串,再由 2 进制数转为普通数字。
1
const reverseBits = function (n) {
2
const temp = n.toString(2).padStart(32, 0).split('').reverse().join('');
3
return Number.parseInt(temp, 2);
4
};
Copied!
复杂度分析
    时间复杂度:
    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) 继续循环
1
const reverseBits = function (n) {
2
let str = '';
3
while (str.length < 32) {
4
if (n % 2 > 0) {
5
str += '1';
6
n = Math.floor(n / 2);
7
} else {
8
str += '0';
9
n = n / 2;
10
}
11
}
12
return parseInt(str, 2);
13
};
Copied!
复杂度分析:
    时间复杂度:
    O(n)O(n)
    二进制数 32 位,所有位数循环一次时间复杂度为
    O(n)O(n)
    空间复杂度:
    O(1)O(1)
    并未申请额外空间,所以空间复杂度为
    O(1)O(1)
最近更新 1yr ago