🌀Algorithm Summary
算法汇总
排序算法
原地算法 in-place
原地算法是基本上不需要借助额外的数据结构（存储空间）就能对输入的数据进行变换的算法。不过，分配少量空间给部分辅助变量是被允许的。wikipedia
算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。
不满足原地原则的算法被称为非原地 not-in-place 算法或异地 out-of-place 算法。
冒泡排序 Bubble Sort
冒泡排序需要重复地访问待排序的数列，一次比较两个元素，如果元素顺序错误就进行交换。wikipedia
平均时间复杂度 O(n^2)；最坏时间复杂度 O(n^2)；最优时间复杂度 O(n)。
比较相邻的元素，如果前者比后者大，就交换两者位置，每对相邻的元素都作同样的比较，从开始的一对直到结尾的最后一对。首次全部比较完成时，最末位的元素会是最大的数。重复上述步骤，直到没有任何一对元素需要比较。
/* JavaScript */
function bubbleSort (arr) {
const { length } = arr;
for(let i = 0; i < length; i++){
for(let j = 0; j < length - 1 - i; j++){
if(arr[j] > arr[j+1]){
let swapTemp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = swapTemp;
}
}
}
return arr;
}
/* Java */
public class BubbleSort{
public static void main (String[] args) {
int[] arrTest = {5, 4, 3, 2, 1};
bubbleSort(arrTest);
for(int item : arrTest){
System.out.println(item);
}
}
private static int[] bubbleSort(int[] array) {
int temp;
for (int i = 0; i < array.length - 1; i++) {
boolean Flag = false; // 是否发生交换。没有交换，提前跳出外层循环
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
Flag = true;
}
}
if (!Flag){
break;
}
}
return array;
}
}
选择排序 Selection sort
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则不会被移动。选择排序每次交换一对元素，至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 (n-1) 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。wikipedia
平均时间复杂度 О(n²)；最坏时间复杂度 О(n²)；最优时间复杂度 О(n²)；空间复杂度总共 О(n)，需要辅助空间O(1)。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
function selectionSort(arr){
const { length } = arr;
let minIndex;
for(let i = 0; i < length-1; i++){
minIndex = i;
for(let j = i+1; j < length; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
if (i !== minIndex) {
let swapTemp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = swapTemp;
}
}
}
return arr;
}
/* Java */
public class SelectionSort {
public void sort(int[] arr) {
int minIndex;
for(int i = 0;i < arr.length;i++) {
minIndex = i;
for(int j = i;j < arr.length;j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
插入排序 Insertion Sort
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。因在从后向前扫描过程中，需反复把已排序元素逐步向后挪位，为新元素提供插入空间，故在实现上通常采用 in-place 排序。wikipedia
平均时间复杂度 O(n^2)；最坏时间复杂度 O(n^2)；最优时间复杂度 O(n)。
从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复取出元素放入的步骤。
function insertionSort(arr){
for(let i = 1; i <= arr.length; i++){
if(arr[i] < arr[i-1]){
let elementToBeManipulated = arr[i], j = i - 1;
arr[i] = arr[j];
while(j >= 0 && elementToBeManipulated < arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = elementToBeManipulated;
}
}
return arr;
}
归并排序 Merge Sort
归并排序是创建在归并操作上的排序算法，是采用分治法 Divide and Conquer 的典型应用，且各层分治递归可以同时进行。效率为 O(n log n)。wikipedia
分治法 => 分割：递归地把当前序列平均分割成两半；集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
递归法 Top-down => 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；设定两个指针，最初位置分别为两个已经排序序列的起始位置；比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；重复步骤直到某一指针到达序列尾；将另一序列剩下的所有元素直接复制到合并序列尾。
/* JavaScript */
function merge(left, right){
var result = [];
while(left.length > 0 && right.length > 0){
if(left[0] < right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left, right);
}
function mergeSort(arr){
if(arr.length <=1) return arr;
var middle = Math.floor(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
/* Java */
static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, result, start1, end1);
merge_sort_recursive(arr, result, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
result[k++] = arr[start1++];
while (start2 <= end2)
result[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
merge_sort_recursive(arr, result, 0, len - 1);
}
快速排序 Quicksort
快速排序使用分治法 Divide and conquer 策略将序列 list 分为较小和较大的 2 个子序列，然后递归地排序两个子序列。wikipedia
排序 n 个项目的平均复杂度为 O(nlogn)。在最坏状况下则需要 O(n^2) 次比较。
步骤 => 挑选基准值 pivot /ˈpivət/；分割并重新排序数列；递归排序子序列
/* JavaScript */
function quickSort(arr){
if(arr.length <= 1) return arr;
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let leftArr = [], rightArr = [];
for(let i = 0; i < arr.length; i++){
if(arr[i] < pivot){
leftArr.push(arr[i]);
} else {
rightArr.push(arr[i]);
}
}
return quickSort(leftArr).concat([pivot], quickSort(rightArr));
}
/* Java */
public class QuickSort{
public static void main (String[] args) {
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
for(int item : arr){
System.out.println(item + " ");
}
}
private static void quickSort(int arr[], int begin, int end) {
if (begin < end) {
int partitionIndex = partition(arr, begin, end);
quickSort(arr, begin, partitionIndex-1);
quickSort(arr, partitionIndex+1, end);
}
}
private static int partition(int arr[], int begin, int end) {
int pivot = arr[end];
int i = (begin-1);
for (int j = begin; j < end; j++) {
if (arr[j] <= pivot) {
i++;
int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}
int swapTemp = arr[i+1];
arr[i+1] = arr[end];
arr[end] = swapTemp;
return i+1;
}
}
基数排序 Radix Sort
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。wikipedia
基数排序的方式可以采用 LSD Least significant digital 或 MSD Most significant digital，LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。
最坏时间复杂度 O(kN)；空间复杂度 O(k+N)。
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序、计数排序和桶排序在桶的使用上存在差异。前者根据键值的每位数字来分配桶；中者的每个桶只存储单一键值；后者每个桶存储一定范围的数值。
function radixSort(arr) {
const max = Math.max(...arr);
const buckets = Array.from({ length: 10 }, () => []);
let m = 1; // 个位
while (m < max) {
arr.forEach(number => {
let digit = ~~((number % (m * 10)) / m);
buckets[digit].push(number);
});
let sortedIndex = 0;
buckets.forEach(bucket => {
while (bucket.length > 0) {
arr[sortedIndex++] = bucket.shift();
}
});
m *= 10;
}
return arr
}
- double tilde ~~
按位非运算符 Bitwise NOT ~ 接受任何数字并将其二进制数字进行反转。那么将一个数字反转两次后，其结果会和以前一样。运算符 ~~ 可以理解为先通过 ~ 运算符转换成不保留小数值的 32 位有符号整数，再反转为原始数字的下限或上限。
当给定数字是正数时，同 Math.floor()；当给定数字是负数时，同 Math.trunc() 和 Math.ceil()。
- Array.from 对类数组或可迭代对象创建一个新的，浅拷贝的数组实例
Array.from(arrayLike[, mapFn[, thisArg]])
搜索算法与随机算法
顺序搜索
// 最基本的搜索算法 —— 顺序搜索
function sequentialSearch (array, value) {
for (let i = 0; i < array.length; i++) {
if (value === array[i]) {
return i;
}
}
return "noExist"
}
let arr = [1,2,3,4,5], value = 0, val = 1;
console.log(sequentialSearch(arr,value)); // noExist
console.log(sequentialSearch(arr,val)); // 0
二分搜索
如果待查找的数是整数，且知道范围，可以考虑二分查找。
- 先设定左下标 left 与右下标 right，再计算中间下标 mid。通常考虑数组头尾。
- 根据
arr[mid]和 target 之间的大小进行判断，相等则直接返回下标，nums[mid]< target 则 left 右移，nums[mid]> target 则 right 左移。
function BinarySearch (array, value) {
let left = 0, right = array.length - 1;
while( left <= right ) {
var mid = parseInt((left + right) / 2);
if (value == array[mid]) {
return mid;
} else if (value > array[mid]) {
left = mid + 1;
} else if (value < array[mid]) {
right = mid - 1;
}
}
return "nonono";
}
let arr = [1,2,3,4,5], value = 1, val = 0, val1 = 3;
BinarySearch(arr,value); // 0
BinarySearch(arr,val); // nonono
BinarySearch(arr,val1); // 2
LeetCode: 35. 搜索插入位置
这里在使用二分法查找结束后若没有相等值则返回 left 为插入位置。
var searchInsert = function(nums, target) {
let left = 0, right = nums.length - 1;
while(left<=right){ // 当越过临界条件时 (left>right) 则表示找不到对应值,跳出
let mid = parseInt((left+right)/2); // 每一次 left、right 改变会使 mid 赋新值,故必须放while中
if(target === nums[mid]){
return mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]){
right = mid -1;
}
}
return left
};
内插搜索
插值搜索之算法与二分搜索算法几乎完全相同，差别在：
- 二分搜索法：猜测键值在中间位置(middle)
- 插值搜索法：用插值公式计算键值位置
function interpolationSearch(arr, value) {
let low = 0, high = arr.length - 1, position = -1, delta = -1;
while (low <= high && value >= arr[low] && value <= arr[high]) {
delta = (value - arr[low]) / (arr[high] - arr[low]);
position = low + Math.floor((high - low) * delta);
if (arr[position] === value) {
return position
}
if (arr[position] < value) {
low = position + 1
} else {
high = position - 1
}
}
return "nonono"
}
let arr = [1,2,3,4,5], value = 1, val = 0;
console.log(interpolationSearch(arr,value)); // 0
console.log(interpolationSearch(arr,val)); // nonono
Fisher-Yates算法
function shuffle (array) {
for (let i = array.length - 1; i > 0; i--) {
// ~~ 视为 Math.truc() 或者 Math.floor()
const randomIndex = ~~(Math.random() * (i+1));
[array[i], array[randomIndex]] = [array[randomIndex], array[i]]
}
return array;
}
let arr = [1,2,3,4,5], zsarr = shuffle(arr)
console.log(shuffle(zsarr)) // 每次产生打乱的随机数组
反排序
function createNonSortedArray(size) {
const array = [];
for (let i = size; i > 0; i--) {
array.push(i)
}
return array;
}
算法思想
分而治之
分解问题为多个可递归的、有类似点的子问题
// 分而治之思想手撕二分法
const no = "nonono"
function binarySearchRecursive(array,value,low,high) {
if (low < high) {
const mid = Math.floor((low + high) / 2);
if (array[mid] < value) {
return binarySearchRecursive(array,value,mid+1,high)
} else if (array[mid] > value) {
return binarySearchRecursive(array,value,low,mid-1)
} else {
return mid;
}
}
return no
}
function binarySearch (array, value) {
const low = 0;
const high = array.length - 1;
return binarySearchRecursive(array, value, low, high)
}
let arr = [1,2,3,4,5]
let array = [1,2,3,4,5]
let val = 1
let value = 0
console.log(binarySearch(arr,val)); // 0
console.log(binarySearch(array,value)); // nonono
动态规划
复杂问题分解小的子问题
// 对于一种物品要么装入背包,要么不装.所以对于一种物品的装入状态只是1或0,此问题称为01背包问题
function knapsack(weights, values, W){
var n = weights.length -1
var f = [[]]
for(var j = 0; j <= W; j++){
if(j < weights[0]){ //如果容量不能放下物品0的重量，那么价值为0
f[0][j] = 0
}else{ //否则等于物体0的价值
f[0][j] = values[0]
}
}
for(var j = 0; j <= W; j++){
for(var i = 1; i <= n; i++ ){
if(!f[i]){ //创建新一行
f[i] = []
}
if(j < weights[i]){ //等于之前的最优值
f[i][j] = f[i-1][j]
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])
}
}
}
return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a) // 15
var b = knapsack([2,3,4],[3,4,5],5)
console.log(b) // 7
贪婪算法
通过局部最优选择达到全局最优解——遵循近似解决问题
对于贪婪算法不一定产生最优解，对于执行时间来说是一个可以接受的解
// 最少硬币找零问题
function minCoinChange(coins, amount) {
const change = [];
let total = 0;
for (let i = coins.length-1; i >= 0; i--) {
const coin = coins[i];
while (total+coin<=amount) {
change.push(coin);
total += coin;
}
}
return change;
}
let c = [0.5,1,5,10],
am = 34;
console.log(minCoinChange(c,am)); // [10, 10, 10, 1, 1, 1, 1]
回溯算法
回溯是一种渐进式寻找并构建问题解决方式的策略。从一个可能的动作尝试解决问题，如果不能解决则回溯到另一个动作直到问题解决。
这里引用一道 LeetCode 上 困难 级别的 N皇后 问题描述回溯
// 解决一个回溯问题,实际上就是一个决策树的遍历过程
// 路径:已经做出的选择、选择列表:当前可以做的选择、结束条件:到达决策树底层,无法再做选择的条件
// 穷举整棵决策树是无法避免的
// 这也是回溯算法的一个特点,不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高
// 回溯算法——N皇后问题
// N*N棋盘放N个皇后,彼此不攻击(棋盘任一行、任一列、任一对角线上不能放置两个皇后)
const NQueens = (n) => {
// 棋盘的初始化
const board = new Array(n);
for (let i = 0; i < n; i++) {
board[i] = new Array(n).fill('.');
}
const res = [];
const isValid = (row, col) => {
for (let i = 0; i < row; i++) { // 之前的行
for (let j = 0; j < n; j++) { // 所有的列
if (board[i][j] == 'Q' && // 发现了皇后，并且和自己同列/对角线
(j == col || i + j === row + col || i - j === row - col)) {
return false; // 不是合法的选择
}
}
}
return true;
};
const putqueen = (row) => { // 放置当前行的皇后
if (row == n) { // 递归的出口，超出了最后一行
const copyBoard = board.slice(); // 拷贝一份放完成功的board
for (let i = 0; i < n; i++) {
copyBoard[i] = copyBoard[i].join(''); // 将每一行拼成字符串
}
res.push(copyBoard); // 推入res数组
return;
}
for (let col = 0; col < n; col++) { // 枚举出所有选择
if (isValid(row, col)) { // 剪掉无效的选择
board[row][col] = "Q"; // 作出选择，放置皇后
putqueen(row + 1); // 继续选择，往下递归
board[row][col] = '.'; // 撤销当前选择
}
}
};
putqueen(0); // 从第0行开始放置
return res;
};
console.log(NQueens(4)); // [[ '.Q..', '...Q', 'Q...', '..Q.' ], [ '..Q.', 'Q...', '...Q', '.Q..' ]]
数据结构
Stack
栈是一种后进先出 LIFO 的有序集合，在回溯问题中应用广泛，可以存储访问过的任务路径、撤销操作等。
// 基于数组的类表示栈
class Stack {
constructor(){
this.items=[]; // 需要一种数据结构保存栈中元素,这里选择数组,大部分方法时间复杂度为O(n)
}
push(element){
this.items.push(element) // 栈添加元素
}
pop(element){
return this.items.pop(element) // 栈顶移除元素
}
peek(){
return this.items[this.items.length-1] // 查看栈顶元素
}
isEmpty(){
return this.items.length === 0 // 检查栈是否为空
}
size(){
return this.items.length // 返回栈长度
}
clear(){
this.items = [] // 清空栈元素
}
}
const zsstack = new Stack() // 初始化
console.log(zsstack.isEmpty()) // 判断栈内是否为空 此处返回 true
zsstack.push(0)
zsstack.push(4)
zsstack.push(2)
zsstack.push(2)
console.log(zsstack.peek()) // 查看栈顶元素 此处返回 2
console.log(zsstack.size()) // 返回栈长度 此处返回 4
console.log(zsstack.isEmpty()) // 判断栈内是否为空 此处返回 false
zsstack.push("what")
zsstack.pop() // 栈顶移除元素
console.log(zsstack.size()) // 返回栈长度 此处返回 4
// 基于对象的 Stack 类
class Stack {
constructor(){
// 属性
this.count = 0; // 帮助记录栈的大小
this.items = {}; // javascript中对象是一系列键值对
}
// 方法
push(element){
this.items[this.count] = element; // 插入元素是items对象的值
this.count++; // count对象是items对象键名
}
size(){ return this.count }
isEmpty(){ return this.count === 0 }
pop(){ // 删除栈顶元素并返回它
if(this.isEmpty()){ return undefined;} // 检验栈是否为空
this.count--;
const result = this.items[this.count];
delete this.items[this.count]; // JS运算符从对象删除一特定的值
return result
}
peek(){
if(this.isEmpty()){return undefined}{return this.items[this.count-1]}
}
clear(){this.items = {} ; this.count = 0}
toString(){ // 数组版本有直接提供的 toString方法
if(this.isEmpty()){
return ''
}
let objString = `${this.items[0]}`;
for(let i=1;i<this.count;i++){
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}
const zsstack = new Stack()
zsstack.push(0)
zsstack.push(4)
zsstack.push(2)
zsstack.push(2)
zsstack.push("needpop")
zsstack.pop()
console.log(zsstack.count); // 返回 4
console.dir(zsstack.toString()) // '0,4,2,2'
Queue
队列遵循先进先出(FiFO)原则的一组有序的项。尾部添加元素，顶部移除元素。
- 队列 JS 实现
class Queue {
constructor() {
this.count = 0; // count作为items对象中的键
this.lowestCount = 0;
this.items = {}; // 获取元素更高效的数据结构选择{}
}
enqueue(element){ // 向队列添加元素
this.items[this.count] = element; // 新项仅能添加队列末尾
this.count++;
}
isEmpty(){
return this.count - this.lowestCount === 0; // 假设count=2,lowestCount=0,则表示队列中仍有两个元素
// return this.size() === 0;
}
dequeue(){ // 队列移除元素也是遵循先进先出的,最先添加的项被最先移除
if(this.isEmpty()){return undefined}
const result = this.items[this.lowestCount] // 暂存以便返回
delete this.items[this.lowestCount]
this.lowestCount++;
return result;
}
peek(){ // 查看列头元素-就是首项
if(this.isEmpty()){return undefined}
return this.items[this.lowestCount]
}
size(){ // 返回队列的长度
return this.count - this.lowestCount
}
clear(){
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
toString(){
if(this.isEmpty()){
return ''; // 空队列返回空字符串
}
let objString = `${this.items[this.lowestCount]}`;
for(let i = this.lowestCount + 1; i<this.count; i++){
objString = `${objString},${this.items[i]}`;
}
return objString
}
}
const zsqueue = new Queue()
zsqueue.enqueue("needdequeue")
zsqueue.enqueue(0)
zsqueue.enqueue(4)
zsqueue.enqueue(2)
zsqueue.enqueue(2)
zsqueue.dequeue()
console.log(zsqueue.peek()) // 0
console.log(zsqueue.toString()); // 0,4,2,2
- 双端队列 JS 实现
双端队列是一种允许同时从前端和后端添加和移除元素的特殊队列。
// 双端队列前端添加元素
// 三种可能出现的情况
addFront(element){
if(this.isEmpty()){
this.addBack(element)
} else if (this.lowestCount>0){
this.lowestCount--;
this.items[this.lowestCount] = element;
} else {
for(let i = this.count; i>0; i--){
this.items[i] = this.items[i-1];
}
this.count++; // 插入element导致count++
this.lowestCount = 0;
this.items[0] = element; // 完成迭代移动,第一项为空闲,则新element覆盖
}
}
Array
数组存储一系列同一数据类型的值。
let arr = new Array(); // new关键字声明初始化数组
arr = new Array(6); // 创建指定长度数组
arr = new Array("zaire","sinatra","xie","zy"); // 直接数组元素做参数传递给他的构造器
-
斐波那契实现
// 创建斐波那契数组
const fibonacci = [] ;
// 定义前两项为1
fibonacci[1] = 1 ;
fibonacci[2] = 2 ;
// 斐波那契额数组的第三项到二十项位置的数字
for(let i = 3 ; i < 20 ; i++){
fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
}
// 输出斐波那契数组每一项
for(let i = 1 ; i < fibonacci.length; i++){
console.log(fibonacci[i]); // 1-6765
}
// 递归版本
function zsfibonacci(n){
if(n==0)return 0
else if(n==1)return 1
else return zsfibonacci(n-1) + zsfibonacci(n-2)
}
console.log(zsfibonacci(20)) // 6765
- 数组末尾插入元素
zsarr[zsarr.length]=待插入元素;
zsarr.push(待插入元素)
- 数组开头插入元素
// 1.不使用API
arr = new Array("zaire","sinatra","xie","zy")
Array.prototype.insertFirstPosition = function(value){
for(let i = arr.length; i > 0; i--) {
arr[i]=arr[i-1]
}
arr[0]=value;
};
arr.insertFirstPosition(1)
console.log(arr) // [ 1, 'zaire', 'sinatra', 'xie', 'zy' ]
// 2.使用unshift()
arr.unshift(1) // [ 1, 1, 'zaire', 'sinatra', 'xie', 'zy' ]
- 数组末尾删除元素
arr = new Array("zaire","sinatra","xie","zy")
arr.pop() // [ 'zaire', 'sinatra', 'xie' ]
- 数组开头删除元素
// 方法一
// 删除数组第一个元素
arr.shift()
// 方法二
// 定义一个数组
arr = new Array("zaire","sinatra","xie","zy")
// 3.除去 undefined
Array.prototype.deleteUn = function(arr){
const newArr = [];
for(i=0;i<arr.length;i++){
if(arr[i]!==undefined){
newArr.push(arr[i])
}
}
return newArr
}
// 手动删除第一个元素重新排序
Array.prototype.removeFirstPosition = function(){
for(let i = 0 ; i < arr.length ; i++){
arr[i] = arr[i+1]
}
// 1.先从这里入手理解,此处若不使用deleteUn方法,则输出[ 'sinatra', 'xie', 'zy', 'undefined' ]
// 2.那么需要去除 undefined => 使用deleteUn除去 undefined返回新数组
return arr.deleteUn(arr)
}
arr = arr.removeFirstPosition()
console.log(arr)
// 实际项目中还是使用 shift() 删除第一项
- 任意位置添加或删除元素
arr.splice(a,b,c,d)
- js实现二维数组
// 二维数组
let zairesinatra = [];
zairesinatra[0] = [1, 2, 3, 4, 5 ];
zairesinatra[1] = [1, 2, 3, 4, 5 ];
zairesinatra[0] = [];
zairesinatra[1] = [];
zairesinatra[0][0] = 1;
zairesinatra[0][1] = 2;
zairesinatra[0][2] = 3;
zairesinatra[0][3] = 4;
zairesinatra[0][4] = 5;
zairesinatra[1][0] = 1;
zairesinatra[1][1] = 2;
zairesinatra[1][2] = 3;
zairesinatra[1][3] = 4;
zairesinatra[1][4] = 5;
function printMatrix(zs){
for(i=0;i<zs.length;i++){
for(j=0;j<zs[i].length;j++){
console.log(zs[i][j])
}
}
}
console.table(zairesinatra)
- 数组去重（语法自身键、两层循环比较）
// 利用 set 集合 => 无重复、无顺序数组
// ES5 解构赋值
let zsset = (arr)=>{ return [...new Set(arr)] }
console.log(zsset([1,1,2,3,true,true])); // [ 1, 2, 3, true ]
// ES6 中 Array.from
function zsunique (arr) {
return Array.from(new Set(arr))
}
var arr = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zsunique(arr)) // [ 0, 6, 'xzy', true, undefined, null, NaN, {}, {} ]
// 嵌套
function zsNested(arr){
for(var i=0; i<arr.length; i++){
for(var j=i+1; j<arr.length; j++){
// 第一个等同于第二个则splice方法删除第二个
if(arr[i]==arr[j]){
arr.splice(j,1);
j--;
}
}
}
return arr;
}
var tarr = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zsNested(tarr)) // [ 0, 6, 'xzy', true, undefined, NaN, NaN, {}, {} ]
// indexOf
// 判断结果数组是否存在当前元素,如果有相同的值则跳过,不相同则push进数组
function zsindex(arr) {
if (!Array.isArray(arr)) {
console.log('type error!')
return
}
var array = [];
for (var i = 0; i < arr.length; i++) {
// indexOf()方法返回在数组中可以找到一个给定元素的第一个索引,如果不存在,则返回-1
if (array.indexOf(arr[i]) === -1) {
array.push(arr[i])
}
}
return array;
}
var ttarr = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zsindex(ttarr)) // [ 0, 6, 'xzy', true, undefined, null, NaN, NaN, {}, {} ]
// includes 去重 => 与 indexOf 类似
function zsin(arr) {
if (!Array.isArray(arr)) {
console.log('type error!')
return
}
var array =[];
for(var i = 0; i < arr.length; i++) {
if(!array.includes(arr[i])) {
array.push(arr[i]);
}
}
return array
}
var arrr = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zsin(arrr)) // [ 0, 6, 'xzy', true, undefined, null, NaN, {}, {} ]
// sort()去重
function zssort(arr) {
if (!Array.isArray(arr)) {
console.log('type error!')
return;
}
arr = arr.sort()
var array= [arr[0]];
for (var i = 1; i < arr.length; i++) {
if (arr[i] !== arr[i-1]) {
array.push(arr[i]);
}
}
return array;
}
var xarr = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zssort(xarr)) // [ 0, 6, NaN, NaN, {}, {}, null, true, 'xzy', undefined ]
// filter() 方法创建一个新数组,其包含通过所提供函数实现的测试的所有元素
function zsfilter(arr) {
return arr.filter((item, index, arr) => {
// 当前元素在原始数组中的第一个索引 === 当前索引值，否则返回当前元素
return arr.indexOf(item) === index;
// 或者 hasOwnProperty 去重
// hasOwnProperty()方法会返回一个布尔值,指示对象自身属性中是否具有指定的属性
});
}
let ffarr = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zsfilter(ffarr)); // [ 0, 6, 'xzy', true, undefined, null, {}, {} ]
// Map 数据结构去重
// Map 对象保存键值对,并且能够记住键的原始插入顺序
function zsMap(aarr) {
let map = new Map();
let array = new Array(); // 数组用于返回结果
for (let i = 0; i < arr.length; i++) {
if (map.has(arr[i])) { // 如果有该key值
map.set(arr[i], true);
} else {
map.set(arr[i], false); // 如果没有该key值
array.push(arr[i]);
}
}
return array ;
}
var aarr = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zsMap(aarr)) // [ 0, 6, 'xzy', true, undefined, null, NaN, {}, {} ]
// reduce()
// reduce() 方法对数组中的每个元素执行一个由您提供的reducer函数(升序执行),将其结果汇总为单个返回值
// Accumulator (acc) (累计器)、Current Value (cur) (当前值)、Current Index (idx) (当前索引)、Source Array (src) (源数组)
function zszs(arr){
return arr.reduce((prev,cur) => prev.includes(cur) ? prev : [...prev,cur], []);
}
var arro = [0,0,6,6,'xzy','xzy',true,true,undefined,undefined,null,null,NaN,NaN,{},{}];
console.log(zszs(arro)); // [ 0, 6, 'xzy', true, undefined, null, NaN, {}, {} ]
LinkedList
数组作为最常用的数据结构，几乎每一种语言都有默认实现数组的结构(python中称为链表)。但是数组也有很多缺点：
- 数组的创建通常需要申请一段连续的内存空间。若当前数组不能满足容量需求时，需要扩容(一般情况是申请一个更大的数组，再将原数组中元素赋值过去)。
- 从数组的起点或中间插入的成本较高，需要移动大量元素。
那么要储存多个元素，另外一个选择就是 链表 。链表相对有更高的内存动态管理。且不必在创建时确定大小、可无限延伸。在 插入和删除 数据时， 时间复杂度 可以达到 O(1) 。
链表是有序的元素集合，但 不同于数组在内存中连续空间 。而是每个元素由一个 存储元素本身的节点 和 指向下一个元素的引用（指针） 组成。
数组中可以直接通过下标值直接访问任何位置的任何元素，但在链表想访问中间一个元素需要 从起点迭代链表 ，这是链表的缺点——访问元素时性能低很多。
在现实中，链表就像是解谜游戏，根据一条线索去寻找下一项的线索，那么线索就是指针。想要得到链表中的线索唯一办法就是从起点顺着链表去寻找。
// util.mjs
export function defaultEquals(a,b){
return a === b;
}
// node.mjs
export class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
import { Node } from './node.mjs'
import { defaultEquals } from './util.mjs'
export default class LinkedList { // 对于封装的东西,我们首先考虑有什么共有的属性和方法
conductor(equalsFn = defaultEquals){
// 1.head指向所有节点的第一个节点 2.node(element、next)
this.count = 0; // 存储链表元素的数量
this.head = null;
this.equalsFn = equalsFn;
}
append(element){
const node = new Node(element); // element作为值传入创建node项
let current; // 设一个
if (this.head == null) { this.head = node }
else {
current = this.head;
while(current.next != null){
current = current.next;
}
current.next = node;
}
this.count++
}
removeAt(index){ // 这里要验证index是否为有效的index
let current = this.head // 通过current创建对列表第一个元素的引用
if(index>=0 && index<this.count){
if(index == 0){this.head = current.next}
else{
let previous;
for(i=0;i<index;i++){ // 迭代链表的node
let previous = current;
current = current.next;
}
previous.next = current.next; // 跳过选择到的current这一项
}
this.count--; // 少了一个node
return current.element; // 返回删除的这个节点元素
}
return undefined;
}
getElementAt(index){
if(index>=0 && index<=this.count){
let node = this.head;
for(i=0; i<index && node!=null; i++){
node = node.next;
}
return node;
}
return undefined;
}
insert(element,index){
if(index>=0&&index<=this.count){ // 检查越界值
let node = new Node(element);
if(index === 0){ // 链表起点添加元素
const current = this.head; // current是第一个元素的引用
node.next = current; // 插入在current元素之前
this.head = node; //head引用改为node
}
else{
const previous = this.getElementAt(index-1); // 迭代找到目标元素
const current = previous.next;
node.next = current; // 改变previous和current之间的链接
previous.next = node;
}
this.count++;
return true;
}
return false; // 错误的index
}
indexOf(element){
let current = this.head; // 拿到指向的第一节点
for(let i=0; i<this.count&¤t!=null; i++){
if(this.equalsFn(element,current.element)){
return i;
}
current = current.next; // 这里current一直在变为下一项
}
return -1;
}
remove(element){ // 复用代码
const index = this.indexOf(element)
return this.removeAt(index)
}
size(){
return this.count;
}
isEmpty(){
return this.size() === 0;
}
getHead(){
return this.head;
}
toString(){
if(this.head == null){ // 链表为空则返回空字符串
return ''
}
else{
let objString = `${this.head.element}`; // 链表第一项初始化最后返回的字符串
let current = this.head.next;
for(let i=0; i<this.size() && current != null; i++){
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
}
}
// 测试代码
var ll = new LinkedList()
ll.append('xzy')
ll.append('zs')
ll.append('zairesinatra')
ll.append(10)
console.log(ll);
console.log(ll.isEmpty());
Set
集合是没有重复元素与顺序概念的数组。常作为数组去重方法。
// Set 无序且唯一 => JavaScript 中对象不允许一个键指向两个不同的属性,保证集合元素唯一
class Set {
constructor() {
this.items = {};
}
has(element) {
// return element in this.items;
return Object.prototype.hasOwnProperty.call(this.items, element)
// Object原型有hasOwnProperty的方法,返回一个对象是否具有特定属性的布尔值; 使用call避免ESLint出现问题
}
add(element) {
if(!this.has(element)){
this.items[element] = element; // 同时作为键值保存有利于查找
return true
}
return false
}
delete(element) {
if(!this.has(element)){
delete this.items[element];
return true
}
false
}
clear() {
this.items = {}
}
// size()方法有三种实现方式
// 方法一,设置一个length,每一次进行add、delete、clear执行加一减以与清除
// 方法二,Javascript中内置的key方法. => Object.prototype.keys(this.items).length返回给定对象所有属性的数组
size() {
return Object.keys(this.items).length
}
// 方法三,手动提取items对象每一个属性,记录属性个数并返回-迭代
sizeLegacy() {
let count = 0;
for(let key in this.items) {
if(this.items.hasOwnProperty((key))){
count++;
}
}
return count;
}
// Object类内置的 Object.values() 方法返回包含给定对象的所有属性值的数组
values() {
return Object.values(this.items);
}
valuesLegacy() {
return Object.values(this.items);
}
// 并集
union(otherset) {
const unionSet = new Set(); // 代表两个集合的并集
// 迭代添加并集集合中
this.values().forEach((value) => {unionSet.add(value)});
otherset.values().forEach((value) => {unionSet.add(value)});
return unionSet;
}
// 交集
interSection(otherset) {
let interSectionSet = new Set(); // 定义要返回的交集集合
let otherValues = otherset.values();
let biggerSet = this.values();
let smallerSet = otherValues;
if(otherValues.length-this.values().length>0){
biggerSet = otherValues;
smallerSet = values;
}
smallerSet.forEach(value=>{
if(biggerSet.includes(value)){
interSectionSet.add(value);
}
});
return interSectionSet;
}
// 差集
difference(otherset){
let differenceset = new Set();
this.values().forEach(value=>{
if(!otherset.has(value)){
differenceset.add(value);
}
});
return differenceset
}
// 子集
isSubsetOf(otherset){
if(this.sizeLegacy()>otherset.sizeLegacy()){
return false;
}
let isSubset = true;
this.values().every(value=>{
if(!otherset.has(value)){ // 这里的意思是其他的集合没有则要考虑改变isSubset的布尔值
isSubset = false;
return false
}
return true;
});
return isSubset
}
}
let zsset = new Set()
zsset.add("z");
zsset.add("s");
console.log(zsset); // Set { items: { z: 'z', s: 's' } }
console.log(zsset.size()); // 2
console.log(zsset.sizeLegacy()); // 2
console.log(zsset.valuesLegacy()); // [ 'z', 's' ]
const zy = new Set()
zy.add(1)
zy.add(2)
zy.add("z")
console.log(zy); // Set { items: { '1': 1, '2': 2, z: 'z' } }
const un = zsset.union(zy)
console.log(un); // 注意这里最后z不存在于un --- Set { items: { '1': 1, '2': 2, z: 'z', s: 's' } }
let zairesinatra = new Set()
zairesinatra.add(1)
zairesinatra.add(2)
zairesinatra.add(3)
let xxx = new Set()
xxx.add(1)
xxx.add(2)
console.log(zairesinatra); // Set { items: { '1': 1, '2': 2, '3': 3 } }
console.log(xxx); // Set { items: { '1': 1, '2': 2 } }
const interr = zairesinatra.interSection(xxx)
const dd = zairesinatra.difference(xxx)
const child = xxx.isSubsetOf(zairesinatra)
console.log(interr); // Set { items: { '1': 1, '2': 2 } }
console.log(dd); // Set { items: { '3': 3 } }
console.log(child); // true
// 到这里实现了 JavaScript 中 Set 类的效果
结束
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！