704. 二分查找

  1. var search = function(nums, target) {
  2.     let low = 0, high = nums.length - 1;
  3.     while (low <= high) {
  4.         const mid = Math.floor((high - low) / 2) + low;
  5.         const num = nums[mid];
  6.         if (num === target) {
  7.             return mid;
  8.         } else if (num > target) {
  9.             high = mid - 1;
  10.         } else {
  11.             low = mid + 1;
  12.         }
  13.     }
  14.     return -1;
  15. };

300. 最长递增子序列

/**
 * @param {number[]} nums
 * @return {number}
 */

// dp[i] = dp[i - 1] + 1
var lengthOfLIS = function(nums) {
    var dp = new Array(nums.length).fill(1)
    var res = 1

    for (let i = 1; i < nums.length; i++) {
      // 这里为啥是j < i
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
            res = Math.max(res, dp[i])
        }
    }
    return res
};

剑指 Offer 10- I. 斐波那契数列

滑动窗口+dp

var fib = function(n) {
    const MOD = 1000000007;
    if (n < 2) {
        return n;
    }
    let p = 0, q = 0, r = 1;
    for (let i = 2; i <= n; ++i) {
        p = q; 
        q = r; 
        // 为何这里取模
        r = (p + q) % MOD;
    }
    return r;
};

209. 长度最小的子数组

// 滑动窗口
var minSubArrayLen = function (target, nums) {
    let l = r = sum = 0,
        len = Infinity; // 先令最小值为无穷大
    while (r < nums.length) {
        sum += nums[r];
        r++
        // 窗口滑动,sum>=target才开始
        while (sum >= target) {
            // 记录的res最小值和当前子序列长度比较取较小的那个
            len = len < r - l ? len : r - l;
            // 减去子序列中第一个元素,并令指向子序列第一个元素的指针l右移一位,继续寻找更小的子序列元素   
            sum -= nums[l++];
        }
    }
    //  最后判断res是不是Infinity,若是则说明其没有出现过sum>=target的阶段也就找不到最小子序列,反之返回当前res的值
    return len === Infinity ? 0 : len;
};