Giter VIP home page Giter VIP logo

algorithms's Introduction

algorithms's People

Contributors

hubvue avatar

Stargazers

avatar avatar avatar avatar

Watchers

avatar

algorithms's Issues

归并排序

归并排序把数据拆分成小的数据块，然后再排序合并

const mergeSort = (arr) => {
    let len = arr.length,
        left = [],
        right = [];
    if(len === 1){
        return arr;
    }
    let mid = Math.floor(len/2);
    for(let i = 0; i < len; i ++) {
        if(i>= mid){
            right.push(arr[i]);
        } else {
            left.push(arr[i]);
        }
    }
    return merge(mergeSort(left),mergeSort(right));
}
const merge = (left,right) => {
    let temp = [],
        leftIdx = 0,
        rightIdx = 0,
        leftLen = left.length,
        rightLen = right.length;

    while(leftIdx < leftLen && rightIdx < rightLen){
        if(left[leftIdx] <right[rightIdx]) {
            temp.push(left[leftIdx]);
            leftIdx ++;
        } else {
            temp.push(right[rightIdx]);
            rightIdx ++;
        }
    }
    while(leftIdx < leftLen){
        temp.push(left[leftIdx]);
        leftIdx ++;
    }
    while(rightIdx < rightLen){
        temp.push(right[rightIdx]);
        rightIdx ++;
    }
    return temp;
} 
console.log(mergeSort([9,8,7,6,5,4,3,2,1]));

19、删除链表的倒数第N个节点

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

题解

解题思路

由于是单链表，所以想到的办法是使用快慢指针的方式，快指针先走n次，然后快指针和慢指针再一起走，当快指针走到尾的时候，慢指针所在的位置就是需要删除节点的位置，将此位置的节点删除即可。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let node = new ListNode();
    node.next = head
    let fastNode = node;
    let slowNode = node;
    let idx = 0;
    while(fastNode.next){
        if(idx >=n) {
            slowNode = slowNode.next;
        }
        fastNode = fastNode.next;
        idx ++;
    }
    slowNode.next = slowNode.next.next;
    return node.next
    
};

写一个isPrime()函数，当其为质数时返回true，否则返回false

判断质数有很多优化的方式：

  1. 负数不是质数。
  2. 能被1和本身整除的数是质数
  3. 1和0不是质数，2是最小的质数。
  4. 2的倍数不是质数(2除外)
  5. 遍历一个数n是否是质数，只需要遍历到根号n即可，因为根号n是一个中间点，后面和前面重复。
const isPrime = n => {
    if(n < 2){
        return false;
    }else if(n === 2){
        return true;
    } else if(n % 2 === 0){
        return false;
    }
    let result = 0;
    for(let i = 2 ; i < Math.pow(n,0.5); i ++) {
        if(n % i === 0){
            result ++;
        }
    }
    if(result === 0) {
        return true;
    }else {
        return false;
    }
} 
const result = isPrime(99);
console.log(result);

24、两两交换链表中的节点

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

题解

解题思路

采用递归的方式，每次将current和next节点替换，下次递归是next.next节点。

例如：1 - 2 - 3 - 4

第一趟： 入口 1 1和2调换

第二趟： 入口3 3和4调换

代码

var swapPairs = function(head) {
    if(head === null || head.next === null) {
        return head;
    }
    let next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    return next;
};

5、最长回文子串

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

题解

什么是回文字符串？

看到这个题目，首先想到的可能就是什么是回文？可能都听说过这句话：上海自来水来自海上，就像这样，正着读和反着读都是一样的就叫做回文。那么根据上一句话的定义，回文字符串就是一个字符串正序和反序相同，比如说：abba是回文字符串，abbb这样就不是回文字符串。

什么是子串

子串可以说成是一个字符串的子集，既然是子集，那必然是一个集合，有多个。比如说abba这个字符串，那么它的子集有：a,b,ab,bb,ba,abb,abba，记得它自身也是它的子集之一。

解题思路

由上面我们已经知道了什么是一个回文字符串，什么是子串，那么究竟用什么方式来解这道题？

这道题使用纯遍历去找的话也是可以的，但是循环层数太多，至少要3层，时间复杂度彪高，很显然不是我们想要的解法，一种比较好的解法就是采用动态规划的方式，动态规划确定状态转移方程就可以很简单的得出答案，通过方程公式的解答很符合IT的思维。

状态如何定义？

动态规划第一点就是定义状态，我们来看这个题要找回文子串，既然是子串那么就必须要标记子串在主串中的位置。因此我们这样定义

                |-- true 
  dp[i][j]--
                |-- false

dp[i][j]表示这个子串的起点是i，终点是j，是一个s[i] - s[j]的子串。如果dp[i][j]为true，那么就认为字符串s中i - j这部分子串是回文的；如果为false就不是回文的。

列出状态转移方程

首先在一个字符串中，如果只是一个单独的字符，比如说a，那么它必然是回文的。我们当a字符在s串中所在的位置是i，即i == j，也就是说dp[i][j] = true。如何推出下一个？此时我们已经知道dp[i][j]是回文了，对于一个回文字符串来说，如果往它的开头和结尾同时添加一个相同的字符，那么也是回文的。比如说：往a开头和结尾同时加上b，那么字符串就变为aba，此时这个字符串也是回文的。

那么我们可以得出状态转移方程为：

if(s[i-1] === s[j + 1] ) {
    dp[i - 1][j + 1] = dp[i][j]
} else {
   dp[i - 1][j + 1] = false
}

得出状态转移方程，那么就可以写代码了。

代码

var longestPalindrome = function(s) {
  let dp = []
  let maxSize = 1
  let start = 0
  let end = 0
  for (let i = 0; i < s.length; i++) {
    dp[i] = []
    dp[i][i] = true
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true
      maxSize = 2
      start = i
      end = i + 1
    } else {
      dp[i][i + 1] = false
    }
  }
  for (let i = s.length - 1; i >= 0; i--) {
    for (let j = 0; j < s.length; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1]
        if (maxSize < j - i + 1 && dp[i][j]) {
          maxSize = j - i + 1
          start = i
          end = j
        }
      } else {
        dp[i][j] = false
      }
    }
  }
  return s.slice(start, end + 1)
}

写的比较粗糙。首先初始化dp，比如说单字符必然是回文的，双字符，如果s[i]和s[i + 1]相等，那么dp[i][i + 1]是回文的，值为true。

然后两层for循环遍历，根据初始化状态的dp得出全部的dp值，我是在dp的过程中，就保存了最长回文子串的i j 值，在最后直接通过slice方法得到。

done

动态规划的**还是用到了，实现容易了很多，但是因为在dp的过程中保存i和j的值，所以整体行数又增加了不少，粗糙了很多，后续可以优化下。

链表

在数据结构中线性表分为顺序表和链表两种。这两种在逻辑结构上都是线性表，在物理结构上有些不相同。

链表

一般来说组织数据的基本方式是数组，但是数组并不是最佳方式。在一些强类型语言中(C)，一般数组的长度是固定的，使用数组来存储数据的时候就必须开辟一段连续的内存空间，使用不完就会浪费。而链表则是当需要插入数据的时候就申请一段内存存储数据，每次都要申请内存，因此可以看出链表开辟的内存空间是不连续的。

另外，在JavaScript中的数组被实现成了对象，与其他语言的数组相比，效率低了很多。

链表的关键概念定义

  1. 链表是由一系列的节点组成的集合，每个节点都使用一个对象的引用指向它的后继，指向另一个节点的引用叫链。
  2. 链表元素靠相互之间的关系进行引用A->B->C，B并不是链表的第二个元素而是跟在A后面，遍历链表就是跟着链接，从链接的首元素一直到尾元素，但不包括头结点，头结点常常被称为链表的接入点。（链表的尾节点指向一个null节点）
  3. 对于单向链表来说，所有节点只有一个后继节点(尾节点的后继为null)。
  4. 对于双向链表来说，头节点只有一个后继节点，尾节点只有一个前驱节点，中间的节点有一个前驱几点和一个后继节点。

链表的增删

单向链表的插入操作

向单向链表中指定节点后插入一个节点，需要先让新节点指向指定节点的后继，然后指定节点的后继再指向新节点。

比如说在A节点后面插入一个新节点

newNode.next = A.next;
A.next = newNode
单向链表的删除操作

从单向链表中删除一个节点，需要将待删除节点的前驱节点指向待删除元素的后继节点。同时将删除元素指向null。

比如说删除A节点后面的一个元素

let Ref = A.next  //保存引用，至为null
A.next = A.next.next;
Ref = null;
双向链表的插入操作

双向链表中一个节点有两个指针引用，所以插入操作有一定的顺序，并且必须保证后继节点不被丢的情况下插入新节点

//比如说在A和B两个节点中插入一个C节点
A.next.prev = C
C.next = A.next
A.next = C
C.prev = A; 
//尾节点的插入操作
    //在A节点后面插入一个B节点
A.next = B
B.prev = A;
B.next = null;
双向链表的删除操作
//A->B->C把B节点删除。
B.prev.next = B.next;
B.next.prev = B.prev;
B.next = null
C.prev = null
//尾节点的删除操作
A.prev.next = null;
A.next = null;
A.prev = null;

代码实现

单向链表

class SingleLinkList {
        constructor(ele){
            this.ele = ele;
            this.next = null;
        }
        //创建头节点
        static createHead() {
            let headNode = new SingleLinkList("head");
            return headNode;
        }
        //查找链表中是否含有一个节点
        static find(linkList,item){
            let node = linkList;
            while(node) {
                if(node.ele === item){
                    return node;
                }
                node = node.next;
            }
            return false;
        }
        //向一个链表中插入一个节点
        static insert(linkList, item, newElement){
             let newNode = new SingleLinkList(newElement);
            let node = linkList;
            while(node){
                if(node.ele === item) {
                    newNode.next = node.next;
                    node.next = newNode;
                }
                node = node.next
            }         
        }
        //向一个链表中删除一个节点
        static remove(linkList, item){
            let node = linkList;
            while(node.next){
                if(node.next.ele === item){
                    let delNode = node.next;
                    node.next = node.next.next;
                    delNode.next = null;
                }
                node = node.next;
            }
        }
        //打印链表内容
        static toString(linkList){
            let linkListValues="",node = linkList.next;
            while(node){
                linkListValues += node.ele;
                node = node.next
            }
            return linkListValues;
        }
    }

