[LeetCode][233]数字 1 的个数

2024-03-30 06:20
文章标签 leetcode 个数 数字 233

本文主要是介绍[LeetCode][233]数字 1 的个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

233. 数字 1 的个数

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

  • 示例 1:

输入:n = 13
输出:6

  • 示例 2:

输入:n = 0
输出:0

  • 提示:
    0 <= n <= 10^9

解法1:

  1. 这种题其实就是找规律,类似于数学归纳法,找出一个计算通式可以在给出任意值时计算到目标结果
  2. 这道题我选择从高位往低位统计
  3. 首先找规律,得出不同位数1出现的次数:0位0次,1位(0-9)1次,2位(0-99)20次…
  4. 然后从高位开始,例如123从高位开始,依次处理 100、20、3。
  5. 100包含了0-99,有20个1,20包含了12个1,3包含了1个1
  6. 而123后面的23又为百位上的1多加了24个1,即100-123百位上共24个1,这个也要统计

class Solution {
public:int countDigitOne(int n) {if(!n) return 0;vector<int> count(10, 0);for(int i=1; i<=9; ++i){//统计不同位数的1出现的次数,0位0次,1位(0-9)1次,2位(0-99)20次...count[i]=i*pow(10, i-1);}// for(auto &ele:count) cout << ele << endl;int numDigits = (int)log10(n) + 1; // 获取数字的位数cout << numDigits << endl;int ans=0;for (int i = numDigits-1; i >= 0; i--) {//从高位开始统计int powerOf10 = (int)pow(10, i);int digit = n / powerOf10; // 获取当前位的数字if(digit==0) continue; //处理类似102这种情况中间的0ans+=digit*count[i];n %= powerOf10; // 移除当前位//如123,23让1多出现了24次(100-123),而423是百位上的1固定出现了100次(101-199)digit<=1 ? ans=ans+n+1 : ans+=powerOf10; }return ans;}
};

解法2:

  1. 另一种解法是统计当前位上,1出现了多少次
  2. 当当前位上为0时,其出现1的次数由高位确定,如1203,十位上1出现的次数由十位以上确定,此处出现了12*10=120次
  3. 当当前位上为1时,其出现1的次数为高位+低位共同确定,如1213,出现了12*10+3+1=124次
  4. 当当前位上位2-9时,其出现1的次数也只由高位确定,如1243,十位上1出现次数为 (12+1)*10=130次

class Solution {
public:int countDigitOne(int n) {long currentDigit = 1; // 当前位的权值,最低位开始int high = n / 10, cur = n % 10, low = 0, count = 0; // 初始化高位、当前位、低位、结果个数while (high != 0 || cur != 0) {if (cur == 0) {// 当前位为0时,结果由高位决定count += high * currentDigit;} else if (cur == 1) {// 当前位为1时,结果由高位和低位共同决定count += high * currentDigit + low + 1;} else {// 当前位大于1时,结果由高位决定count += (high + 1) * currentDigit;}// 更新低位并跳到下一位low += cur * currentDigit;cur = high % 10;high /= 10;currentDigit *= 10; // 更新位数权值}return count;}
};

这篇关于[LeetCode][233]数字 1 的个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/860709

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return