记录下自己的思路与能理解的解法,可能并不是最优解法,不定期持续更新~
1.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
个人想法: 就是找出x轴与y轴相乘哪个最大, 水往下流, 所以两个y轴取最小的数
// /**
// * 暴力解,这解法数据多的时候会很慢
// * @param {number[]} height
// * @return {number}
// */
// var maxArea = function (height) {
// if (height.length <= 0) return height[0]
// let maxNumber = 0
// for (let index = 0; index < height.length; index++) {
// const item = height[index]
// for (let i = index; i < height.length; i++) {
// const diff = i - index
// const num = diff * Math.min(height[i], item)
// maxNumber = Math.max(maxNumber,num)
// }
// }
// return maxNumber
// };
/**
* 双指针解法
*/
var maxArea = function (height) {
if (height.length <= 0) return height[0]
let maxNumber = 0
let left = 0
let right = height.length - 1
while (left < right) {
const num = (right - left) * Math.min(height[left], height[right])
maxNumber = Math.max(maxNumber, num)
if (height[left] < height[right]) {
left++
} else {
right--
}
}
return maxNumber
};
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))
2.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
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];
} else{
map.set(nums[i], i)
}
}
return []
};
3.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
个人想法:每一个按键逐层递加,
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function (digits) {
if (digits.length == 0) return [];
const map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
};
const length = digits.length
const queue = []
queue.push('')
for (let i = 0; i < length; i++) {
const levelSize = queue.length; // 当前层的节点个数
for (let u = 0; u < levelSize; u++) {
const current = queue.shift()
const letters = map[digits[i]]
for (const l of letters) {
queue.push(current + l); // 生成新的字母串入列
}
}
}
return queue
};
console.log(letterCombinations("232"))
4.两数相除
会溢出,这是我能解的程度了,正确的看不懂
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function (dividend, divisor) {
const INT_MIN = -Math.pow(2, 31)
const INT_MAX = Math.pow(2, 31) - 1
if (dividend == INT_MIN && divisor == -1) return INT_MAX
// 处理边界，防止转正数溢出
// 除数绝对值最大，结果必为 0 或 1
if (divisor == INT_MIN) {
return dividend == divisor ? 1 : 0;
}
let isMinus = false
if (divisor < 0) isMinus = !isMinus
if (dividend < 0) isMinus = !isMinus
let result = 0
dividend = Math.abs(dividend)
divisor = Math.abs(divisor)
if (dividend === divisor) {
result = 1
} else {
while (dividend > divisor) {
dividend = dividend - Math.abs(divisor)
console.log(dividend, divisor)
result++
}
}
return isMinus ? -result : result
};
console.log(divide(-10, 3))
5.三数之和
个人题目理解:
1.三个数加起来为0
2.下标不能一样
3.数组不能一样
- 用三个循环的方式也可以,就是会溢出
注意测试用例太多的时候别在里面打log...
var threeSum = function (nums) {
nums.sort((a, b) => a - b) //排序
const arr = [] //记录符合条件的数组
const length = nums.length
for (let i = 0; i < length; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
// nums[i] 为"定数",与左右三个数相加,符合条件(为0)的添加进数组
let left = i + 1
let right = length - 1
while (left < right) {
const sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
arr.push([nums[i], nums[left], nums[right]])
while (left < right && nums[left] == nums[left + 1]) left++ // 去重
while (left < right && nums[right] == nums[right - 1]) right-- // 去重
left++
right--
} else if (sum < 0) {
// 数字太小,向右移
left++
} else if (sum > 0) {
// 数字太大,向左移
right--
}
}
}
return arr
};
console.log(threeSum([-1,0,1,2,-1,-4]))
6.N 字形变换
var convert = function (s, numRows) {
if (numRows === 1 || s.length <= numRows) {
return s;
}
const result = Array(numRows).fill('');
let row = 0;
let direction = -1;
for (let i = 0; i < s.length; i++) {
result[row] += s[i];
if (row === 0 || row === numRows - 1) {
direction *= -1;
}
row += direction;
}
return result.join('');
};
就是先准备numRows.length个数组，假设是3,依次从左到右，从上到下将字符串推进数组，再转为字符串输出
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
let result = []
let resultStr = ''
let state = 'add'
let pointer = 0
const length = s.length - 1
s = [...s]
s.forEach((item, index) => {
if (state === 'add') {
result[pointer] = result[pointer] === undefined ? [item] : [...result[pointer], item]
pointer++
if (pointer === numRows - 1) state = 'minus'
} else {
result[pointer] = result[pointer] === undefined ? [item] : [...result[pointer], item]
pointer--
if (pointer === 0) state = 'add'
}
})
result.flat(Infinity).forEach(item => resultStr += item)
return resultStr
}; pointer--
if (pointer === 0) state = 'add'
}
})
return result.flat(Infinity).join('')
};
7.旋转图像
个人理解:第一排对应右边第一排,第二排对应右边第二排…以此类推,那么拿到长度后,从右边开始递减赋值.例如第一排123对应每排数组的第length - 第一排的位置,
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
const length = matrix[0].length - 1
const copyMatrix = JSON.parse(JSON.stringify(matrix))
copyMatrix.forEach((item, index) => {
item.forEach((i, key) => {
matrix[key][length - index] = i
})
return item
})
return matrix
};
console.log(rotate([
[5, 1, 9, 11],
[2, 4, 8, 10],
[13, 3, 6, 7],
[15, 14, 12, 16]
]), '------------')
8.组合总和
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
const result = []
const deep = (consistute, diff, pointer) => {
// 到数组尽头了停止递归
if (pointer === candidates.length) return;
// target已经被整减,可以添加数组,并且已经没有值了,无需往下执行
if (diff === 0) {
result.push(consistute)
return
}
// 先跳过一部分,例如该例子target是7,7>3会进入if分支,7-3=4再次进入递归来到if分支,diff变成4的时候
// 4依然>3,4-3=1,1<3,这就进行不下去了.
// 所以需要在第一步7-3时,进入递归,递归中再次进入递归(第一个递归,指针需要+1),那么就变成diff 4 - 2
// 然后diff变成2,进入if分支的deep ,2-2==0,return出去
deep(consistute, diff, pointer + 1)
if (diff - candidates[pointer] >= 0) {
deep([...consistute, candidates[pointer]], diff - candidates[pointer], pointer)
}
}
deep([], target, 0)
return result
};
console.log(combinationSum([7, 6, 3, 2], 7), '------------')
9. 外观数列
个人想法:就是数数,数几个一样的,比如"1",就是一个一,那就写作"11",下一次就是两个一,就写作"21",再下次就是一个二一个一,写作’1211’…以此类推
/**
* @param {number} n
* @return {string}
*/
var countAndSay = function(n) {
const deep = (remainRow, num) => {
if (remainRow === 0) return num
const numArr = Array.from(num)
let tempNum = ''
let contrast = numArr[0]
let count = 0
const length = numArr.length - 1
numArr.forEach((item, index) => {
if (item === contrast) {
count++
} else {
tempNum += count + numArr[index - 1]
contrast = item
count = 1
}
if (index === length) tempNum += count + item
})
return deep(remainRow - 1, tempNum)
}
return deep(n - 1, '1')
};
console.log(countAndSay(4))
10. 有效的数独
- 个人想法:每一行、每一列、每个3x3去除’.'后,判断去重后数组长度是否与原数组长度一致,不一致就是出现多次,就无效
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function (board) {
// 用来验证结果
let result = true
// 其实这两个都是9,只是这么写灵活点
const length = board.length
const rowLength = board[0].length
// 用于"数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。"时盛放的容器
// 到时会将例子编写为变量的[
// [5,3,6,9,8],
// [7,1,9,5,]
// .....
// ]
let resetBoard = Array.from({
length: length
}).fill([])
for (let index = 0; index < length; index++) {
// 装每一行去除'.'的数据
let row = []
// 装每一列去除'.'的数据
let column = []
for (let index2 = 0; index2 < rowLength; index2++) {
if (board[index][index2] !== '.') {
// 装进行
row.push(board[index][index2])
// 这部分是装进'resetBoard'那个步骤的,
// 逻辑是:Math.floor(行 / 3) * 3 + Math.floor(列 / 3)
// 举例子:第三行那个6,就是 (3 / 3) * 3 + (7 / 3) = 0 * 3 + 2.333 = 0 + 2 ,放在下标为2的位置
// 举例子:第四行那个6,就是 (4 / 3) * 3 + (4 / 3) = 1 * 3 + 1 = 3 + 1 ,放在下标为4的位置
const index3 = Math.floor(index / 3) * 3 + Math.floor(index2 / 3)
resetBoard[index3] = [...resetBoard[index3], board[index][index2]]
}
// 装进列
if (board[index2][index] !== '.') column.push(board[index2][index])
}
// 如果是去重后数组长度与原数组长度不一致,那就是有重复的,返回false
result = [...new Set(row)].length === row.length
if (!result) return result
result = [...new Set(column)].length === column.length
if (!result) return result
}
// 判断3x3的数组有没有重复
for (let index = 0; index < rowLength; index++) {
result = [...new Set(resetBoard[index])].length === resetBoard[index].length
if (!result) return result
}
return result
};
console.log(isValidSudoku(
[
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]))
11.最接近的三数之和
个人理解: 不断相加, 减target最小的就替换
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
// 计算总数
let sum = 0
// 用来判断是否更接近target,如果是就替换
let diff = null
// 排序
nums = nums.sort((a, b) => a - b)
const length = nums.length
for (let index = 0; index < length; index++) {
// 排序后是从小到大的,这里有三个指针,一个是遍历数组的下标,一个是遍历数组下标的前一位,一个是数组的末尾
// 如果大于目标值了,right就向左一步(就是让数字变小),如果小于目标值了,就让lef右一步(就是让数字变大)
let left = index + 1
let right = length - 1
while (left < right) {
// 当前总和数
const tempSum = nums[index] + nums[left] + nums[right]
const tempDiff = target - tempSum
if (diff === null || Math.abs(tempDiff) < Math.abs(diff)) {
diff = tempDiff
sum = tempSum
}
if (tempSum < target) left++
else if (tempSum > target) right--
else if (tempSum == target) {
sum = tempSum
break
}
}
}
return sum
};
console.log(threeSumClosest([-1, 2, 1, -4, 5, 0], -7))
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
if(nums.length==3) return nums[0]+nums[1]+nums[2]
const len = nums.length
let result = nums[0]+nums[1]+nums[2];
for (let i = 0; i < len-2; i++) {
for (let j = i + 1; j < len-1; j++) {
for (let k = j+1; k < len; k++) {
// console.log(target - sum,nums[k]);
if(Math.abs(nums[i] + nums[j] + nums[k] - target) < Math.abs(result - target)) {
result = nums[i] + nums[j] + nums[k]
}
}
}
}
return result
};
12.最长回文子串
思路: 就是一个字符串,某一截翻转前跟反转后要一致,如例子’babad’所示,遍历到第二位时,left 与 right指针都是1,于是符合条件,左右指针分别向两边挪一位,判断是否一致,如果一致就继续执行上面动作直至到达边界.
然后判断哪个回文子串最长,就返回
var longestPalindrome = function (s) {
let longest = '';
let length = s.length
for (let i = 0; i < length; i++) {
// 奇数
const add = expandAroundCenter(s, i, i)
// 偶数
const even = expandAroundCenter(s, i, i + 1)
const diff = even.length > add.length ? even : add
longest = longest.length > diff.length ? longest : diff
}
// 中心扩展法
function expandAroundCenter(s, left, right) {
while (left >= 0 && right <= length && s[left] === s[right]) {
left--
right++
}
return s.slice(left + 1, right)
}
return longest;
};
console.log(longestPalindrome("babad"))
13.罗马数字转整数
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
const romeList = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000
}
let result = 0
const length = s.length
for (let index = 0; index < length; index++) {
// 先找出对应的数字
const value = romeList[s[index]]
//如果含有特殊符号就减,否则就加
if (value < romeList[s[index + 1]]) {
result -= value
} else {
result += value
}
}
return result
};
14.整数转罗马数字
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function (num) {
let result = ''
const remoList = {
1: 'I',
4: 'IV',
5: 'V',
9: 'IX',
10: 'X',
40: 'XL',
50: 'L',
90: 'XC',
100: 'C',
400: 'CD',
500: 'D',
900: 'CM',
1000: 'M'
}
// 数字数组
const numKey = Object.keys(remoList)
// 简单判断下数字大小决定从哪里开始
let right = num > 40 ? numKey.length - 1 : 7
const deep = (num) => {
// 如果能减的动就添加罗马数字,并且使num变为剩余数字
let diff = num - numKey[right]
if (diff >= 0) {
result += remoList[numKey[right]]
num = diff
}
// 如果指针大于0 才减,以免尾数减不尽,如果num<0表示尾数减完了,就停止
// diff < numKey[right] 用来判断整数的情况,例如20-10 还有10,还要减当前数,所以right不用--
if (right > 0 && num > 0 && diff < numKey[right]) {
right--
} else if (num <= 0) {
return
}
deep(num)
}
deep(num)
return result
};
console.log(intToRoman(20))
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function (num) {
const arr = ['I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M'];
const numArr = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000];
let str = '';
for (let i = numArr.length - 1; i >= 0; i--) {
if (num >= numArr[i]) {
str += arr[i];
num -= numArr[i];
i++
}
}
return str
};
15.可以攻击国王的皇后
在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。
给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。
//思路:从国王开始八个方向出发,记录第一个遇到的皇后
/**
* @param {number[][]} queens
* @param {number[]} king
* @return {number[][]}
*/
var queensAttacktheKing = function(queens, king) {
let y = king[0]
let x = king[1]
let top = y
let left = x
let right = x
let bottom = y
let count = 0
let queensMap = new Map();
queens.forEach(item => {
let key = item.join("");
queensMap.set(key, item);
});
let max = 7
let result = {
'left': undefined,
'right': undefined,
'top': undefined,
'bottom': undefined,
'upperLeft': undefined,
'upperRight': undefined,
'leftLower': undefined,
'rightLower': undefined,
}
while (max >= 0) {
top--
left--
right++
bottom++
count++
max--
if (!result.top && queensMap.has(`${top}${x}`)) {
result.top = queensMap.get(`${top}${x}`)
}
if (!result.left && queensMap.has(`${y}${left}`)) {
result.left = queensMap.get(`${y}${left}`)
}
if (!result.right && queensMap.has(`${y}${right}`)) {
result.right = queensMap.get(`${y}${right}`)
}
if (!result.bottom && queensMap.has(`${bottom}${x}`)) {
result.bottom = queensMap.get(`${bottom}${x}`)
}
if (!result.upperLeft && queensMap.has(`${y - count}${x - count}`)) {
result.upperLeft = queensMap.get(`${y - count}${x - count}`)
}
if (!result.upperRight && queensMap.has(`${y - count}${x + count}`)) {
result.upperRight = queensMap.get(`${y - count}${x + count}`)
}
if (!result.leftLower && queensMap.has(`${y + count}${x - count}`)) {
result.leftLower = queensMap.get(`${y + count}${x - count}`)
}
if (!result.rightLower && queensMap.has(`${y + count}${x + count}`)) {
result.rightLower = queensMap.get(`${y + count}${x + count}`)
}
}
return Object.values(result).filter(item => item)
};
//大佬的脑子:
var queensAttacktheKing = function(queens, king) {
queen_pos = new Set();
for (const queen of queens) {
let x = queen[0], y = queen[1];
queen_pos.add(x * 8 + y);
}
const ans = [];
for (let dx = -1; dx <= 1; ++dx) {
for (let dy = -1; dy <= 1; ++dy) {
if (dx == 0 && dy == 0) {
continue;
}
let kx = king[0] + dx, ky = king[1] + dy;
while (kx >= 0 && kx < 8 && ky >= 0 && ky < 8) {
let pos = kx * 8 + ky;
if (queen_pos.has(pos)) {
ans.push([kx, ky]);
break;
}
kx += dx;
ky += dy;
}
}
}
return ans;
};
16.字符串相乘
个人理解:可以拿张纸用乘法算一下,其实就是把我们平时的乘法运算逻辑变成代码
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function (num1, num2) {
if (num1 === '0' || num2 === '0') return '0'
let multiplication = []
let num1Length = num1.length
let num2Length = num2.length
let result = new Array(num1Length + num2Length).fill(0)
// 从个位数开始乘
for (let reverseIndex = num1Length - 1; reverseIndex >= 0; reverseIndex--) {
for (let reverseIndex2 = num2Length - 1; reverseIndex2 >= 0; reverseIndex2--) {
const p1 = reverseIndex + reverseIndex2
const p2 = reverseIndex + reverseIndex2 + 1
// 相乘再加进位,这里的p2就是上一循环的进位p1
let sum = num1[reverseIndex] * num2[reverseIndex2] + result[p2]
// 进位
result[p1] += Math.floor(sum / 10)
result[p2] = sum % 10
}
}
if (result[0] === 0) result.shift()
return result.join('')
};
console.log(multiply('123', '456'))
17.找出字符串中第一个匹配项的下标
- 个人思路:比较简单,就一个个截取出来匹配正不正确
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle) {
const length = haystack.length
const needleLen = needle.length
for (let index = 0; index < length; index++) {
const temp = haystack.slice(index, index + needleLen)
if (temp === needle) return index
if (index === length - 1) return -1
}
};
console.log(strStr('leetcode', 'leeto'))
18.搜索旋转排序数组
- 说是中级难度,但是简单到有点不可置信,可能因为我没有极致优化速度跟内存…
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
return nums.findIndex(v => v === target)
};
console.log(search([4, 5, 6, 7, 0, 1, 2], 0))
var search = function (nums, target) {
let result = -1
let length = nums.length
if (target < nums[0]) {
for (let index = length - 1; index >= 0; index--) {
const item = nums[index];
if (item === target) return index
}
} else {
for (let index = 0; index < length; index++) {
const item = nums[index];
if (item === target) return index
}
}
return result
};
console.log(search([4, 5, 6, 7, 0, 1, 2], 0))
19. 删除有序数组中的重复项 II
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
//用来判断是否超过2
let count = 0
//下标
let left = 0
while (left < nums.length) {
//如果当前的数跟上一位一样count就+1,否则就重置进入下一循环
if (nums[left] === nums[left - 1]) {
count++
//超过2就删除一位 ,否则进入下一循环, splice会改变原数组,所以不++
count > 1 ? nums.splice(left, 1) : left++
} else {
count = 0
left++
}
}
return nums.length
};
20.在排序数组中查找元素的第一个和最后一个位置
var searchRange = function (nums, target) {
// 先找到第一个元素,如果没有找到说明整个数组都没有,直接返回[-1,-1]
let point = nums.findIndex(item => item === target)
if (point === -1) return [-1, -1]
const length = nums.length
let left = point
let right = length - 1
let first = point
let end = false
// 现在就直接从后面开始找最后面的,找到立马返回
while (left <= right) {
if (nums[right] === target) {
return [first, right]
} else {
right--
}
};
};
// 这种方式vscode是可以运行的,不知道为什么力扣报没有findLastIndex这个方法
var searchRange = function (nums, target) {
let left = nums.findIndex(item => item === target)
if (left === -1) return [-1, -1]
let right = nums.findLastIndex(item2 => item2 === target)
return [left, right]
}
console.log(searchRange([5, 7, 7, 8, 8, 10], 8))
21.跳跃游戏
var canJump = function (nums) {
// 必须到达end下标的数字
let end = nums.length - 1;
for (let i = nums.length - 2; i >= 0; i--) {
if (end - i <= nums[i]) {
end = i;
}
}
return end == 0;
};
// console.log(canJump([2, 0, 0]))
// console.log(canJump([3,2,1,0,4]))
// console.log(canJump([2, 0, 2]))
// console.log(canJump([1,0,2]))
// console.log(canJump([0, 2, 3]))
console.log(canJump([2,3,1,1,4]))
22.全排列
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const result = [];
const length = nums.length
const deep = (arr) => {
if (arr.length === length) {
result.push([...arr])
return
}
for (const item of nums) {
if(!arr.includes(item)){
arr.push(item)
deep(arr)
arr.pop()
}
}
}
deep([])
return result
};
23.多数元素
/**
* @param {number[]} nums
* @return {number}
*/
//大佬做法
var majorityElement = function(nums) {
const n = nums.length;
nums = nums.sort((a,b) => a-b);
if (nums[0] === nums[Math.floor(n / 2)]) {
return nums[0]
} else if (nums[n - 1] === nums[Math.floor(n / 2)]) {
return nums[n - 1];
}
return nums[Math.floor(n / 2)]
};
//我的做法
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
const target = Math.floor(nums.length / 2)
const count = {}
nums.forEach(item => {
count[item] ? count[item]++ : count[item] = 1
})
for (const key in count) {
if (count[key] > target) return key
}
};
24.轮转数组
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
if (k > nums.length) {
// 这种写法需要的时间比较长,就是一遍遍地将最后一个往第一个加
for (let index = 0; index < k; index++) {
nums.unshift(nums.pop())
}
} else {
// 这个就快一点,直接裁剪最后的部分往前加,但是当k大于nums长度的时候就不行
nums.unshift(...nums.splice(nums.length - k, nums.length))
}
return nums
};
console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3))
25.买卖股票的最佳时机
/**
* @param {number[]} prices
* @return {number}
*/
let maxProfit = function (prices) {
let diff = 0
let minValue = prices[0]
for (const item of prices) {
diff = Math.max(diff, item - minValue)
minValue = Math.min(item, minValue)
}
return diff
};
console.log(maxProfit([7, 5, 1, 3, 6, 4]))
26.买卖股票的最佳时机 II
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
//今天比昨天钱多就累计起来
let totle = 0
const length = prices.length
for (let index = 1; index < length; index++) {
const item = prices[index];
const diff = item - prices[index - 1]
if (diff > 0) totle += diff
}
return totle
};
27.H 指数
用人话解释这道题是这样的:因为h是文章数量， 有3个超过引用3次的文章，所以是3， 如果5或6，就需要是有5篇超过被引用5次的文章，6同理。
/**
* @param {number[]} citations
* @return {number}
*/
var hIndex = function (citations) {
citations = citations.sort((a, b) => a - b)
let result = 0;
let index = citations.length - 1
while (index >= 0 && citations[index] > result) {
result++
index--
}
return result
};
console.log(hIndex([0, 1]))
28.加油站
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function (gas, cost) {
let totalGas = 0; // 总剩余油量
let currentGas = 0; // 当前起点的剩余油量
let start = 0; // 起点
let length = gas.length
for (let index = 0; index < length; index++) {
totalGas += gas[index] - cost[index]
currentGas += gas[index] - cost[index]
if (currentGas < 0) {
start = index + 1
currentGas = 0
}
}
if (totalGas >= 0) {
return start;
} else {
return -1;
}
};
console.log(canCompleteCircuit([1,2,3,4,5],[3,4,5,1,2]))
29.最后一个单词的长度
/**
* @param {string} s
* @return {number}
*/
var lengthOfLastWord = function(s) {
const arr = s.split(' ').filter(item => item != '')
return arr[arr.length - 1].length
};
30.翻转字符串中的单词
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function (s) {
const arr = s.split(' ')
const length = arr.length
let result = ''
for (let index = length; index >= 0; index--) {
const item = arr[index];
if (item) result += `${item} `
}
return result.substring(0, result.length - 1)
};
console.log(reverseWords("the sky is blue"))
/**
* @param {string} s
* @return {string}
*/
let reverseWords = function(s) {
return s.split(/[\s]+/).filter(e=>e!="").reverse().join(" ")
};
31.验证回文串
先统一去除非数字与字母的字符,转小写,再左右两方对比
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
s = s.replace(/[\W_]/g, '').toLowerCase();
let left = 0
let right = s.length - 1
while (left < right) {
if (s[left] != s[right]) return false
left++
right--
}
return true
};
32.判断子序列
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
let target = 0
const length = t.length
for (let index = 0; index < length; index++) {
const element = t[index];
if (s[target] === element) target++
}
return target === s.length
};
33.两数之和 II - 输入有序数组
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let left = 0,
right = numbers.length - 1;
while (left < right) {
const total = numbers[left] + numbers[right]
if (total === target) {
return [left + 1, right + 1]
} else if (total > target) {
right--
} else if(total < target) {
left++
}
}
};
console.log(twoSum( [5,25,75], 100))
34.长度最小的子数组
我们使用两个指针，一个左指针 left 和一个右指针 right 来定义一个滑动窗口。
初始时，左指针和右指针都指向数组的第一个元素，窗口大小为1。
我们计算窗口内所有元素的总和（从左指针到右指针），并将其与目标值进行比较。
如果窗口内元素的总和小于目标值，我们将右指针向右移动，扩大窗口，以便窗口内的总和变大。
如果窗口内元素的总和大于或等于目标值，我们记录当前窗口的长度（right - left + 1），然后将左指针向右移动，缩小窗口，以寻找更小的长度。
重复步骤4和步骤5，直到遍历完整个数组。在此过程中，我们不断调整窗口大小，以找到满足条件的最小子数组。
最终，我们得到了满足条件的最小子数组的长度。
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (target, nums) {
let result = Infinity
let left = 0
let sum = 0
const length = nums.length
for (let index = 0; index < length; index++) {
sum += nums[index];
while (sum >= target) {
result = Math.min(result, index - left + 1)
sum -= nums[left];
left++
}
}
return result === Infinity ? 0 : result
};
console.log(minSubArrayLen(7, [2,3,1,2,4,3]))
35.无重复字符的最长子串
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let newMap = new Map()
const length = s.length
let result = 0
let start = 0
for (let index = 0; index < length; index++) {
const item = s[index];
if (newMap.has(item)) {
start = Math.max(newMap.get(item) + 1, start)
}
newMap.set(item, index)
result = Math.max(result, index - start + 1)
}
return result
};
console.log(lengthOfLongestSubstring("pwwkew"))
36.火柴拼正方形
文章来源：https://www.toymoban.com/news/detail-723329.html
/**
* @param {number[]} matchsticks
* @return {boolean}
*/
var makesquare = function(matchsticks) {
if(matchsticks.length<4)return false
let total = matchsticks.reduce((i,x)=>x+=i)
if(total%4) return false
matchsticks.sort((a,b)=>b-a)
const SIDE = total/4
if(matchsticks[0]>SIDE)return false
let edges = [0,0,0,0]
const dfs = (i) => {
if(i === matchsticks.length)return true
for(let k = 0;k<4;k++){
if(edges[k] + matchsticks[i] > SIDE || (k&&edges[k]===edges[k-1]))continue
edges[k] += matchsticks[i]
if(dfs(i+1))return true
edges[k] -= matchsticks[i]
}
return false
}
return dfs(0);
};
37.单词搜索
文章来源地址https://www.toymoban.com/news/detail-723329.html
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board = [
["C", "A", "A"],
["A", "A", "A"],
["B", "C", "D"]
], word = "AAB") {
const rows = board.length;
const cols = board[0].length;
const dfs = (i, j, count) => {
// 超出范围与不符合字母的去除
if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] !== word[count]) {
return false
}
// 符合所有条件直接返回true
if (count === word.length - 1) return true
// 临时删除已经使用的字母
const temp = board[i][j]
board[i][j] = '/'
// 往四面散开排查
const found =
dfs(i - 1, j, count + 1) ||
dfs(i + 1, j, count + 1) ||
dfs(i, j - 1, count + 1) ||
dfs(i, j + 1, count + 1)
// 回显之前的字母到数组
board[i][j] = temp
return found
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false
};
console.log(exist())
到了这里，关于刷一下算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
