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

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

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

  • 滑动窗口

  • Python

     1class Solution:
 2    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
 3        count = 0
 4        for ch in s:
 5            if ch == "1":
 6                count += 1
 7        if count < k:
 8            return ""
 9
10        ans = s
11        count = 0
12        l = 0
13        for r, ch in enumerate(s):   # O(N)
14            if ch == "1":
15                count += 1
16
17            while count > k or s[l] == "0":
18                if s[l] == "1":
19                    count -= 1
20                l += 1
21
22            if count == k:
23                cur = s[l:r+1]
24                if len(cur) < len(ans) or len(cur) == len(ans) and cur < ans:  # O(N)
25                    ans = cur
26        return ans

  • Go

     1func shortestBeautifulSubstring(s string, k int) string {
 2	cnt := 0
 3	for _, ch := range s {
 4		if ch == '1' {
 5			cnt++
 6		}
 7	}
 8	if cnt < k {
 9		return ""
10	}
11
12	l := 0
13	ans := s
14	cnt = 0
15	for r, ch := range s {
16		if ch == '1' {
17			cnt++
18		}
19
20		for cnt > k || s[l] == '0' {
21			if s[l] == '1' {
22				cnt--
23			}
24			l++
25		}
26
27		if cnt == k {
28			cur := s[l : r+1]
29			if len(cur) < len(ans) || (len(cur) == len(ans) && cur < ans) {
30				ans = cur
31			}
32		}
33	}
34	return ans
35}

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

  • 枚举

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

  • Python

     1class Solution:
 2    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
 3        max_idx, min_idx = 0, 0
 4
 5        for j in range(indexDifference, len(nums)):
 6            i = j - indexDifference
 7
 8            if nums[i] > nums[max_idx]:
 9                max_idx = i
10            elif nums[i] < nums[min_idx]:
11                min_idx = i
12
13            if nums[max_idx] - nums[j] >= valueDifference:
14                return [max_idx, j]
15
16            if nums[j] - nums[min_idx] >= valueDifference:
17                return [min_idx, j]
18
19        return [-1, -1]

  • Go

     1func findIndices(nums []int, indexDifference int, valueDifference int) []int {
 2	minIdx, maxIdx := 0, 0
 3
 4	for j := indexDifference; j < len(nums); j++ {
 5		i := j - indexDifference
 6		if nums[i] < nums[minIdx] {
 7			minIdx = i
 8		} else if nums[i] > nums[maxIdx] {
 9			maxIdx = i
10		}
11
12		if nums[j]-nums[minIdx] >= valueDifference {
13			return []int{j, minIdx}
14		}
15
16		if nums[maxIdx]-nums[j] >= valueDifference {
17			return []int{j, maxIdx}
18		}
19	}
20	return []int{-1, -1}
21}

构造乘积矩阵

  • 前后缀分解

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

  • Python

     1class Solution:
 2    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
 3        m, n = len(grid), len(grid[0])
 4        p = [[0] * n for _ in range(m)]
 5        MOD = 12345
 6
 7        aft = 1
 8        for i in range(m-1, -1, -1):
 9            for j in range(n-1, -1, -1):
10                p[i][j] = aft
11                aft = aft * grid[i][j] % MOD
12
13        pre = 1
14        for i in range(m):
15            for j in range(n):
16                p[i][j] = p[i][j] * pre % MOD
17                pre = pre * grid[i][j] % MOD
18
19        return p

  • Go

     1func constructProductMatrix(grid [][]int) [][]int {
 2	const mod = 12345
 3	m, n := len(grid), len(grid[0])
 4	p := make([][]int, m)
 5	for i := 0; i < m; i++ {
 6		p[i] = make([]int, n)
 7	}
 8
 9	aft := 1
10	for i := m - 1; i >= 0; i-- {
11		for j := n - 1; j >= 0; j-- {
12			p[i][j] = aft
13			aft = (aft * grid[i][j]) % mod
14		}
15	}
16
17	pre := 1
18
19	for i := 0; i < m; i++ {
20		for j := 0; j < n; j++ {
21			p[i][j] = (p[i][j] * pre) % mod
22			pre = (pre * grid[i][j]) % mod
23		}
24	}
25
26	return p
27}