数据结构与算法

动态规划
连续子数组的最大和
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let pre=0,max=-Infinity;
    nums.forEach(v=>{
        pre=Math.max(v+pre,v);
        max=Math.max(max,pre);
    })
    return max;
};
贪心算法
二分查找
寻找旋转排序数组中的最小值
function findMin(nums: number[]): number {
  let i=0,j=nums.length-1;
  let min = Infinity;
  while(i<=j){
    let mid = Math.floor((j-i)/2)+i;
    if(nums[mid]>min){
      if(nums[mid]<nums[j]){
        j=mid-1;
      }else{
        i=mid+1;
      }
    }else{
      min=nums[mid];
      if(nums[mid]<nums[j]){
        j=mid-1;
      }else{
        i=mid+1;
      }
    }
  }
  return min;
};
 搜索旋转排序数组
function search(nums: number[], target: number): number {
    let l=0,r=nums.length-1;
    let mid;
    while(l<=r){
        mid=Math.floor((r-l)/2)+l;
        const rightIsSort:boolean=nums[mid]<nums[r];
        if(nums[mid]===target){
            return mid;
        }else if(nums[mid]>target){
            if(!rightIsSort){
                if(nums[r]<target){
                    r=mid-1;
                }else{
                    l=mid+1;
                }
                
            }else{
                r=mid-1;
            }
        }else{ 
            if(rightIsSort){
                if(nums[r]<target){
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }else{
                l=mid+1;
            }
            
        }
    }
    return -1;
};
在 D 天内送达包裹的能力
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int max=0,sum=0;
        for(int val:weights){
            if(val>max)max=val;
            sum+=val;
        }
​
        while(max<sum){
            int mid=(sum+max)/2;
            int curDay = calDays(weights,mid);
            if(curDay>D){
                max=mid+1;
            }else if(curDay<=D){
                sum=mid;
            }
        }
        return max;
    }
