当前位置: 首页 > news >正文

重庆颐众达网站青岛seo整站优化哪家专业

重庆颐众达网站,青岛seo整站优化哪家专业,网站做端口是什么,网站管理基本内容把数字翻译成字符串 题目描述示例示例1示例2 题解动态规划代码实现复杂度分析 总结 题目描述 有一种将字母编码成数字的方式:‘a’->1, ‘b’->2, … , ‘z’->26。 现在给一串数字,返回有多少种可能的译码结果。 数据范围:字符串…

把数字翻译成字符串

    • 题目描述
    • 示例
      • 示例1
      • 示例2
    • 题解
      • 动态规划
      • 代码实现
      • 复杂度分析
    • 总结

题目描述

有一种将字母编码成数字的方式:‘a’->1, ‘b’->2, … , ‘z’->26。

现在给一串数字,返回有多少种可能的译码结果。

数据范围:字符串长度满足 (0 < n \leq 90)

进阶:空间复杂度 (O(n)),时间复杂度 (O(n))

示例

示例1

输入

"12"

返回值

2

说明
2种可能的译码结果(“ab” 或 “l”)

示例2

输入

"31717126241541717"

返回值

192

说明
192种可能的译码结果

题解

动态规划

我们可以使用动态规划来解决这个问题。设 dp[i] 表示前 i 个数字可以翻译成多少种不同的字符串。状态转移方程如下:

  1. 如果当前数字 nums[i] 不为 0,则 dp[i] += dp[i-1]
  2. 如果当前数字 nums[i-1]nums[i] 组成的两位数在 1026 之间,则 dp[i] += dp[i-2]

边界条件

  • dp[0] = 1,表示空字符串有一种翻译方式。
  • dp[1] = 1,如果第一个字符不为 0,则有一种翻译方式。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 解码函数
int solve(char* nums) {int length = strlen(nums); // 获取输入字符串的长度if (length == 0) return 0; // 如果字符串为空,返回0// 分配动态规划数组,dp[i] 表示前 i 个字符的解码方法数int* dp = (int*)calloc(length + 1, sizeof(int));dp[0] = 1; // 空字符串有一种解码方式// 初始化第一个字符的解码方法数if (nums[0] > '0' && nums[0] <= '9') {dp[1] = 1; // 如果第一个字符是有效的数字(1-9),有一种解码方式} else {return 0; // 如果第一个字符无效(如 '0'),直接返回0}// 遍历字符串,计算每个位置的解码方法数for (int i = 1; i < length; i++) {// 将当前字符和前一个字符组合成一个两位数int two = (nums[i-1] - '0') * 10 + (nums[i] - '0');// 如果当前字符是 '0'if (nums[i] == '0') {// 如果两位数无效(如 '00' 或大于 '26'),返回0if (two == 0 || two >= 30) {return 0;}// 当前位置的解码方法数等于前两个字符的解码方法数dp[i+1] = dp[i-1];} // 如果两位数在 11 到 26 之间,可以解码为一个字母else if (two >= 11 && two <= 26) {// 当前位置的解码方法数等于前一个字符和前两个字符的解码方法数之和dp[i+1] = dp[i] + dp[i-1];} // 其他情况,当前字符单独解码else {dp[i+1] = dp[i];}}// 获取最终结果int result = dp[length];free(dp); // 释放动态规划数组return result;
}int main() {char nums[] = "226"; // 示例输入int result = solve(nums); // 调用解码函数printf("Number of ways to decode: %d\n", result); // 打印结果return 0;
}

复杂度分析

  • 时间复杂度:(O(n)),其中 (n) 是字符串的长度。我们只需要遍历一次字符串即可。
  • 空间复杂度:(O(n)),用于存储动态规划数组 dp

总结

本题通过动态规划的方法,将问题分解为子问题,逐步求解。通过状态转移方程,我们可以有效地计算出所有可能的译码结果。这题最傻逼的就是如何处理0,还好只要考虑“00”到“99”一百种情况。所以不需要考虑太多。

http://www.zhongyajixie.com/news/18778.html

相关文章:

  • 有了源码怎么做网站网站建设哪家好
  • 织梦做视频网站交换链接网站
  • 网络规划设计师哪个机构好seo关键词优化推广报价表
  • 网站建设网页制济南优化seo公司
  • 六里桥做网站公司广州搜发网络科技有限公司
  • 陌上香坊是做盗版的网站吗汕头网站建设推广
  • 领券的网站怎么建设百度关键词优化系统
  • 房地产网站建设批发南京疫情最新情况
  • 网站开发的社会可行性小程序排名优化
  • 做网站开发公司做网络推广为什么会被抓
  • 网站可以做软件检测吗百度推广手机版
  • 扁平化设计网站代码竞价点击软件排名
  • 制作一个收费网站要多少钱html友情链接
  • 淘宝网站建设方案seo网站诊断方案
  • 考试网站建设b2b网站大全免费
  • 免费效果图网站什么是关键词广告
  • 工商局网站查询入口免费关键词挖掘网站
  • 网站开发前后端配比哪家公司做推广优化好
  • 南京网站建设有限公司精准客源推广引流
  • 网站制作接单平台活动策划
  • 用什么做网站后台烟台seo外包
  • 商业空间设计图片seo运营做什么
  • 网站优化代码青岛seo精灵
  • 南昌高端模板建站iis7站长工具
  • 做公司网站的平台中国疫情最新消息
  • 网站建设职业发展前景打开百度搜索网站
  • 广州学校论坛网站建设天津网站建设公司
  • 成都网站建设外包太原百度seo排名软件
  • 天津外贸公司网站制作seo关键词排名优化销售
  • 怎么用手机搭建网站百度网盘官网登陆入口