LeetCode每日一题之2023年4月份

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

2023年04月01日

831. 隐藏个人信息

解法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
func maskPII(s string) string {
    var ans string
    if strings.Contains(s, "@") {
        s = strings.ToLower(s)
        ans = s[0:1] + "*****"
        for i := 1; i < len(s); i++ {
            if s[i] == '@' {
                ans += s[i-1:]
                break
            }
        }
    } else {
        var tmp string
        for i := 0; i < len(s); i++ {
            if unicode.IsDigit(rune(s[i])) {
                tmp += string(s[i])
            }
        }

        ans =  tmp[len(tmp)-4:]
        switch len(tmp)-10 {
        case 0:
            ans = "***-***-" + ans
        case 1:
            ans = "+*-***-***-" + ans
        case 2:
            ans = "+**-***-***-" + ans
        case 3:
            ans = "+***-***-***-" + ans
        default:
        }
    }

    return ans
}

2023年04月02日

1039. 多边形三角剖分的最低得分

解法1：是用DP，将问题转换成相同的子问题，使用二维DP，记录两个坐标之间的数字组成的多边形形成最低分。

则有

1
dp[i][j] = min(dp[i][k] + values[i] * values[k] * values[j] + dp[k][j])
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 minScoreTriangulation(values []int) int {
   m := len(values)
   dp := make([][]int, m)
   for i := 0; i < m; i++ {
      dp[i] = make([]int, m)
   }

   // 宽度
   for g := 2; g < m; g++ {
      // i
      for i := 0; i < m-g; i++ {
         // j = i + g
         j := g + i
         dp[i][j] = math.MaxInt
         for k := i + 1; k < j; k++ {
            dp[i][j] = min(dp[i][j], dp[i][k]+values[i]*values[k]*values[j]+dp[k][j])
         }
      }
   }
   return dp[0][m-1]
}

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

2023年04月03日

解法1：按照题意，使用贪心算法，需要计算出转换数字之后的值小于当前数字，并且该数字最大，那么就需要进行逆序遍历，找到i，满足arr[i] > arr[i+1]，然后找到j，满足arr[j] < arr[i] && arr[j] != arr[j-1]，并且j最大值，因此，j也可以逆序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func prevPermOpt1(arr []int) []int {
   m := len(arr)

   i := m - 2
   for ; i >= 0; i-- {
      if arr[i] > arr[i+1] {
         j := m-1
         for arr[j] >= arr[i] || arr[j] == arr[j-1] {
            j--
         }
         arr[i], arr[j] = arr[j], arr[i]
         break
      }
   }
   return arr
}

2023年04月04日

1000. 合并石头的最低成本

DP的好题！

解法1：题目是一个区间动态规划问题，需要注意的是，比以前射气球的问题要经典，状态不仅仅是石头堆，还有其他的dp，因此，为了简化思维，可以将其他的dp也通过子问题的形式解决。使用三维dp，一维是左区间，二维是右区间，三维则是堆数。

第三维使用堆，这个挺难想出来的。

最终结果是求解dp[0][m-1][1]，因此遍历的时候，左区间是从右到左，右区间则是从左区间从左到右。

状态转移有两种，对应两种情况：

  1. 从k堆，合并成1堆，则有dp[i][j][1]=dp[i][j][k] + sum[i][j]，因此要存储前缀和。前缀和的方式有两种，一种是使用二维数组，记录i到j之间的和，二种是使用一维数组，i到j之间的和是sum[j]-sum[i]+stones[i]

  2. 堆数从2堆到p堆，有关系

    1
    dp[i][j][p] = min(dp[i][l][1] + dp[l+1][j][p-1]);其中l=[i,j-1],p=[2,k]

    解释起来，就是将左边i到l合并成1堆，其他的合并成p-1堆，这就是一个区间dp，直到求出k堆，而且中间值p的步长是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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
