目录

例 完美立方

例 生理周期

例 称硬币

练习​​​​​ 剑指 Offer 57 - II. 和为s的连续正数序列

练习 找出三位偶数

练习 1291. 顺次数

---

例子源于慕课课程：程序设计与算法二

例 完美立方

输入正整数N，N以内满足 a^3=b^3+c^3+d^3 ；需要满足b<=c<=d；

分析

• a最大，[2,n]

• b,c,d  [2,n-2]

• 四个循环进行枚举，a最外层，d最内层，输出条件为满足立方和大小关系

代码：

#include<iostream>
using namespace std;
//完美立方
int main()
{int a, b, c, d;int n;cin >> n;for (a = 2; a <= n; a++){for (b = 2; b < n ; b++){for (c = 2; c < n ; c++){for (d = 2; d < n ; d++){if (a * a *a == b * b *b+ c * c * c + d * d*d && b<=c && c<=d){cout << "a:  " << a<<endl;cout << "bcd:  " << b <<" " <<c<<" "<<d<< endl;}}}}}return 0;
}输入输出
12
a:  6
bcd:  3 4 5
a:  12
bcd:  6 8 10

例 生理周期

 

题目限制：日子小于21250；当输入p,e,i为-1时退出循环

分析：

• 三个循环，设三峰条件为k，输出 k-d
• k需满足三峰条件： 
• 优化：枚举可以跳过明显不符合要求的项，要满足双峰需要先满足单峰，所有第二个自增23，要满足双峰，需要先满足三峰，所以第三个自增 23*28,也就是最小公倍数

#include<iostream>
using namespace std;
#define N 21250
int main()
{int p,e,i,d;int k;while (cin >> p >> e >> i >> d&&p!= -1){for (k = d + 1; (k - p) % 23 != 0; k++)for (; (k - e) % 28 != 0; k += 23)for (; (k - i) % 33 == 0&&k<=N; k += 23 * 28)cout << k - d << endl;}return 0;
}

例 称硬币

 

 

分析

• even:平衡； up:右边向上； down：右边向下（右边重）
• 一共12个A~L，假设A是轻的假币，判断是否满足样例条件，假设A是重的假币，判断是否满足样例条件；B……
• 因数据多，用二维数组，三行七列

#include<iostream>
#include<cstring>
using namespace std;
char Left[3][7];//不用left，不明确
//7：12个最多一边6个，但是以字符串读入，遇到空格停止，需要有默认的'/'占一个位置，否则读入6个溢出
char Right[3][7];
char result[3][7];//结果
bool isFake(char c, bool light);int main()
{int t;//次数cin >> t;while (t--){for (int i = 0; i < 3; i++)cin >> Left[i] >> Right[i]>>result[i];for (char c = 'A'; c <= 'L'; c++){if (isFake(c, true)){cout << c << "is the light coin that fake" << endl; break;}else if (isFake(c, false)){cout << c << "is the heavy coin that fake" << endl; break;}}}return 0;
}bool isFake(char c, bool light)
{for (int i = 0; i < 3; i++){char* pLeft, * pRight;if (light){pLeft = Left[i];pRight = Right[i];}else{pLeft = Right[i];pRight = Left[i];}switch (result[i][0]){case 'u':if (strchr(pRight, c) == NULL)  return false;break;case 'e':if (strchr(pLeft, c) || strchr(pRight, c)) return false;break;case 'd':if (strchr(pLeft, c) == NULL) 	return false;break;}}return true;
}

练习​​​​​ 剑指 Offer 57 - II. 和为s的连续正数序列

分析

• 确定从1 一直试到 (target+1) / 2，因为大于target的一半的数再加上另一个更大的一定不符合条件
• 在第二层循环过程中，遇到满足条件的就退出，sum至0，vector清空
• 因为不确定个数，用二维动态数组，而且题目有提示输出格式

class Solution {
public:vector<vector<int>> findContinuousSequence(int target) {vector<int> vec;vector<vector<int>> ves;int sum=0;for (int i = 1; i <= (target+1) / 2; i++) {for (int j = i; j <= (target + 1) / 2; j++) {sum += j;if (sum == target){vec.clear();for (int k = i; k <= j; k++){vec.push_back(k);//压入尾端}ves.push_back(vec);sum = 0;break;}else if(sum>target){ sum = 0;break;}}}return ves;}
};

注：vector知识点：C++ primer page86

练习 找出三位偶数

​​​​​​​力扣 2094. 找出 3 位偶数

class Solution {
public:vector<int> findEvenNumbers(vector<int>& digits) {set<int> st;vector<int> vec;int n = digits.size();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {if (i == j || j == k || k== i) {continue;//break?}// 注意：不能是同一位置重复三次，如果不同位置数相等则可以int tmp = digits[i] * 100 + digits[j] * 10 + digits[k];if ((tmp >= 100) && (tmp % 2 == 0))st.insert(tmp);}}}set<int>:: iterator i;for (i = st.begin(); i != st.end(); i++) {vec.push_back(*i);//i?}sort(vec.begin(), vec.end());return vec;}
};

（注意判断条件的设置，前导不为0，则数值一定大于等于100；注意push_back（）的参数是*i，而不是i）

练习 1291. 顺次数

分析：

• 枚举所有顺次数，判断是否在区间内
•   num = num * 10 + j;//12，123，1234……

class Solution {
public:vector<int> sequentialDigits(int low, int high) {vector<int> vec;int num = 0;for (int i = 1; i <= 9; i++) {//所有数枚举num = i;for (int j = i + 1; j <= 9; j++) {num = num * 10 + j;if (num >= low && num <= high)vec.push_back(num);}}sort(vec.begin(), vec.end());return vec;}
};