数组-字符串
27. 移除元素
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
解法1
遍历一次如果相等往前覆盖
function removeElement(nums: number[], val: number): number {
let idx = 0
for(let num of nums) {
if(num!==val) {
nums[idx++] = num;
}
}
return idx;
}
26. 删除有序数组中的重复项
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
function removeDuplicates(nums: number[]): number {
let i = 1,j = 0;
for(; i< nums.length ;i++) {
if(nums[j] !== nums[i]){
nums[j++] = nums[i];
}
}
return j+1;
};
80. 删除有序数组中的重复项 II
示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
let i = 0;
for (let num of nums) {
if (i < 2 || num > nums[i - 2]) {
nums[i++] = num
}
}
return i
169. 多数元素
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
function majorityElement(nums: number[]): number {
let e = 0,j=0;
nums.forEach(num => {
if(j == 0) e = num;
j+=(e===num)?1:-1;
})
return e;
};
189. 轮转数组
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
function rotate(nums: number[], k: number): void {
let step = k %nums.length
for(let i=0;i<k;i++){
nums.unshift(nums.pop())
}
};
121. 买卖股票的最佳时机
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
//枚举 + 维护前缀最小值
function maxProfit(prices: number[]): number {
let ans = 0,min = prices[0];
prices.forEach(price => {
ans = Math.max(ans,price-min);
min = Math.min(min,price);
})
return ans;
};
122. 买卖股票的最佳时机 II
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0
function maxProfit(prices: number[]): number {
let ans = 0,min = prices[0];
prices.forEach(price => {
min = Math.min(min,price)
if(price-min>0) {
ans+=price-min;
min = price
}
})
return ans;
};
55. 跳跃游戏
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
function canJump(nums: number[]): boolean {
let cover = 0;
for(let i =0 ;i<=cover ;i++){
cover = Math.max(cover,i+nums[i]);
if(cover >= nums.length-1) return true;
}
return false
};
2 倒叙 只要index下标的值大于等于空间数就可以
function canJump(nums: number[]): boolean {
let len = nums.length,end = len-1;
for(let i = len-1 ;i>=0 ;i--){
if((end-i) <=nums[i]) end = i
}
return !end
};
45. 跳跃游戏 II
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
function jump(nums: number[]): number {
let step =0;
let currPosEnd = 0;
let maxPos =0
for(let i = 0; i< nums.length-1;i++){
maxPos =Math.max(maxPos,i+nums[i]);
if(i===currPosEnd){
currPosEnd = maxPos;
step++;
}
}
return step;
};
274. H 指数
示例 1：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
示例 2：
输入：citations = [1,3,1]
输出：1
function hIndex(citations: number[]): number {
const n =citations.length;
const cnt = new Array(n+10).fill(0);
citations.forEach(citation=> {
cnt[Math.min(citation,n)]++;
})
for(let i = n, tot = 0;i >= 0;i--){
tot += cnt[i];
if(tot >=i ) return i;
}
return -1;
}
380. O(1) 时间插入、删除和获取随机元素
输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]
解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
class RandomizedSet {
list: Array<number>;
map: object;
constructor() {
this.list = [];
this.map = {};
}
insert(val: number): boolean {
if (val in this.map) {
return false;
}
this.list.push(val);
this.map[val] = this.list.length - 1; // ->索引
return true;
}
remove(val: number): boolean {
if (val in this.map) {
// 找到要删除的元素的索引
const index = this.map[val];
let last = this.list[this.list.length - 1];
// 将尾部元素放到 要删除的元素的位置
this.list[index] = last;
this.map[last] = index;
// 删掉尾元素
delete this.map[val];
this.list.pop();
return true;
}
return false;
}
getRandom(): number {
const i = Math.floor(Math.random() * this.list.length);
return this.list[i];
}
}
238. 除自身以外数组的乘积
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const ans = new Array(n).fill(1);
for (let i = 1, j = 1; i <= n; i++) {
ans[i - 1] *= j; j *= nums[i - 1];
}
for (let i = n, j = 1; i >= 1; i--) {
ans[i - 1] *= j; j *= nums[i - 1];
}
return ans;
};
239. 滑动窗口最大值
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
function maxSlidingWindow(nums: number[], k: number): number[] {
const ans = [];
const q = [];
for(let i = 0;i < nums.length;i++){
while(q.length && nums[q[q.length-1]]<=nums[i]) {
q.pop();
}
q.push(i);
if(i - q[0] >= k){
q.shift();
}
if(i >= k - 1){
ans.push(nums[q[0]]);
}
}
return ans;
};
134. 加油站
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
解法1
two tasks，1个是找到起点，一个是统计油量
function canCompleteCircuit(gas: number[], cost: number[]): number {
let totalSum = 0;
let curSum = 0;
let start = 0;
for(let i = 0 ;i < gas.length ;i++){
totalSum += gas[i] - cost[i];
curSum += gas[i] - cost[i];
if(curSum < 0){
curSum = 0;
start = i + 1;
}
}
return totalSum < 0 ? -1 : start;
};
135. 分发糖果
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
function candy(ratings: number[]): number {
let n = ratings.length;
let dp = new Array(n).fill(1);
for(let i = 1;i < n;i++){
if(ratings[i] > ratings[i-1]) dp[i] = dp[i-1] +1;
}
for(let i = n-2;i >= 0;i--){
if(ratings[i] > ratings[i + 1]) dp[i] = Math.max(dp[i],dp[i+1] +1);
}
return dp.reduce((p,c)=> p+c)
};
42. 接雨水
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
function trap(height: number[]): number {
let ans = 0, left = 0, right = height.length - 1, lmax = 0, rmax = 0;
while (left < right) {
lmax = Math.max(lmax, height[left]);
rmax = Math.max(rmax, height[right]);
if (lmax < rmax) {
ans += lmax - height[left++];
} else {
ans += rmax - height[right--];
}
}
return ans;
};
罗马数字转整数
示例 1:
输入: s = "III"
输出: 3
示例 2:
输入: s = "IV"
输出: 4
示例 3:
输入: s = "IX"
输出: 9
示例 4:
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
function romanToInt(s: string): number {
const RomanDict: Record<string, number> = { M: 1000, D: 500, C: 100, L: 50, X: 10, V: 5, I: 1 };
let result = 0, max = 0;
for(let i = s.length-1 ;i >=0; i--){
const value = RomanDict[s[i]];
if(value < max) {
result -= value;
} else {
result += value;
max = value;
}
}
return result;
};
整数转罗马数字
示例 1:
输入: num = 3
输出: "III"
示例 2:
输入: num = 4
输出: "IV"
示例 3:
输入: num = 9
输出: "IX"
示例 4:
输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:
输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
function intToRoman(num: number): string {
const numToString = {
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'
};
let result = ''
const str = Object.keys(numToString);
//匹配数据 从max开始
for(let i = str.length-1;i>=0;i--){
const value = Number(str[i]);
if(num/value>=1){
result+= numToString[value];
num -= value;
i++;
}
if(num===0) {
break;
}
}
return result;
};
58. 最后一个单词的长度
示例 1：
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。
示例 2：
输入：s = " fly me to the moon "
输出：4
解释：最后一个单词是“moon”，长度为 4。
示例 3：
输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。
function lengthOfLastWord(s: string): number {
return s.trim().split(' ').slice(-1)[0].length
};
14. 最长公共前缀
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
function longestCommonPrefix(strs: string[]): string {
strs = strs.sort();
let a = strs[0],b = strs[strs.length-1];
let result = ''
for(let i = 0 ;i< a.length;i++){
if(a[i] === b[i]) result +=a[i]
else break;
}
return result;
};
151. 反转字符串中的单词
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
function reverseWords(s: string): string {
return s.match(/\b\w+\b/g).reverse().join(' ')
};
//
function reverseWords(s: string): string {
return s.split(' ').filter(item => item).reverse().join(' ');
};
6. Z 字形变换
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：s = "A", numRows = 1
输出："A"
function convert(s: string, numRows: number): string {
if(s.length<=numRows || numRows === 1){return s}
const arr = new Array(numRows).fill('')
let num = 0
let downflag = true
for(let i = 0 ;i< s.length ;i++){
arr[num] += s[i];
num +=downflag?1:-1;
if(num===0) downflag = true;
if(num===numRows-1) downflag=false;
}
return arr.join('')
};
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
function strStr(haystack: string, needle: string): number {
if(needle.length === 0) return 0
let arr = haystack.split(needle) //
if( arr.length > 0 && arr[0] !== haystack){
return arr[0].length
}else{
return -1
}
};
68. 文本左右对齐
示例 1:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:
输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
解法1
result 存储每行的结果 lineWords = 一行的长度 空格间距相等 => line 存储一行的数据
line.length = 空格间距
line.length + lineWords + words[i].length > maxWidth 表示可以组成，且不能在放其他的单词， maxWidth - lineWords => 空格数,line.length也是空格 循环加空格数 每个位置的空格就是 line[j%(line.length > 1? line.length-1:1)] += ' ', 设置区间避免空的情况line.length > 1? line.length-1:1 result.push(line.join('')) line = [] lineWords = 0; line.push(words[i]) linewords+=words[i].length; 最后一行时有可能不足maxWidth 因此就要添加空格和补充剩余参数padEnd(maxWith,' ')
function fullJustify(words: string[], maxWidth: number): string[] {
const result = [];
let line = [];
let lineLength = 0;
for (let i = 0; i < words.length; i++) {
if (lineLength + line.length + words[i].length > maxWidth) {
for (let j = 0; j < maxWidth - lineLength; j++) {
line[j % (line.length > 1 ? line.length - 1 : 1)] += ' '
}
result.push(line.join(''));
line = [];
lineLength = 0
}
line.push(words[i])
lineLength += words[i].length
}
result.push(line.join(' ').padEnd(maxWidth, ' '));
return result;
};
‘abc12d3456ef789gh’=>’a1b2c3d4e5f6g7h89’
function rearrange(str) {
const letters = str.match(/[a-zA-Z]/g) || [];
const numbers = str.match(/\d/g) || [];
let result = '';
for (let i = 0; i < Math.max(letters.length, numbers.length); i++) {
if (letters[i]) result += letters[i];
if (numbers[i]) result += numbers[i];
}
return result;
}
日期格式化
function format(date, formatString) {
const options = {
year: 'numeric',
month: '2-digit',
day: '2-digit'
};
return new Intl.DateTimeFormat('en-US', options).format(date).replace(/\//g, '-');
}
// Example usage
console.log(format(new Date(), 'YYYY-MM-DD'));
解析 URL 的参数
function parseUrlParams(url) {
const params = {};
const queryString = url.split('?')[1];
if (!queryString) return params;
const pairs = queryString.split('&');
for (const pair of pairs) {
const [key, value] = pair.split('=');
if (key in params) {
if (Array.isArray(params[key])) {
params[key].push(decodeURIComponent(value));
} else {
params[key] = [params[key], decodeURIComponent(value)];
}
} else {
params[key] = decodeURIComponent(value);
}
}
return params;
}