算法hot150

算法hot150

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
nums1.splice(m,nums1.length-m,...nums2);
nums1.sort((a,b)=>a-b);
};

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。
1
2
3
4
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
let left = 0
for(let right =0;right<nums.length;right++){
    if(nums[right]!==val){
        nums[left]=nums[right]
        left++
    }
    
}
 return left
};

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

1
2
输入：nums = [3,2,3]
输出：3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
let candidate = nums[0];
  let count = 1;

  // Boyer-Moore 投票算法
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === candidate) {
      count++;
    } else {
      count--;
      if (count === 0) {
        candidate = nums[i];
        count = 1;
      }
    }
  }

  return candidate;
};

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1
2
3
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
if(nums.length<=2){
    return nums.length
}
let slow = 2,fast = 2;
while(fast<nums.length){
    if(nums[slow-2]!==nums[fast]){
        nums[slow]=nums[fast]
        slow++
    }
fast++
}
return slow
};

26. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
 if(nums.length === 0){
    return 0
 }
 let fast =1,slow=1
 while(fast<nums.length){
    if(nums[fast]!==nums[fast-1]){
        nums[slow]=nums[fast]
        slow++
    }
 fast++

 }
 return slow
};

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

1
2
3
4
5
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const n=nums.length
const newArr= new Array(n)
for(let i=0;i<n;++i){
    newArr[(i+k)%n]=nums[i]
}
for(let i=0;i<n;++i){
    nums[i]=newArr[i]
}

};

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const n=prices.length
    let min_price=0;
    let max_profile=0
if(n<2)
{return 0}
for (let i=1;i<n;i++){
    if(prices[i]<prices[min_price]){
        min_price=i
    }else{

        max_profile=Math.max(max_profile,prices[i]-prices[min_price])
    }
}
return max_profile
};

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

1
2
3
4
5
输入：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 。
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
let ans = 0
let n=prices.length
for(let i=1;i<n;++i){
    ans +=Math.max(0,prices[i]-prices[i-1]) 
}
return ans
};

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
let max_path =0
for(let i=0;i<nums.length&&i<=max_path;i++){
    max_path=Math.max(max_path,i+nums[i])
    if(max_path>=nums.length-1){
        return true
    }

}
return false
};

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
let jumps = 0;
    let currentJumpEnd = 0;
    let farthest = 0;
 
    for (let i = 0; i < nums.length - 1; i++) {
       
        farthest = Math.max(farthest, i + nums[i]);
        if (i === currentJumpEnd) {
            jumps++;
            currentJumpEnd = farthest;
            
            // 如果已经可以到达最后一个位置，就可以直接返回了
            if (currentJumpEnd >= nums.length - 1) {
                return jumps;
            }
        }
    }
    
    return jumps;
};

274. H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，**h 指数** 是其中最大的那个。

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3

380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
var RandomizedSet = function() {

    this.map = new Map()
    this.list =[]

};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
if(this.map.has(val)){
    return false
}
this.map.set(val, this.list.length)
this.list.push(val)
return true;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if (!this.map.has(val)) {
        return false;
    }
    const index = this.map.get(val)
    const last = this.list[this.list.length - 1];
    this.list[index] = last;
     this.map.set(last, index);
        this.list.pop();
    this.map.delete(val);

    return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
const randomindex = Math.floor(Math.random()*this.list.length)
return this.list[randomindex]
};

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
const n=nums.length
const a = new Array(n).fill(1)

let left = 1
let right = 1
for(let i=0;i<n;i++){
a[i]=left
left*=nums[i]
}
for(let i=n-1;i>=0;i--){
a[i]*=right
right*=nums[i]
}
return a
};

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

1
2
3
4
5
6
7
8
9
10
输入: 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 可为起始索引。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
let tol=0
let plus=0
let start =0
for(let i=0;i<gas.length;i++){
    tol +=gas[i]-cost[i]
    plus +=gas[i]-cost[i]
    if(plus<0){
        plus=0;
        start=i+1
    }
}
return tol>=0?start:-1
};

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

1
2
3
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
let n=ratings.length
const candies=new Array(n).fill(1)


for(let i=1;i<n;i++){
    if(ratings[i]>ratings[i-1]){
        candies[i]=candies[i-1]+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)
    }
}
return candies.reduce((sum,candy)=>sum+candy,0)
};

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

img

1
2
3
输入：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 个单位的雨水（蓝色部分表示雨水）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const n=height.length
let left = new Array(n).fill(0)
let right = new Array(n).fill(0)

