betty985 / algorithm Goto Github PK

View Code? Open in Web Editor NEW

1.0 1.0 0.0 64 KB

算法练习

JavaScript 100.00%

algorithm's Introduction

链表

技巧

哑节点一般用来处理头节点的边界情况

递归

条件

大问题可以拆成子问题
子问题的求解方式和大问题一样
存在最小子问题
终止条件
递
归

function 递归(){
  //todo
  递归()
}

分治

贪心

能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

建立数学模型
分解子问题
找出子问题的局部最优解
找出最优解

方案：

排序
Math.max Math.min

回溯

记录状态
可以回退（栈？）
DFS可以实现回溯

例题

全排列

let ans=[]
var permute = function(nums) {
    if(nums.length==0) return nums 
    dfs(nums,[])
    return ans
};
 function dfs(nums,stack){
    //终止条件
    if(nums.length===stack.length){
        ans.push(stack.slice())
        return
    }
    for(let i=0;i<nums.length;i++){
        if(stack.includes(nums[i])) continue
        //选择
        stack.push(nums[i])
         // 操作：遍历
        dfs(nums,stack)
         // 撤销状态
        stack.pop()
    }
}

电话号码的字母组合

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
 let res=[]
  if (digits.length==0) return res
  //哈希表
  let map=new Map()
  map.set(2,['a','b','c'])
  map.set(3,['d','e','f'])
  map.set(4,['g','h','i'])
  map.set(5,['j','k','l'])
  map.set(6,['m','n','o'])
  map.set(7,['p','q','r','s'])
  map.set(8,['t','u','v'])
  map.set(9,['w','y','x','z'])
  //全排列问题
   const backtrack = (digits, start, sb) => {
        // 到达回溯树底部
        if (sb.length === digits.length) {
            res.push(sb.join(''))
            return
        }
        for (let i = start; i < digits.length; i++) {
            let digit = digits.charAt(i)*1
            for (let c of map.get(digit)) {
                // 做选择
                sb.push(c)
                // 递归下一层回溯树
                backtrack(digits, i + 1, sb)
                // 撤销选择
                sb.pop()
            }
        }
    }
    backtrack(digits, 0, [])
    return res
};

动态规划

划分状态
写出状态转移方程
设置初始状态
执行状态转移
写出最终解

注意

确定边界
由结果推过程

双指针

快慢指针等，可以删除某些元素快慢指针可以用来查找链表的中点，判断链表是否有环（及环的起点），删除元素

单调栈

BFS

可以求最短路径

图

建图
bfs或者dfs
关注入度和出度以及visited

algorithm's People

Contributors

Stargazers

Watchers

algorithm's Issues

插入排序

**

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

代码

function insertSort(arr){
    let tmp;
    for(let i=1;i<arr.length;i++){
        tmp=arr[i]
        for(let j=i;j>=0;j--){
            if(arr[j-1]>tmp){
                arr[j]=arr[j-1]
            }else{
                arr[j]=tmp
                break
            }
        }
    }
    return arr
}

深度优先遍历 DFS（Depth-First-Search）

**

从上至下，对每一个分支一直往下层遍历直到这个分支结束，然后返回上一层，对上一层的右子树分支继续深度遍历，直到一整棵树完全遍历。符合栈后进先出的特点
特性：不全部保留节点，占用空间少，有回溯操作，运行速度慢

递归

function deepTraversal(node){
 let nodes=[]
 if(node!=null){
  nodes.push(node)
  let childrens =node.children
  for(let i=0;i<childrens.length;i++){
   deepTraversal(childrens[i])
  }
 }
 return nodes
}

非遍历

function deepTraversal(node){
 let nodes=[]
 if(node!=null){
  let stack=[]
 //将要访问的节点
  stack.push(node)
  while(stack.length!=0){
   let item=stack.pop()
//正在访问的节点
   nodes.push(item)
   let childrens=item.children
   for(let i=childrens.length-1;i>=0;i--){
    stack.push(childrens[i])
   }
  }
 }
 return nodes
}

快速排序

**

在数据集中，选择一个元素作为基准；
小于基准的元素放到基准的左边，大于基准的元素放到基准的右边。这个操作叫分区。分区操作结束后，基准元素所处的元素就是它最后的位置；
对基准左右的子集，不断重复第一步和第二步，直到所有子集只剩一个元素。

代码

