跳到主要内容

5 篇博文 含有标签「algorithm」

查看所有标签

暴力枚举​

var twoSum = function (nums, target) {
  const n = nums.length

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (nums[i] + nums[j] === target && i !== j) {
        return [i, j]
      }
    }
  }
}

哈希表​

var twoSum = function (nums, target) {
  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    }
    map.set(nums[i], i)
  }
}
algorithm阅读需 1 分钟

排序+双指针​

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b)

  const ans = []
  const n = nums.length

  for (let i = 0; i < n - 2; i++) {
    // 当前元素不等于上一个元素
    if (i > 0 && nums[i] == nums[i - 1]) continue

    // 优化
    if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break
    if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue

    let j = i + 1
    let k = n - 1

    while (j < k) {
      const sum = nums[i] + nums[j] + nums[k]

      if (sum > 0) {
        k--
      } else if (sum < 0) {
        j++
      } else {
        ans.push([nums[i], nums[j], nums[k]])

        j++
        while (j < k && nums[j] === nums[j - 1]) {
          j++
        }

        k--
        while (j < k && nums[k] === nums[k + 1]) {
          k--
        }
      }
    }
  }

  return ans
}
algorithm阅读需 1 分钟

无重复字符的最长子串​

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
var lengthOfLongestSubstring = function (s) {
  const counter = {}
  let ans = 0
  let left = 0

  for (let right in s) {
    counter[s[right]] = (counter[s[right]] || 0) + 1

    while (counter[s[right]] > 1) {
      counter[s[left]] -= 1
      left++
    }

    ans = Math.max(ans, right - left + 1)
  }

  return ans
}

时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符）。

长度最小的子数组​

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
var minSubArrayLen = function (target, nums) {
  let ans = Infinity
  let sum = 0
  let left = 0

  for (let right in nums) {
    sum += nums[right]

    while (sum >= target) {
      ans = Math.min(ans, right - left + 1)
      sum -= nums[left]
      left++
    }
  }

  return ans <= nums.length ? ans : 0
}

乘积小于 K 的子数组​

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

输入：nums = [1,2,3], k = 0
输出：0
var numSubarrayProductLessThanK = function (nums, k) {
    if (k <= 1) return 0

    let left = 0
    let count = 0
    let product = 1

    for (let right = 0; right < nums.length; right++) {
        product *= nums[right]

        while (product >= k) {
            product /= nums[left]
            left++
        }

        count += right - left + 1
    }

    return count
};

最小覆盖子串​

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
function minWindow(s, t) {
  const charCount = new Map()
  let left = 0,
    minLen = Infinity,
    minWindowStart = 0,
    charsToMatch = t.length

  // 初始化字符计数
  for (const char of t) {
    charCount.set(char, (charCount.get(char) || 0) + 1)
  }

  for (let right = 0; right < s.length; right++) {
    const rightChar = s[right]

    if (charCount.has(rightChar) && charCount.get(rightChar) > 0) {
      charsToMatch--
    }

    charCount.set(rightChar, (charCount.get(rightChar) || 0) - 1)

    // 缩小左窗口
    while (charsToMatch === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1
        minWindowStart = left
      }

      const leftChar = s[left]
      charCount.set(leftChar, (charCount.get(leftChar) || 0) + 1)

      if (charCount.get(leftChar) > 0) {
        charsToMatch++
      }

      left++
    }
  }

  return minLen === Infinity ? '' : s.substr(minWindowStart, minLen)
}
algorithmsliding-window阅读需 4 分钟

以下是有关双指针相关算法的题目与题解。

移除元素​

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

我的解法​

var removeElement = function (nums, val) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === val) {
      nums.splice(i, 1)
      i--
    }
  }

  return nums.length
}

然而 splice 操作时间复杂度为 O(n)，并且每次删除一个元素都会导致数组的重新排序。因此在算法解题中应尽量避免使用数组自带方法操作

方法: 双指针​

var removeElement = function (nums, val) {
  let left = 0,
    right = nums.length
  while (left < right) {
    if (nums[left] === val) {
      nums[left] = nums[right - 1]
      right--
    } else {
      left++
    }
  }
  return left
}

如果题目有要求排序的话，不如将符合条件(nums[i] !== val)的元素移到数组头部，这样就不需要排序了。

var removeElement = function (nums, val) {
  const n = nums.length
  let left = 0

  for (let right = 0; right < n; right++) {
    if (nums[right] !== val) {
      nums[left] = nums[right]
      left++
    }
  }

  return left
}

删除有序数组中的重复项​

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。

我的解法​

var removeDuplicates = function (nums) {
  const counter = {}
  let count = 0
  for (let i = 0; i < nums.length; i++) {
    counter[nums[i]] = (counter[nums[i]] || 0) + 1

    if (counter[nums[i]] > 2) {
      continue
    } else {
      nums[count] = nums[i]
      count++
    }
  }

  return count
}

