算法题练习

五大算法

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

数据树

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

    • 完全二叉树
      • 若设二叉树的深度为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;
}
本文结束感谢您的阅读

本文标题:算法题练习

文章作者:陈宇(cosyer)

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

最后更新:2020年09月13日 - 23:09

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

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

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