LeetCode每日一题之2023年4月份

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
}