前言

❤️笔芯❤️~

栈

栈是一种 后进先出 的有序集合。新添加或待删除的元素都保存在栈的同一端，叫做栈顶，另外一端叫栈底。

创建栈

创建一个类来表示栈：(如何使用Stack类)

1
2
3
function Stack() {
 // 各种属性和方法的声明
}

声明数组，保存栈里的元素：

1
let items = []
  • push()，添加一个或几个新元素到栈顶
  • pop()，移除栈顶的元素，同时返回被移除的元素
  • peek()，返回栈顶的元素，不对栈做任何修改
  • isEmpty()，如果栈里没有任何元素就返回true，否则返回false
  • clear()，移除栈里的所有元素
  • size()，返回栈里的元素个数

向栈添加元素（往栈里添加新元素）

示例：

1
2
3
4
// 只添加元素到栈顶，也就是栈的末尾
this.push = function(element) {
 items.push(element);
});

从栈移除元素（移出的是最后添加进去的元素）

示例：

1
2
3
this.pop = function() {
 return items.pop();
};

查看栈顶元素（用于想找到栈里面最后添加的元素是什么）

示例，返回栈顶的元素：

1
2
3
this.peek = function() {
 return items[items.length-1];
};

检查栈是否为空

如果栈为空的话将返回true，否则就返回false。

示例：

1
2
3
this.isEmpty = function() {
 return items.length == 0;
};

返回栈的长度：

1
2
3
this.size = function() {
 return items.length;
};

清空和打印栈元素

clear方法用来移除栈里所有的元素，把栈清空。

1
2
3
this.clear = function() {
 items = [];
};

把栈里的元素都输出来：

1
2
3
this.print = function() {
 console.log(item.toString());
};

使用Stack类

初始化Stack类：

1
2
let stack = new Stack(); 
console.log(stack.isEmpty()); //输出为true

往栈里添加一些元素

1
2
stack.push(1); 
stack.push(2);

如果调用peek方法，将会输出2

1
console.log(stack.peek()); //输出2

如何用ES6声明Stack类

代码：

1
2
3
4
5
6
7
8
9
// 在类的构造函数constructor里声明, ES6的类是基于原型的。
class Stack {
 constructor() {
  this.items = [];
 }
 push(element) {
  this.items.push(element);
 }
}

基于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性或方法。

  • 用ES6的限定作用域Symbol实现类

ES6新增了一种叫做Symbol的基本类型，它是不可变的，可以用作对象的属性。

示例：

1
2
3
4
5
6
7
8
// 声明了Symbol类型的变量_items，在类的constructor函数中初始化它的值
let _items = Symbol();

class Stack {
 constructor() {
  this[_items] = [];
 }
}

使用ES6新增的Object.getOwnPropertySymbols方法能够取到类里面声明的所有Symbols属性。

1
2
3
4
5
6
7
8
9
let stack = new Stack(); 
stack.push(2); 
stack.push(3); 
let objectSymbols = Object.getOwnPropertySymbols(stack); 
console.log(objectSymbols.length); // 1 
console.log(objectSymbols); // [Symbol()]  数组Symbols属性
console.log(objectSymbols[0]); // Symbol() 
stack[objectSymbols[0]].push(1); 
stack.print(); //输出 2, 3, 1

访问stack[objectSymbols[0]]获得_items的，_items属性是一个数组，可以进行任意的数组操作。所以不该使用这种方法。

  • ES6中的WeakMap实现类

使用WeakMap确保属性是私有的，WeakMap可以存储键值对，其中键是对象，值可以是任意数据类型。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 声明了一个WeakMap类型的变量items
const items = new WeakMap(); // 谁都可以改动它

class Stack { 
 constructor () { 
 // 在constructor中，以this为键，把代表栈的数组存入items
 items.set(this, []);
 } 
 push(element) { 
 // 从WeakMap中取出值，即以this为键从items中取值
 let s = items.get(this);
 s.push(element); 
 } 
 pop() { 
 let s = items.get(this); 
 let r = s.pop(); 
 return r; 
 } 
 //其他方法
}

itmes在Stack类里是真正的所有属性了。

使用闭包：

1
2
3
4
5
6
7
8
9
10
11
12
// 当Stack函数里的构造函数被调用时，会返回Stack类的一个实例
let Stack = (function () { 
 const items = new WeakMap(); 
 class Stack { 
   constructor () { 
   	items.set(this, []); 
   } 
   //其他方法
  }
  return Stack; //当被调用时，会返回Stack类的一个实例
})();
// 使用这种方法，扩展类无法继承私有属性

