题目 #
You are given a 0-indexed integer array nums of length n.
You can perform the following operation as many times as you want:
- Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].
Return true if you can make nums a strictly increasing array using the above operation and false otherwise.
A strictly increasing array is an array whose each element is strictly greater than its preceding element.
Example 1:
Input: nums = [4,9,6,10]
Output: true
Explanation: In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums[0], so that nums becomes [1,9,6,10].
In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums becomes equal to [1,2,6,10].
After the second operation, nums is sorted in strictly increasing order, so the answer is true.
Example 2:
Input: nums = [6,8,11,12]
Output: true
Explanation: Initially nums is sorted in strictly increasing order, so we don't need to make any operations.
Example 3:
Input: nums = [5,8,3]
Output: false
Explanation: It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.
Constraints:
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 1000
- nums.length == n
思路1 筛质数+二分 #
分析 #
- 1000以内的质数全部先找出来
- 每个数都尽可能小就好了，那么就是找质数里面小于当前到前一个差值的最大的那个
代码 #
1func oulerPrimes(mx int, primes *[]int) {
2 flag := make([]bool, mx+1) // 标记数有没有被筛掉，false就是没有
3 for i := 2; i < mx+1; i++ {
4 if !flag[i] {
5 // 数没有被比自己小的数筛掉，就代表是质数
6 *primes = append(*primes, i)
7 }
8 for _, v := range *primes {
9 if i*v > mx {
10 break
11 }
12 // 每一个数都作为因子乘以比自己小的素数筛掉后面的数
13 flag[i*v] = true
14 if i%v == 0 {
15 // 减少时间复杂度的关键算法
16 // 12 = 2 * 3 * 2，i = 4时，只排了8就退出了，因为6会将12排除
17 // 也就是，假设v可以整除i即i = kv，有某个数为x = mi = kmv
18 // 那么存在一个数 i < km < x可以把x排掉，用i乘以所有的质数去排除就没什么意义了，提前退出减少时间复杂度
19 break
20 }
21 }
22 }
23}
24
25var primes []int = make([]int, 0, 168)
26
27func init() {
28 oulerPrimes(1000, &primes)
29}
30
31func primeSubOperation1(nums []int) bool {
32 pre := 0
33 for _, v := range nums {
34 // 每个数都尽可能小
35 if v <= pre {
36 return false
37 }
38 // 找到能尽可能接近pre的最大质数，反过来就是找v-pre之间的最大质数
39 i := sort.SearchInts(primes, v-pre) - 1
40 if i < 0 {
41 pre = v
42 } else {
43 pre = v - primes[i]
44 }
45 }
46 return true
47}
思路2 倒着做 #
分析 #
- 和上面一样，只是上面不好理解，倒着好理解，没上面写的快
- 尽可能让每一个数减去质数后小于但最接近后一个
代码 #
1func oulerPrimes(mx int, primes *[]int) {
2 flag := make([]bool, mx+1) // 标记数有没有被筛掉，false就是没有
3 for i := 2; i < mx+1; i++ {
4 if !flag[i] {
5 // 数没有被比自己小的数筛掉，就代表是质数
6 *primes = append(*primes, i)
7 }
8 for _, v := range *primes {
9 if i*v > mx {
10 break
11 }
12 // 每一个数都作为因子乘以比自己小的素数筛掉后面的数
13 flag[i*v] = true
14 if i%v == 0 {
15 // 减少时间复杂度的关键算法
16 // 12 = 2 * 3 * 2，i = 4时，只排了8就退出了，因为6会将12排除
17 // 也就是，假设v可以整除i即i = kv，有某个数为x = mi = kmv
18 // 那么存在一个数 i < km < x可以把x排掉，用i乘以所有的质数去排除就没什么意义了，提前退出减少时间复杂度
19 break
20 }
21 }
22 }
23}
24
25var primes []int = make([]int, 0, 168)
26
27func init() {
28 oulerPrimes(1000, &primes)
29}
30
31func primeSubOperation(nums []int) bool {
32 n := len(nums)
33 last := nums[n-1]
34 for i := n - 2; i >= 0; i-- {
35 v := nums[i]
36 if v < last {
37 last = v
38 continue
39 }
40 for _, vp := range primes {
41 if vp >= v {
42 return false
43 }
44 if v-vp < last {
45 v -= vp
46 break
47 }
48 }
49 if v >= last {
50 return false
51 }
52 last = v
53 continue
54 }
55 return true
56}