func mergeStones(stones []int, k int) int {
   m := len(stones)

   if (m-1)%(k-1) != 0 {
      return -1
   }

   sum := make([][]int, m)
   for i := 0; i < m; i++ {
      sum[i] = make([]int, m)
      sum[i][i] = stones[i]
      for j := i + 1; j < m; j++ {
         sum[i][j] = sum[i][j-1] + stones[j]
      }
   }

   // 定义三维数组，一维是左边边界，二维是右边边界，三维是堆数，值是最低成本
   //
   // 则有状态转移
   // 1. 将k堆，集合成1堆
   // dp[i][j][1] = dp[i][j][k] + sum[i][j]
   // 2. 集合成p堆
   // dp[i][j][p] = min(dp[i][l][1] + dp[l+1][j][p-1]);其中l=[i,j-1],p=[2,k]
   // 初始化 dp[i][i][1] = 0 代表不需要移动

   dp := make([][][]int, m)
   for i := m - 1; i >= 0; i-- {
      dp[i] = make([][]int, m)
      dp[i][i] = make([]int, k+1)
      dp[i][i][1] = 0
      for j := i + 1; j < m; j++ {
         dp[i][j] = make([]int, k+1)
         for p := 2; p < k+1; p++ {
            dp[i][j][p] = math.MaxInt
            for l := i; l < j; l += k - 1 {
               dp[i][j][p] = min(dp[i][j][p], dp[i][l][1]+dp[l+1][j][p-1])
            }
         }
         dp[i][j][1] = dp[i][j][k] + sum[i][j]
      }
   }

   return dp[0][m-1][1]
}

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

2023年04月05日

2427. 公因子的数目

解法1：按照题目要求，从1便利到a或者b其中较小的数，求余即可

1
2
3
4
5
6
7
8
9
10
11
func commonFactors(a int, b int) int {
    var ans int

    for i := 1; i <= a && i <= b ; i++ {
        if a %i == 0 && b %i == 0 {
            ans ++
        }
    }

    return ans
}

2023年04月06日

1017. 负二进制转换

解法1：使用数学中的模拟，判断最后一位，是否是0，如果是0，则为0，如果不为0，则为1，并且为1的时候，要加1或者减1，当位数为偶数是减1，如果为奇数位时，加1，最终将结果翻转即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func baseNeg2(n int) string {
    if n == 0 {
        return "0"
    }
    var ans []string
    k := -1
    for n != 0 {
        if n%2 == 0 {
            ans = append(ans, "0")
        } else {
            ans = append(ans, "1")
            n += k
        }
        k *= -1
        n >>= 1
    }
    for i := 0; i < len(ans)/2; i++ {
        ans[i], ans[len(ans)-1-i] = ans[len(ans)-1-i], ans[i]
    }

    return strings.Join(ans,"")
}

2023年04月07日

1040. 移动石子直到连续 II

解法1：使用数学的方式思考。先排序，最大值和最小值之间空的位置可以计算出来，为了求得最大值，则可以确保将空闲最小的边界留出来，其他的位置填满，也就是比较0到1之间的空隙，和n-1和n-2之间的空隙，取小，将这部分留出来，其他位置填上，最大值就是留空的部分，减去间隙小的部分。

最小值是填补上间隙，并且可以确保这个长度n是可以填满的，花费就是m - (j - i + 1)，取最小值。并且需要考虑当出现边界上是端点，并且其他的石头是连续的时候，需要花费2个这个特例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func numMovesStonesII(stones []int) []int {
    sort.Ints(stones)
    m := len(stones)

    s1 := stones[m-1] - stones[0] + 1 - m
    s2 := min(stones[m-1]-stones[m-2]-1, stones[1]-stones[0]-1)
    max := s1 - s2

    mi := max
    for i, j := 0, 0; i < m-1; i++ {
        for j+1 < m && stones[j+1]-stones[i]+1 <= m {
            j++
        }
        cost := m - (j - i + 1)
        if j-i+1 == m-1 && stones[j]-stones[i]+1 == m-1 {
            cost = 2
        }
        mi = min(mi, cost)
    }

    return []int{mi, s1 - s2}
}

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

2023年04月08日

1125. 最小的必要团队

解法1：将能力转换成二进制，然后使用dfs，选取任意成员是否参与，也就是暴力方法，这种方法会超时。

