10月
04
更新于
10月04
2020

算法题练习

发表于 | 热度 ℃
| 字数统计： 2,262 (字) | 阅读时长： 11 (分钟)

五大算法

  • 贪心算法：局部最优解法
  • 分治算法：分成多个小模块，与原问题性质相同
  • 动态规划：每个状态都是过去历史的一个总结
  • 回溯法：发现原先选择不优时，退回重新选择
  • 分支限界法：按广度优先策略搜索问题的解空间树，适合求解最优化问题

数据树

  • 二叉树: 最多只有两个子节点

    • 完全二叉树
      • 若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边
    • 满二叉树
      • 深度为 h, 有 n 个节点，且满足 n = 2^h - 1
    • 平衡二叉树
      • 它或者是一颗空树，或它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树
    • 最优二叉树(哈夫曼树)
      • 树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

  • 二叉查找树: 是一种特殊的二叉树，能有效地提高查找效率

    • 小值在左，大值在右
    • 节点 n 的所有左子树值小于 n，所有右子树值大于 n

binary-search-tree

  • 遍历节点
    • 前序遍历
      • 根节点
      • 访问左子节点，回到 1
      • 访问右子节点，回到 1
    • 中序遍历
      • 先访问到最左的子节点
      • 访问该节点的父节点
      • 访问该父节点的右子节点， 回到 1
    • 后序遍历
      • 先访问到最左的子节点
      • 访问相邻的右节点
      • 访问父节点， 回到 1

DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）

dlr

LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）

ldr

LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

lrd

  • 插入与删除节点

写出一个方法输出1-100内的所有素数

解析： 由素数（质数）定义可知：

  • ① 0、1都不是质数，那么最小的质数就是2。
  • ② 除了1和它自身，不能被其他数整除，那么代码表达式表示为：
1
i % j === 0
  • 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
function fn() {
  const arr = []
  for (let i = 2; i <= 100; i++) {
    let bl = false
    for (let j = 2; j <= i; j++) {
      if (i === j) continue
      i % j === 0 && (bl = true)
    }
    !bl && arr.push(i)
  }
  return arr
}
console.log(fn())

(数组中第K大元素)给定一个整数数组，实现快速排序算法进行升序排列。如[2, 5, 8, 9, 3] =>[2, 3, 5, 8, 9]

解析：（分治法） 将一个列表分割为左右两块，然后再将字列表再进行分割为左右两块，如何反复，知道子元素长度为1时，结束！

  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function qSort(arr) {
      if (arr.length <= 1) return arr
      const index = Math.floor(arr.length / 2)
      const midVal = arr.splice(index, 1)[0]
      const left = [],
        right = []
      arr.forEach(item => {
        if (item < midVal) left.push(item)
        else right.push(item)
      })
      return [...qSort(left), midVal, ...qSort(right)]
    }
    qSort([2, 5, 8, 9, 3])

求一个字符串中最长的非重复连续子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function find(s) {
    var str = '';//存放当前最大无重复项字符串
    var len = 0;//存放当前最大无重复项字符串长度
    for(var i=0;i<s.length;i++){
        var char = s.charAt(i);
        var index = str.indexOf(char);
        if(index === -1){  //遍历s将元素挨个放入到str中，每放入一次判断str中是否有重复项
            str += char;
            len = len<str.length?str.length:len;//记录最大长度项,每次重新记录str进行判断，是否大于上次一次最大项
        }
        else{
            str = str.substr(index + 1) + char; //从当前重复项开始重新记录str
        }
    }
    return len;
}
// 'adasdddddddfghti' 6

求字符串数组的最长公共前缀

比如输入: [“flower”,”flow”,”flight”]，输出: “fl”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    if(strs.length === 1) return strs[0]
    let min = 0, max = 0
    for(let i = 1; i < strs.length; i++) {
        if(strs[min] > strs[i]) min = i
        if(strs[max] < strs[i]) max = i
    }
    for(let j = 0; j < strs[min].length; j++) {
        if(strs[min].charAt(j) !== strs[max].charAt(j)) {
            return strs[min].substring(0, j)
        }
    }
    return strs[min]
};

实现二叉树(构建、遍历)

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
function TreeCode() {
    let BiTree = function (ele) {
        this.data = ele;
        this.lChild = null;
        this.rChild = null;
    }

    this.createTree = function () {
        let biTree = new BiTree('A');
        biTree.lChild = new BiTree('B');
        biTree.rChild = new BiTree('C');
        biTree.lChild.lChild = new BiTree('D');
        biTree.lChild.lChild.lChild = new BiTree('G');
        biTree.lChild.lChild.rChild = new BiTree('H');
        biTree.rChild.lChild = new BiTree('E');
        biTree.rChild.rChild = new BiTree('F');
        biTree.rChild.lChild.rChild = new BiTree('I');
        return biTree;
    }
}

//前序遍历
function ProOrderTraverse(biTree) {
    if (biTree == null) return;
    console.log(biTree.data);
    ProOrderTraverse(biTree.lChild);
    ProOrderTraverse(biTree.rChild);
}

//中序遍历
function InOrderTraverse(biTree) {
    if (biTree == null) return;
    InOrderTraverse(biTree.lChild);
    console.log(biTree.data);
    InOrderTraverse(biTree.rChild);
}

//后续遍历
function PostOrderTraverse(biTree) {
    if (biTree == null) return;
    PostOrderTraverse(biTree.lChild);
    PostOrderTraverse(biTree.rChild);
    console.log(biTree.data);
}

