力扣9.25

2306. 公司命名

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：

从 ideas 中选择 2 个不同名字，称为 ideaA 和 ideaB 。
交换 ideaA 和 ideaB 的首字母。
如果得到的两个新名字都不在ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
否则，不是一个有效的名字。
返回不同且有效的公司名字的数目。

数据范围

2 <= ideas.length <= 5 * 104
1 <= ideas[i].length <= 10
ideas[i] 由小写英文字母组成
ideas 中的所有字符串互不相同

分析

将字母按开头分类，放入 $v ec t or$ 中，预处理每个开头对应的集合中的单词在和后面的字母交换首字母后仍然合法的单词的数量，放在 $c n t [i] [j]$ 中( $c n t [i] [j]$ 表示以 $i$ 开头的单词集中若和字符j交换首字母后仍然合法的单词数目)，外层循环遍历所有的单词，内存循环遍历字母序比当前单词首字母小的字母，若能交换，则 $res$ 加上 $c n t$ 对应的值。

代码

typedef long long LL;
class Solution {
public:
    const static int N = 35, M = 5e4 + 5;
    // unordered_map<string, bool> vis;
    unordered_set<string> st;
    int cnt[N][N];
    vector<string> idea[N];
    long long distinctNames(vector<string>& ideas) {
        for(auto v : ideas) {
            // vis[v] = true;
            st.insert(v);
            idea[v[0] - 'a'].push_back(v);
        }
        for(int i = 'a' - 'a'; i <= 'z' - 'a'; i ++ ) {
            for(int j = 'a'; j <= 'z'; j ++ ) {
                for(auto k : idea[i]) {
                    string ts = k;
                    ts[0] = j;
                    // if(!vis[ts]) cnt[i][j - 'a'] ++ ;
                    if(!st.count(ts)) cnt[i][j - 'a'] ++ ;
                }
            }
        }
        LL res = 0;
        for(int i = 'a' - 'a'; i <= 'z' - 'a'; i ++ ) {
            for(auto s : idea[i]) {
                for(int j = 0; j < i; j ++ ) {
                    string ts = s;
                    ts[0] = char(j + 'a');
                    if(st.count(ts)) continue;
                    res += cnt[j][i];
                }
            }
        }
        return res * 2;
    }
};

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

数据范围

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

分析

将每个数字出现的个数用cnt数组记录，令dp[i][0]表示不删除值为i的数获得点数最大值，dp[i][1]表示删除值为i的数获得点数最大值，状态转移如下

$d p [i] [0] = ma x (d p [i - 1] [1], d p [i - 1] [0])$
$d p [i] [1] = d p [i - 1] [0] + c n t [i] * i$

代码

class Solution {
public:
    const static int N = 1e4 + 5;
    int cnt[N];
    int dp[N][2];
    int n;
    int deleteAndEarn(vector<int>& nums) {
        n = nums.size();
        for(int i = 0; i < n; i ++ ) cnt[nums[i]] ++ ;
        for(int i = 1; i <= N - 5; i ++ ) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + cnt[i] * i;
        }
        int res = 0;
        for(int i = 0; i <= N - 5; i ++ ) {
            res = max(res, dp[i][0]);
            res = max(res, dp[i][1]);
        }
        return res;
    }
};

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

数据范围

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

分析

简单DP，注意在边界的情况

代码

class Solution {
public:
    const static int N = 205;
    int dp[N][N];
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j <= i; j ++ ) {
                if(j == 0) dp[i + 1][j + 1] = dp[i][j  + 1] + triangle[i][j]; 
                else if(j == i) dp[i + 1][j + 1] = dp[i][j] + triangle[i][j]; 
                else dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i][j]) + triangle[i][j];
            }
        }
        int res = 0x3f3f3f3f;
        for(int i = 0; i < n; i ++ ) res = min(res, dp[n][i + 1]);
        return res;
    }
};