ACM题解 – 经典0/1背包问题
0/1背包问题是非常经典的算法问题. 要求是: 给定 n 个物件, 每个物件的重量(或体积)是 A 那么请问一个最多装重(或体积) m 的背包最多可以装下多少这些物件. 如果用数学表示这个问题: max(sum(j * A)) subject to: j = {0, 1} and sum(j * A) <= m where 0 =< …
Category: 程序设计
ACM 解题报告 – O(n)找多数算法
给定一些整数, 请找出它们中的的”多数”. 一个数字如果超过了一半, 那么它就是多数. 假定这样的数是存在的. 比如, 给定 , 您的算法将给出 答案 1 因为1出现了4次超过了一半(3.5次) 最直接的算法就是通过 字典(或者HASHMAP)记录每个出现数字的次数, 然后只要判断其中一个出现超过一半了, 就返回它. class Solution { public: /* * @param nums: a list of integers * …
ACM题解系列之 – 最小堆栈 (Min Stack)
没事刷刷题能防止老年痴呆, 而且也能让你随时处于最佳状态, 随时都可以炒老板鱿鱼另谋高就. 题目: 设计一个堆栈(Stack)使 push, pop, 和取最小 min 操作时间复杂度都是 O(1). 这题的难点就是在于怎么样用O(1)常数时间复杂度来取得堆栈里的最小值. class MinStack { public: MinStack() { // write your code here } /* * @param number: An …
用异步来提高性能 (SteemIt)
我注意到一些STEEMIT在线工具返回数据很慢, 特别是当返回的数据很多行时, 经常需要等个几十秒, 非常的不友好. 比如, 现有138人代理给YY银行, 通过 这个代理查询工具 则需要几十秒才能返回数据. 今天我稍微研究了一下, 发现在使用 steem-python中的 converter 特别的慢. steem = Steem(nodes = steem_nodes) converter = Converter(steemd_instance = steem) while some loop: r.append( "sp": …
使用AWK来估计您下次出块还需要多久? (SteemIt)
上次我们用了一个LINUX命令AWK 结合管道来显示STEEMIT每次出块的间隔和时间: docker logs | grep "Generated" | awk '{cur=substr($8,2);if (NR>1){print "blocks=",cur-prev," hours=",(cur-prev)*3/3600}prev=cur;}' 今天我们稍微修改一下, 这样就能显示每次出块的时间, 还有距离上次的块数和小时数. 并且在最后显示距离下次出块大约需要多少时间(这是根据你最近一次出块需要时间和已经过去多久计算而得的) 当然, 你需要安装 gawk, 这是awk 的GNU版本, 安装(sudo apt-get install gawk)后 命令awk则回通常被链接到 gawk 完整的命令如下: …
使用AWK来看见证人生成块的速度
每次见证人出块, 媳妇总我说 “又生了”. 每次出块我总会去算一下离上次出块多少时间, 这是可以通过当前块数和上次出块数算出来的. 首先, 我们可以通过 docker logs 来显示很多很多的记录: 有一个脚本 ./run.sh logs是显示最近几条记录 (tail) 我们可以通过管道 grep “Generated” 列出出块时候的记录. 然后我们就可以通过AWK来处理文本了, 比如 $8 返回第8列, 我们就可以算出每次出块的间隔, 然后已知每3秒STEEM产生一个块, 这样我们就知道时间了. NR 表示行号, substr($8, 2) …
通过程序来减少到交易所转帐出错的可能
虽然现在在STEEMIT上转帐到交易所的时候如果没有填写 MEMO, 是会提示的, 但是有时候你手快, 可能把你的帐号地址给复制过去然后就点发送了, 这时候就悲剧了. 很久之前, 我误操作100 SBD到 @blocktrades 就是把MEMO填成帐号地址了, 幸运的是通过各方途径联系了官方, 几个小时内收到了退款. 但是别的交易所, 如 bittrex 可能就不是这么的幸运了, 转帐转错了有时候权当捐款了. 是不是每次转帐的时候都提心吊胆, 生怕转没了? 其实你只要懂一点程序, 完全可以通过程序的方式来转帐, 程序只要调通了第一次, 之后再执行出错的可能性几乎没有了. 比如, 我的自动转帐脚本如下 (Python) from steem …