思路很清晰，就是用一个计数对象来计数，然后遍历数组，如果计数大于 1，就跳过，否则就赋值。不过我这里引入了 counter 对象，因此空间复杂度为 O(k)，其中 k 表示不同元素的数量。

如果以我这个思路去解决 删除有序数组中的重复项 II 解决题目就会特别容易，只需要将 > 1 换成 1 即可。不过题目要求 不使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

并且通常哈希计数针对无序而言，而题目所给定的数据又有序，因此想要解得好就需要采用其他方案。

方法: 双指针​

由于题目声明输入 升序排列 的数组，因此采用快慢双指针来判断后一个元素是否等于前一个，如果不相等则说明是不同的元素，慢指针(不同数字次数)加一，快指针继续遍历。

var removeDuplicates = function (nums) {
  const n = nums.length

  let fast = 1,
    slow = 1
  while (fast < n) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast]
      ++slow
    }
    ++fast
  }
  return slow
}

判断子序列​

我的解法(失败)​

既然判断子序列，那我就把无关元素删除，然后判断最后元素是否包含即可。

var isSubsequence = function (s, t) {
  t = t.replace(new RegExp(`[^${s}]`, 'g'), '')
  return t.includes(s)
}

然而假设输入数据为

s = "leetcode"
t = "yyyyyleeeytcode"

处理后数据为

s = "leetcode"
t = "leeetcode"

很显然这里 includes 无法判断子序列，因此这种思路不可行。

方法: 双指针​

var isSubsequence = function (s, t) {
  let i = 0,
    j = 0
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) {
      i++
    }
    j++
  }

  return i === s.length
}

两数之和 II - 输入有序数组​

方法: 双指针​

function twoSum(nums, target) {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) {
      return [left, right]
    }

    if (sum > target) {
      right--
    } else if (sum < target) {
      left++
    }
  }
}
algorithmdouble-pointer阅读需 4 分钟

快乐数​

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 02 = 1

我的解法​

var isHappy = function (n) {
  let deep = 0
  while (n !== 1 && deep < 10) {
    const digits = n.toString().split('')

    n = 0
    digits.forEach(num => {
      n += Math.pow(num, 2)
    })

    deep++
  }

  return n === 1
}

这个解法其实很粗糙，通过肯定是能通过的，但有几个很明显的问题。

  1. 首先在数位分离我采用 n.toString().split('') ，不过这是借用到了 js 的特性，要是换其他语言肯定不行。
  2. 重复计算，比如 19 第一次计算 1² + 9² = 82，第二次计算 8² + 2² = 68，第三次计算 6² + 8² = 100 ...，这里的 8² 就可以将其结果存起来，避免重复计算。
  3. 因为存在某些数(如 2)会无限循环，所以需要设置一个深度限制 deep，不然会死循环。

改进​

在数位分离上可以依次使用 num % 10 来得到 个十百...位, 通过下方代码则可以得到所有位上的数字。

function getDigist(nums) {
  let digits = []
  while (nums > 0) {
    digits.unshift(nums % 10)
    nums = Math.floor(nums / 10)
  }

  return digits
}

getDigist(1234)

而要避免重复运算最简单就是使用哈希集合，将计算过的结果存起来。

const cache = {}

digits.forEach(num => {
  if (!cache[num]) {
    cache[num] = Math.pow(num, 2)
  }

  n += cache[num]
})

然而现在还有一个问题，就是如何处理 deep 的问题，由于官方题解中对于这部分给出分析，这里便不赘述了。如果一个数不是快乐数，那么它一定存在一个循环，可以将生成循环链的数字存入哈希集合中来判断是否处于无限循环中。最终代码如下

var isHappy = function (n) {
  function getDigist(nums) {
    let digits = []
    while (nums > 0) {
      digits.unshift(nums % 10)
      nums = Math.floor(nums / 10)
    }
    return digits
  }

  const cache = {}
  const set = new Set()

  while (n !== 1 && !set.has(n)) {
    const digits = getDigist(n)
    set.add(n)

    n = 0
    digits.forEach(num => {
      if (!cache[num]) {
        cache[num] = Math.pow(num, 2)
      }

      n += cache[num]
    })
  }

  return n === 1
}

最长连续序列​

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

我的解法

  1. 对数组去重并排序
  2. 判断 nums[i] === nums[i+1] - 1，为真则缓存当前最长序列的长度
  3. 不符合条件则重新计算当前最长序列的长度，取 maxLen 和 currentLen 最大值作为返回值
