367 LeetCode周赛

找出满足差值条件的下标 I

• 同 找出满足差值条件的下标 II

最短且字典序最小的美丽子字符串

• 滑动窗口

• Python

  class Solution:
      def shortestBeautifulSubstring(self, s: str, k: int) -> str:
          count = 0
          for ch in s:
              if ch == "1":
                  count += 1
          if count < k:
              return ""
  
          ans = s
          count = 0
          l = 0
          for r, ch in enumerate(s):   # O(N)
              if ch == "1":
                  count += 1
  
              while count > k or s[l] == "0":
                  if s[l] == "1":
                      count -= 1
                  l += 1
  
              if count == k:
                  cur = s[l:r+1]
                  if len(cur) < len(ans) or len(cur) == len(ans) and cur < ans:  # O(N)
                      ans = cur
          return ans 

• Go

  func shortestBeautifulSubstring(s string, k int) string {
      cnt := 0
      for _, ch := range s {
          if ch == '1' {
              cnt++
          }
      }
      if cnt < k &#123;
          return ""
      &#125;
  
      l := 0
      ans := s
      cnt = 0
      for r, ch := range s &#123;
          if ch == '1' &#123;
              cnt++
          &#125;
  
          for cnt > k || s[l] == '0' &#123;
              if s[l] == '1' &#123;
                  cnt--
              &#125;
              l++
          &#125;
  
          if cnt == k &#123;
              cur := s[l : r+1]
              if len(cur) < len(ans) || (len(cur) == len(ans) && cur < ans) &#123;
                  ans = cur
              &#125;
          &#125;
      &#125;
      return ans
  &#125;
  

找出满足差值条件的下标 II

• 枚举

  枚举 下标 j前indexDifference 的出现的最大值和最小值。

• Python

  class Solution:
      def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
          max_idx, min_idx = 0, 0
  
          for j in range(indexDifference, len(nums)):
              i = j - indexDifference
  
              if nums[i] > nums[max_idx]:
                  max_idx = i
              elif nums[i] < nums[min_idx]:
                  min_idx = i
  
              if nums[max_idx] - nums[j] >= valueDifference:
                  return [max_idx, j]
  
              if nums[j] - nums[min_idx] >= valueDifference:
                  return [min_idx, j]
  
          return [-1, -1]

• Go

  func findIndices(nums []int, indexDifference int, valueDifference int) []int {
      minIdx, maxIdx := 0, 0
  
      for j := indexDifference; j < len(nums); j++ &#123;
          i := j - indexDifference
          if nums[i] < nums[minIdx] &#123;
              minIdx = i
          &#125; else if nums[i] > nums[maxIdx] &#123;
              maxIdx = i
          &#125;
  
          if nums[j]-nums[minIdx] >= valueDifference &#123;
              return []int&#123;j, minIdx&#125;
          &#125;
  
          if nums[maxIdx]-nums[j] >= valueDifference &#123;
              return []int&#123;j, maxIdx&#125;
          &#125;
      &#125;
      return []int&#123;-1, -1&#125;
  &#125;
  

构造乘积矩阵

• 前后缀分解

  同 238 除自身以外数组的乘积

• Python

  class Solution:
      def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
          m, n = len(grid), len(grid[0])
          p = [[0] * n for _ in range(m)]
          MOD = 12345
  
          aft = 1
          for i in range(m-1, -1, -1):
              for j in range(n-1, -1, -1):
                  p[i][j] = aft
                  aft = aft * grid[i][j] % MOD
  
          pre = 1
          for i in range(m):
              for j in range(n):
                  p[i][j] = p[i][j] * pre % MOD
                  pre = pre * grid[i][j] % MOD
  
          return p

• Go

  func constructProductMatrix(grid [][]int) [][]int {
      const mod = 12345
      m, n := len(grid), len(grid[0])
      p := make([][]int, m)
      for i := 0; i < m; i++ &#123;
          p[i] = make([]int, n)
      &#125;
  
      aft := 1
      for i := m - 1; i >= 0; i-- &#123;
          for j := n - 1; j >= 0; j-- &#123;
              p[i][j] = aft
              aft = (aft * grid[i][j]) % mod
          &#125;
      &#125;
  
      pre := 1
  
      for i := 0; i < m; i++ &#123;
          for j := 0; j < n; j++ &#123;
              p[i][j] = (p[i][j] * pre) % mod
              pre = (pre * grid[i][j]) % mod
          &#125;
      &#125;
  
      return p
  &#125;