解法2：使用dp进行状态压缩，自定向下的dp，dp[i]记录需要技能集合为i时，所需要的最少人数，最终结果是dp[(1<<m)-1]。逐步增加成员，增加成员时，更新dp状态。

状态转移为：增加一个成员时，跟之前所有已记录的状态进行对比，取合集，称为新的技能合集，如果新技能合集原始不存在，则更新，如果存在，则判断人数，新的技能合集的人数小于老技能合集的人数+1时进行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func smallestSufficientTeam(reqSkills []string, people [][]string) (ans []int) {
    // 将人员的能力压缩成二进制
    peopleSkill := make([]int, len(people))
    for i, p := range people {
        var tmp int
        for _, skill := range p {
            for k, reqSkill := range reqSkills {
                if reqSkill == skill {
                    tmp += 1 << k
                    break
                }
            }
        }
        peopleSkill[i] = tmp
    }
    //fmt.Println(peopleSkill)

    dp := make([][]int, 1<<len(reqSkills))
    // 便利所有人的技能
    for i := 0; i < len(peopleSkill); i++ {
        // 便利已经存在的技能
        for j := len(dp) - 1; j >=0; j-- {
            if len(dp[j]) == 0 {
                continue
            }
            // 这个人的技能和已存在的技能合并
            tmp := j | peopleSkill[i]
            // 新的技能集合不存在
            // 或者存在，但是长度太大
            if dp[tmp] == nil || len(dp[j])+1 < len(dp[tmp]) {
                // golang注意，append的时候，可能会影响原数组，因此要copy
                dp[tmp] = make([]int,len(dp[j]))
                copy(dp[tmp],dp[j])
                dp[tmp] = append(dp[tmp], i)
            }
        }
        if len(dp[peopleSkill[i]]) != 1 {
            dp[peopleSkill[i]] = []int{i}
        }
    }

    return dp[(1<<len(reqSkills))-1]
}

2023年04月09日

2399. 检查相同字母间的距离

解法1：使用有限数组代替HashMap，记录这个字母首次出现的位置，第二次出现的时候获取间隔，与distance进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func checkDistances(s string, distance []int) bool {
    var all [26]int
    for i := 0; i < len(s); i++ {
        tmp := int(s[i] - 'a')
        if all[tmp] == 0 {
            all[tmp] = i + 1
        } else {
            if i - all[tmp] != distance[tmp] {
                return false 
            }
        }
    }
    
    return true
}

2023年04月10日

1019. 链表中的下一个更大节点

解法1：使用单调递减栈记录最大值和位置值，然后遍历node，碰到小于或等于栈顶的入栈，大于栈顶的出栈，一直出到不大于栈顶，出栈的时候，通过位置值修改结果

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
func nextLargerNodes(head *ListNode) []int {
    // 单调递减栈和结果
    type node struct {
        i   int
        max int
    }

    res := []int{0}
    stack := []node{{i: 0, max: head.Val}}
    start := 1
    head = head.Next
    for head != nil {
        for len(stack) > 0 && head.Val > stack[len(stack)-1].max {
            res[stack[len(stack)-1].i] = head.Val
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, node{
            i:   start,
            max: head.Val,
        })
        start++
        res = append(res, 0)
        head = head.Next
    }
    return res
}

2023年04月11日

1041. 困于环中的机器人

解法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
func isRobotBounded(instructions string) bool {
    pos := [2]int{}
    dir := [2]int{0, 1}

    for i := 0; i < 4; i++ {

        for _, instruction := range instructions {
            switch instruction {
            case 'G':
                pos[0] += dir[0]
                pos[1] += dir[1]
            case 'L':
                pos[0], pos[1] = pos[1]*-1, pos[0]
            case 'R':
                pos[0], pos[1] = pos[1], pos[0]*-1
            }
        }
        if pos == [2]int{0, 0} && dir == [2]int{0, 1} {
            return true
        }
    }

    return false
}

2023年04月12日

1147. 段式回文

