柳婼の blog – 第93页 – 我不管，反正我最萌～

PAT 1140. Look-and-say Sequence (20) – 甲级

Look-and-say sequence is a sequence of integers as the following:
D, D1, D111, D113, D11231, D112213111, …
where D is in [0, 9] except 1. The (n+1)st number is a kind of description of the nth number. For example, the 2nd number means that there is one D in the 1st number, and hence it is D1; the 2nd number consists of one D (corresponding to D1) and one 1 (corresponding to 11), therefore the 3rd number is D111; or since the 4th number is D113, it consists of one D, two 1’s, and one 3, so the next number must be D11231. This definition works for D = 1 as well. Now you are supposed to calculate the Nth number in a look-and-say sequence of a given digit D.
Input Specification:
Each input file contains one test case, which gives D (in [0, 9]) and a positive integer N (<=40), separated by a space.
Output Specification:
Print in a line the Nth number in a look-and-say sequence of D.
Sample Input:
1 8
Sample Output:
1123123111
题目大意：给两个数字D和n，第一个序列是D，后一个序列描述前一个序列的所有数字以及这个数字出现的次数，比如D出现了1次，那么第二个序列就是D1，对于第二个序列D1，第三个序列这样描述：D出现1次，1出现1次，所以是D111……以此类推，输出第n个序列～
分析：用string s接收所需变幻的数字，每次遍历s，从当前位置i开始，看后面有多少个与s[i]相同，设j处开始不相同，那么临时字符串 t += s[i] + to_string(j – i);然后再将t赋值给s，cnt只要没达到n次就继续加油循环下一次，最后输出s的值～

#include <iostream>
using namespace std;
int main() {
    string s;
    int n, j;
    cin >> s >> n;
    for (int cnt = 1; cnt < n; cnt++) {
        string t;
        for (int i = 0; i < s.length(); i = j) {
            for (j = i; j < s.length() && s[j] == s[i]; j++);
            t += s[i] + to_string(j - i);
        }
        s = t;
    }
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

int n, j;

cin >> s >> n;

for (int cnt = 1; cnt < n; cnt++) {

string t;

for (int i = 0; i < s.length(); i = j) {

for (j = i; j < s.length() && s[j] == s[i]; j++);

t += s[i] + to_string(j - i);

}

s = t;

}

cout << s;

return 0;

}

LeetCode 322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

题目大意：你有一些不同面值的硬币，你需要用这些硬币凑成amount值，计算需要的最少的硬币个数～如果不能凑成，就返回-1

分析：设立dp数组（dp[i]表示凑成i需要的最小硬币个数），一开始dp[0]等于0，i从1到amount填充dp[i]的值，第二层循环遍历coins数组，假设coins[j]作为第一个硬币，那么dp[i-coins[j]]表示剩下的金额需要的硬币个数，此时判断i-coins[j]是否等于-1，也就是是否能够凑成，如果能够凑成，那么当dp[i]>0时表示凑成i需要dp[i]个硬币，这种情况下如果dp[i-coins[j]]+1更小，就更新dp[i]，否则就保留dp[i]的值。如果dp[i]本身就<=0说明前面没有方法可以凑成i，那么就直接更新dp[i]为dp[i-coins[j]] + 1的值，有一种凑成的方法总比没有好～最后返回dp[amount]的值表示凑成amount数量需要的最小硬币个数，如果不存在，本身dp数组的初值就为-1，所以也会按照要求返回-1～

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i >= coins[j] && dp[i-coins[j]] != -1) {
                    if (dp[i] > 0) 
                        dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                    else
                        dp[i] = dp[i-coins[j]] + 1;
                }
            }
        }
        return dp[amount];
    }
};

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

vector<int> dp(amount + 1, -1);

dp[0] = 0;

for (int i = 1; i <= amount; i++) {

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

if (i >= coins[j] && dp[i-coins[j]] != -1) {

if (dp[i] > 0)

dp[i] = min(dp[i], dp[i-coins[j]] + 1);

else

dp[i] = dp[i-coins[j]] + 1;

}

return dp[amount];

}

};

【C++】max_element() 和 min_element()

0. 在头文件 #include <algorithm> 中，返回的是迭代器，所以输出值的话要在前面加 *

1. 第三个参数cmp可写可不写， max_element() 和 min_element() 默认是从小到大排列，然后 max_element() 输出最后一个值， min_element() 输出第一个值，但是如果自定义的 cmp 函数写的是从大到小排列，那么会导致 max_element() 和 min_element() 的两个结果是对调的

2. 可以用于 vector<int> 或者 vector<string> 等，也可以用于 int arr[4] 或者 string arr[4] ，也可以用于结构体vector或者结构体数组～

struct node {
    int x, y;
};
bool cmp1(node a, node b) {
    return a.x > b.x;
}
int main() {
    vector<int> v(3);
    int arr[4];
    vector<node> v1(3);
    cout << *max_element(v.begin(), v.end());
    cout << *min_element(arr, arr + 4);
    cout << (*max_element(v1.begin(), v1.end(), cmp1)).y;
    return 0;
}

struct node {

int x, y;

};

bool cmp1(node a, node b) {

return a.x > b.x;

}

int main() {

vector<int> v(3);

int arr[4];

vector<node> v1(3);

cout << *max_element(v.begin(), v.end());

cout << *min_element(arr, arr + 4);

cout << (*max_element(v1.begin(), v1.end(), cmp1)).y;

return 0;

}

【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];

}

};