let myTree = new TreeCode();
console.log(myTree.createTree());
console.log('前序遍历')
ProOrderTraverse(myTree.createTree());
console.log('中序遍历')
InOrderTraverse(myTree.createTree());
console.log('后续遍历')
PostOrderTraverse(myTree.createTree());

二叉树的非递归遍历

深度优先非递归(栈的先进后出)DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function DepthFirstSearch(biTree) {
    let stack = [];
    stack.push(biTree);

    while (stack.length != 0) {
        let node = stack.pop();
        console.log(node.data);
        if (node.rChild) {
            stack.push(node.rChild);
        }
        if (node.lChild) {
            stack.push(node.lChild);
        }

    }

}

广度优先非递归(队列的先进先出)BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function BreadthFirstSearch(biTree) {
    let queue = [];
    queue.push(biTree);
    while (queue.length != 0) {
        let node = queue.shift();
        console.log(node.data);
        if (node.lChild) {
            queue.push(node.lChild);
        }
        if (node.rChild) {
            queue.push(node.rChild);
        }
    }

}

一个数组，里面是排好序的数字，输入一个数字怎么能找到它的index

把这些数字放到对象的key里，index变成value，然后直接取 时间复杂度O(n) => O(1)

二分法查找

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
let arr = [0, 1, 2, 4, 5, 6, 7, 8];
let arr2 = [88, 77, 66, 55, 44, 33, 22, 11];

BinarySearch(arr2, 77);
BinarySearch(arr, 2);

function BinarySearch(arr, target) {
    let s = 0;
    let e = arr.length - 1;
    let m = Math.floor((s + e) / 2);
    let sortTag = arr[s] <= arr[e];//确定排序顺序

    while (s < e && arr[m] !== target) {
        if (arr[m] > target) {
            sortTag && (e = m - 1);
            !sortTag && (s = m + 1);
        } else {
            !sortTag && (e = m - 1);
            sortTag && (s = m + 1);
        }
        m = Math.floor((s + e) / 2);
    }

    if (arr[m] == target) {
        console.log('找到了,位置%s', m);
        return m;
    } else {
        console.log('没找到');
        return -1;
    }

}

洗牌(乱序)算法

时间复杂度:O(n²)

1
2
3
4
5
function shuffle(arr) {
  return arr.sort(function() {
      return Math.random() - 0.5;
  });
}

时间复杂度:O(n)空间复杂度O(1)

1
2
3
4
5
6
7
8
9
function shuffle(arr) {
  var newArr = [];
  for(var i = 0, len = arr.length; i < len; i++) {
    var j = Math.floor(Math.random() * (len - i));
    newArr[i] = arr[j];
    arr.splice(j, 1)
  }
  return newArr;
}

两数之和

[2,7,11,88,34],9 => [0,1]

双循环

1
2
3
4
5
6
7
8
9
10
11
function twoSum(arr, target) {
  var result = []
  for (let m=0;m<arr.length -1;m++) {
    for (let n= m+1;n<arr.length;n++) {
      if(arr[m]+arr[n]===target){
        result.push(m,n)
        return result
      }
    }
  }
}

Map

1
2
3
4
5
6
7
8
9
function(arr, target) {
 let result = new Map()
    for(let i=0;i<arr.length;i++){
      if(result.has(target-arr[i])){
        return [result.get(target-nums[i]),i] 
      }
      result.set(nums[i],i)
    }
};

假设有130个苹果，你我轮流拿，每次可拿1-5个，如何保证你拿到最后一个苹果

巴什博奕嘛保证剩最后6个给对面取，先取者可必胜，第一次取4个，剩126个，对面随便取，取的时候保证一直剩余6的倍数，最后一定出现剩6个苹果的情况。

手动控制并发请求fetchWithLimit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function fetchWithLimit(urls, max, callback) {
  const urlCount = urls.length;
  const requestsQueue = [];
  const results = [];
  let i = 0;
  const handleRequest = (url) => {
    const req = fetch(url).then(res => {
      const len = results.push(res);
      if (len < urlCount && i + 1 < urlCount) {
        requestsQueue.shift();
        handleRequest(urls[++i])
      } else if (len === urlCount) {
        'function' === typeof callback && callback(results)
      }
    }).catch(e => {
      results.push(e)
    });
    if (requestsQueue.push(req) < max) {
      handleRequest(urls[++i])
    }
  };
  handleRequest(urls[i])
}

有一个数n=5，不用for循环，怎么返回[1,2,3,4,5]这样一个数组

1
2
3
4
5
6
7
8
9
10
function getArr(n) {
    var a = [],
        b = [],
        m = 0;
    a.length = n + 1;
    a.toString().replace(/,/g, function () {
        b.push(++m);
    });
    return b;
}

判断单链表是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function main(node){
  let tmp = node.next;
  let nodes = [];
  nodes.push(tmp)
  while(tmp){
    if(isInnodes(node,tmp))
      return true;
    else{
      nodes.push(tmp);
      tmp = tmp.next;
    }
      
  }
  return false;
}
function isInnodes(node,tmp){
  for(let i = 0;i<node.length;i++){
    if(tmp.next===node[i])
      return true;
  }
  return false;
}
本文结束感谢您的阅读

本文标题:算法题练习

文章作者:陈宇（cosyer）

发布时间:2020年04月23日 - 01:04

最后更新:2020年10月04日 - 23:10

原始链接:http://mydearest.cn/2020/%E7%AE%97%E6%B3%95%E9%A2%98%E7%BB%83%E4%B9%A0.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

坚持原创技术分享，您的支持将鼓励我继续创作！