双向链表

class DoubleLinkList {
        constructor(ele){
            this.ele = ele;
            this.next = null;
            this.prev = null;
        }
        //创建头节点
        static createHead(){
            return new DoubleLinkList('head');
        }
        //向一个链表中查找一个节点
        static find(linkList,item) {
            let node = linkList;
            while(node){
                if(node.ele === item){
                    return node;
                }
                node = node.next;
            }
            return node;
        }
        //插入一个节点
        static insert(linkList, item, newElement){
            let newNode = new DoubleLinkList(newElement);
            let node = linkList;
            while(node){
                if(node.ele === item){
                    if(node.next === null){
                        newNode.next = node.next;
                        newNode.prev = node;
                        node.next = newNode;
                    } else {
                        node.next.prev = newNode;
                        newNode.next = node.next;
                        node.next = newNode;
                        newNode.prev = node;
                    }
                    break;
                }
                node = node.next;
            }
        }
        //删除一个节点
        static remove(linkList, item){
            let node = linkList;
            while(node){
                if(node.ele === item) {
                    if(node.next !== null){
                        node.prev.next = node.next;
                        node.next.prev = node.prev;
                        node.next = null;
                        node.prev = null;
                    } else {
                        node.prev.next = node.next;
                        node.next = null;
                        node.prev = null;
                    }
                }
                node = node.next;
            }
        }
        //打印一个节点
        static toString(linkList){
            let linkListValues = "", node = linkList.next;
            while(node){
                linkListValues += node.ele;
                node = node.next;
            }
            return linkListValues;
        }
        //链表逆序输出
        static reverse(linkList){
            let node = linkList;
            while(node.next){
                node = node.next;
            }
            let reverseValues  = "";
            while(node.prev){
                reverseValues += node.ele;
                node = node.prev;
            }
            return reverseValues;
        }
    }

16、最接近的三数之和

题目

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题解

解题思路

这道题和三数之和非常像，就是用三数之和的解法，在过程中加上判断，从而找出最接近target的那个数。三数之和不懂的可以先看三数之和，判断很简单在代码里就可以看懂。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    let len = nums.length;
    let result;
    let diff;
    nums.sort((a,b) => a - b);
    for(let i = 0; i < len - 2; i ++) {
        let first = nums[i];
        let l = i + 1;
        let r = len - 1;
        while(l < r) {
            let second = nums[l];
            let thired = nums[r];
            let num = first + second + thired;
            if(num === target) {
                return num;
            }
            let numResult = Math.abs(num - target);
            if(num < target) {
                l ++;
            } else {
                r --;
            }
            if(result === undefined) {
                result = num;
                diff = numResult
            } else {
                
                if(diff > numResult) {
                    diff = numResult;
                    result = num;
                }
                
            }

        }
    }
    return result;
};

26、删除排序数组中的重复项

题目

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

题解

解题思路

采用一个set来标记数组中元素，如果在set中已经出现，使用数组的splice方法删除掉。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let set = new Set();
    for(let i = 0; i < nums.length; i ++) {
        if(set.has(nums[i])) {
            nums.splice(i, 1);
            i--;
        } else {
            set.add(nums[i]);
        }
    }
    return nums.length;
};

27、移除元素

题目

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

题解

解题思路

遍历数组，如果当前index元素与value元素相同，则使用数组的splice将元素删除

代码

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    for(let i = 0; i < nums.length; i ++){
        if(nums[i] === val) {
            nums.splice(i,1);
            i--;
        }
    }
    
    return nums.length;
};

冒泡排序

冒泡排序是最慢的排序算法之一，数据值会像气泡一样从数据的一端飘逸到另一端。

 const bubbleSort = arr => {
     let temp,len = arr.length;
     for(let i = 0; i < len -1; i++){
         for(let j = len - 1; j > i; j -- ){
            if(arr[j] < arr[j - 1]){
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
         }
     } 
     return arr;
 }
 console.log(bubbleSort([1,4,3,5,9,7,3,3,5,3,2]))

插入排序-C++

插入排序C++版

#include "iostream"

using namespace std;

void insert_sort(int arr[], int len);
int main()
{
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int len = sizeof(arr) / sizeof(int);
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << ' ';
  }
  cout << endl;
  insert_sort(arr, len);
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << ' ';
  }
  cout << endl;
}
//插入排序
void insert_sort(int arr[], int len)
{
  for (int i = 1; i < len; i++)
  {
    int j = i - 1;
    int k = arr[i];
    while (j >= 0 && k < arr[j])
    {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = k;
  }
}

判断一个单词是否是回文

回文字符串就是指：一个字符串正着和反着相同。

JavaScript中判断字符串是否是回文很容易，只需要转成数组反序然后再拼接回字符串就可以了。

这里我使用的是Point free的方式

/**
 * 
 * 判断一个单词是否是回文
 * 
 */

 const palindrome = str => {
     const split = str => str.split("");
     const reverse = arr => arr.reverse();
     const join = arr => arr.join("");
     const compose = (...fns) => fns.reduce((f,g) => (...args) => f(g(...args)));
     const result = compose(join, reverse, split)(str);
     return result === str;
 }
 const result = palindrome('abccbaa');
 console.log(result);

22、括号生成

题目

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题解

解题思路

生成n对括号，那么就是2n长度的字符串，使用递归的方式生成，在生成过程中使用left和right记录左括号与右括号的生成数量，需要注意的是一定是左括号先生成再生成右括号，右括号的生成条件必须是右括号的数量小于n并且左括号的数量大于右括号的数量。

代码

/**
 * @param {number} n
 * @return {string[]}
 */
function _gen(list, left, right, n, result) {
      if(left == n && right == n) {
            list.push(result);
            return; 
      }
      if(left < n) {
            _gen(list, left + 1, right, n, result + '(');
      }
      if(right < n && left > right) {
            _gen(list, left, right + 1, n, result + ')');
      }
}
var generateParenthesis = function(n) {
      let list = [];
      _gen(list, 0, 0, n, '');
      return list;
};

列表

列表是数据结构中最基础的数据结构，列表的形式在生活中也是随处可见的，比如说购物清单等等。

列表的基础特点

  • 元素不是很多
  • 不需要很长序列查找元素或者排序
  • 列表是一种最自然的数据组织方式

列表的关键定义以及专业术语

  • 列表往往是一组有序的数据。每个列表中的数据项称为元素，元素的数量受内存控制。

  • 不包含任何元素的列表称为空列表。

  • 列表是可以向下迭代的。

    • 访问元素时不必关心底层的数据结构
    • 增加和删除元素要比for更加灵活
    • 迭代器访问列表里的元素提供了统一的方法。

列表的代码实现

定义一个简单的列表

function List () {
    this.listSize = 0;  //列表元素的个数
    this.pos = 0;        //列表当前位置
    this.dataStore = [];  //初始化一个空数组来保存列表元素
}

上面这样的数据结构，一个列表就完成了。列表有哪些操作方法呢？

clear：清空所有的元素

//清空列表的所有元素
List.prototype.clear = function () {
    this.dataStore.length = 0;
    this.pos = this.listSize = 0;
}

find：查找指定元素

//查找指定元素
List.prototype.find = function(ele) {
    let dataStore = this.dataStore;
    for(let i = 0,len = dataStore.length; i < len; i ++){
        if(dataStore[i] === ele){
            return true;
        }
    }
    return false;
}

toString：返回列表的字符串形式

//返回列表字符串形式
List.prototype.toString = function () {
    return this.dataStore.toString();
}

insert：在现有元素指定元素后插入新元素

//在现有元素指定元素后插入新元素，如果没有指定元素则插入失败
List.prototype.insert = function(ele,newEle) {
    let dataStore = this.dataStore;
    for(let i = 0, len = dataStore.length; i<len; i++){
        if(dataStore[i] === ele && dataStore[i] !==dataStore[i+1] ){
            i++;
            this.dataStore[i] = newEle;
        }
        this.dataStore[i] = dataStore[i]
    }
    this.listSize ++;
}

append：在列表末尾插入新元素

//在列表元素末尾插入新元素
List.prototype.append = function(ele) {
    this.dataStore[this.listSize++] = ele;
}

remove：从列表中删除指定元素

//从列表中删除指定元素
List.prototype.remove = function(ele) {
    let dataStore = this.dataStore;
    for(let i = 0,len = dataStore.length; i < len ; i ++) {
        if(dataStore[i] === ele && dataStore[i] !==dataStore[i+1] ){
            i--;
        }
        this.dataStore[i] = dataStore[i]
    }
}

front：从列表的当前位置移动到下一个位置

//从列表的当前位置移动到第一个位置
List.prototype.front = function() {
    this.pos = 0;
}

end：从列表的当前位置移动到最后一个位置

//从列表的当前位置移动到最后一个位置
List.prototype.end = function () {
    this.pos = this.listSize;
}

prev：将当前位置前移一位

//将当前位置前移一位
List.prototype.prev = function(){
    this.pos --;
}

next：将当前位置后移一位

//将当前位置后移一位
List.prototype.next = function(){
    this.pos ++;
}

length：返回列表包含的元素个数

//列表包含元素的个数
List.prototype.length = function() {
    return this.listSize;
}

currPos：返回列表当前位置

//返回列表当前位置
List.prototype.currPos = function() {
    return this.pos;
}

moveTo：将当前位置移动至指定位置

//将当前位置移动至指定位置
List.prototype.moveTo = function(index) {
    if(index > this.listSize){
        return false;
    }
    this.pos = index;
}

getElement：返回当前元素

//返回当前元素
List.prototype.getElement = function () {
    return this.dataStore[this.pos];    
}

contains：判断列表是否包含该元素

//判断列表是否包含该元素
List.prototype.contains = function(ele) {
    let dataStore = this.dataStore;
    for(let i =0, len = dataStore.length; i < len; i ++) {
        if(dataStore[i] === ele){
            return true;
        }
    }
    return false;
}

12、 整数转罗马数字

题目

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: "III"

示例 2:

输入: 4
输出: "IV"

示例 3:

输入: 9
输出: "IX"

示例 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

题解

解题思路

由题目可知，这道题是把整数转换成罗马数字，并且有对应的数字，因此，这道题可以使用贪心的**来解，优先转换最大的，依次转换小的。

首先声明两个数组是数字和罗马数字的映射

let mapKey = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
let mapValue = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I'];

循环num做求余，终止条件就是num为0；

怎样优先找到最大的呢？循环mapKey就可以的，找到第一个小于num的，就是转成罗马字符最大的

while(mapKey[idx] > num) {
       idx ++;
 }

然后除去最大的mapKey值，得出有多少个mapValue，最终把结果拼接起来即可。

代码

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    let mapKey = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
    let mapValue = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I'];
    let idx = 0;
    let result = '';
    while(num !== 0) {
        while(mapKey[idx] > num) {
            idx ++;
        }
        let n = (num / mapKey[idx]) | 0;
        num = num % mapKey[idx];
        result += mapValue[idx].repeat(n);
    }
    return result;
};