left[0] = height[0];
for(let i=1;i<n;i++){
    left[i]=Math.max(height[i],left[i - 1])
}

right[n-1] = height[n-1];
for(let i=n-2;i>=0;i--){
     right[i] = Math.max(height[i], right[i + 1]);
}
let tol=0
for(let i=0;i<n;i++){
    tol+=Math.min(left[i],right[i])-height[i]
}
return tol
};

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
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
2
输入: s = "III"
输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const romanMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };
        let total = 0;
        for(let i=0;i<s.length;i++){
            const c=romanMap[s[i]]

            const n=romanMap[s[i+1]]
            if(n&&c<n){
                total-=c
            }else{
                total+=c
            }
        }
        return total
};

12. 整数转罗马数字

七个不同的符号代表罗马数字，其值如下：

符号 值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

  • 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
  • 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
  • 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    const romanMap = [
        { value: 1000, symbol: 'M' },
        { value: 900, symbol: 'CM' },
        { value: 500, symbol: 'D' },
        { value: 400, symbol: 'CD' },
        { value: 100, symbol: 'C' },
        { value: 90, symbol: 'XC' },
        { value: 50, symbol: 'L' },
        { value: 40, symbol: 'XL' },
        { value: 10, symbol: 'X' },
        { value: 9, symbol: 'IX' },
        { value: 5, symbol: 'V' },
        { value: 4, symbol: 'IV' },
        { value: 1, symbol: 'I' }
    ];
    let result = ''
    for(const{value,symbol}of romanMap){
        while (num>=value){
            result+=symbol
            num-=value
        }
    }
    return result
}

58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大

子字符串

1
2
3
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。
1
2
3
4
5
6
7
8
9
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
s=s.trim()
let last=s.lastIndexOf(' ')
return s.length-last-1
}

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    n=strs.length

if(n===0)return ""
let p = strs[0]
for(let i=1;i<n;i++){
    while(strs[i].indexOf(p)!==0){
        p=p.substring(0,p.length-1)
        if(p==="")return ""
    }
}
return p
};

151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格

1
2
输入：s = "the sky is blue"
输出："blue is sky the"
1
2
3
4
5
6
7
8
9
10
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
s=s.trim()
let words=s.split(/\s+/)
words.reverse();
return words.join(' ')
};

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);
1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
if(numRows===1||s.length<=numRows){
    return s
}
const rows = new Array(numRows).fill('')
let c=0
let d=false
for(const char of s){
    rows[c]+=char
    if(c===0||c===numRows-1){
        d=!d
    }
    c+=d?1:-1
}
return rows.join('')
};

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 
1
2
3
4
5
6
7
8
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
return haystack.indexOf(needle)
};

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 

1
2
3
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
const t = s.toLowerCase().replace(/[^a-z0-9]/g, '')

const reversedString = t.split('').reverse().join('');
    
    // 比较原字符串和反转后的字符串
    return t === reversedString;

};

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

1
2
输入：s = "abc", t = "ahbgdc"
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
let sp=0
let tp=0
while(sp<s.length&&tp<t.length){
    if(s[sp] ===t[tp]){
        sp++
    }
    tp++
}
return sp===s.length
};

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

1
2
3
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        // 使用位运算来代替加法，可能会稍微快一些
        const sum = (numbers[left] + numbers[right]) | 0;

        if (sum === target) {
            // 使用数组字面量而不是 new Array()
            return [left + 1, right + 1];
        }
        
        // 使用三元运算符来替代 if-else，可能会稍微快一些
        sum < target ? left++ : right--;

        // 利用排序数组的特性，跳过重复值
        while (left < right && numbers[left] === numbers[left - 1]) left++;
        while (left < right && numbers[right] === numbers[right + 1]) right--;
    }

    // 题目保证有唯一解，所以理论上不会到达这里
    return [];
 
};

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器

img

