题目 #

You are given two 0-indexed integer arrays nums and divisors.

The divisibility score of divisors[i] is the number of indices j such that nums[j] is divisible by divisors[i].

Return the integer divisors[i] with the maximum divisibility score. If there is more than one integer with the maximum score, return the minimum of them.

Example 1:

Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 5.
The divisibility score of divisors[1] is 1 since nums[0] is divisible by 2.
The divisibility score of divisors[2] is 3 since nums[2], nums[3], and nums[4] are divisible by 3.
Since divisors[2] has the maximum divisibility score, we return it.

Example 2:

Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 2 since nums[0] and nums[3] are divisible by 5.
The divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 7.
The divisibility score of divisors[2] is 2 since nums[0] and nums[3] are divisible by 5.
Since divisors[0], divisors[1], and divisors[2] all have the maximum divisibility score, we return the minimum of them (i.e., divisors[2]).

Example 3:

Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 10.
The divisibility score of divisors[1] is 0 since no number in nums is divisible by 16.
Since divisors[0] and divisors[1] both have the maximum divisibility score, we return the minimum of them (i.e., divisors[0]).

Constraints:

• 1 <= nums.length, divisors.length <= 1000
• $1 <= nums[i], divisors[i] <= 10^9$

思路1 状态机 #

分析 #

• 因为是周期性，所以状态机直接统计

代码 #

 1func addMinimum(word string) int {
 2	res := 0
 3	state := 0
 4	for i := 0; i < len(word); i++ {
 5		v := word[i]
 6		switch state {
 7		case 0:
 8			if v != 'a' {
 9				res++
10				i--
11			}
12			state = 1
13		case 1:
14			if v != 'b' {
15				res++
16				i--
17			}
18			state = 2
19		case 2:
20			if v != 'c' {
21				res++
22				i--
23			}
24			state = 0
25		}
26	}
27	if state != 0 {
28		res += 3 - state
29	}
30	return res
31}

思路2 分组 #

分析 #

• 统计分组，一组的一定后一个大于前一个

代码 #

1func addMinimum1(word string) int {
2	t := 1
3	for i := 1; i < len(word); i++ {
4		if word[i] <= word[i-1] {
5			t++
6		}
7	}
8	return 3*t - len(word)
9}