牛牛的分配
思路:贪心。我们发现,为了使可以达到要求的瓶子尽可能地多的话,我们就要把原来已经达到要求的,而且多出来的水先收集起来,然后,按目前未达到的要求的瓶子的水量从少到多进行分配,直到把所有的多出来的水都被用完了或者已经不能再使得任何一个瓶子达到要求或者我们能把所有的瓶子都达到要求。
代码:
class Solution { public: /** * 返回重新分配后,满足牛牛要求的水量的瓶子最多的数量 * @param n int整型 瓶子的数量 * @param x int整型 牛牛的对瓶中的水量要求 * @param a int整型vector 每个瓶子中的含水量 * @return int整型 */ int solve(int n, int x, vector<int>& a) { // write code here sort(a.begin(),a.end()); long long sum=0; int k=-1; for(int i=n-1;i>=0;i--){ if(a[i]<x){ k=i; break; } else{ long long tmp=a[i]-x; sum+=tmp; } } int ans=n; for(int i=k;i>=0;i--){ long long tmp=x-a[i]; if(sum<tmp){ ans=n-i-1; break; } else sum-=tmp; } return ans; } };
playfair
思路:模拟+STL。这个题目有点复杂,关键是要先读懂题目来。我们首先要处理的问题是先根据输入的密钥求出相应的密码表,然后才好进行相应的查询操作。加密过程中的j都由i来代替。playfair加密算法首先需要绘制密码表,密码表是一个5*5的矩阵,开始由密钥按顺序排列,其余按照未出现的字母顺序。若密钥中含有重复字母需要将重复字母去掉,若有j用i来代替。这些话十分关键,它给了我们以下信息:
1、密码表肯定是5x5的,那么我们就可以开一个矩阵进行存储密码表。
2、如果密钥里面有j,就要用i来替换掉,也就是可以先把密钥的j都换成i,然后再转成密码表。
3、如果待加密的字符串里面有j,也要用i先进行替换,然后再根据密码表进行转换。
然后,介绍几个比较好的小技巧,我们对于每一个位置,假如我们想要快速的知道给位置在密码表中的具体的坐标的话,可以用一个map来进行映射,然后该字符的坐标用一个node结构体进行存储。这样,我们在比较相邻字符改如何进行转化的时候就可以比较快速的查询到每个字符的具体的坐标了。
代码:
class Solution { public: /** * playfair加密算法 * @param key string字符串 密钥 * @param str string字符串 明文 * @return string字符串 */ char c[6][6]; bool inq[1000]={false}; struct node{ int x,y; }; map<char,node> mp; string Encode(string key, string str) { // write code here int len=key.size(); string rk; for(int i=0;i<len;i++){ if(inq[key[i]]==false){ if(key[i]=='j'){ rk+='i'; inq['j']=true; inq['i']=true; continue; } if(key[i]=='i') inq['j']=true; rk+=key[i]; inq[key[i]]=true; } } for(int i='a';i<='z';i++){ if(inq[i]==false){ if(i=='j') continue; rk+=i; inq[i]=true; } } // cout<<rk<<endl; int k=0; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ c[i][j]=rk[k++]; node Node; Node.x=i,Node.y=j; mp[c[i][j]]=Node; } } string ans; len=str.size(); int x1,x2,y1,y2; for(int i=0;i<len;i++){ if(str[i]=='j') str[i]='i'; } for(int i=0;i<len;i++){ x1=mp[str[i]].x,y1=mp[str[i]].y; i++; if(i==len) break; x2=mp[str[i]].x,y2=mp[str[i]].y; char s; //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl; if(x1!=x2&&y1!=y2){ s=c[x1][y2]; ans+=s; s=c[x2][y1]; ans+=s; } else if(x1==x2&&y1==y2){ ans+=str[i]; ans+=str[i]; } else if(x1==x2){ if(y1==5) y1=0; if(y2==5) y2=0; s=c[x1][y1+1]; ans+=s; s=c[x2][y2+1]; ans+=s; } else if(y1==y2){ if(x1==5) x1=0; if(x2==5) x2=0; s=c[x1+1][y1]; ans+=s; s=c[x2+1][y2]; ans+=s; } } if(len&1) ans+=str[len-1]; return ans; } };
牛牛摇骰子
思路:打表题。直接进行bfs肯定会被T,我们知道可以通过打表发现对于每个位置,都是在以11为周期进行变化的。然后初始的从1-11对应的答案分别为:3,2,1,2,3,2,1,2,3,2,1,但是这里有个例外就是当坐标在2的时候所需摇塞子的次数为4次,其余的就可以根据上面那个周期求得。没多出11就在原来的基础之上加上1.
代码:
class Solution { public: /** * 把所有询问的答案按询问顺序放入vector里 * @param arr int整型vector 要查询坐标的数组 * @return int整型vector */ //typedef long long ll; int a[12]={-1,3,2,1,2,3,2,1,2,3,2,1}; vector<int> MinimumTimes(vector<int>& arr) { // write code here int len=arr.size(); vector<int> ans; for(int i=0;i<len;i++){ int num=arr[i]; if(num==2) ans.push_back(4); else{ int cnt,id; if(num%11==0){ cnt=num/11-1; id=11; } else{ cnt=num/11; id=num%11; } int tmp=a[id]+cnt; ans.push_back(tmp); } } return ans; } };