算法
从1到abcdef,c位1的个数sum分为2部分:
sum += abc * 1000
if c > 1: sum += 1000; if c == 1: sum += def + 1
时间复杂度: O(log(n))
空间复杂度: O(1)
C++代码
class Solution {
public:
static int numberOf1Between1AndN_Solution(const int n) {
int sum = 0;
int ab = n;
int def = 0;
int digit = 1;
while (ab) {
const int c = ab % 10;
ab /= 10;
sum += ab * digit;
if (c > 1) {
sum += digit;
} else if (c == 1) {
sum += def + 1;
}
def += c * digit;
digit *= 10;
}
return sum;
}
};
Java代码
class Solution {
static public int numberOf1Between1AndN_Solution(final int n) {
int sum = 0;
int ab = n;
int def = 0;
int digit = 1;
while (ab > 0) {
final int c = ab % 10;
ab /= 10;
sum += ab * digit;
if (c > 1) {
sum += digit;
} else if (c == 1) {
sum += def + 1;
}
def += c * digit;
digit *= 10;
}
return sum;
}
}
Python3代码
class Solution(object):
@staticmethod
def numberOf1Between1AndN_Solution(n):
sum = 0
ab = n
def1 = 0
digit = 1
while ab > 0:
c = ab % 10
ab //= 10
sum += ab * digit
if c > 1:
sum += digit
elif c == 1:
sum += def1 + 1
def1 += c * digit
digit *= 10
return sum
谢谢大家的支持。2024年了。
谢谢大家的支持。2020年的前几个月沉迷游戏了。从6月份开始,戒游戏,学算法。
x=’‘
for i in range(1,200):
x=x+str(i)
list_x=list(x)
list_y=[]
for i in list_x:
i=int(i)
if i ==1:
list_y.append(i)
y=len(list_y)
print(y)
这不更简单吗
TQL
加油
牛逼
........
TQL
干净利落啊
tql