var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0

  nums = [...new Set(nums)]
  nums = nums.sort((a, b) => a - b)

  const n = nums.length

  let maxLen = 0
  let currentLen = 0

  for (let i = 0; i < n - 1; i++) {
    if (nums[i] === nums[i + 1] - 1) {
      currentLen++
    } else {
      maxLen = Math.max(maxLen, currentLen)
      currentLen = 0
    }
  }

  maxLen = Math.max(maxLen, currentLen) + 1

  return maxLen
}

哈希表​

var longestConsecutive = function (nums) {
  let numSet = new Set(nums)

  let maxLen = 0

  for (let num of numSet) {
    if (!numSet.has(num - 1)) {
      let currentNum = num
      let currentLen = 1

      while (numSet.has(currentNum + 1)) {
        currentNum++
        currentLen++
      }

      maxLen = Math.max(maxLen, currentLen)
    }
  }

  return maxLen
}

解释: 只有当一个数是连续序列的第一个数的情况下才会进入内层循环 if (!numSet.has(num - 1))，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。

单词规律​

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

我的解法​

var wordPattern = function (pattern, s) {
    // 提取 pattern 的索引 { a: [0,3], b:[1,2] }
    const rules = {}
    pattern.split('').forEach((p, i) => {
        rules[p] ||= []
        rules[p].push(i)
    })

    const words = s.match(/[a-z]+\b/g)

    for (let value of Object.values(rules)) {
        const group = new Set()

        for (let v of value) {
            if (group.size === 0) {
                group.add(words[v])
            }

            if (!group.has(words[v])) {
                return false
            }

            group.add(words[v])
        }
    }
    return true
};

而对于下列数据会返回 true，显然是不符合条件的。

pattern = "abba"

s = "dog dog dog dog"

原因就在于 ab 要不同，因此就需要改进验证组 group。

于是就想到既然提取 pattern 的索引，不如也提取 words 索引，然后判断两者值

var wordPattern = function (pattern, s) {
    function convertArray(arr) {
        const result = [];
        let charMap = {};

        for (let i = 0; i < arr.length; i++) {
            const char = arr[i];
            if (charMap[char] === undefined) {
                charMap[char] = [i];
            } else {
                charMap[char].push(i);
            }
        }

        for (const char in charMap) {
            result.push(charMap[char]);
        }

        return result;
    }

  	// "abba" => [[0, 3], [1, 2]]
    const patternValues = convertArray(pattern)
    // "dog cat cat dog" => [[0, 3], [1, 2]]
    const wordValues = convertArray(s.match(/[a-z]+\b/g))

    for (let i in patternValues) {
        if (JSON.stringify(patternValues[i]) !== JSON.stringify(wordValues[i])) {
            return false
        }
    }

    return true
};

然而我没想到，但有字母为 constructor 时，wordsRules[w] 就会变成 wordsRules[constructor] 相当于下图所示。

image-20230921010005890

不过也好解决，因为这里的 key a,b,dog,cat 事实上我们都没用到。只需要把{ a: [0,3], b: [1,2] } 转成 [[0,3], [1,2]] 即可。

然而我发现 将 "abba" 转成 [[0,3], [1,2]] 在不借助 Object.values() 情况下是一件很困难的事情。于是既然 {}[constructor] 不行，那么我就用 Map.get() 来解决便可。贴上 convertArray 函数代码

function convertArray(arr) {
        const result = [];
        const charMap = new Map();

        for (let i = 0; i < arr.length; i++) {
            const char = arr[i];
            if (charMap.has(char)) {
                charMap.get(char).push(i);
            } else {
                charMap.set(char, [i]);
            }
        }

        charMap.forEach((indices) => result.push(indices));

        return result;
    }

很显然，上述的解法缺陷很多，这里就不一一列举了，直接来看正确答案。

正确答案​

var wordPattern = function (pattern, s) {
    const word2ch = new Map();
    const ch2word = new Map();
    const words = s.split(' ');
    if (pattern.length !== words.length) {
        return false;
    }

    for (const [i, word] of words.entries()) {
        const ch = pattern[i];
        if (word2ch.has(word) && word2ch.get(word) != ch || ch2word.has(ch) && ch2word.get(ch) !== word) {
            return false;
        }
        word2ch.set(word, ch);
        ch2word.set(ch, word);
    }
    return true;
};Ï

要判断一个集合与另一个集合是否相同的关系叫「双射」，利用 两个哈希集合的 key 与 value 来判断便可。

同构字符串​

有了上题解题思路，这题就容易许多了。

var isIsomorphic = function(s, t) {
    const s2t = {};
    const t2s = {};
  
    for (let i = 0; i < s.length; ++i) {
        const x = s[i], y = t[i];
        if ((s2t[x] && s2t[x] !== y) || (t2s[y] && t2s[y] !== x)) {
            return false;
        }
        s2t[x] = y;
        t2s[y] = x;
    }
    return true;
};
algorithmhash-table阅读需 7 分钟