LeetCode冲刺：Day25

发布于 2022-12-02  36 次阅读

1. 兼具大小写的最好英文字母

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

用一个数组标记下每个字母的大小写形式的出现情况即可，从后往前遍历到第一个两个形式都出现的字母并返回。

代码

class Solution {
public:
    string greatestLetter(string s) {
        vector<int> vec(26, -1);
        for (auto& ch : s) {
            if (ch - 'a' >= 0 && ch - 'a' < 26) {
                if (vec[ch - 'a'] == -1) vec[ch - 'a'] = 0;
                else if (vec[ch - 'a'] == 1) vec[ch - 'a'] = 2;
            }
            else {
                if (vec[ch - 'A'] == -1) vec[ch - 'A'] = 1;
                else if (vec[ch - 'A'] == 0) vec[ch - 'A'] = 2;
            }
        }
        string ans = "";
        for (int i = 25; i >=0; --i) {
            if (vec[i] == 2) {
                ans += char('A' + i);
                return ans;
            }
        }
        return ans;
    }
};

2. 个位数字为 K 的整数之和

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

把问题想复杂了。

列式子看一下，其实num可以表示成10的倍数加上n乘以k的和。因为集合中所有元素都以k为个位数字，那么他们加起来的和一定是n乘以k加上10的倍数。那么只要从小到大遍历n就可以了。要注意num为0和k为0的情况。前者直接返回0，后者应当让k等于10。

其实数学类的题，只要注意到是数学问题，是不难想出来的。

代码

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        if (k == 0) k = 10;
        for (int i = 1; i * k <= num; ++i) {
            if ((num - i *k) % 10 == 0) return i;
        }
        return -1;
    }
};

3. 小于等于 K 的最长二进制子序列

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

写的比较繁琐，但好歹过了。

要值小于等于目标值，又要求长度最长。注意是子序列，不要求连续，那么前导零当然越多越好。于是先统计每一位左边一共有多少0，然后自左向右遍历，如果当前值再进一步就超过目标值，则停止下来，返回当前长度和左侧0数量的总和。

实际操作过程中，容易发生溢出，所以先计算目标值共有几位，以及当前遍历到的长度，如果长度超过位数，不用计算值，肯定超过了，如果没超过，那么加上对应值即可。

代码

class Solution {
public:
    int longestSubsequence(string s, int k) {
        int n = s.size();
        vector<int> zeroNum(n, 0);
        for (int i = 1; i < n; ++i) {
            if (s[i - 1] == '0') {
                zeroNum[i] = zeroNum[i - 1] + 1;
            }
            else zeroNum[i] = zeroNum[i - 1];
        }
        long long num = 0LL;
        int pos = 0;
        int target = log(k) / log(2);
        int j = n - 1;
        for (; j >=0; --j) {
            if (s[j] == '1') {
                if (pos > target) break;
                else {
                    num += 1LL << pos;
                    if (num > k) break;
                }

            }
            pos += 1;
        }
        int zero = j < 0 ? 0 : zeroNum[j];
        return zero + n - j - 1;
    }
};

4. 计算应缴税款总额

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

按部就班计算即可。因为保证了最后一级的上限大于收入，所以也不用考虑超过的情况。

代码

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        int n = brackets.size();
        double ans = 0.0;
        if (income <= brackets[0][0]) return income * brackets[0][1] * 0.01;
        ans += brackets[0][0] * brackets[0][1] * 0.01;
        for (int i = 1; i < n; ++i) {
            if (income <= brackets[i][0]) {
                ans += (income - brackets[i - 1][0]) * brackets[i][1] * 0.01;
                break;
            }
            else {
                ans += (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] * 0.01;
            }
        }
        return ans;

    }
};

5. 网格中的最小路径代价

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

DP的思路是用二维数组，记录从第一行到第i行j列元素所用的最小消耗。这样表示之后，后面的逻辑不难得出，最后时间复杂度是m乘以n的平方。而每次我们只关心当前层和上一层，所以空间可以优化。

代码

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) dp[0][i] = grid[0][i];
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int minCost = INT_MAX;
                for (int k = 0; k < n; ++k) {
                    int cost = dp[i - 1][k] + moveCost[grid[i - 1][k]][j];
                    minCost = min(minCost, cost);
                }
                dp[i][j] = minCost + grid[i][j];
            }
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; ++i) {
            ans = min(ans, dp[m - 1][i]);
        }
        return ans;
    }
};

6. 公平分发饼干

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

先是感觉类似背包问题，但小朋友的数目会超过两个，无法用背包解。最后用回溯居然擦线过了。但显然还有比较大的剪枝空间。

代码

class Solution {
private:
    int ans = INT_MAX;
    void backtracking(vector<int>& cookies, int cookie, const int& n, vector<int>& children, const int& k) {
        if (cookie == n) {
            ans = min(ans, *max_element(children.begin(), children.end()));
            return;
        }
        for (int i = 0; i < k; ++i) {
            children[i] += cookies[cookie];
            backtracking(cookies, cookie + 1, n, children, k);
            children[i] -= cookies[cookie];
        }
    }
public:
    int distributeCookies(vector<int>& cookies, int k) {
        ans = INT_MAX;
        vector<int> children(k, 0);
        backtracking(cookies, 0, cookies.size(), children, k);
        return ans;
    }
};

7. 公司命名

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

参考这篇 一种比较好理解的思路。

用一个二维数组，记录“用字母B代替一个字母A”对于组中多少字符串是可行的。这个过程中，其实也就统计了“用字母A代替字母B”对于多少字符串是可行的。于是这两种实际上是互补的，是可以作为一个可行解的，于是将两者相乘，最后计算这类互补的累加值即可。

对于字符串类题目，要想到如何用枚举字母的方法做。

代码

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        long long ans = 0L;
        unordered_set<string> s(ideas.begin(), ideas.end());
        vector<vector<long long>> cnt(26, vector<long long>(26));
        for (auto& idea : ideas) {
            int pre = idea[0] - 'a';
            for (int i = 0; i < 26; ++i) {
                idea[0] = 'a' + i;
                if (!s.count(idea)) cnt[pre][i]++;
            }
        }

        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                ans += cnt[i][j] * cnt[j][i];
            }
        }
        return ans;
    }
};