前言
看算法确实会让编码思路有所不同,看完好的方案,就会觉得自己的很low
。今年开始尽量每天一道算法题,卷死自己,长期更新
Question
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。 有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合
示例:
示例 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)
感触
坚持是真难哦,工作、生活各种事情忙起来就各种没时间,话说也才搞了一周都坚持不起来了,惜败惜败
标签:index,押韵,const,target,nums,item,算法,let,生锈 From: https://blog.51cto.com/u_14627797/7809088