解法1：使用双指针，前和尾指针往中间移动，移动期间，便利长度的指针，如果满足条件，则结果加2，如果不满足条件，则结果加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func longestDecomposition(text string) int {
    start, end, res := 0, len(text)-1, 0

    for start <= end {
        var l int
        // 左指针往右移动，寻找字符相等右边的，并且字符串也相等
        for start+l < end  && text[start:start+l+1] != text[end-l:end+1] {
            l++
        }

        if start+l < end-l {
            res += 2
        } else {
            res += 1
        }
        start += l + 1
        end -= l + 1
    }

    return res
}

2023年04月13日

2404. 出现最频繁的偶数元素

解法1：使用HashMap或者有限数组，key或者位置为偶数，值为个数，便利的时候判断个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func mostFrequentEven(nums []int) int {
    all := [10e5 >> 1]int{}
    res, pos := -1, 0

    for i := 0; i < len(nums); i++ {
        if nums[i]%2 == 0 {
            half := nums[i] >> 1
            all[half]++
            if all[half] > res {
                res = all[half]
                pos = half
            } else if all[half] == res && half < pos {
                pos = half
            }
        }
    }

    if res == -1 {
        return -1
    }

    return pos * 2
}

2023年04月14日

1023. 驼峰式匹配

解法1：使用双指针，一个指针移动query，一个指针移动pattern，如果相等，则共同移动，如果不相等，则判断query是否是小写，如果是小写，则移动query的指针，如果不是，则停止指针移动。 最终判断下剩余的query是否还含有大写字母。

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
func camelMatch(queries []string, pattern string) []bool {
    ans := make([]bool, len(queries))

    for i, query := range queries {
        var m, n int
        for m < len(query) && n < len(pattern) {
            if query[m] == pattern[n] {
                m++
                n++
            } else {
                if unicode.IsLower(rune(query[m])) {
                    m++
                } else {
                    break
                }
            }
        }
        for m < len(query) && unicode.IsLower(rune(query[m])) {
            m++
        }
        if n == len(pattern) && m == len(query) {
            ans[i] = true
        }
    }

    return ans
}

2023年04月15日

1042. 不邻接植花

解法1:DFS思路，先创建路径数组，然后便利

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func gardenNoAdj(n int, paths [][]int) []int {
    adj := make([][]int, n)
    for i := 0; i < n; i++ {
       adj[i] = []int{}
    }
    for _, path := range paths {
       adj[path[0]-1] = append(adj[path[0]-1], path[1]-1)
       adj[path[1]-1] = append(adj[path[1]-1], path[0]-1)
    }
    ans := make([]int, n)
    for i := 0; i < n; i++ {
       colored := make([]bool, 5)
       for _, vertex := range adj[i] {
          colored[ans[vertex]] = true
       }
       for j := 1; j <= 4; j++ {
          if !colored[j] {
             ans[i] = j
             break
          }
       }
    }
    return ans
}

2023年04月16日

1157. 子数组中占绝大多数的元素

解法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
type MajorityChecker struct {
    arr []int
    loc map[int][]int
}

func Constructor(arr []int) MajorityChecker {
    rand.Seed(time.Now().UnixNano())
    loc := map[int][]int{}
    for i, x := range arr {
       loc[x] = append(loc[x], i)
    }
    return MajorityChecker{arr, loc}
}

func (mc *MajorityChecker) Query(left, right, threshold int) int {
    length := right - left + 1
    for i := 0; i < 20; i++ {
       x := mc.arr[rand.Intn(right-left+1)+left]
       pos := mc.loc[x]
       occ := sort.SearchInts(pos, right+1) - sort.SearchInts(pos, left)
       if occ >= threshold {
          return x
       }
       if occ*2 >= length {
          break
       }
    }
    return -1
}

2023年04月17日

2409. 统计共同度过的日子数

解法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
func countDaysTogether(arriveAlice string, leaveAlice string, arriveBob string, leaveBob string) int {
    datesOfMonths := []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
    prefixSum := make([]int, 1)
    for _, date := range datesOfMonths {
       prefixSum = append(prefixSum, prefixSum[len(prefixSum) - 1] + date)
    }

    arriveAliceDay := calculateDayOfYear(arriveAlice, prefixSum)
    leaveAliceDay := calculateDayOfYear(leaveAlice, prefixSum)
    arriveBobDay := calculateDayOfYear(arriveBob, prefixSum)
    leaveBobDay := calculateDayOfYear(leaveBob, prefixSum)

    return max(0, min(leaveAliceDay, leaveBobDay) - max(arriveAliceDay, arriveBobDay) + 1)
}