function quickSort(arr){
    if(arr.length<=1) return arr
    let paritionIndex=Math.floor(arr.length/2)
    let tmp=arr[paritionIndex]
    let left=[]
    let right=[]
    for(let i=0;i<arr.length;i++){
        if(i==paritionIndex) continue
        if(arr[i]<tmp){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([tmp],quickSort(right))
}

二叉搜索树

binary-search-tree
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

class BST{
    constructor(val,left,right){
       this.val = (val===undefined ? 0 : val)
       this.left = (left===undefined ? null : left)
       this.right = (right===undefined ? null : right)
    }
//     判断其是否是一个有效的二叉搜索树。
    isValidBST(root){
        // 借助辅助函数扩展参数列表
       return this.isValid(root,null,null)
    }
    isValid(root,min,max){
        if(root==null) return true
        else if(root.val<=min.val){
            return false
        }
        else if(root.val>=max.val){
            return false
        }
        return  this.isValid(root.left,null,root)&&this.isValid(root.right,root,null)
    }
    // 在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 
    // 如果节点不存在，则返回 null 。
    searchBST(root,val){
         if(root==null) return null
        while(root){
        if(root.val==val)
        return root
        root=root.val>val?root.left:root.right
    }
    return null
    }
    // 插入操作
    insertIntoBST(root=this,val){
        if(root==null) return new BST(val)
        if(root.val==val) {
            return new Error('val is on the bst')
        }
        else if(root.val>val) root.left=this.insertIntoBST(root.left,val)
        else if(root.val<val) root.right=this.insertIntoBST(root.right,val)
        return root
    }
    // 删除操作  默认用右子树的最小节点替换
    deleteNode(root,val,right=true){
        if(root==null) return null
        if(root.val==val){
            // 要删除的节点是叶子节点或者只有一个节点
            if(root.left==null) return root.right
            if(root.right==null) return root.left
            // 要删除的节点有两个子节点，用左边最大的元素或者右边最小的元素替换
            if(right){
                let node=this.getMin(root.right)
                root.val=node.val
                root.right=deleteNode(root.right,node.val)
            }else{
                let node=this.getMin(root.left)
                root.val=node.val
                root.left=deleteNode(root.left,node.val)
            }

        }else if(root.val<val){
            root.right=deleteNode(root.right,val)
        }
        else if(root.val>val){
            root.right=deleteNode(root.left,val)
        }
        return root
    }
    // 获取最小节点
    getMin(root){
        // 左子树不为空
        while(root.left){
            root=root.left
        }
        return root
    }
    // 获取最大节点
    getMax(root){
        // 右子树不为空
        while(root.right){
            root=root.right
        }
        return root
    }
// 层序遍历
levelOrder(root) {
    let res = []
    if (root == null) return res
    // 利用堆栈保存每层的节点
    let queue = [root]
    while (queue.length != 0) {
        let size = queue.length
        // 该层节点存放在这里
        res.push([]) for (let i = 0; i < size; i++) {
            let node = q.shift() res[res.length - 1].push(node.val) 
          if (node.left) q.push(node.left) 
         if (node.right) q.push(node.right)
        }
    }
    return res
}
}

位运算.md

x & (x−1)把x 的二进制表示的最后一个 1变成 0

选择排序

**

假设第一个元素未排序元素中为最小的，通过循环找到找出最小元素和第一个交换。
假设第二个元素是未排序元素中最小的。。。。。

代码

function selectSort(arr){
    for(let i=0;i<arr.length-1;i++){
        for(let j=i+1;j<arr.length;j++){
            if(arr[i]>arr[j]){
                [arr[i],arr[j]]=[arr[j],arr[i]]
            }
        }
    }
    return arr
}

冒泡排序

**

遍历要排序的元素列，一次比较两个相邻的元素，如果顺序错误就交换过来。

代码

function bubbleSort(arr){
    let len=arr.length
    for(let i=0;i<len;i++){
       for(let j=1;j<len-i;j++){
           if(arr[j-i]>arr[j]){
               [arr[j-1],arr[j]]=[arr[j],arr[j-1]]
           }
       }
    }
    return arr
}

原地排序（Sorted in place）

特指空间复杂度为O（1)的排序算法

稳定排序

待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前序列中领先的，排序后依然领先，则称所用的方法是稳定的。
稳定排序

插入排序
基数排序
归并排序
冒泡排序
计数排序
不稳定排序
快速排序
希尔排序
简单选择排序
堆排序

为什么要分稳定排序和非稳定排序

希尔排序

**

递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

代码

function shellSort(arr){
    let len=arr.length
    let i,j,tmp,gap
    for(gap=len>>1;gap>=1;gap>>=1){
        for(i=gap;i<len;i++){
            if(arr[i]<arr[i-gap]){
            tmp=arr[i]
            for(j=i-gap;j>=0&&tmp<arr[j];j-=gap){
                arr[j+gap]=arr[j]
            }
            arr[j+gap]=tmp
        }
    }
  }
    return arr
}

归并排序

**

将序列中待排序数组中每个数字分为一组
将若干组两两合并，并保证合并后的组是有序的
重复第二步操作直到只剩下一组，排序完成

递归

function mergeSort(arr){
    // 自上而下
    let len=arr.length
    // 终止条件
    if(len<2){
        return arr
    }
    let middle=Math.floor(len/2)
    let left=arr.slice(0,middle)
    let 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
}

分析

归并排序不是原地排序算法

归并排序是一种稳定的排序算法

归并排序的时间复杂度是O(nlogn),空间复杂度是O(n)

广度优先遍历 BFS(Breath First Search)

**

BFS的**是从左到右，对树每一层中所有节点依次遍历，当一层的节点遍历完全后，对下一层开始遍历，而下一层节点是上一层的子节点，符合队列先进先出的特点
特性：保留全部节点，占用空间大，无回溯操作，运行速度快。

递归

function wideTraversal(node) {
    let nodes=[]
    let i=0
    if(node !=null){
        nodes.push(node)
        wideTraversal(node.nextElementSlibing)
        node=nodes[i++]
        wideTraversal(node.firstElementChild)
    }
    return nodes
}

非递归

function wideTraversal(node){
    let nodes=[]
    let i=0
    while(node!=null){
        nodes.push(node)
        node=nodes[i++]
        let childrens=node.chilren
        for(let j=0;j<childrens.length;j++){
            nodes.push(childrens[j])
        }
    }
    return nodes
}

多叉树的层序遍历

将节点按层入队，队列中只存储当前层和下一层的节点。队列长度不为0 时，进入循环并记录下此时队列的长度（即当前层的节点个数）。让节点依次出队，将节点值放入当前层的数组，并将节点的children入队。当前节点全部出队后，将当前层的节点放入结果数组。

var levelOrder = function(root) {
    if (!root) {
        return [];
    }

    const ans = [];
    const queue = [root];

    while (queue.length) {
        const size= queue.length;
        const level = [];
        for (let i = 0; i < size; ++i) {
            const cur = queue.shift();
            level.push(cur.val);
            for (const child of cur.children) {
                queue.push(child);
            }
        }
        ans.push(level);
    }

    return ans;
};