LC-有效的括号

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

题目描述

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

有效字符串需满足：

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

1 2	输入: "()" 输出: true

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

1 2	输入: "(]" 输出: false

代码实现

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

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

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

/**
 * @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 分类于读书笔记

原型链继承

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"]

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

问题：

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

借用构造函数

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

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

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

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()也能够用于识别基于组合继承创建的对象。

原型式继承

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"]

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

寄生式继承

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"]

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

寄生组合式继承

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 是因为减去外循环中已经跑过的轮数，就可以避免内循环中所有不必要的比较。

// 冒泡排序
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 轮

// 选择排序
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));

插入排序

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

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

// 插入排序
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));

希尔排序

// 希尔排序
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))

归并排序

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

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

// 归并排序
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));

快速排序

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

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

// 快速排序
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描述）