func calculateDayOfYear(day string, prefixSum []int) int {
    month, _ := strconv.Atoi(day[:2])
    date, _ := strconv.Atoi(day[3:])
    return prefixSum[month - 1] + date
}

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

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

2023年04月18日

1026. 节点与其祖先之间的最大差值

解法1:将当前最大值和最小值传递到子节点，然后在子节点判断最大差值，然后dfs到下层判断。

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
func max(a, b int) int {
    if a > b {
       return a
    }
    return b
}

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

func abs(a int) int {
    if a < 0 {
       return -a
    }
    return a
}

func dfs(root *TreeNode, mi, ma int) int {
    if root == nil {
       return 0
    }
    diff := max(abs(root.Val - mi), abs(root.Val - ma))
    mi, ma = min(mi, root.Val), max(ma, root.Val)
    diff = max(diff, dfs(root.Left, mi, ma))
    diff = max(diff, dfs(root.Right, mi, ma))
    return diff
}

func maxAncestorDiff(root *TreeNode) int {
    return dfs(root, root.Val, root.Val)
}

2023年04月19日

1043. 分隔数组以得到最大和

解法1:DP，定义数组，第i个代表数组长度为i时，分割数组的最大和，有 dp[i]=max{dp[j]+len*max[j->i]} ，当j从1到k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxSumAfterPartitioning(arr []int, k int) int {
    n := len(arr)
    d := make([]int, n+1)
    for i := 1; i <= n; i++ {
       maxValue := arr[i-1]
       for j := i - 1; j >= max(0, i - k); j-- {
          d[i] = max(d[i], d[j] + maxValue * (i - j))
          if j > 0 && arr[j - 1] > maxValue {
             maxValue = arr[j - 1]
          }
       }
    }
    return d[n]
}

func max(x, y int) int {
    if x > y {
       return x
    }
    return y
}

2023年04月20日

1373. 二叉搜索子树的最大键值和

解法1:DFS，判断每个子节点是否是搜索树，如果是搜索树，则使用左右节点和自身的加值

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
const INF = 0x3f3f3f3f
type SubTree struct {
    IsBST bool
    MinVal int
    MaxVal int
    SumVal int
}
var res int

func maxSumBST(root *TreeNode) int {
    res = 0
    dfs(root)
    return res
}

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

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

func dfs(root *TreeNode) *SubTree {
    if root == nil {
       return &SubTree{true, INF, -INF, 0}
    }
    left := dfs(root.Left)
    right := dfs(root.Right)

    if left.IsBST && right.IsBST && root.Val > left.MaxVal && root.Val < right.MinVal {
       sum := root.Val + left.SumVal + right.SumVal
       res = max(res, sum)
       return &SubTree{true, min(left.MinVal, root.Val), max(root.Val, right.MaxVal), sum}
    } else {
       return &SubTree{false, 0, 0, 0}
    }
}

2023年04月21日

LCP 33. 蓄水

解法1:首先可以确定，先升级桶，然后倒水比较好，那么反向推倒，如果倒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
func storeWater(bucket []int, vat []int) int {
    n := len(bucket)
    maxk := 0
    for _, v := range vat {
       if v > maxk {
          maxk = v
       }
    }
    if maxk == 0 {
       return 0
    }
    res := math.MaxInt32
    for k := 1; k <= maxk && k < res; k++ {
       t := 0
       for i := 0; i < n; i++ {
          t += max(0, (vat[i] + k - 1) / k - bucket[i])
       }
       res = min(res, t+k)
    }
    return res
}

func max(x, y int) int {
    if x > y {
       return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
       return x
    }
    return y
}

2023年04月22日

1080. 根到叶路径上的不足节点

解法1: DFS，将剩余的 limit 传递到左右节点，返回该节点是否满足，如果节点值小于 limit ，则删除该节点

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
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
    haveSufficient := checkSufficientLeaf(root, 0, limit)
    if haveSufficient {
       return root
    } else {
       return nil
    }
}

