leecode198.打家劫舍（复盘）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
学习思路分析：
利用动态规划数组dp，初始化dp[0]=nums[0],dp[1]=max(nums[0],nums[1]),利用循环再把前面计算过的前面两个dp[i-1],dp[i-2]进行比较，dp[i-2]加上当前位置的nums数组里面数值nums[i]再与d[i-1]作比较，取出大的一方为当前i+1个数的dp[i]值，即为当前偷到的最高金额。因此结束循环后，得到的dp数组的最后一个值dp[n-1]为所求解。
如1，2，3，4
dp[0]=1.dp[1]=2,dp[2]=4，dp[3]=6
学习的解决代码：
class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
if(!n)return 0;
if(n == 1)return nums[0];
if(n == 2)return max(nums[0],nums[1]);
int dp[n];
dp[0] = nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2; i<n; i++)
dp[i]=max(dp[i - 2]+nums[i],dp[i - 1]);
return dp[n-1];
}
};
最小差值(http://118.190.20.162/view.page?gpid=T68)
问题描述
给定n个数，请找出其中相差（差的绝对值）最小的两个数，输出它们的差值的绝对值。
输入格式
输入第一行包含一个整数n。
第二行包含n个正整数，相邻整数之间使用一个空格分隔。
输出格式
输出一个整数，表示答案。
样例输入1
5
1 5 4 8 20
样例输出1
1
样例输入2
5
9 3 6 1 3
样例输出2
0
数据规模和约定
对于所有评测用例，2 ≤ n ≤ 1000，每个给定的整数都是不超过10000的正整数。
心路历程
水题，找找手感。好久没碰发现好多东西都忘了。。。。
当时在做这道题其实给我感觉跟上面的那题十分相像，所以当时在看到leecode198的第一想法也是 打算隔一个加起来没有考虑到可以隔很多个的情况，相对198那题来说这题还是很基础的，无脑循环就是了。
代码如下
#include<iostream>
#include<cstdlib>
using namespace std;
#define max 10000
int main(){
int n,min,total;
while(cin>>n){
if(n<2)break;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
min=abs(a[0]-a[1]);
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
total=abs(a[i]-a[j]);
if(total<min)min=total;
}
}
cout<<min<<endl;
}
}
打酱油 (http://118.190.20.162/view.page?gpid=T63)
问题描述
小明带着N元钱去买酱油。酱油10块钱一瓶，商家进行促销，每买3瓶送1瓶，或者每买5瓶送2瓶。请问小明最多可以得到多少瓶酱油。
输入格式
输入的第一行包含一个整数N，表示小明可用于买酱油的钱数。N是10的整数倍，N不超过300。
输出格式
输出一个整数，表示小明最多可以得到多少瓶酱油。
样例输入
40
样例输出
5
样例说明
把40元分成30元和10元，分别买3瓶和1瓶，其中3瓶送1瓶，共得到5瓶。
样例输入
80
样例输出
11
样例说明
把80元分成30元和50元，分别买3瓶和5瓶，其中3瓶送1瓶，5瓶送2瓶，共得到11瓶。
分析：
3*2>5,傻子都知道买5瓶的划算，所以先把买五瓶送两瓶的凑齐了，剩下的看够不够三瓶再继续凑。看到这个题的时候一下子就写出来了，放到ccf的判题平台发现1.忽略了小细节：N是10的整数倍，N不超过300。 2.超时了。第一个问题很快就解决了，第二个问题看了我好一会，最后想起来由于对5瓶进行不断循环计算赠送的瓶数，结束循环时的num必定小于5，所以当结算买三瓶送一瓶的时候，只需要一个简单的if语句就行了，用while会超时。
代码如下:
#include<iostream>
using namespace std;
int main(){
int n,num,total;
while(cin>>n){
if(n>300&&n%10!=0)return 0;
total=num=n/10;
while(num>=5){
num-=5;
total+=2;
}
if(num>=3){
total++;
}
cout<<total<<endl;
}
return 0;
}
914. 卡牌分组
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
- 每组都有
X张牌。 - 组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
提示：
1 <= deck.length <= 10000
0 <= deck[i] < 10000
示例 1：
输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
示例 2：
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。
示例 3：
输入：[1]
输出：false
解释：没有满足要求的分组。
示例 4：
输入：[1,1]
输出：true
解释：可行的分组是 [1,1]
示例 5：
输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]
我的思路：
看到邵崇耿在群上发的一道题目，觉得他的思路有点复杂（太绕了），想着不如用一个count数组，利用count[deck[i]]++统计每个数字的个数，找出公约数，能被所有count[i]整除就返回true否则返回false更直接简单明了。这样从头到尾直接操作count数组就行了，然后就去实现了下。
其中控制count数组中的0个数是关键，避免0对count数组中不为0的最小值min产生影响。
#define N 10000
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
int count[N]={0},min;
for(int i=0;i<deck.size();i++)
count[deck[i]]++;
min=10000;
for(int i=0;i<N;i++){
if(count[i]<min&&count[i]!=0){
min=count[i];//找出count数组中不为0的最小值
}
}
if(min<2)return false;
for(int j=2;j<=min;j++){//找公约数
if(min%j==0){
int i=0;
for(;i<N;i++){
if(count[i]%j!=0&&count[i]!=0)break;
}
if(i==N)return true;//i没有被中断，说明找到了公约数，分组成功
}
}
return false;
}
};
