Code – 第93页

【C++】accumulate函数的用法（STL）

在头文件 #include <numeric> 里（但是我用的时候在PAT里面不写头文件似乎也没关系……）

主要是用来累加容器里面的值，比如int、string之类，可以少写一个for循环

比如直接统计 vector<int> v 里面所有元素的和：（第三个参数的0表示sum的初始值为0）

int sum = accumulate(v.begin(), v.end(), 0);

比如直接将 vector<string> v 里面所有元素一个个累加到string str中：（第三个元素表示str的初始值为空字符串）

string str = accumulate(v.begin(), v.end(), "");

LeetCode 377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

题目大意：给一个数组，都是正整数且没有重复的数字，任取里面的数字，问有多少种相加等于target的方式
分析：建立dp数组，（dp[i]表示相加等于i的方法有dp[i]个）设dp[0]等于1。i从1到target，给dp[i]赋值。要想知道dp[i]的值，用j遍历nums数组，只要将dp[i-nums[j]]的值累加即可得到，注意只累加i大于等于nums[j]的情况，表示让nums[j]作为第一个数字，剩下的数字有的组合方法有dp[i-nums[j]]个，最终返回dp[target]的值即可～

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++)
            for (int j = 0; j < nums.size(); j++)
                if (i >= nums[j]) dp[i] += dp[i - nums[j]];
        return dp[target];
    }
};

class Solution {

public:

int combinationSum4(vector<int>& nums, int target) {

vector<int> dp(target + 1);

dp[0] = 1;

for (int i = 1; i <= target; i++)

for (int j = 0; j < nums.size(); j++)

if (i >= nums[j]) dp[i] += dp[i - nums[j]];

return dp[target];

}

};

LeetCode 740. Delete and Earn

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] – 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
Example 2:
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2 and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

题目大意：给一个数组，你可以拿起nums[i]并且删除nums[i]并得到nums[i]分数，但是你必须删除数组中所有的nums[i]-1和nums[i]+1，就是说nums[i]-1和nums[i]+1的分数是不可能得到了～求问你能够获得最大的分数会是多少～

分析：数组不是有序的，且在1～10000之间，所以先遍历数组，将i数字所拥有的个数保存在cnt[i]中。设立dp数组，含有10001个元素，（dp[i]表示遍历到i这个数的时候当前情况下的最大值。最后返回dp[10000]的值就是所求），dp[0] = 0, dp[1] = cnt[1]。i从2遍历到10000。对于dp[i]，因为如果要了i这个数就不能要i-1和i+1，所以当前i有两个选择：一，要i这个数带来的分数cnt[i] * i，那就不能要dp[i-1]只能要dp[i-2]。二，不要i带来的分数要dp[i-1]的分数。这两个选择取最大值，所以dp[i] = max(dp[i-1], cnt[i] * i + dp[i-2])，最后返回dp[10000]～

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> cnt(10001, 0), dp(10001, 0);
        for (int i = 0; i < n; i++) cnt[nums[i]]++;
        dp[1] = cnt[1];
        for (int i = 2; i <= 10000; i++)
            dp[i] = max(dp[i-1], cnt[i] * i + dp[i-2]);
        return dp[10000];
    }
};

class Solution {

public:

int deleteAndEarn(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

vector<int> cnt(10001, 0), dp(10001, 0);

for (int i = 0; i < n; i++) cnt[nums[i]]++;

dp[1] = cnt[1];

for (int i = 2; i <= 10000; i++)

dp[i] = max(dp[i-1], cnt[i] * i + dp[i-2]);

return dp[10000];

}

};

LeetCode 650. 2 Keys Keyboard

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:
Input: 3
Output: 3
Explanation:
Intitally, we have one character ‘A’.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get ‘AA’.
In step 3, we use Paste operation to get ‘AAA’.
Note:
The n will be in the range [1, 1000].

题目大意：一开始给一个A，每次只能复制所有、或者粘贴上一次复制的内容。问要想最后变成n个A，至少得经过多少步～

分析：可以用贪心算法解决，i从2到√n，尝试是否能被n整除，如果能被整除，说明可以通过复制1次粘贴i-1次得到，则计数器ans加上i次，然后将n除以i。再次判断是否能被i整除，直至不能整除为止。然后尝试下一个i……最终n如果等于1则直接返回ans，否则要加上n表示对A复制一次粘贴n-1次～

class Solution {
public:
    int minSteps(int n) {
        int ans = 0;
        for (int i = 2; i <= sqrt(n); i++) {
            while (n % i == 0) {
                ans += i;
                n /= i;
            }
        }
        if (n != 1) ans += n;
        return ans;
    }
};

class Solution {

public:

int minSteps(int n) {

int ans = 0;

for (int i = 2; i <= sqrt(n); i++) {

while (n % i == 0) {

ans += i;

n /= i;

}

if (n != 1) ans += n;

return ans;

}

};

LeetCode 746. Min Cost Climbing Stairs

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Note:
cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

题目大意：爬n阶的楼梯，每层都有一个cost值（0～n-1），每次可以爬1层或者2层，求爬完全程的最小花费cost（可以从第0层开始也可以从第1层开始）

分析：dp数组，每次dp[i] = cost[i] + min(dp[i-1], dp[i-2])，最终返回dp[n-1]和dp[n-2]中较小的那个～

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[0] = cost[0], dp[1] = cost[1];
        for (int i = 2; i < n; i++)
            dp[i] = cost[i] + min(dp[i-1], dp[i-2]);
        return min(dp[n-1], dp[n-2]);
    }
};