我的博客

leetcode 剑指 offer 面试题14- I. 剪绳子 - 一行代码

目录
  1. 解题思路
  2. 代码

解题思路

学习了 @Wilson79题解(本文和他思路基本一致,但他的实现是 O(n))

发现他的方法是可以写成 O(1) 时间的。

一句话代码(附在最后)不好理解,写成多行的:

1
2
3
4
5
6
7
8
9
10
class Solution:
def cuttingRope(self, n: int) -> int:
if n < 4:
return n - 1
if n % 3 == 0: # 都剪成 3
return 3 ** (n//3)
if n % 3 == 1: # 剪一个 4,剩下的都剪成 3 (或者剪两个 2,剩下的都剪成 3)
return 3 ** ((n-4)//3) * 4
if n % 3 == 2: # 剪一个 2,剩下的都剪成 3
return 3 ** ((n-2)//3) * 2

至于为什么这样,Wilson79 的题解已经给出了详细的解释,为什么 3 最好,我再重复一下归纳以后的策略:

剪出长度 1 是不划算的,尽量不要出现 1,实际上只有 n = 2, n = 3 的时候会剪出 1。其余时候一律不剪 1。

然后策略就是优先剪 3, 但是如果剩下的是 4,就不剪了(因为剩下 4 再剪 3,会剩下 1,还不如不剪),如果剩下 2 也没法剪。

代码

1
2
3
class Solution:
def cuttingRope(self, n: int) -> int:
return n-1 if n < 4 else [3**(n//3) , 3**((n-4)//3)*4, 3**(n//3)*2][n%3]

leetcode 剑指 offer 面试题13. 机器人的运动范围

目录
  1. 解题思路
  2. 代码

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

解题思路

由题意知,除了第一个格子外,机器人到所有可去的格子都至少有这两种方法之一: 向下到达、向右到达。
换句话:如果一个格子可达,那么我们肯定可以从他左边的格子向右走一步过去,或者从他上边的格子向下走一步过去。

这么讲,不是排除从下面去或者从左面去。但是这说明我们只看 向下、向右 就够了。

代码中设置了 ln 标记数组,ln[i] 标识上一行 i 位置机器人能不能到达。初始化为全 False

标记 f 记录当前行有没有可到大达的格子,如果当前行一个可以到的都没有,那么后面的行都不用管了,肯定到不了。

标记 f2 记录该格子的左边紧邻的格子能不能到。f2 初始化为 False。

这样一个格子可以到达,有两个条件: 值满足这个规则、他的上面的格子或者左面的格子可达。

代码

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
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
cnt = 0
def getv(n):
v = 0
for ch in list(str(n)):
v += int(ch)
return v
ln = [False for _ in range(m)]
for i in range(n):
v = getv(i)
f = False
f2 = False
nln = [False for _ in range(m)]
if i == 0: f2 = True
for j in range(m):
if getv(j) + v <= k and (f2 or ln[j]):
f = True
f2 = True
nln[j] = True
cnt += 1
else:
f2 = False
ln = nln
if not f:
break
return cnt

调试错误、查看表结构、交易 input,output 数量分布 - 使用 Google Big Query API 处理比特币数据(三)

目录
  1. 报错的 SQL
    1. 获取表 schema
    2. 获取一条数据
    3. 原来 bigquery 有两个不同的比特币数据集
    4. 最终代码与可视化

前面两篇文章:
Kaggle 上的比特币链上数据集 - 使用 Google Big Query API 处理比特币数据(一)
总结了 kaggle 上入门 kernal 的代码

用 SQL 获取 bigquery 比特币数据 - 使用 Google Big Query API 处理比特币数据(二)
使用最简单的 SQL 获取原始数据

报错的 SQL

写了一个统计比特币交易输入输出数量的查询

1
2
3
4
5
6
from google.cloud import bigquery

client = bigquery.Client()
query = "SELECT SUM(output_count), COUNT(1) AS tx_count FROM `bigquery-public-data.bitcoin_blockchain.transactions` as tx GROUP BY output_count"
r = client.query(query)
df = r.to_dataframe()

结果报错:

BadRequest: 400 Unrecognized name: output_count at [1:12]

意思是没有这一列?

我于是回到数据集主页查看,结果发现有这一列。

获取表 schema

参考 notebook

1
2
3
4
5
6
dataset_ref = client.dataset("bitcoin_blockchain", project="bigquery-public-data")
dataset = client.get_dataset(dataset_ref)

# 打印看数据集里所有的表格
for table in client.list_tables(dataset):
print(table.table_id)

blocks
transactions

看到这里就不对了,这个数据集应该是有 4 张表,这里却只有两个,继续看 transactions 表内容吧

1
2
3
4
5
table_ref = dataset_ref.table("transactions")
table = client.get_table(table_ref)
for col in table.schema:
print(col)
print()

SchemaField(‘timestamp’, ‘INTEGER’, ‘NULLABLE’, None, ())

SchemaField(‘transaction_id’, ‘STRING’, ‘NULLABLE’, None, ())

SchemaField(‘inputs’, ‘RECORD’, ‘REPEATED’, None, (SchemaField(‘input_script_bytes’, ‘BYTES’, ‘NULLABLE’, None, ()), SchemaField(‘input_script_string’, ‘STRING’, ‘NULLABLE’, None, ()), SchemaField(‘input_script_string_error’, ‘STRING’, ‘NULLABLE’, None, ()), SchemaField(‘input_sequence_number’, ‘INTEGER’, ‘NULLABLE’, None, ()), SchemaField(‘input_pubkey_base58’, ‘STRING’, ‘NULLABLE’, None, ()), SchemaField(‘input_pubkey_base58_error’, ‘STRING’, ‘NULLABLE’, None, ())))

SchemaField(‘outputs’, ‘RECORD’, ‘REPEATED’, None, (SchemaField(‘output_satoshis’, ‘INTEGER’, ‘NULLABLE’, None, ()), SchemaField(‘output_script_bytes’, ‘BYTES’, ‘NULLABLE’, None, ()), SchemaField(‘output_script_string’, ‘STRING’, ‘NULLABLE’, None, ()), SchemaField(‘output_script_string_error’, ‘STRING’, ‘NULLABLE’, None, ()), SchemaField(‘output_pubkey_base58’, ‘STRING’, ‘NULLABLE’, None, ()), SchemaField(‘output_pubkey_base58_error’, ‘STRING’, ‘NULLABLE’, None, ())))

SchemaField(‘block_id’, ‘STRING’, ‘NULLABLE’, None, ())

SchemaField(‘previous_block’, ‘STRING’, ‘NULLABLE’, None, ())

SchemaField(‘merkle_root’, ‘STRING’, ‘NULLABLE’, None, ())

SchemaField(‘nonce’, ‘INTEGER’, ‘NULLABLE’, None, ())

SchemaField(‘version’, ‘INTEGER’, ‘NULLABLE’, None, ())

SchemaField(‘work_terahash’, ‘INTEGER’, ‘NULLABLE’, None, ())

SchemaField(‘work_error’, ‘STRING’, ‘NULLABLE’, None, ())

还真的没有 output_count

获取一条数据

1
2
3
r1 = client('SELECT * FROM `bigquery-public-data.bitcoin_blockchain.transactions` WHERE transaction_id = "4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b"')
df = r1.to_dataframe()
df.shape

(1, 11)

返回的数据只有 11 列,这和上一篇文章的结果不同。

原来 bigquery 有两个不同的比特币数据集

上篇文章中用到的是:
bigquery-public-data.crypto_bitcoin.transactions
这个是数据集主页提到的

上面出现错误的代码中用的是
bigquery-public-data.bitcoin_blockchain.transactions
是从数据集主页推荐的官方 kernal 中使用的。

这两个数据集无论是表的数量,还是表的结构都有不同。

所以还是使用第一个比较好

最终代码与可视化

1
2
3
4
5
6
7
from google.cloud import bigquery

client = bigquery.Client()
query = "SELECT output_count, COUNT(1) AS tx_count FROM `bigquery-public-data.crypto_bitcoin.transactions` as tx GROUP BY output_count ORDER BY output_count"
r = client.query(query)
df = r.to_dataframe()
r.total_bytes_processed / (1024 ** 3)

3.7562014535069466

1
df

image.png

1
2
s = df['tx_count'].sum()
s

504172778

该数据集有 5 亿交易

1
df['tx_count'][0] / s * 100, df['tx_count'][1] / s * 100 , df['tx_count'][2] / s * 100,

(11.770812822424935, 78.09005467566121, 5.974420340480977)

output_count 为 1、2、3 的交易分别占比 11.77%, 78.09%, 5.97%

数据长尾很明显, 90 以上的交易集中在 1 - 3。所以只画前 10 行的条形图看一下

1
df[:10].set_index('output_count').plot.bar()

image.png

有一个夜晚我烧毁了所有的记忆

目录

自从上次比赛回来到现在,终于又把起床时间调到 7 点左右了。

睁眼看了一下微信看到舅舅 6 点多发的朋友圈:

有一个夜晚我烧毁了所有的记忆,
从此我的梦就透明了。

有一个早晨我扔掉了所有的昨天,
从此我的脚步就轻盈了。

——泰戈尔

我赶紧点了赞,然后从被窝里爬出来,洗漱,买早饭去了。

还记得有一年高考作文题目是什么放下担子,轻装上阵之类的,那时候的我还很讨厌写作文。

我昨天突然想到我的一个问题,我太在乎别人的看法了,我现在做事,往往先考虑别人的看法,然后考虑其他,这很荒谬。这是缺乏勇气的表现。导致的结果是非常严重的。对我做事情是一种无形的阻力。处处受到限制。

另一篇博客

python 字符常量(字面值)- 字符串常量前缀总结

目录

python3 官方文档相关部分:

  1. 文本序列类型 str
  2. 字符串和字节串字面值
  3. PEP 414 – Explicit Unicode Literal for Python 3.3

python 中用单引号或双引号声明字符串常量(二者等价)

用三个连续引号声明跨行字符串,其中所有白空格都会被包含在字符串中。

常见的字符串常量前缀有:

  1. r’’ 原始字符串

    引号内的转义字符不生效,常用于书写正则表达式、windows 下的带反斜杠的路径等。

    如:'C:\\windows\\system32'r'C:\windows\system32' 等价

  2. u’’ unicode 字符串

    用于声明 unicode 字符串

    是 python2 的内容,对于 python3 没有意义,因为 python3 的普通字符串就是 unicode 字符串,本来 python3 中不包括,但是 python3.3 开始为了增强对 python2 代码的兼容性重新引入。

  3. f’’ 格式化字符串

    格式化字符串,如

    1
    2
    3
    x = 'word'
    s = f'hello {x}!'
    print(s)

    将会输出:hello word!

  4. b’’ bytes 序列(这个不算字符串)

    用于声明 bytes 序列。

用 SQL 获取 bigquery 比特币数据 - 使用 Google Big Query API 处理比特币数据

目录
  1. 创建查询对象
  2. 一次查询
  3. 数据格式
    1. transactions 表
      1. 查寻第 50 万块中所有交易

之前写过一篇,主要是总(ban)结(运)了 kaggle 上入门 kernal 的代码:
Kaggle 上的比特币链上数据集 - 使用 Google Big Query API 处理比特币数据

但是实际上这个数据集相关的 kernal 不算很多,很多想要做的东西缺乏参考,需要自己探索。本次文章记录了我探索 bigquery 数据的过程。

创建查询对象

1
2
from google.cloud import bigquery
client = bigquery.Client()

一次查询

一段废话:很久没有写过 SQL 了,第一次写 SQL 是大一自学 PHP 后开发了一个用于统计我们专业期末成绩的网站。结果最终版的代码在 Azure 欠费后还都丢掉了。后来上数据库原理不喜欢那个老师,也没好好学,再后来用 django 都是 orm 了,更写 SQL。后来去中智实习,做 ETL 这是第一次实践中用 SQL 才明白 SQL 有这么强大的能力。但是现在也都忘了。

写个最简单,查询 0 号区块的所有信息。

1
2
3
4
query = """
SELECT * FROM bigquery-public-data.crypto_bitcoin.blocks where number=0
"""
r = client.query(query)

看一下 QueryJob 对象 r 有哪些方法和属性:

1
type(r), dir(r)

(google.cloud.bigquery.job.QueryJob,
[
‘job_id’,
‘job_type’,
‘labels’,
‘location’,
‘path’,
‘query’,
‘query_parameters’,
‘referenced_tables’,
‘state’,
‘table_definitions’,
‘timeline’,
‘to_dataframe’,
‘total_bytes_billed’,
‘total_bytes_processed’,
‘user_email’,
])

有很多,这里就选了一些可能用的着的。
看一下它们的值(这代码是在 kaggle notebook 里输入的,所以不用 print 也能返回结果。)

1
r.state, r.job_id, r.labels, r.location, r.path, r.query, r.referenced_tables, r.state, r.timeline, r.total_bytes_billed, r.total_bytes_processed, r.user_email

(‘DONE’,
‘ee67ed4d-80d4-4abf-bab4-522d33b52438’,
{},
‘US’,
‘/projects/kaggle-161607/jobs/ee67ed4d-80d4-4abf-bab4-522d33b52438’,
‘\nSELECT * FROM `bigquery-public-data.crypto_bitcoin.blocks` where number=0\n’,
[TableReference(DatasetReference(‘bigquery-public-data’, ‘crypto_bitcoin’), ‘blocks’)],
‘DONE’,
[<google.cloud.bigquery.job.TimelineEntry at 0x7faad8e9e860>],
196083712,
196019375,
'data-proxy-public@kaggle-bq.iam.gserviceaccount.com‘)

这些都是一些状态信息之类的,最重要的是数据:
r.to_dataframe 是函数,返回一个 pandas.core.frame.DataFrame 对象。

1
2
df = r.to_dataframe()
df.head()

image.png

至此已经得到比特币原始数据了。

数据格式

这里大致分析一下我们可以在 bigquery 拿到哪些比特币的数据。

一共有 4 个表: blocks、inputs、outputs、transactions

数量集应该是这样:至今(2020 年 2 月 16 日)比特币有 61 万多区块,交易数量估计是 6 亿左右,而输入输出可能有 10 亿。

但是他这个数据并不是最新的。所以没有这么多数据。

这里面最关键的是 transactions 表。

transactions 表

一共 17 列

hash 交易哈希 String
size 交易大小(bytes) Numeric
virtual_size 好像隔离见证交易这个字段会与 size 不同 Numeric
version 协议版本 Numeric
lock_time 矿工可以把交易纳入 Merkel 树的最早时间 Numeric
block_hash 交易属于的块的哈希 String
block_number 交易属于的区块的编号 Numeric
block_timestamp 区块时间戳 Date
block_timestamp_month 区块时间的月 Date
input_count 输入数量 Numeric
output_count 输出数量 Numeric
input_value 输入值总和 Numeric
output_value 输出值总和 Numeric
is_coinbase 是否是铸币交易 Boolean
fee 交易手续费 Numeric
inputs 交易的输入数组 数组
outputs 交易的输出数组 数组

查寻第 50 万块中所有交易

image.png

1
2
3
4
5
6
query = """
SELECT * FROM `bigquery-public-data.crypto_bitcoin.transactions` where block_number=500000
"""
transactions_r = client.query(query)
tx_df = transactions_r.to_dataframe()
transactions_r.total_bytes_processed / (1024 ** 3)

这里显示: 1076.8477526148781 难道查询一个区块的交易就处理的 1 T 多的数据吗?有点奇怪。

可以使用

1
2
3
for i, row in tx_df.iterrows():
print(i, row['hash'], row['block_timestamp'])
break

遍历 dataframe 对象

leetcode 多次求和构造目标数组 1354. Construct Target Array With Multiple Sums

目录
  1. 方法
  2. 代码

中文题目 英文题目

方法

看起来很难,但是找到规律后实现很简单。

因为两个步骤是交替进行的。所以:

  1. 当前数组中最大的一个数必然是当前的 x(代码中的 current_x)。
  2. 数组所有数的和减去这个最大数,就是这次的 x 比上一次 x 增大的增量(inc)。

经过 wangtaoking1 提醒,修改了循环中更新 x 的方法。之前是 x = x - val,现在是 x = x % val。我原来的方法有可能超时,只是测试数据比较弱才侥幸过了。

又得到 zdyxry 的提醒,第二版代码里可能出现 inc == 0 的问题。如果 target 数组长度大于 1, inc 一定大于 0,因为 inc = sum(target) - current_x , traget 中每个元素都大于等于 1,所以 target 的元素和,减去 target 中最大的元素大于 0。
但是如果 target 长度为 1。第二版代码的 inc == 0,改进后的代码出现除 0 错误; 而最初代码陷入死循环。

还是没考虑全,经 @Gorilla 提醒,增加对 current_x % inc 为 0 的判断。(2020 年 3 月 16 日)

代码

第四版代码,增加对 current_x % inc 为 0 的判断。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isPossible(self, target: List[int]) -> bool:
if len(target) == 1: return target[0] == 1
while True:
current_x = max(target)
if current_x == 1:
return True # 最大的数等于 1 了而且数组中无小于 1 的数,那么说明整个数组都是 1,返回 True
idx = target.index(current_x)
inc = sum(target) - current_x
target[idx] = current_x % inc
if inc >= current_x or target[idx] == 0:
return False # inc 大于等于 x,这样将会出现小于 1 的值,不是合法情况,返回 False

第三版代码(在第二版基础上排除了 target 长度为 1 的情况,避免 inc == 0)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isPossible(self, target: List[int]) -> bool:
if len(target) == 1: return target[0] == 1
while True:
current_x = max(target)
if current_x == 1:
return True # 最大的数等于 1 了而且数组中无小于 1 的数,那么说明整个数组都是 1,返回 True
idx = target.index(current_x)
inc = sum(target) - current_x
if inc >= current_x:
return False # inc 大于等于 x,这样将会出现小于 1 的值,不是合法情况,返回 False
target[idx] = current_x % inc

第二版代码(target 长度为 1,且这个元素不等于 1 时, inc 等于 0,发生除零错误)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isPossible(self, target: List[int]) -> bool:
while True:
current_x = max(target)
if current_x == 1:
return True # 最大的数等于 1 了而且数组中无小于 1 的数,那么说明整个数组都是 1,返回 True
idx = target.index(current_x)
s = sum(target)
inc = s - current_x
if inc >= current_x:
return False # inc 大于等于 x,这样将会出现小于 1 的值,不是合法情况,返回 False
target[idx] = current_x % inc

最初代码(有数据会超时,比如 [1, 1000000000])

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isPossible(self, target: List[int]) -> bool:
while True:
cx = max(target)
if cx == 1:
return True
idx = target.index(cx)
s = sum(target)
lv = cx - (s - cx)
if lv < 1:
return False
target[idx] = lv

leetcode 最多可以参加的会议数目 1353. Maximum Number of Events That Can Be Attended

目录
  1. 方法
  2. 代码

英文题目 中文题目

方法

贪心算法。使用优先队列,先从最小的一天开始安排。

策略是按照开始日期分组,每一组(也就是每天)只取一个结束时间最早的(也就是会议长度最短的)。然后这把一组其他的所有其他会议的开始时间修改为下一天,放入优先队列排序。

大致是在这样,但是可以有一些小的优化,比如结束日期就是当前处理的一天的会议就可以直接安排上。因为这个会议安排上一定不会影响后面别的会。

整体的贪心策略就是尽可能安排这一天开一个结束日期最早的会。

代码

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
import queue

class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
q = queue.PriorityQueue()
for e in events:
q.put(e)
e = q.get()
cnt = 1
cd = e[0] + 1
while not q.empty():
e = q.get()
if e[0] == cd:
if e[1] >= cd:
cd += 1
cnt += 1
elif e[0] > cd:
cd = e[0] + 1
cnt += 1
else: # e[0] < cd
if e[1] == cd:
cd += 1
cnt += 1
if e[1] > cd:
e[0] = cd
q.put(e)
return cnt

leetcode 最后 K 个数的乘积 1352. Product of the Last K Numbers

目录
  1. 方法
  2. 代码

英文题目

中文题目

方法

第一可能查询的次数很多,区间也可能很大,如果每次查询都现算可能超时。但是每个数字都不大。

这时候就考虑不存数字本身,而是存连乘后的结果。例如输入的 a b c d。则存的是 a,a×b,a×b×c,a×b×c×d。这样。如果查询最后两个数相乘,就是倒数第一除以倒数第三就是 (a×b×c×d)/ (a×b)= c × d。这样每次查询只需要做一次除法,每次输入只需要做一次乘法。

用 python 的一个优势是,不用考虑整数溢出的问题。

这里还有一个问题没有处理,就是 0。当时没考虑到,但是样例救了我,跑样例除了除零错误。

对于 0 的思路是,每次遇到 0 直接清空列表,因为前面是啥都没用了,只要超过 0 的位置,前面的都是 0 了。

而相应的查询的地方,长度超过列表长度,直接返回 0,因为面前肯定是遇到 0 了。

再一个为了代码方便,直接列表第一个默认自带一个 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class ProductOfNumbers:

def __init__(self):
self.p = [1]

def add(self, num: int) -> None:
if num == 0:
self.p = [1]
else:
self.p.append(self.p[-1] * num)

def getProduct(self, k: int) -> int:
if k >= len(self.p): return 0
return self.p[-1] // self.p[-k-1]

leetcode 统计有序矩阵中的负数 1351. Count Negative Numbers in a Sorted Matrix

目录
  1. 方法
  2. 代码

英文题目 中文

方法

可以行、列都从后往前遍历,遇到非负数就 break。

但是这个数据很少,应该全部遍历也不会超时。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
c = 0
for i in range(n-1, -1, -1):
if grid[i][-1] >= 0: break
for j in range(m-1, -1, -1):
if grid[i][j] < 0:
c += 1
else:
break
return c