牛客竞赛每日俩题 - Day6

目录

数学等比数列优化

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

---

数学等比数列优化

猴子分桃__牛客网

思路：

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

                        可以分得桃子数量，                 剩余的桃子数量
第一个小猴子，( 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<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;
    }
};