var merge = function(nums1, m, nums2, n) {
let p1 = m-1
let p2 = n-1
let p = m+n-1
while(p1 >= 0 && p2 >=0) {
if(nums1[p1]> nums2[p2]) {
nums1[p] = nums1[p1]
p1--
} else {
nums1[p] = nums2[p2]
p2--
}
p--
}
while(p2>=0) {
nums1[p] = nums2[p2]
p2--
p--
}
};var removeElement = function(nums, val) {
let p = 0
for(let i = 0; i < nums.length; i++) {
if(nums[i] !== val) {
nums[p++] = nums[i]
}
}
return p
};var removeDuplicates = function (nums) {
let p = 0
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[p]) {
p++
last = nums[i]
nums[p] = last
}
}
return p+1
};var removeDuplicates = function(nums) {
let p = 2
for(let i = 2; i < nums.length; i++) {
if(nums[i] !== nums[p-2]) {
nums[p] = nums[i]
p++
}
}
return p
};var majorityElement = function(nums) {
let count = 1
let curr = nums[0]
for(let i = 1; i < nums.length; i++) {
if(!count) {
curr = nums[i]
}
if(curr !== nums[i]) {
count--
} else {
count++
}
}
return curr
};var maxProfit = function(prices) {
let dp = new Array(prices.length).fill(0)
let min = prices[0]
for(let i = 1; i < prices.length; i++) {
min = Math.min(min, prices[i])
dp[i] = Math.max(dp[i-1], prices[i] - min)
}
return dp[prices.length - 1]
};var rotate = function(nums, k) {
k = k % nums.length;
const reverse = (left, right) => {
while(left<right) {
[nums[left], nums[right]] = [nums[right], nums[left]]
left++
right--
}
}
nums.reverse()
reverse(0,k-1)
reverse(k, nums.length - 1)
return nums
};var maxProfit = function(prices) {
let res = 0
for(let i=1;i<prices.length;i++) {
if(prices[i] > prices[i-1]) {
res+=prices[i] - prices[i-1]
}
}
return res
};var canJump = function(nums) {
let maxReach = 0
for(let i = 0; i< nums.length; i++) {
if(i>maxReach) {
return false
}
maxReach = Math.max(maxReach, i + nums[i])
if(maxReach >= nums.length - 1) {
return true
}
}
};var jump = function(nums) {
let steps = 0
let end = 0
let maxPosition = 0
for(let i = 0; i < nums.length-1; i++) {
maxPosition = Math.max(maxPosition, i+nums[i])
if(i === end) {
steps++
end = maxPosition
if(end >= nums.length - 1) {
break
}
}
}
return steps
};var hIndex = function(citations) {
let res = 0
citations.sort((a, b) => a -b)
for(let i = 0; i < citations.length; i++) {
if(citations[i] >= citations.length - i) {
return citations.length - i
}
}
return 0
};var RandomizedSet = function () {
this.nums = []
this.indices = new Map()
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
if (this.indices.has(val)) {
return false
}
this.indices.set(val, this.nums.length)
this.nums.push(val)
return true
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
if(!this.indices.has(val)) {
return false
}
const index = this.indices.get(val)
const lastNum = this.nums[this.nums.length - 1]
this.nums[index] = lastNum
this.indices.set(lastNum, index)
this.nums.pop()
this.indices.delete(val)
return true
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
const randomIndex = Math.floor(Math.random() * this.nums.length)
return this.nums[randomIndex]
};var productExceptSelf = function (nums) {
const len = nums.length
const left = new Array(len).fill(1)
const res = new Array(len).fill(1)
for (let i = 1; i < len; i++) {
left[i] = nums[i - 1] * left[i - 1]
}
let temp = 1
for(let i = len - 1; i>=0; i--){
if(i === len - 1) {
temp = 1
} else {
temp = nums[i+1] * temp
}
res[i] = temp * left[i]
}
return res
};var canCompleteCircuit = function(gas, cost) {
let total = 0
let cur = 0
let start = 0
for(let i = 0; i< gas.length; i++) {
let temp = gas[i] - cost[i]
total += temp
cur += temp
if(cur<0) {
start = i+1
cur = 0
}
}
return total >= 0 ? start : -1
};var romanToInt = function (s) {
const map = {
'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000
};
let ans = 0
for (let i = 0; i < s.length; i++) {
let curr = map[s[i]]
let next = map[s[i + 1]]
if (i < s.length - 1 && curr < next) {
ans -= curr
} else {
ans += curr
}
}
return ans
};var intToRoman = function (num) {
let arr = [[1000, "M"], [900, "CM"], [500, "D"], [400, "CD"],
[100, "C"], [90, "XC"], [50, "L"], [40, "XL"],
[10, "X"], [9, "IX"], [5, "V"], [4, "IV"], [1, "I"]]
let ans = ''
for (let i = 0; i < arr.length; i++) {
while (num >= arr[i][0]) {
num -= arr[i][0]
ans += arr[i][1]
}
}
return ans
};var trap = function (height) {
let left = 0
let maxLeft = 0
let right = height.length - 1
let maxRight = 0
let count = 0
while (left < right) {
if (height[left] < height[right]) { // 1. 左边矮，处理左指针
if (height[left] >= maxLeft) {
maxLeft = height[left]; // 更新左边最大值
} else {
count += maxLeft - height[left]; // 结算当前left位置的水量
}
left++; // 左指针右移
} else { // 2. 右边矮或相等，处理右指针
if (height[right] >= maxRight) { // 注：图中代码少了个等号，但不影响正确性
maxRight = height[right]; // 更新右边最大值
} else {
count += maxRight - height[right]; // 结算当前right位置的水量
}
right--; // 右指针左移
}
}
return count
};var candy = function(ratings) {
const n = ratings.length;
// 步骤 1：初始化每人 1 颗糖果
const candies = new Array(n).fill(1);
// 步骤 2：从左向右遍历，满足左规则
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// 步骤 3：从右向左遍历，满足右规则，并同时统计总糖果数
// 最后一个孩子的糖果数已经确定，可以直接加到总数里
let totalCandies = candies[n - 1];
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
// 取两者的最大值，确保同时满足左右两边的条件
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
totalCandies += candies[i];
}
return totalCandies;
};var lengthOfLastWord = function(s) {
let i = s.length - 1
let res = 0
while(i>=0 && s[i] === ' ') {
i--
}
while(i >= 0 && s[i] !== ' ') {
res++
i--
}
return res
};var longestCommonPrefix = function(strs) {
if(!strs|| strs.length === 0) return ''
for(let i = 0; i<strs[0].length; i++) {
let char = strs[0][i]
for(let j = 1; j < strs.length; j++) {
if(i === strs[j].length || strs[j][i] !== char) {
return strs[0].substring(0, i)
}
}
}
return strs[0]
};var convert = function(s, numRows) {
// 如果只有一行，或者字符串长度比行数还小，直接返回原字符串
if (numRows === 1 || s.length <= numRows) return s;
// 创建一个数组，里面有 numRows 个空字符串，代表每一行
const rows = new Array(numRows).fill("");
let curRow = 0;
let goingDown = false; // 初始方向
// 遍历每一个字符
for (let char of s) {
rows[curRow] += char; // 把字符加到当前行
// 在达到第一行或最后一行时，改变方向
if (curRow === 0 || curRow === numRows - 1) {
goingDown = !goingDown;
}
// 根据方向，行数 +1 或 -1
curRow += goingDown ? 1 : -1;
}
// 把所有行拼接成一个字符串返回
return rows.join("");
};var strStr = function(haystack, needle) {
return haystack.indexOf(needle);
};
var strStr = function(haystack, needle) {
const hLen = haystack.length;
const nLen = needle.length;
// 如果 needle 比 haystack 还长，绝对匹配不上
if (hLen < nLen) return -1;
// 只需要遍历到能够容纳 needle 的最后一个起始位置即可
for (let i = 0; i <= hLen - nLen; i++) {
// 截取当前位置开始、长度为 nLen 的子串
if (haystack.substring(i, i + nLen) === needle) {
return i;
}
}
return -1;
};var compareVersion = function(version1, version2) {
let n1 = version1.length, n2 = version2.length
let p1 = 0, p2 = 0
while(p1 < n1 || p2 < n2) { // 任一段没走完就继续（隐含补零）
let num1 = 0
while(p1 < n1 && version1[p1] !== '.') { // 内层：累加数字直到 '.' 或末尾
num1 = num1 * 10 + (+version1[p1]) // 字符转数字再累加
p1++
}
if(p1 < n1) p1++ // 跳过 '.'
let num2 = 0
while(p2 < n2 && version2[p2] !== '.') {
num2 = num2 * 10 + (+version2[p2])
p2++
}
if(p2 < n2) p2++
if(num1 !== num2) return num1 < num2 ? -1 : 1
}
return 0
};复杂度 O(N+M)，空间 O(1)；前导零和补零由”数字累加 + 未走完继续”天然处理。