第一题：存在连续三个奇数的数组
给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false。
示例：
输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。
分析
直接写一个判断就解决了。
代码
Python
class Solution:
def threeConsecutiveOdds(self, arr: List[int]) -> bool:
count = 0
for n in arr:
if not n % 2:
count = 0
elif count == 2:
return True
else:
count += 1
return False
C++
class Solution {
public:
bool threeConsecutiveOdds(vector<int>& arr) {
int count = 0;
for (int n = 0; n < arr.size(); ++n) {
if (!(arr[n] % 2)){
count = 0;
}
else if (count == 2){
return true;
}
else{
count += 1;
}
}
return false;
}
};
第二题：使数组中所有元素相等的最小操作数
存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。
一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都相等。题目测试用例将会保证：在执行若干步操作后，数组中的所有元素最终可以全部相等。
给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的最小操作数。
示例：
输入：n = 3
输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]
分析
这一道题实质上是一道找规律题。这一个 +1 和 -1 的操作实际上可以看做是把 1 从一个数移到另一个数，最后达到数列整体的一个平衡；因为这个数列是一个等差数列，所以规律性十分明显，即：
n 为奇数：$count = 2 + 4 + 6 + \cdots + [2\times(\lfloor n/2\rfloor + 1)]$
n 为偶数：$count = 1 + 3 + 5 + 7 + \cdots + [(2\times\lfloor n/2\rfloor) + 1]$
当然，这个还遵从一个更简单的规律（我在 LeetCode 讨论区看到的），即移动的次数等于 $\frac{n^2}{4}$。当时看到了这个答案，我突然就明白了和大佬之间的差距，他们总能够在规律中找到更简单的规律。
代码
Python
class Solution:
def minOperations(self, n: int) -> int:
temp = 0
if n % 2:
for i in range(n // 2):
temp += 2 * (i + 1)
else:
for i in range(n // 2):
temp += (2 * i) + 1
return temp
C++
class Solution {
public:
int minOperations(int n) {
int temp = 0;
if (n % 2){
for(int i = 0; i < n / 2; ++i){
temp += 2 * (i + 1);
}
}
else{
for(int i = 0; i < n / 2; ++i){
temp += (2 * i) + 1;
}
}
return temp;
}
};
第三题：两球之间的磁力
在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间最小磁力最大。
已知两个球如果分别位于 x 和 y，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
示例：
输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。
分析
这一道题我一开始想使用 DP 去求解，但是发现貌似行不通，所以最后用的是二分查找法 AC 的。
首先需要排序，然后取出左右两端，即为位置的最大值和最小值；为了判断满不满足条件，所以有个额外的 check 函数来进行检查。
check 函数的原理是这样的：因为有 m 个球，所以最小值的临界状况就是平均分布，即有 m - 1 个间隔。从最小的值开始进行遍历，然后计算每一个篮子到第一个篮子的距离，如果大于传入 check 的参数，则 count++；最后如果 count >= m - 1，则证明这个距离比平均距离要小，所以就去大一些的地方看看能不能满足条件（能不能逼近），反之就到小一点的地方判断。
代码
Python
class Solution:
def maxDistance(self, position: List[int], m: int) -> int:
position.sort()
def check(x):
cnt = 1
t = position[0]
for i in range(1, len(position)):
if position[i] - t > x:
cnt += 1
t = position[i]
return cnt >= m
l, r = 0, position[-1]
while l < r:
mid = (l + r) // 2
if check(mid):
l = mid + 1
else:
r = mid
return l
C++
class Solution {
public:
bool check(int x, vector<int>& a, int m) {
int cnt = 0;
int target = a[0] + x;
for(int i = 0; i < a.size() - 1; i++) {
if(a[i] < target && a[i + 1] >= target) {
cnt++;
target = a[i + 1] + x;
}
}
return cnt >= m - 1;
}
int maxDistance(vector<int>& a, int m) {
sort(a.begin(), a.end());
int len = a.size();
int diff = a[len - 1] - a[0]; // 最大间隔
int mn = INT_MAX; // 记录最小间隔
for(int i = 0; i < len - 1; i++) {
if(mn > a[i + 1] - a[i]) {
mn = a[i + 1] - a[i];
}
}
if(m == 2) { // 这里特判了m = 2的情况，也可以归到底下的代码中。
return diff;
} else {
int l = mn, r = diff / (m - 1); // 确定左右边界
while(l <= r) { // 二分搜索
int mid = (l + r) / 2;
if(check(mid, a, m)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l - 1;
}
}
};
第四题：吃掉 N 个橘子的最少天数
分析
这一道题是一个递归题，直接用 dfs 递推就行了。但是我做题时，这其中有一个门道需要注意，就是下面的这一行代码：
min(self.minDays(n // 2) + n % 2, self.minDays(n // 3) + n % 3)
这是最主要的一个逻辑，注意两个参数后面的 + n % 2 和 + n % 3，我一开始因为没有加上这个最后出错了。这里的意思就是越早整除吃越好，如果不能整除，那立刻吃几个到可以整除，再整除吃；因为基数大，整除吃掉的也多。
后面这段就是立刻吃到可以整除要花的次数，从而可以更贪心一些，吃的次数更少。
代码
Python
class Solution:
@lru_cache(None)
def minDays(self, n: int) -> int:
if n <= 2: return n
return 1 + min(self.minDays(n // 2) + n % 2, self.minDays(n // 3) + n % 3)
C++
class Solution {
public:
unordered_map<int, int> mark;
int f(int n) {
if(n <= 1) {
return n;
}
auto it = mark.find(n);
if(it != mark.end()) {
return it->second;
}
return mark[n] = min(f(n/2) + n%2, f(n/3) + n%3) + 1;
}
int minDays(int n) {
return f(n);
}
};