[数据结构与算法]【记录】算法 - JavaScript版

0、基础

（1）异或

相异为1，相同为0。
性质

• N^0=N N^N=0
• 满足交换律和结合律

（2）与

1&1=1，其他都=0。

//利用临时变量实现交换
function swap(arr, i, j){
	let temp = arr[i];
	arr[i] = arr[j];
	arr[j] = arr[i];
}
//利用异或实现交换
//前提：i和j地址值不同（相当于自己地址值里的内容跟自己地址值里的内容异或=0）。
function swap(arr, i, j){
	arr[i] = arr[i]^arr[j];
	arr[j] = arr[i]^arr[j];
	arr[i] = arr[i]^arr[j];
}
//利用解构赋值实现交换
function swap(arr, i, j){
	[arr[i], arr[j]] = [arr[j], arr[i]];
}

//数组中有一个数只出现奇数次，其余都出现偶数次。请找出这个数。
//leetcode-136
//时间复杂度O(n)，空间复杂度O(1)
var singleNumber = function(nums) {
	let i = 0;
	nums.forEach(n=>{
		i ^= n;
	});
	return i;
};

//数组中有两个数只出现奇数次，其余都出现偶数次。请找出这两个数。
//leetcode-260
//时间复杂度O(n)，空间复杂度O(1)
var singleNumber = function(nums) {
    let eor = 0;
    nums.forEach(n=>{
        eor ^= n;
    });
	//此时eor=a^b，且不等于0
	//找出eor二进制表示中为1的最低位
    let right = eor & (~eor+1);
	let one = 0;//得到a或b
	//根据right位，可以将所有数分成两部分:others1和a，others2和b
    nums.forEach(n=>{
		//将和right位相同的数异或，得到的结果就是a或b
        if(n & right){
            one ^= n;
        }
    });
    return Array.of(one, eor^one);
};

(3)生成随机数

//0-1
Math.random()
//0-x
Math.around(Math.random()*x)
//1-10
Math.around(Math.random()*9+1)
//x-y
Math.around(Math.random()*(y-x) + x)

（4）master公式

T(N) = a*T(N/b) + O(N^d)

• log b a < d，时间复杂度为O(N^d)
• log b a > d，时间复杂度为O(N^(log b a))
• log b a = d，是件复杂度为O(N^d * logN)

（5）比较器

//返回负数时，a排在前；返回正数时，b排在前；返回0，不变。
function cmp(a, b){
	//按id升序
	/*
		if(a.id < b.id){
			return -1;
		}else if(a.id > b.id){
			return 1;
		}else{
			return 0;
		}
	*/
	return a.id - b.id;
	//按id降序
	//return b.id - a.id; 
}

arr.sort(cmp);

1、排序

• 要快选快排；空间少选堆排序；稳定选归并排序。
• sort()，基础类型使用快排，非基础类型使用归并：是为了稳定性。

基于比较的排序

（1）选择排序

• 时间复杂度O(n^2)
• 空间复杂度O(1)
• 不稳定
• 每趟从后面未排序序列中选出一个最小的。

function selectSort(arr){
	if(arr === null || arr.length < 2) return;
	//长度n，下标0~n-1
	//遍历i~n-2
	for(let i = 0; i < arr.length-1; i++){
		//以i为标杆
		let minIndex = i;
		//遍历i+1~n-1
		for(let j = i+1; j < arr.length; j++){
			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
		}
		swap(arr, i, minIndex);
	}
}

（2）冒泡排序

• 时间复杂度O(n^2)
• 空间复杂度O(1)
• 稳定
• 从前往后，两两比较，大的往后放，每趟比较后冒出一个最大的元素。

function bubbleSort(arr){
	if(arr === null || arr.length < 2) return;
	//长度n，下标0~n-1
	//i放每趟排序后冒出来的元素。
	for(let i = arr.length - 1; i > 0; i--){
		//遍历0~i-1
		for(let j = 0; j < i; j++){
			if(arr[j] > arr[j+1]){
				swap(arr, j, j+1);
			}
		}
	}
}

（3）插入排序

• 时间复杂度最差O(n^2)，最佳(n)
• 空间复杂度O(1)
• 稳定
• 将元素从后往前插入已排序序列中，比较直到前一个元素比元素小结束。

function insertSort(arr){
	if(arr === null || arr.length < 2) return;
	//长度n，下标0~n-1
	//i指向待插入元素。
	for(let i = 0; i < arr.length-1; i++){
		//j指向i前面元素，比较j和j+1
		for(let j = i - 1; j > 0 && arr[j] > arr[j+1];j--){
			swap(arr, j, j+1);
		}
	}
}