栈

栈也是一种特殊的线性表。

栈是一种高效的数据结构，因为数据只能在栈顶删除或增加，操作很快。

栈这种方式在生活中体现的不是那么明显，在计算机中却使用很多，比如JavaScript中的函数调用栈等等。

栈的关键定义

  1. 栈内元素只能通过一端访问，这一端称之为栈顶(反之栈底)。
  2. 栈是一种后进先出的数据结构，就是说数据只能从栈顶进栈，只能从栈底出栈：LIFO(list-in-first-out)
  3. 插入新元素称为进栈、入栈或压栈，从栈中删除一个元素称为出栈或退栈。

代码实现

function Stack() {
    this.dataStore = [];    //保存栈内元素
    this.top = 0; //栈顶，标记可以插入新元素的位置
}

补充一下栈的操作方法

入栈操作

//入栈操作
Stack.prototype.push = function(ele) {
    this.dataStore.unshift(ele);
}

出栈操作

//出栈
Stack.prototype.pop = function(ele){
    return this.dataStore.shift();
}

返回栈顶元素

Stack.prototype.peek = function(){
    return this.dataStore[0];
}

清空栈

Stack.prototype.clear = function(){
    this.dataStore.length = 0;
}

返回栈的长度

Stack.prototype.length = function(){
    return this.dataStore.length;
}

实战一下：括号匹配

