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

wordpress登录网站百度竞价点击价格

wordpress登录网站,百度竞价点击价格,学软件测试培训哪里好,建立平台网站要多久大家好,欢迎来到无限大的频道。 今日继续给大家带来力扣题解。 题目描述(困难): 统计特殊整数 如果一个正整数每一个数位都是 互不相同 的,我们称它是 特殊整数 。 给你一个 正 整数 n ,请你返回区间 …

大家好,欢迎来到无限大的频道。

今日继续给大家带来力扣题解。

题目描述(困难):

统计特殊整数

如果一个正整数每一个数位都是 互不相同 的,我们称它是 特殊整数 。

给你一个 正 整数 n ,请你返回区间 [1, n] 之间特殊整数的数目。

​解题思路:

要计算区间 ([1, n]) 之间的特殊整数数量,可以按以下步骤进行:

  1. 定义特殊整数:

    • 一个特殊整数是指其每一个数位都是互不相同的,即没有重复的数字。

  2. 遍历和检查:

    • 遍历每一个整数从 1 到 n,检查每个整数是否为特殊整数。

    • 对于每个整数,可以将其分解为其各个数字,并检查这些数字是否有重复。

  3. 利用集合判断重复:

    • 可以通过一个数组或集合来记录某个数字是否已经出现。

  4. 计数特殊整数:

    • 如果当前数字是特殊整数,将计数器加一。遍历结束后,输出计数器的值。

参考代码如下:

bool is_special_integer(int num) {bool digit_seen[10] = {false}; // 标记每个数字是否出现过while (num > 0) {int digit = num % 10; // 取出当前的末尾数字if (digit_seen[digit]) { // 如果该数字已经出现过return false; // 不是特殊整数}digit_seen[digit] = true; // 标记该数字出现过num /= 10; // 去掉当前数字}return true; // 所有数字都互不相同
}
​
int countSpecialNumbers(int n) {int count = 0; // 特殊整数计数器for (int i = 1; i <= n; i++) {if (is_special_integer(i)) { // 判断是否为特殊整数count++; // 增加计数}}return count; // 返回特殊整数的数量
}

代码解析:

  1. is_special_integer 函数:

    • 输入一个整数 num 并检查其每位数字是否互不相同。使用一个布尔数组 digit_seen 来记录 0-9 这 10 个数字的出现情况。

  2. countSpecialNumbers 函数:

    • 遍历 1 到 n 的所有整数,调用 is_special_integer 函数来判断该数字是否是特殊的,并更新计数器。

但是此代码的时间复杂度过高,测试用例超过了限定时间,所以要进行优化。

解题思路:

  1. 理解特殊整数:

    • 特殊整数是在其每一位上没有重复的数字(例如,123、456是特殊整数,但 112、121、123 等不是)。

  2. 动态规划 + 记忆化搜索:

    • mask:用于表示当前已经使用的数字,采用位掩码。

    • prefixSmaller:表示当前构建的前缀数字是否小于目标数字的前缀。

    • nStr:将 ( n ) 转换成字符串形式,以便逐位处理各数字。

    • 使用动态规划和哈希表来存储已经计算过的状态,以避免重复计算,提升效率。

    • 状态定义:

  3. 递归函数 (DP):

    • 通过递归函数 dp 实现动态规划,当当前使用的数字数量等于 ( n ) 的位数时返回 1。

    • 对于每个数字,可以根据当前的状态,在允许的范围内选择下一个数字(既 [0,9] 中未被使用的数字)。

    • 通过哈希表 memo 存储计算过的 mask 和 prefixSmaller 的组合,以加速后续计算。

  4. 计算统计:

    • 首先计算位数小于 ( n ) 的所有特殊整数数量;

    • 然后计算与 ( n ) 有相同位数的特殊整数数量。

参考代码如下:

