gzl的博客

  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

LC-有效的括号

发表于 2019-07-18 更新于 2020-03-13 分类于 LeetCode

题目描述

有效的括号

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

1
2
输入: "()"
输出: true
1
2
输入: "()[]{}"
输出: true
1
2
输入: "(]"
输出: false

代码实现

这是一个很经典的关于栈的问题

如果 s.length 是奇数,直接返回 false 提高效率

利用栈的原理,使用 for of 代替 for 循环来遍历字符串,非常简便。

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
/**
* @param {string} s
* @return {boolean}
*/
const obj = {
"(": ")",
"{": "}",
"[": "]"
}
var isValid = function(s) {
if (s.length % 2 !== 0) {
return false;
}
let stack = [];
for (let c of s) {
if (c in obj) {
stack.push(obj[c]);
} else {
if (c !== stack.pop()) {
return false;
}
}
}
return stack.length === 0;
}

console.log(isValid("()")) // true
console.log(isValid("(){}[]")) // true
console.log(isValid("(]")) // false
console.log(isValid("{([])}")) // true

RN-《JavaScript高级程序设计》第六章继承

发表于 2018-10-19 更新于 2020-02-06 分类于 读书笔记

原型链继承

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function Parent() {
this.colors = ['red','blue','yellow'];
}

function Child() {}

Child.prototype = new Parent(); // 核心
Child.prototype.constructor = Child;

var child1 = new Child();

child1.colors.push('orange');

console.log(child1.colors); //  ["red", "blue", "yellow", "orange"]

var child2 = new Child();

console.log(child2.colors); // ["red", "blue", "yellow", "orange"]

实现的本质是重写原型对象,代之以一个新类型的实例。

问题:

  1. 引用类型的属性被所有实例共享
  2. 在创建 Child 的实例时,不能向Parent传参

借用构造函数

这种技术的基本思想相当简单,即在子类型构造函数的内部调用超类型构造函数。别忘了,函数只不过是在特定环境中执行代码的对象,因此通过使用 apply()和 call()方法也可以在(将来)新创建的对象上执行构造函数。

可以在子类型构造函数中向超类型构造函数传递参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function Parent(name) {
this.name = name;
this.colors = ['red','blue','yellow'];
}

function Child(name) {
Parent.call(this,name); // 核心
}

let child1 = new Child("gzl1");

child1.colors.push('orange');

console.log(child1.colors); //  ["red", "blue", "yellow", "orange"]
console.log(child1.name); // gzl1

let child2 = new Child("gzl2");

console.log(child2.colors); // ["red", "blue", "yellow"]
console.log(child2.name); // gzl2

问题:方法都在构造函数中定义

组合继承

组合继承(combination inheritance),有时候也叫做伪经典继承,指的是将原型链和借用构造函数的技术组合到一块,从而发挥二者之长的一种继承模式。其背后的思路是使用原型链实现对原型属性和方法的继承,而通过借用构造函数来实现对实例属性的继承。这样,既通过在原型上定义方法实现了函数复用,又能够保证每个实例都有它自己的属性。

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
function Parent(name) {
this.name = name;
this.colors = ['red','blue','yellow'];
}

function Child(name,age) {
Parent.call(this,name); // 核心
this.age = age;
}

Child.prototype = new Parent(); // 核心
Child.prototype.constructor = Child;

let child1 = new Child("gzl1",18);

child1.colors.push('orange');

console.log(child1.colors);//  ["red", "blue", "yellow", "orange"]
console.log(child1.name); // gzl1
console.log(child1.age); // 18

let child2 = new Child("gzl2",19);

console.log(child2.colors);// ["red", "blue", "yellow"]
console.log(child2.name); // gzl2
console.log(child2.age); // 19

问题:会调用两次父构造函数,且child1,2的原型中会有colors

组合继承避免了原型链和借用构造函数的缺陷,融合了它们的优点,成为 JavaScript 中最常用的继承模式。而且,instanceof 和 isPrototypeOf()也能够用于识别基于组合继承创建的对象。

原型式继承

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
function createObj(o) {
function F(){}
F.prototype = o;
return new F();
}
//ES5 Object.create 的模拟实现,将传入的对象作为创建的对象的原型
var person = {
name: 'gzl',
friends: ['x', 'y']
}

var person1 = createObj(person);
person1.name = 'gzl1'; // 并非修改了原型上的 name 值
person1.friends.push('z');

var person2 = createObj(person);
person2.name = 'gzl2'; // 并非修改了原型上的 name 值
person2.friends.push('c');


console.log(person1.name); // gzl1
console.log(person1.friends); // ["x", "y", "z", "c"]

console.log(person2.name); // gzl2
console.log(person2.friends); // ["x", "y", "z", "c"]

问题:包含引用类型的属性值始终都会共享相应的值,这点跟原型链继承一样

寄生式继承

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function createObj (o) {
var clone = Object.create(o);
clone.sayName = function () {
console.log(this.friends);
}
return clone;
}

