数据结构与算法

动态规划
最长回文子串
i,j索引间的字符串的判断可以有i+1,j-1之间的字符串是否是回文串得出
我们就可以得出状态转移方程:dp[i][j]=dp[i+1][j-1]
另外只有一位长度的字符串不用判断,(i-1)-(i+1)<1 ==> j-i<3,满足这个条件为回文串
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const n=s.length;
    const dp = Array.from(s).reduce((acc)=>{
        const fillArr = new Array(n);
        acc.push(fillArr)
        return acc
    },[])
    let maxLen=1,maxIndex=0;
    for(let j=1;j<n;j++){
        for(let i=0;i<j;i++){
            if(s[i]===s[j]){
                if(j-i<3){
                    dp[i][j]=true;
                }else{
                    dp[i][j]=dp[i+1][j-1];
                }
            }else{
                dp[i][j]=false;
            }
            if(dp[i][j]&&j-i+1>maxLen){
                maxIndex=i;
                maxLen=j-i+1;
            }
        }
    }
    return s.substring(maxIndex,maxIndex+maxLen)
};
连续子数组的最大和
/**
 * @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;
};
最长连续递增序列
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    let count=1;
    let dp=new Array(nums.length).fill(1);
    for(let i=1;i<nums.length;i++){
        for(let j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1);
                if(count<dp[i])count=dp[i];
            }
        }
    }
    return count;
};
​
// 贪心解法
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    if(nums.length===0)return 0;
    let res=1,count=1;
    for(let i=0;i<nums.length-1;i++){
        if(nums[i+1]>nums[i]){
            count++;
        }else{
            count=1;
        }
        if(count>res)res=count;
    }
    return res;
};
俄罗斯套娃信封问题
/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
    envelopes = envelopes.sort((a,b)=>{
        if(a[0]===b[0]){
            return a[1]-b[1];
        }else{
            return a[0]-b[0];
        }
    })
    let count=1;
    let dp=new Array(envelopes.length).fill(1);
    for(let i=1;i<envelopes.length;i++){
        for(let j=0;j<i;j++){
            if((envelopes[i][1]>envelopes[j][1])&&(envelopes[i][0]>envelopes[j][0])){
                dp[i]=Math.max(dp[i],dp[j]+1);
                if(dp[i]>count)count=dp[i];
            }
        }
    }
    return count;
};
贪心算法
二分查找
寻找旋转排序数组中的最小值
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;
};
二叉树
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]
};
前缀和
区域和检索 - 数组不可变
数组前缀和
/**
 * @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 5 days ago