算法题

无重复字符的最长子串

var lengthOfLongestSubstring = function(s) {
    let dic = '';
    let left = 0; 
    let right = 0;
    let res = 0
    while(s.length-left >= res) {
        if(!dic.includes(s.charAt(right))) {
            dic += s.charAt(right);  
            res = Math.max(res, dic.length);
        } else {
            let step = dic.indexOf(s.charAt(right)) + 1;
            left +=step
            dic = dic.substr(step)
            dic += s.charAt(right);
        }
        right++;
    }
    return res
};

比较版本号

var compareVersion = function(version1, version2) {
    const versions1 = version1.split('.');
    const versions2 = version2.split('.');
    for(let i =0; i<Math.max(versions1.length,version2.length); i++) {
        const v1 = versions1[i];
        const v2 = versions2[i];
        if(Number(v1) > Number(v2)) return 1;
        if(Number(v1) < Number(v2)) return -1;
        if(Number(v1) && !Number(v2)) return 1;
        if(!Number(v1) && Number(v2)) return -1;
        if(i === Math.max(versions1.length,version2.length) - 1) return 0
    }
};

合并两个有序数组

const merge = function(nums1, m, nums2, n) {
    nums1.splice(m, n, ...nums2);
    nums1.sort((a,b) => a-b);
    return nums1
};

或者双指针

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;
    }
};

求根节点到叶节点数字之和

深度优先

var sumNumbers = function(root) {
    const defSum = function(node, sum) {
        sum = 10 * sum + node.val;
        if(node.right && !node.left) {
            return defSum(node.right, sum)
        } 
        if(node.left && !node.right) {
            return defSum(node.left, sum)
        }
        if(node.left && node.right) {
            return defSum(node.left, sum) + defSum(node.right, sum)
        }
        return sum
    }
    return defSum(root, 0)
};

广度优先

var sumNumbers = function(root) {
    let sum = 0
    const nodeArr = [];
    const numArr = []
    nodeArr.push(root)
    numArr.push(root.val)
    while(nodeArr.length) {
        const node = nodeArr.shift();
        const num = numArr.shift()
        if(!node.left && !node.right) {
            sum += num
        }
        if(node.left) {
            nodeArr.push(node.left);
            numArr.push(num * 10 + node.left.val)
        }
        if(node.right) {
            nodeArr.push(node.right);
            numArr.push(num * 10 + node.right.val)
        }
    }
    return sum
};

路径总和

var hasPathSum = function(root, targetSum) {
    let flag = false
    function def(node, sum) {
        if(flag || !node) return
        if(!node.left && !node.right && (sum + node.val) === targetSum) flag = true
        if(node.left) def(node.left, sum+node.val)
        if(node.right) def(node.right, sum+node.val)
    }
    def(root, 0)
    return flag
};

最大子数组和

var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
        console.log(x, pre, maxAns)
    });
    return maxAns;
};

爬楼梯

一次爬1个或者两个台阶，问爬n个台阶有多少种组合

var climbStairs = function(n) {
    let p = 0, q = 0, r = 1;
    for (let i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
};

反转链表

var reverseList = function(head) {
    if(!head) return head
    const result = new ListNode()
    let temp = result
    function def(node, depth) {
        if(node.next) {
            def(node.next, depth+1)
        }
        temp.val = node.val;
        if(depth === 0) return
        temp.next = new ListNode()
        temp = temp.next
    }
    def(head, 0)
    return result
};

字符串相加

var addStrings = function (num1, num2) {
    if (!num1 && !num2) return '';
    if (!num1) return num2;
    if (!num2) return num1;
    const len = Math.max(num1.length, num2.length)
    let sum = []
    let addition = 0
    for (let i = len - 1; i > -1; i--) {
        let num = 0
        if (num1.length > num2.length) {
            num = (addition + 1 * (num1[i] || 0) + 1 * (num2[i - num1.length + num2.length] || 0))
        } else {

            num = (addition + 1 * (num1[i + num1.length - num2.length] || 0) + 1 * (num2[i] || 0))
        }
        if (num >= 10) {
            addition = 1;
            num = num - 10;
        } else {
            addition = 0
        }
        sum.unshift(num)
    }
    if (addition) {
        sum.unshift(1)
    }
    return sum.join('')
};

全排列

var permute = function(nums) {
    if(nums.length === 0 || nums.length === 1) return [nums];
    const res = []
    const used = []
    let path = []
    function back() {
        if(path.length === nums.length) {
            res.push([...path]);
            return
        }
        for(let i =0; i< nums.length ; i++) {
            if(used[i]) continue;
            path.push(nums[i]);
            used[i] = true
            back();
            path.pop()
            used[i] = false;
        }
    }
    back();
    return res
};

打家劫舍

var rob = function(nums) {
    let result = 0;
    if(nums.length === 0 )return 0
    if(nums.length === 1) return nums[0]
    if(nums.length === 2) return Math.max(nums[0], nums[1])
    const dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1])
    for(let i = 2; i<nums.length; i++) {
        dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])
    }
    return dp[nums.length - 1]
};

二分查找

var search = function(nums, target) {
    if(!nums) return -1
    if(nums.length === 1) {
        if(nums[0] === target) return 0
        return -1
    }
    function _search(n, k) {     
        const center = Math.floor((k+n)/2)
        if(n>k) return -1
        if(nums[center] === target) return center;
        if(nums[center] > target) return _search(n, center-1) 
        return _search(center+1, k)
    }
    return _search(0, nums.length - 1)
};

快速排序

function partion(arr, start, end) {
  let pivotIndex = start;
  const pivotValue = arr[end];
  for(let i = start; i<end; i++) {
    if(arr[i] < pivotValue) {
      [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]]
      pivotIndex++
    }
  }
  [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]]
  return pivotIndex
}

function quickSort(arr, start, end) {
  if(start >= end) return;
  const partionIndex = partion(arr, start ,end);
  quickSort(arr, start, partionIndex - 1)
  quickSort(arr, partionIndex + 1, end)
} 

function sortArray(nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums
}

平衡二叉树

function depth(node) {
    if(!node) return 0
    return Math.max(depth(node.left), depth(node.right)) + 1
}
var isBalanced = function(node) {
    if(!node) return true
    const result = Math.abs(depth(node.left) - depth(node.right)) <= 1
    if(result) {
        return isBalanced(node.left) && isBalanced(node.right)
    }
    else return false
};