数组中和为0的三个数
数组中和为0的三个数
原题链接：https://leetcode.cn/problems/1fGaJU/
1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时，
123456789101112131415161718192021222324252627class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; //使用双指针解决剩余两个数字 for (int j = i + 1; j < nums.size(); ++j) { for (int k = j + 1; k < nums.size(); ++k) { if (nums[i] + nums[j] + nums[k] == 0) { //判定符合要求的答案是否重复 //ans.push_back({nums[i], nums[j], nums[k]}); if (ans.size() == 0) ans.push_back({nums[i], nums[j], nums[k]}); else { int flag = 1; for (in ...
奶牛碑文
奶牛碑文
原题链接：https://oj.haizeix.com/problem/516
约翰和他的奶牛在大草原漫游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C,O,W。
尽管约翰看不懂，但是令他高兴的是，C,O,W的顺序形式构成了一句他最喜欢的奶牛单词 “COW”。
现在，他想知道有多少次 COW出现在文本中。
如果 COW内穿插了其他字符，只要COW字符出现在正确的顺序，约翰也不介意。
他也不介意出现不同的COW共享一些字母。例如CWOW出现了1次COW，CCOW算出现了2次COW，CCOOWW算出现了8次COW。
输入：
第一行一个整数 N。（1≤N≤105）
第二行为含有 N 个字符的字符串，字符只可能是 C,O,W。
输出：
输出 COW 作为输入字符串的子串出现的次数（不一定是连续的），答案可能会很大。
样例：
126COOWWW
16
参考代码
暴力法：三重for循环分别对C,O,W进行遍历，可能会导致超时。
利用前缀和思想：空间复杂度换时间复杂度，
1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;char str[100005];int numc[100005], numw[100005], n;long long ans;int main() { cin >> n >> str; for (int i = 0; str[i]; ++i) {//从前向后遍历 计算有多少个C（前缀和C） if (i == 0) { numc[i] = (str[i] == 'C'); } else { numc[i] = numc[i - 1] + (str[i] == 'C'); } } for (int i = n - 1; i >= 0; --i) {//从后向前遍历 计算有多少个W（后缀和W） if (i == n - 1) { numw[i] = (str[i] == 'W' ...
三角形个数
三角形个数
原题链接：https://oj.haizeix.com/problem/517
输入一根木棒的长度 n，将其分成三段，每段的长度是正整数，输出由这三小段木棒组成的不一样的三角形个数。
输入：
第一行一个整数 n。（1 ≤ n ≤ 104）
输出：
输出组成的不一样的三角形的个数。
样例：
110
12
样例说明：
两个能组成的三角形边长分别为 2,4,4 和 3,3,4。
参考代码123456789101112131415161718#include<iostream>using namespace std;int main() { int ans = 0; int n; cin >> n; //注意枚举范围 for (int i = 1; i <= n / 3; ++i) {//枚举最小边 for (int j = i; j <= (n - i) / 2; ++j) {//枚举次小边 if ((i + j) > (n - i - j)) {//判断最长边的合法性 ans++; //cout << i << " " << j << " " << n - i - j << endl; } } } cout << ans << endl; return 0;}
优雅数
优雅数
原题链接：https://oj.haizeix.com/problem/519
优雅枚举
给定两个数 L,R 求 L,R 之间（含）有多少个“优雅数”。
优雅数的定义：把一个数看做一个长度为 n 的字符串，n 个字符中 n−1 个全相同，有且仅有一个字符不同。例如 33323,119 都是优雅的，99999, 2332 都是不优雅的。
输入：
输入一行两个整数 L, R。（100 ≤ L ≤ R ≤ 1016）
输出：
输出两数间优雅数的个数。
样例：
1110 133
113
样例说明：
1110,112,113,114,115,116,117,118,119,121,122,131,133
参考代码
思路1：暴力法，遍历两数区间，直接对优雅数进行判定。
思路2：构造优雅数，将区间之内的所有优雅数直接构造出来，判定是否构造的优雅数是否在给定区间范围内。
单独的数字是几
多个的数字是几
优雅数的长度
单独的数字在优雅数中的位置（构造优雅数）
若一堆数为0的话，单独的数字必须要在优雅数的首位（不允许前导零）
若一个数为0的话，单独的0数字必须不能在首位（不允许前导零）
123456789101112131415161718192021222324252627282930#include<iostream>using namespace std;int main() { long long ans = 0; long long a, b; cin >> a >> b; for (int i = 0; i < 10; ++i) {//枚举单个的数字 for (int j = 0; j < 10; ++j) {//枚举多个的数字 if (i == j) continue; for (int k = 3; k < 18; ++k) {//枚举优雅数的数字长度 for (int l = 1; l <= k; ++l) {//枚举单独的数字在优雅数中的位置 if (i == 0 && l == 1) continue; if (j == 0 && l != 1) bre ...
火柴棒等式
火柴棒等式
原题链接：https://oj.haizeix.com/problem/514
给出 n 根火柴棒，可以拼出多少个形如 a + b = c 的等式。
等式中的 a,b,c 是用火柴棒拼出的整数（不能有前导零），数字和符号使用的火柴棒数量如下：
1234567891011120:61:22:53:54:45:56:67:38:79:6+:2=:2
有以下注意事项：
加号和等号各自需要两根火柴棒
如果 a ≠ b，则 a + b = c 和 b + a = c 视为不同的等式，a,b,c 均不小于 0
n 根火柴棒必须全部用上。
输入：
共一行一个整数 n。（1 ≤ n ≤ 24）
输出：
输出能组成的等式数。
样例：
114
12
样例说明：两个等式如下
120 + 1 = 11 + 0 = 1
参考代码难点：枚举范围的确定，取火柴消耗数量最少的数字1举例（使得相加数值最大，由此确定最大范围），最大为1111+1111=2222。
123456789101112131415161718192021222324252627282930#include<iostream>using namespace std;int n;//火柴数量int ans;int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};int func(int x) { int count = 0; if (x == 0) return 6; while (x) { count += num[x % 10]; x /= 10; } return count;} int main() { cin >> n; for (int i = 0; i <= 2000; ++i) { for (int j = 0; j <= 2000; ++j) { if ((func(i) + func(j) + func(i + j) + 4) == n) { ans++; cout << i << " + " << ...
比例简化
比例简化
原题链接：https://oj.haizeix.com/problem/515
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为 1498:902
不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A’ 比 B’，
要求在 A’ 和 B’ 均不大于L，且 A’ 和 B’ 互质的前提下，
A’ / B’ ≥ A / B
且 A’ / B’ − A / B的值尽可能小
输入：
共一行三个整数 A, B, L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限
输出：
共一行两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例
样例：
11498 902 10
15 3
参考代码==思路==：
若从1开始枚举，
如果枚举出一个答案 A’，B’（互质），当在继续枚举出一个新的答案 A’，B’（不互质），必然存在一个原来就有的A’，B’（互质）
并且新的答案与原来的答案，比例应该是一样的。
即使用两个暴力for循环遍历，保证答案满足A’ / B’ ≥ A / B ，且A’ / B’ − A / B的值尽可能小即可。
1
3.OnlineJ516：奶牛碑文约翰和他的奶牛在大草原漫游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C,O,W。
尽管约翰看不懂，但是令他高兴的是，C,O,W的顺序形式构成了一句他最喜欢的奶牛单词 “COW”。
现在，他想知道有多少次 COW出现在文本中。
如果 COW内穿插了其他字符，只要COW字符出现在正确的顺序，约翰也不介意。
他也不介意出现不同的COW共享一些字母。例如CWOW出现了1次COW，CCOW算出现了2次COW，CCOOWW ...
两数之和
两数之和
原题链接：https://leetcode.cn/problems/two-sum/
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
1.暴力法1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; for (i = 0; i < nums.size(); ++i) { for (j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {i, j}; }};
2.二分查找思想：sort排序 + 二分查找
使用for循环遍历数组中的每一个数字
在for循环内部，使用target值减去当前遍历的数字值获取配对值ret，使用二分查找该数字ret
如果找到该数字则直接输出其下标(初始若有序的情况下)
实际是无序的！难点在于如何联系被sort打乱下标后的vec与未打乱的nums，并从其中找出目标数字的下标？
1234for (int j = 0; j < n; j++) { if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j); if(result.size() == 2) return result;}
12345678910111213141516171819202122 ...
Euler枚举
Euler枚举
1.E22：Name score在文本文件names.txt 中包含了五千多个名字，
首先将它们按照字母序排列，然后计算出每个名字的字母价值，乘以它在按字母顺序排列后的位置，就算出了这个名字的得分。
例如，按照字母序排列后，位于第938位的名字是COLIN，它的字母价值是3 + 15 + 12 + 9 + 14 = 53
因此，COLIN这个名字的得分是 938 × 53 = 49714.
上述文本文件中，所有名字的得分之和是多少？
1.暴力枚举
将name.txt文件下载下来，进行初步处理%s/","/ /g（将连接符替换为空格分隔）、%s/"/ /g（处理开头结尾的单引号）
将名字输入保存到name[6005]数组中
首先使用sort算法对name数组进行排序
外循环遍历name数字中的每一个名字，内循环遍历name的每一个字母计算每个名字的价值value
输出最后累加的score分数
123456789101112131415161718192021222324#include<iostream>#include<string>#include<algorithm>using namespace std;string name[6005];int n;int main(){ while(cin >> name[n]){ n++; } sort(name, name + n); long long score = 0; for(int i = 0; i < n; ++i){ int value = 0;//name的价值 for(int j = 0; j < name[i].size(); ++j){ value += name[i][j] - 'A' + 1; } score += value * (i + 1); } cout << score << endl; return 0;& ...
Largest palindrome product
Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
1.枚举
利用两个for循环枚举两个三位数相乘
判断相乘的乘积是否是回文整数(将数字倒置判断是否等于原数字
动态刷新最大回文整数
12345678910111213141516171819202122232425262728293031#include <iostream>using namespace std;//自定义判断回文数字func函数int func(int num){ int raw = num, reverse = 0; while(num){ //(1)将x值的最后一位放入reverse中，并且向前移动一位 reverse = reverse * 10 + num % 10; //(2)去掉x值的最后一位 num /= 10; } return raw == reverse;}int main(){ int ans = 0; //1.利用两个for循环枚举两个三位数相乘 for(int i = 0; i < 1000; i++){ for(int j = i; j < 1000; j++){ //2.判断相乘的乘积是否为回文数字 if(func(i * j)){ //3.动态刷新最大回文数字 ans = max(ans, i * j); } } } cout << ans ...
Multiples of 3 and 5
Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
1.枚举123456789101112#include <iostream>using namespace std;int main(){ int ans = 0; //时间复杂度:O(n) for(int i = 1; i < 1000; i++){ if(i % 3 == 0 || i % 5 == 0) ans += i; } cout << ans << endl; return 0;}
2.前n项求和公式思路：3或5的倍数之和 = 3的倍数之和 + 5的倍数之和 - 15的倍数之和（减去重复计入值）
1234567891011#include <iostream>using namespace std;int main(){ //时间复杂度:O(4) int t3 = (3 + 999) * 333 / 2; int t5 = (5 + 995) * 199 / 2; int t15 = (15 + 990) * 66 / 2; cout << t3 + t5 - t15 <<endl; return 0;}