一 美丽下标对的数目

  • 模拟 GCD

  • Python

     1class Solution:
 2    def countBeautifulPairs(self, nums: List[int]) -> int:
 3        n = len(nums)
 4        ans = 0
 5
 6        for i in range(n):
 7            first = nums[i]
 8            while first >= 10:
 9                first //= 10
10            for j in range(i+1, n):
11                last = nums[j] % 10
12                if gcd(first, last) == 1:
13                    ans += 1
14        return ans
15
16
17def gcd(a, b):
18    if b == 0:
19        return a
20    return gcd(b, a % b)

  • Golang

     1func countBeautifulPairs(nums []int) (ans int) {
 2    n := len(nums)
 3
 4    for i := 0; i < n; i++ {
 5        first := nums[i]
 6        for first >= 10 {
 7            first /= 10
 8        }
 9        for j := i + 1; j < n; j++ {
10            last := nums[j] % 10
11            if gcd(first, last) == 1{
12                ans++
13            }
14        }
15    }
16    return ans
17}
18
19func gcd(a, b int) int {
20    if b == 0 {
21        return a
22    }
23    return gcd(b, a%b)
24}

[二 得到整数零需要执行的最少操作数]

  • 枚举

    从1开始枚举k, 设x=num1-num2*k， x为k个 2 **i 之和

    当x < k时，但k个 2 **i 之和最小为k，此时操作不成立。且随着k增大，x减小，之后条件也不会成立。因此，此时返回-1

    当k最小为 bitCount(x)，bitCount为x中1的个数，由于2 i 可以由两个2i-1组成。因此k的取值范围为 bitCount(x) <=k < x

  • Python

     1class Solution:
 2    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
 3        k = 1
 4        while True:
 5            x = num1 - k * num2
 6
 7            if x < k:
 8                return -1
 9
10            if k >= x.bit_count():
11                return k
12            k += 1

  • Golang

     1
 2func makeTheIntegerZero(num1 int, num2 int) int {
 3    k := 1
 4    for {
 5        x := num1 - num2*k
 6
 7        if x < k {
 8            return -1
 9        }
10
11        if k >= bitCount(x) {
12            return k
13        }
14        k++
15    }
16}
17
18func bitCount(a int) (c int) {
19    for a != 0 {
20        if a%2 != 0 {
21            c++
22        }
23        a /= 2
24    }
25    return
26}

[三 将数组划分成若干好子数组的方式]

  • 数学

  • Python

     1class Solution:
 2    def numberOfGoodSubarraySplits(self, nums: List[int]) -> int:
 3        if sum(nums) == 0:
 4            return 0
 5        ans = 1
 6        pre = 1
 7        i = 0
 8
 9        while nums[i] != 1:
10            i += 1
11
12        while i < len(nums):
13            if nums[i] == 1:
14                ans *= pre
15                ans %= (10**9 + 7)
16                pre = 1
17            else:
18                pre += 1
19            i += 1
20        return ans

  • Golang

     1func numberOfGoodSubarraySplits(nums []int) int {
 2    i := 0
 3    n := len(nums)
 4
 5    for i < n && nums[i] == 0 {
 6        i++
 7    }
 8
 9    if i == n {
10        return 0
11    }
12
13    ans := 1
14    pre := 1
15    for i < n {
16        if nums[i] == 1 {
17            ans *= pre
18            pre = 1
19            ans %= 1e9  + 7
20        }else{
21            pre ++
22        }
23        i++
24    }
25    return ans
26}

四 机器人碰撞

  • 栈 排序

  • Python

     1class Solution:
 2    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
 3        stack = []
 4        n = len(positions)
 5        robots = [[positions[i], healths[i], directions[i], i] for i in range(n)]
 6        robots.sort(key=lambda x: x[0])
 7
 8        for i in range(n):
 9            if robots[i][2] == "L":
10                while stack and stack[-1][0] == "R" and stack[-1][1] < robots[i][1]:
11                    stack.pop()
12                    robots[i][1] -= 1
13                if stack and stack[-1][0] == "R":
14                    if stack[-1][1] > robots[i][1]:
15                        stack[-1][1] -= 1
16                    elif stack[-1][1] == robots[i][1]:
17                        stack.pop()
18                else:
19                    stack.append([robots[i][2], robots[i][1], robots[i][3]])
20            else:
21                stack.append([robots[i][2], robots[i][1], robots[i][3]])
22
23        stack.sort(key=lambda x: x[2])
24
25        return [stack[i][1] for i in range(len(stack))]

  • Golang

     1func survivedRobotsHealths(positions []int, healths []int, directions string) []int {
 2    n := len(positions)
 3
 4    type robot struct {
 5        p   int
 6        h   int
 7        d   byte
 8        idx int
 9    }
10
11    robots := make([]robot, n)
12
13    for i := 0; i < n; i++ {
14        robots[i] = robot{positions[i], healths[i], directions[i], i}
15    }
16
17    sort.Slice(robots, func(i, j int) bool {
18        return robots[i].p < robots[j].p
19    })
20
21    stack := make([]robot, 0)
22
23    for i := 0; i < n; i++ {
24        if robots[i].d == 'L' {
25            for len(stack) > 0 && stack[len(stack)-1].d == 'R' && stack[len(stack)-1].h < robots[i].h {
26                stack = stack[:len(stack)-1]
27                robots[i].h--
28            }
29            if len(stack) > 0 && stack[len(stack)-1].d == 'R' {
30                if stack[len(stack)-1].h > robots[i].h {
31                    stack[len(stack)-1].h--
32                } else {
33                    stack = stack[:len(stack)-1]
34                }
35            } else {
36                stack = append(stack, robots[i])
37            }
38        } else {
39            stack = append(stack, robots[i])
40        }
41    }
42
43    ans := make([]int, 0)
44    sort.Slice(stack, func(i, j int) bool {
45        return stack[i].idx < stack[j].idx
46    })
47
48    for i := 0; i < len(stack); i++ {
49        ans = append(ans, stack[i].h)
50    }
51
52    return ans
53}