5.LeetCode刷题day05

【思路】KMP算法。判断a、b长度是否一样，如果不一样则不是旋转词。否则，先将a扩展一遍a = a + a，再判断b是否是a的子串即可。

bool isRotate(string s, string t) {
    if (s.size() != t.size() || s == t) {
        return false;
    }
    s = s + s;
    int res = s.find(t);
    return res == -1 ? false : true;
}

【思路】遍历数组统计奇数个数a，包含4因子的偶数c和包含2因子b的偶数的个数。分为如下几种情况：

1. 如果b == 0，c != 0，c >= a - 1才可以。两个奇数中间起码有一个4因子的偶数才能符合要求。
2. b≠0，c >= a才可以。2因子的数不能和奇数放在一块，因此，2因子的数放在一起，后面得接4因子的数，4因子的数和奇数轮流放。

【代码】

bool isFour(vector &arr) {
    int a = 0, b = 0, c = 0; //a奇数个数，b：2因子偶数个数，c：4因子偶数个数
    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] % 2) { //奇数
            ++a;
        } else if (arr[i] == 2){ //2因子偶数
            ++b;
        } else { //4因子偶数
            ++c;
        }
    }
    if (b == 0) {
        if (a == 1 && c >= 1) {
            return true;
        } else if (a > 1 && c >= a - 1) {
            return true;
        } else {
            return false;
        }
    } else {
        return c >= a ? true : false;
    }
}

【思路】斐波那契数列。假设去除木棍后，从小到大的第i根木棍为f（i）。如果能满足拼成三角形，则需要f(n - 1) + f(n - 2) > f(n);反之，不能拼出的极限状态就是f(n) = f(n - 1) + f(n - 2)。那么题目就变成1~n的斐波那契数列最多有几项。

【代码】

int remove(int n) {
    int pre2 = 1, pre2 = 2, cur = 3, count = 3;
    while (cur <= n) {
        pre2 = pre1;
        pre1 = cur;
        cur = pre2 + pre1;
        ++count;
    }
    return n - count + 1;
}

【思路】0 - 1背包。如果n袋零食选出正好等于背包容量，我们写出的dp表dp[i[j]的含义是，用第0~i袋零食正好凑出背包w的方法数有几种，第n - 1行的含义是用0~i袋零食正好凑出j容量的方法数有几种，这题是不超过背包容量，那么把最后一行中不超过w的值累加起来即可。

【原始暴力递归代码】

//用第0~i袋零食正好凑出背包容量w的方法是有几种 
int process(vector& nums, int i, int bag) {
    if (bag == 0) {
        return 1;
    }
    if (i == 0) {
        return bag == nums[0];
    }
    if (bag < 0) {
        return 0;
    }
    int p1 = process(nums, i - 1, bag);
    int p2 = process(nums, i - 1, bag - nums[i]);
    return p1 + p2;
}

【动态规划初始版】

int paths(vector& v, int bag) {
    int n = v.size();
    vector> dp(n, vector(bag + 1));
    for (int i = 0; i < n; ++i) {
        dp[i][0] = 1;
    }
    dp[0][v[0]] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= bag; ++j) {
            if (j - v[i] >= 0) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - v[i]];
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    int res = 0;
    for (int j = 0; j <= bag; ++j) {
        res += dp[n - 1][j];
    }
    return res;
}

【动态规划滚动数组优化版】

int paths(vector& v, int bag) {
    int n = v.size();
    vector dp(bag + 1);
    dp[0] = 1;
    dp[v[0]] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = bag; j >= 0; --j) {
            if (j - v[i] >= 0) {
                dp[j] = dp[j] + dp[j - v[i]];
            }
        }
    }
    int res = 0;
    for (int j = 0; j <= bag; ++j) {
        res += dp[j];
    }
    return res;
}

【思路】有序表。先将jobarr按难度从小到大排序，再将jobarr按报酬从大到小排序。建立一个新数组，存放同样难度中报酬最高的，高难度中报酬大于低难度的，这就是我们需要考虑的几个工作。

【代码】

class Job {
public:
    Job(int hard, int money) : money(money), hard(hard) {}
    int hard;
    int money;
};
class MyCompare {
public:
    bool operator()(Job& lhs, Job& rhs) {
        if (lhs.hard == rhs.hard) {
            return lhs.money > rhs.money;
        }
        else {
            return lhs.hard < rhs.hard;
        }
    }
};
vector getJob(vector& job, vector& ability) {
    sort(job.begin(), job.end(), MyCompare());
    map map;
    map[job[0].hard] = job[0].money;
    Job pre = job[0]; //pre之前的组长
    for (int i = 1; i < job.size(); ++i) {
        if (job[i].hard != pre.hard && job[i].money > pre.money) {
            pre = job[i];
            map[job[i].hard] = job[i].money;
        }
    }
    //cout << map.begin()->first << " " << map.rbegin()->first;
    for (int i = map.begin()->first; i != map.rbegin()->first; ++i) {
        if (map.find(i) == map.end()) {
            map[i] = map[i - 1];
        }
    }
    vector res(ability.size());
    for (int i = 0; i < ability.size(); ++i) {
        res[i] = map.find(ability[i]) == map.end() ? 0 : map[ability[i]];
    }
    return res;
}

【思路】符合日常书写有以下要求：

1. 数字字符之外只允许出现“-”号。
2. 如果有“-”号，只会出现在开头且只出现一次，且后面只能跟着不为0的数字字符。
3. 如果开头为0，后面必须没有字符。

【代码】

bool isValid(string &str) {
    //第一个字符不是减号且不是数字字符不符合
    if (str[0] != '-' && (str[0] < '0' || str[0] > '9')) {
        return false;
    }
    //第一个字符是减号，但是只有一个减号字符或者-0不符合
    if (str[0] == '-' && (str.size() == 1 || str[1] == 0)) {
        return false;
    }
    for (int i = 1; i < str.size(); ++i) {
        if (str[i] < '0' || str[i] > '9') {
            return false;
        }
    }
    return true;
 }

int convert(string &str) {
    if (str.empty()) {
        return 0;
    }
    if (!isValid(str)) {
        return -1;
    }
    return stoi(str);
}