【LeetCode】2022 8月 每日一题

【LeetCode】2022 8月 每日一题

8.1 生成每种字符都是奇数个的字符串

题目

1374. 生成每种字符都是奇数个的字符串

给你一个整数 n，请你返回一个含 n 个字符的字符串，其中每种字符在该字符串中都恰好出现 奇数次 。

返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串，则返回其中任意一个即可。

思路

纯纯的简单题，偶数字符串就是奇数 + 1的形式，奇数字符串，直接返回这个奇数*a

代码

function generateTheString(n: number): string {
    let res  = new Array<string>(n-1).fill('a').join('')
    return n % 2 == 0 ? res + 'b' : res + 'a'
}
1
2
3
4

8.2 设计循环队列

题目

622. 设计循环队列

思路

循环队列就完事了，数据结构课还用c写过

代码

class MyCircularQueue {
    que: number[]
    s: number   // 队首
    e: number   // 队尾
    l: number   // 队列最大长度
    cnt: number // 目前队列长度
    constructor(k: number) {
        this.que = new Array(k)
        this.l = k
        this.s = 0
        this.e = 0
        this.cnt = 0
    }

    enQueue(value: number): boolean {
        if (this.cnt == this.l) return false
        this.que[this.e] = value
        this.e = (this.e + 1) % this.l
        this.cnt++
        return true
    }

    deQueue(): boolean {
        if (this.cnt == 0) return false
        this.s = (this.s + 1) % this.l
        this.cnt--
        return true
    }

    Front(): number {
        if (this.cnt == 0) return -1
        return this.que[this.s]
    }

    Rear(): number {
        if (this.cnt == 0) return -1
        return this.que[(this.e - 1 + this.l) % this.l]
    }

    isEmpty(): boolean {
        return this.cnt == 0
    }

    isFull(): boolean {
        return this.cnt == this.l
    }
}
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

8.3 有序队列

题目

899. 有序队列

给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。

返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。

思路

k = 1，只能换一个字母，暴力遍历比较一次

k > 1，直接返回字典序最小的（因为k只要>=2就能实现冒泡排序）

代码

