【leetcode458】【规律题】【突破性思维】可怜的小猪

【leetcode458】【规律题】【突破性思维】可怜的小猪

先看一个题

题目

有1000只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在15分钟内死去。

问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?

回答这个问题,并为下列的进阶问题编写一个通用算法。

进阶:

假设有 n 只水桶,猪饮水中毒后会在 m 分钟内死亡,你需要多少猪(x)就能在 p 分钟内找出“有毒”水桶?n只水桶里有且仅有一只有毒的桶。

分析

可怜的小猪,被拿去做实验了。

先看1只小猪,60分钟的话,它最多可以判断出 60/15+1 = 5只水桶中的毒药桶。每隔十五分钟喝一次水,喝四次,如果幸运的话活了下来,就是最后一桶。

再接着看2只小猪,60分钟,它最后可以判断出25只水桶,可以这样:

00     01     02     03      04

10     11     12     13      14

20     21     22     23      24

30     31     32     33      34

40     41     42     43      44

将桶像上面摆放,第一只猪猪喝掉第一二三四五混合后的水,每隔15分钟喝一次,这样如果不幸运,在x行被毒死了,则证明毒药在第x行,幸运活下来的话,则毒药在第五行;在第一只猪猪和的同时让第二只猪猪喝第一二三四列混合后的水,如果在y列被毒死,则毒药在第y列,如果活下来,则毒药在第五列。这样第一只猪猪判断出了横坐标x,第二只猪猪判断出来纵坐标y,则可以知道哪桶水有毒。

以此类推,1只小猪5^1,  2只小猪5^2,  3只小猪5^3,  4只小猪5^4  ,5只小猪5^5……

java代码:

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        
        if(buckets == 1) return 0;
        
        int w = minutesToTest / minutesToDie + 1;
        int re = 1;
        while(Math.pow(w,re) < buckets)
            re ++;
        
        return re;
    }
}


引用 leetcode 458. 可怜的小猪 及 题目的不严谨

以下是原文

这道题很有意思,感觉是之前老鼠喝毒药的进阶版,增加了个时间属性,不错解法差不多,主要是看看在测试时间内,有多少批猪死亡,例如:60分钟内,死亡时间为15,则增加了4个状态,则变成了5个状态,所以就要对log(1000) / log(5)上取整,有这么多头猪就可以了。

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        if(minutesToTest < minutesToDie)
            return 0;
        return ceil(log(buckets) / log(floor(minutesToTest/minutesToDie) + 1));
    }

};

 

题目不严谨,有可能只需一只猪就可以判断1000个桶

为什么要规定每15分钟猪才能喝一次水?作为一只小猪猪难道不可以每一分钟喝水?

那么由5个状态就变成46个状态,我真是一个天才,哈哈

 

就如上图所示,其他人陷入思维误区,以为把60分钟分为4个15分钟,上图红色所示,我们16分钟那批猪如果检查出毒药了,那肯定是1分钟那批桶有问题,自查看1分钟那批桶的编号即可,依次类推,就可以增加了无数个时间状态,其实可以分成无数个15分钟,涉及到精度的问题,暂且规定1分钟为一批猪,则可以分成60-15个状态,即45个状态,和之前的那个二进制状态,一共46个状态。那么就是log(1000) / log(46) ,上取整,为2只猪。

如果你手速很快,猪可以一秒喝一口水的话,那就有45*60+1个状态,则需要1只猪就可以了。

原程序竞赛总目录

原程序竞赛总目录

SDAU暑假训练第七天休息日&第一周总结(201885)

SDAU暑假训练第七天休息日第一周总结(201885)

暑假集训第一周总结

 一周过去了,谈一下感受:

一.训练强度是真的大:

 这一点虽然老师早就给打了预防针,仍然没有预料到会这么大,6天完成两大章内容,虽然有高中的一点基础撑着,仍然是相当吃不消。到了后期虚到几乎就是在在集训室都能睡着的地步。不过学到的东西挺多的,虽然不如大佬们理解的深刻,但对我来说是不小的进步啦

