刷题不在多，需要举一反三
1. 两数之和
javascript
// 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
let result = target - nums[i]
if (nums.lastIndexOf(result) !== -1 && nums.lastIndexOf(result) !== i) {
return [i, nums.lastIndexOf(result)]
}
}
}
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
let result = nums.lastIndexOf(target - nums[i])
if (result > i) {
return [i, result]
}
}
}
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
}
var twoSum = function (nums, target) {
let map = new Map()
for (let i = 0; i < nums.length; i++) {
let k = target - nums[i]
if (map.has(k)) {
return [map.get(k), i]
}
map.set(nums[i], i)
}
return []
}2. 两数相加
javascript
// 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
let c = 0
let r = new ListNode()
let p = r
let p1 = l1
let p2 = l2
while (p1 || p2 || c) {
c += (p1 && p1.val) + (p2 && p2.val)
p.next = new ListNode(c % 10)
c = parseInt(c / 10)
p1 && (p1 = p1.next)
p2 && (p2 = p2.next)
p = p.next
}
return r.next
}3. 无重复字符的最长子串
javascript
// 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
/**
* @param {string} s
* @return {number}
*/
// var lengthOfLongestSubstring = function (s) {
// let arr = [], max = 0;
// for (let i = 0; i < s.length; i++) {
// let index = arr.indexOf(s[i]);
// if (index !== -1) {
// arr.splice(0, index + 1);
// }
// arr.push(s.charAt(i));
// max = Math.max(arr.length, max);
// }
// return max;
// };
var lengthOfLongestSubstring = function (s) {
let index = 0,
max = 0
for (let i = 0, j = 0; j < s.length; j++) {
index = s.substring(i, j).indexOf(s[j])
if (index === -1) {
max = Math.max(max, j - i + 1)
} else {
i = i + index + 1
}
}
return max
}7. 整数反转
javascript
// 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
/**
* @param {number} x
* @return {number}
*/
var reverse = function (x) {
var result = 0
var sign = Math.sign(x)
x = Math.abs(x)
while (x != 0) {
result = result * 10 + (x % 10)
x = (x / 10) | 0
}
if (result > 2147483647 || result < -2147483648) {
return 0
}
return sign * result
}9. 回文数
javascript
// 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function (x) {
return x.toString() === x.toString().split('').reverse().join('')
}13. 罗马数字转整数
javascript
// 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
// 字符 数值
// I 1
// V 5
// X 10
// L 50
// C 100
// D 500
// M 1000
// 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
// 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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 的范围内。
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function (s) {
const map = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000,
}
let req = 0
for (let i = 0; i < s.length; i++) {
if (i < s.length && map[s[i]] < map[s[i + 1]]) {
req -= map[s[i]]
} else {
req += map[s[i]]
}
}
return req
}17. 电话号码的字母组合
javascript
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function (digits) {
if (digits.length <= 0) return []
let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
let num = digits.split('')
let code = []
num.forEach((item) => {
if (map[item]) {
code.push(map[item])
}
})
let comb = (arr) => {
let tmp = []
if (arr.length == 1) {
for (let i = 0; i < arr[0].length; i++) {
tmp.push(arr[0][i])
}
return tmp
} else {
for (let i = 0; i < arr[0].length; i++) {
for (let j = 0; j < arr[1].length; j++) {
tmp.push(`${arr[0][i]}${arr[1][j]}`)
}
}
arr.splice(0, 2, tmp)
if (arr.length > 1) {
comb(arr)
} else {
return tmp
}
return arr[0]
}
}
return comb(code)
}20.有效的括号
javascript
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
let map = {
'{': '}',
'(': ')',
'[': ']',
}
let stack = []
for (let i = 0; i < s.length; i++) {
if (map[s[i]]) {
stack.push(s[i])
} else if (s[i] !== map[stack.pop()]) {
return false
}
}
return stack.length === 0
}
/**
* @param {string} s
* @return {boolean}
*/
let isValid = function (s) {
let sl = s.length
if (sl % 2 !== 0) return false
let leftToRight = {
'{': '}',
'[': ']',
'(': ')',
}
// 建立一个反向的 value -> key 映射表
let rightToLeft = createReversedMap(leftToRight)
// 用来匹配左右括号的栈
let stack = []
for (let i = 0; i < s.length; i++) {
let bracket = s[i]
// 左括号 放进栈中
if (leftToRight[bracket]) {
stack.push(bracket)
} else {
let needLeftBracket = rightToLeft[bracket]
// 左右括号都不是 直接失败
if (!needLeftBracket) {
return false
}
// 栈中取出最后一个括号 如果不是需要的那个左括号 就失败
let lastBracket = stack.pop()
if (needLeftBracket !== lastBracket) {
return false
}
}
}
if (stack.length) {
return false
}
return true
}
function createReversedMap(map) {
return Object.keys(map).reduce((prev, key) => {
const value = map[key]
prev[value] = key
return prev
}, {})
}21. 合并两个有序链表
javascript
// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function (l1, l2) {
if (l1 === null) return l2
let cur = l1
while (l2) {
let node = new ListNode()
if (cur.val >= l2.val) {
node.val = cur.val
node.next = cur.next
cur.val = l2.val
cur.next = node
l2 = l2.next
} else if (cur.next && l2.val <= cur.next.val) {
node.val = l2.val
node.next = cur.next
cur.next = node
l2 = l2.next
} else if (!cur.next) {
node.val = l2.val
node.next = null
cur.next = node
l2 = l2.next
continue
}
cur = cur.next
}
return l1
}89. 格雷编码
javascript
// 格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
// 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
// 格雷编码序列必须以 0 开头。
/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function (n) {
let make = (n) => {
if (n === 1) {
return ['0', '1']
} else {
let prev = make(n - 1)
let result = []
let max = Math.pow(2, n) - 1
for (let i = 0; i < prev.length; i++) {
result[i] = `0${prev[i]}`
result[max - i] = `1${prev[i]}`
}
return result
}
}
return make(n)
}
var grayCode = function (n) {
let make = (n) => {
if (n === 1) return [0, 1]
let result = make(n - 1)
let highBit = 1 << (n - 1)
for (let i = result.length - 1; i >= 0; i--) {
result.push(result[i] + highBit)
}
return result
}
if (n === 0) return [0]
return make(n)
}
var grayCode = function (n) {
let res = [0]
for (let i = 0; i < n; i++) {
res = res.concat(res.map((item) => (1 << i) + item).reverse())
}
return res
}164. 最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。 如果数组元素个数小于 2，则返回 0。 示例 1:输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9]**_, _**其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 示例 2:输入: [10] 输出: 0 解释: 数组元素个数小于 2，因此返回 0。
javascript
/**
* @param {number[]} nums
* @return {number}
*/
var maximumGap = function (nums) {
if (nums.length < 2) return 0
nums.sort((a, b) => a - b)
// 保存相邻元素的最大差值
let max = 0
let temp = []
for (let i = 0; i < nums.length - 1; i++) {
temp = nums[i + 1] - nums[i]
if (temp > max) {
max = temp
}
}
return max
}258. 各位相加
javascript
// 给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
/**
* @param {number} num
* @return {number}
*/
var addDigits = function (num) {
let arr = []
for (let index of num.toString()) {
arr.push(index)
}
if (arr.length === 1) {
return parseInt(arr[0])
}
let number = 0
for (let i = 0; i < arr.length; i++) {
number += parseInt(arr[i])
}
if (number > 9) {
return addDigits(number)
} else {
return number
}
}349. 两个数组的交
javascript
// 给定两个数组，编写一个函数来计算它们的交集。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function (nums1, nums2) {
let arr1 = Array.from(new Set(nums1))
let arr2 = Array.from(new Set(nums2))
let arr3 = new Array()
for (let [v, k] of arr1.entries()) {
if (arr2.includes(k)) {
arr3.push(k)
}
}
return arr3
}
var intersection = function (...arrs) {
let res = arrs[0]
for (let i = 1; i < arrs.length; i++) {
res = res.filter((item) => arrs[i].includes(item))
}
return [...new Set(res)]
}605. 种花问题
javascript
// 605. 种花问题
// 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
// 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function (flowerbed, n) {
let max = 0
for (let i = 0; i < flowerbed.length - 1; i++) {
if (flowerbed[i] === 0) {
if (i === 0 && flowerbed[1] === 0) {
max++
i++
} else if (flowerbed[i - 1] === 0 && flowerbed[i + 1] === 0) {
max++
i++
}
}
}
return max >= n
}
// var canPlaceFlowers = function (flowerbed, n) {
// let count = 1, sum = 0;
// for (val of flowerbed) {
// if (val == 1) {
// if (count > 1) sum += Math.floor((count - 1) / 2);
// count = 0;
// } else {
// count++;
// }
// }
// if (count > 1) sum += Math.floor(count / 2);
// return sum >= n;
// };914. 卡牌分组
javascript
// 给定一副牌，每张牌上都写着一个整数。
// 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
// 每组都有 X 张牌。
// 组内所有的牌上都写着相同的整数。
// 仅当你可选的 X >= 2 时返回 true。
/**
* @param {number[]} deck
* @return {boolean}
*/
var hasGroupsSizeX = function (deck) {
if (deck.length <= 1) return false
deck.sort((a, b) => {
a - b
})
let min = Number.MAX_SAFE_INTEGER
let dst = []
let result = true
let tmp = []
for (let i = 0; i < deck.length; i++) {
tmp.push(deck[i])
for (let j = i + 1; j < deck.length - 1; j++) {
if (deck[i] === deck[j]) {
tmp.push(deck[j])
} else {
if (min > tmp.length) {
min = tmp.length
}
dst.push([].concat(tmp))
tmp.length = 0
i = j
break
}
}
}
dst.every((item) => {
if (item.length % min !== 0) {
result = false
return false
}
})
return result
}
var hasGroupsSizeX = function (deck) {
// 最大公约数计算公式
function gcd(num1, num2) {
// 利用辗转相除法来计算最大公约数
return num2 === 0 ? num1 : gcd(num2, num1 % num2)
}
// 相同牌出现次数Map
let timeMap = new Map()
// 遍历牌
deck.forEach((num) => {
// 统计每张牌出现的次数
timeMap.set(num, timeMap.has(num) ? timeMap.get(num) + 1 : 1)
})
// Map.protype.values()返回的是一个新的Iterator对象，所以可以使用扩展运算符(...)来构造成数组
let timeAry = [...timeMap.values()]
/*
最大公约数
因为该数组是出现次数数组，最小值至少为1（至少出现1次），所以默认赋值为数组首位对公约数计算无干扰
*/
let g = timeAry[0]
// 遍历出现次数，计算最大公约数
timeAry.forEach((time) => {
// 因为需要比较所有牌出现次数的最大公约数，故需要一个中间值
g = gcd(g, time)
})
// 判断是否满足题意
return g >= 2
}1047. 删除字符串中的所有相邻重复项
javascript
// 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
// 在 S 上反复执行重复项删除操作，直到无法继续删除。
// 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
/**
* @param {string} S
* @return {string}
*/
var removeDuplicates = function (S) {
let stack = []
for (const c of S) {
let prev = stack.pop()
if (prev !== c) {
stack.push(prev)
stack.push(c)
}
}
return stack.join('')
}1209. 删除字符串中的所有相邻重复项 II
javascript
// 给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
// 你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
// 在执行完所有删除操作后，返回最终得到的字符串。
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var removeDuplicates = function (s, k) {
let stack = []
for (const c of s) {
let prev = stack.pop()
if (!prev || prev[0] !== c) {
stack.push(prev)
stack.push(c)
} else if (prev.length < k - 1) {
stack.push(prev + c)
}
}
return stack.join('')
}1295. 统计位数为偶数的数字
javascript
// 给你一个整数数组 nums，
// 请你返回其中位数为 偶数 的数字的个数。
// 示例 1：
// 输入：nums = [12,345,2,6,7896]
// 输出：2
// 解释：
// 12 是 2 位数字（位数为偶数）
// 345 是 3 位数字（位数为奇数）
// 2 是 1 位数字（位数为奇数）
// 6 是 1 位数字 位数为奇数）
// 7896 是 4 位数字（位数为偶数）
// 因此只有 12 和 7896 是位数为偶数的数字
// 示例 2：
// 输入：nums = [555,901,482,1771]
// 输出：1
// 解释：
// 只有 1771 是位数为偶数的数字。
// 提示：
// 1 <= nums.length <= 500
// 1 <= nums[i] <= 10^5
/**
* @param {number[]} nums
* @return {number}
*/
var findNumbers = function (nums) {
let time = 0
for (let i = 0; i < nums.length; i++) {
if (String(nums[i]).length % 2 === 0) {
time++
}
}
return time
}
const findNumbers = (nums) =>
nums.reduce((prev, next) => prev + (String(next).length % 2 === 0 ? 1 : 0), 0)1313. 解压缩编码列表
javascript
// 给你一个以行程长度编码压缩的整数列表 nums 。
// 考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。
// 请你返回解压后的列表。
/**
* @param {number[]} nums
* @return {number[]}
*/
var decompressRLElist = function (nums) {
const result = []
for (let i = 1; i < nums.length; i++) {
if (i % 2 === 1) {
result.push(...Array.from(Array(nums[i - 1]), () => nums[i]))
}
}
return result
}1317. 将整数转换为两个无零整数的和
javascript
// 「无零整数」是十进制表示中 不含任何 0 的正整数。
// 给你一个整数 n，请你返回一个 由两个整数组成的列表 [A, B]，满足：
// A 和 B 都是无零整数
// A + B = n
// 题目数据保证至少有一个有效的解决方案。
// 如果存在多个有效解决方案，你可以返回其中任意一个。
/**
* @param {number} n
* @return {number[]}
*/
var getNoZeroIntegers = function (n) {
let time = 1
while (String(time).includes('0') || String(n - time).includes('0')) {
time++
}
return [time, n - time]
}剑指 Offer 11. 旋转数组的最小数字
javascript
// 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
/**
* @param {number[]} numbers
* @return {number}
*/
// var minArray = function (numbers) {
// for (let i = 0; i < numbers.length; i++) {
// if (numbers[i + 1] < numbers[i]) {
// return numbers[i + 1];
// }
// }
// return numbers[0];
// };
var minArray = function (numbers) {
let i = 0,
j = numbers.length - 1
while (i < j) {
const m = Math.floor((i + j) / 2)
if (numbers[m] > numbers[j]) {
i = m + 1
} else if (numbers[m] < numbers[j]) {
j = m
} else {
j--
}
}
return numbers[i]
}