的字符只包含三种括号：花括号{ }、中括号[ ]、圆括号( )，即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法，判断该字符串是否有效，即字符串中括号是否匹配。括号匹配要求括号必须以正确的顺序配对，如 “{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等为正确的格式，而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均为不正确的格式。

function isPalindrome (word) {
    let wordArr = word.split("");
    let stack = new Stack();
    for(let i = 0, len = wordArr.length; i<len; i ++) {
        if(stack.length() === 0) {
            stack.push(wordArr[i]);
        } else {
            if(stack.peek() === wordArr[i]){
                stack.pop();
            }else{
                stack.push(wordArr[i])
            }
        }
    }
    if(stack.length() === 0){
        return true;
    } else {
        return false;
    }
}

找出下列正数组中的最大差值 

/**
 * 
 * 找出下列正数组中的最大差值
 * 
 */
const maxDiffData = arr => {
    if(arr.length == 0) {
        return;
    }
    let max = arr[0];
    let min = arr[0];
    arr.forEach(item => {
        item < max ? item < min ? min = item : void 0 : max = item;
    })
    return max - min;
}
let result = maxDiffData([10,5,11,7,8,9,20,1])
console.log(result);

数据结构导论

数据结构的用途

实际上数据结构对于程序员来说是一门重要的基本功，数据结构和算法可以称为程序员的内功心法。

数据结构可以有效的管理数据对象。

在前段开发中会遇到各种各样的性能问题，为了解决效率问题，使用数据结构可以有效的提升性能。

面试过程中面试官会问数据结构和算法相关的问题。

对于前端开发工程师来说，数据结构需要了解到什么层次呢？

首先必须要了解常用的数据结构，其次在传统的前段开发过程中，接触最多的就是DOM，而DOM就是数据结构中的树结构

当需要编写一些自己的前端控件的时候，对数据结构仍然有很大的要求。

如果要写前端方面的游戏的话，数据结构也是不可缺少的。

什么是数据结构呢？

首先数据结构起源于程序设计，数据结构是计算机用来存储和组织数据的方式，数据结构不能让开发者学会编码但是会提供一种重要的编程**，从而获得更好的编程思路。、

数据结构有两种说法

  1. 广义的说法：数据结构 = 数据存储 + 算法
  2. 狭义的说法：数据结构 = 数据的存储。

计算机中的计算：

  1. 数值相关的计算：1 + 1 = 2 等
  2. 非数值相关的计算： 计算地图上两点之间的距离、计算机和人类围棋比赛。

总结：数据结构是介于数学、硬件和软件三者之间的一门核心学科。

数据结构中的几个基本概念

  • 数据
  • 数据对象
  • 数据元素
  • 数据项

数据

数据是用来描述计算机事物的一种符号，在计算机当中，所有的运算都是依赖这种符号的。这种符合可以依赖到计算机当中并且可以让计算机识别

举例子来说：数据不仅仅包括整型，字符串这种类型，还包括声音、图像、视频等这些非数值类型

数据对象

数据对象是性质相同的数据元素的集合。

数据元素

数据元素是一种有一定意义的最基本的数据单位。

当我们使用计算机来处理数据的时候，数据元素通常被我们作为一个整体来处理。这个整体可以称为记录。

数据项

数据项是组成数据的最小单位。

数据结构就是相互之间存在一种或者多种特定关系的数据

关系

数据与数据之间的关系被称为结构，数据结构和算法结合是非常紧密的。

对于结构来讲分为两种：

  • 逻辑结构：反应数据元素之间的逻辑关系。简单的说就是谁在谁之前，谁在谁之后。
  • 存储结构：数据结构的存储关系涉及到了计算机的底层，存储结构就是数据结构在计算机内存当中以一种什么样的形式进行表示。

算法：狭义的说就是对数据进行一种怎么样的操作。

按照逻辑结构来分类：

  • 集合(无逻辑结构)
  • 线性结构(线性表)
  • 一维数组
  • 队列
  • 栈
  • 非线性结构
    • 树
    • 图
    • 多维数组

按照存储结构分类：

  • 顺序存储结构
  • 链式存储结构
  • 索引存储结构
  • 散列存储结构

集合

在集合中任何两个元素都是没有逻辑关系的，形式比较松散。

例子：火车站广场的游客，可以作为一个元素，每一个游客之间没有任何关系。

线性结构

按照一定方式排列的形式就是线性结构，并且相邻元素之间按照元素独有的形式形成了前后衔接的结构。

树型结构

树型结构的特定就是分叉，在计算机中树型结构可以系列为一课倒置的树(从树根到各个分叉)。

树型结构有分支并且层次分明。

树型结构中的节点除了根节点之外，有且仅有一个父节点，有多个子节点，是一对多的关系。

图状结构

在图中节点与节点之间是多对多的关系。

存储结构

计算机内存相关的知识

  • 内存的原理与构造
  • 地址、指针、引用
  • 存储结构和内存管理

内存的原理和构造

在计算机当中，内存是一个很重要的部件，那么内存是怎样存储数据的呢？内存本身就像在一个长条纸上打了很多格子。数据就存储在格子当中，并且每一个格子中只可以存储一个字节的数据。通过数据都是由多个字节组成的，因此一个数据就会占用内存中一个或多个连续的格子。

比如说字符类型，一个字符就是一个字节，只占用内存中的一个格子，整型，一个整型是4个字节，就会占用内存中的四个格子。
对于更复杂的数据类型，占用格子的方式会更加的麻烦，那么怎么管理这个数据呢？

为了方便计算机的管理，计算机对内存进行了编号，也就是内存的地址。通常第一个格子的编号为0，第一个格子的编号为1，第二个格子编号为2，以此类推。
最后一个编号也可以表示为内存的大小。

计算机所能管理的内存的大小受制于CPU的型号还有操作系统的具体实现

通常在理论中内存是可以向后一直延伸的，在计算机中内存的编号被称为内存的地址，地址就表示每一个小格子在内存中实际的位置，通常使用十六进制来表示地址
例如：0号地址 0X0、二号地址 0X1

指针：
内存是存储数据的，也就是说内存中存放的数据的某一个字节，而指针也是一块内存，只不过与存储数据的内存不同的是指针所在的内存中存储的是另外一块内存的地址。

指针是计算机内存管理当中一个非常重要的概念。

指针对于我们前端工程师来说比较偏底层了，在前端中是另外一个是引用，引用是对指针的一个高级封装(这种只体现在高级语言中：js)，前端中对象的操作就是引用。

怎样在内存中来表示内存的存储关系？

在软件开发中线性结构是最常见的存储结构，线性结构通常在内存中使用两种形式来表示：一种是数组(顺序表)，一种是链表

  • 数组在内存中是一整段的连续的内存空间。

  • 对于链表来讲，一个节点分为两个部分：数据段和指针。
    数据段存放需要保存的数据，指针段指向后继节点的地址。

顺序表和链表的比较

  1. 存储结构：顺序表定义必须是定长的数据，链表的长度伸缩性大
  2. 查找数据：顺序表中可以直接通过索引直接找到一个值，而在链表中还需要从前向后循环遍历找到需要查找的值。
  3. 增删数据：顺序表在增加一个数据和删除一个数据的时候，需要改变修改位置之后的所有数据的位置，而链表只需要把指针段的指向修改一下即可。
  4. 选择结构：当我们的数据是确定个数的时候，可以使用顺序表，查找效率比较高，如果数据的个数不确定(在以后可能会删除或者增加数据)使用链表会更方便。
  5. 结构：无论是链表还是顺序表存储结构都是线性结构。

线性表的延伸结构

栈结构

在线性表中每一个元素是可以被读被写被删的，操作线性表的任何元素都不不受限制的，但是对于栈来讲是有严格的要求的，栈可以说成是一端开口的容器，例如桶装薯片，只能从桶的一端出薯片，并且后放进去的薯片先吃到。可以说栈结构是一种被限制操作的线性表。

可以操作栈的一端称为栈顶，反之称为栈底，栈操作遵循后进先出的规则(last in first out),当向栈中存储数据的操作叫做入栈，向栈中取数据的操作叫做出栈

可以看出第一个元素在栈底位置，最后一个进入的元素在栈顶的位置。

队列结构

队列和栈了类似，也是被限制的线性表。

队列就像我们买票的通道，先排队的先买票，后排队的只能等前面的人买完票之后才能买票。

队列操作遵循先进先出的队则(first in first out),队列增加一个数据叫做入队，删除一个数据叫做出队，入队的一端叫做队尾，出队的一段叫做队首，

队列与栈的比较
  1. 结构：都是线性表
  2. 操作规则：栈是后进先出规则；队列是先进先出规则。

串

把一些相同的元素串在一起，通常遇到最多的就是字符串，字符串的本身就是字符数组，字符数组中的每一个存储格子就是一个字符。

对于字数数组来讲，有一个起始位置，有一个结束位置。起始位置是字符数组的开始，结束位置是用来标记字符串的结束，如果没有结束位置那么计算机在处理串的时候就会把后面不属于串的数据也处理掉，因此必须要给定一个^符号作为结束位。

对于串来讲，在操作的时候一般是操作成批的字符，例如子串。

树

数据结构中的树由若干个节点组成，除了根节点外，每一个节点都可以有一个父节点和多个子节点。节点与节点之间所连成的线叫做边。

在一个有n个节点的树中有n-1条边。

一个节点有几个节点，那么该节点的度就是几。

树的遍历

  1. 深度优先遍历
    1. 先序遍历
    2. 中序遍历
    3. 后序遍历
  2. 广度优先遍历
    1. 层序遍历
二叉树

二叉树是最多只有两个子节点、最少有0个节点的树。

满二叉树是所有节点除了最后一层都达到两个子节点的二叉树。

完全二叉树是除了最后一层，从根节点到倒数第二层是满二叉树的树。满二叉树也是完全二叉树

图

图是由顶点的集合和边的集合组成。顶点与顶点之间使用边连接，在图中顶点与顶点之间是多对多的关系。在图中可以对边进行赋值，值可以称为两个顶点之间的距离，也叫做边的权。

图分为有向图和无向图。
具有方向的边所构成的图就是有向图。

树的节点可以是空集，但是图不行，图不存在空图。

数组去重

第一种：ES6新特性Set

Set是最简单的数组去重的方法，Set底层实现是hash表，借助于hash表的key值是唯一的特性达到数组去重的目的，Set内置Iterator接口，因此可以使用扩展运算符把set展开。

const unique = arr => [...new Set(arr)];
 console.log(unique([1,1,2,2,3,4,5,5,5]))

第二种：forEach

事先定义一个数组，遍历目标数组，每次判断新数组中是否存在数据项，若有则不进行任何操作，若无则添加进新数组。

const unique = arr => {
    let newArr = [];
    arr.forEach(item => {
        if(!newArr.find(x=> x === item)){
            newArr.push(item);
        }
    })
    return newArr;
}
const result = unique([1,2,3,4,5,1,2,3,5,3,2,4]);
console.log(result);

第三种：reduce

第三种方式和第二种差不多，都是借助一个额外的数组。

const unique = arr => arr.reduce((arr,item) => {
    if(!arr.find(x=> x === item)){
        arr.push(item);
    }
    return arr;
},[])
const result = unique([1,2,3,4,5,1,2,3,5,3,2,4]);
console.log(result);

第四种：对象

第四种是借助一个对象和一个数组，把数组中已有的数在对象中标识出来。

const unique = arr => {
    let obj = {};
    let newArr = [];
    for(let i = 0,len = arr.length; i < len; i ++){
        if(!obj[arr[i]]){
            obj[arr[i]] = '1';
            newArr.push(arr[i]);
        }
    }
    return newArr;
}
const result = unique([1,2,3,4,5,1,2,3,5,3,2,4]);
console.log(result);

插入排序

类似于人们按数组或字母顺序对数据进行排序，后面的要为前面的腾位置。

const insertSort = arr => {
    let len = arr.length,temp,idx;
    for(let i = 1; i < len; i ++){
        temp = arr[i];
            idx = i;
            while(arr[idx -1] > temp){
                arr[idx] = arr[idx-1];
                idx--;
            }
            arr[idx] = temp;
    }
    return arr;
}
console.log(insertSort([1,4,3,5,9,7,3,3,5,3,2]))

字典

字典

字典是以一种键值对形式存储的，就向我们的电话号码簿一样，要找到一个电话时，名字找到了电话号码也就找到了。

JavaScript的Object类就是以字典的形式设计的。我们要实现一个Dictionary类，这样会比object方便：比如显示字典中的所有元素，对属性进行排序等。

字典概念定义

  1. key-value键值对

代码实现

class Dictionary {
    constructor(){
        this.dataStore = [];
    }
    //添加一条数据
    add(key,value){
        this.dataStore[key] = value;
    }
    //查找
    find(key){
        return this.dataStore[key];
    }
    //删除
    remove(key){
        delete this.dataStore[key];
    }
    //显示所有
    showAll(){
        let str = "";
        Object.keys(this.dataStore).forEach(item => {
            str += `${JSON.stringify(item)}\n`; 
        })
        return str;
    }
    //字典的长度
    count(){
        return Object.keys(this.dataStore).length;
    }
    //清空字典
    clear(){
        Object.keys(this.dataStore).forEach(item => {
            delete this.dataStore[item];
        })
    }
}

3. 无重复字符的最长子串

无重复字符的最长子串

题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

题解：这道题找的字符串中无重复的最长的字串，可以采用滑动窗口的**。使用两个变量分别表示滑动窗口的头和尾，遍历字符串先判断当前遍历的这个字符是否在滑动窗口中，如果不在则滑动窗口的头部加1，如果不在(判断是否存在滑动窗口中，会返回字符在滑动窗口的位置)滑动窗口的尾部为该字符在活动窗口中的位置加1。判断当前滑动窗口的长度只需要使用头部减去尾部就可以得到，而当前滑动窗口的大小就是当前计算出的无重复字符的最长字串的大小。找出整体的最大值就可以了。

const is = (s, i, j, item) => {
    for(let k = i; k < j; k ++) {
        if(s[k] === item) {
            return k;
        }
    }
    return false;
}
var lengthOfLongestSubstring = function(s) {
    let i = 0, j = 0;
    let max = 0;
    let len = s.length;
    while(j < len) {
        let k = is(s,i,j,s[j]);
        if(typeof k === 'boolean'){
            j++;
            max = Math.max(max,j - i);
        }else {
            i = k + 1;
        }
    }
    return max;
};

代码中is方法就是用来判断当前字符是否存在滑动窗口中，lengthOfLongestSubstring函数中用来遍历字符串，通过is方法判断是否存在来做不同的逻辑。当is的返回值为false时，说明滑动窗口中没有该字符； 当滑 动 窗口为数字的时候，就说明滑动窗口中有该数字，再做滑动窗口尾端++的情况。

28、 实现 strStr()

题目

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

题解

解题思路

这道题做的时候有点不像写算法了(是真不像)，直接用语言的API了，也没有重新一遍的激情。解题思路还是字符串的匹配操作，可以利用KMP匹配规则进行匹配，匹配到了返回响应的索引，匹配不到返回-1

代码

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle)
};

归并排序-C++

归并排序C++版

#include <iostream>

using namespace std;

void merge_sort(int *arr, int len);
void merge(int *arr, int *L, int leftLen, int *R, int rightLen);
// 主函数
int main()
{
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int len = sizeof(arr) / sizeof(int);
  merge_sort(arr, len);
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}
// 归并排序
void merge_sort(int *arr, int len)
{
  if (len < 2)
  {
    return;
  }
  int mid = len / 2;
  int *L = new int[mid];
  int *R = new int[len - mid];
  for (int i = 0; i < mid; i++)
  {
    L[i] = arr[i];
  }
  for (int i = mid; i < len; i++)
  {
    R[i - mid] = arr[i];
  }
  merge_sort(L, mid);
  merge_sort(R, len - mid);
  merge(arr, L, mid, R, len - mid);
}

void merge(int *arr, int *L, int leftLen, int *R, int rightLen)
{
  int i = 0, j = 0, k = 0;
  while (i < leftLen && j < rightLen)
  {
    if (L[i] < R[j])
    {
      arr[k++] = L[i++];
    }
    else
    {
      arr[k++] = R[j++];
    }
  }
  while (i < leftLen)
  {
    arr[k++] = L[i++];
  }
  while (j < rightLen)
  {
    arr[k++] = R[j++];
  }
}

选择排序

从数组的开头开始，将第一个元素和其他元素比较，最小的元素会被放到数组第一个位置，再从第二个位置继续。