typedef struct {int key;int val;UT_hash_handle hh;
} HashItem; 
​
HashItem *hashFindItem(HashItem **obj, int key) {HashItem *pEntry = NULL;HASH_FIND_INT(*obj, &key, pEntry);return pEntry;
}
​
bool hashAddItem(HashItem **obj, int key, int val) {if (hashFindItem(obj, key)) {return false;}HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));pEntry->key = key;pEntry->val = val;HASH_ADD_INT(*obj, key, pEntry);return true;
}
​
bool hashSetItem(HashItem **obj, int key, int val) {HashItem *pEntry = hashFindItem(obj, key);if (!pEntry) {hashAddItem(obj, key, val);} else {pEntry->val = val;}return true;
}
​
int hashGetItem(HashItem **obj, int key, int defaultVal) {HashItem *pEntry = hashFindItem(obj, key);if (!pEntry) {return defaultVal;}return pEntry->val;
}
​
void hashFree(HashItem **obj) {HashItem *curr = NULL, *tmp = NULL;HASH_ITER(hh, *obj, curr, tmp) {HASH_DEL(*obj, curr);  free(curr);}
}
​
int dp(int mask, bool prefixSmaller, const char *nStr, HashItem **memo) {if (__builtin_popcount(mask) == strlen(nStr)) {return 1;}int key = mask * 2 + (prefixSmaller ? 1 : 0);if (!hashFindItem(memo, key)) {int res = 0;int lowerBound = mask == 0 ? 1 : 0;int upperBound = prefixSmaller ? 9 : nStr[__builtin_popcount(mask)] - '0';for (int i = lowerBound; i <= upperBound; i++) {if (((mask >> i) & 1) == 0) {res += dp(mask | (1 << i), prefixSmaller || i < upperBound, nStr, memo);}}hashAddItem(memo, key, res);}return hashGetItem(memo, key, 0);
}
​
int countSpecialNumbers(int n) {char nStr[64];sprintf(nStr, "%d", n);int res = 0;int prod = 9;int len = strlen(nStr);HashItem *memo = NULL;for (int i = 0; i < len - 1; i++) {res += prod;prod *= 9 - i;}res += dp(0, false, nStr, &memo);hashFree(&memo);return res;
}

代码分析:

1. 哈希表结构与操作
typedef struct {int key;int val;UT_hash_handle hh; // 哈希表的内部处理
} HashItem; 
  • 定义了一个结构体 HashItem,用于存储键值对(key 和 val),并使用 UT_hash_handle 宏,以便利用 uthash 提供的哈希表功能。

  • 哈希表相关操作如下:

HashItem *hashFindItem(HashItem **obj, int key);
bool hashAddItem(HashItem **obj, int key, int val);
bool hashSetItem(HashItem **obj, int key, int val);
int hashGetItem(HashItem **obj, int key, int defaultVal);
void hashFree(HashItem **obj);
  • hashFindItem 查找哈希表的项。

  • hashAddItem 添加项到哈希表,如果已存在则返回 false。

  • hashSetItem 设置某项的值,如果不存在,则插入新项。

  • hashGetItem 获取项的值,若不存在则返回默认值。

  • hashFree 释放哈希表的内存。

2. 动态规划函数 dp
int dp(int mask, bool prefixSmaller, const char *nStr, HashItem **memo) {// 检查当前使用的数字数量是否等于目标字符串的数量if (__builtin_popcount(mask) == strlen(nStr)) {return 1; // 如果是,返回 1,表示成功构造了一个有效的特殊整数}// 生成一个唯一的键以访问缓存int key = mask * 2 + (prefixSmaller ? 1 : 0);// 如果当前状态没有被计算过if (!hashFindItem(memo, key)) {int res = 0;int lowerBound = (mask == 0) ? 1 : 0; // 第一个数字不能是 0// 确定当前可以选择的数字上限int upperBound = prefixSmaller ? 9 : nStr[__builtin_popcount(mask)] - '0';// 尝试选择每一个数字for (int i = lowerBound; i <= upperBound; i++) {if (((mask >> i) & 1) == 0) { // 检查当前数字是否未被使用// 递归调用,加入当前选择并更新状态res += dp(mask | (1 << i), prefixSmaller || (i < upperBound), nStr, memo);}}hashAddItem(memo, key, res); // 缓存当前状态的结果}return hashGetItem(memo, key, 0); // 返回缓存的结果或 0
}
  • dp 函数中,使用 mask 来表示当前使用的数字,利用位运算避免重复。

  • 使用 prefixSmaller 判断当前构造的数字是否小于对应的 ( n ) 的前缀。

  • 计算当前状态下所能构造的特殊整数数量,并将其缓存到哈希表中。

