wy的leetcode刷题记录_Day2

854. 相似度为 K 的字符串

今天的每日一题是：854. 相似度为 K 的字符串
854. 相似度为 K 的字符串

题目介绍

对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的相似度为 k 。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

示例 1：
输入：s1 = “ab”, s2 = “ba”
输出：1

示例 2：
输入：s1 = “abc”, s2 = “bca”
输出：2

思路

代码

class Solution {
public:
    int kSimilarity(string s1, string s2) {
        queue<string> q{{s1}};
        unordered_set<string> vis{{s1}};
        int ans = 0;
        while (1) {
            for (int i = q.size(); i; --i) {
                auto s = q.front();
                q.pop();
                if (s == s2) {
                    return ans;
                }
                for (auto& nxt : next(s, s2)) {
                    if (!vis.count(nxt)) {
                        vis.insert(nxt);
                        q.push(nxt);
                    }
                }
            }
            ++ans;
        }
    }

    vector<string> next(string& s, string& s2) {
        int i = 0, n = s.size();
        for (; s[i] == s2[i]; ++i) {}
        vector<string> res;
        for (int j = i + 1; j < n; ++j) {
            if (s[j] == s2[i] && s[j] != s2[j]) {
                swap(s[i], s[j]);
                res.push_back(s);
                swap(s[i], s[j]);
            }
        }
        return res;
    }
};

收获

343. 整数拆分

题目介绍

给定?个正整数 n，将其拆分为?少两个正整数的和，并使这些整数的乘积最?化。返回你可以获得的最?乘积。

示例 1:
输?: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输?: 10
输出: 36
解释: 10= 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不?于 2 且不?于 58

思路

动态规划：
1.确定DP数组的含义：设立dp[i]表示i可以做整数拆分所得到的最大值
2.确定递推公式：对于dp[i]的求法有俩种：一种是（i-j）*j，另一种是dp[i-j]*j。这里不拆j的原因是因为在遍历中我们已经对j进行了拆分，每当j+1就相当于拆分加一另一个乘数换成dp[i-j-1]。所以，递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))

代码

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2]=1;
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<i-1;j++)
            {
                dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
            }
        }
        return dp[n];
    }
};