const selectionStor = arr => {
    let temp,
        min,
        len = arr.length;
    for(let i = 0; i < len -1; i ++){
        min = i;
        for(let j = i+1; j < len ; j ++){
            if(arr[j]<arr[min]){
                min = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;

    }
    return arr;
}
console.log(selectionStor([1,4,3,5,9,7,3,3,5,3,2]))

希尔排序

希尔排序是对插入排序的改进。插入排序是比较相邻的元素，而希尔排序是比较相对较远的位置。

它会首先比较较远的元素而非相邻的元素。让元素尽快回到正确的位置。通过定义一个间隔序列来标识在排序过程中进行比较的元素间隔。

const shellSort = arr => {
    //动态
    let len = arr.length,
        h = 1,
        temp,
        idx;
    //动态确定间隔值
    while(h < len/3){
        h = 3 * h +1;
    }
    while(h >=1){
        for(let i = h; i < len; i ++){
            temp = arr[i];
            idx = i;
            while(arr[idx - h] > temp){
                arr[idx] = arr[idx - h];
                idx -=h;
            }
            arr[idx] = temp;
        }
        h = (h-1) /3;
    }
    return arr;
}
console.log(shellSort([9,8,7,6,5,4,3,2,1]))

选择排序-C++

选择排序C++版

#include "iostream";

using namespace std;
//选择排序
void select_sort(int * arr, int len)
{
  for (int i = 0; i < len; i++)    //控制选择排序的次数
  {
    int index = i;     //index的值始终是最小值的索引
    for (int j = i + 1; j < len; j++)  //循环找出最小的
    {
      if (arr[j] < arr[i])
      {
        index = j;
      }
    }
    if (index != i)   //如果最小值不是在头部，那么把最小值和头部值交换。
    {
      int temp = arr[i];
      arr[i] = arr[index];
      arr[index] = temp;
    }
  }
}
int main()
{
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int len = sizeof(arr) / sizeof(int);
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << ' ';
  }
  cout << endl;
  select_sort(arr, len);
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << ' ';
  }
  cout << endl;
  return 0;
}

25、K 个一组翻转链表

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

题解

解题思路

反转链接的升级版，k个一组，当遍历链表的时候，首先要记录经历的节点数，如果到了k个，采用反转链表的方式反转一下，直到循环完毕即可。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */

var reverseKGroup = function(head, k) {
    if(!head) {
        return head
    }
    let node = head, pre = null
    let result = new ListNode()
    result.next = node;
    let temp = result;
    while(node) {
        let preNode = node
        let lastNode = node;
        let n = 0;
        while(n < k && lastNode) {
            lastNode = lastNode.next;
            n ++;
        }
        let left = preNode;
        let right = lastNode;
        if(n === k) {
            while(left !== right) {
                let next = left.next
                left.next = pre;
                pre = left;
                left = next;
            }
            preNode.next = right
            temp.next = pre;
            temp = preNode;
            pre = preNode;
        }
        
        node = lastNode
    }
    return result.next
    
};

快速排序-C++

快排C++版

#include <iostream>

using namespace std;
void quick_sort(int arr[], int l, int r);
int main()
{
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int len = sizeof(arr) / sizeof(int);
  quick_sort(arr, 0, len - 1);
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << ',';
  }
  cout << endl;
  return 0;
}
// 快速排序
void quick_sort(int arr[], int l, int r)
{
  if (l < r)
  {
    int left = l, right = r, target = arr[left];

    while (left < right)
    {
      while (left < right && arr[right] > target)
      {
        right--;
      }
      if (left < right)
      {
        arr[left] = arr[right];
      }
      while (left < right && arr[left] < target)
      {
        left++;
      }
      if (left < right)
      {
        arr[right] = arr[left];
      }
    }
    arr[left] = target;
    quick_sort(arr, l, left - 1);
    quick_sort(arr, left + 1, r);
  }
}

散列表(哈希表)

散列表

散列表又称为哈希表，专注于存储数据的结构，散列表类似于key-value的结构存储数据，插入、删除和取用速度非常的快(时间复杂度O(1))，但是如果在散列表中查询最大值和最小值，效率就很低了。

JavaScript散列表基于数组设计，理想情况散列函数会将每一个键值映射为唯一索引，数组长度有限制，更现实的策略是将键均匀分布。

数据长度是预先设定的，可以随时增加，所有元素根据和该元素对应的键，保存数组特定位置。

即时使用高效的散列函数，仍然存在连个键值相同的情况，这种现象称为碰撞。

解决碰撞的方法

1.让散列表的长度为质数

由于散列函数一般是对一个数取余，如果不是质数可能会多次得到相同的key值，碰撞次数增大，如果是质数，极大的减少得到相同的key值减少碰撞次数。

2.开链法

当存储数据出现相同的key值的时候，在key的位置开辟一个链表结构用于存储数据，这种方式就叫做开链法。

3.线性探测法

线性探测法是一种开放寻址散列，当存储数据散列的时候反向得到的key值已经有了数据，那么存储数据的key值就+1，直到找到key值没有数据存储再把当前数据存进去。这种方式必须要保证散列表的长度必须要大于数据的数量。

代码实现

第一种方式就是使用数组长度为质数的方式，使用除留余数法找出数据对应的key值。

class HashTable {
        constructor(){
            this.table = new Array(137);
        }
        //质数法
        simpleHash(data) {
            //除留余数法
            let total = 0;
            for(let str of data) {
                total += str.charCodeAt(str);
            }
            return total % this.table.length;
        }
        put(data){
            let pos = this.simpleHash(data);
             this.table[pos][index] = data;
        }
        get(key){
            return this.table[key];
        }
        showDistro(){
            for(let i = 0; i < this.table.length; i ++) {
                if(this.table[i] !== undefined){
                    console.log('key->' + i + "  value->" + this.table[i]);
                }
            }
        }
    }

这种方式质数的方式还是不怎么好，key分配的不均匀，可以使用换那算法让key值分配的均匀一些

betterHash(data) {
            //换那算法
            // 在每次得到total的时候乘上一个质数，这样就会使拿到的键稍微均匀一些。
            const H = 31;
            let total = 0;
            for(let str of data) {
                total +=H * total + str.charCodeAt(str);
            }
            if(total < 0){
                total += this.table.length;
            }
            return total % this.table.length;
        }

更为使用的方式是开链法，如果有key发生碰撞，则开辟一个链表，把key值相同的数据存放在链表里面。

首先开辟链表

buildChians(){
    for(let i = 0, len = this.table.length; i < len; i ++) {
        this.table[i] = new Array();
    }
}

修改一下put方法

let pos = this.simpleHash(data);
let index = 0;  //链表的索引
if(this.table[pos][index] === undefined) {  //判断当前位置是否有值，没有就插入，有就找到没有为止
    this.table[pos][index] = data;  
} else {
    while(this.table[pos][index] !== undefined){
        ++index;
    }
    this.table[pos][index] = data;
}

线性探测法主要适用于散列表的长度大于数据的数量。当数据的key存在数据的时候就让key++，直到找到key没有数据，把当前数据存放进去。

 let pos = this.simpleHash(data);
//线性探测法
if(this.table[pos] === undefined) {
    this.table[pos] = data;
} else {
    while(this.table[pos] !== undefined){
        pos++;
    }
    this.table[pos] = data;
}

随机生成指定长度的字符串

在程序中定义一个字符集合，通过随机数随机选取集合中的一个。循环拼接成指定长度。

const randomLen = n => {
    const setStr = 'abcdefghijklmnopqrstuvwxyz1234567890';
    let result = "";
    for(let i = 0 ; i < n ; i ++) {
        result += setStr.charAt(Math.random() * setStr.length);
    }
    return result;
}
const result = randomLen(10);
console.log(result);

21、合并两个有序链表

题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

题解

解题思路

由于是合并两个链表，而是是有序，所以首先对两个链表统一遍历，终止条件就是任何一方到尾部，在遍历过程中判断节点值的大小往新开的链表上衔接。遍历完了之后两个链表要么都遍历完了，要么有一个剩余，然后分别遍历两个链表，把剩余的节点连接到新链表上。最终新链表就是合并并排序好的链表了。

代码

var mergeTwoLists = function(l1, l2) {
    if(!l1){
        return l2;
    }
    if(!l2){
        return l1;
    }
    let tempNode = new ListNode("head");
    let temp = tempNode;
    while(l1 !== null && l2 !== null){
        let node = new ListNode();
        if(l1.val <= l2.val){
            node.val = l1.val;
            tempNode.next = node;
            tempNode = node;
            l1 = l1.next;
        } else {   
            node.val = l2.val;
            tempNode.next = node;
            tempNode = node;
            l2 = l2.next;
        }
    }
    while(l1 !== null){
        let node1 = new ListNode();
        node1.val = l1.val;
        tempNode.next = node1;
        tempNode = node1;
        l1 = l1.next;
    }
    while(l2 !== null){
        let node2 = new ListNode();
        node2.val = l2.val;
        tempNode.next = node2;
        tempNode = node2;
        l2 = l2.next;
    }
    return temp.next;
};

6、Z 字形变换

题目

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

题解

还好这道题转换的是行数而不是列数，如果是列数的话真不知道该怎么办了。

规定是行数，那么这道题就是一道规律的题。

规律如何来？

竖着排成Z的形状，既然已经知道了多少行，比如说有n行，那么是不是就可以从第1行到第n行依次放入一个字母，当放到n行的时候转方向继续将字母放入数组，到1一行的时候再转方向将字母放入数组，知道所有的字母遍历完毕。

这样我们就发现每一个数组中存放的字母就是对应的行的字母，然后依次将字母连接起来即可。

代码

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if(numRows === 1) {
        return s;
    }
    let len = s.length;
    let arr = [];
    let idx = 0;
    let flag;
    let result;
    for(let i = 0; i < len; i ++) {
        arr[idx] =  arr[idx] || [];
        arr[idx].push(s[i]);
        if(idx === numRows - 1) {
            flag = true;
        } else if(idx === 0) {
            flag = false
        }
        if(flag) {
            idx --
        } else {
            idx ++;
        }
    }
    result = arr.reduce((str, item) => str += item.join(''), "");
    return result;
};

18、四数之和

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题解

解题思路

