华为笔试题

1、数的分解

给定一个正整数n，如果能够分解为m(m > 1)个连续正整数之和，
请输出所有分解中，m最小的分解。
如果给定整数无法分解为连续正整数，则输出字符串"N"。
输入描述：
输入数据为一整数，范围为（1, 2^30]
输出描述：
比如输入为：
21
输出：
21=10+11
补充说明：
21可以分解的连续正整数组合的形式有多种
21=1+2+3+4+5+6
21=6+7+8
21=10+11
输出，21=10+11，是最短的分解序列。

思路：
k + (k + 1) + (k + 2) +…+(k + m - 1) = n
m * [k + (k + m - 1)] / 2 = n
mk + m * (m - 1) / 2 = n
如果存在k作为起始点，m个连续的数字相加等于n,
即：
mk = n - [m * (m -1) / 2]
则：m 能被 n - [m * (m -1) / 2] 整除
且k = { n - [m * (m -1) / 2] } / m

code

#include <iostream>
#include <vector>using namespace std;
void Find(int & n) {bool flag = false;for (int m = 2; m *(m - 1) < 2 * n; m++) {if ((n - m * (m -1) / 2) % m == 0) {int k = (n - m * (m -1) / 2) / m;if (k > 0) {cout << n << "=";for(int i = 0; i < m - 1; i++) {cout << k + i << "+";}cout <<  k + m - 1 << endl;flag = true;break;}      }}if (!flag)cout << "N" << endl;
}int main(){int n;while(cin>>n) {Find(n);}return 0;
}

2、字符串判断子串

描述
输入两个字符串 S 和 L，都只包含英文小写字母。S 长度\u003C=100，L 长度\u003C=500,000。
判定 S 是否是 L 的有效子串。
判定规则：
S 中的每个字符在 L 中都能找到（可以不连续），
且 S 在Ｌ中字符的前后顺序与 S 中顺序要保持一致。
（例如，S=”ace”是 L=”abcde”的一个子序列且有效字符是 a、c、e，
而”aec”不是有效子序列，且有效字符只有 a、e）
输入描述
输入两个字符串 S 和 L，都只包含英文小写字母。
S 长度\u003C=100，L 长度\u003C=500,000。
先输入 S，再输入 L，每个字符串占一行。
输出描述
S 串最后一个有效字符在 L 中的位置。（首位从 0 开始计算，无有效字符返回-1）
示例一
输入输出示例仅供调试
输入
ace
abcde
输出4
思路
双指针直接比较

code

#include <iostream>
#include <vector>using namespace std;
int Find(string& s, string& l) {int s_len = s.length();int l_len = l.length();int i = 0, j = 0;int res = 0;while (j < l_len) {if (s[i] == l[j]){i++;res = i;if (i == s_len){return j;}}j++;}return -1;    
}int main(){string s,l;while(cin>>s>>l) {int res = Find(s, l);cout << res << endl;}return 0;
}