此篇文章将记录我在LeeCode上刷过的题目与解答。
难度由简单开始。
两数之和
给定一个整数数组 nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
const twoSum = function(nums, target){
//构造map对象
const map = new Map()
//遍历nums
for (let i = 0; i < nums.length; i++) {
let result = target-nums[i]
//判断map中是否有result，有的话返回结果，没有就将nums[i]作为key，i作为value存入map中
if(map.has(result)) return [map.get(result), i]
map.set(nums[i],i)
}
}
整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [ ,
− 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
var reverse = function(x) {
let MIN = Math.pow(-2, 31)
let MAX = Math.pow(2, 31) - 1
if(x<0){
x = -x
let temp = x.toString().split('').reverse().join('');
if(temp < MIN || temp > MAX){
return 0
}else{
return -temp
}
}else{
let temp = x.toString().split('').
if(temp < MIN || temp > MAX){
return 0
}else{
return temp
}
}
};
回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
var isPalindrome = function(x) {
if(x<0){
//如果参数小于0，那么倒序肯定不是回文数
return false
}else{
let arr = x.toString().split('')
if(arr[arr.length-1] === '0' && arr.length > 1) return false //转化为数组后，如果长度大于0并且最后一位是0，那么也不是回文数
if(arr.toString() === arr.reverse().toString()){
return true
}else{
return false
}
}
};
罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符: 数值
I: 1
V: 5
X: 10
L: 50
C: 100
D: 500
M: 1000
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
- 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
var romanToInt = function(s) {
//先将特殊情况排列
const special = {
I: ['V', 'X'],
X: ['L', 'C'],
C: ['D', 'M']
}
// 以字符为key，数字为value放入对象中
const map = {I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000}
//记录上一次的字符
let last = ''
//存放每个字符对等数字的数组
const result = [];
// 遍历参数s
for(let char of s){
//如果上一位字符存在special中，并且所对应的数组含有char，那么就属于特殊规则，第一次遍历不会成立！
if(special[last] && special[last].includes(char)){
//这里，其实IV === 4， 我们可以看作此时的V === 3，依次类推
result.push(map[char] - (map[last] * 2))
}else{
result.push(map[char])
last = ''
}
//如果此次的char在special中存在，那么我们要准备好他与下一位字符可能会是特殊规则
if(special[char]) {
last = char;
}
}
return result.reduce((a,b) => a+b)
};
反正这个方法很慢就是了-。-
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (strs.length === 0) return ''
//如果输入数组只有一个元素，那么这个元素本事就是最长公共前缀
if (strs.length === 1) return strs[0]
let result = '' //用来存放结果
strs.sort((a, b)=> a.length>b.length) //将输入数组排序，数组长度升序，这样我们可以以长度最短的字符串作为基准
let shortest = strs[0]
// 双循环遍历，当输入数组中其中一个字符串不包含这个字符，就return result，结束程序
for( let i = 0; i < shortest.length; i++ ){
for( let j = 0; j < strs.length; j++){
if(shortest[i] !== strs[j][i]) return result
}
result += shortest[i]
}
return result
};
有效的括号
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
//有效的括号，多想一想我们就能明白，如果是有效的括号，那么必然字符串靠左的一部分是 ( or [ or {，
//如果不是这样的，那么必然不是有效括号
const arr= [];
//如果参数s为空字符串，不会进入循环，直接return
for(let i = 0; i < s.length; i++) {
let char = s.charAt(i)
if (char == '(' || char == '[' || char == '{'){
arr.push(char)
} else {
if(arr.length === 0) return false
//到这里时，已经不可能是 ( or { or [, 如果他与前一位是有效的括号，那么他必定和 topChar匹配
let topChar = arr.pop()
if (char == ')' && topChar != '(') return false
if (char == ']' && topChar != '[') return false
if (char == '}' && topChar != '{') return false
}
}
//如果参数s是有效的字符串，那么遍历到最后，arr的length必定是0
return !arr.length;
};