3. 主函数 countSpecialNumbers
int countSpecialNumbers(int n) {char nStr[64];sprintf(nStr, "%d", n); // 将 n 转换为字符串形式int res = 0;int prod = 9; // 可能的数字引导初始值为 9int len = strlen(nStr); // 目标长度HashItem *memo = NULL; // 初始化缓存// 计算所有位数小于 n 的特殊整数的数量for (int i = 0; i < len - 1; i++) {res += prod; // 将当前的数量加入结果prod *= 9 - i; // 更新可能的选择数}res += dp(0, false, nStr, &memo); // 计算与 nStr 长度相同的特殊整数hashFree(&memo); // 释放内存return res; // 返回总结果
}
  • 主函数中,首先将 ( n ) 转为字符串以便逐位处理。

  • 计算所有位数小于 ( n ) 的特殊整数数量。

  • 通过 dp 函数计算与 ( n ) 有相同位数的特殊整数数量。

  • 最后释放内存并返回结果。

总结:

整段代码结合了动态规划与哈希表的缓存机制,优雅地解决了问题:

  • 通过位掩码有效记录已使用的数字。

  • 通过记忆化搜索加速计算,避免重复递归。

  • 提供了高效的方式来计算区间 ([1, n]) 中所有特殊整数的数量,可以适用于较大的数字范围。

这种方法的时间复杂度主要由位数 ( m ) 影响,且结合了组合的计算,通常在实际问题中能够高效运行。

http://www.dinnco.com/news/36773.html

相关文章:

  • 桦南县建设局网站福州seo网站管理
  • 安卓aso关键词优化seo关键词怎么选
  • 做电影网站的流程seo公司 上海
  • 福建省人民政府新闻网络seo是什么
  • 怎么下载四川人社app草根seo视频大全
  • 网站开发企业中国舆情观察网
  • 安阳网站建设哪家专业seo网站快速排名
  • 做食品的网站设计要注意东莞网站建设最牛
  • 温州vi设计公司整站优化提升排名
  • seo营销是什么意思旺道seo推广有用吗
  • 农行网站不出动画怎么做seo营销服务
  • 官网开发seo从0到1怎么做
  • 铁岭手机网站建设关键词排名优化
  • 郑州做网站哪家公司好网络推广方式主要有
  • 做公益的网站有哪些免费网站可以发布广告
  • 21dove谁做的的网站seo基础理论
  • 公司网站重新建站通知学编程的正规学校
  • 品牌建设网站公司排名美食软文300字
  • 21天网站建设实录pdf百度关键词价格
  • 销售型网站如何做推广长沙优化排名
  • 做网站选云服务器内核外贸网站推广与优化
  • 动态网站开发服务器端脚本语言百度榜单
  • 手机网站设计开发电商网络营销
  • 新闻网页设计模板东莞seo搜索
  • 巢湖网站建设公司江东怎样优化seo
  • 高邮建设银行网站关键词林俊杰无损下载
  • 网站的ui规范百度seo排名优化技巧分享
  • b2c模式的电商网站青岛seo关键词优化排名
  • 下载中心软件seo关键词平台
  • 90设计网站免费素材网络营销包括几个部分