title: 【每日一题】LeetCode 91.解码方法
tags:

  • leetcode
  • acwing
  • 算法
  • 每日一题
    abbrlink: d73dd87b
    date: 2021-04-21 20:22:22

断更说明

前两天停止更新了两天，不是因为我放弃挣扎了，而是后面几天的每日一题都被预判了。。。在之前的文章（推送）里面都可以找到，今天题目恢复正常，每日一题也开始正常更新

之后可能会把几天的每日一题汇总起来一次发推送，提高每篇文章的丰富度，如果有任何好的建议，欢迎给我留言。

LeetCode 91. 解码方法

思路

本题的大致意思是要将一段编码后的字符串解码，而按照对应的转换关系，编码后的数字会有很多种不同的划分方式对应着不同的解码方式，这里就需要用到动规的思想，先判断当前如果是1-9即可算一种排列方式，接着再判断当前数和前一个数字组合以后能够组成一个10-26之间的数（与字母对应）即可认为也存在一种情况，直接加上这种情况即可。

C++代码

  1. class Solution {
  2. public:
  3.     int numDecodings(string s) {
  4.         int n=s.size();
  5.         s=' '+s;
  6.         vector<int> f(n+1);
  7.         f[0]=1;
  8.         for(int i=1;i<=n;i++)
  9.         {
  10.             if(s[i]>='1' && s[i]<='9')  f[i]+=f[i-1];
  11.             if(i>1)
  12.             {
  13.                 int t=(s[i-1]-'0') * 10 + s[i] - '0';
  14.                 if(t>=10 && t<=26)
  15.                     f[i]+=f[i-2];
  16.             }
  17.         }
  18.         return f[n];
  19.     }
  20. };

AcWing 821.跳台阶

思路

一道基本的动规题目，斐波那契的应用

C++代码

  1. #include<iostream>
  2. #include<algorithm>
  4. using namespace std;
  6. const int N=20;
  8. int n;
  9. int f[N];
  11. int main()
  12. {
  13.     cin>>n;
  14.     f[0]=1, f[1]=1;
  15.     for(int i=2;i<=n;i++)
  16.         f[i]=f[i-1]+f[i-2];
  17.     cout<<f[n]<<endl;
  18.     return 0;
  19. }