之前写过三数之和，已经很明白这些n数之和的套路，我的解题方法是，将四数之和多加一次循环，转换成三数之和，然后按照三数之和的逻辑解题。值得欣赏的是处理边界的代码，借鉴的网上大佬的，真的很优雅。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    let len = nums.length;
    let result = [];
    nums.sort((a,b) => a - b);
    for(let i = 0; i < len - 3; i ++) {
        let first = nums[i];
        if(i > 0 && nums[i] === nums[i - 1]) continue;
        for(let j = i + 1; j < len; j ++) {
            let secound = nums[j];
            let r = len - 1;
            let l = j + 1;
            if(j > i + 1 && nums[j] === nums[j - 1]) continue;
            while(l < r) {
                let left = nums[l];
                let right = nums[r];
                let temp = first + secound + left + right;
                if(temp < target) {
                    l ++;
                } else if(temp > target) {
                    r --;
                } else {
                    result.push([first,secound,left, right])
                    while(l < r && nums[l] === nums[l + 1]) {
                        l ++;
                    }
                    while(l < r && nums[r] === nums[r + 1]) {
                        r --;
                    }
                    l++;
                    r--;
                }
            }
        }
    }
    return result
};

冒泡排序-C++

冒泡排序C++版

#include <iostream>

using namespace std;

int main()
{
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int len = sizeof(arr) / sizeof(int);     //获取数组的长度
  int temp;
  for (int i = 0; i < len; i++)      
  {
    for (int j = len - 1; j > i; j--)    
    {
      if (arr[j] < arr[j - 1])
      {
        temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
  }
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << ',';
  }
  cout << endl;
  return 0;
}

15、 三数之和

题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题解

思路

三数之和，首先想到的最简单的解法就是和两数之和一样的暴力解法，直接3层循环搞定。但是，不能，毕竟要做一个有追求的前端。

回想起写两数之和的时候使用hash表将O(n²)的时间复杂度降到了O(1)，这个可不可以呢？显然可以，但是不能这样做，因为会出现重复的现象。

首先我们需要将这个数组排序一下，然后遍历一次可以得到三数之和的第一个值，在循环中采用双指针的方法。由于是排序好的，两个指针指向剩余的头和尾，当和小于目标值的时候让left ++，当和大于目标值的时候让right --，直到两个指针碰面，如果找到就找到了， 没找到就是没有，继续下一轮寻找。

这里可能会出现重复的现象，所以在比较的时候，如果两个相邻的数相同，则使用while略过。

代码如下：

代码

var threeSum = function(nums) {
      nums.sort((a, b) => a - b);
      let result = [], i = 0, len = nums.length;
      while(i < len - 1) {
            let j = i + 1, k = len -1;
            let a = nums[i];
            while(j < k) {
                  let b = nums[j];
                  let c = nums[k];
                  let sum = a +b + c;
                  if(sum === 0) {
                        result. push([a,b,c])
                  }
                  if(sum <= 0) {
                        while(nums[j] == b && j < k) {
                              j ++;
                        }
                  }
                  if(sum >= 0) {
                        while(nums[k] == c && j < k) {
                              k --;
                        }
                  }
            }
            while(nums[i] == a && i < len -1) {
                  i ++;
            }
      }
      return result;
}

队列

队列是一种特殊的线性表。

队列在生活中也是无处不在：比如说在银行排队的人群，排在最前面的人第一个办理业务，新来的人在后面排队，直到轮到他们为止。

队列的关键定义

  1. 队列只能在队尾插入元素，在队首删除元素，是一种典型的先进先出(First-in-First-out)的数据结构。
  2. 插入新元素称作入队，删除一个新元素称作出队。
  3. 当队列只规划了空间，但是没有元素在里面，这样的队列叫做空队列。
  4. 当队列中只有一个元素的时候，即这个元素又是队首也是队尾。

有一种特殊的情况，在删除元素不必遵守先进先出的约定，比如急诊。这种应用我们需要优先队列的数据结构来模拟。

队列的用途

队列被用在很多地方，比如任务队列，打印任务池，提交操作系统执行的一些列流程。

代码实现

function Queue() {
    this.dataStore = [];
}

这样一个队列就创建完成了，来为它补充一些操作方法

向队尾插入一个元素

Queue.prototype.enqueue = function (ele) {
    return this.dataStore.push(ele);
}

删除队首元素

Queue.prototype.dequeue = function () {
    return this.dataStore.shift();
}

读取队首元素

Queue.prototype.getFront = function () {
    return this.dataStore[0];
}

读取队尾元素

Queue.prototype.getEnd = function () {
    return this.dataStore[this.dataStore.length - 1];
}

显示列表中所有的元素

Queue.prototype.toString = function () {
    return this.dataStore.toString();
}

判断队列是否为空

Queue.prototype.isEmpty = function () {
    this.dataStore.length === 0 ? true : false;
}

实战一下：方块舞的舞伴分配问题

当男男女女来到舞池, 他们按照自己的性别排成两列. 当舞池中有地方空出来时, 选两个队列中的第一个人组成舞伴. 他们身后的人各自向前移动一位, 变成新的队首. 当一对舞伴迈入舞池时, 主持人会大声喊出他们的名字. 当一对舞伴走出舞池, 且两排队伍中有任意一队没人时, 主持人也会把这种情况告诉大家。

let manDancers = new Queue();
let womanDancers = new Queue();
manDancers.enqueue("小张");
manDancers.enqueue("小明");
womanDancers.enqueue("小红");
womanDancers.enqueue("小绿");
function getDancers(){
    return `♂${manDancers.dequeue()} ♀${womanDancers.dequeue()}`
}
console.log(getDancers());
console.log(getDancers());

优先队列

在队列中有一种特殊情况：在删除元素不必遵守先进先出的约定，比如急诊。这种应用我们需要优先队列的数据结构来模拟。

这种情况存在的时候就必须要使用优先队列：出队的时候不再遵循先进先出，而是根据优先级出队。

使用优先队列最基本的条件就是，每一个元素必须有特定的优先级

function Patient(name,code){
    this.name = name;
    this.code = code;
}

有限队列就不可以使用上面那种出队的方式，要重新定义一下。

Queue.prototype.dequeue = function(){
    let idx = 0;
    for(let i = 0, len = this.dataStore.length; i < len; i++){
        if(this.dataStore[i].code > this.dataStore[idx].code) {
            idx = i;
        }
    }
    return this.dataStore.splice(idx,1);
}

打印输出也要重新定义一下

Queue.prototype.toString = function(){
    var retStr = "";
    for(let i = 0, len = this.dataStore.length; i < len; i ++){
        retStr += this.dataStore[i].name + 'code:' + this.dataStore[i].code + '\n';
    }
    return retStr;
}

JavaScript中图的实现

图的概念

我们接触最多的就是地图，什么是图，可以想想一下我们国家的铁路，各条铁路相互连接相互交错，就构成了图。在计算机中，图就是顶点和边组成的数据结构。

图的关键概念定义

  1. 图由边的集合及顶点的集合组成。每一个城市就是一个顶点，每一个道路就是一个边。

  2. 顶点也有权重，也称为成本。如果一个图的顶点对是有序的，则称之为有向图。在对有向图中的顶点排序后，便可以在两个顶点之间绘制一个箭头

  3. 有向图表明了顶点的流向。流程图就是一个有向图的例子。

  4. 如果图是无序的，则可以称之为无序图或无向图。

  5. 从一个节点走到另外一个节点的这一组边称为路径。路径中所有的顶点都由边连接。路径的长度用路径中的第一个顶点到最后一个顶点之间
    边的数量表示。指向自身的顶点组成的路径为环，环的长度为0。

  6. 圈是至少有一条边的路径，且路径的第一个顶点和最后一个顶点相同。无论有向图还是无向图只要没有重复顶点的圈就是一个简单圈，除了第一个

  7. 和最后一个顶点外，路径的其他顶点有重复的圈称为平凡圈。

  8. 如果两个顶点之间有路径，那么这两个顶点之间就是强连通的，如果有向图的所有顶点都是强连通的，那么这个有向图也是强连通的。

邻接表

在图的数据结构中，需要维护一张邻接表，邻接表中存储的是顶点与相邻顶点连线的映射。

图的搜索

  1. 深度有限搜索

    深度优先搜索可以说是不撞南墙不回头的所有，一条路走到头，无路可走然后再回来走另外一条路。

  2. 广度优先搜索

    广度优先搜索是分散式搜索，每次搜索都是搜索该节点周围的所有节点。地毯式把所有节点搜索完毕。

代码实现

class Graph{
    constructor(v){
        this.vertices = v;
        this.edges = 0;     //图的边
        this.adj = {};
        this.set = new Set();
        this.defeTo = []; //最短路径的所有的边
    }
    //加点加边
    addEdge(v,w){
        if(!(this.adj[v] instanceof Array)){
            this.adj[v] = [];
        }
        if(!(this.adj[w] instanceof Array)){
            this.adj[w] = [];
        }
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges ++;
    }
    //显示图
    showGraph(){
        console.log(this.adj)
        Object.keys(this.adj).forEach(adj => {
            let edges = "";
            for(let item of this.adj[adj]){
                    edges += item + ' ';
            }
            console.log(adj + '->' + edges);
        })    
    }
    //深度优先遍历
    dfs(v){
        if(this.adj[v] != undefined){
            console.log(v + "节点已经被访问");
        }
        this.set.add(v);
        this.adj[v].forEach(item => {
            if(!this.set.has(item)){
                this.dfs(item);
            }
        })
    }
    //广度优先遍历
    bfs(v){
        let set = [];
        let temp = [];
        set.push(v);
        while(set.length !== 0) {
            let adj = set.shift();
            console.log(adj + "节点已经被访问");
            temp.push(adj);
            this.adj[adj].forEach(item => {
                if(!temp.includes(item)){
                    set.push(item);
                }   
            })
        }
    }
}

快速排序

JavaScript快速排序的**：找出数组中间的那个数，以中数为基准把数组分成左右两个区域，左区域的数小于中数，右区域的数大于中数，把左右两区域依次递归，得到有序数列。

/**
 * 
 * 快排
 * 
 */
const quickSort = (arr) => {
    let left = [];
    let right = [];
    if(arr.length < 2){
        return arr;
    }
    let medianIndex = Math.floor(arr.length / 2);
    let median = arr.splice(medianIndex,1)[0];
    for(let i = 0 ,len = arr.length ; i < len; i ++){
        arr[i] < median ? left.push(arr[i]) : right.push(arr[i]);
    }
    
    return quickSort(left).concat([median],quickSort(right));
}
let result = quickSort([2,7,4,6,9,1,4,3,5]);
console.log(result);

集合

集合

集合集合是一种包含不同元素数据结构，在很多编程语言中并不把集合当成一种数据类型，当你想要创建一个数据结构，用来保存一段独一无二的文字的时候集合就非常有用。

集合的特点

  1. 集合的成员是无序的
  2. 集合中不允许相同成员存在。

集合关键概念定义

  1. 集合是一组无序但彼此之间又有一定相关性的成员构成的，集合中的元素称为成员。
  2. 不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。
  3. 如果两个集合的成员相同，则称两个集合相等
  4. 如果一个集合中的所有成员都属于另外一个集合，则前一集合称为后一集合的子集。
  5. 并集：将两个集合中的成员进行合并，得到一个新的集合
  6. 交集：两个集合**同存在的成员组成一个新的集合
  7. 补集：属于一个集合不属于另外一个集合的成员组成的集合。

代码实现

class Set {
        constructor(){
            this.dataStore = [];
        }
        //向集合中加入一个成员
        add(data) {
            if(!this.dataStore.includes(data)){
                this.dataStore.push(data);
                return data;
            }
            return false;
        }
        //从集合中移除一个成员
        remove(data){
            let idx = this.dataStore.indexOf(data);
            let value = this.dataStore[idx];
            if(idx !== -1){
                this.dataStore.splice(idx,1);
                return value;
            }
            return false;
        }
        //显示集合中的所有成员
        show(){
            return this.dataStore.toString();
        }
        //并集
        union(set){
            const tempSet = new Set();
            for(let i = 0, len = this.dataStore.length; i < len; i ++) {
                tempSet.add(this.dataStore[i]);
            }
            for(let i = 0, len = set.dataStore.length; i < len; i ++) {
                if(!tempSet.dataStore.includes(set.dataStore[i])){
                    tempSet.add(set.dataStore[i]);
                }
            }
            return tempSet;
        }
        //交集
        intersect(set){
            const tempSet = new Set();
            for(let i = 0, len = this.dataStore.length; i < len; i ++) {
                if(set.dataStore.includes(this.dataStore[i])){
                    tempSet.add(this.dataStore[i]);
                }
            }
            return tempSet;
        }
        //补集
        difference(set){
            const tempSet = new Set();
            for(let i = 0, len = this.dataStore.length; i < len; i ++) {
                if(!set.dataStore.includes(this.dataStore[i])){
                    tempSet.add(this.dataStore[i]);
                }
            }
            return tempSet;
        }
        //子集
        subset(set){
            if(set.size() > this.size()){
                return false;
            } else {
                for(let i = 0, len = set.size(); i < len; i ++){
                    if(!this.dataStore.includes(set.dataStore[i])){
                        return false;
                    }
                }
                return true;
            }
        }
        //返回集合的长度
        size(){
            return this.dataStore.length;
        }
        
    }

23、合并K个排序链表

题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

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

题解

解题思路

我的解法比较暴力，首先把所有节点放在一个数组里面，然后排序，最后遍历数组生成一条新的链表。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
      let arr = [],
            len = lists.length;
      for (let i = 0; i < len; i++) {
            let node = lists[i]
            while (node) {
                  arr.push(node.val);
                  node = node.next;
            }
      }
      arr.sort((a, b) => a - b);
      let len2 = arr.length;
      let head = new ListNode();
      let _self = head;
      for (let i = 0; i < len2; i++) {
            if (arr[i] !== undefined) {
                  let node = new ListNode(arr[i])
                  _self.next = node;
                  _self = node;
            }
      }
      return head.next;
};

