一 美丽下标对的数目
模拟GCDPython
class Solution: def countBeautifulPairs(self, nums: List[int]) -> int: n = len(nums) ans = 0 for i in range(n): first = nums[i] while first >= 10: first //= 10 for j in range(i+1, n): last = nums[j] % 10 if gcd(first, last) == 1: ans += 1 return ans
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
- Golang
```go
func countBeautifulPairs(nums []int) (ans int) {
n := len(nums)
for i := 0; i < n; i++ {
first := nums[i]
for first >= 10 {
first /= 10
}
for j := i + 1; j < n; j++ {
last := nums[j] % 10
if gcd(first, last) == 1{
ans++
}
}
}
return ans
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}[二 得到整数零需要执行的最少操作数]
枚举从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
class Solution: def makeTheIntegerZero(self, num1: int, num2: int) -> int: k = 1 while True: x = num1 - k * num2 if x < k: return -1 if k >= x.bit_count(): return k k += 1Golang
func makeTheIntegerZero(num1 int, num2 int) int { k := 1 for { x := num1 - num2*k if x < k { return -1 } if k >= bitCount(x) { return k } k++ } } func bitCount(a int) (c int) { for a != 0 { if a%2 != 0 { c++ } a /= 2 } return }
[三 将数组划分成若干好子数组的方式]
数学Python
class Solution: def numberOfGoodSubarraySplits(self, nums: List[int]) -> int: if sum(nums) == 0: return 0 ans = 1 pre = 1 i = 0 while nums[i] != 1: i += 1 while i < len(nums): if nums[i] == 1: ans *= pre ans %= (10**9 + 7) pre = 1 else: pre += 1 i += 1 return ansGolang
func numberOfGoodSubarraySplits(nums []int) int { i := 0 n := len(nums) for i < n && nums[i] == 0 { i++ } if i == n { return 0 } ans := 1 pre := 1 for i < n { if nums[i] == 1 { ans *= pre pre = 1 ans %= 1e9 + 7 }else{ pre ++ } i++ } return ans }
四 机器人碰撞
栈排序Python
class Solution: def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]: stack = [] n = len(positions) robots = [[positions[i], healths[i], directions[i], i] for i in range(n)] robots.sort(key=lambda x: x[0]) for i in range(n): if robots[i][2] == "L": while stack and stack[-1][0] == "R" and stack[-1][1] < robots[i][1]: stack.pop() robots[i][1] -= 1 if stack and stack[-1][0] == "R": if stack[-1][1] > robots[i][1]: stack[-1][1] -= 1 elif stack[-1][1] == robots[i][1]: stack.pop() else: stack.append([robots[i][2], robots[i][1], robots[i][3]]) else: stack.append([robots[i][2], robots[i][1], robots[i][3]]) stack.sort(key=lambda x: x[2]) return [stack[i][1] for i in range(len(stack))]Golang
func survivedRobotsHealths(positions []int, healths []int, directions string) []int { n := len(positions) type robot struct { p int h int d byte idx int } robots := make([]robot, n) for i := 0; i < n; i++ { robots[i] = robot{positions[i], healths[i], directions[i], i} } sort.Slice(robots, func(i, j int) bool { return robots[i].p < robots[j].p }) stack := make([]robot, 0) for i := 0; i < n; i++ { if robots[i].d == 'L' { for len(stack) > 0 && stack[len(stack)-1].d == 'R' && stack[len(stack)-1].h < robots[i].h { stack = stack[:len(stack)-1] robots[i].h-- } if len(stack) > 0 && stack[len(stack)-1].d == 'R' { if stack[len(stack)-1].h > robots[i].h { stack[len(stack)-1].h-- } else { stack = stack[:len(stack)-1] } } else { stack = append(stack, robots[i]) } } else { stack = append(stack, robots[i]) } } ans := make([]int, 0) sort.Slice(stack, func(i, j int) bool { return stack[i].idx < stack[j].idx }) for i := 0; i < len(stack); i++ { ans = append(ans, stack[i].h) } return ans }