十进制转二进制问题算法

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function divideBy2(decNumber){ 
 var remStack = new Stack(), 
 rem, 
 binaryString = ''; 
 while (decNumber > 0){ 
   rem = Math.floor(decNumber % 2);  
   remStack.push(rem); 
   decNumber = Math.floor(decNumber / 2); 
 } 
 while (!remStack.isEmpty()){ 
   binaryString += remStack.pop().toString(); 
 } 
 return binaryString; 
}

十进制转换成任何进制

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function baseConverter(decNumber, base){ 
 var remStack = new Stack(), 
 rem, 
 baseString = '', 
 // 多了digits
 digits = '0123456789ABCDEF'; 
 // 基数
 while (decNumber > 0){ 
 rem = Math.floor(decNumber % base); 
 remStack.push(rem); 
 decNumber = Math.floor(decNumber / base); 
 } 
 
 while (!remStack.isEmpty()){ 
 baseString += digits[remStack.pop()]; 
 } 
 return baseString; 
}

两数之和

解题思路：

  • 暴力法
  • 哈希表法

示例伪代码：

1
2
3
4
5
6
7
8
9
func(nums,target) -> []
result = []; [0,1] 长度为2
for i in [0, len(nums)]; // 不动
for j in [i+1, len(nums)]; // 移动
sum = nums[i]+nums[j];
if sm == target;
result[0] = i
result[1] = j
result result

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
func(nums, target) -> [];
result = []
map = HashTable()

for i in [0, len(nums)];
 map.add(nums[i], i);

for j in [0, len(nums)];
 diff = target - nums[j]
 if(map.containskey(diff) and map.get(diff) != j)
  result[0] = j
  result[1] = map.get(diff)
  return result

两数相加

  • 迭代法
  • 递归法

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func (l1, l2) -> Listnode
total = 0 // 两个相加的和是多少
next1 = 0 // 下一个进位

result = ListNode()
cur = result

while (l1 != null and l2 != null);
total = l1.val + l2.vale + next1

cur.next = ListNode(total%10)
next1 = total / 10

l1 = l1.next
l2 = l2.next
cur = cur.next

while l1 != null
 total = l1.val + next1
 cur.next = ListNode(total%10)
 nextl = total / 10
 l1 = l1.next
 cur = cur.next
 
while l2 != null
 total = l2.val + next1
 cur.next = ListNode(total%10)
 next1 = total / 10
 l2 = l2.next
 cur = cur.next
 
if next1 ! = 0
 cur.next = ListNode(next1)
 return reult.next

递归法：

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (l1, l2) -> ListNode
 total = l1.val + l2.val
 next1 = total / 10
 res = ListNode(total % 10)
 if( l1.next != null or l2.next != null or next1 != 0 )
  if(l1.next ! = null)
   l1 = l1.next
  else
   l2 = ListNode(0)
   
  if(l2.next != null)
   l2 = l2.next
  else
   l2 = ListNode(0)
   
  l1.val = l1.val + next1
  res.next = fun(l1,l2)
 return res

有效的括号

栈的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var isValid = function (s) {
  let valid = true;
  const stack = [];
  const mapper = {
    "{": "}",
    "[": "]",
    "(": ")",
  };

  for (let i in s) {
    const v = s[i];
    if (["(", "[", "{"].indexOf(v) > -1) {
      stack.push(v);
    } else {
      const peak = stack.pop();
      if (v !== mapper[peak]) {
        return false;
      }
    }
  }

  if (stack.length > 0) return false;

  return valid;
};

合并两个有序链表

  • 迭代法
  • 递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

22. 括号生成

一、题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

二、思路分析

  • 回溯法

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fun(n) -> []
 result = []
 backtracking(n,result,0,0, "")
 return result
 backtracking(n,result,left,right,str) -> void
 
 if right > left
 return
 if left == right == n
 result.add(str)
 return
 
 if left<n
 backtracking(n,result,left+1,right,str+"(")
 if right<left
 backtracking(n,result,left,right+1,str+")")

三、答案代码

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number} n
 * @return {string[]}
 * @param l 左括号已经用了几个
 * @param r 右括号已经用了几个
 * @param str 当前递归得到的拼接字符串结果
 * @param res 结果集
 */
const generateParenthesis = function (n) {
  const res = [];

  function dfs(l, r, str) {
    if (l == n && r == n) {
      return res.push(str);
    }
    // l 小于 r 时不满足条件 剪枝
    if (l < r) {
      return;
    }
    // l 小于 n 时可以插入左括号，最多可以插入 n 个
    if (l < n) {
      dfs(l + 1, r, str + "(");
    }
    // r < l 时 可以插入右括号
    if (r < l) {
      dfs(l, r + 1, str + ")");
    }
  }
  dfs(0, 0, "");
  return res;
};

四、总结

栈,括号生成分析

回看笔者往期高赞文章，也许能收获更多喔！

❤️关注+点赞+收藏+评论+转发❤️，原创不易，鼓励笔者创作更好的文章