关于前端:算法

33次阅读

共计 8101 个字符,预计需要花费 21 分钟才能阅读完成。

数组

疾速排序

function quickSort(arr, left, right) {if (left >= right) return
    const base = arr[left]
    let p = left, q = right
    while (p < q) {while (arr[q] > base && q >= p) {q--}
        while (arr[p] < base && p <= q) {p++}
        const temp = arr[q]
        arr[q] = arr[p]
        arr[p] = temp
    }
    arr[p] = base

    quickSort(arr, left, p)
    quickSort(arr, p + 1, right)
}

归并排序

function mergeSort(arr) {if (arr.length <= 1) return arr
    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)

    const leftArr = mergeSort(left)
    const rightArr = mergeSort(right)

    const result = []

    while (leftArr.length > 0 && rightArr.length > 0) {if (leftArr[0] < rightArr[0]) {result.push(leftArr.shift())
        } else {result.push(rightArr.shift())
        }
    }
    return result.concat(leftArr).concat(rightArr)
}

两数之和

var twoSum = function (nums, target) {let hash = {};
    for (let i = 0; i < nums.length; i++) {if (hash[target - nums[i]] !== undefined) {return [i, hash[target - nums[i]]];
      }
      hash[nums[i]] = i;
    }
    return [];};

三数之和

var threeSum = function(nums) {
    const len = nums.length;
    if(len < 3) return [];
    nums.sort((a, b) => a - b);
    const resSet = new Set();
    for(let i = 0; i < len - 2; i++) {if(nums[i] > 0) break;
        let l = i + 1, r = len - 1;
        while(l < r) {const sum = nums[i] + nums[l] + nums[r];
            if(sum < 0) {l++; continue};
            if(sum > 0) {r--; continue};
            resSet.add(`${nums[i]},${nums[l]},${nums[r]}`);
            l++;
            r--;
        }
    }
    return Array.from(resSet).map(i => i.split(","));
};

二分查找

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    // 应用左闭右闭区间
    while (left <= right) {let mid = left + Math.floor((right - left)/2);
        if (nums[mid] > target) {right = mid - 1;  // 去右面闭区间寻找} else if (nums[mid] < target) {left = mid + 1;   // 去右面闭区间寻找} else {return mid;}
    }
    return -1;
};

螺旋矩阵遍历

var generateMatrix = function(n) {
    let startX = startY = 0;   // 起始地位
    let loop = Math.floor(n/2);   // 旋转圈数
    let mid = Math.floor(n/2);    // 两头地位
    let offset = 1;    // 管制每一层填充元素个数
    let count = 1;     // 更新填充数字
    let res = new Array(n).fill(0).map(() => new Array(n).fill(0));

    while (loop--) {
        let row = startX, col = startY;
        // 上行从左到右(左闭右开)for (; col < startY + n - offset; col++) {res[row][col] = count++;
        }
        // 右列从上到下(左闭右开)for (; row < startX + n - offset; row++) {res[row][col] = count++;
        }
        // 上行从右到左(左闭右开)for (; col > startX; col--) {res[row][col] = count++;
        }
        // 左列做下到上(左闭右开)for (; row > startY; row--) {res[row][col] = count++;
        }

        // 更新起始地位
        startX++;
        startY++;

        // 更新 offset
        offset += 2;
    }
    // 如果 n 为奇数的话,须要独自给矩阵最两头的地位赋值
    if (n % 2 === 1) {res[mid][mid] = count;
    }
    return res;
};

合并两个有序数组