func checkSufficientLeaf(node *TreeNode, sum int, limit int) bool {
    if node == nil {
       return false
    }
    if node.Left == nil && node.Right == nil {
       return node.Val+sum >= limit
    }
    haveSufficientLeft := checkSufficientLeaf(node.Left, sum+node.Val, limit)
    haveSufficientRight := checkSufficientLeaf(node.Right, sum+node.Val, limit)
    if !haveSufficientLeft {
       node.Left = nil
    }
    if !haveSufficientRight {
       node.Right = nil
    }
    return haveSufficientLeft || haveSufficientRight
}

2023年04月23日

1090. 受标签影响的最大值

解法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
func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {
    n := len(values)
    idx := make([]int, n)
    for i := 0; i < n; i++ {
       idx[i] = i
    }
    sort.Slice(idx, func(i, j int) bool {
       return values[idx[i]] > values[idx[j]]
    })

    ans, choose := 0, 0
    cnt := make(map[int]int)
    for i := 0; i < n; i++ {
       label := labels[idx[i]]
       if cnt[label] == useLimit {
          continue
       }
       choose++
       ans += values[idx[i]]
       cnt[label]++
       if choose == numWanted {
          break
       }
    }
    return ans
}

2023年04月24日

1377. T 秒后青蛙的位置

解法1:先将图使用二维数组做出来，然后使用DFS跳。

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
func frogPosition(n int, edges [][]int, t int, target int) float64 {
    G := make([][]int, n+1)
    for i := 0; i <= n; i++ {
       G[i] = make([]int, 0)
    }
    for _, e := range edges {
       G[e[0]] = append(G[e[0]], e[1])
       G[e[1]] = append(G[e[1]], e[0])
    }
    seen := make([]bool, n+1)
    return dfs(G, seen, 1, t, target)
}

func dfs(G [][]int, seen []bool, i int, t int, target int) float64 {
    nxt := len(G[i])
    if i > 1 {
       nxt -= 1
    }
    if t == 0 || nxt == 0 {
       if i == target {
          return 1.0
       } else {
          return 0.0
       }
    }
    seen[i] = true
    ans := 0.0
    for _, j := range G[i] {
       if !seen[j] {
          ans += dfs(G, seen, j, t - 1, target)
       }
    }
    return ans / float64(nxt)
}

2023年04月25日

2418. 按身高排序

解法1: sort排序即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func sortPeople(names []string, heights []int) []string {
    n := len(names)
    indices := make([]int, n)
    for i := 0; i < n; i++ {
       indices[i] = i
    }
    sort.Slice(indices, func(i, j int) bool {
       return heights[indices[j]] < heights[indices[i]]
    })
    res := make([]string, n)
    for i := 0; i < n; i++ {
       res[i] = names[indices[i]]
    }
    return res
}

2023年04月26日

1031. 两个非重叠子数组的最大和

解法1: 计算左边字段和右边字段相加的最大和，通过中间的线往右移动，进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxSumTwoNoOverlap(nums []int, firstLen, secondLen int) (ans int) {
    n := len(nums)
    s := make([]int, n+1)
    for i, x := range nums {
       s[i+1] = s[i] + x // 计算 nums 的前缀和
    }
    maxSumA, maxSumB := 0, 0
    for i := firstLen + secondLen; i <= n; i++ {
       maxSumA = max(maxSumA, s[i-secondLen]-s[i-secondLen-firstLen])
       maxSumB = max(maxSumB, s[i-firstLen]-s[i-firstLen-secondLen])
       ans = max(ans, max(maxSumA+s[i]-s[i-secondLen], // 左 a 右 b
          maxSumB+s[i]-s[i-firstLen])) // 左 b 右 a
    }
    return
}

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

2023年04月27日

1048. 最长字符串链

解法1: 先排序，从长度从短到长排序，然后动态规划，到某个字段的最大长度 = 前字段最大长度 + 1 ，如果前字段是该字段的前身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func longestStrChain(words []string) int {
    cnt := map[string]int{}
    sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
    res := 0
    for _, word := range words {
       cnt[word] = 1
       for i := range word {
          prev := word[:i] + word[i + 1:]
          if j := cnt[prev] + 1; j > cnt[word] {
             cnt[word] = j
          }
       }
       if cnt[word] > res {
          res = cnt[word]
       }
    }
    return res
}