二.身体是学习的基础:

 以前觉着学习和体力是分开的,再加上我喜欢思考东西不喜欢运动,所以身体素质差一点,本以为也不是什么大不了的事,我靠脑力照样能养活自己。集训了6天之后才发现,体力是脑力的物质基础,脑力是体力的上层建筑。做ACM的基本都会熬夜,别人熬一次夜只要第二天多睡一会就行了,但是我要好几天才能完全消除负面影响,这几天一直在熬夜,身体一直处于负面循环中,下学期除了学习也应该每周抽些时间锻炼身体。

三.比我优秀的人比我更努力:

 经历了六天的脑力风暴之后,迎来了宝贵的休息日,本来想就在宿舍放飞一下自我,后来大约10点还是忍不住去613了,五位比我优秀的大佬待在那里学习,然后就跟大佬们一起在那了一天,为自己先前的想法感到羞愧,本来这几天学的就没别人好,哪来的资本去玩?

四.学会自己找资料学习很重要

 数学一本通好多地方都很迷,有些地方干脆一笔带过,真是不愧对一本通的称呼,这个时候自己去网上找资料学习就很重要了,(这六天东西倒是没学着点,找东西的本领倒是提升了不少,哈哈)

五.睡觉!

简易图书馆借还书系统(核心部分)

简易图书馆借还书系统(核心部分)

【第一题】
源程序:
/*假设图书馆的图书包含书名、编号和作者属性,读者包含姓名和借书证号属性,每个读者最多可借5本书。设计一个类object,从它派生出图书类Book和读者类Reader,在Reader类中有一个
rentbook()成员函数用于借阅图书。主函数进行测试。说明:这是一个简单的借阅过程。借阅时,假设要借阅的图书是存在的。提示:
(1)在基类object中定义字符数组(或string类型)的name和整型数据no,这两个数据成员被Book类继承后,用于表示书名和编号,这两个数据成员被Reader类继承后,
用于表示读者姓名和借书证号;(2)Book类新增数据成员:作者(字符数组或string类型);Reader类新增数据成员:目前借书的数量(整型)、所借图书的信息
(可定义成Book类对象数组,Book rent[5]);(3)Reader类中的成员函数rentbook()的形参可以设置为Book类对象的引用,主函数中每调用一次rentbook(),表示借
阅一本书,所以rentbook()函数体代码:{rent[top]=b; top++;}。
*/

 

#include<iostream>
#include<string>
using namespace std;
class object
{
protected:
  string name;
  int no;
public:
	