1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
let left = 0
let right = height.length-1
let max = 0
while(left<right){
    const w=right-left
    const h = Math.min(height[right],height[left])
const water = w*h
max =Math.max(max,water)
if(height[left]<height[right])
{
    left++
}else{
    right--
}
}
return max
};

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
const result = []
nums.sort((a,b)=>a-b)
for(let i =0 ;i<nums.length-2;i++){
    if(i>0&&nums[i]===nums[i-1])continue
let l=i+1
let r = nums.length-1
while (l<r){
    const sum =nums[i]+nums[r]+nums[l]
    if(sum===0){
        result.push([nums[i], nums[l], nums[r]]);
        while(nums[l]===nums[l+1])l++;
        while(nums[r]===nums[r-1])r--;

        l++
        r--
    }else if(sum<0){l++}
    else{r--}

}

}
return result
};

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
 let n = nums.length;
    let left = 0;
    let currSum = 0;
    let minLength = Infinity;

    for (let right = 0; right < n; right++) {
        currSum += nums[right];
        
        while (currSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            currSum -= nums[left];
            left++;
        }
    }

    return minLength !== Infinity ? minLength : 0;
};

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
let n= s.length
let set = new Set()
let ans =0,i=0,j=0;
while(i<n&&j<n){
    if(!set.has(s[j])){
        set.add(s[j++])
        ans = Math.max(ans,j-i)
    }else{
        set.delete(s[i++])
    }
}
return ans 
};

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

36. 有效的数独

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 空白格用 '.' 表示。

示例 1：

img

1
2
3
4
5
6
7
8
9
10
11
输入：board = 
[["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"]]
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
const rows=new Array(9).fill(0).map(()=>new Array(9).fill(0))
const columns =new Array(9).fill(0).map(()=>new Array(9).fill(0))
const nine =new Array(3).fill(0).map(()=>new Array(3).fill(0).map(()=>new Array(9).fill(0)))


for(let i=0;i<9;i++){
    for(let j=0;j<9;j++){
        const c=board[i][j]
        if(c!=='.'){
           const index=c.charCodeAt()- '0'.charCodeAt()-1
           rows[i][index]++
           columns[j][index]++
           nine[Math.floor(i/3)][Math.floor(j/3)][index]++

           if(rows[i][index]>1||columns[j][index]>1||nine[Math.floor(i/3)][Math.floor(j/3)][index]>1){
            return false
           }
        }
    }
}
return true
};

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
if(!matrix.length || !matrix[0].length){
    return []
}
const rows=matrix.length,columns=matrix[0].length
const order = []
let left =0,right = columns-1,top=0,bottom=rows-1

while(left<=right &&top<=bottom){

for(let i=left;i<=right;i++){
    order.push(matrix[top][i])
}
for(let row =top+1;row<=bottom;row++){
    order.push(matrix[row][right]);
}
if (left < right && top < bottom) {
            for (let column = right - 1; column > left; column--) {
                order.push(matrix[bottom][column]);
            }
            for (let row = bottom; row > top; row--) {
                order.push(matrix[row][left]);
            }
        }


[left, right, top, bottom] = [left + 1, right - 1, top + 1, bottom - 1];
}
 return order;
};

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

1
2
输入：ransomNote = "a", magazine = "b"
输出：false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
if(ransomNote.length>magazine.length){return false}
const cnt =new Array(26).fill(0)
for(const c of magazine){
    cnt[c.charCodeAt()-'a'.charCodeAt()]++
}
for (const c of ransomNote) {
        cnt[c.charCodeAt() - 'a'.charCodeAt()]--;
        if(cnt[c.charCodeAt() - 'a'.charCodeAt()] < 0) {
            return false;
        }
    }

return true

};

205. 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

1
2
输入：s = "egg", t = "add"
输出：true

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

示例 1：

img

1
2
输入：head = [1,2,2,1]
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var isPalindrome = function(head) {
    console.log(head)
    const vals = [];
    while (head !== null) {
        vals.push(head.val);
        head = head.next;
    }
    for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
        if (vals[i] !== vals[j]) {
            return false;
        }
    }
    return true;

 
};

160. 相交链表

已解答

简单

相关标签

相关企业

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 

1
2
3
4
5
6
7
8
9
10
11
12
var getIntersectionNode = function(headA, headB) {
        if (headA === null || headB === null) {
        return null;
    }
    let pA=headA,pB=headB
    while(pA!==pB){
        pA=pA===null?headB:pA.next
        pB=pB===null?headA:pB.next

    }
    return pA
};

226. 翻转二叉树

简单

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

img

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root === null) {
        return null;
    }
    const left = invertTree(root.left)
    const right = invertTree(root.right)
root.right=left
root.left=right
return root

};

206. 反转链表

简单

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
let curr=head
let prev=null
while(curr){
    const next =curr.next
    curr.next=prev
    prev=curr
    curr=next
}
return prev
};

136. 只出现一次的数字

简单（位运算）

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

1
2
输入：nums = [2,2,1]
输出：1
1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
let result=0
for(let i=0;i<nums.length;i++){
    result^=nums[i]
}
return result
};

