leetcode刷题日记 1

https://leetcode.cn/problems/decode-ways/description/

题目分析

在这里插入图片描述

分析了一下题目，我的第一想法：和之前的上楼梯问题很像

为什么这么说呢，感觉他们的值和他们之前元素都有千丝万缕的联系

就像上楼梯问题

就是我们的dp问题

怎么解释呢？可以理解为将一个大问题分为一个一个的小问题（贪心贪一半（bushi））

我觉得dp问题的最核心的就是**：dp[i]表示什么**

像这个问题就可以将dp[i]表示成i位置是能够解码的方式有多少

其实，仔细的来看，我们每一个i位置都会面临两个情况：

是否1<= s[i]<=9
*是否10<= s[i-1]10+s[i] <=26

这就是判断能不能将其当做一种解法的关键

否则这个i地方的数字将会dp[i]等于0

连锁反应的是是这样的话之后dp表的值都是

原理：

简单来说，我们也说了，每一个s[i]都有两个情况，四种可能

如果1<= s[i]<=9的话那么这种可能的可以行得通，返回dp[i-1],证明这种方法可行

不行的话就会返回0

如果10<= s[i-1]*10+s[i] <=26，那么这种可能的可以行得通返回dp[i-2],证明这种方法可行

不行的话就会返回0

dp[i]就是将这两个可能返回的值加在一起

还要注意初始化，因为我们要用到dp[i-2]，所以我们的得保证dp[i-2]不会溢出，所以当i<2时我们要单独拿出来初始化

代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int numDecodings(string s) {
        vector<int> bp(s.size() + 1);
        int ans1 = 0;
        int ans2 = 0;
        if (s.size() == 1 && (s[0]-'0') >= 1 && (s[0] - '0') <= 9)
        {
            ans1 = 1;
        }
        else ans1 = 0;
        bp[0] = ans1;
        if (s.size() == 2)

        {
            if ((s[0] - '0') >= 1 && (s[0] - '0') <= 9)
            {
                ans1 = 1;
            }
            else
            {
                ans1 = 0;
            }
            bp[0] = ans1 ;
            if ((s[1] - '0') >= 1 && (s[1] - '0') <= 9)
            {
                ans1 = bp[0];
            }
            else
            {
                ans1 = 0;
            }

            if (((s[0] - '0') * 10) + (s[1] - '0') >=10  && ((s[0] - '0') * 10) + (s[1] - '0') <= 26)
            {
                ans2 = bp[0];
            }
            else
            {
                ans2 = 0;
            }
            bp[1] = ans1 + ans2;
        }


        for (int i = 2; i < s.size(); i++)
        {
            if ( (s[0] - '0') >= 1 && (s[0] - '0') <= 9)
            {
                ans1 = 1;
            }
            else ans1 = 0;
            bp[0] = ans1;

             if ((s[1] - '0') >= 1 && (s[1] - '0') <= 9)
                {
                    ans1 = bp[0];
                }
                else
                {
                    ans1 = 0;
                }
               

                if (((s[0] - '0') * 10) + (s[1] - '0') >= 10 && ((s[0] - '0') * 10) + (s[1] - '0') <= 26)
                {
                    ans2 =1;
                }
                else
                {
                    ans2 = 0;
                }
                bp[1] = ans1 + ans2;
            

            ans1 = 0;
            ans2 = 0;
            if ((s[i] - '0') >= 1 && (s[i] - '0') <= 9)
            {
                ans1 = bp[i - 1];
            }
            else
            {
                ans1 = 0;
            }
            if (((s[i-1] - '0') * 10) + (s[i] - '0') >= 10 && ((s[i-1] - '0') * 10) + (s[i] - '0') <= 26)
            {
                ans2 = bp[i - 2];
            }
            else
            {
                ans2 = 0;
            }
            bp[i] = ans1 + ans2;

        }
        return bp[s.size() - 1];

    }
};