	object(){}
	object(string ch,int a):name(ch),no(a)
	{}
};
class Book:public object
{
private:
   string author;
   public:
	 friend ostream &operator<<(ostream& out,Book &book)
	{
			out<<"书名:"<<book.name<<"\t编号:"<<book.no<<"\t作者:"<<book.author<<endl;
			return out;
	}
	 Book():object(){}
     Book(string ch,int a,string ch1):object(ch,a)
     { author=ch1;
	   ch="《"+ch;                                                                      
	   ch=ch+"》";
	  cout<<"恭喜您,借阅成功!\n该书信息为:"<<endl
		  <<"------------------------------------------\n"
		  <<"书名:"<<ch<<endl
		  <<"编号为:"<<a<<endl
		  <<"作者:"<<ch1<<endl
		  <<"------------------------------------------\n";
     }
};
class Reader:public object
{
	int num;
	Book rent[5];
	static int top;
public:
	Reader():object(),num(){}
    Reader(string ch,int a,int c):object(ch,a),num(c)
    {

      cout<<"读者为:"<<ch<<endl;
      cout<<"借书证号为:"<<a<<endl;
      cout<<"想要借书的数量为:"<<c<<endl;
      cout<<"请输入这"<<c<<"本书的书名、编号、作者:"<<endl;
    }
	void rentbook(Book &b)
	{
      this->rent[top]=b;
	  top++;
	}
	void show()
	{
		cout<<"读者目前持有的图书:\n"
			<<"------------------------------------------\n";
		for(int i=0;i<top;i++)
			cout<<this->rent[i];
		cout<<"------------------------------------------\n";

	}
};
int Reader::top=0;
int main()
{ 
	Reader database[10];
	int top=0;
	string a,c,key("123456"),keyin;
	char in_choose,system_choose='Y';
    int b,d;
	do{
		int Reader::top=0;
		printf("请输入您的姓名和借书证号:\n");
		cin>>a>>b;
	   printf("输入您的密码:(默认密码123456)\n");
	   while(1)
	   {
		   cin>>keyin;
		   if(key!=keyin) cout<<"密码错误,请重试"<<endl;
		   else 
		   {
			   cout<<"密码正确\n"<<endl;
			   break;
		   }
	   }
		cout<<"请输入想要借书的数量:"<<endl;
		cin>>d;
		Reader reader(a,b,d);
		database[top++]=reader;
		for(int i=0;i<d;i++)
		{
		   cout<<"请输入书名和编号和作者:"<<endl;
		   cin>>a>>b>>c;
		   Book temp(a,b,c);
		   reader.rentbook(temp);
		}
		 reader.show();
		 cout<<"--->下一个读者请按请按Y\n--->任意键退出系统\t"<<endl;
		 cin>>in_choose;
	}while (in_choose==system_choose);
	cout<<"系统已经退出!"<<endl;
    return 0;
}

 

 

运行结果:
请输入您的姓名和借书证号:
于衡 20175962
输入您的密码:(默认密码123456)
337
密码错误,请重试
123456
密码正确

请输入想要借书的数量:
2
读者为:于衡
借书证号为:20175962
想要借书的数量为:2
请输入这2本书的书名、编号、作者:
请输入书名和编号和作者:
活着 1 余华
恭喜您,借阅成功!
该书信息为:
——————————————
书名:《活着》
编号为:1
作者:余华
——————————————
请输入书名和编号和作者:
感性的蝴蝶 2 林清玄
恭喜您,借阅成功!
该书信息为:
——————————————
书名:《感性的蝴蝶》
编号为:2
作者:林清玄
——————————————
读者目前持有的图书:
——————————————
书名:活着       编号:1 作者:余华
书名:感性的蝴蝶 编号:2 作者:林清玄
——————————————
下一个读者请按请按Y
任意键退出系统
Y
请输入您的姓名和借书证号:
李雨 337
输入您的密码:(默认密码123456)
123456
密码正确

请输入想要借书的数量:
1
读者为:李雨
借书证号为:337
想要借书的数量为:1
请输入这1本书的书名、编号、作者:
请输入书名和编号和作者:
量子史话 4 曹天元
恭喜您,借阅成功!
该书信息为:
——————————————
书名:《量子史话》
编号为:4
作者:曹天元
——————————————
读者目前持有的图书:
——————————————
书名:量子史话   编号:4 作者:曹天元
——————————————
—>下一个读者请按请按Y
—>任意键退出系统
3
系统已经退出!

请按任意键继续. . .


 

【字符串处理】佩奇打字

【字符串处理】佩奇打字

佩奇打字

猪妈妈让佩奇练习打字她给了佩奇一篇只有小写字母的字符串S ( 1 <= |S| <= 105)。 但是佩奇记不住键盘字母的位置只能看着键盘一个一个打淘气的乔治趁佩奇不注意偷偷的换了键盘按键的位置乔治是这样操作的乔治每次扣下来两个键帽并且将这两个键帽互换位置重新安回去乔治越玩越起劲一直重复了m(1 <= m <= 105)请输出佩奇打完字后屏幕上显示的实际字符串

输入描述:

第一行输入一个字符串S ( 1 <= |S| <= 105);
第二行输入一个数字m(1 <= m <= 105)表示佩奇要操作m
之后有m每行有两个字母 c1, c2 表示佩奇要把这两个键帽互换位置

输出描述:

输出一行字符串即佩奇用乔治玩坏的键盘输出的实际字符串

#include<iostream>
#include<string>
using namespace std;
string paper;
int main()
{
	int letter[128];
	for(int i=int('a');i<=int('z');i++)
		letter[i]=i;
	cin>>paper;
	int m=0;
	cin>>m;
	for(int i=0;i<m;i++)
	{
		char a,b;
		cin>>a>>b;
		swap(letter[a],letter[b]);
	}
	for(int i=0;i<paper.length();i++)
	cout<<char(letter[paper[i]]);
	cout<<endl;
	return 0;
}

注意:

1.字符串本质为整数串

2.注意最后输出的时候的技巧

SDAU训练日志第一篇排序算法(上)(2018年1月29日)

SDAU训练日志第一篇排序算法(上)(2018年1月29日)

引例:

         经过了在山东农业大学一学期的学习,我们迎来了耿霞老师开设C++程序设计课程的期末考试,在程序设计题的第一题给我们出了一道这样的题:

((✺ω✺))给你一组数据(1<n<1000),数据中可能有重复,你的任务是完成去重,并按照从小到大顺序输出数据。(NOIP2006)

考试的时候拿到这个题有两个思路:

1.先去重再排序输出   2. 先排序再去重输出(重复的都在一起)

对于第一种思路,我们可以假设有很多桶,然后我们挨着枚举数据,把数据扔进带有编号的桶中,标记该桶,枚举完成后将带有标记的桶的编号进行输出。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000;
int main()
{
	bool flag[MAXN+1];
	//因为数组下标是少1的,我们多加一个元素表示maxn
	memset(flag,0,sizeof(flag));
	//初始化该桶
	int n=0,temp=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>temp;
		flag[temp]=true;
		//标记该桶
	}
	for(int i=1;i<=1000;i++)
		if(flag[i])
			cout<<i<<' ';
	return 0;
}

对于第二种思路:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int shuzu[101];
	memset(shuzu,0,sizeof(shuzu));
	int n=0;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>shuzu[i];
	sort(shuzu,shuzu+n);
	cout<<shuzu[0]<<' ';
	for(int i=1;i<n;i++)
	{
		if(shuzu[i]!=shuzu[i-1])//不重复就输出
			cout<<shuzu[i]<<' ';
	}
	return 0;
}

由第一种方法的代码稍加修改可以引出今天学习的第一种排序:简化版的桶排序

#include<iostream>
using namespace std;
const int MAXN=1000;
int main()
{
	int flag[MAXN+1];
	//因为数组下标是少1的,我们多加一个元素表示maxn
	memset(flag,0,sizeof(flag));
	//初始化该桶
	int n=0,temp=0;
	cin>>n;
	for(int i=1;i<=MAXN;i++)
	{
		cin>>temp;
		flag[temp]++;
	}
	for(int i=1;i<=MAXN;i++)
		for(int j=1;j<=flag[i];j++)//划重点
			cout<<i<<' ';
	return 0;
}

简化版桶排序的时间复杂度只有O(M+N),可以看出是一种很快的排序方法,然而却是不完美的,在应用过程中主要有以下几大问题:

  1. 只能对整数进行排序
  2. 以空间的方式纵使降低了时间复杂度,然而空间的浪费问题严重
  3. 无法处理有复杂要求的排序问题

对于第一个问题,别的排序算法能解决这个问题,就不多写了。谈一下第一个问题,假设要对五个数排序,每个数的范围在1-1亿之间,那么且不说系统会不会给你一个1亿大小的数组,为了五个数这样太浪费空间了,也不可行,还是需要别的排序方法(文末会总结各个排序方法的适用情况)。第三个问题:如果每个数据都带着名称,在排序的时候无法同时对别的关联项进行排序。