（4）归并排序

• 时间复杂度O(NlogN)
• 空间复杂度O(N)
• 稳定
• 分成左右两序列，使左右序列分别有序；合并左右序列，小的插入result，指针后移。

function main(arr){
	if(arr === null || arr.length < 2) return arr;
	process(arr, 0, arr.length-1);
	return arr;
}
function process(arr, L, R){
	if(L === R) return;
	//mid = (R-L)/2；为了防止溢出，mid = L + (R-L)/2；位运算更快。
	let mid = L + (R-L)>>1;
	process(arr, L, mid);
	process(arr, mid+1, R);
	merge(arr, L, mid, R);
}
function merge(arr, L, M, R){
	let result = new Array(R-L+1);
	let i = 0;//指向result当前要放入元素的位置
	let p1 = L;//指向左序列当前遍历到哪里
	let p2 = M+1;//指向右序列当前遍历到哪里
	//当指针p1、p2还未超出范围时
	while(p1 <= M && p2 <= R){
		result[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}
	while(p1 <= M){
		result[i++] = arr[p1++];
	}
	while(p2 <= R){
		result[i++] = arr[p2++];
	}
	for(let i = 0; i < result.length; i++){
		arr[L+i] = result[i];
	}
}


//应用
//小和问题：在一个数组中，遍历每个数，把每个数左边比当前数小的数累加起来，叫做这个数组的小和。
function smallSum(arr){
	if(arr === null || arr.length < 2) return 0;
	return process(arr, 0, arr.length-1);
}
function process(arr, l, r){
	if(l === r) return 0;
	let mid = l + ((r - l)>>1);
	//左边处理完的累积小和+右边处理完的累积小和+这趟处理产生的累积小和。
	return process(arr, 1, mid)
			+ process(arr, mid+1, r)
			+ merge(arr, 1, mid, r);
}
function merge(arr, l, m, r){
	let result = new Array(r-l+1);
	let i = 0;
	let p1 = l;
	let p2 = m+1;
	let res = 0;
	while(p1 <= m && p2 <= r){
		res += arr[p1] < arr[p2] ? (r-p2+1)*arr[p1] : 0;
		//注意是<
		result[i++] = arr[p1] < arr[p2]? arr[p1++] : arr[p2++];
	}
	while(p1 <= m){
		result[i++] = arr[p1++];
	}
	while(p2 <= r){
		result[i++] = arr[p2++];
	}
	for(let j = 0; j < result.length; j++){
		arr[l+i] = result[i];
	}
	return res;
}
//逆序对问题：在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请求出逆序对的总数。
//leetcode-剑指offer51
var reversePairs = function(nums) {
    if(nums === null || nums.length < 2) return 0;
    return process(nums, 0, nums.length-1);
};
function process(arr, l, r){
    if(l === r) return 0;
    let mid = l + ((r-l)>>1);
    return process(arr, l, mid)
            + process(arr, mid+1, r)
            + merge(arr, l , mid, r);
}
function merge(arr, l, m, r){
    let result = new Array(r-l+1);
    let i = 0;
    let p1 = l;
    let p2 = m+1;
    let res = 0;
    while(p1<=m && p2<=r){
		//注意比较符号
        res += arr[p1] > arr[p2] ? r-p2+1 : 0;
        result[i++] = arr[p1] > arr[p2]? arr[p1++] : arr[p2++]; 
    }
    while(p1<=m){
        result[i++] = arr[p1++];
    }
    while(p2<=r){
        result[i++] = arr[p2++];
    }
    for(let i = 0; i < result.length; i ++){
        arr[l+i] = result[i];
    }
    return res;
}

（5）快速排序

• 时间复杂度O(NlogN)
• 空间复杂度O(logN)
• 不稳定

//问题1：给定一个数组arr和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
//时间复杂度O(N)，空间复杂度O(1)
function divide(arr, num){
	//指向≤区的最后一个元素。
	let i = -1;
	let p = 0;
	while(p < arr.length){
		//≤num，和i的下一个数交换（插入≤区，≤区右扩）。
		if(arr[p] <= num){
			swap(arr, i+1, p);
			i++;
		}
		//>num，不处理；
		
		p++;
	}
	return arr;
}

//荷兰国旗问题：给定一个数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
//时间复杂度O(N)，空间复杂度O(1)
function dutchNationalFlag(arr, num){
	let i = -1;
	let j = arr.length;
	let p = 0;
	while(p < arr.length){
		//<num，和i的下一个数交换（≤区右扩），p右移。
		if(arr[p]<num){
			swap(arr, i+1, p++);
			i++;
		}
		//=num，p右移。
		else if(arr[p]===num){
			p++;
		}
		//>num，和j的前一个数交换（>区左扩），p不动（交换后p还未被比较过）。
		else if(arr[p]>num){
			swap(arr, p, --j);
		}
	}
}

//快排1.0：最后一个数为num，以问题1为处理算法，不断递归。
//快排2.0：最后一个数为num，以荷兰国旗问题为处理算法，不断递归。
//快排3.0：随机一个数为num，以荷兰国旗问题为处理算法，不断递归。
function quickSortMain(arr){
	if(arr === null || arr.length < 2)return;
	quickSort(arr, 0, arr.length-1);
}
function quickSort(arr, L, R){
	if(L < R){
		//从R-L之间随机选一个数和R交换，作为标杆。
		swap(arr, L + Math.around(Math.random()*(R-L+1)), R);
		//p[0]是=区的左边界，p[1]是=区的右边界。
		let p = [...partition(arr, L, R)];
		//<区再做快排
		quickSort(arr, L, p[0]-1);
		//>区再做快排
		quickSort(arr, p[1]+1, R);
	}
}
function partition(arr, L, R){
	let i = L-1;
	let j = R;
	let p = L;
	while(p < j){
		if(arr[p] < arr[R]){
			swap(arr, ++i, p++);
		}else if(arr[p] === arr[R]){
			p++;
		}else if(arr[p] > arr[R]){
			swap(arr, p, --j);
		}
	}
	//最后将>区的左边界和标杆换位置。
	swap(arr, j, R);
	//返回=区的左右边界。
	return new Array.of(++i, --j);
}


//优化：样本数<60使用插入排序；其余使用快排。

（6）堆排序

• 时间复杂度O(NlogN)
• 空间复杂度O(1)
• 不稳定
• 优先级队列结构就是堆结构。

//完全二叉树中，（结点下标为i），i结点的父结点为(i-1)/2，左孩子2i+1，右孩子2i+2。

//给了个大根堆，从index位置开始往上调整成大根堆。
//不断跟父节点比较，比父节点大上浮。
//时间复杂度O(logN)
function heapInsert(arr, index){
	//比父亲小 或 我的父亲就是我自己 时跳出循环。
	while(arr[index] > arr[(index-1)/2]){
		swap(arr, index, (index-1)/2);
		index = (index - 1) / 2;
	}
}

//给了个大根堆，从index位置开始往下调整成大根堆。
//不断跟子节点较大的比较，比子节点小下沉。
//时间复杂度O(logN)
function heapify(arr, index, heapSize){
	let lchild = index*2+1;
	while(lchild < heapSize){
		//左右孩子进行比较
		let bigOne = lchild+1 < heapSize && arr[lchild] < arr[lchild+1]? lchild+1 : lchild;
		//左右孩子较大的和父节点进行比较
		bigOne = arr[bigOne] > arr[index]? bigOne : index;
		if(bigOne === index) break;
		
		swap(arr, bigOne, index);
		index = bigOne;
		lchild = index*2+1;
	}
}

//给了个大根堆，把index位置改成某个数num，要求调整成大根堆。
//num和arr[index]进行比较，如果num<arr[index]往下调整；如果num>arr[index]往上调整。


//堆排序
function heapSort(arr){
	if(arr === null || arr.length < 2) return;
	//从0位置开始往上调整大根堆。
	//for(let i = 0; i < arr.length; i++){
	//	heapInsert(arr, i);
	//}
	
	//倒序遍历，向下调整大根堆。
	for(let i = arr.length - 1; i >= 0; i--){
		heapify(arr, i, arr.length);
	}
	
	
	let heapSize = arr.length;
	swap(arr, 0, --heapSize);
	while(heapSize > 0){
		heapify(arr, 0, heapSize);
		swap(arr, 0, --heapSize);
	}
}


//已知一个几乎有序的数组，选择合适的算法对数组进行排序，要求数组排好顺序后，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。
function sortedArrDistanceLessK(arr, k){
	let heap = new Array();
	let index = 0;
	//把数组前k个数放进堆里，调整堆。
	//求出数组长度和k中的最小值（防止k>>数组长度）
	for(; index < Math.min(arr.length, k); index++){
		heap.push(arr[index]);
		heapInsert(heap, index);
	}
	let i = 0;
	//把k+1个数放进堆里，调整堆，弹出堆顶。
	for(; index < arr.length; i++, index++){
		heap[index] = arr[index];
		heapInsert(heap, index);
		//弹出
		arr[i] = heap[0];
		heap[0] = heap[heap.length-1];
		heap.pop();
		heapify(heap, 0);
	}
	while(heap.length>0){
		arr[i++] = heap[0];
		heap[0] = heap[heap.length-1];
		heap.pop();
		heapify(heap, 0);
	}
}

非基于比较的排序

（1）计数排序

• 建立数组，下标即为数字，统计数字出现的频率。

（2）桶排序（基数排序）

function radixSortMain(arr){
	if(arr === null || arr.length < 2)return;
	radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
//求最多有几位十进制数。
function maxbits(arr){
	let max = Number.MAX_VALUE;
	for(let i = 0; i < arr.length; i++){
		max = Math.max(max, arr[i]);
	}
	let res = 0;
	while(max !== 0){
		res++;
		max /= 10;
	}
	return res;
}
function radixSort(arr, L, R, digit){
	const radix = 10;
	let i = 0, j = 0;
	let bucket = new Array(R-L+1);
	for(let d = 1; d <= digit; d++){
		//原count数组，count[i]表示d位上，i出现的次数。
		//现count数组，count[i]等于count[i]前面的数字累加，表示d位上<=i的有几个（每个数字的片加起来）；每个数该放在bucket数组下标=count[i]-1。
		let count = new Array(radix);
		//统计出现的次数
		for(i = L; i <= R; i++){
			j = getDigit(arr[i], d);
			count[j]++;
		}
		//累加
		for(i = 1; i < radix; i++){
			count[i] = count[i] + count[i-1];
		}
		//从右往左遍历数组(保证先入桶的先出桶)
		for(i = R; i >= L; i--){
			j = getDigit(arr[i], d);
			bucket[count[j]-1] = arr[i];
			count[j]--;
		}
		for(i = L, j = 0; i <= R; i++, j++){
			arr[i] = bucket[j];
		}
	}
}
function getDigit(x, d){
	return ((x / (Math.pow(10, d-1)))%10);
}

2、二分查找

有序数组，找某个数是否存在。

• 时间复杂度O( logN)

有序数组，找>=某个数最左侧的位置。

• 时间复杂度O(logN)

局部最小值
无序数组，相邻数一定不相等，求局部最小值。

• 时间复杂度O(N)

3、哈希表

哈希表

• 增删改查操作的时间复杂度可以认为是O(1)，但是常数时间比较大。
• 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用的是这个东西的大小；如果不是基础类型，内部按引用传递，内存占用的是这个东西内存地址的大小。
• JS中的Object

• 有序表
• 有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织。
• 放入有序表的东西，如果是基础类型，内部按值传递，内存占用的是这个东西的大小；如果不是基础类型， 必须提供比较器，内部按引用传递，内存占用的是这个东西内存地址的大小。
• 红黑树、AVL树、size-balance-tree和跳表都属于有序表。
• JS中的Map、Set

4、链表

//反转单链表
//leetcode-206
//指针法
var reserveList = function(head){
	let prev = null;
	let curr = head;
	let next = head;
	while(curr !== null){
		next = curr.next;
		curr.next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
};
//指针法-简写（利用解构赋值）
var reverseList = function(head){
	let prev = null;
	let curr = head;
	while(curr !== null){
		[curr.next, prev, curr] = [prev, curr, curr.next];
	}
	return prev;
};
//递归法
var reverseList = function(head){
	if(head === null || head.next === null){
		return head;
	}
	//last用来指向反转后的头节点
	const last = reserveList(head.next);
	head.next.next = head;
	head.next = null;
	return last;
};


//反转双链表
var reserve = function(head){
	let prev = null;
	let curr = head;
	while(curr!==null){
		curr.prev = curr.next;
		curr.next = prev;
		prev = curr;
		curr = curr.prev;
		//[curr.prev, curr.next, prev, curr] = [curr.next, prev, curr, curr.prev];
	}
	return prev;
};

//打印两个有序链表的公共部分
//牛客网-程序员bla-CD48（os：牛客网真难用）
//谁小谁移动，相等打印并移动，有一个越界停。
var print = function(head1, head2){
	let p1 = head1, p2 = head2;
	while(p1!==null && p2!==null){
		if(p1.data < p2.data){
			p1 = p1.next;
		}else if(p1.data > p2.data){
			p2 = p2.next;
		}else{
			console.log(p1.data);
			p1 = p1.next;
			p2 = p2.next;
		}
	}
}

//分割链表
//分成<，=，>区版本
//定义六个指针变量sH/sT/eH/eT/bH/bT
var partition = function(head, x){
	let sH = null;
	let sT = null;
	let eH = null;
	let eT = null;
	let bH = null;
	let bT = null;
	let next = null;
	while(head !== null){
		//next记录下一个节点。
		next = head.next;
		//摘下头节点。
		head.next = null;
		if(head.val < x){
			if(sH === null){
				sH = head;
				sT = head;
			}else{
				sT.next = head;
				sT = head;
			}
		}else if(head.val === x){
			if(eH === null){
				eH = head;
				eT = head;
			}else{
				eT.next = head;
				eT = head;
			}
		}else{
			if(bH === null){
				bH = head;
				bT = head;
			}else{
				bT.next = head;
				bT = head;
			}
		}
		head = next;
	}
	//s区非空，连接s区和e区
	if(sH !== null){
		sT.next = eH;
		//判断e区是否为空
		eT = eT === null? sT : eT;
	}
	//e区非空，连接e区和b区
	if(eH !== null){
		eT.next = bH;
	}
	return sH !== null ? sH : (eH !== null ? eH : bH);
};


//分成<，>=区版本
//leetcode-86
var partition = function(head, x){
	let sH = null;
	let sT = null;
	let eH = null;
	let eT = null;
	let next = null;
	while(head !== null){
		//next记录下一个节点。
		next = head.next;
		//摘下头节点。
		head.next = null;
		if(head.val < x){
			if(sH === null){
				sH = head;
				sT = head;
			}else{
				sT.next = head;
				sT = head;
			}
		}else{
			if(eH === null){
				eH = head;
				eT = head;
			}else{
				eT.next = head;
				eT = head;
			}
		}
		head = next;
	}
	//s区非空，连接s区和e区
	if(sH !== null){
		sT.next = eH;
	}
	return sH !== null ? sH : eH;
};

//判断回文链表
//leetcode-234
var isPalindrome = function(head){
	let slow = head;
	let fast = head;
	while(fast !== null && fast.next !== null){
		//慢指针一个一个走；快指针走双倍。
		//如果链表长度是奇数，最后slow走到中间，fast走到end。
		//如果链表长度是偶数，最后slow走到中间后一个，fast走到end+1(null)。
		slow = slow.next;
		fast = fast.next.next;
	}
	//链表长度是奇数，slow还需要往后走一个。
	if(fast !== null){
		slow = slow.next;
	}
	//分成左右两块开始遍历
	let left = head;
	//将slow后面的链表反转
	let right = reverse(slow);
	while(right !== null){
		if(left.val !== right.val)
			return false;
		left = left.next;
		right = right.next;
	}
	return true;
};
var reverse = function(head){
	let prev = null;
	let curr = head;
	while(curr !== null){
		[curr.next, prev, curr] = [prev, curr, curr.next];
	}
	return prev;
};

//复制带随机指针的链表
//leetcode-138
//用哈希表
var copyRandomList = function(head){
	if(!head) return head;
	let map = new Map();
	let cur = head;
	while(cur !== null){
		//key为老节点，value为新节点
		map.set(cur, new Node(cur.val));
		cur = cur.next;
	}
	cur = head;
	while(cur !== null){
		//根据map.get来查map，从而设置新节点。
		map.get(cur).next = map.get(cur.next) || null;
		map.get(cur).random = map.get(cur.random) || null;
		cur = cur.next;
	}
	return map.get(head);
}

//骚操作
var copyRandomList = function(head){
	if(!head) return head;
	let cur = head;
	let next = null;
	while(cur !== null){
		next = cur.next;
		//把每个节点的克隆节点放在每个节点的后面。
		cur.next = new Node(cur.val);
		//克隆节点串上原来的next
		cur.next.next = next;
		cur = next;
	}
	cur = head;
	//拷贝random指向
	//遍历新节点
	let curCopy = null;
	while(cur !== null){
		//遍历老节点
		next = cur.next.next;
		curCopy = cur.next;
		curCopy.random = cur.random !== null ? cur.random.next : null;
		cur = next;
	}
	const res = head.next;
	cur = head;
	//拷贝next
	while(cur !== null){
		next = cur.next.next;
		curCopy = cur.next;
		
		//修改新旧节点的next指向
		cur.next = next;
		curCopy.next = next !== null ? next.next : null;
		
		cur = next;
	}
	return res;
}