数学等比数列优化

猴子分桃__牛客网

思路：

把他当成高中数学等比数列题目，一下子就简单起来了！！

                        可以分得桃子数量，                 剩余的桃子数量
第一个小猴子，( x -1) *1/5                           ( x-1) * 4/5 = 4/5x - 4/5
第二个小猴子，((x - 1)*4/5-1)*1/5                ( 4/5x - 4/5-1)*4/5 = (4/5)^2* x- (4/5)^2- 4/5
第三个小猴子，(( 4/5x - 4/5-1)*4/5-1)*1/5    ((4/5)^2* x-(4/5)^2-4/5 -1)*4/5=(4/5)^3* x- (4/5)^3 - (4/5)^2 - 4/5

于是我们可以推出分给第n个猴子后剩下：

((4/5)^n *x - ((4/5)^n +(4/5)^n-1 + ...+(4/5)^1 ) )

令s = (4/5)^n +(4/5)^n-1 + ...+(4/5)^1,使用等比数列前n项和公式

得

s = 4*(1 - 4/5^n)
所以(4/5)^n * x - 4* (1 - 4/5^n) ---->   4^n / 5^n*(x +4) - 4（剩下）
(x＋4)是5^n的倍数，最小的情况∶(x+4) = 5^n
即x = 5^n - 4时取剩下最小值4^n-4

 数学优化O(1)复杂度！！

#include 
#include 
#include 
using namespace std;
int main()
{int n;while(cin >> n) {if (n == 0) break;long total = pow(5, n) - 4;long left = pow(4, n) + n - 4;cout << total << " " << left << endl;}return 0;
}

简单哈希/sort妙用/抵消法

数组中出现次数超过一半的数字_牛客题霸_牛客网

方法一：

简单哈希；如果哈希表里有则加一，无则加入新表

class Solution {
public:int MoreThanHalfNum_Solution(vector numbers) {unordered_map map;int half=numbers.size()/2;for(auto e:numbers){if(map.count(e)) map[e]++;else map.insert(make_pair(e,1));if(map[e]>half) return e;}return 0;}
};

 方法二：

利用sort性质

class Solution {
public:int MoreThanHalfNum_Solution(vector numbers) {sort(numbers.begin(),numbers.end());return numbers[numbers.size()/2];}
};

方法三：

目标数据超过数组长度的一半，那么对数组，我们同时去掉两个不同的数字，到最后剩下的一个数就是该数字。 如果剩下两个，那么这两个也是一样的，就是结果，在其基础上把最后剩下的一个数字或者两个回到原来数组中， 将数组遍历一遍统计一下数字出现次数进行最终判断。

class Solution {public:int MoreThanHalfNum_Solution(vector numbers) {if (numbers.size() == 0) {return 0;}
//重点写一下//可以采取不同的数量进行抵消的思路int number = numbers[0];int times = 1;for (int i = 1; i < numbers.size(); i++) {if (times == 0) { //如果当前times是0，说明之前的不同抵消完了number = numbers[i];times = 1;} else if (numbers[i] == number) times++;else times--;}
//如果输入本身满足条件，则times一定>0, 并且number保存的就是准目标，但是还需要确认int count = 0;for (int i = 0; i < numbers.size(); i++) {if (numbers[i] == number) {count++;}}return count > numbers.size() / 2 ? number : 0;}
};