Onehr7

一 美麗下標對的數目#

• 模擬 GCD

• Python

  Copy

  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

  Copy

  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

  Copy

  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

  Copy

  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

  Copy

  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

  Copy

  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

  Copy

  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

  Copy

  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
  }