二叉树及其操作

树的概念及用途

树是一种非线性的数据结构，特点是分层存储数据。树被用来存储具有层级关系的数据，还被用来存储有序列表。

树关键概念定义

  1. 树由一组以边连接的节点组成。
  2. 一棵树最上面的节点称为根节点,如果一个节点相面连接多个节点,那么该节点称为父节点,它下面的节点被称为子节点.一个节点可以有0个、1个、或多个子节点。没有任何子节点的节点称为叶子节点。
  3. 二叉树是一种特殊的树，子节点个数不超过两个。
  4. 从一个节点走到另一个节点的者一组边叫做路径。
  5. 以某种特定顺序访问树中的所有节点称为树的遍历。
  6. 树分为几个层次，根节点是第0层，它的子节点是第1层，以此类推。我们定义树的层数就是树的深度。
  7. 每个节点都有一个与之相关的值，该值有时被称为键。
  8. 一个父节点的两个子节点分别称为左节点和右节点。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点，较大的值保存在右节点，者一特性使得查找效率很高。

二叉树

什么是二叉树，一个树最多只有两个子节点，最少有0个子节点，这样的树叫做二叉树。

当一个树的左子节点小于该节点，右子节点大于该节点，这样的树叫做二叉排序树或者叫做二叉搜索树。

二叉搜索树查找特别快，为二叉树添加或删除元素也特别快，把相对较小的值放在左节点，相对较大的值放在右节点。

二叉树的遍历

  1. 先序：根左右
  2. 中序：左根右
  3. 后续：左右根

二叉树的查找

查找最小值

从根节点出发，递归查找左节点，直到找到节点没有左子节点为止，那么此节点的值就是最小值。

查找最大值

从根节点出发，递归查找右节点，直到找到节点没有右子节点为止，那么此节点的值就是最大值。

二叉树的插入

对二叉树插入一个值，从根节点出发与插入值进行比较，当找到最终比较节点，如果比最终比较节点小，则插入到它的左侧，反之插入右侧。

二叉树的删除操作

  1. 首先先查找二叉树中是否有该值。
  2. 判断节点是否是子节点，是否只有一个节点，是否有两个节点。
  3. 当是子节点的时候直接把子节点删除即可。
  4. 当只有一个子节点的时候，则需要把节点删除，子节点替换到节点原来的位置。
  5. 当有两个子节点的时候，则需要把原节点删除，右子树的节点替换到节点的原来的位置上。

代码实现二叉搜索树

创建一个节点的构造函数，一个show方法显示节点的数据。

class Node{
    constructor(data,left,right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    show(){
        return this.data;
    }
}
class BST{
    constructor(){
        this.root = null;
    }
    //插入操作
    insert(data){
        let node = new Node(data,null,null);
        if(this.root === null) {
            this.root = node;
        }else{
            let current = this.root;
            while(true){
                if(data > current.data){
                    if(current.right === null) {
                        current.right = node;
                        return node;
                    } else{
                        current = current.right;
                    }
                } else {
                    if(current.left === null) {
                        current.left = node;
                        return node;
                    } else{
                        current = current.left;
                    }
                }
            }
        };
        return false;
    }
    //递归
    //中序遍历
    recInOrder(node){
        // console.log(node);
        if(!(node === null)) {
            this.recInOrder(node.left);
            console.log(node.data);
            this.recInOrder(node.right);
        }
    }
    //先序遍历
    recPreOrder(node){
        if(!(node === null)) {
            console.log(node.data);
            this.recPreOrder(node.left);
            this.recPreOrder(node.right);
        }
    }
    //后序遍历
    recOutOrder(node){
        if(!(node === null)) {
            this.recOutOrder(node.left);
            this.recOutOrder(node.right);
            console.log(node.data);
        }
    }
    //非递归
    //中序
    noRecInOrder(node){
        let stack = [];
        let temp;
        stack.push(node);
        while(stack.length !== 0){
            while((temp = stack[stack.length - 1]) && temp){
                stack.push(temp.left);
            }
            stack.pop();
            if(stack.length !== 0){
                temp = stack.pop();
                console.log(temp.data);
                stack.push(temp.right)
            }
        }
    }
    //先序
    noRecPreOrder(node){
        let stack = [];
        let temp;
        stack.push(node);
        while(stack.length !== 0){
            temp = stack.pop();
            while(temp){
                console.log(temp.data);
                if(temp.right){
                    stack.push(temp.right);
                }
                temp = temp.left;
            }
        }
    }
    //后序
    noRecOutOrder(node){
        let stack = [];
        let temp = node;
        while(temp || stack.length !== 0){
            if(temp){
                stack.push(temp);
                stack.push(temp);
                temp = temp.left
            } else {
                temp = stack.pop();
                if(temp === stack[stack.length - 1]){
                    temp = temp ? temp.right : null;
                } else {
                    console.log(temp.data);
                    temp = null;
                }
            }
        }
    }
    //获取到最小值
    getMin(root){
        let temp = root;
        while(temp.left){
            temp = temp.left;
        }
        return temp;
    }
    //获取到最大值
    getMax(root){
        let temp = root;
        while(temp.right){
            temp = temp.right;
        }
        return temp;
    }
    // 查找特定的值
    find(data){
        let root = this.root;
        while(root){
            if(data === root.data){
                return root.data;
            }else if(data > root.data) {
                root = root.right;
            } else if(data < root.data) {
                root = root.left;
            }
        }
        return false;
    }
    //删除一个节点
    remove(data){
        this.removeNode(this.root,data);
    }
    removeNode(node,data){
        if(!node){
            return null;
        }
        if(data === node.data) {
            if(node.left == null && node.right == null) {
                return null;
            }
            if(node.left == null) {
                return node.right;
            }
            if(node.right == null) {
                return node.left;
            }
            let tempNode = this.getMin(node.right);
            node.data = tempNode.data;
            node.right = this.removeNode(node.right,tempNode.data);
            return node;
        } else if(data < node.data) {
            node.left = this.removeNode(node.left,data);
            return node;
        } else {
            node.right = this.removeNode(node.right,data);
            return node;
        }
    }
}

算法导论

什么是算法

算法是完成某以特定任务的过程，通常使用数据结构作为工具来辅助算法完成任务。

程序 = 数据结构 + 算法

算法本身并不是数学，但是可以用数学来描述。

在写代码过程中，常用的增删改查这些都是算法的一部分。

