数学等比数列优化
思路：
把他当成高中数学等比数列题目，一下子就简单起来了！！
可以分得桃子数量， 剩余的桃子数量
第一个小猴子，( 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 <iostream> #include <string> #include <cmath> 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<int> numbers) { unordered_map<int,int> 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<int> numbers) { sort(numbers.begin(),numbers.end()); return numbers[numbers.size()/2]; } };
方法三：
目标条件：
目标数据超过数组长度的一半，那么对数组，我们同时去掉两个不同的数字，到最后剩下的一个数就是该数字。
如果剩下两个，那么这两个也是一样的，就是结果 ，在其基础上把最后剩下的一个数字或者两个回到原来数组中， 将数组遍历一遍统计一下数字出现次数进行最终判断。
class Solution { public: int MoreThanHalfNum_Solution(vector<int> 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; } };
