LeetCode每日一题之2023年2月份

Posted on Edited on In Views:
数据结构和算法是很重要的，无论是在工作过程中还是在面试笔试中。这里记录LeetCode每日一题。

2023年02月22日

1140. 石子游戏 II

解法1：DP，茅塞顿开点：

  1. 从后往前推导
  2. 自己拿的最多，则B拿的最少
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
func stoneGameII(piles []int) int {
    n := len(piles)
    // 二维数组，记录当A拿第一堆时，第i堆被A拿的时候对应的M的最大石头数量
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    // 从最后一堆开始往前循环
    for i, s := n-1, 0; i >= 0; i-- {
        s += piles[i]
        // M 从1开始循环，直到 i/2+1，也就是假设可以一次性拿一半，M最大是已经拿了的一倍
        for m := 1; m <= i/2+1; m++ {
            // 状态转移方程，可以全部都拿，就全部都拿
            if i+m*2 >= n {
                f[i][m] = s
            } else {
                // 不能全部都拿
                mn := math.MaxInt
                // 便利M，获取B拿最少的
                for x := 1; x <= m*2; x++ {
                    mn = min(mn, f[i+x][max(m, x)])
                }
                // 剩下的就是自己最多的
                f[i][m] = s - mn
            }
        }
    }
    return f[0][1]
}

func min(a, b int) int {
    if b < a {
        return b
    }
    return a
}
func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

2023年02月23日

1238. 循环码排列

解法1：将所有的值与start取反，res[j]^start，得到格雷码，res[j]^start|1<<i处理格雷码，然后再与start取反，得到结果

1
2
3
4
5
6
7
8
9
10
func circularPermutation(n int, start int) []int {
    res := make([]int, 1, 1<<n)
    res[0] = start
    for i := 0; i < n; i++ {
        for j := len(res) - 1; j >= 0; j-- {
            res = append(res, res[j]^start|1<<i^start)
        }
    }
    return res
}

顺便解决格雷编码的问题：89. 格雷编码

1
2
3
4
5
6
7
8
9
10
func grayCode(n int) []int {
    res := make([]int, 1, 1<<n)
    res[0] = 0
    for i := 0; i < n; i++ {
        for j := len(res) - 1; j >= 0; j-- {
            res = append(res, res[j]|1<<i)
        }
    }
    return res
}

2023年02月24日

2357. 使数组中所有元素都等于零

解法1：使用HashMap，记录所有非0的数字且数字不重复的个数

1
2
3
4
5
6
7
8
9
func minimumOperations(nums []int) int {
    all := make(map[int]bool, len(nums))
    for i := 0; i < len(nums); i++ {
        if nums[i] != 0 && !all[nums[i]] {
            all[nums[i]] = true
        }
    }
    return len(all)
}

解法2：题目中数字大小不超过100，可以使用有限数组代替，最后计算这个数组中有数字的位的次数。

2023年02月25日

1247. 交换字符使得字符串相同

解法1：字符串计算，理解要点：

  • 可以通过一次交换，使得xy或yx的值减少 2。
  • 可以通过两次交换，使得xy和yx的值各减少 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func minimumSwap(s1 string, s2 string) int {
    var xy, yx int
    // 计算xy和yx的个数
    for i := 0; i < len(s1); i++ {
        if s1[i] != s2[i] {
            if s1[i] == 'x' {
                xy++
            } else {
                yx++
            }
        }
    }

    // 如果两者相加最后是奇数，则代表无法交换得到结果
    if (xy-yx)&1 == 1 {
        return -1
    }

    // 最终结果是将一次交换使得xy-2,yx-2，以及两次交换使得xy和yx各-1
    return xy>>1 + yx>>1 + (xy&1)*2
}

2023年02月26日

1255. 得分最高的单词集合

解法1：暴力，dfs，将单词往下面尝试

核心理解点是，只有两种情况，要么算上自己，letters中减去自己的字母，然后加上之后的最大值，要么回溯，不计算自己，用原来的letters直接计算之后的最大值。

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
func maxScoreWords(words []string, letters []byte, score []int) (ans int) {
    // 计算每个英文字母的个数
    var letter [26]int
    for i := 0; i < len(letters); i++ {
        letter[letters[i]-'a']++
    }
    // 使用dfs，进行回溯
    return dfs(words, letter, score)
}

func dfs(words []string, letter [26]int, score []int) int {
    // 没有words的情况下直接返回
    if len(words) == 0 {
        return 0
    }

    // 例如有a，b，c
    // 只有两种情况，要么是加上a，然后计算dfs(b,c)
    // 要么就是回溯，不加上a，计算dfs(b,c)
    // 返回两者的最大值
    var res int
    var flag bool
    tmpLetter := letter
    tmp := words[0]
    for i := 0; i < len(tmp); i++ {
        if tmpLetter[tmp[i]-'a'] <= 0 {
            flag = true
            break
        }
        tmpLetter[tmp[i]-'a']--
        res += score[tmp[i]-'a']
    }

    if flag {
        // 此时a不满足，则直接下一个
        return dfs(words[1:], letter, score)
    }
    // 此时a满足，结果只有两种情况，要么是算自己的最大值，要么是不算自己的最大值，两者选一个最大值返回
    return max(dfs(words[1:], tmpLetter, score)+res, dfs(words[1:], letter, score))
}

func max(i, i2 int) int {
    if i > i2 {
        return i
    }
    return i2
}

2023年02月27日

1144. 递减元素使数组呈锯齿状

解法1：暴力，将两种情况需要的次数都计算出来，选小的一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func movesToMakeZigzag(nums []int) int {
    if len(nums) == 1 {
        return 0
    }
  
    var inc, dec int
    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            var tmpMin int
            if i == 0 {
                tmpMin = nums[1]
            } else if i == len(nums)-1 {
                tmpMin = nums[len(nums)-2]
            } else {
                tmpMin = min(nums[i-1], nums[i+1])
            }
            if nums[i] >= tmpMin {
                inc += nums[i] - tmpMin + 1
            }
        } else {
            var tmpMin int
            if i == len(nums)-1 {
                tmpMin = nums[len(nums)-2]
            } else {
                tmpMin = min(nums[i-1], nums[i+1])
            }
            if nums[i] >= tmpMin {
                dec += nums[i] - tmpMin + 1
            }
        }
    }
    return min(inc, dec)
}

func min(i int, i2 int) int {
    if i < i2 {
        return i
    }
    return i2
}

2023年02月28日

2363. 合并相似的物品

解法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
func mergeSimilarItems(items1 [][]int, items2 [][]int) [][]int {
    sort.Slice(items1, func(i, j int) bool { return items1[i][0] < items1[j][0] })
    sort.Slice(items2, func(i, j int) bool { return items2[i][0] < items2[j][0] })

    var res [][]int
    i, j := 0, 0
    for i < len(items1) && j < len(items2) {
        if items1[i][0] < items2[j][0] {
            res = append(res, items1[i])
            i++
        } else if items1[i][0] > items2[j][0] {
            res = append(res, items2[j])
            j++
        } else {
            items1[i][1] += items2[j][1]
            res = append(res, items1[i])
            i++
            j++
        }
    }
    for ; i < len(items1); i++ {
        res = append(res, items1[i])
    }
    for ; j < len(items2); j++ {
        res = append(res, items2[j])
    }
    return res
}