​
    int calDays(vector<int>& weights,int weight){
        int D=0;
        int sum=0;
        for(int val:weights){
            if((sum+val)>weight){
                D++;
                sum=val;
            }else if((sum+val)==weight){
                D++;
                sum=0;
            }else{
                sum+=val;
            }
        }
        if(sum!=0)D++;
        return D;
    }
};
二叉树
DFS
BFS
从上到下打印二叉树 III
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root)return []
    const queue=[root]
    let direct=false
    const ret=[]
    while(queue.length){
        const tmp=[]
        const len=queue.length
        for(let i=0;i<len;i++){
            const curNode = queue.shift()
            tmp.push(curNode.val)
            curNode.left&&queue.push(curNode.left)
            curNode.right&&queue.push(curNode.right)
        }
        if(direct){
            tmp.reverse()
        }
        direct=!direct
        ret.push(tmp)
    }
    return ret
};
链表
两个链表的第一个公共节点
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
​
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let p1=headA;
    let p2=headB;
    while(p1!=p2){
        p1 = p1?p1.next:headA;
        p2 = p2?p2.next:headB;
    }
    return p1;
};
两数相加
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let ret=[];
    let n=0;
    while(l1||l2){
        let num1=0,num2=0;
        if(l1){
            num1=l1.val;
            l1=l1.next;
        }
        if(l2){
            num2=l2.val;
            l2=l2.next;
        }
        let count=num1+num2+n;
        n=count>=10?1:0;
        count%=10;
        ret.push(count);
    }
    if(n===1)ret.push(n);
    let head = new ListNode();
    let node=head;
    ret.forEach((value)=>{
        node.next = new ListNode(value);
        node=node.next;
    })
    return head.next;
};
栈
验证二叉树的前序序列化
模拟前序遍历，用栈存储节点，当两个'#'连着出现时，代表栈尾最后一个非空节点遍历完成
当前为'#'，栈顶也是'#',则出栈两位，出栈过程中如果栈空，直接返回false，并循环判断当前栈顶是不是'#'，直到不是后入栈'#'
最后栈只剩一个元素且为'#'时返回true
/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
    const preorderArr = preorder.split(',');
    const stack=[preorderArr.shift()];
    for(let i=0;i<preorderArr.length;i++){
        if(preorderArr[i]==='#'){
            while(stack[stack.length-1]==='#'){
                stack.pop();
                if(!stack.length)return false;
                stack.pop();
            }
            stack.push('#');
        }else{
            stack.push(preorderArr[i]);
        }
    }
    return stack.length===1&&stack[0]==='#';
}; 
逆波兰表达式求值
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    const stack=[];
    let res=0;
    if(tokens.length<2){
        return tokens[0]||res
    }
    for(let i=0;i<tokens.length;i++){
        if(!Number.isNaN(Number(tokens[i]))){
            stack.push(Number(tokens[i]));
        }else{
            const numR=stack.pop();
            const numL=stack.pop();
            if(tokens[i]==='+'){
                res=numL+numR;
            }else if(tokens[i]==='-'){
                res=numL-numR;
            }else if(tokens[i]==='*'){
                res=numL*numR;
            }else{
                res=numL/numR;
                if(res>0){
                    res=Math.floor(res)
                }else{
                    res=Math.ceil(res)
                }
            }
            stack.push(res)
        }
    }
    return res;
};
每日温度
单调栈
/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    const ret=new Array(T.length).fill(0);
    const stack=[];
    for(let i=0;i<T.length;i++){
        const obj={index:i,value:T[i]};
        while(stack.length&&T[i]>stack[stack.length-1].value){
            const top = stack[stack.length-1];
            const {index,value}=top;
            ret[index]=i-index;
            stack.pop();
        }
        stack.push(obj); 
    }
    return ret;
};
队列
堆
回溯
二叉树中和为某一值的路径
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function (root, sum) {
  const res = []
  const path = []
  function recur(node, tar) {
    if (!node) return
    tar -= node.val
    path.push(node.val)
    if (tar === 0 && !node.left && !node.right) {
      res.push([...path])
    }
    recur(node.left, tar)
    recur(node.right, tar)
    path.pop()
  }
  recur(root, sum)
  return res
}
全排列
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let res=[],track=[];
    function backTrack(res,track,nums){
        if(track.length===nums.length){
            res.push([...track]);
            return;
        }
        for(let i=0;i<nums.length;i++){
            if(track.find(v=>v===nums[i])!==undefined){
                continue;
            }
            track.push(nums[i]);
            backTrack(res,track,nums);
            track.pop();
        }
    }
    backTrack(res,track,nums);
    return res;
};
位运算
异或
相同的数异或为0
数组中数字出现的次数
先计算两个不同的数字的异或值
再计算出这个异或值中某个1位,也就是用来两个数字是不同的位数
将数组中的值分组异或
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumbers = function(nums) {
    let n=0;
    nums.forEach(num=>{
        n^=num;
    })
    let k=1;
    while((k&n)===0){
        k<<=1;
    }
    let a=0,b=0;
    nums.forEach(num=>{
        if(num&k){
            a^=num;
        }else{
            b^=num;
        }
    })
    return [a,b]
};
前缀和
矩形区域不超过 K 的最大数值和
function maxSumSubmatrix(matrix: number[][], k: number): number {
    const y=matrix.length,x=matrix[0].length;
    const sum=new Array(y+1);
    for(let i=0;i<=y;i++)sum[i]=new Array(x+1);
    let max=-Infinity;
    for(let i=1;i<=x;i++){
        for(let j=1;j<=y;j++){
            sum[j][i]=matrix[j-1][i-1]+(sum[j][i-1]||0)+(sum[j-1][i]||0)-(sum[j-1][i-1]||0);
        }
    }
    for(let i=1;i<=x;i++){
        for(let j=1;j<=y;j++){
            for(let p=i;p<=x;p++){
                for(let q=j;q<=y;q++){
                    let cur = sum[q][p]-(sum[q][i-1]||0)-(sum[j-1][p]||0)+(sum[j-1][i-1]||0);
                    if(cur>max&&cur<=k)max=cur;
                }                                                                                                
            }
        }
    }
    return max;
};
区域和检索 - 数组不可变
数组前缀和
/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.cache=[]
    nums.reduce((acc,cur,index)=>this.cache[index]=(acc+cur),0)
};
​
/** 
 * @param {number} i 
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function(i, j) {
    return this.cache[j]-(this.cache[i-1]||0)
};
​
/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(i,j)
 */
二维区域和检索 - 矩阵不可变
二维数组前缀和
/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
    const colLen=matrix.length
    if(colLen===0){
        this.isEmpty=true
        return
    }
    const rowLen=matrix[0].length
    if(rowLen===0){
        this.isEmpty=true
        return
    }
    this.rowLen=rowLen
    this.colLen=colLen
    this.rowCache=new Array(colLen)
    this.colCache=new Array(colLen)
    for(let i=0;i<colLen;i++){
        this.rowCache[i]=new Array(rowLen).fill(0)
    }
    for(let i=0;i<colLen;i++){
        matrix[i].reduce((acc,cur,index)=>this.rowCache[i][index]=(acc+cur),0)
    }
};
​
/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    if(this.isEmpty)return 0;
    if(row1>this.colLen){row1=this.colLen}
    if(row2>this.colLen){row2=this.colLen}
    if(col1>this.rowLen){col1=this.rowLen}
    if(col2>this.rowLen){col2=this.rowLen}
    let res=0;
    for(;row1<=row2;row1++){
        res+=this.rowCache[row1][col2]-(this.rowCache[row1][col1-1]||0)
    }
    return res;
};
​
/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */
网络
react-native
Last updated 3 months ago