一 美しいペアの数#
-
シミュレーションGCD -
Python
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
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 を 2 つ組み合わせることができるため、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 += 1 -
Golang
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 ans -
Golang
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 }