141. 环形链表

简单

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    while(head){
    if(head.tag)
    {return true}
    head.tag=true
    head=head.next
    }
    return false
};

338. 比特位计数

简单

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

1
2
3
4
5
6
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

奇偶 + 位操作
示例
0 => 0
1 => 1
2 => 10
3 => 11
4 => 100
5 => 101
6 => 110
7 => 111
8 => 1000
归纳
设 dp(n) 为数字n二进制中1的个数
n为奇数
dp(n) = dp(n-1) + 1
n为偶数
dp(n) = dp(n/2)
初始化
result = [0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(num) {
    let result = [0];
    let n = 1;
    while(n <= num){
        let count = 0;
        if(n & 1 ==1){
            result[n] = result[n-1]+1;
        }else{
            result[n] = result[n>>1]
        }
        n++;
    }
    return result;
};

448. 找到所有数组中消失的数字

已解答

简单

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

1
2
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
var findDisappearedNumbers = function(nums) {
 let temp = new Array(nums.length + 1).fill(0); // 注意这里长度要 +1
    for (let i = 0; i < nums.length; i++) {
        temp[nums[i]] = 1; // 标记出现的数字
    }
    let result = [];
    for (let i = 1; i <= nums.length; i++) { // 从 1 开始遍历，因为数组下标从 0 开始
        if (temp[i] === 0) { 
            result.push(i); 
        }
    }
    return result;
};

461. 汉明距离

简单

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

1
2
3
4
5
6
7
输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。
1
2
3
4
5
6
7
8
var hammingDistance = function(x, y) {
let s=x^y,ret=0
while(s!=0){
ret +=s&1
s>>=1
}
return ret
};

20. 有效的括号

简单

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

1
2
输入：s = "()"
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var isValid = function(s) {
 s = s.split('');
    let sl = s.length;
    if (sl % 2) return false;
   let map = new Map([[')', '('], [']', '['], ['}', '{']]);
let stack=[]
for(let i of s){
    if(map.get(i)){
        if(stack[stack.length-1]!==map.get(i)) return false
        else stack.pop()
    }else{
        stack.push(i)
    }
}
return !stack.length
};

21. 合并两个有序链表

简单

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var mergeTwoLists = function(l1, l2) {
    if(l1 === null){
        return l2;
    }
    if(l2 === null){
        return l1;
    }
    if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
 
};

543. 二叉树的直径

简单

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

img

1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var diameterOfBinaryTree = function(root) {
    let ans =1
function depth(rootNode){
    if(!rootNode){
        return 0
    }
    let L=depth(rootNode.left)
    let R=depth(rootNode.right)
ans =Math.max(ans,L+R+1)
return  Math.max(L, R) + 1;
}
depth(root)
return ans-1
};

283. 移动零

简单

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

21. 合并两个有序链表

简单

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var mergeTwoLists = function(l1, l2) {
    if(l1 === null){
        return l2;
    }
    if(l2 === null){
        return l1;
    }
    if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
 
};

94. 二叉树的中序遍历

简单

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

img

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var inorderTraversal = function(root) {
const res=[]
const stk=[]
while(root||stk.length){
    while(root){
        stk.push(root)
        root= root.left
    }
    root=stk.pop()
    res.push(root.val)
    root =root.right
}
return res
};

20. 有效的括号

已解答

简单

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

1
2
输入：s = "()"
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var isValid = function(s) {
 s = s.split('');
    let sl = s.length;
    if (sl % 2) return false;
   let map = new Map([[')', '('], [']', '['], ['}', '{']]);
let stack=[]
for(let i of s){
    if(map.get(i)){
        if(stack[stack.length-1]!==map.get(i)) return false
        else stack.pop()
    }else{
        stack.push(i)
    }
}
return !stack.length
};

1. 两数之和

简单

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3
4
5
6
7
8
9
10
var twoSum = function(nums, target) {
map = new Map()
for(let i=0;i<nums.length;i++){
    x=target-nums[i]
    if(map.has(x)){
        return [map.get(x),i]
    }
    map.set(nums[i],i)
}
};

70. 爬楼梯

简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
1
2
3
4
5
6
7
8
9
10
var climbStairs = function(n) {
let p,q=0
let r=1
for(let i=1;i<=n;++i){
    p=q
    q=r
    r=p+q
}
return r
};
算法hot150
http://example.com/2024/08/11/算法hot150/
作者
John Doe
发布于
2024年8月11日
许可协议