2025年｜跟着瓶子刷算法

,

js两个数组的交集

1
2
3
4
5
6

function intersection(num1: number[], num2: number[]): number[] {
    return [...new Set(num1.filter(item => num2.includes(item)))]
}


两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function twoSum(nums: number[], target: number): number[] {
    let helperMap = new Map();
    let resArr = [];
    let resIndex = undefined;
    for(let i = 0; i< nums.length; i++){
        if(helperMap.has(target - nums[i])){
            resIndex = helperMap.get(target - nums[i])
            if(resIndex !== undefined){
                resArr = [nums[i], resIndex]
                break;
            }
            helpMap.set(nums[i], i)
        } 
    }
    return resArr;
}

三数之和

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
46
47

function threeSum(nums: number[]): number[][] {
    const len = nums.length;
    const res = [];
    if(len < 3) {
        return res
    }

    nums.sort((a, b) => a - b) 

    for(let i = 0; i < len -2; i++){
        if(nums[i] > 0){
            break;
        }

        if(i && nums[i] === nums[i-1]){
            continue;
        }

        let left = i + 1;
        let right = len -1

        while(left < right){
            const sum = nums[i] + nums[left] + nums[right]
            if(sum === 0){
                res.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){
                right --
            } else {
                left++
            }
        }
    }

    return res
}


链表

1
2
3
4
5
理解改指针。插入X，A → B
X.next = A.next
A.next = X
A → X → B
head 是 入口，丢了 head，整个链表就找不到了

合并两个有序链表

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

function mergeTwoLists(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(l2.next, l1)
        return l2
    }
}
/**
1️⃣ 有空的，直接接
2️⃣ 比头结点，谁小选谁
3️⃣ 选中的 next = 递归剩下的
4️⃣ return 选中的
**/