针对第三个问题,我又学习了冒泡排序和选择排序,再加上结构体关联名称和数据,轻松解决第三个问题;

来聊一聊冒泡排序:

算法思想很简单就不码字了,直接上代码

基本版的冒泡排序:

void bubble_sort(int arr[], int len) {  
    int i, j;  
    for (i = 0; i < len - 1; i++)  
        for (j = 0; j < len - 1 - i; j++)  
            if (arr[j] > arr[j + 1])  
                swap(arr[j], arr[j + 1]);  
}  

冒泡的时间复杂度高达O(n^2),排序速度慢,我们进行如下升级

第一次升级:设立了结束标志的冒泡:

void bubble_sort(int arr[], int len) {  
    int i, j;  
    bool flag;
    for (i = 0; i < len - 1 && flag!=0; i++)  
        {  
                flag=0;  
        for (j = 0; j < len - 1 - i; j++)  
            if (arr[j] > arr[j + 1])  
                        {  
                swap(arr[j], arr[j + 1]);  
                                flag = 1;  
                         }  
        }  
}  

变量flag用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换,说明序列已经有序了,结束冒泡。

第二次升级:鸡尾酒排序(本段源引自郭威gowill博客)

        鸡尾酒排序又叫定向冒泡排序,搅拌排序、来回排序等,是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

鸡尾酒排序在于排序过程是先从低到高,然后从高到低;而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要从低到高,然后从高到低就可以完成排序,但如果使用冒泡排序则需要四次。

但是在乱数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲。

void cocktail_sort(int arr[], int len) {  
    int j, left = 0, right = len - 1;  
    while (left < right) {  
        for (j = left; j < right; j++)  
            if (arr[j] > arr[j + 1])  
                swap(arr[j], arr[j + 1]);  
        right--;  
        for (j = right; j > left; j--)  
            if (arr[j - 1] > arr[j])  
                swap(arr[j - 1], arr[j]);  
        left++;  
    }  
}  

还有选择排序:

void SelectSort(int arr[],int n)
{
    for(int i = 0; i <n - 2; ++i)
    {
        int k = i;
        for(int j = i + 1; j < n - 1; ++j)
        {
            //找到最小的数的下标
            if(v[j] < v[k])
                k = j;
        }
        if(k != i)
        {
            swap(v[k],v[i]);
        }
    }
}

选择排序进化!:双极端的选择排序

在每一次查找最小值的时候,也可以找到一个最大值,然后将两者分别放在它们应该出现的位置,这样遍历的次数就会少一半!

void SelectSort(int arr[],int n)
{
    int left = 0;
    int right = n - 1;
    int min = left;//用来存储最小值的下标
    int max = left;//用来存储最大值的下标
    while(left <= right)
    {
        min = left;
        max = left;
        for(int i = left; i <= right; i++)
        {
            if(arr[i]<arr[min])
                min = i;
            if(arr[i] > arr[max])
                max = i;
        }
        swap(arr[left],arr[min]);
        if(left == max)
            max = min;
        swap(arr[right],arr[max]);
		left++,right++;
    }
}

今天第一次写训练日志,就先写到这吧,剩下的几种排序算法明天再写,

总结一下:

今天学习了简化版桶排序,冒泡排序、选择排序及各自的升级版本,还有插入排序和快速排序(这两个明天写吧)

  • 桶排序,以空间换时间,对于处理取值范围小的领域占优势(比如学生成绩),但处理取值大的数据或者有较复杂要求的排序题就弱鸡了,限制较高
  • 选择和冒泡,占用空间比桶排序要小,可是时间复杂度超级高,当排序数据量高的时候会慢出翔。

有没有能对不同类的问题有着更好的适应性能并且能保证排序的速度呢?

且听下回分解:排序算法(下)


注:本人第一次写博客,难免会有错误,希望能在评论指出!十分感谢