前言

题目比较简单。 第一题打卡题，直接按题意操作即可。 第二题dp，属于dp的入门。 第三题也是比较简单的模拟题。

T1

给定一个整数数组nums和一个整数目标值target,.请在该数组中找出和为目标值target的两个整数，并返回它们在数组中的位置（按顺序为0,1,2…）。

可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

例如整数数组nums=[3,2,4]，整数目标值target=6

因为nums[1]+nums[2]=6,因此返回1,2

输入描述：

【一个整数数组】

一个整数目标值

输出描述：

和为目标值的两个整数对应数组里的位置

输入
[3,2,4] 
6
输出
1,2

思路与代码：

用map存出现过的数字，每次读入一个数x，直接在map里找target-x即可。

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
  unordered_map<int, int> numMap;
  for (int i = 0; i < nums.size(); ++i) {
    int complement = target - nums[i];
    if (numMap.find(complement) != numMap.end()) {
      return {numMap[complement], i};
    }
    numMap[nums[i]] = i;
  }
  return {};
}

int main() {
  vector<int> nums;
  char c;
  while (cin >> c) {
    if (isdigit(c) || c == '-') {
      cin.putback(c);
      int num;
      cin >> num;
      nums.push_back(num);
    } else if (c == ']') {
      break;
    }
  }
  int target;
  cin >> target;
  vector<int> result = twoSum(nums, target);
  if(result.size()!=2) cout << -1 << endl;
  else cout << result[0] << "," << result[1] << endl;

  return 0;
}

T2

假设你正在完成一项爬楼梯任务，需要n个步骤才能完成。每次你可以完成1个步骤，或者2个步骤并行。你有多少种不同的方法可以完成任务? 例如，你需要3个步骤完成爬楼梯任务，你可以有以下方法: 1+1+1 1+2 2+1 共3种方法。

输入描述:

所需的步骤，为一个整数。例如3

输出描述:

能有的方法，为一个整数。例如:3

输入
3
输出
3

思路与代码：

递推出一个数组即可。状态转移dp[i]=dp[i-1]+dp[i-2]

#include <iostream>
#include <vector>

using namespace std;

int solve(int n) {
    if (n <= 1) {
        return 1;
    }

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    cin >> n;
    int ways = solve(n);

    cout << ways << endl;

    return 0;
}

T3

假如一个n位自然数等于自身各个数位上数字的n次幂之和，则称此数为n位自幂数。例如: 153就是一个三位自幂数。因为153是三位数，各位数分别为: 1、5、3，且1^3 + 5^3+ 3^3 = 153 现给定一个大于等于3小于等于9的正整数n，以及正整数num，且n为num的位数，请判断该num是否为n位自幂数。如果是则输出1，否则输出-1。

输入描述:

大于等于3小于等于9的正整数n，以及正整数num

输出描述:

如果是则输出1，否则输出-1

输入样例:

3,153

输出样例:

1

输入
3,153
输出
1

思路与代码：

提取num的每一位，求n次幂看是否等于num即可。

#include <iostream>
#include <cmath>

using namespace std;

int solve(int n, int num) {
    int temp = num;
    int sum = 0;

    while (temp > 0) {
        int digit = temp % 10;
        sum += pow(digit, n);
        temp /= 10;
    }

    return (sum == num) ? 1 : -1;
}

int main() {
    int n, num;
    scanf("%d,%d", &n,&num);
    int result = solve(n, num);

    cout << result << endl;

    return 0;
}