两道网测题

发表于
字数统计: 800 words | 阅读时长 ≈ 4 mins

今天主要做了两道online的测试题，用的是CodinGame平台，刚开始Tutorial的给的input和output接口不是很会用摸索了一番，最后直接用sys.stdin()读取输入的数据(即便换行依然可以存入), 然后就是用print直接生成结果(也可以调用sys.stdout.write())

第一题

给定一个范围，寻找幸运数字的个数。
如果一个数包含了’6‘或者’8‘，那么该数为幸运数字，但是如果同时包含了这两个数字，则不算。
举个例子：60和88都算幸运数字，但是68，234， 806这样的都不算。

直接进行简单暴力求解，但是到了后期测试数字变大，超时。

寻求更优的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
## lucky number
from sys import stderr
from time import process_time
from typing import Dict, List


def calculate_possibilities(max):
	"""Calculate the numbers of lucky numbers from 0 to 10**(max - 1)"""
	possibilities: Dict[int, int] = { 0: 0, 1: 2 }
	index: int = 2
	while index < max:
		possibilities[index] = 2 * (9 ** (index - 1)) + 8 * possibilities[index - 1]
		index += 1
	return possibilities


def count(number):
	"""
	Count the lucky numbers from 0 to number with a fast mathematic range.
	"""
	digits = [int(c) for c in str(number)]
	pow_10: int = len(digits) - 1
	possibilities = calculate_possibilities(pow_10 + 1)
	lucky_numbers = 0

	found_lucky_digit = False
	lucky_digit = -1

	for digit in digits:
		if not found_lucky_digit:
			# We're in the classic case.
			if digit == 7:
				lucky_numbers += 6 * possibilities[pow_10] + 9 ** pow_10
			elif digit == 8:
				lucky_numbers += 7 * possibilities[pow_10] + 9 ** pow_10
			elif digit == 9:
				lucky_numbers += 7 * possibilities[pow_10] + 2 * (9 ** pow_10)
			else:
				lucky_numbers += digit * possibilities[pow_10]
		else:
			# Things change now that we know we have a lucky digit before us.
			if digit == 6:
				lucky_numbers += 6 * (9 ** pow_10)
				if found_lucky_digit and lucky_digit != 6:
					# We'll find no more lucky numbers.
					return lucky_numbers

			elif digit == 7:
				if lucky_digit == 6:
					lucky_numbers += 7 * (9 ** pow_10)
				else:
					lucky_numbers += 6 * (9 ** pow_10)

			elif digit == 8:
				lucky_numbers += 7 * (9 ** pow_10)
				if found_lucky_digit and lucky_digit != 8:
					# We'll find no more lucky numbers.
					lucky_numbers += 9 ** pow_10
					return lucky_numbers

			elif digit == 9:
				lucky_numbers += 8 * (9 ** pow_10)
			else:
				lucky_numbers += digit * (9 ** pow_10)

		pow_10 -= 1

		if not found_lucky_digit and (digit == 6 or digit == 8):
			lucky_digit = digit
			found_lucky_digit = True

	return lucky_numbers


l, r = 92871036442, 3363728910382456
start: float = process_time()

if l == r:
	## l and r is the same and only contain '6' or '8' but not the both
	if ('6' in str(l)) ^ ('8' in str(l)):
		print(1)
	else:
		print(0)
else:
	print(count(r+1) - count(l))

第二题

大概因为第一题没有做出来，第二题难度就降低了，比较时间大小。
一个文件里面的时间格式HH:MM:SS，每行表示一个时间记录，找出里面最小的时间。

两种思路，第一是将时间转化为秒数比较大小，第二种就是直接进行排序比较，感觉直接用排序更简单直观，但是脑子抽风了用了第一种解法。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
## way 1
import sys
def get_sec(time_str):
	h, m, s = time_str.split(':')
	return int(h) * 3600 + int(m) * 60 + int(s)

## skip first line 
inputs = set([line.strip() for line in sys.stdin][1:])
result = {get_sec(el):el for el in inputs}
min_diff = get_sec(inputs[0])
for char in result:
	if char <= min_diff:
		min_diff = char 

print(result.get(min_diff))
# print(val for key, val in result.items() if key == min_diff) 

## way 2
import time
timestamp.sort(key=lambda x: time.strptime(x, '%Y-%m-%d %H:%M:%S'))