function orderlyQueue(s: string, k: number): string {
    const fun = (s: string) => {
        let n = s
        for (let i = 1; i < s.length; i++) {
            if (s[i] > n[0]) continue
            let nn = s.substr(i) + s.substr(0,i)
            if (n > nn) {
                n = nn
            }
        }
        return n
    }

    return k == 1 ? fun(s) : s.split("").sort().join("")
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

8.4 非递增顺序的最小子序列

题目

1403. 非递增顺序的最小子序列

思路

先遍历一次数组，算出所有元素的sum

逆序排序数组

从前向后遍历新数组，加起来的tmpSum > sum - tmpSum就行

代码

function minSubsequence(nums: number[]): number[] {
    let sum = 0
    nums.forEach(item => {sum += item})
    nums.sort((a,b) => b-a)
    let res = []
    let tmp = 0
    for (let it of nums) {
        tmp += it
        res.push(it)
        if (tmp > sum - tmp) {
            return res
        }
    }

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

8.5 在二叉树中增加一行

题目

623. 在二叉树中增加一行

思路

层序遍历，遍历到depth-1层就给他加上新的一层

代码

function addOneRow(root: TreeNode | null, val: number, depth: number): TreeNode | null {
    if (root == null) {
        return null
    }
    if (depth == 1) {
        return new TreeNode(val,root)
    }
    let res = root
    let curRow = 0
    let que = []
    que.push(root)
    while (que.length != 0) {
        curRow++
        let len = que.length    // 先把目前队列长度给定死，不然下面的for循环会改变
        for (let i = 0; i < len; i++) {
            let node = que.shift()
            if (node.left != null) {
                que.push(node.left)
            }
            if (node.right != null) {
                que.push(node.right)
            }
            if (curRow == depth - 1) {
                node.left = new TreeNode(val,node.left)
                node.right = new TreeNode(val, null, node.right)
            }
        }
    }
    return res
}
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

8.6 数组中的字符串匹配

题目

1408. 数组中的字符串匹配

思路

直接按长度降序，遍历前面的加入tmp字符串中，查看当前遍历的str是否在tmp字符串中

代码

function stringMatching(words: string[]): string[] {
    words.sort((a, b) => b.length - a.length)   // 按长度排序，长的在前面
    console.log(words)
    let curConcat = ''
    let res = []
    for (let word of words) {
        if (curConcat.indexOf(word) !== -1) {
            res.push(word)
        }
        curConcat += word + " "
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13

8.7 函数的独占时间

题目

636. 函数的独占时间

思路

直接栈模拟即可，单线程，会挤占，梦回操作系统的作业调度

代码

function exclusiveTime(n: number, logs: string[]): number[] {
    let stack = []
    let res = new Array<number>(n)
    res.fill(0)
    logs.forEach(log => {
        let taskId = parseInt(log.split(":")[0])
        let cmd = log.split(":")[1]
        let time = parseInt(log.split(":")[2])
        if (cmd[0] == 's') {
            // 开始执行，查看stack中是否未空
            if (stack.length != 0) {
                let preId = stack[stack.length-1].taskId
                let preTime = stack[stack.length-1].time
                res[preId] += time - preTime
            }
            stack.push({
                taskId: taskId,
                time: time
            })
        } else {
            // 结束执行，判断stack是否未空
            let data = stack.pop()
            res[taskId] += time - data.time + 1
            if (stack.length != 0) {
                // 更新栈顶的任务时间
                stack[stack.length - 1].time = time + 1
            }
        }
    })
    return res
}
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

8.8 特殊的二进制序列

题目

761. 特殊的二进制序列

特殊的二进制序列是具有以下两个性质的二进制序列：

• 0 的数量与 1 的数量相等。
• 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。
1
2
3
4
5

说明:

1. S 的长度不超过 50。
2. S 保证为一个满足上述定义的特殊 的二进制序列。

思路

是我可以做的困难题。

首先如何理解特殊序列二进制数？把1当作(，把0当作)，0和1成对出现，同时1永远在0前面，同时1的数量和0的数量一致。如果比作括号，那么就是，左括号一定在右括号的前面，同时括号是成对出现的。

如果对于一个字符串进行无限拆分，直到拆成了题目所需要的特殊的二进制字符串的形式，那么必然是1 ?? 0的形式，这里的??也是遵守上述括号原则的

那么直接递归求解，首先给一个空的list，递归字符串，每次找到当前字符串可以拆分的形式，加入到list中

最终的list里面存储的就是所有的特殊的二进制序列，对这个list进行排序，1开头的一定是在前面的（字典序最大），直接降序输出就行了

代码

function makeLargestSpecial(s: string): string {
    let list: string[] = []   // 存放有效的特殊二进制序列
    let len: number = s.length
    let cur: number = 0
    let socre: number = 0
    for (let i = 0; i < len; i++) {
        socre += s[i] == "1" ? 1 : -1
        if (socre == 0) {
            // 等于0表示是有效的一对二进制序列
            list.push("1" + makeLargestSpecial(s.substring(cur + 1, i)) + "0")
            cur = i + 1
        }
    }
    list.sort((a: string,b: string) => b.localeCompare(a))  // 1在前面的肯定比0在前面的大，其实是比较 b+a 和 a+b
    return list.join("")
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.9 逐步求和得到正数的最小值

题目

1413. 逐步求和得到正数的最小值

给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。

你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。

请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。

示例 1：

输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
                累加求和
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2
1
2
3
4
5
6
7
8
9
10

示例 2：

输入：nums = [1,2]
输出：1
解释：最小的 startValue 需要是正数。
1
2
3

示例 3：

输入：nums = [1,-2,-3]
输出：5
1
2

提示：

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

思路

前缀和即可

代码

我直接是暴力求解，其实可以在算前缀和的时候就计算，懒得动脑子

function minStartValue(nums: number[]): number {
    let len = nums.length
    const sum = []
    let s = 0
    for (let num of nums) {
        s += num
        sum.push(s)
    }
    let min = 101
    sum.forEach(it => {
        if (it < min) {
            min = it
        }
    })
    return min < 0 ? -(min-1) : 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.10 求解方程

题目

640. 求解方程

求解一个给定的方程，将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。

如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 “Infinite solutions” 。

如果方程中只有一个解，要保证返回值 ‘x’ 是一个整数。

示例 1：

输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"
1
2

示例 2:

输入: equation = "x=x"
输出: "Infinite solutions"
1
2

示例 3:

输入: equation = "2x=x"
输出: "x=0"
1
2

提示:

• 3 <= equation.length <= 1000
• equation 只有一个 '='.
• equation 方程由整数组成，其绝对值在 [0, 100] 范围内，不含前导零和变量 'x' 。

思路

模拟即可，需要注意有很特殊的用例0x=0之类的

代码

const NO = "No solution"
const INF = "Infinite solutions"

function solveEquation(equation: string): string {
    let [left, right] = equation.split("=")
    let leftX = 0, leftInt = 0, rightX = 0, rightInt = 0
    let curSign = left[0] == '-' ? -1 : 1
    let curInt = 0
    for (let i = 0; i < left.length; i++) {
        if (left[i] == '+') {
            leftInt += curInt * curSign
            curInt = 0
            curSign = 1
        }
        else if (left[i] == '-') {
            leftInt += curInt * curSign
            curInt = 0
            curSign = -1
        }
        else if (left[i] == 'x') {
            if (i > 0 && left[i - 1] == '0') continue
            leftX += (curSign * curInt) == 0 ? curSign : (curSign * curInt)
            curInt = 0
        }
        else if (left[i] >= '0' && left[i] <= '9') {
            curInt = curInt * 10 + parseInt(left[i])
        }
        if (i == left.length - 1 && curInt != 0) {
            leftInt += curInt * curSign
        }
    }
    curSign = right[0] == '-' ? -1 : 1
    curInt = 0
    for (let i = 0; i < right.length; i++) {
        if (right[i] == '+') {
            rightInt += curInt * curSign
            curInt = 0
            curSign = 1
        }
        else if (right[i] == '-') {
            rightInt += curInt * curSign
            curInt = 0
            curSign = -1
        }
        else if (right[i] == 'x') {
            if (i > 0 && right[i - 1] == '0') continue
            rightX += (curSign * curInt) == 0 ? curSign : (curSign * curInt)
            curInt = 0
        }
        else if (right[i] >= '0' && right[i] <= '9') {
            curInt = curInt * 10 + parseInt(right[i])
        } 
        if (i == right.length - 1 && curInt != 0) {
            rightInt += curInt * curSign
        }
    }
    // console.log(leftX,leftInt,rightX,rightInt)
    if (leftX == rightX && leftInt == rightInt) {
        return INF
    }
    if (leftX == rightX && leftInt != rightInt) {
        return NO
    }
    if ((rightInt - leftInt) % (leftX - rightX) != 0) {
        return "x=0"
    }
    return "x="+((rightInt - leftInt) / (leftX - rightX)).toString()
}
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
67
68

只要提交的够早，双百不是问题

8.11 重新格式化字符串

题目

1417. 重新格式化字符串

思路

直接模拟

代码

function reformat(s: string): string {
    let nums: string[] = []
    let strs: string[] = []
    let len: number = s.length
    for (let i = 0; i < len; i++) {
        if (s[i] >= '0' && s[i] <= '9') nums.push(s[i])
        else strs.push(s[i])
    }
    const numsLen: number = nums.length
    const strsLen: number = strs.length
    let res = ''
    if (numsLen === strsLen || numsLen - 1 === strsLen || strsLen - 1 === numsLen) {
        let flag: number = 0    // 一样长
        if (numsLen > strsLen) flag = 1     // 数字长
        else if (numsLen < strsLen) flag = 2    // 字母长
        for (let i = 0; i < Math.min(numsLen, strsLen); i++) {
            if (flag === 2) res += strs[i] + nums[i]
            else res += nums[i] + strs[i]
        }
        if (flag === 2) {
            res += strs[strsLen - 1]
        } else if (flag === 1) {
            res += nums[numsLen - 1]
        }
    }
    return res
}
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

8.12 用户分组

题目

1282. 用户分组

思路

创建一个map，存放大小为x的组中存在的人的下标，默认情况是有x人

为了保证x组中超出了x人，需要遍历这个map进行进一步筛选

遍历map，看看x组中的y人需要分多少组

循环组数x/y次，进行筛选

代码

function groupThePeople(groupSizes: number[]): number[][] {
    const map: Map<number, number[]> = new Map()
    groupSizes.forEach((item,idx) => {
        !map.has(item) && map.set(item,[])
        map.get(item).push(idx)
    })
    const res: number[][] = []
    // 因为可以保证至少有一个解。所以可以进行遍历筛选
    map.forEach((val, key) => {
        const groupLen: number = key
        const list: number[] = val
        const cnt: number = list.length / groupLen    // n人要分多少组
        let idx: number = 0
        for (let i = 0; i < cnt; i++) {
            let tmp: number[] = []
            for (let j = 0; j < groupLen; j++) {
                tmp.push(list[idx++])
            }
            res.push(tmp)
        }
    })
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

8.13 最多能完成排序的块 II

题目

768. 最多能完成排序的块 II

思路

排序后遍历，查看前缀和是否相同。

代码

function maxChunksToSorted(arr: number[]): number {
    let res = []
    Object.assign(res, arr)
    res.sort((a, b) => a - b)
    let sum1 = 0, sum2 = 0
    let ans = 0
    for (let i = 0; i < arr.length; i++) {
        sum1 += res[i]
        sum2 += arr[i]
        if (sum1 == sum2) ans++
    }
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13

8.14 分割字符串的最大得分

题目

1422. 分割字符串的最大得分

思路

前缀和求解即可

代码

function maxScore(str: string): number {
    let one: number = 0
    for (let s of str) {
        if (s == '1') one++
    }
    let res: number = 0
    let oneCnt: number = 0
    let zeroCnt: number = 0
    let len: number = str.length
    if (one === len || one === 0) {
        return Math.max(one, len) - 1
    }
    for (let i = 0 ; i < len - 1; i++) {
        const s = str[i]
        if (s === '1') oneCnt++
        else zeroCnt++
        res = Math.max(res, zeroCnt + one - oneCnt)
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8.15 设计循环双端队列

题目

641. 设计循环双端队列

思路

模拟就行了，循环双端队列，数组实现

代码

class MyCircularDeque {
    que: number[]
    size: number
    curCnt: number
    font: number
    tail: number
    constructor(k: number) {
        this.que = new Array(k)
        this.size = k
        this.curCnt = 0
        this.font = 0
        this.tail = 0
    }

    insertFront(value: number): boolean {
       if (this.curCnt == this.size) return false
        this.font = (this.font - 1 + this.size) % this.size
        this.que[this.font] = value
        this.curCnt++
        return true
    }

    insertLast(value: number): boolean {
        if (this.curCnt == this.size) return false
        this.que[this.tail] = value
        this.tail = (this.tail + 1) % this.size
        this.curCnt++
        return true
    }

    deleteFront(): boolean {
        if (this.isEmpty()) return false
        this.font = (this.font + 1) % this.size
        this.curCnt--
        return true
    }

    deleteLast(): boolean {
        if (this.isEmpty()) return false
        this.tail = (this.tail - 1 + this.size) % this.size
        this.curCnt--
        return true
    }

    getFront(): number {
        if (this.isEmpty()) return -1
        return this.que[this.font]
    }

    getRear(): number {
        if (this.isEmpty()) return -1
        return this.que[(this.tail - 1 + this.size) % this.size]    // tail - 1才是队尾
    }

    isEmpty(): boolean {
        return this.curCnt == 0
    }

    isFull(): boolean {
        return this.curCnt == this.size
    }
}
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

8.16 设计有序流

题目

1656. 设计有序流

思路

模拟就行

代码

class OrderedStream {
    ptr: number
    map: string[]
    constructor(n: number) {
        this.ptr = 1
        this.map = new Array(n+2).fill("")
    }

    insert(idKey: number, value: string): string[] {
        this.map[idKey] = value
        if (this.map[this.ptr] == "") {
            return []
        }
        let res = []
        while (this.map[this.ptr] != "") {
            res.push(this.map[this.ptr])
            this.ptr++
        }
        return res
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

8.17 层数最深叶子节点的和

题目

1302. 层数最深叶子节点的和

思路

层序遍历即可

代码

function deepestLeavesSum(root: TreeNode | null): number {
    let que: TreeNode[] = []
    let map: Map<TreeNode, number> = new Map()
    let row: number = 0
    que.push(root)
    while (que.length) {
        row++
        let len = que.length
        for (let i = 0; i < len; i++) {
            let node: TreeNode = que.shift()
            if (node.left != null) que.push(node.left)
            if (node.right != null) que.push(node.right)
            if (node.left == null && node.right == null) map.set(node, row)
        }
    }
    let max: number = -Infinity
    map.forEach((value, key) => {
        if (value > max) {
            max = value
        }
    })
    let res: number = 0
    map.forEach((value, key) => {
        if (value == max) {
            res += key.val
        }
    })
    return res
}
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

看了5s后直接写的，当时没考虑清除，多搞了个map来存储，纯纯的失了智

不需要这个map，直接在每层计数就行了

8.18 最大相等频率

题目

1224. 最大相等频率

思路

用map存储，记录

代码

function maxEqualFreq(nums: number[]): number {
    const freq = new Map()
    const count = new Map()
    let res = 0, maxFreq = 0
    for (let i = 0; i < nums.length; i++) {
        if (!count.has(nums[i])) {
            count.set(nums[i], 0);
        }
        if (count.get(nums[i]) > 0) {
            freq.set(count.get(nums[i]), freq.get(count.get(nums[i])) - 1)
        }
        count.set(nums[i], count.get(nums[i]) + 1)
        maxFreq = Math.max(maxFreq, count.get(nums[i]))
        if (!freq.has(count.get(nums[i]))) {
            freq.set(count.get(nums[i]), 0)
        }
        freq.set(count.get(nums[i]), freq.get(count.get(nums[i])) + 1)
        const ok = maxFreq === 1 ||
                freq.get(maxFreq) * maxFreq + freq.get(maxFreq - 1) * (maxFreq - 1) === i + 1 && freq.get(maxFreq) === 1 ||
                freq.get(maxFreq) * maxFreq + 1 === i + 1 && freq.get(1) === 1
        if (ok) {
            res = Math.max(res, i + 1)
        }
    }
    return res
}
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

8.19 在既定时间做作业的学生人数

题目

1450. 在既定时间做作业的学生人数

思路

遍历判断是否在区间内

代码

function busyStudent(startTime: number[], endTime: number[], queryTime: number): number {
    let res: number = 0
    for (let i = 0 ; i < startTime.length; i++) 
        if (startTime[i] <= queryTime && endTime[i] >= queryTime)
            res++
    return res
}
1
2
3
4
5
6
7

8.20 最大二叉树

题目

654. 最大二叉树

思路

直接0点准时解题，递归一把嗦，当然有条件的可以直接从原数组改值，我这里用了slice截取，空间复杂度高了

代码

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    let maxIdx: number = 0
    let maxVal: number = -Infinity
    nums.forEach((val: number, idx: number) => {if (val > maxVal) {
        maxVal = val
        maxIdx = idx
    }})
    let leftArr: number[] = nums.slice(0, maxIdx)
    let rightArr: number[] = nums.slice(maxIdx+1)
    let res: TreeNode = new TreeNode(maxVal)
    if (leftArr.length) res.left = constructMaximumBinaryTree(leftArr)
    else res.left = null
    if (rightArr.length) res.right = constructMaximumBinaryTree(rightArr)
    else res.right = null
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.21 检查单词是否为句中其他单词的前缀

题目

1455. 检查单词是否为句中其他单词的前缀

思路

模拟遍历即可

代码

function isPrefixOfWord(sentence: string, searchWord: string): number {
    const words: string[] = sentence.split(" ")
    const res: Function = (): number => {
        for (let i = 0; i < words.length; i++) {
            if (words[i].startsWith(searchWord))
                return i + 1
        }
        return -1
    }
    return res()
}
1
2
3
4
5
6
7
8
9
10
11

8.22 输出二叉树

题目

655. 输出二叉树

思路

使用层序遍历，先求出树的高度（这里的高度是我们理解的高度-1，题目认为二叉树的高度从0开始）

求出高度后，计算m、n

BFS将res数组进行赋值操作

代码

function printTree(root: TreeNode | null): string[][] {
    const getHeight = (root: TreeNode) => {
        let height: number = 0
        let que: TreeNode[] = [root]
        while (que.length) {
            height++
            let len: number = que.length
            for (let i = 0; i < len; i++) {
                let node: TreeNode = que.shift()
                if (node.left) que.push(node.left)
                if (node.right) que.push(node.right)
            }
        }
        return height
    }
    const height: number = getHeight(root)-1
    const m: number = height + 1
    const n: number = 2**m - 1
    const res: string[][] = new Array(m)
    for (let i = 0; i < m; i++) res[i] = new Array(n).fill('')
    let map: Map<TreeNode, number[]> = new Map()
    map.set(root, [0, (n-1)/2])
    let que: TreeNode[] = [root]
    while (que.length) {
        let node = que.shift()
        const [r, c] = map.get(node)
        res[r][c] = node.val + ''
        if (node.left) {
            map.set(node.left, [r+1, c-2**(height-r-1)])
            que.push(node.left)
        }
        if (node.right) {
            map.set(node.right, [r+1, c+2**(height-r-1)])
            que.push(node.right)
        }
    }
    return res
}
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

8.23 变为棋盘

题目

782. 变为棋盘

思路

翻译自这篇文章

代码

function movesToChessboard(o: number[][]): number {
    const e = o.length;
    if (o.some((e, r) => e.some((e, t) => o[0][0] ^ o[r][0] ^ o[0][t] ^ e)))
        return -1;
    const r = o.reduce((e, r, t) => e + o[0][t], 0),
        t = o.reduce((o, e, r) => o + e[0], 0);
    if (
        Math.floor(e / 2) > r ||
        r > Math.floor((e + 1) / 2) ||
        Math.floor(e / 2) > t ||
        t > Math.floor((e + 1) / 2)
    )
        return -1;
    const n = o.reduce((o, e, r) => o + Number(e[0] == r % 2), 0),
        u = o.reduce((e, r, t) => e + Number(o[0][t] == t % 2), 0),
        h = e % 2 ? (n % 2 ? e - n : n) : Math.min(e - n, n),
        a = e % 2 ? (u % 2 ? e - u : u) : Math.min(e - u, u);
    return Math.floor((h + a) / 2);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

8.24 通过翻转子数组使两个数组相等

题目

1460. 通过翻转子数组使两个数组相等

思路

桶排序的思想，记录1000个数字出现的次数

代码

function canBeEqual(target: number[], arr: number[]): boolean {
    const len1: number = target.length
    const len2: number = arr.length
    if (len1 !== len2) return false
    let bucket: number[] = new Array(1000).fill(0)
    for (let i = 0; i < len1; i++) {
        bucket[target[i]-1]++
        bucket[arr[i]-1]--
    }
    return !bucket.some(item => item > 0)
}
1
2
3
4
5
6
7
8
9
10
11

8.25 找到 K 个最接近的元素

题目

658. 找到 K 个最接近的元素

思路

类似滑动窗口，只不过这个窗口的最初大小为数组长度，通过比较左值和右值和x的差的abs来进行窗口的左缩小或右缩小，最后得到一个结果窗口返回

代码

function findClosestElements(arr: number[], k: number, x: number): number[] {
    const len: number = arr.length
    let l: number = 0
    let r: number = len - 1
    let remove = len - k
    for (let i = 0; i < remove; i++) {
        if (Math.abs(arr[l] - x) > Math.abs(arr[r] - x)) l++
        else r--
    }
    return arr.slice(l, r + 1)
}
1
2
3
4
5
6
7
8
9
10
11

8.26 数组中两元素的最大乘积

题目

1464. 数组中两元素的最大乘积

思路

当一个合格的掉库者

代码

function maxProduct(nums: number[]): number {
    nums.sort((a, b) => b - a)
    return (nums[0] - 1) * (nums[1] - 1)
}
1
2
3
4

8.27 二叉树最大宽度

题目

662. 二叉树最大宽度

思路

层序遍历，给每个二叉树节点一个下标，每次遍历一层，计算当前层数的下标差的最大值

代码

function widthOfBinaryTree(root: TreeNode | null): number {
    let que: Array<TreeNode> = [root]
    let map: Map<TreeNode, number> = new Map()
    map.set(root, 1)
    let res: number = 1
    while (que.length) {
        const len: number = que.length
        for (let i = 0; i < len; i++) {
            const node: TreeNode = que.shift()
            if (node.left) {
                map.set(node.left, (map.get(node) * 2 + 1) % 2**31-1)
                que.push(node.left)
            }
            if (node.right) {
                map.set(node.right, (map.get(node) * 2) % 2**31-1)
                que.push(node.right)
            }
            map.delete(node)
        }
        let tmpMax: number = -Infinity
        let tmpMin: number = Infinity
        map.forEach((value, key) => {
            if (value > tmpMax) tmpMax = value
            if (value < tmpMin) tmpMin = value
        })
        res = Math.max(res, tmpMax - tmpMin + 1)
    }
    return res
}
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

8.28 阶乘函数后 K 个零

题目

793. 阶乘函数后 K 个零

思路

数学方法求解，我直接看评论大佬的

代码

function preimageSizeFZF(k: number): number {
    let start: number = 1
    while (start < k) {
        start = start * 5 + 1
    }
    while (start > 1) {
        if (start - 1 == k) {
            return 0
        }
        start = (start - 1) / 5
        k %= start
    }
    return 5 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

8.29 重新排列数组

题目

1470. 重新排列数组

思路

一次遍历，直接push进去

代码

function shuffle(nums: number[], n: number): number[] {
    let res: number[] = []
    for (let i = 0; i < n; i++) {
        res.push(nums[i])
        res.push(nums[i+n])
    }
    return res
}
1
2
3
4
5
6
7
8

8.30 最大二叉树 II

题目

998. 最大二叉树 II

思路

如果val是最大的，那么根节点的值就要是val，val前面的数（也就是前面的整棵树）做为val的左子树。如果val不是最大的，那么就把val往右子树上面插（val的位置是最后，肯定在最大值右边）。

代码

function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {
    if (root == null) return new TreeNode(val)
    if (root.val < val) {
        let res: TreeNode = new TreeNode(val)
        res.left = root
        return res
    } else {
        root.right  =insertIntoMaxTree(root.right, val)
        return root
    }
}
1
2
3
4
5
6
7
8
9
10
11

8.31 验证栈序列

题目

946. 验证栈序列

思路

直接模拟一个stack就完事了

代码

function validateStackSequences(pushed: number[], popped: number[]): boolean {
    let stack: number[] = []
    let len = pushed.length
    if (len != popped.length) return false
    let push_start = 0
    let pop_start = 0
    while (push_start < len) {
        stack.push(pushed[push_start++])
        while (stack.length - 1 >= 0 && stack[stack.length-1] == popped[pop_start]) {
            // 如果栈顶元素，等于poped，模拟出栈
            stack.pop()
            pop_start++
        }
    }
    return stack.length == 0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

插句题外话，今天提交的时候突然看到去年我用Java写了那么多次，今天却直接一遍过，感觉还是在一年半学到了很多哈哈哈

题目

998. 最大二叉树 II

思路

如果val是最大的，那么根节点的值就要是val，val前面的数（也就是前面的整棵树）做为val的左子树。如果val不是最大的，那么就把val往右子树上面插（val的位置是最后，肯定在最大值右边）。

代码

function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {
    if (root == null) return new TreeNode(val)
    if (root.val < val) {
        let res: TreeNode = new TreeNode(val)
        res.left = root
        return res
    } else {
        root.right  =insertIntoMaxTree(root.right, val)
        return root
    }
}
1
2
3
4
5
6
7
8
9
10
11

8.31 验证栈序列

题目

946. 验证栈序列

思路

直接模拟一个stack就完事了

代码

function validateStackSequences(pushed: number[], popped: number[]): boolean {
    let stack: number[] = []
    let len = pushed.length
    if (len != popped.length) return false
    let push_start = 0
    let pop_start = 0
    while (push_start < len) {
        stack.push(pushed[push_start++])
        while (stack.length - 1 >= 0 && stack[stack.length-1] == popped[pop_start]) {
            // 如果栈顶元素，等于poped，模拟出栈
            stack.pop()
            pop_start++
        }
    }
    return stack.length == 0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

插句题外话，今天提交的时候突然看到去年我用Java写了那么多次，今天却直接一遍过，感觉还是在一年半学到了很多哈哈哈

打卡时刻