思路：用双指针移动，来贪心的选择某些满足约束的数据构成结果集

11. 盛最多水的容器

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5. var maxArea = function(height) {
  6.   let max = 0;
  7.   let l = 0, r = height.length - 1;
  8.   while (l < r) {
  9.     max = Math.max(max, (r-l) * Math.min(height[l], height[r]));
  10.     if (height[l] < height[r]) {
  11.       l += 1;
  12.     } else {
  13.       r -= 1;
  14.     }
  15.   }
  16.   return max;
  17. };

55. 跳跃游戏

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  let max = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > max) return false;

    // 最远能够跳到的坐标位置。
    max = Math.max(max, i + nums[i]); 
    if (max >= nums.length-1) return true;
  }
  return true;
};

45. 跳跃游戏 II

解法一：贪心

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
  // end 表示当前这次能够到达的最远位置，
  // max 表示下一个最远的位置
  let max = 0, end = 0, ans = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    max = Math.max(max, i + nums[i]);
    if (max >= nums.length-1) {
      ans++;
      return ans;
    };
    if (i === end) {
      end = max;
      ans++;
    }
  }
  return ans;
};

解法二：动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
  let len = nums.length;
  const dp = new Array(len).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    let right = Math.min(nums[i], nums.length - i - 1);
    for (let j = 1; j <= right; j++) {
      dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
    }
  }
  return dp[len-1];
};

455. 分发饼干

思路：总是找刚好满足孩子胃口的饼干，找到一个就匹配计数一次。

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  let cl = g.length;
  let sl = s.length;
  let j = 0;
  let ans = 0;
  for (let i = 0; i < cl && j < sl; i++, j++) {
    while (j < sl && s[j] < g[i]) {
      j++;
    }
    if (j < sl) {
      ans += 1;
    }
  }
  return ans;
};

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother添加此问题并且创建所有测试用例。

示例 1：
输入：s = “abc”, t = “ahbgdc” 输出：true
示例 2：
输入：s = “axc”, t = “ahbgdc” 输出：false

提示：

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。
    /**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
const sl = s.length, tl = t.length;
let si = 0, ti = 0;
while (si < sl && ti < tl) {
  if (s[si] !== t[ti]) {
    ti += 1;
  } else {
    si += 1;
    ti += 1;
  }
}
return si === sl;
};

    624. 数组列表中的最大距离

    难度中等53收藏分享切换为英文接收动态反馈
    给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离
    示例 1：
    输入： [[1,2,3], [4,5], [1,2,3]] 输出： 4 解释： 一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

注意：

  1. 每个给定数组至少会有 1 个数字。列表中至少有两个非空数组。
  2. 所有 m 个数组中的数字总数目在范围 [2, 10000] 内。
  3. m 个数组中所有整数的范围在 [-10000, 10000] 内。

image.png

/**
 * @param {number[][]} arrays
 * @return {number}
 */
var maxDistance = function(arrays) {
  let ans = Number.MIN_SAFE_INTEGER;
  let min = arrays[0][0];
  let max = arrays[0][arrays[0].length - 1];
  for (let i = 1; i < arrays.length; i++) {
    ans = Math.max(ans,  Math.abs(min - arrays[i][arrays[i].length - 1]),  Math.abs(arrays[i][0] - max));
    min = Math.min(arrays[i][0], min);
    max = Math.max(arrays[i][arrays[i].length - 1], max);
  }
  return ans;
};

44. 通配符匹配

思路一：动态规划

要点：
i,j 分别指向s和p的当前遍历下标

1、* 字符匹配任意个字符，所以当前结果与之前结果保持一致，即
dp[i][j] = dp[i][j-1] || dp[i-1][j]

2、？或者字符完全匹配，则
dp[i][j] = dp[i-1][j-1]

3、base case：

  • 空串匹配：dp[0][0] = true

  • ‘‘字符匹配：dp[0][i] = true, p[i-1] === ‘‘

    /**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
const dp = makeArray(s.length + 1, p.length + 1, false);
dp[0][0] = true; // 空串空模式匹配。

for (let i = 1; i <= p.length; i++) { 
  if (p[i-1] === '*') {
    dp[0][i] = true;  // 空串非空模式匹配边界，若出现非*的模式，则为false。
  } else {
    break;
  }
}
for (let i = 1; i <= s.length; i++) {
  for (let j = 1; j <= p.length; j++) {
    const pp = p.charAt(j-1);
    if (pp === '*') {
      dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
    } else if (pp === '?' || pp === s.charAt(i-1)) {
      dp[i][j] = dp[i-1][j-1];
    }
  }
}
return dp[s.length][p.length];
};
function makeArray(m, n, value) {
const r = new Array(m);
for (let i = 0; i < m; i++) {
  r[i] = new Array(n).fill(value);
}
return r;
}

    思路二：使用双指针贪心 + 回溯

    /**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let left = 0, right = 0;
let preLeft = -1, preRight = -1;
while (left < s.length) {
  // case 1: ? 以及字符匹配场景
  if (right < p.length && (p.charAt(right) === '?' || p.charAt(right) === s.charAt(left))) {
    left ++;
    right++;
    continue;
  }
  // case 2: * 场景，贪心选择匹配一个字符，并记录当前left，和right的位置，方便后面发现问题时回溯。
  if (preRight < p.length && p.charAt(right) === '*') {
    preLeft = left; // 记录星号
    // 并且right移到下一位,准备下个循环s[left]和p[right]的匹配
    //(也就是匹配0个字符)
    preRight = right++; 
    continue;
  }

  // case 3: 匹配不成功，说明前面的*匹配有错，需要回溯。
  if (preLeft >= 0) {
    // left 回溯到 preLeft + 1，显然匹配字符的量出错，现在多匹配一个，且自身加一，方便后面如果发现有问题，再次回溯。
    left = ++ preLeft;
    // right 回溯到preRight + 1 重新使用p串*后的部分开始对齐s串preLeft
    right = preRight + 1; 
    continue;
  }

  // case 4: 所有匹配场景都不匹配，则匹配失败。
  return false;
}

// case 5 : 若right后面的模式串没有被匹配，则需要检查剩下的是否都是*，否则匹配失败。
while (right < p.length && p[right] == '*') ++right;

return right === p.length;
};