算法打卡2

Tony4/8/2022打卡算法

#前言

之前的算法打卡(opens new window)已经快一年了，由于代码行数较多，因此打开缓慢，故决定再新建一个，用于下一周期的算法打卡

#比较含退格的字符串

// 栈方法
function backspaceCompare(s: string, t: string): boolean {
    const buildWord = (w: string) => {
        const arr: string[] = []
        for (const word of w) {
            word === '#' ? arr.pop() : arr.push(word)
        }
        return arr.join(',')
    }
    return buildWord(s) === buildWord(t)
};

1
2
3
4
5
6
7
8
9
10
11

// 快慢指针
function backspaceCompare(s: string, t: string): boolean {
    let sLast = s.length - 1
    let tLast = t.length - 1
    let newS = ''
    let newT = ''
    let i = 0
    while (sLast >= 0) {
        if (s[sLast] === '#') {
            i++
            sLast--
            continue
        }

        if (i === 0) {
            newS += s[sLast]
        }
        i > 0 && i--
        sLast--
    }

    i = 0
    while (tLast >= 0) {
        if (t[tLast] === '#') {
            i++
            tLast--
            continue
        }

        if (i === 0) {
            newT += t[tLast]
        }
        i > 0 && i--
        tLast--
    }
    return newT === newS
};

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

// 快慢指针，从后往前遍历
function backspaceCompare(s: string, t: string): boolean {
    let sLast = s.length - 1
    let tLast = t.length - 1
    while (sLast >= 0 || tLast >= 0) {
        // 退格个数
        let i = 0
        while (sLast >= 0 && i >= 0) {
            if (s[sLast] === '#') {
                i++
            } else {
                if (i === 0) {
                    break
                }
                i--
            }
            sLast--
        }
        i = 0
        while (tLast >= 0 && i >= 0) {
            if (t[tLast] === '#') {
                i++
            } else {
                if (i === 0) {
                    break
                }
                i--
            }
            tLast--
        }

        if (s[sLast--] !== t[tLast--]) {
            return false
        }
    }

    return sLast === tLast
};

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

#同构字符串

地址(opens new window)

