剑指Offer-第10天 动态规划（中等）

第一题

题目链接：https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

个人题解：动态规划
\(f[i]=\left\{\begin{matrix} f[i-1],stol(s[-1] \in [10,25])\\ f[i-1]+f[i-2] ,stol(s[-2:-1] \in others) \end{matrix}\right.\)

代码：

class Solution {
public:
    int translateNum(int num) {
        string ss = to_string(num);
        int len = (int)ss.size();

        vector dp(len, 0);

        dp[0] = 1;
        for(int i = 1; i < len; i++) {
            if(stoi(ss.substr(i - 1, 2)) <= 25 && ss[i - 1] != '0') {
                if(i - 2 < 0) {
                    dp[i] = dp[i - 1] + 1;
                } else {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
            } else {
                dp[i] = dp[i - 1];
            }
        }

        return dp[len - 1];
    }
};

运行截图：

第二题

题目链接：https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

个人题解：哈希表+双指针

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map hash;
        int res=0;
        for(int i=0,j=0;i1) hash[s[j++]]--;
            res=max(res,i-j+1);
        }
        return res;
    }
};

运行截图：