// 二分查找
function aaa(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = left + ((right - left) >> 1);
if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
console.log(aaa([23, 34, 45, 89, 100], 89));
// 中位数
function bbb(arr) {
if (arr.length % 2 === 0) {
return (arr[(arr.length - 1) >> 1] + arr[(arr.length) >> 1]) / 2
} else {
return arr[arr.length >> 1];
}
}
console.log(bbb([2, 3, 4, 5, 6, 7]))
// 递归node dfs 深度优先
let dfs = (node, result = []) => {
if (node !== null) {
result.push(node)
node.children && node.children.forEach(item => {
dfs(children[i], result)
})
}
return result
}
// 递归tree dfs 深度优先
function dfsTree(tree, result = []) {
if (tree) {
ccc(tree.left, result)
result.push(tree, result)
ccc(tree.right, result)
}
}
// dfs 非递归
function dfs2(tree, result = []) {
const stack = [];
const node = [];
if (tree) {
stack.push(tree)
while (stack.length) {
const item = stack.pop();
node.push(item);
const children = [stack.left, stack.right].filter(w => w);
children.forEach(i => {
stack.push(i);
})
}
}
return nodes;
}
// bfs
function bfs(tree, result = []) {
const stack = [];
const node = [];
if (tree) {
stack.push(tree)
while (stack.length) {
const item = stack.shift();
node.push(item);
const children = [stack.left, stack.right].filter(w => w);
children.forEach(i => {
stack.push(i);
})
}
}
return nodes;
}
// 快速排序
function sort(arr) {
if (arr.length < 2) {
return arr;
}
let [target, ...arrRest] = arr;
let left = [];
let right = [];
arrRest.forEach(item => {
if (item < target) {
left.push(item);
} else {
right.push(item);
}
})
return sort(left).concat([target], sort(right))
}
console.log(sort([12, 23, 24, 90, 45]))
// set
class setMock {
constructor() {
this.obj = {};
}
add(key) {
if (!this.obj.hasOwnProperty(key)) {
this.obj[key] = key;
}
}
}
// mapMock
class mapMock {
constructor() {
this.arr = [];
}
calc() { }
set(key, value) {
let key = this.calc(key)
this.arr[key] = value;
}
get(key) {
let key = this.calc(key)
return this.arr[key];
}
}
let m = new mapMock();
m.set({ a: 123 }, 123);
m.get({ a: 345 });
// 链表
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
class LinkList {
constructor() {
this.head = null;
this.length = 0;
}
insert() { }
append(element) {
let node = new Node(element);
if (!this.head) {
this.head = element;
} else {
let cursor = 0;
let current = this.head;
while (++cursor < this.length) {
current = current.next;
}
current.next = node;
}
this.length++;
}
}
// 二叉树最简单的代码
class treeNode {
constructor(element) {
this.element = element;
this.left = null;
this.right = null;
}
}
class Tree {
constructor() {
this.root = null;
}
insert(root, node) {
if (node < root.element) {
if (root.left === null) {
root.left = node;
} else {
this.insert(root.left, node)
}
} else {
if (root.right === null) {
root.right = node;
} else {
this.insert(root.right, node)
}
}
}
add(data) {
let node = new treeNode(data);
if (!this.root) {
this.root = data;
} else {
this.insert(this.root, node);
}
}
}
let t = new Tree();
tree.add(100);
tree.add(60);
tree.add(140);
// 冒泡排序
function bubbleSort(array) {
for (let j = 0; j < array.length; j++) {
let complete = true;
for (let i = 0; i < array.length - 1 - j; i++) {
// 比较相邻数
if (array[i] > array[i + 1]) {
[array[i], array[i + 1]] = [array[i + 1], array[i]];
complete = false;
}
}
// 没有冒泡结束循环
if (complete) {
break;
}
}
return array;
}
// 归并排序
function mergeSort(array) {
if (array.length < 2) {
return array;
}
const mid = Math.floor(array.length / 2);
const front = array.slice(0, mid);
const end = array.slice(mid);
return merge(mergeSort(front), mergeSort(end));
}
function merge(front, end) {
const temp = [];
while (front.length && end.length) {
if (front[0] < end[0]) {
temp.push(front.shift());
} else {
temp.push(end.shift());
}
}
while (front.length) {
temp.push(front.shift());
}
while (end.length) {
temp.push(end.shift());
}
return temp;
}
// 选择排序
function sort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
}
return arr;
}
console.log(sort([12, 23, 24, 90, 45]))
// 插入排序
function sort(arr) {
for (let i = 1; i < arr.length; i++) {
let minIndex = i;
for (let j = i - 1; j >= 0; j--) {
if (arr[minIndex] > arr[j]) {
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
minIndex = j;
} else {
break;
}
}
}
return arr;
}
console.log(sort([12, 23, 24, 90, 45]))
二叉树的最大深度
function TreeDepth(pRoot) {
return !pRoot ? 0 :
(Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1)
}
二叉树的最小深度
var minDepth = function (root) {
if (!root) {
return 0;
}
if (!root.left) {
return 1 + minDepth(root.right);
}
if (!root.right) {
return 1 + minDepth(root.left);
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1
};
url 切割
// 方法一
var url = 'https://www.baidu.com/a/b?name=王小二&age=8&hobby=敲代码&hobby=soccer';
function fn(str) {
let obj = {};
var arr = str.split('?')[1].split('&');
arr.forEach(item => {
const key = item.split('=')[0];
const value = item.split('=')[1];
if (!obj[key]) {
obj[key] = value;
} else {
obj[key] = [].concat(obj[key], value);
}
})
return obj;
}
console.log(fn(url));
// 方法2
let str = 'sadf?key=14&key=24&key=34&test=44';
let result = {};
str.replace(/([^?=&]+)=([^&=]+)/g, function () {
// console.log(arguments[0], arguments[1], arguments[2])
// key=14 key 14
if (!result[arguments[1]]) {
result[arguments[1]] = arguments[2];
} else {
result[arguments[1]] = [].concat(result[arguments[1]], arguments[2])
}
});
字符串每三位加一个逗号
---方法1：
// JS 自带的 toLocaleString
function formatNumber(num) {
return Number(num).toLocaleString()
}
---方法2：
// 正则表达式
function formatNumber(num) {
return num.toString().replace(/\d+/, function (n) {
return n.replace(/(\d)(?=(?:\d{3})+$)/g, '$1,')
})
}
console.log(formatNumber(123456789.123)) // 123,456,789.123
---方法4：
// slice 截取分割
function formatNumber(num, char=',', length=3) {
let result = ''
let nums = num.toString().split('.')
let int = nums[0];
let decmial = nums[1] ? '.' + nums[1] : ''
while (int.length > length) {
result = char + int.slice(-length) + result
int = int.slice(0, int.length - length)
}
if (int) { result = int + result }
return result + decmial
}
console.log(formatNumber(123456789.123)) // 123,456,789.123
---反转字符串
var reverseString = function(s) {
const n = s.length;
for (let left = 0, right = n - 1; left < right; ++left, --right) {
[s[left], s[right]] = [s[right], s[left]];
}
}
---比较版本
function compare( version1 , version2 ) {
let arr1=version1.split(".");
let arr2=version2.split(".");
let length=Math.max(arr1.length,arr2.length);
for (let i = 0; i < length; i++) {
const n1 = Number(arr1[i]||0)
const n2 = Number(arr2[i]||0)
if (n1 > n2) return 1
if (n1 < n2) return -1
}
return 0
}
---两数之和
var twoSum = function(nums, target) {
const map = new Map();
for(let i = 0, len = nums.length;i < len;i++) {
if(map.has(target - nums[i])) {
return [map.get(target - nums[i]), i];
}
map.set(nums[i], i);
}
return [];
};
---三数之和为0
---方法2 排序 + 双指针
时间复杂度：O(N^2) 时间复杂度O(N)
var threeSum = function(nums) {
let arr = []
// 直接sort()是根据字母、数字大小排序，导致-1排在-3左边
nums.sort((a,b) => a-b)
for (let i = 0; i < nums.length-2; i++) {
// 当遍历下一个target与前面的相同时，跳过
if (i > 0 && nums[i] == nums[i-1]) continue
let target = nums[i], x = i + 1, y = nums.length - 1
while (x < y) {
let sum = target + nums[x] + nums[y]
if (sum == 0) {
arr.push([target, nums[x], nums[y]])
// 准备夹逼前，将左右俩边移到相同数值最紧处
while (x < y && nums[x+1] == nums[x]) x++
while (x < y && nums[y-1] == nums[y]) y--
// 有了上述的准备过程，这里夹逼时，左右俩边数值与上次数值不同
x++
y--
} else if (sum > 0) {
y--
} else {
x++
}
}
}
return arr
};
---在排序数组中查找元素的第一个和最后一个位置
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
----答案
const binarySearch = (nums, target, lower) => {
let left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
var searchRange = function(nums, target) {
let ans = [-1, -1];
const leftIdx = binarySearch(nums, target, true);
const rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) {
ans = [leftIdx, rightIdx];
}
return ans;
};
合并两个有序数组
1. 直接合并然后排序
时间复杂度：(m+n)log(m+n)
空间复杂度：log(m+n)
2. 双指针
时间复杂度：O(m+n)
空间复杂度：O(m+n)
var merge = function(nums1, m, nums2, n) {
let p1 = 0, p2 = 0;
const sorted = new Array(m + n).fill(0);
var cur;
while (p1 < m || p2 < n) {
if (p1 === m) {
cur = nums2[p2++];
} else if (p2 === n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (let i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
};
寻找两个正序数组的中位数
----方法1.合并数组
----方法2：方法二：划分数组（太复杂，不建议背诵）
版权声明：本文为weixin_42201346原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。