var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1, p2 = n - 1;
    let tail = m + n - 1;
    var cur;
    while (p1 >= 0 || p2 >= 0) {if (p1 === -1) {cur = nums2[p2--];
        } else if (p2 === -1) {cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {cur = nums1[p1--];
        } else {cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
};

随机排序

  function shuffle(arr) {
    var i, j,  temp;
    for (i = arr.length - 1; i > 0; i--) {j = Math.floor(Math.random() * (i + 1));
      temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
    return arr;
}
// 这个实现有问题
  function shuffle(arr){return arr.sort(function(){return Math.random() - 0.5;
    });
}

字符串

两数之和

var addStrings = function (num1, num2) {const result = []
    let p = num1.length - 1
    let q = num2.length - 1
    let add = 0
    while (p >= 0 || q >= 0 || add) {const x = p >= 0 ? Number(num1[p]) : 0
        const y = q >= 0 ? Number(num2[q]) : 0
        const sum = x + y + add
        result.unshift(sum % 10)
        add = Math.floor(sum / 10)
        p--
        q--
    }

    return result.join('')
};

千分符格式化

var thousandSeparator = function(n) {
    let res = ''
    let count = 0
    const str = n.toString()
    const len = str.length

    for(let i = len - 1; i >= 0; i--) {
        count++
        if (count % 3 === 0 && i !== 0) {res = '.' + str[i] + res
        } else {res = str[i] + res
        }
    }

    return res

};

无效括号

var isValid = function(s) {
    const n = s.length;
    if (n % 2 === 1) {return false;}
    const pairs = new Map([[')', '('],
        [']', '['],
        ['}', '{']
    ]);
    const stk = [];
    for (let ch of s){if (pairs.has(ch)) {if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {return false;}
            stk.pop();} 
        else {stk.push(ch);
        }
    };
    return !stk.length;

};

链表

反转链表

var reverseList = function(head) {
    let pre = null
    let cur = head

    while(cur !== null) {
        const temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }

    return pre

};

删除链表倒数第 N 个结点

var removeNthFromEnd = function(head, n) {let ret = new ListNode()
    ret.next = head
    let p = ret, q = ret

    // p 先后退 N
    while(n--) {p = p.next}
    // p 遍历到尾结点
    while(p.next !== null) {
        p = p.next
        q = q.next
    }
    q.next = q.next.next
    return ret.next
};

合并两个有序链表

var mergeTwoLists = function(l1, l2) {const prehead = new ListNode(-1);

    let prev = prehead;
    while (l1 != null && l2 != null) {if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }

    // 合并后 l1 和 l2 最多只有一个还未被合并完,咱们间接将链表开端指向未合并完的链表即可
    prev.next = l1 === null ? l2 : l1;

    return prehead.next;
};

二叉树

深度优先遍历(递归和迭代)

// 递归
var preorderTraversal = function(root) {let res=[];
    const dfs=function(root){if(root===null)return ;
        // 先序遍历所以从父节点开始
        res.push(root.val);
        // 递归左子树
        dfs(root.left);
        // 递归右子树
        dfs(root.right);
    }
    // 只应用一个参数 应用闭包进行存储后果
    dfs(root);
    return res;
};
// 迭代
var preorderTraversal = function(root, res = []) {if(!root) return res;
    const stack = [root];
    let cur = null;
    while(stack.length) {cur = stack.pop();
        res.push(cur.val);
        cur.right && stack.push(cur.right);
        cur.left && stack.push(cur.left);
    }
    return res;
};

档次遍历

var levelOrder = function(root) {
    // 二叉树的层序遍历
    let res=[],queue=[];
    queue.push(root);
    if(root===null){return res;}
    while(queue.length!==0){
        // 记录以后层级节点数
        let length=queue.length;
        // 寄存每一层的节点 
        let curLevel=[];
        for(let i=0;i<length;i++){let node=queue.shift();
            curLevel.push(node.val);
            // 寄存以后层下一层的节点
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        // 把每一层的后果放到后果数组
        res.push(curLevel);
    }
    return res;
};

最大深度

var maxdepth = function(root) {if (!root) return root
    return 1 + math.max(maxdepth(root.left), maxdepth(root.right))
};

最近公共先人

var lowestCommonAncestor = function(root, p, q) {
    // 应用递归的办法
    // 须要从下到上,所以应用后序遍历
    // 1. 确定递归的函数
    const travelTree = function(root,p,q) {
        // 2. 确定递归终止条件
        if(root === null || root === p||root === q) {return root;}
        // 3. 确定递归单层逻辑
        let left = travelTree(root.left,p,q);
        let right = travelTree(root.right,p,q);
        if(left !== null&&right !== null) {return root;}
        if(left ===null) {return right;}
        return left;
    }
   return  travelTree(root,p,q);
};

对称二叉树

var isSymmetric = function(root) {
    // 应用递归遍历左右子树 递归三部曲
    // 1. 确定递归的参数 root.left root.right 和返回值 true false 
    const compareNode=function(left,right){
        //2. 确定终止条件 空的状况
        if(left===null&&right!==null||left!==null&&right===null){return false;}else if(left===null&&right===null){return true;}else if(left.val!==right.val){return false;}
        //3. 确定单层递归逻辑
        let outSide=compareNode(left.left,right.right);
        let inSide=compareNode(left.right,right.left);
        return outSide&&inSide;
    }
    if(root===null){return true;}
    return compareNode(root.left,root.right);
};

动静布局

最长重复子数组

// 输出:A: [1,2,3,2,1] B: [3,2,1,4,7] 输入:3 解释:长度最长的公共子数组是 [3, 2, 1]。const findLength = (A, B) => {
    // A、B 数组的长度
    const [m, n] = [A.length, B.length];
    // dp 数组初始化,都初始化为 0
    const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0));
    // 初始化最大长度为 0
    let res = 0;
    for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {// 遇到 A[i - 1] === B[j - 1],则更新 dp 数组
            if (A[i - 1] === B[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // 更新 res
            res = dp[i][j] > res ? dp[i][j] : res;
        }
    }
    // 遍历实现,返回 res
    return res;
};

最长公共子序列

// 输出:text1 = "abcde", text2 = "ace" 输入:3 解释:最长公共子序列是 "ace",它的长度为 3。const longestCommonSubsequence = (text1, text2) => {let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0));

    for(let i = 1; i <= text1.length; i++) {for(let j = 1; j <= text2.length; j++) {if(text1[i-1] === text2[j-1]) {dp[i][j] = dp[i-1][j-1] +1;;
            } else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[text1.length][text2.length];
};

最长间断递增序列

const findLengthOfLCIS = (nums) => {let dp = Array(nums.length).fill(1);


    for(let i = 0; i < nums.length - 1; i++) {if(nums[i+1] > nums[i]) {dp[i+1] = dp[i]+ 1;
        }
    }

    return Math.max(...dp);
};

最大回文子串

var longestPalindrome = function (s) {
    const len = s.length
    if (len < 2) return s 
    let max = 0
    let str = s[0]
    const dp = Array.from(new Array(len), () => new Array(len))
  
  
    for(let j=0; j< len; j++) {for(let i=0; i<j; i++) {dp[i][j] = s[i] === s[j] && (j - i < 3 || dp[i+1][j-1])
        if(dp[i][j] && j -i + 1 > max) {
          max = j - i + 1
          str = s.substring(i, j+1)
        }
      }
    }
    return str
  }

最长回文子序列

  const longestPalindromeSubseq = (s) => {
    const strLen = s.length;
    let dp = Array.from(Array(strLen), () => Array(strLen).fill(0));
    
    for(let i = 0; i < strLen; i++) {dp[i][i] = 1;
    }

    for(let i = strLen - 1; i >= 0; i--) {for(let j = i + 1; j < strLen; j++) {if(s[i] === s[j]) {dp[i][j] = dp[i+1][j-1] + 2;
            } else {dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    return dp[0][strLen - 1];
};

无重复子数组最大长度 (滑动窗口)

function sub(arr) {
    let max = 0
    let base = 0
    const has = new Map()
    for(let i = 0; i < arr.length; i++) {const cur = arr[i]
        if (hash.hash(cur)) {base = Math.max(base, has.get(cur) + 1)
        }
        hast.set(cur, i)
        max = Math.max(max, i - base + 1)
    }
    return max
}

子数组乘积最大

function largestSum(arr) {let max = Number.MIN_SAFE_INTEGER, fmin = arr[0], fmax= arr[0]

    for(let num of arr) {if (num < 0) {
            const temp = fmax
            fmax = fmin
            fmin = temp
        }

        fmin = Math.min(fmin*num, num)
        fmax = Math.max(fmax*num, num)
        max = Math.max(max, fmax)
    }
    return max
}

最小费用

function minCount(days, cost) {
    const len = days.length
    let maxDay = days[len - 1], minDay = days[0]
    let dp = new Array(maxDay + 31).fill(0)

    for(let d = maxDay, i = len -1; d >= minDay; d--) {if (days[i] === d) {dp[d] = Math.min(dp[d + 1] + cost[0], dp[d+7] + cost[1], dp[d+30]+cost[2])
            i--
        } else {dp[d] = dp[d+1]
        }
    }
    return dp[minDay]
}

正文完
 0