jiegiser的博客

1. 动态规划算法：

题目：
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wildcard-matching

var isMatch = function(s, p) {
  let cur = new Array(s.length + 1).fill(false)
  cur[0] = true
  
  for (const c of p) {
    if (c == '*'){
      let begin = cur.indexOf(true)
      if (begin == -1) {
        return false
      }
      cur.fill(true, begin)
    } else {
      for(let j = s.length;j > 0; --j){
        cur[j] = (c == '?' || c == s[j-1]) && cur[j-1]
      }
      cur[0] = false
    }

  }
  return cur[s.length]

};

2. 两数相加

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答：

// 第一种
var twoSum = function(nums, target) {
    let re = []
    for (let i = 0;i<nums.length;i++){
        let item = nums[i]
        let j = nums.indexOf(target-item)
        if (j > -1) {
            if (j !==i){
              return [i, j]
            }

        }
    }
};

// 第二种
var twoSum = function (nums, target) {
    let map = {};
    for (let i = 0, len = nums.length; i < len; i++) {
        let num = target - nums[i];
        if (typeof map[nums[i]] === 'number') return [map[nums[i]], i];
        map[num] = i;
    }
};

// 第三种 （超出输出范围？）
var twoSum = function(nums, target) {
    for(let j =0;j<nums.length;j ++) {
        console.log(j,nums[j])
      for(i=nums.length-1 ;i >j; i--) {
          console.log(nums[j],nums[i])
          if(nums[j] + nums[i] === target) {
              return [i, j]
          }
      }  
    }
};