A. 存在连续三个奇数的数组
给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
class Solution {
public:
bool threeConsecutiveOdds(vector<int>& arr) {
int a = 0,b = 1,c = 2;
while(c < arr.size()){
if((arr[a]&1)&&(arr[b]&1)&&(arr[c]&1)) return true;
a++;b++;c++;
}
return false;
}
};
B. 使数组中所有元素相等的最小操作数
存在一个长度为 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 中所有元素相等所需的 最小操作数 。
class Solution {
public:
int minOperations(int n) {
int ans = 0;
for(int i = 0;i <=(n-1)/2;i++){
ans += (n - 2*i -1);
}
return ans;
}
};
C. 两球之间的磁力
在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
思路:
二分答案
class Solution {
public:
bool judge(int k,vector<int>& p,int m){
int n = p.size();
int now = p[0];
int cnt = 1;
auto x = p.begin();
while(cnt < m){
x = lower_bound(x,p.end(),now+k);
if(x == p.end())return false;
now = *x;
cnt++;
}
return true;
}
int maxDistance(vector<int>& position, int m) {
sort(position.begin(),position.end());
int l = 1,r = position[position.size()-1] - position[0];
int ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(judge(mid,position,m)){
l = mid + 1;
ans = max(ans,mid);
}
else{
r = mid - 1;
}
}
return ans;
}
};
D. 吃掉N个橘子的最少天数
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
- 吃掉一个橘子。
- 如果剩余橘子数
n能被2整除，那么你可以吃掉n/2个橘子。 - 如果剩余橘子数
n能被3整除，那么你可以吃掉2*(n/3)个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
1 <= n <= 2*10^9
思路：
记忆化搜索，复杂度并不会到2e9，因为不需要一直减1。
class Solution {
public:
map<int,int>ans;
int solve(int n){
if(ans.count(n) != 0)return ans[n];
if(n == 1)return ans[1] = 1;
if(n % 2 == 0 && n % 3 == 0){
return ans[n] = min(solve(n/2),solve(n/3)) + 1;
}
if(n % 2 == 0 && n % 3 != 0){
return ans[n] = min(solve(n/2),solve(n-1)) + 1;
}
if(n % 2 != 0 && n % 3 == 0){
return ans[n] = min(solve(n-1),solve(n/3)) + 1;
}
return ans[n] = solve(n-1) + 1;
}
int minDays(int n) {
return solve(n);
}
};