第一题 [蓝桥杯 2013 省] 买不到的数目
题目描述
解题报告
解法一是一种数学知识的积累吧。
两个互质的数x,y不能组成的最大整数为x*y-x-y，如果题目给定的两个数不互质的话，那么任何数都能组成，所以给定的数一定是互质的。
解法二是动态规划。
这个动态规划不用闫式DP分析了。直接可以从递推的想法来实现。
bool数组 bool f[i]来记录是否能组成当前这个数字i
状态转移就十分简单了，倘若能够从f[i-n]转移过来或者能从f[i-m]转移过来，就是能够组成，否则就记录答案，表示不能组成当前的数字（从两个数字中最小的开始枚举，就能够递推找到最大的数字了）
参考代码(C++版本)
解法一：
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL n,m; int main() { scanf("%lld %lld",&n,&m); printf("%lld",n*m - n -m); return 0; }
解法二
#include <bits/stdc++.h> using namespace std; typedef long long LL; bool f[1000010]; int n,m; int main() { cin >> n >>m; int maxv = max(n,m); int minv = min(n,m); f[0] = true; int ans = 0; for(int i = minv; i <= n * m;i++) { if(f[i-minv]) f[i] = true; else if(i >= maxv && f[i-maxv]) f[i] = true; else ans = i; } cout << ans; return 0; }
第二题 P3951 [NOIP2017 提高组] 小凯的疑惑
题目描述
解题报告
参考代码(C++版本)
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL n, m; //2,147,483,648 int main() { scanf("%lld %lld",&n,&m); printf("%lld\n",n*m-n-m); return 0; }
第三题 191. 位1的个数
积累lowbit运算
题目描述
解题报告
lowbit运算——这东西是板子，背着就好
关于lowbit运算的知识点：
在这里插入图片描述
根据图片中对lowbit运算的定义，对于非负整数10，其二进制表示为( 1010 ) 2 (1010)_2(1010)
2
，那么lowbit(n) = ( 10 ) 2 (10)_2(10)
2
= 2
lowbit运算的证明/推导
关于运算的证明可以权当了解，现阶段会用，能Ac就好，以后学习更深入了再搞定原理也不迟的。
lowbit运算的作用
① 可以配合哈希表找出整除二进制表示下的所有是1的位数
② lowbit运算是树状数组的一个基本运算
参考代码(C++版本)
class Solution { public: int hammingWeight(uint32_t n) { int ans = 0; while(n) { n -= (n & (-n)); ans ++; } return ans; } };
第四题 461. 汉明距离
题目描述
解题报告
使用右移运算符一位一位的移动，比较
参考代码(C++版本)
class Solution { public: int hammingDistance(int x, int y) { //一位一位的移动，比较 int ans = 0; while(x || y) { if((x&1) != (y&1)) ans ++; x >>= 1; y >>= 1; } return ans; } };
解法二：
学习一下英雄哥的玩法
class Solution { public: int hanmingWeight(uint32_t n) { int ans = 0; while(n) { ans += (n & 1); n >>= 1; } return ans; } int hammingDistance(int x, int y) { return hanmingWeight(x^y); } };
第五题 136. 只出现一次的数字
异或运算积累
题目描述
解题报告
解法一：哈希表
解法二：任意两个相同的数字(2的倍数同样成立哦)异或结果为0，那么把所有的数字全部异或之后，最后得到的结果就0 ^ 只出现一次的数字。因为异或运算有时候也称我不进位加法，0 ^ 只出现一次的数字 = 0 + 只出现一次的数字
参考代码(C++版本)
解法一
class Solution { public: int singleNumber(vector<int>& nums) { //哈希表的思想 unordered_map <int,int> mp; int n = nums.size(); for(int i = 0; i < n;i++) mp[nums[i]] ++; int ans = 0; for(int i = 0; i < n;i++) if(mp[nums[i]] == 1) ans = nums[i]; return ans; } };
解法二：
这个解法的效率，嘎嘎提升了
class Solution { public: int singleNumber(vector<int>& nums) { int n = nums.size(); int ans = nums[0]; for(int i = 1; i < n;i++) ans ^= nums[i]; return ans; } };
第六题 137. 只出现一次的数字 II
数位统计——为状态压缩动态规划做铺垫了
题目描述
解题报告
老规矩，也是可以直接哈希表
解法二：数位统计
参考代码(C++版本)
解法一：
class Solution { public: int singleNumber(vector<int>& nums) { unordered_map <int,int> mp; int n = nums.size(); for(int i = 0; i < n;i++) mp[nums[i]] ++; int ans = 0; for(int i = 0; i < n;i++) if(mp[nums[i]] == 1) ans = nums[i]; return ans; } };
解法二：
数位统计的思想
看到这个题的数据范围了，其实就可以向着位运算的方向思考了。
现在了，其实可以使用一个32位的二进制来表示咱们要进行计算的十进制数字，然后对用于表示的32位的二进制进行求和，因为除了咱们需要的答案，其他的结果都是三的倍数，那么可以将求和的结果的每一位和3进行取模，最后得到的结果就是咱们需要的答案了，再把其从二进制转换为十进制就好。
样例演示：
nums = [2,2,3,2]
将这四个数字转换为32位的二进制：
[00000000000000000000000000000010, 00000000000000000000000000000010, 00000000000000000000000000000011, 00000000000000000000000000000010]；
对这四个二进制的每一位进行求和：
[00000000000000000000000000000041]
将求和结果的每一位进行3的取模运算：
[00000000000000000000000000000011]
将得到的结果[00000000000000000000000000000011]从二进制转换成十进制就是3
class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; int n = nums.size(); for(int i = 0; i < 32;i++) { int sum = 0; for(int j = 0;j < n;j++) sum += ((nums[j] >> i) & 1); if(sum%3) //将得到的二进制转十进制 ans |= (1 << i); } return ans; } };
总结
① 积累买不到数目的数学想法，我记得是使用裴蜀定理来证明的，后续补上吧
② 积累lowbit运算
③ 数位统计的想法
