题目一：移动最短距离（分析法）
#include<iostream>#include<algorithm>using namespace std;#include<vector>//用于记录最短跳跃的n行1列的二维数组，path//输入的二维数组目标点point//跳跃的次数k,n行，目标值距离起始点的距离target。//分析这道题：假设移动了k次，每次任意地向左或向右移动，那么最终达到的位置实际上就是1,2,3,……，k。// 这k个整数添加正号或负号后求和的值。如果target<0，可以将这k个数的符号全部取反，这样求和的值为−target>0。//所以我们可以只考虑target>0 的情况。我们假设移动最小k次，移动总长度为L，能够超越起始点距目标值的距离target//若此时正好L=target，那k就是我们所求的最小步数，如果L-target为偶数，那此时的最小步数也为k.//例如起始点为0，目标值为4， L=1+2+3=6>target=4, 6-4=2为偶数，那我们是不是可以找到一个2/2的数令他为负数，一加一减就为2了//此时移动为：向左移动1位，向右移动两位，向右移动三位，-1+2+3=4，到达目标值，移动次数为3//若L-target为奇数时，我们没办法凑出这样的数字，所以我们要使步数k+1，或加2，因为这样必定有一个使L-target为偶数的数，难以理解的话可以看例子//target为奇数，L为偶数，L-target此时为奇数，不能凑数，我们使k加1来看看，比如L=6，target=5，那么此时k=3，另k +=1，L+k此时等于10。//10-5=5，还是为奇数，那么在另k+=1，L+k=15,15-5=10，看，此时是不是求出来一个偶数，是不是就又可以凑数了。此时移动次数为5。class Solution {public://先求从零点出发寻找的第一个目标值，因为这里我们是0行0列，没办法减去前一个目标值，所以单独拿出来计算static vector<vector<int>> search1(vector<vector<int>> point, vector<vector<int>> &path,int &target) {target = abs(point[0][0]); //abs函数，取模值，因为我们上文分析过，拿正数去计算即可int k = 0;while (target > 0) {k++;target -= k;}int res = target % 2 == 0 ? k : k + 1 + k % 2;//基础薄弱的话可以去看一下这个三元运算符path[0][0] = res; //把求得的移动次数放入到二维数组中，记录答案return path;}static vector<vector<int>> search2(vector<vector<int>> point, vector<vector<int>> &path, int &target, int n) {for (int i = 1; i < n; i++) {int k = 0; //很关键，因为每次循环找到终点时，k要重新计算，归零target = abs(point[i][0] - point[i - 1][0]); //因为我们要在上一个目标值上进行移动，所以拿当前的目标值减去上次的目标值，就是起始点到终点的距离while (target > 0) {k++;target -= k;}int result = target % 2 == 0 ? k : k + 1 + k % 2;path[i][0] = result; //把最小次数挨个放入二维数组中}return path;}};int main() {int n;cin >> n;int target = 0;vector<vector<int>> point(n, vector<int>(1));vector<vector<int>> path(n,vector<int>(1));for (int i = 0; i < n; i++) {cin >> point[i][0];}Solution:: search1(point, path, target);Solution:: search2(point, path, target, n);for (int i = 0; i < n; i++) {cout << path[i][0] << endl;}return 0;}
测试案例AC如下：
题目二：字母映射数字，求最大得分
一开始我还想用递归去做，真不知道怎么想的，就下面写的代码我觉得时间复杂度还是有点高，应该可以优化，只不过我没有想到，下述代码时间复杂度O（nlogn）,空间复杂度O（n)。
#include<iostream>#include<algorithm>using namespace std;#include<vector>#include<string>int MaxSum(int n,int k,string s,vector<int>& vec,int &sum) {int m = n - 1;for (int i = 0; i < n; i++) { //把字母转换成数字放入vec容器中vec[i] = s[i] - 'a' + 1;}sort(vec.begin(), vec.end());while (k--) { //求前k个最大数之和sum += vec[m--];}return sum;}//n个字母，按k次，最大得分sum，字符串s，把英文字母挨个转换成数字的vecint main() {int n;int k;int sum = 0;cin >> n>>k;string s;cin >> s;vector<int> vec(n);MaxSum(n, k, s, vec,sum);cout << sum << endl;return 0;}
测试案例如下 ：
