每天一算法，脑子不生锈（真押韵）

前言

看算法确实会让编码思路有所不同，看完好的方案，就会觉得自己的很low。今年开始尽量每天一道算法题，卷死自己，长期更新

Question

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合

示例：

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([)]"
输出：false

示例 5：
输入：s = "{[]}"
输出：true

Answer

思路：对称性符合栈后入先出特性

// const s = '{[()]}'
const s = '()[]{}'
const arr = s.split('')
const obj = {
  "(": ")",
  "[": "]",
  "{": "}"
}
const stack = []
const valdate = data => {
  if (!data || data.length % 2 !== 0) return false
  let isRight = true
  data.split('').forEach(item => {
    if (obj[item]) {
      stack.push(item)
    } else {
      if (!stack.length || obj[stack.pop()] !== item) {
        isRight = false
      }
    }
  })
  if (stack.length) isRight = false
  return isRight
}
console.log(valdate(s)) // true

2023-02-02

Question

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

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

输入：nums = [3,3], target = 6
输出：[0,1]

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

Answer

const nums = [2, 7, 11, 15], target = 9;
  // const nums = [3, 2, 4], target = 6
  // const nums = [3, 3], target = 6
  // const twoSum = function(nums, target) {
  //   let i = 0
  //   let next
  //   let isFind = false
  //   while(i < nums.length - 1 && !next) {
  //     const current = nums[i]
  //     if (current >= 9) {
  //       i++
  //     } else {
  //       nums.forEach((item, index) => {
  //         if (i !== index && item + current === target) {
  //           next = index
  //         }
  //       })
  //       if (!next) i++
  //     }
  //   }
  //   if (next) {
  //     return [i, next]
  //   }
  // }
  // console.log(twoSum(nums, target))
  // 减少一层循环（时间复杂度）
  var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0, len = nums.length;i < len;i++) {
      if(map.has(target - nums[i])) {
          return [map.get(target - nums[i]), i];
      }
      map.set(nums[i], i);
    }
    return [];
  };
  console.log(twoSum(nums, target))

2023-02-03

Question

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

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

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

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

输入: s = ""
输出: 0

Answer

// 方便参考，输出连带字符串结果
const s = 'abcabcbb'
// const s = "bbbbb"
// const s = "pwwkew"
// const s = ''
const lengthOfLongestSubstring = (s) => {
  let str = ''
  let index = 0
  let obj = { len: index, str }
  if (!s) return obj
  s.split('').forEach(item => {
    if(str.includes(item)) {
      const { len } = obj
      if (index > len) obj = { len: index, str }
      index = 1
      str = item
    } else {
      str += item
      index++
    }
  })
  return obj
}
const { len, str } = lengthOfLongestSubstring(s)
console.log(len, str)

Question

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入：nums = [0]
输出：[[],[0]]

Answer

const nums = [1, 2, 3]
// const subsets = nums => {
//   if (nums.length === 0) return [[]];
//   let resArr = [];
//   backtrack(nums, 0, [], resArr);
//   return resArr;
// };
// function backtrack(nums, index, subArr, resArr) {
//   if (Array.isArray(subArr)) {
//     resArr.push(subArr.slice());
//   }
//   if (index === nums.length) {
//     return;
//   } 
//   for (let i = index; i < nums.length; i++) {
//     subArr.push(nums[i]);
//     backtrack(nums, i + 1, subArr, resArr);
//     subArr.pop();
//   }
// }
// subsets(nums)
const getAllSubsets = nums => nums.reduce(
  (subsets, value) => subsets.concat(
    subsets.map(set => [value,...set])
  ),
[[]]);

console.log(getAllSubsets(nums));

Question

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

Answer

// 如何减少遍历？这么搞打败不了对手啊
const strs = ["flower","flow","flight"]
// const strs = ["dog","racecar","car"]
// const strs = ["aab123v", 'aab123b', 'aba123a']
const longestCommonPrefix = strs => {
  strs.sort((a, b) => a.length - b.length)
  const [firtst, ...others] = strs
  let s = ''
  let isOver = false
  for(let i = 0; i < firtst.length; i++) {
    others.forEach(item => {
      if (item[i] !== firtst[i]) isOver = true
    })
    if (!isOver) {
      s += firtst[i]
    }
  }
  return s
};
longestCommonPrefix(strs)

感触

坚持是真难哦，工作、生活各种事情忙起来就各种没时间，话说也才搞了一周都坚持不起来了，惜败惜败