var person = {
name: 'gzl',
friends: ['x', 'y']
}

var person1 = createObj(person);
person1.sayName(); //  ["x", "y"]

问题:跟借用构造函数模式一样,每次创建对象都会创建一遍方法。

寄生组合式继承

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
function Parent (name) {
this.name = name;
this.colors = ['red', 'blue', 'green'];
}

Parent.prototype.getName = function () {
console.log(this.name)
}

function Child (name, age) {
Parent.call(this, name);
this.age = age;
}

inheritPrototype(Child,Parent);

function obj(o) {
function F() {}
F.prototype = o;
return new F();
}

function inheritPrototype(child, parent) {
var prototype = obj(parent.prototype);
prototype.constructor = child;
child.prototype = prototype;
}

var child1 = new Child("gzl1",18);
child1.colors.push('orange');
console.log(child1.colors); // ["red", "blue", "green", "orange"]

var child2 = new Child("gzl2",19);
console.log(child2.colors); // ["red", "blue", "green"]

开发人员普遍认为寄生组合式继承是引用类型最理想的继承范式。

排序算法

发表于 2018-10-14 更新于 2020-03-12 分类于 算法

冒泡排序

外循环会从数组的第一位迭代至最后一位,它控制了在数组中经过多少轮排序,每一轮比较都会把数组中最大的数放到最后。

下面的内循环代码中 减去了 i 是因为减去外循环中已经跑过的轮数,就可以避免内循环中所有不必要的比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 冒泡排序
function bubbleSort(arr) {
const { length } = arr;
console.time('冒泡排序耗时');
for(let i = 0; i < length; i ++) {
for(let j = 0; j < length - 1 - i; j ++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
console.timeEnd('冒泡排序耗时');
return arr;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr));

选择排序

选择排序算法是一种原址比较排序算法。大致思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。

下面代码中 minIndex 记录的是每一轮最小值的位置,内循环选出 minIndex 后外循环进行交换,一共需要进行 len - 1 轮

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 选择排序
function selectionSort(arr) {
let { length } = arr;
let minIndex;
console.time('选择排序耗时');

for(let i = 0; i < length - 1; i ++) {
minIndex = i;
for(let j = i + 1; j < length; j ++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (i !== minIndex) {
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
}
}
console.timeEnd('选择排序耗时');
return arr;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(selectionSort(arr));

插入排序

原理很简单,就像打扑克牌的时候一样按顺序整理牌。如果后一个大于前一个,那么就插入,小于的话就不做交换。

  1. 从第一个元素开始,该元素可以认为已经被排序;

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;

  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;

  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

  5. 将新元素插入到该位置后;

  6. 重复步骤2~5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 插入排序
function insertionSort(arr) {
let len = arr.length;
console.time('插入排序耗时');
for (let i = 1; i < len; i++) {
for (let j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
[ arr[j], arr[j - 1] ] = [ arr[j - 1], arr[j] ];
} else {
continue;
}
}
}
console.timeEnd('插入排序耗时');
return arr;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(insertionSort(arr));

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 希尔排序
function shellSort(arr,gap) {
console.log(arr)//为了方便观察过程,使用时去除
for(let i = 0; i<gap.length; i ++) { //最外层循环,一次取不同的步长,步长需要预先给出
let n = gap[i]; //步长为n
for(let j = i + n; j < arr.length; j ++) { //接下类和插入排序一样,j循环依次取后面的数
for(let k = j; k > 0; k-=n) { //k循环进行比较,和直接插入的唯一区别是1变为了n
if(arr[k] < arr[k-n]) {
[arr[k],arr[k-n]] = [arr[k-n],arr[k]];
console.log(`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k-n]}`)//为了观察过程
} else {
continue;
}
}
}
}
return arr;
}

let arr = [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0];
let gap = [3,2,1];
console.log(shellSort(arr,gap))

归并排序

分而治之思想的算法应用:算法首先将原始数组分割直至只有一个元素的子数组,然后开始归并。

  1. 把长度为n的输入序列分成两个长度为n/2的子序列;

  2. 对这两个子序列分别采用归并排序;

  3. 将两个排序好的子序列合并成一个最终的排序序列。

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
35
// 归并排序
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
let result = [];

while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length) {
result.push(left.shift())
}
while (right.length) {
result.push(right.shift());
}

return result;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(mergeSort(arr));

快速排序

分而治之思想在排序算法上的典型应用

  1. 从数列中挑出一个元素,称为 “基准”(pivot);

  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 快速排序
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)]
// return quickSort(left).concat([pivot], quickSort(right));
};

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(arr));

参考

十大经典排序算法总结(JavaScript描述)

1…282930…32

gzl

96 日志
14 分类
37 标签
© 2020 gzl
由 Hexo 强力驱动 v3.7.1
|
主题 – NexT.Pisces v7.2.0