// badc
// baba
function isIsomorphic(s: string, t: string): boolean {
    const map = new Map()
    const map1 = new Map()
    const len = s.length
    for(let i = 0; i < len; i++) {
        // 1. 不存在值
        if (map.has(s[i]) && map.get(s[i]) !== t[i]) {
            return false
        }

        if (map1.has(t[i]) && map1.get(t[i]) !== s[i]) {
            return false
        }

        map.set(s[i], t[i])
        map1.set(t[i], s[i])
    }

    return true
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#长度为 K 子数组中的最大和

地址(opens new window)

function maximumSubarraySum(nums: number[], k: number): number {
    const len = nums.length
    if (k === 1) {
        return Math.max(...nums)
    }
    let result = 0
    let index = 0

    // 过程中的总数
    let sum = nums[0]
    let set = {
        [nums[0]]: true
    }

    while (index <= len - k) {
        let i = index

        //  新加的一个变量是否存在相同值
        // 存在的情况
        const lastNum = nums[index + k - 1]

        if (set[lastNum]) {
            index = index + k - 1;
            set = {}
            sum = lastNum
            set[lastNum] = true
            continue
        }

        // 2. 不存在的时候
        if (sum > nums[index]) {
            sum += lastNum - nums[index - 1]
            result = Math.max(result, sum)
            Reflect.deleteProperty(set, nums[index - 1])
            set[lastNum] = true
            index++
            continue
        }

        // 3. 从index到k+index
        i += 1
        for (; i < k + index; i++) {
            if (set[nums[i]]) {
                sum = nums[i]
                set = {}
                index = i
                set[nums[i]] = true
                break
            }

            sum += nums[i]
            set[nums[i]] = true
        }


        if (i < k + index) {
            continue
        }

        result = Math.max(sum, result)
        Reflect.deleteProperty(set, nums[index])
        index++
    }

    return result
};

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#两地调度

地址(opens new window)

// cost[1] - cost[0]进行排序
function twoCitySchedCost(costs: number[][]): number {
    let result = 0
    costs.sort((a, b) => a[1] - a[0] - b[1] + b[0])
    const len = costs.length

    for (let i = 0, last = len / 2; i < last; i++) {
        result += costs[i][1]
        result += costs[len - i - 1][0]
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13

#翻转矩阵后的得分

地址(opens new window)

function matrixScore(grid: number[][]): number {
    // 先左右翻转
    const m = grid[0].length
    const n = grid.length
    let result = 0
    for (let i = 0; i < n; i++) {
        if (grid[i][0] === 0) {
            for (let j = 0; j < m; j++) {
                grid[i][j] = grid[i][j] ? 0 : 1
            }
        }
    }

    // 取值
    for (let i = 0; i < m; i++) {
        let zeroNum = 0
        for (let j = 0; j < n; j++) {
            if (grid[j][i] === 0) {
                zeroNum++
            }
        }

        result += 2 ** (m - i - 1) * Math.max(zeroNum, n - zeroNum)
    }

    return result
};

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

#保持城市天际线

地址(opens new window)

// [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] === 35
function maxIncreaseKeepingSkyline(grid: number[][]): number {
    let result = 0
    const row: number[] = []
    const col: number[] = []
    const m = grid.length
    const n = grid[0].length

    // 获取每一行的最大值
    for (let i = 0; i < m; i++) {
        row[i] = Math.max(...grid[i])
    }

    // 获取每一列的最大值
    for (let i = 0; i < n; i++) {
        col[i] = grid[0][i]
        for (let j = 1; j < m; j++) {
            col[i] = Math.max(col[i], grid[j][i])
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result += Math.min(row[i], col[j]) - grid[i][j]
        }
    }

    return result
};

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

#【贪心算法】森林中的兔子

地址(opens new window)

// [1,0,1,0,0])
// [0,0,1,1,1])
// [2,1,2,2,2,2,2,2,1,1])
function numRabbits(answers: number[]): number {
    const map = new Map()
    let result = 0
    for (let i = 0; i < answers.length; i++) {
        if (answers[i] && map.has(answers[i])) {
            const val = map.get(answers[i])
            if (val === 1) {
                map.delete(answers[i])
                continue
            }
            map.set(answers[i], val - 1)
            continue
        }

        result += answers[i] + 1
        map.set(answers[i], answers[i])
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#【贪心算法】最多能完成排序的块

地址(opens new window)

// 思路就是先找到对应数值，然后遍历从起始到终止时的值，不断更新最后的值，然后找出分块
// 测试数据[1,5,3,0,2,8,7,6,4]、[2,0,1,3]、[1,0,2,3,4]
function maxChunksToSorted(arr: number[]): number {
    let result = 0
    let start = 0
    while(start < arr.length) {
        let index = arr.indexOf(start, start)
        for (let j = start; j <= index; j++) {
            index = Math.max(index, arr[j])
        }

        result++
        start = index + 1
    }
    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function maxChunksToSorted(arr: number[]): number {
    let result = 0
    let max = 0
    for (let j = max; j < arr.length; j++) {
        max = Math.max(max, arr[j])
        if (max === j) {
            result++
        }
    }
    return result
}

1
2
3
4
5
6
7
8
9
10
11

#【贪心算法】最大交换

地址(opens new window)

function maximumSwap(num: number): number {
    const numStr = num.toString().split('')
    for (let i = 0; i < numStr.length - 1; i++) {
        let j = i + 1
        let maxIndex = i

        // 找到最大的值
        for (; j < numStr.length; j++) {
            if (Number(numStr[j]) > Number(numStr[maxIndex])) {
                maxIndex = j
            } else if (Number(numStr[j]) === Number(numStr[maxIndex]) && maxIndex !== i) {
                maxIndex = j
            }
        }

        if (maxIndex !== i) {
            let value = numStr[maxIndex]
            numStr[maxIndex] = numStr[i]
            numStr[i] = value
            break
        }
    }

    return Number(numStr.join(''))
};

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

#【贪心算法】最长数对链

地址(opens new window)

function findLongestChain(pairs: number[][]): number {
    pairs.sort(([prev, prev1], [next, next1]) => prev - next || prev1 - next1)
    let result = 1
    let prev = pairs[0][1]

    for (let i = 1; i < pairs.length; i++) {
        if (pairs[i][0] > prev) {
            prev = pairs[i][1]
            result++
        } else if (pairs[i][1] < prev) {
            // 注意与前面的对比
            prev = pairs[i][1]
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

【简化】

function findLongestChain(pairs: number[][]): number {
    pairs.sort(([, prev1], [, next1]) => prev1 - next1)
    let result = 1
    let prev = pairs[0][1]

    for (let i = 1; i < pairs.length; i++) {
        if (pairs[i][0] > prev) {
            prev = pairs[i][1]
            result++
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#【贪心算法】盛最多水的容器

地址(opens new window)

// 从左到右，从右到左，分别计算
function maxArea(height: number[]): number {
    const len = height.length
    let result = 0
    for (let i = 0; i < len; i++) {
        let last = len - 1
        while (last > i && height[last] < height[i]) {
            last--
        }

        result = Math.max(result, (last - i) * height[i])
    }

    for (let i = len - 1; i >= 0; i--) {
        let last = 0
        while (last < i && height[last] < height[i]) {
            last++
        }

        result = Math.max(result, (i - last) * height[i])
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

【双指针】：从最左和最右开始，较小的值移动

function maxArea(height: number[]): number {
    let result = 0
    let prev = 0
    let next = height.length - 1
    while (prev < next) {
        result = Math.max(result, Math.min(height[prev], height[next]) * (next - prev))
        height[prev] > height[next] ? next-- : prev++
    }
    return result
};

1
2
3
4
5
6
7
8
9
10

#【字符串】最简分数

地址(opens new window)

function simplifiedFractions(n: number): string[] {
    const result: string[] = []
    let prev = 1

    // 判断是否存在最小公倍数
    const isPair = (prev: number, next: number) => {
        const half = Math.min(Math.floor(next / 2), prev)
        let start = 2
        while(start <= half) {
            if (prev % start === 0 && next % start === 0) {
                return true
            }
            start++
        }
        return false
    }


    while(prev <= n) {
        let next = prev + 1
        while(next <= n) {
            if (prev === 1 || !isPair(prev, next)) {
                result.push(`${prev}/${next}`)
            }
            next++
        }
        prev++
    }

    return result
};

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

function simplifiedFractions(n: number): string[] {
    const result: string[] = []
    const set = new Set()
    let prev = 1

    while(prev <= n) {
        let next = prev + 1
        while(next <= n) {
            if (prev === 1 || !set.has(`${prev},${next}`)) {
                result.push(`${prev}/${next}`)
                let i = 2

                // 存起来
                while(next * i <= n) {
                    set.add(`${prev * i},${next * i}`)
                    i++
                }
            }
            next++
        }
        prev++
    }

    return result
};

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

#【字符串】从英文中重建数字

地址(opens new window)

// 找到特征字符
function originalDigits(s: string): string {
    const obj = {
        'zero': 0,
        'xis': 6,
        'seven': 7,
        'wto': 2,
        'geiht': 8,
        'vfie': 5,
        'ufor': 4,
        'rthee': 3,
        'one': 1,
        'inne': 9
    }
    const words = {}
    for (const word of s) {
        words[word] = (words[word] || 0) + 1
    }

    const arr: number[] = Array(10).fill(0);
    Object.keys(obj).forEach((key) => {
        if (words[key[0]]) {
            let num = words[key[0]]
            arr[obj[key]] = num
            for (const k of key) {
                words[k] -= num
            }
        }
    })

    return arr.reduce((prev, next, index) => {
        if (next !== 0) {
            prev += `${index}`.repeat(next)
        }
        return prev
    }, '')
};

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

#【字符串】字母异位词分组

地址(opens new window)

function groupAnagrams(strs: string[]): string[][] {
    const results: string[][] = []
    const map = new Map()

    for (const str of strs) {
        // 切割后排序
        const result = str.split('').sort((a, b) => a.codePointAt(0) - b.codePointAt(0)).join('')

        if (map.has(result)) {
            results[map.get(result)].push(str)
        } else {
            map.set(result, results.length)
            results[results.length] = [str]
        }
    }

    return results
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#【链表】合并零之间的节点

地址(opens new window)

// 思路就是快慢指针
function mergeNodes(head: ListNode | null): ListNode | null {
    if (!head) {
        return head
    }

    let fast = head
    let slow = head
    let val = 0

    while (fast?.next) {
        val += fast.val
        if (fast.next.val !== 0) {
            fast = fast.next
            continue
        }

        slow.next = fast.next
        fast.next.val = val
        val = 0
        slow = slow.next
        fast = slow.next
    }
    return head.next
};

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

#【字符串】检查相同字母间的距离

地址(opens new window)

function checkDistances(s: string, distance: number[]): boolean {
    const map = new Map()
    for (let i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
            const index = s[i].charCodeAt(0) - 'a'.charCodeAt(0)
            if (distance[index] !== i - map.get(s[i]) - 1) {
                return false
            }
        } else {
            map.set(s[i], i)
        }
    }

    return true
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#【双指针】最长优雅子数组

地址(opens new window)

function longestNiceSubarray(nums: number[]): number {
   const len = nums.length
    if (len === 1) {
        return 1
    }

    let prev = 0
    let next = 1
    let result = 0

    while (next < len) {
        // 确定新加入的是否与之前的&为0
        let i = next - 1
        while(i >= prev) {
            if ((nums[i] & nums[next]) !== 0) {
                prev = i + 1
                break
            }
            i--
        }
        result = Math.max(result, next - prev + 1)
        next++
    }
    return result
};

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

#【链表】奇偶链表

地址(opens new window)

// 大致思路
// 比如1->2->3->4->5->6->7
// 第一步2->3互换，然后变成1->3->2->4->5->6->7
// 第二步2->4与5互换，变成1->3->5->2->4->6->7
// 第三步2->4->6与7互换，变成1->3->5->7->2->4->6
function oddEvenList(head: ListNode | null): ListNode | null {
    let node = head
    let index = 1

    while(node) {
        let j = index
        let next = node
        while (j > 0) {
            next = next.next
            j--
        }

        if (!next) {
            break
        }

        let afterNext = next.next
        if (!afterNext) {
            break
        }

        next.next = next.next.next
        afterNext.next = null
        next = node.next
        node.next = afterNext
        node.next.next = next
        node = node.next
        index++
    }

    return 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
27
28
29
30
31
32
33
34
35
36
37

// 一个取奇数链表
// 一个取偶数链表
function oddEvenList(head: ListNode | null): ListNode | null {
    if (!head) {
        return head
    }
    let evenNode = head
    let oddNode = head.next

    let evenList = evenNode
    let oddList = oddNode
    let node = head.next
    let index = 0

    while(node) {
        if (index % 2) {
            oddList.next = node.next
            oddList = oddList.next
        } else {
            evenList.next = node.next
            if (node.next) {
                evenList = evenList.next
            }
        }
        node = node.next
        index++
    }
    evenList.next = oddNode
    return evenNode
};

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

#LRU 缓存

地址(opens new window)

class LRUCache {
    max: number
    cache: Map<number, number>

    constructor(capacity: number) {
        this.max = capacity
        this.cache = new Map()
    }

    get(key: number): number {
        if (this.cache.has(key)) {
            const val = this.cache.get(key)
            this.cache.delete(key)
            this.cache.set(key, val)
        }
        return this.cache.get(key) ?? -1
    }

    put(key: number, value: number): void {
        this.cache.delete(key)
        this.cache.set(key, value)

        if (this.cache.size > this.max) {
            for (const key of this.cache.keys()) {
                this.cache.delete(key)
                break
            }
        }
    }
}

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

#【链表】重排链表

地址(opens new window)

// 思路是反着输出一个链表，然后进行节点交换
function reorderList(head: ListNode | null): void {
    if (!head) {
        return
    }
    let index = 0
    let node = head
    let newRoot: ListNode | null = null
    while(node) {
        newRoot = new ListNode(node.val, newRoot)
        node = node.next
        index++
    }

    let start = 0
    let left = newRoot
    node = head

    while(start < index - 1) {
        let part = node.next
        node.next = left
        left = part
        node = node.next
        start++
    }

    node.next = null
};

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

#【链表】二叉树展开为链表

地址(opens new window)

// 先取出右边的值然后放在左节点的最右子节点上
// 然后左节点指向右节点
function flatten(root: TreeNode | null): void {
    let node = root

    while (node) {
        const right = node.right
        let left = node.left
        if (!left) {
            node = node.right
            continue
        }
        while (left.right) {
            left = left.right
        }

        left.right = right
        node.right = node.left
        node.left = null
        node = node.right
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#【链表】有序链表转换二叉搜索树

地址(opens new window)

// 1. 取出链表内的所有元素
// 2. 取出中间的数分别构成左右的二叉树值
function sortedListToBST(head: ListNode | null): TreeNode | null {
    if (!head) {
        return null
    }

    const arr: number[] = []
    while(head) {
        arr.push(head.val)
        head = head.next
    }

    const cascader = (arr: number[], left: number, right: number) => {
        if (left > right) {
            return null
        }

        const mid = Math.floor((left + right) / 2)
        const node = new TreeNode(arr[mid])
        node.left = cascader(arr, left, mid - 1)
        node.right = cascader(arr, mid + 1, right)
        return node
    }

    return cascader(arr, 0, arr.length - 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

#【链表】反转链表 II

地址(opens new window)

整体思路是获取左边链表、反转中间链表、获取右侧链表，然后组合起来

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    if (left === right) {
        return head
    }
    head = new ListNode(0, head)
    let prev = head
    let index = 1
    while (true) {
        if (index <= left - 1) {
            prev = prev.next
            index++
            continue
        }
        break
    }

    let node = prev.next
    let mid = new ListNode(node.val, null)
    let list = mid
    node = node.next
    index++

    while(true) {
        if (index <= right) {
            list = new ListNode(node.val, list)
            node = node.next
            index++
            continue
        }
        break
    }

    mid.next = node
    prev.next = list

    return head.next
};

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

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    if (left === right) {
        return head
    }

    head = new ListNode(0, head)
    let prev = head
    let node = head
    let mid = null
    let midStart = null
    let index = 1
    while(index <= right + 1) {
        if (index < left) {
            prev = prev.next
        }

        if (index > left) {
            mid = new ListNode(node.val, mid)
            if (!midStart) {
                midStart = mid
            }
        }

        node = node.next
        index++
    }

    midStart.next = node
    prev.next = mid
    return head.next
};

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

#【链表】分隔链表

地址(opens new window)

function partition(head: ListNode | null, x: number): ListNode | null {
    if (!head) {
        return head
    }

    // 防止第一个就大于x
    head = new ListNode(x - 1, head)
    let fast = head
    let slow = head

    while (fast) {
        if (fast.next && fast.next.val < x) {
            if (slow === fast) {
                slow = slow.next
                fast = fast.next
                continue
            }

            let val = fast.next.val
            fast.next = fast.next.next
            slow.next = new ListNode(val, slow.next)
            slow = slow.next
            continue
        }
        fast = fast.next
    }

    return head.next
};

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

function partition(head: ListNode | null, x: number): ListNode | null {
    if (!head) {
        return head
    }

    // 防止第一个就大于x，同时维护两个链表值
    const small = new ListNode(x-1)
    const large = new ListNode(x+1)
    let smallNode = small
    let largeNode = large
    let node = head
    while(node) {
        if (node.val < x) {
            smallNode.next = new ListNode(node.val)
            smallNode = smallNode.next
        } else {
            largeNode.next = new ListNode(node.val)
            largeNode = largeNode.next
        }
        node = node.next
    }
    smallNode.next = large.next
    return small.next
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#【链表】旋转链表

地址(opens new window)

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (k === 0 || !head) {
        return head
    }

    let slow = head
    let fast = head

    // 快指针循环到k位置
    for (let i = 0; i < k; i++) {
        if (fast) {
            fast = fast.next

            if (!fast) {
                fast = head
            }
        }
    }

    // 快慢指针一起走
    while(fast.next) {
        fast = fast.next
        slow = slow.next
    }

    // 获取需要分割的链表位置
    // 例如 1 2 3 4 5, k = 2
    // slow现在是3 4 5，因此拿到slow.next，同时slow.next置为Null
    let mid = slow.next
    if (!mid) {
        return head
    }

    slow.next = null
    fast = mid
    while(fast.next) {
        fast = fast.next
    }
    fast.next = head
    return mid
};

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

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (k === 0 || !head) {
        return head
    }

    // 获取链表的长度
    let m = 0
    let node = head
    while(node) {
        node = node.next
        m++
    }

    if (k % m === 0) {
        return head
    }

    k = m - k % m
    node = head
    while (k > 1) {
        node = node.next
        k--
    }

    let mid = node.next
    if (!mid) {
        return head
    }

    node.next = null
    node = mid
    while(node.next) {
        node = node.next
    }
    node.next = head

    return mid
};

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

#【双指针】寻找重复数

地址(opens new window)

// 双指针，类似于环形链表
function findDuplicate(nums: number[]): number {
    let fast = 0
    let slow = 0

    while(true) {
        fast = nums[nums[fast]]
        slow = nums[slow]
        if (fast === slow) {
            slow = 0
            while (fast !== slow) {
                fast = nums[fast]
                slow = nums[slow]
            }
            return fast
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#【双指针】环形链表

地址(opens new window)

function hasCycle(head: ListNode | null): boolean {
    let fast = head
    let slow = head
    while (fast?.next) {
        fast = fast.next.next
        slow = slow.next
        if (fast === slow) {
            return true
        }
    }
    return false
};

1
2
3
4
5
6
7
8
9
10
11
12

#【数组】螺旋矩阵

地址(opens new window)

function spiralOrder(matrix: number[][]): number[] {
    const m = matrix[0].length
    const n = matrix.length
    const result: number[] = []

    let i = 0
    let j = m
    while (true) {
        if (i >= j) {
            break
        }

        // 从左到右
        for (let left = i; left < j; left++) {
            result.push(matrix[i][left])
        }

        if (i + 1 >= n - i) {
            break
        }

        // 从上到下
        for (let top = i + 1; top < n - i; top++) {
            result.push(matrix[top][j-1])
        }

        if (j - 2 < i) {
            break
        }

        // 从右到左
        for (let right = j - 2; right >= i; right--) {
            result.push(matrix[n-i-1][right])
        }

        if (n - i - 2 <= i) {
            break
        }

        // 从下到上
        for (let bottom = n - i - 2; bottom > i; bottom--) {
            result.push(matrix[bottom][i])
        }

        i++
        j--
    }

    return result
};

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
48
49
50

#【动态规划】最大子序列交替和

地址(opens new window)

// 1. dp[i][0]接下来是奇数 1. 要么直接选自身nums[i] 2. 要么选前面的 3. 要么是前面是偶数的加上当前的
// 2. dp[i][1]接下来是偶数 1. 要么选前面的 2. 要么前面是奇数减去当前的
function maxAlternatingSum(nums: number[]): number {
    const dp: number[][] = []
    const len = nums.length
    dp[0] = [nums[0], 0]

    for (let i = 1; i < len; i++) {
        dp[i] = []
        dp[i][0] = Math.max(nums[i], dp[i-1][0], dp[i-1][1] + nums[i])
        dp[i][1] = Math.max(dp[i-1][0] - nums[i], dp[i-1][1])
    }

    return Math.max(...dp[len-1])
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 简化
function maxAlternatingSum(nums: number[]): number {
    let [prev, next] = [nums[0], 0]
    const len = nums.length

    for (let i = 1; i < len; i++) {
        [prev, next] = [Math.max(prev, next + nums[i]), Math.max(prev - nums[i], next)]
    }

    return Math.max(prev, next)
};

1
2
3
4
5
6
7
8
9
10
11

// 贪心算法
function maxAlternatingSum(nums: number[]): number {
    const len = nums.length
    let result = 0
    let pre = 0

    for (let i = 0; i < len; i++) {
        if (nums[i] > pre) {
            result += nums[i] - pre
            pre = nums[i]
        } else {
            pre = nums[i]
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#【动态规划】所有子字符串中的元音

地址(opens new window)

// 例如 abaabbbbbba
// dp[i] = dp[i-1] + 前一个元音排列的个数即(dp[lastVowel] - dp[lastVowel-1]) + (1 + i)(如果当前是元音)
function countVowels(word: string): number {
    const len = word.length
    const dp: number[] = Array(len).fill(0)
    dp[-1] = 0
    const vowelObj = { a: true, e: true, i: true, o: true, u: true }
    let lastVowel = 0 // 最后一个元音的位置
    if (vowelObj[word[0]]) {
        dp[0] = 1
    } else {
        dp[0] = 0
    }

    for (let i = 1; i < word.length; i++) {
        if (vowelObj[word[i]]) {
            dp[i] = dp[i-1] + i + dp[lastVowel] - dp[lastVowel-1] + 1
            lastVowel = i
        } else {
            dp[i] = dp[i-1] + dp[lastVowel] - dp[lastVowel-1]
        }
    }

    return dp.pop()
};

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

function countVowels(word: string): number {
    const len = word.length
    const vowelObj = { a: true, e: true, i: true, o: true, u: true }
    let result = 0

    for (let i = 0; i < len; i++) {
        if (vowelObj[word[i]]) {
            // i + 1左边的组合个数
            // len - i右边的组合个数
            result += (i + 1) * (len - i)
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#最长定差子序列

地址(opens new window)

function longestSubsequence(arr: number[], difference: number): number {
    const obj = {}
    let result = 1
    obj[arr[0]] = 1

    for (let i = 1; i < arr.length; i++) {
        if (obj[arr[i] - difference]) {
            result = Math.max(result, obj[arr[i] - difference] + 1)
            obj[arr[i]] = obj[arr[i] - difference] + 1
        } else {
            obj[arr[i]] = 1
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#【动态规划】最长湍流子数组

地址(opens new window)

function maxTurbulenceSize(arr: number[]): number {
    const len = arr.length
    if (!len) {
        return 0
    }

    if (len === 1) {
        return 1
    }

    let result = 1
    let num = 2

    for (let i = 1; i < len; i++) {
        // 避免重复值
        if (arr[i] === arr[i-1]) {
            continue
        }

        // 判断是否为湍流
        if (arr[i] > arr[i-1] && arr[i] > arr[i+1]) {
            num++
            continue
        } else if (arr[i] < arr[i-1] && arr[i] < arr[i+1]) {
            num++
            continue
        }

        result = Math.max(result, num)
        num = 2
    }

    return result
};

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

#【动态规划】股票平滑下跌阶段的数目

地址(opens new window)

function getDescentPeriods(prices: number[]): number {
    let result = 1
    let val = prices[0]
    let num = 1

    for (let i = 1; i < prices.length; i++) {
        result++

        if (prices[i] - val === -1) {
            result += num
            num++
            val -= 1
        } else {
            val = prices[i]
            num = 1
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#【动态规划】使字符串平衡的最少删除次数

地址(opens new window)

// 与题目将字符串翻转到单调递增类似

// dp[i][0] 前面删掉b的情形
// dp[i][1] 前面删掉a的情形
function minimumDeletions(s: string): number {
    let dp: number[][] = []
    dp[0] = [0, 0]

    for (let i = 1; i <= s.length; i++) {
        dp[i] = []
        if (s[i-1] === 'a') {
            dp[i][0] = dp[i-1][0]
            dp[i][1] = dp[i-1][1] + 1
        } else {
            // 这里注意两种场景，一种是前面都是b，一种是前面都是a
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1])
            dp[i][0] = dp[i-1][0] + 1
        }
    }

    return Math.min(...dp[s.length])
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 简化
function minimumDeletions(s: string): number {
    let [prev, next] = [0, 0]

    for (let i = 1; i <= s.length; i++) {
        if (s[i-1] === 'a') {
            next += 1
        } else {
            next = Math.min(prev, next)
            prev += 1
        }
    }

    return Math.min(prev, next)
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#【动态规划】任意子数组和的绝对值的最大值

地址(opens new window)

// 暴力破解，未通过
function maxAbsoluteSum(nums: number[]): number {
    let result = Math.abs(nums[0])

    for (let i = 0; i < nums.length; i++) {
        let val = nums[i]
        for (let j = i - 1; j >= 0; j--) {
            val += nums[j]
            result = Math.max(result, Math.abs(val))
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function maxAbsoluteSum(nums: number[]): number {
    // dp[i][0]代表负数值，dp[i][1]代表正数值
    const dp: number[][] = [[0, 0]]
    if (nums[0] > 0) {
        dp[0][1] = nums[0]
    } else {
        dp[0][0] = nums[0]
    }
    let result = Math.abs(nums[0])

    for (let i = 1; i < nums.length; i++) {
        dp[i] = [0, 0]
        if (nums[i] > 0) {
            dp[i][1] = dp[i-1][1] + nums[i]
            dp[i][0] = Math.min(0, nums[i] + dp[i-1][0])
        } else {
            dp[i][0] = dp[i-1][0] + nums[i]
            dp[i][1] = Math.max(0, nums[i] + dp[i-1][1])
        }

        result = Math.max(result, Math.abs(dp[i][0]), Math.abs(dp[i][1]))
    }

    return result
};

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

// 优化一下
function maxAbsoluteSum(nums: number[]): number {
    let [prev, next] = [0, 0]
    if (nums[0] > 0) {
        next = nums[0]
    } else {
        prev = nums[0]
    }
    let result = Math.abs(nums[0])

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > 0) {
            [prev, next] = [Math.min(0, nums[i] + prev), next + nums[i]]
        } else {
            [prev, next] = [prev + nums[i], Math.max(0, nums[i] + next)]
        }

        result = Math.max(result, -prev, next)
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 想象成一个股市图，最大值减去最小值
function maxAbsoluteSum(nums: number[]): number {
   const dp: number[] = [0]
    for (let i = 1; i <= nums.length; i++) {
        dp[i] = dp[i-1] + nums[i-1]
    }
    return Math.max(...dp) - Math.min(...dp)
};

1
2
3
4
5
6
7
8

#【动态规划】生成平衡数组的方案数

地址(opens new window)

// 第一版
function waysToMakeFair(nums: number[]): number {
    // prev[0]表示偶数和、prev[1]表示奇数和
    const prev: number[][] = []
    prev[-1] = [0, 0]
    const next: number[][] = []
    next[-1] = [0, 0]
    const len = nums.length
    let result = 0

    for (let i = 0, j = len - 1; i < len; i++, j--) {
        if (i % 2) {
            prev[i] = [prev[i-1][0], prev[i-1][1] + nums[i]]
            next[i] = [next[i-1][0], next[i-1][1] + nums[j]]
        } else {
            prev[i] = [prev[i-1][0] + nums[i], prev[i-1][1]]
            next[i] = [next[i-1][0] + nums[j], next[i-1][1]]
        }
    }

    // 根据奇数还是偶数数列判断加的和
    let [prevIdx, nextIdx] = len % 2 ? [1, 0] : [0, 1]
    for (let i = 0, j = len - 1; i < len; i++, j--) {
        if (prev[i-1][0] + next[j-1][prevIdx] === prev[i-1][1] + next[j-1][nextIdx]) {
            result++
        }
    }

    return result
};

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

// 优化一下，思路就是删除当前元素，那么之后的偶数之和就变为奇数之和、后面的奇数之和变为偶数之和
function waysToMakeFair(nums: number[]): number {
    const len = nums.length
    let odd = 0
    let even = 0
    let result = 0
    let prevOdd = 0 // 奇数之和
    let prevEven = 0 // 遍历之前的偶数之和

    for (let i = 0; i < len; i++) {
        if (i % 2) {
            odd += nums[i]
        } else {
            even += nums[i]
        }
    }

    for (let i = 0; i < len; i++) {
        if (i % 2) {
            // 前面的偶数+后面的偶数（后面奇数都变为偶数）=前面的奇数
            if (prevEven + odd - nums[i] - prevOdd === prevOdd + even - prevEven) {
                result++
            }
            prevOdd += nums[i]
        } else {
            if (prevEven + odd - prevOdd === prevOdd + even - prevEven - nums[i]) {
                result++
            }
            prevEven += nums[i]
        }
    }

    return result
};

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

// 简化
function waysToMakeFair(nums: number[]): number {
    const len = nums.length
    let val = 0
    let result = 0
    let prev = 0

    for (let i = 0; i < len; i++) {
        if (i % 2) {
            val -= nums[i]
        } else {
            val += nums[i]
        }
    }

    for (let i = 0; i < len; i++) {
        if (i % 2) {
            if (2 * prev - val === nums[i]) {
                result++
            }
            prev -= nums[i]
        } else {
            if (2 * prev - val === - nums[i]) {
                result++
            }
            prev += nums[i]
        }
    }

    return result
};

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

// 再简化
function waysToMakeFair(nums: number[]): number {
    const len = nums.length
    let val = 0
    let result = 0
    let prev = 0

    for (let i = 0; i < len; i++) {
        val += nums[i] * (i % 2 ? -1 : 1)
    }

    for (let i = 0; i < len; i++) {
        if (2 * prev - val === nums[i] * (i % 2 ? 1 : -1)) {
            result++
        }
        prev += nums[i] * (i % 2 ? -1 : 1)
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#最佳观光组合

地址(opens new window)

// 暴力破解
function maxScoreSightseeingPair(values: number[]): number {
    let result = 0
    for (let i = 0; i < values.length - 1; i++) {
        for (let j = i + 1; j < values.length; j++) {
            result = Math.max(values[i] + values[j] + i - j, result)
        }
    }
    return result
};

1
2
3
4
5
6
7
8
9
10

// 优化
function maxScoreSightseeingPair(values: number[]): number {
    let result = 0

    // 取观光景点i
    let maxVal = values[0]

    for (let i = 1; i < values.length; i++) {
        result = Math.max(result, maxVal + values[i] - i)
        if (values[i] + i > maxVal) {
            maxVal = values[i] + i
        }
    }
    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#受限条件下可到达节点的数目

地址(opens new window)

function reachableNodes(n: number, edges: number[][], restricted: number[]): number {
    const restrictedObj = restricted.reduce((prev, next) => {
        prev[next] = true
        return prev
    }, {})
    const arivedObj = {}
    const used = {}
    for (let i = 0; i < n - 1; i++) {
        if (!arivedObj[edges[i][0]]) {
            arivedObj[edges[i][0]] = []
        }
        arivedObj[edges[i][0]].push(edges[i][1])

        if (!arivedObj[edges[i][1]]) {
            arivedObj[edges[i][1]] = []
        }
        arivedObj[edges[i][1]].push(edges[i][0])
    }
    let m = 1
    const cascader = (num: number) => {
        used[num] = true

        for (let i = 0; i < arivedObj[num].length; i++) {
            if (used[arivedObj[num][i]]) {
                continue
            }
            if (!restrictedObj[arivedObj[num][i]]) {
                m++
                cascader(arivedObj[num][i])
            }
        }
    }
    cascader(0)
    return m
};

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

#算术三元组的数目

地址(opens new window)

function arithmeticTriplets(nums: number[], diff: number): number {
    const set = new Set([...nums])
    let result = 0
    for (let i = 0; i < nums.length; i++) {
        if (set.has(nums[i] + diff) && set.has(nums[i] + 2 * diff)) {
            result++
        }
    }
    return result
};

1
2
3
4
5
6
7
8
9
10

#【动态规划】检查数组是否存在有效划分

地址(opens new window)

function validPartition(nums: number[]): boolean {
    const len = nums.length
    if (len === 2) {
        return nums[0] === nums[1]
    }

    const dp: boolean[] = [false]
    dp[1] = nums[1] === nums[0]
    dp[2] = dp[1] && nums[2] === nums[1] || (nums[2] - nums[1] === 1 && nums[1] - nums[0] === 1)

    for (let i = 3; i < len; i++) {
        // 加这个的原因的判断是两个相等还是三个相等
        if (nums[i] === nums[i-1] && nums[i-2] === nums[i-1]) {
            dp[i] = dp[i-2] || dp[i-3]
        } else if (nums[i] === nums[i-1]) {
            dp[i] = dp[i-2]
        } else if (nums[i] > nums[i-1]) {
            dp[i] = dp[i-3] !== false && nums[i] - nums[i-1] === 1 && nums[i-1] - nums[i-2] === 1
        } else {
            dp[i] = false
        }
    }

    return dp[len-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

#【动态规划】将字符串翻转到单调递增

地址(opens new window)

// dp[i][0]代表之前都为0
// dp[i][1]代表符合字符串单调递增
function minFlipsMonoIncr(s: string): number {
    const dp: [number, number][] = []
    dp[0] = [0, 0]
    if (s[0] === '1') {
        dp[0][0] = 1
    } else {
        dp[0][1] = 1
    }

    for (let i = 1; i < s.length; i++) {
        dp[i] = [0, 0]
        if (s[i] === '0') {
            dp[i][0] = dp[i-1][0]
            dp[i][1] = dp[i-1][1] + 1
        } else {
            // 要么前面都是0后面都是1，要么前面都是1
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1])
            dp[i][0] = dp[i-1][0] + 1
        }
    }

    return Math.min(...dp[s.length-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

function minFlipsMonoIncr(s: string): number {
    let [prev, next] = [0, 0]

    for (let i = 1; i <= s.length; i++) {
        if (s[i-1] === '0') {
            next += 1
        } else {
            // 要么前面都是0后面都是1
            next = Math.min(prev, next)
            prev += 1
        }
    }

    return Math.min(prev, next)
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#字符串的好分割数目

地址(opens new window)

function numSplits(s: string): number {
    const prevObj = {}
    const nextObj = {}
    const prevArr: number[] = []
    const nextArr: number[] = []
    let prevNum = 0
    let nextNum = 0
    let result = 0

    for (let i = 0, j = s.length - 1; i < s.length; i++, j--) {
        if (!prevObj[s[i]]) {
            prevNum++
            prevObj[s[i]] = true
        }
        prevArr[i] = prevNum

        if (!nextObj[s[j]]) {
            nextNum++
            nextObj[s[j]] = true
        }

        nextArr[j] = nextNum
    }

    for (let i = 0; i < s.length - 1; i++) {
        if (prevArr[i] === nextArr[i + 1]) {
            result++
        }
    }

    return result
};

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

#计数质数

地址(opens new window)

function countPrimes(n: number): number {
    if (n < 2) {
        return 0
    }

    let result = 0
    const isPrime = (n: number) => {
        for (let i = 2; i * i <= n; i++) {
            if (n % i === 0) {
                return true
            }
        }
        return false
    }

    for (let i = 2; i < n; i++) {
        if (!isPrime(i)) {
            result++
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function countPrimes(n: number): number {
    if (n < 2) {
        return 0
    }

    let result = 0
    const arr: boolean[] = Array(n).fill(false)
    for (let i = 2; i < n; i++) {
        if (!arr[i]) {
            result++

            // 质数的倍数肯定不为质数
            for (let j = i * i; j < n; j += i) {
                arr[j] = true
            }
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#丑数

地址(opens new window)

function isUgly(n: number): boolean {
    if (n < 1) {
        return false
    }

    while(n > 1) {
        if (n % 2 === 0) {
            n /= 2
            continue
        }

        if (n % 3 === 0) {
            n /= 3
            continue
        }

        if (n % 5 === 0) {
            n /= 5
            continue
        }
        return false
    }

    return 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

#【动态规划】超级丑数

地址(opens new window)

function nthSuperUglyNumber(n: number, primes: number[]): number {
    const dp: number[] = []
    const len = primes.length
    dp[1] = 1
    const arr: number[] = Array(len).fill(1)

    for (let i = 2; i <= n; i++) {
        let min = Infinity
        for (let j = 0; j < len; j++) {
            if (min > dp[arr[j]] * primes[j]) {
                min = dp[arr[j]] * primes[j]
            }
        }

        for (let j = 0; j < len; j++) {
            if (min === dp[arr[j]] * primes[j]) {
                arr[j] += 1
            }
        }
        dp[i] = min
    }

    return dp[n]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#【动态规划】丑数 II

地址(opens new window)

// 使用过的需要加1
// dp[i] = Math.min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
function nthUglyNumber(n: number): number {
    if (n === 1) {
        return 1
    }

    const dp: number[] = []
    dp[1] = 1
    let p2 = 1
    let p3 = 1
    let p5 = 1

    for (let i = 2; i <= n; i++) {
        let num2 = dp[p2] * 2
        let num3 = dp[p3] * 3
        let num5 = dp[p5] * 5
        dp[i] = Math.min(num2, num3, num5)
        if (dp[i] === num2) {
            p2++
        }

        if(dp[i] === num3) {
            p3++
        }

        if (dp[i] === num5) {
            p5++
        }
    }

    return dp[n]
};

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

#旋转数字

地址(opens new window)

// 正则
function rotatedDigits(n: number): number {
    let result = 0
    const rorateDifReg = /[2569]+/
    const rorateErrReg = /[347]+/

    for (let i = 1; i <= n; i++) {
        if (rorateErrReg.test(i.toString())) {
            continue
        }

        if (rorateDifReg.test(i.toString())) {
            result++
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#【动态规划】删除并获得点数

地址(opens new window)

// 1. 排序
// 2. 获取每个值的个数
// 3. 从前往后叠加，遇到相邻的不叠加
function deleteAndEarn(nums: number[]): number {
    nums.sort((prev, next) => prev - next)
    const map = new Map()

    for (let i = 0; i < nums.length; i++) {
        if (!map.has(nums[i])) {
            map.set(nums[i], 0)
        }
        map.set(nums[i], map.get(nums[i]) + 1)
    }

    const dp: number[][] = [[Infinity, 0]]
    let dpLen = 1

    for (const [num, time] of map.entries()) {
        const [prevNum, sum] = dp[dp.length - 1]
        if (prevNum === Infinity) {
            dp.push([num, time * num])
        } else if (prevNum + 1 === num) {
            dp.push([num, time * num + Math.max(dp[dpLen - 2][1], dp[dpLen - 3]?.[1] ?? -Infinity)])
        } else {
            dp.push([num, time * num + Math.max(sum, dp[dp.length - 2][1])])
        }
        dpLen++
    }
    const len = dp.length

    return Math.max(dp[len - 1][1], dp[len - 2][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

function deleteAndEarn(nums: number[]): number {
    nums.sort((prev, next) => prev - next)
    const map = new Map()

    for (let i = 0; i < nums.length; i++) {
        if (!map.has(nums[i])) {
            map.set(nums[i], 0)
        }
        map.set(nums[i], map.get(nums[i]) + nums[i])
    }

    // 简化
    let [prev, next] = [[0, 0], [0, -Infinity]]

    for (const [num, val] of map.entries()) {
        if (next[1] === -Infinity) {
            next = [num, val]
        } else if (next[0] + 1 === num) {
            [prev, next] = [[next[0], Math.max(prev[1], next[1])], [num, val + prev[1]]]
        } else {
            let max = Math.max(prev[1], next[1]);
            [prev, next] = [[next[0], max], [num, max + val]]
        }
    }

    return Math.max(prev[1], next[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

类似打家劫舍

function deleteAndEarn(nums: number[]): number {
    const maxNum = Math.max(...nums)
    const arr: number[] = Array(maxNum + 1).fill(0)
    let max = 0
    for (const num of nums) {
        arr[num] += num
    }

    let [prev, next] = [arr[0], arr[1]]
    for (let i = 2; i < arr.length; i++) {
        [prev, next] = [next, Math.max(arr[i] + prev, next)]
    }

    return next
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#【动态规划】杨辉三角 II

地址(opens new window)

function getRow(rowIndex: number): number[] {
    let dp: number[] = []

    for (let i = 0; i <= rowIndex; i++) {
        const newDp: number[] = []

        for (let j = 0; j <= i; j++) {
            if (j === 0 || j === i) {
                newDp[j] = 1
            } else {
                newDp[j] = dp[j-1] + dp[j]
            }
        }

        dp = [...newDp]
    }

    return dp
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#【动态规划】杨辉三角

地址(opens new window)

function generate(numRows: number): number[][] {
    const result: number[][] = []

    for (let i = 0; i < numRows; i++) {
        result[i] = []
        for (let j = 0; j <= i; j++) {
            if (j === 0 || j === i) {
                result[i][j] = 1
            } else {
                result[i][j] = result[i-1][j-1] + result[i-1][j]
            }
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#【动态规划】第 N 个泰波那契数

地址(opens new window)

function tribonacci(n: number): number {
    if (n === 0) {
        return 0
    }

    if (n < 3) {
        return 1
    }

    let [dp1, dp2, dp3] = [0, 1, 1]

    for (let i = 3; i <= n; i++) {
        [dp1, dp2, dp3] = [dp2, dp3, dp1 + dp2 + dp3]
    }

    return dp3
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#【动态规划】获取生成数组中的最大值

地址(opens new window)

function getMaximumGenerated(n: number): number {
    if (n === 0) {
        return 0
    }

    if (n === 1) {
        return 1
    }

    const dp: number[] = [0, 1]
    let max = 1

    for (let i = 2; i <= n; i++) {
        if (i % 2) {
            dp[i] = dp[Math.ceil(i / 2)] + dp[Math.floor(i / 2)]
        } else {
            dp[i] = dp[i / 2]
        }

        max = Math.max(max, dp[i])
    }

    return max
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#【动态规划】下降路径最小和

地址(opens new window)

// 思路是从上一个路径得出下一个路径的最小值
function minFallingPathSum(matrix: number[][]): number {
    const len = matrix.length
    let dp: number[] = matrix[0]

    for (let i = 1; i < len; i++) {
        const newArr: number[] = []
        for (let j = 0; j < len; j++) {
            newArr[j] = matrix[i][j] + Math.min(dp[j-1] ?? Infinity, dp[j], dp[j+1] ?? Infinity)
        }
        dp = [...newArr]
    }

    return Math.min(...dp)
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#将整数按权重排序

地址(opens new window)

function getKth(lo: number, hi: number, k: number): number {
    const map = new Map()
    const dp: [number, number][] = []

    // 获取权重
    for (let i = lo; i <= hi; i++) {
        let j = i
        let k = 0
        let mid: number[] = [j]

        while (j !== 1) {
            if (map.has(j)) {
                k += map.get(j)
                break
            }

            j = j % 2 ? (3 * j + 1) : (j / 2)
            k++
            mid.push(j)
        }

        for (let m = 0; m < mid.length; m++) {
            map.set(mid[m], k - m)
        }

        dp[i-lo] = [i, k]
    }

    return dp.sort(([,prev], [,next]) => prev - next)[k - 1][0]
};

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

#等差数列划分

地址(opens new window)

function numberOfArithmeticSlices(nums: number[]): number {
    const len = nums.length
    if (len < 3) {
        return 0
    }

    const dp: number[] = Array(len).fill(-Infinity)
    let result = 0
    dp[1] = nums[1] - nums[0]

    for (let i = 2; i < len; i++) {
        dp[i] = nums[i] - nums[i-1]

        let j = i

        // 往回算出差值
        while (j > 0 && dp[j] === dp[j-1]) {
            result++
            j--
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

优化：

// 如果有n个连续的等差数列，那么3个以上的连续等差数列有n * (n + 1) / 2
function numberOfArithmeticSlices(nums: number[]): number {
    const len = nums.length
    if (len < 3) {
        return 0
    }

    let dp = nums[1] - nums[0]
    let result = 0
    let t = 0 // 等差数列的个数

    for (let i = 2; i < len; i++) {
        if (nums[i] - nums[i-1] === dp) {
            t++
        } else {
            dp = nums[i] - nums[i-1]
            t = 0
        }

        result += t
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#【回溯】公平分发饼干

地址(opens new window)

function distributeCookies(cookies: number[], k: number): number {
    let result = Infinity
    const content: number[] = Array(k).fill(0)

    const cascader = (cur: number[], start = 0) => {
        if (start >= cookies.length) {
            result = Math.min(result, Math.max(...cur))
            return
        }
        for (let i = 0; i < k; i++) {
            cur[i] += cookies[start]
            cascader(cur, start + 1)
            cur[i] -= cookies[start]
        }
    }

    cascader(content)
    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 剪枝利用空间换时间
function distributeCookies(cookies: number[], k: number): number {
    let result = Infinity
    const content: number[] = Array(k).fill(0)
    const map = new Map()
    const maxNum = cookies.length - k + 1

    const cascader = (cur: number[], start = 0) => {
        if (start >= cookies.length) {
            result = Math.min(result, Math.max(...cur))
            return
        }
        for (let i = 0; i < k; i++) {
            if (map.get(i) >= maxNum) {
                continue
            }

            cur[i] += cookies[start]
            map.set(i, (map.get(i) || 0) + 1)
            cascader(cur, start + 1)
            cur[i] -= cookies[start]
            map.set(i, map.get(i) - 1)
        }
    }

    cascader(content)
    return result
};

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

#【动态规划】统计作战单位数

地址(opens new window)

function numTeams(rating: number[]): number {
    const len = rating.length
    // dpMax[i][1] 表示连续2个构成统战 dp[i][2] 连续3个构成统战
    const dpMax: number[][] = Array.from({ length: len }, () => [1, 0, 0])
    const dpMin: number[][] = Array.from({ length: len }, () => [1, 0, 0])
    let result = 0

    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            if (rating[j] < rating[i]) {
                dpMax[i][1] += dpMax[j][0]
                dpMax[i][2] += dpMax[j][1]
            } else if (rating[j] > rating[i]) {
                dpMin[i][1] += dpMin[j][0]
                dpMin[i][2] += dpMin[j][1]
            }
        }
    }

    for (let i = 0; i < len; i++) {
        result += dpMax[i][2] + dpMin[i][2]
    }

    return result
};

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

#统计全为 1 的正方形子矩阵

地址(opens new window)

【动态规划】

function countSquares(matrix: number[][]): number {
    const n = matrix.length
    const m = matrix[0].length

    // 拿到第一组
    let dp: number[] = matrix[0]
    let result = matrix[0].reduce((prev, next) => prev + next, 0)

    for (let i = 1; i < n; i++) {
        const arr: number[] = []
        for (let j = 0; j < m; j++) {
            if (j === 0) {
                arr.push(matrix[i][j])
                result += matrix[i][j]
                continue
            }

            if (matrix[i][j] && matrix[i][j-1] && matrix[i-1][j] && matrix[i-1][j-1]) {
                // 取到正方形边长的最小值
                const val = Math.min(dp[j], arr[j-1], dp[j-1]) + 1
                result += val
                arr.push(val)
            } else {
                result += matrix[i][j]
                arr.push(matrix[i][j])
            }
        }
        dp = [...arr]
    }

    return result
};

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

优化：

function countSquares(matrix: number[][]): number {
    const n = matrix.length
    const m = matrix[0].length

    let dp: number[] = matrix[0]
    let result = matrix[0].reduce((prev, next) => prev + next, 0)

    for (let i = 1; i < n; i++) {
        const arr: number[] = []
        for (let j = 0; j < m; j++) {
            // 只要当前值为1，就可以拓展为多个正方形
            if (j > 0 && matrix[i][j]) {
                const val = Math.min(dp[j], arr[j-1], dp[j-1]) + 1
                result += val
                arr[j] = val
            } else {
                result += matrix[i][j]
                arr[j] = matrix[i][j]
            }
        }
        dp = [...arr]
    }

    return result
};

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

#优美的排列

地址(opens new window)

function countArrangement(n: number): number {
    let result = 0
    const numArr = Array.from({ length: n }, (v, i) => i + 1)
    const set = new Set()

    // 回溯
    const cascader = (numArr: number[], size: number = 1) => {
        if (size === n + 1) {
            result++
            return
        }

        for (const num of numArr) {
            // 满足条件
            if (set.has(num)) {
                continue
            }

            if (size % num && num % size) {
                continue
            }
            set.add(num)
            cascader(numArr, size + 1)
            set.delete(num)
        }
    }

    cascader(numArr)
    return result
};

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

#字母在字符串中的百分比

地址(opens new window)

function percentageLetter(s: string, letter: string): number {
    let n = 0
    for (const word of s) {
        word === letter && n++
    }

    return Math.floor(n / s.length * 100)
};

1
2
3
4
5
6
7
8

#装满石头的背包的最大数量

地址(opens new window)

function maximumBags(capacity: number[], rocks: number[], additionalRocks: number): number {
    const add: number[] = []
    let fullNum = 0
    for (let i = 0; i < capacity.length; i++) {
        if (capacity[i] === rocks[i]) {
            fullNum++
        } else {
            add.push(capacity[i] - rocks[i])
        }
    }

    // 排序
    add.sort((a, b) => a - b)

    for (let i = 0; i < add.length; i++) {
        if (add[i] > additionalRocks) {
            break
        }
        fullNum++
        additionalRocks -= add[i]
    }

    return fullNum
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#在长度 2N 的数组中找出重复 N 次的元素

地址(opens new window)

function repeatedNTimes(nums: number[]): number {
    const len = nums.length
    const half = len / 2
    const map = new Map()

    for (const n of nums) {
        if (map.get(n) === half - 1) {
            return n
        }

        map.set(n, (map.get(n) || 0) + 1)
    }
    return 0
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#不含特殊楼层的最大连续楼层数

地址(opens new window)

function maxConsecutive(bottom: number, top: number, special: number[]): number {
    special.sort((a, b) => a - b)
    let maxLevel = special[0] - bottom

    for (let i = 1; i < special.length; i++) {
        maxLevel = Math.max(special[i] - special[i-1] - 1, maxLevel)
    }

    maxLevel = Math.max(maxLevel, top - special[special.length - 1])
    return maxLevel
};

1
2
3
4
5
6
7
8
9
10
11

#移除字母异位词后的结果数组

地址(opens new window)

function removeAnagrams(words: string[]): string[] {
    if (words.length <= 1) {
        return words
    }

    let i = 1
    while (i < words.length) {
        if (words[i-1].split('').sort().join('') === words[i].split('').sort().join('')) {
            words.splice(i, 1)
            continue
        }
        i++
    }
    return words
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#删列造序

地址(opens new window)

function minDeletionSize(strs: string[]): number {
    let num = 0

    for (let i = 0; i < strs[0].length; i++) {
        for (let j = 1; j < strs.length; j++) {
            if (strs[j][i].charCodeAt(0) < strs[j-1][i].charCodeAt(0)) {
                num++
                break
            }
        }
    }
    return num
};

1
2
3
4
5
6
7
8
9
10
11
12
13

#序列化和反序列化二叉搜索树

地址(opens new window)

// 前序遍历
function serialize(root: TreeNode | null): string {
    if (!root) {
        return ''
    }

    let str = ''
    const cascader = (root: TreeNode | null) => {
        if (!root) {
            return str
        }

        str += root.val + ','
        cascader(root.left)
        cascader(root.right)
    }
    cascader(root)
    return str
};

/*
 * Decodes your encoded data to tree.
 */
// 已知前序和中序遍历生成二叉树
function deserialize(data: string): TreeNode | null {
    const numArr = data.split(',').slice(0, -1).map(item => +item)

    const cascader = (numArr: number[], start: number = 0, end: number = numArr.length) => {
        if (start >= end) {
            return null
        }

        const root = new TreeNode(numArr[start])
        const index = numArr.findIndex((num, idx) => {
            if (idx >= start) {
                return num > numArr[start]
            }
        })

        root.left = cascader(numArr, start + 1, index === -1 ? end : index)
        if (index > -1) {
            root.right = cascader(numArr, index, end)
        }
        return root
    }

    return cascader(numArr)
};

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
48

#增减字符串匹配

地址(opens new window)

// 贪心算法
// 1. 当前值为I，代表当前值小于下一个值
// 2. 当前值为D，代表当前值大于下一个值
function diStringMatch(s: string): number[] {
    const len = s.length
    let max = len
    let min = 0
    const result: number[] = []

    for (let i = 0; i < len; i++) {
        if (s[i] === 'I') {
            result.push(min++)
        } else {
            result.push(max--)
        }
    }
    result.push(min)
    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#数组中重复的数据

地址(opens new window)

function findDuplicates(nums: number[]): number[] {
    const map = {}
    const result: number[] = []
    for (let i = 0; i < nums.length; i++) {
        if (map[nums[i]]) {
            result.push(nums[i])
        }
        map[nums[i]] = 1
    }
    return result
};

1
2
3
4
5
6
7
8
9
10
11

#前序遍历构造二叉搜索树

地址(opens new window)

// 已知前序遍历和中序遍历，构建二叉树
function bstFromPreorder(preorder: number[]): TreeNode | null {
    const cascader = (preorder, start = 0, end = preorder.length) => {
        if (start >= end) {
            return null
        }

        const node = new TreeNode(preorder[start])
        const index = preorder.findIndex((item, index) => {
            if (index > start) {
                return item > preorder[start]
            }
        })

        // 小于根节点的值为左子节点
        node.left = cascader(preorder, start + 1, index === -1 ? end : index)

        // 超过根节点的值为右子节点
        if (index > -1) {
            node.right = cascader(preorder, index, end)
        }
        return node
    }

    return cascader(preorder)
};

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

#链表最大孪生和

地址(opens new window)

// 直接取出数据，然后求和
function pairSum(head: ListNode | null): number {
    const result: number[] = []
    while(head) {
        result.push(head.val)
        head = head.next
    }
    let max = -Infinity
    let start = 0
    let end = result.length - 1
    while (start < end) {
        max = Math.max(max, result[start] + result[end])
        start++
        end--
    }
    return max
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#最小差值 I

地址(opens new window)

// 得到最大和最小值，然后判断
function smallestRangeI(nums: number[], k: number): number {
    let max = nums[0]
    let min = nums[0]
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > max) {
            max = nums[i]
        } else if (nums[i] < min) {
            min = nums[i]
        }
    }

    if (min + 2 * k >= max) {
        return 0
    }

    return max - min - 2 * k
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#按奇偶排序数组

地址(opens new window)

// 遍历
function sortArrayByParity(nums: number[]): number[] {
    const result: number[] = []
    for (let i = 0; i < nums.length; i++) {
        (nums[i] % 2) ? result.push(nums[i]) : result.unshift(nums[i])
    }
    return result
};

1
2
3
4
5
6
7
8

// 双指针
function sortArrayByParity(nums: number[]): number[] {
    let prev = 0
    let next = nums.length - 1
    while (prev < next) {
        if (nums[prev] % 2 === 0) {
            prev++
            continue
        }

        if (nums[next] % 2) {
            next--
            continue
        }

        let mid = nums[prev]
        nums[prev] = nums[next]
        nums[next] = mid
        prev++
        next--
    }
    return nums
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#括号生成

地址(opens new window)

function generateParenthesis(n: number): string[] {
    const arrLen = n * 2
    const isValid = (content: string, n: number) => {
        let stack: string[] = []
        let start = 0
        for (let i = 0; i < content.length; i++) {
            if (content[i] === '(') {
                stack.push(')')
                if (++start > n) {
                    return false
                }
            } else if (stack.length) {
                stack.pop()
            } else {
                return false
            }
        }
        return true
    }
    let result: string[] = ['(']
    let i = 1

    while (i < arrLen) {
        const len = result.length
        for (let i = 0; i < len; i++) {
            const str = result.shift()
            if (isValid(str + '(', n)) {
                result.push(str + '(')
            }

            if (isValid(str +')', n)) {
                result.push(str + ')')
            }
        }
        i++
    }

    return result
};

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

// 溯源
function generateParenthesis(n: number): string[] {
    const result: string[] = []
    const end = n * 2

    const cancader = (word: string = '', leftNum = 0) => {
        if (word.length === end) {
            // 无缺失
            !leftNum && result.push(word)
            return
        }

        for (const i of '()') {
            if (leftNum > n) {
                continue
            }

            if (i === ')' && leftNum === 0) {
                break
            }
            cancader(word + i, i === '(' ? leftNum + 1 : leftNum - 1)
        }
    }
    cancader()
    return result
};

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

#二进制间距

地址(opens new window)

function binaryGap(n: number): number {
    const twoN = n.toString(2)
    let result = 0
    let start = -1

    for (let i = 0; i < twoN.length; i++) {
        if (twoN[i] === '1') {
            if (start !== -1) {
                result = Math.max(i - start, result)
            }
            start = i
        } else if (twoN[i] === '0' && twoN[i-1] === '1') {
            start = i - 1
        }
    }

    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#分隔数组以得到最大和

地址(opens new window)

// dp[i] = Math.max(dp[i-j] + max * j, dp[i])
function maxSumAfterPartitioning(arr: number[], k: number): number {
    let len = arr.length
    const dp: number[] = Array(len + 1).fill(0)

    for (let i = 1; i <= len; i++) {
        let max = arr[i-1]
        for (let j = 1; j <= k && j <= i; j++) {
            max = Math.max(max, arr[i-j])
            dp[i] = Math.max(dp[i-j] + max * j, dp[i])
        }
    }

    return dp[len]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#山羊拉丁文

地址(opens new window)

function toGoatLatin(sentence: string): string {
    // 1. 存元音字符
    const set = new Set(['a', 'e', 'i', 'o', 'u'])
    // 2. 切割成数组然后再根据规则获取字符串
    return sentence.split(' ').reduce((str, item, index) => {
        if (set.has(item[0].toLowerCase())) {
            str += ' ' + item + 'ma' + 'a'.repeat(index+1)
        } else {
            str += ' ' + item.slice(1) + item[0] + 'ma' + 'a'.repeat(index+1)
        }
        return str
    }, '').slice(1)
};

1
2
3
4
5
6
7
8
9
10
11
12
13

#两个字符串的删除操作

地址(opens new window)

// 动态规划
function minDistance(word1: string, word2: string): number {
    const len1 = word1.length
    const len2 = word2.length
    const dp: number[][] = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(0))

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
            }
        }
    }

    return len1 + len2 - 2 * dp[len1][len2]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#最常见的单词

地址(opens new window)

// 1. 利用正则切割成数组
// 2. 使用set拿到禁用单词哈希表
// 3. 数组循环拿到最多出现次数的单词
function mostCommonWord(paragraph: string, banned: string[]): string {
    const strArr = paragraph.split(/\W+/i)
    const set = banned.reduce((set, word) => {
        set.add(word)
        return set
    }, new Set)
    let max = 0
    let result = ''
    strArr.reduce((map, word) => {
        let low = word.toLocaleLowerCase()
        if (!set.has(low)) {
            let times = (map.get(low) || 0) + 1
            map.set(low, times)

            if (times > max) {
                max = times
                result = low
            }
        }
        return map
    }, new Map)
    return result
};

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

#迷你语法分析器

地址(opens new window)

// 案例"[123,[456,[789,-222],555],-852]"
function deserialize(s: string): NestedInteger {
    let stack: NestedInteger[] = []
    let num = ''
    for(let i = 0; i < s.length; i++) {
        if (s[i] === ',') {
            if (s[i-1] === ']') {
                continue
            }

            stack[stack.length - 1].add(new NestedInteger(Number(num)))
            num = ''
            continue
        }

        if (s[i] === ']') {
            if (num) {
                stack[stack.length - 1].add(new NestedInteger(Number(num)))
                num = ''
            }

            stack.length > 1 && stack[stack.length - 2].add(stack.pop())
            continue
        }

        if (s[i] === '[') {
            stack.push(new NestedInteger())
            continue
        }
        num += s[i]
    }

    if (num) {
        return new NestedInteger(Number(num))
    }
    return stack[0]
};

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

#最富有客户的资产总量

地址(opens new window)

function maximumWealth(accounts: number[][]): number {
    let max = 0
    for (const account of accounts) {
        let sum = account.reduce((s, val) => s + val, 0)
        max = Math.max(sum, max)
    }
    return max
};

1
2
3
4
5
6
7
8

#单词拆分 II

地址(opens new window)

function wordBreak(s: string, wordDict: string[]): string[] {
    const dp: boolean[] = Array(s.length + 1).fill(false)
    dp[0] = true

    for (let i = 1; i <= s.length; i++) {
        for (let word of wordDict) {
            const wLen = word.length
            if (i >= wLen && s.startsWith(word, i - wLen) && dp[i-wLen]) {
                dp[i] = true
            }
        }
    }

    if (!dp[s.length]) {
        return []
    }

    const set = wordDict.reduce((set, w) => {
        set.add(w)
        return set
    }, new Set)

    // 回溯
    const result: string[] = []
    let sArr: string[] = []

    const cascader = (s: string, start: number = 1) => {
        if (start > s.length) {
            result.push(sArr.join(' '))
            return
        }
        let s1 = ''
        for (let i = start; i <= s.length; i++) {
            s1 += s[i-1]
            if (dp[i] && set.has(s1)) {
                sArr.push(s1)
                cascader(s, i + 1)
                sArr.pop()
            }
        }
    }

    cascader(s)
    return result
};

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

#零钱兑换

地址(opens new window)

// 动归
// dp[j]表示amount时最少的硬币个数
function coinChange(coins: number[], amount: number): number {
  const dp: number[] = Array(amount + 1).fill(Infinity)
    dp[0] = 0

    for (const coin of coins) {
        for (let j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j-coin] + 1)
        }
    }

    return dp[amount] > Number.MAX_SAFE_INTEGER ? -1 : dp[amount]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Tony's Blob

算法打卡2

算法打卡2

#前言

#比较含退格的字符串

#同构字符串

#长度为 K 子数组中的最大和

#两地调度

#翻转矩阵后的得分

#保持城市天际线

#【贪心算法】森林中的兔子

#【贪心算法】最多能完成排序的块

#【贪心算法】最大交换

#【贪心算法】最长数对链

#【贪心算法】盛最多水的容器

#【字符串】最简分数

#【字符串】 从英文中重建数字

#【字符串】字母异位词分组

#【链表】合并零之间的节点

#【字符串】检查相同字母间的距离

#【双指针】最长优雅子数组

#【链表】奇偶链表

#LRU 缓存

#【链表】重排链表

#【链表】二叉树展开为链表

#【链表】有序链表转换二叉搜索树

#【链表】反转链表 II

#【链表】分隔链表

#【链表】旋转链表

#【双指针】寻找重复数

#【双指针】环形链表

#【数组】螺旋矩阵

#【动态规划】最大子序列交替和

#【动态规划】所有子字符串中的元音

#最长定差子序列

#【动态规划】最长湍流子数组

#【动态规划】股票平滑下跌阶段的数目

#【动态规划】使字符串平衡的最少删除次数

#【动态规划】任意子数组和的绝对值的最大值

#【动态规划】生成平衡数组的方案数

#最佳观光组合

#受限条件下可到达节点的数目

#算术三元组的数目

#【动态规划】检查数组是否存在有效划分

#【动态规划】将字符串翻转到单调递增

#字符串的好分割数目

#计数质数

#丑数

#【动态规划】超级丑数

#【动态规划】丑数 II

#旋转数字

#【动态规划】删除并获得点数

#【动态规划】杨辉三角 II

#【动态规划】杨辉三角

#【动态规划】第 N 个泰波那契数

#【动态规划】获取生成数组中的最大值

#【动态规划】下降路径最小和

#将整数按权重排序

#等差数列划分

#【回溯】公平分发饼干

#【动态规划】统计作战单位数

#统计全为 1 的正方形子矩阵

#优美的排列

#字母在字符串中的百分比

#装满石头的背包的最大数量

#在长度 2N 的数组中找出重复 N 次的元素

#不含特殊楼层的最大连续楼层数

#移除字母异位词后的结果数组

#删列造序

#序列化和反序列化二叉搜索树

#增减字符串匹配

#数组中重复的数据

#前序遍历构造二叉搜索树

#链表最大孪生和

#最小差值 I

#按奇偶排序数组

#括号生成

#二进制间距

#分隔数组以得到最大和

#山羊拉丁文

#【字符串】从英文中重建数字