  1. 排序算法
  2. 查找算法
  3. 推荐算法
  4. 贪心算法

算法的特征

  1. 有穷性：算法在执行有限的步骤之后必须终止。
  2. 确切性：算法的每一个步骤都必须要有明确的定义。
  3. 输入项：一个算法必须要有0或多个输入项，输入项是用来规定初始的情况的，所谓0个输入项就是算法本身就给出了初始的条件。
  4. 输出项：至少有一个输出，输出就是算法在一定的处理之后所得到的结果。
  5. 可行性(有效性)：算法中的每一个步骤都必须能分解成基本的可执行的操作，而且每一个计算步骤都必须在一定的时间内完成。

用什么衡量一个算法的好坏

五个方面

  1. 时间复杂度：表示算法执行完成所消耗的时间是长还是短
  2. 空间复杂度：表示算法执行完成所消耗的额外的空间是不是非常的大。
  3. 正确性：表示算法执行完成所得到的结果必须是正确的。
  4. 可读性：让开发人员在审视一个算法的时候，是不是容易被理解。
  5. 健壮性：表示算法本身是不是稳定的，会不会出现一些其他的意外，在出现意外的时候可不可以对算法进行容错。

常见的算法

必须掌握的算法：排序算法和查找算法

排序算法

排序算法是否稳定
稳定：多次排序的结果一致。
不稳定：多次排序的结果不一致。

  1. 冒泡排序 稳定 时间复杂度较高
  2. 选择排序 不稳定
  3. 插入排序 稳定
  4. 快速排序 不稳定
  5. 希尔排序
  6. 归并排序
  7. 堆排序 不稳定

查找算法

  1. 二分查找算法 前提：数组中的值必须是提前排好序的
  2. 线性查找 从头到尾挨个查找
  3. 分块查找 根据查找的数值决定查找某一块。
  4. 散列表

遍历算法

  1. 深度优先遍历
  2. 广度优先遍历

高级算法

  1. 动态规划法
  2. 贪心算法
  3. 贝叶斯分类算法

文件操作

  1. 压缩算法
    内存和硬盘都比以前大了很多，但是我们的数据量膨胀的速度要远远大于内存和硬盘增长的速度，为了在有限的空间内来保存更多的数据，我们就需要用到压缩算法。

    压缩算法最直接的目的就是节约空间，另外一个目的就是节约网络带宽，在网络通信中，数据量的大小决定着数据传输时间的长短，所以在数据进行传输之前需要对数据进行压缩，这样以来就会节省带宽的消耗，也会提高数据所传输的速度。

    平时所看到的视频和音乐很大程度上都是被经过压缩的。

    那么数据为什么能被压缩呢？
    数据在计算机存储中最小的单位是比特，比特是比字节更小的单位，一个字节是8个比特位组成，比特位所表示的除了0就是1。

     当查看数据的时候会发现，有很多连续相同的数据，就可以把这些连续相同的数据进行一个压缩处理，从而减少数据所占用的空间。
     例如：1111110 = 1*60;

 压缩算法底层所依赖的数据结构就是霍夫曼树。

数据传输

  1. 加密算法

    明文：没有被加密的信息
    密文：加密之后的信息
    密码：密码就像进入大们的一把钥匙，
    秘钥：必要是参与加密的数据

两种加密算法

  1. 对称加密算法
  2. 非对称加密算法

图像显示

  1. 图形渲染算法

游戏中炫酷的效果就是图形渲染算法，这种算法对计算机中某一个硬件的要求是非常高的，这个硬件就是显卡，显卡之上核心是GPU。
GPU渲染能力的强弱就决定了渲染性能的好坏。

人工智能算法

人工智能算法所表现出来的是策略性和智能性，要实现这两点就需要相当强大的计算机硬件来支持

二分查找法 

/**
 * 
 * 一维数组二分查找法
 *  规则：有序数组
 */

 const bunarySearch = (arr,result) => {
     let medianIndex = Math.floor(arr.length / 2);
     let median = arr[medianIndex];
     if(median == result) {
         return true;
     }
     if(arr.length === 1){
         return false;
     }
     arr = result > median ? arr.slice(medianIndex,arr.length) : arr.slice(0,medianIndex);
     return bunarySearch(arr,result);
 }
 console.log(bunarySearch([1,2,3,4,5,6,7,8],8));

非递归方式

const bunarySearch = arr => data => {
        let top = arr.length-1,
            bottom = 0;
        console.log(arr);
        while(bottom <= top){
            let mid = Math.floor((bottom + top)/2);
            console.log(arr[mid]);
            if(arr[mid] === data){
                return true;
            } else if(arr[mid] > data){
                top = mid -1;
            } else {
                bottom = mid + 1;
            }
        }
        return false;
    }
    console.log(bunarySearch([1,2,3,4,5,6,7,8])(8));
/**
 * 
 * 二维数组二分查找法
 * 规则 从上到下有序排列，从左到右有序排列
 */

 const bunarySearch = (arr) => result => {
     let row = 0;
     let col = arr[row].length - 1;
     let target;
     let maxRow = arr.length - 1;
     while(row <= maxRow && col >= 0 ){
         
        target = arr[row][col];
        console.log(target);

         if(target === result) {
             return true;
         }
         if(result < target) {
             col --;
         }
         if(result > target){
             row ++ ;
         }
     }
     return false;
 }
let result = bunarySearch([
    [1,2,3,4,5,6,7,8,9],
    [2,3,4,5,6,7,8,9,10],
    [3,6,7,11,15,17,18,19,20]
],)(15);
 console.log(result);

统计字符串中字母个数或统计最多字母数

使用hash表的方式把字母当做key值，把子母出现的次数当做value值

const maxWords = str => {
    let map = new Map();
    for(let item of str) {
        if(! map.has(item)){
            map.set(item,1);
        }else{
            map.set(item,map.get(item) + 1);
        }
    }
    let arr = [...map.entries()];
    
    arr = arr.sort((a,b) => b[1] - a[1]);
    return arr[0][0];
}
const result = maxWords("abcabcaa");
console.log(result);

17、电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

题解

解题思路

这道题其实就是解对应数字的排列组合。首先定义一个map结构，是数字和所对应字母的映射。

const map = {
    '2': ['a', 'b', 'c'],
    '3': ['d', 'e', 'f'],
    '4': ['g', 'h', 'i'],
    '5': ['j', 'k', 'l'],
    '6': ['m', 'n', 'o'],
    '7': ['p', 'q', 'r', 's'],
    '8': ['t', 'u', 'v'],
    '9': ['w', 'x', 'y', 'z']
}

在组合过程中我是使用深度搜索的方式，将所按下的第一个数字搜到到所按下的最后一个数字，找出能通过的所有路径，并存储在一个数组中，这个数组就是最终的结果。

代码

/**
 * @param {string} digits
 * @return {string[]}
 */
const map = {
    '2': ['a', 'b', 'c'],
    '3': ['d', 'e', 'f'],
    '4': ['g', 'h', 'i'],
    '5': ['j', 'k', 'l'],
    '6': ['m', 'n', 'o'],
    '7': ['p', 'q', 'r', 's'],
    '8': ['t', 'u', 'v'],
    '9': ['w', 'x', 'y', 'z']
}
let result = []
function combination(digits,s) {
    let len = digits.length;
    if(len === 0) {
        result.push(s);
        return;
    }
    let sArr = map[digits[0]];
    for(let i = 0; i < sArr.length; i ++) {
        combination(digits.slice(1, len), s + sArr[i]);
    }
}
var letterCombinations = function(digits) {
    result.length = 0;
    let len = digits.length;
    if(len === 0 ){
        return result
    }
    let sArr = map[digits[0]];
  
    for(let i = 0; i < sArr.length; i ++) {
        combination(digits.slice(1,len),sArr[i]);
    }
    return result;
};

编写一个方法，求一个字符串的字节长度

字符串中，英文字符站一个字节，中文字符站两个字节。

原理：待补充!

/**
 * 
 * 编写一个方法，求一个字符串的字节长度
 * 
 */

const byteLen = str => {
    let len = str.length;
    for(let s of str) {
        if(s.charCodeAt() >255){
            len ++;
        }
    }
    return len;
} 
const result = byteLen('fdsafd网');
console.log(result);

20、有效的括号

题目

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

题解

解题思路

一道很简单的题，参数栈的数据结构，在JavaScript就用数组就可以了。遍历字符串，控制以下条件：

  1. 当数组为空的时候将字符push到栈中，否则走2
  2. 当字符为( { [的时候将字符push到栈中否则走3
  3. 维护一个括号的映射表，当字符为) } ]的时候并且与映射表中的字符相对应，将栈顶元素pop出去
  4. 以上条件不符合，将字符push到栈中

最后判断栈是否为空，为空就是匹配完成返回true，否则返回false。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
   let map = {
       ')': '(',
       '}': '{',
       ']': '['
   };
    let stack = [];
    for(let i = 0, len = s.length; i < len; i ++) {
        if(stack.length === 0){
            stack.push(s[i]);
        } else if(s[i] === '(' || s[i] === '{' || s[i] === '[') {
            stack.push(s[i])
        } else if((s[i] === ')' || s[i] === '}' || s[i] === ']') && stack[stack.length - 1] === map[s[i]]) {
            stack.pop();
        } else {
            stack.push(s[i]);
        }
    }
    return !stack.length
};

有100节台阶，可以跨一个台阶，也可以跨两个台阶，那么一共有多少种走法？

这道题采用递归的思维。

假设n节台阶，一共有f(n)种走法。

n-1节台阶，一共有f(n-1)再+1种走法

n-2 节台阶，一共有f(n-2)再+1+1(一步走一节)或者+2(一步走两节)走法。

由n-2节可以发现，1+1这种走法存在与n-1节中，那么就可以得出 f(n) = f(n-1) + f(n-2);

代码如下：

const findStep = (n) => {
    if(n===0 || n === 1 || n === 2){
        return n;
    }
    return findStep(n -1) + findStep(n - 2);
}
const result = findStep(3);
console.log(result)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.