2023年04月28日

1172. 餐盘栈

解法1: 使用数组模拟栈，一个数组记录每个栈顶在栈的位置，一个数组记录 PopAtStack 删除的位置。push 时，先考虑记录删除位置栈的地方是否为空，为空则先填入，如果非空，则先填入。popAtStack 时，找到这个栈顶的位置，找到具体的值，pop出去之后，记录到删除位置的数组中。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
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
69
70
71
72
type DinnerPlates struct {
    capacity int
    stack []int
    top []int
    poppedPos []int
}

func Constructor(capacity int) DinnerPlates {
    return DinnerPlates{capacity, []int{}, []int{}, []int{}}
}

func (this *DinnerPlates) Push(val int) {
    if len(this.poppedPos) == 0 {
       pos := len(this.stack)
       this.stack = append(this.stack, val)
       if pos % this.capacity == 0 {
          this.top = append(this.top, 0)
       } else {
          stackPos := len(this.top) - 1
          stackTop := this.top[stackPos]
          this.top[stackPos] = stackTop + 1
       }
    } else {
       pos := this.poppedPos[0]
       this.poppedPos = this.poppedPos[1:]
       this.stack[pos] = val
       index := pos / this.capacity
       stackTop := this.top[index]
       this.top[index] = stackTop + 1
    }
}

func (this *DinnerPlates) Pop() int {
    for len(this.stack) > 0 && len(this.poppedPos) > 0 && this.poppedPos[len(this.poppedPos) - 1] == len(this.stack) - 1 {
       this.stack = this.stack[:len(this.stack) - 1]
       pos := this.poppedPos[len(this.poppedPos) - 1]
       this.poppedPos = this.poppedPos[:len(this.poppedPos) - 1]
       if pos % this.capacity == 0 {
          this.top = this.top[:len(this.top) - 1]
       }
    }
    if len(this.stack) == 0 {
       return -1
    } else {
       pos := len(this.stack) - 1
       val := this.stack[pos]
       this.stack = this.stack[:pos]
       if pos % this.capacity == 0 && len(this.top) > 0 {
          this.top = this.top[:len(this.top) - 1]
       } else if len(this.top) > 0 {
          this.top[len(this.top) - 1] -= 1
       }
       return val
    }
}

func (this *DinnerPlates) PopAtStack(index int) int {
    if index >= len(this.top) {
       return -1
    }
    stackTop := this.top[index]
    if stackTop < 0 {
       return -1
    }
    this.top[index] = stackTop - 1
    pos := index * this.capacity + stackTop
    i := sort.SearchInts(this.poppedPos, pos)
    this.poppedPos = append(this.poppedPos, 0)
    copy(this.poppedPos[i+1:], this.poppedPos[i:])
    this.poppedPos[i] = pos
    return this.stack[pos]
}

2023年04月29日

2423. 删除字符使频率相同

解法1: 便利字符，记录每个字符的出现次数，然后每一个字母减去一个，判断减去之后的字符出现的是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func equalFrequency(word string) bool {
    charCount := [26]int{}
    for _, c := range word {
       charCount[c - 'a']++
    }
    for i := 0; i < 26; i++ {
       if charCount[i] == 0 {
          continue
       }
       charCount[i]--
       frequency := make(map[int]bool)
       for _, f := range charCount {
          if f > 0 {
             frequency[f] = true
          }
       }
       if len(frequency) == 1 {
          return true
       }
       charCount[i]++
    }
    return false
}

2023年04月30日

1033. 移动石子直到连续

解法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
func numMovesStones(a int, b int, c int) []int {
    x:= min(min(a, b), c)
    z:= max(max(a, b), c)
    y:= a + b + c - x - z
    res := []int{2, z - x - 2}
    if ((z - y) == 1 && (y - x) == 1) {
       res[0] = 0;
    } else if ((z - y) <= 2 || (y - x) <= 2) {
       res[0] = 1;
    }
    return res
}

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

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