JavaScript 算法
var arr = [0, 1, 2, 3, 4, 5, 6];
function binarySearch(arr: number[], result: number) {
let len = arr.length;
let low = 0;
let high = len - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] < result) {
low = mid + 1;
} else if (arr[mid] > result) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
console.log(binarySearch(arr, 4));
// https://xxoo521.com/2020-02-04-btree-find-path/
interface Node {
val: number;
left: Node;
right: Node;
}
function getPaths(sum: number, root: Node) {
if (!root) {
return [];
}
let paths: number[][] = [];
searchPath(sum, root, paths, []);
return paths;
}
function searchPath(
sum: number,
root: Node,
paths: number[][],
path: number[]
) {
if (!root) {
return;
}
path = [...path, root.val];
if (root.left === null && root.right === null && root.val === sum) {
paths.push(path);
return;
}
searchPath(sum - root.val, root.left, paths, path);
searchPath(sum - root.val, root.right, paths, path);
}
interface TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
}
const root: TreeNode = {
val: 0,
left: {
val: 1,
left: {
val: 3,
left: null,
right: null
},
right: {
val: 4,
left: null,
right: null
}
},
right: {
val: 2,
left: {
val: 5,
left: null,
right: null
},
right: {
val: 6,
left: null,
right: null
}
}
};
function bfs(node: TreeNode) {
if (node === null) {
return;
}
let queue: TreeNode[] = [node];
while (queue.length) {
let currentNode = queue.shift();
console.log(currentNode.val);
currentNode.left && queue.push(currentNode.left);
currentNode.right && queue.push(currentNode.right);
}
}
new Array(10).fill(new Array(20).fill(0));
/**
用 Javascript 构造一个双向链表,并且实现它的插入和删除方法,
例如 insert(position, element) 表示在 position
位置插入值为 element 的节点,removeAt(position) 表示删除 position 位置的节点。
*/
interface LinkNode {
value: number;
next: LinkNode | null;
prev: LinkNode | null;
}
class LinkList {
public head: LinkNode | null = null;
public length: number = 0;
insert(position: number, node: LinkNode): boolean {}
removeAt(position: number) {}
}
// 数组重复数组
var findDuplicates = function(nums) {
if(!nums || nums.length < 1){return [];}
nums.sort((a,b)=>{
return a-b;
})
nums = nums.filter((item,index)=>{
return nums[index] == nums[index+1];
})
return nums;
};
// 图遍历广搜
Graph.prototype.bfs = function(v) {
var queue = [], marked = []
marked[v] = true
queue.push(v) // 添加到队尾
while(queue.length > 0) {
var s = queue.shift() // 从队首移除
if (this.edges.has(s)) {
console.log('visited vertex: ', s)
}
let neighbors = this.edges.get(s)
for(let i=0;i<neighbors.length;i++) {
var w = neighbors[i]
if (!marked[w]) {
marked[w] = true
queue.push(w)
}
}
}
}
// 图遍历深搜
Graph.prototype.dfs = function() {
var marked = []
for (var i=0; i<this.vertices.length; i++) {
if (!marked[this.vertices[i]]) {
dfsVisit(this.vertices[i])
}
}
function dfsVisit(u) {
let edges = this.edges
marked[u] = true
console.log(u)
var neighbors = edges.get(u)
for (var i=0; i<neighbors.length; i++) {
var w = neighbors[i]
if (!marked[w]) {
dfsVisit(w)
}
}
}
}
// 图类
function Graph() {
this.vertices = [] // 顶点集合
this.edges = new Map() // 边集合
}
Graph.prototype.addVertex = function(v) { // 添加顶点方法
this.vertices.push(v)
this.edges.set(v, [])
}
Graph.prototype.addEdge = function(v, w) { // 添加边方法
let vEdge = this.edges.get(v)
vEdge.push(w)
let wEdge = this.edges.get(w)
wEdge.push(v)
this.edges.set(v, vEdge)
this.edges.set(w, wEdge)
}
Graph.prototype.toString = function() {
var s = ''
for (var i=0; i<this.vertices.length; i++) {
s += this.vertices[i] + ' -> '
var neighors = this.edges.get(this.vertices[i])
for (var j=0; j<neighors.length; j++) {
s += neighors[j] + ' '
}
s += '\n'
}
return s
}
// 归并排序
function merge_sort(arr){
if(arr.length < 2){
return arr;
}
var middle = parseInt(arr.length/2);
var left = arr.slice(0,middle);
var right = arr.slice(middle);
return merge(merge_sort(left),merge_sort(right));
}
// 合并两个有序数组
function merge(left,right){
var result = [];
var i = 0, j = 0;
while(i < left.length && j < right.length){
if(left[i] > right[j]){
result.push(right[j++]);
}
else{
result.push(left[i++]);
}
}
while(i < left.length){
result.push(left[i++]);
}
while(j < right.length){
result.push(right[j++]);
}
return result;
}
var arr = [1, 2, 3, 5, 6, 7, 8, 9];
var result = merge_sort(arr);
console.log(result); //[1, 2, 3, 5, 6, 7, 8, 9]
var arr1 = [1,3,5,5,5];
var arr2 = [2,3,6];
function merge(arr1, arr2) {
var result = [];
var i=0, j=0;
while(i < arr1.length && j < arr2.length) {
var num1 = arr1[i];
var num2 = arr2[j];
if (num1 <= num2) {
result.push(num1);
i++;
} else {
result.push(num2);
j++;
}
}
while(i < arr1.length) {
result.push(arr1[i++]);
}
while(j < arr2.length) {
result.push(arr2[j++]);
}
return result;
}
function max(num1, num2) {
return num1 >= num2 ? num1 : num2;
}
console.log(merge(arr1, arr2));
// 时间复杂度 最优:nlogn 最坏:n2
function quickSort(arr: number[]) {
if (arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr.splice(pivotIndex, 1)[0];
const left: number[] = [];
const right: number[] = [];
arr.forEach(num => {
if (num < pivot) {
left.push(num);
} else {
right.push(num);
}
});
return quickSort(left).concat([pivot], quickSort(right));
}
console.log(quickSort([2, 1, 3, 4, 5]));
// 快排
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
Array.prototype.quickSort = function() {
const len = this.length;
if (len < 2) return this;
const basic = this[0];
let left = [];
let right = [];
for (let i=1; i<len; i++) {
if(this[i] > basic) {
right.push(this[i]);
} else {
left.push(this[i]);
}
}
return left.quickSort().concat(basic, right.quickSort());
}
console.log([2,3,2,4].quickSort());
// 数组去重
arr.filter(function(item, i){
return arr.indexOf(item) === i;
})
function unique(array) {
// res用来存储结果
var res = [];
for (var i = 0, arrayLen = array.length; i < arrayLen; i++) {
for (var j = 0, resLen = res.length; j < resLen; j++ ) {
if (array[i] === res[j]) {
break;
}
}
// 如果array[i]是唯一的,那么执行完循环,j等于resLen
if (j === resLen) {
res.push(array[i])
}
}
return res;
}
function unique(array) {
return Array.from(new Set(array));
}
// 整数翻转
var reverse = function(x) {
var min = -Math.pow(2, 31);
var max = Math.pow(2, 31) - 1;
var result = 0;
while(x!=0) {
console.log(result)
result = result * 10 + x%10;
x = parseInt(x / 10);
}
if (result < min || result > max) {
return 0;
}
return result;
};
// 斐波那契 fibonacci
function fibonacci(n) {
if(n==0 || n == 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}
let fibonacci = (function() {
let memory = []
return function(n) {
if(memory[n] !== undefined) {
return memory[n]
}
return memory[n] = (n === 0 || n === 1) ? n : fibonacci(n-1) + fibonacci(n-2)
}
})()
var fibonacci = (function () {
var memory = {}
return function(n) {
if(n==0 || n == 1) {
return n
}
if(memory[n-2] === undefined) {
memory[n-2] = fibonacci(n-2)
}
if(memory[n-1] === undefined) {
memory[n-1] = fibonacci(n-1)
}
return memory[n] = memory[n-1] + memory[n-2]
}
})()
// 循环遍历
function fibonacci(n) {
let n1 = 1,
n2 = 1,
sum = 1
for(let i = 3; i <= n; i += 1) {
sum = n1 + n2
n1 = n2
n2 = sum
}
return sum
}
// 尾调用方案
function fibonacci(n, n1, n2) {
if(n <= 1) {
return n2
}
return fibonacci(n - 1, n2, n1 + n2)
}
// 公式
function fibonacci(n){
var sum = 0
for(let i = 1; i <= n; i += 1) {
sum += fib(i)
}
return sum
function fib(n) {
const SQRT_FIVE = Math.sqrt(5);
return Math.round(1/SQRT_FIVE * (Math.pow(0.5 + SQRT_FIVE/2, n) - Math.pow(0.5 - SQRT_FIVE/2, n)));
}
}
/**
* 旋转数组
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
while(k--) {
nums.unshift(nums.pop());
}
return nums;
};
// 最大子序和
var maxSubArray = function(nums) {
var max = -Number.MAX_VALUE;
var sum = 0;
for (let num of nums) {
if (sum < 0) {
sum = 0;
}
sum += num;
max = Math.max(max, sum);
}
return max;
}
function dp(str1: string, str2: string) {
let maxLen = 0;
let pointer = 0;
let len1 = str1.length;
let len2 = str2.length;
let record = new Array(len1 + 1).fill(new Array(len2 + 1).fill(0));
for (let i = 0; i < len1; i++) {
for (let j = 0; j < len2; j++) {
if (str1[i] === str2[j]) {
record[i + 1][j + 1] = record[i][j] + 1;
if (record[i + 1][j + 1] > maxLen) {
maxLen = record[i + 1][j + 1];
pointer = i;
}
}
}
}
let result = "";
while (maxLen--) {
result = str1[pointer] + result;
pointer--;
}
return result;
}
console.log(dp("1712391234", "12345"));
function maxWidth(root) {
let queue = [root]
let maxWidth = 0
while (queue.length > 0) {
let newQueue = []
for (let i = 0; i < queue.length; i++) {
newQueue = newQueue.concat(queue[i].children)
}
queue = newQueue
maxWidth = Math.max(maxWidth, newQueue.length)
}
return maxWidth
}
// 深搜
function dfs(node,nodeList) {
if (node) {
nodeList.push(node);
var children = node.children;
for (var i = 0; i < children.length; i++) {
dfs(children[i],nodeList);
}
}
return nodeList;
}
var root = document.getElementById('root')
console.log(deepTraversal(root,nodeList=[]))
// 广搜
function bfs(node) {
var nodes = [];
if (node != null) {
var queue = [];
queue.unshift(node);
while (queue.length != 0) {
var item = queue.shift();
nodes.push(item);
var children = item.children;
for (var i = 0; i < children.length; i++)
queue.push(children[i]);
}
}
return nodes;
}
var root = document.getElementById('root');
console.log(bfs(root));