C语言名题精选百则之最长平台

發表於 2019-03-16

冼镜光老师的《C语言名题精选百则》是我最喜欢的一本算法书, 因为它比较亲民些。大一的时候见到这本书，顿时爱不释手，只是当时水平有限，很多题目做的很吃力，就没有继续做下去了。比较意外的是，这本书印刷的次数竟然很少，有些可惜。还有书中都是用C语言写的，对于专注算法来说，并不是很好，于是决定抽空用Python重写。

已知一个已经从小到大排序的数组，这个数组中的一个平台(plateau) 就是连续的一串相同的元素，并且这一串元素不能再延伸。

例如，在1，2，2，3，3，3，4，5，5，6中1，2.2，3.3.3，4，5.5，6都是平台。试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。

在上面的例子中，3.3.3就是该数组的最长平台。

说明:
这个程序十分简单，但是要编写号却不容易，因此在编写程序时应该考虑下面几点：

使用的变量越少越好
能否只把数组的元素每一个只查一次就得到结果？
程序语句越少越好。

这个问题曾经困扰过 David Gries这位知名的技术机科学家。本题与解答取自David Gries编写的有光程序设计的专著。

解答见pleateau.py

联系作者

加德纳之无解的难题

By robinjia

發表於 2019-03-09

这题来自马丁加德纳的趣味数学，这个号称“无解的难题”的最初形式, 也是流传最广泛的形式如下. 某天, 老师召集了他最聪明的两个学生P和S, 递给每人一张纸条, 然后说, 有两个不小于2的整数x和y,满足x != y, 且x + y < 100. 给P的纸条上写有两个数的乘积p = x * y, 给S的纸条上写有两个数的和s = x + y, 请他们确定这两个数具体的值是多少. 于是P和S进行对话:

P: 我无法确定这两个数是多少.
S: 我知道你无法确定这两个数是多少.
P: 既然这样, 那我知道这两个数是多少了.
S: 既然这样, 那我也知道这两个数是多少了.

请读者根据以上信息确定这两个数是多少.

稍加分析后，可以写出程序用计算机来找答案，当然手算也是可以的。

P: 我无法确定这两个数是多少. 这里说的是乘积p有多种分解，所以无法确定x和y是什么。如28有2 14, 4 7两种分解。
S: 我知道你无法确定这两个数是多少.这里说的是s = x + y中的x和y的乘积都满足条件1，即有多种分解。如11等于2 + 9, 3 + 8, 4 + 7, 5 + 6, 而2 9等于18有2 9, 3 6两种分解 3 8等于24有2 12, 3 8, 4 6三种分解，4 7等于28有2 14, 4 7两种分解, 5 6等于30有2 15, 3 10, 5 6三中分解。
P: 既然这样, 那我知道这两个数是多少了. 这里说的是，在p的所有分解x * y中只有一个x + y满足条件2
S: 既然这样, 那我也知道这两个数是多少了. 这里说的是在s = x + y中，只有一个x * y满足条件3

于是写Python代码如下

# coding:utf-8
from math import sqrt


def pone(p, u):
    c = 0
    for x in range(2, int(sqrt(p)) + 1):
        if p % x == 0 and x + int(p / x) < u:
            c += 1
    return c >= 2


def sone(s, u):
    for x in range(2, int(s / 2)):
        y = s - x
        if not pone(x * y, u):
            return False
    return True


def ptwo(p, u):
    c = 0
    for x in range(2, int(sqrt(p)) + 1):
        if p % x == 0 and x + int(p / x) < u:
            y = int(p / x)
            if sone(x + y, u):
                c += 1
    return c == 1


def stwo(s, u):
    c = 0
    for x in range(2, int(s / 2)):
        y = s - x
        if ptwo(x * y, u):
            c += 1
    return c == 1


if __name__ == "__main__":
    u = 100
    for x in range(2, int(u / 2)):
        for y in range(x + 1, u - x):
            p = x * y
            s = x + y
            if pone(p, u) and sone(s, u) and ptwo(p, u) and stwo(s, u):
                print("x: %d, y: %d, p: %d, s: %d " % (x, y, p, s))

联系作者

show processlist 过滤

By robinjia

發表於 2018-12-06

想对show processlist命令的结果进行过滤，分组操作，不支持。在The INFORMATION_SCHEMA PROCESSLIST Table里可以看到SHOW FULL PROCESSLIST 和 SELECT * FROM INFORMATION_SCHEMA.PROCESSLIST效果是相等的，于是可以在PROCESSLIST表上进行过滤分组操作。

需要对host进行统计 select substring_index(host,’:’ ,1) as server, count(*) from information_schema.processlist group by server;

查询执行时间超过2分钟的线程，然后拼接成 kill 语句 select concat(‘kill ‘, id, ‘;’) from information_schema.processlist where command != ‘Sleep’ and time > 2*60 order by time desc

参考资料

联系作者

无法导入DerBitString错误

By robinjia

發表於 2018-10-11

在安装Python包时，报如下错误

from Crypto.PublicKey import RSA
from Crypto.Util.asn1 import (DerSequence, DerInteger, DerBitString,
    
ImportError: cannot import name 'DerBitString' from 'Crypto.Util.asn1'

在网上只找到ImportError: cannot import name ‘DerBitString’, 评论里说 Could you please try in a new virtualenv? It seems related to your virtualenv.

我使用的是pyenv搭建的Python3.6.2, 报错, 后来同事用virtualenv搭了个Python3.7.0的环境，不会报错。于是试了用pyenv搭建个Python3.7.0的环境，还是报错。于是可以确定是pyenv的原因，用virtualenvwarpper搭了个Python3.6.5的环境，这次没有报错。

用了这么久pyenv, 第一次遇到这种问题，莫名奇妙。

2018年11月23日更新: 发现原因了，是因为PyCrypto包和PyCryptodome有冲突，当只安装PyCrypto时就没有这个问题。事实上，最好使用PyCryptodome这个包，因为它是PyCrypto的替代者，只是这里应用依赖PyCrypto包，所以才用它。

联系作者

Django-REST-framework嵌套序列化过滤

By robinjia

發表於 2018-08-09

有些时候，需要用到嵌套过滤，例如如果要求数据都只是逻辑删除时，此时就会用到。例如有一个应用表，还有一个应用成员表, 如果显示应用详情时，想在一个接口把应用成员一起显示出来，此时就需要过滤掉那些被逻辑删除的成员。

如下定义的application和member

class Application(models.Model):
    """应用"""

    name = models.CharField(max_length=32, help_text='应用名称')
    is_deleted = models.BooleanField(default=False, help_text='是否已删除')
    gmt_create = models.DateTimeField(auto_now_add=True)
    gmt_modify = models.DateTimeField(auto_now=True)

class Member(models.Model):
    """应用成员"""

    application = models.ForeignKey(Application, help_text='应用', related_name='members', on_delete=models.PROTECT, db_constraint=False)
    user = models.ForeignKey(User, help_text='成员', on_delete=models.PROTECT, db_constraint=False)
    is_deleted = models.BooleanField(default=False, help_text='是否已删除')
    gmt_create = models.DateTimeField(auto_now_add=True)
    gmt_modify = models.DateTimeField(auto_now=True)

序列化如下

class MemberSerializer(Serializer):
    '''应用成员 序列化器'''

    class Meta:
        model = Member
        fields = '__all__'
        read_only_fields = ('gmt_create', 'gmt_modify', 'is_deleted')


class ApplicationDetailSerializer(Serializer):
    members = MemberSerializer(many=True)

    class Meta:
        model = Application
        fields = '__all__'
        read_only_fields = ('gmt_create', 'gmt_modify', 'is_deleted')

此时会把应用中逻辑删除掉的用户也查出来，查看How do you filter a nested serializer in Django Rest Framework?得到解答。需要在Meta中添加list_serializer_class, 修改后如下

class DeletedFilterListSerializer(ListSerializer):

    def to_representation(self, data):
        data = data.filter(is_deleted=False)
        return super(DeletedFilterListSerializer, self).to_representation(data)


class MemberSerializer(Serializer):
    '''应用成员 序列化器'''

    class Meta:
        list_serializer_class = DeletedFilterListSerializer
        model = Member
        fields = '__all__'
        read_only_fields = ('gmt_create', 'gmt_modify', 'is_deleted')

如此序列化应用时，就不会把删除掉的应用成员查出来

联系作者

在命令行打开html文件

By robinjia

發表於 2018-08-09

有时候在命令行看到一个html文件，就想在浏览器中打开看看是什么。

此时要么在Finder里找到文件打开，或者在浏览器中用file:// + 文件绝对路径。但总觉得不够好。

今天上午搜索之后，发现Mac下有open命令

于是可以用open -a safari 文件名，或者也可以用open -a Google\ Chrome 文件名打开

故事还没完，在我向同事展示学习到的黑科技时，同事给出了一种更高效的打开方式，按住Command, 点击文件。

联系作者

一个错误的邮箱匹配正则表达式

By robinjia

發表於 2018-08-03

之前同事发来一个邮箱匹配的正则表达式，^([a-z0-9A-Z]+[-|\\.|_]?)+[a-z0-9A-Z]@([a-z0-9A-Z]+(-[a-z0-9A-Z]+)?\\.)+[a-zA-Z]{2,}$，说匹配的时候会卡住, 测试一下re.match("^([a-z0-9A-Z]+[-|\\.|_]?)+[a-z0-9A-Z]@([a-z0-9A-Z]+(-[a-z0-9A-Z]+)?\\.)+[a-zA-Z]{2,}$", "sdfwerwerwerwerwsdfsdfsdfsdfsdfsdf"), 果然卡死。找了很久没发现原因，后来看到浅析ReDoS的原理与实践后，才恍然大悟。([a-z0-9A-Z]+[-|\\.|_]?)+就是(a+)+这种形式, 而(a+)+这种类型的正则匹配时回溯次数特别多，很容易引起正则攻击.

类似的正则有

(a+)+
([a-zA-Z]+)*
(a|aa)+
(a|a?)+
(.*a){x} for x > 10

查看《正则指引》，书中给了一个Python版本的正则表达式。r'^(?!\.)(?![\w.]*?\.\.)[\w.]{1,64}@(?=[-a-zA-Z0-9.]{0,255}(?![-a-zA-Z0-9.]))((?!-)[-a-zA-Z0-9]{1,63}\.)*(?!-)[-a-zA-Z0-9]{1,63}$'

其中@之前的部分是用户名，其长度不超过64个字符，所以是[\w.]{1,64}, 用户名不能以点号开头，所以添加环视(?!.), 同时用户名不能包含连续点号, 所以需要添加环视(?![\w.]*?\.\.)

@后面的部分是主机名，主机名分为很多段，每段长度不超过63，所以是[-a-zA-Z0-9]{1,63}, 且每段不能以横线开头，这一点用环视(?!-)保证，总长度不能超过255，用(?=[-a-zA-Z0-9.]{0,255}(?![-a-zA-Z0-9.]))来保证。主机名可以看做是”段+点号”的重复，所以是((?!-)[-a-zA-Z0-9]{1,63}\.)*, 最后的段必须出现，所以再添加一个(?!-)[-a-zA-Z0-9]{1,63}。

看到晚上很多错误的例子，https://blog.csdn.net/xxm282828/article/details/43549959， https://blog.csdn.net/bug_love/article/details/78799277， https://www.oschina.net/code/snippet_1021818_47946，抄来抄去，都是错的。

联系作者

CSRF匹配失败错误查找

By robinjia

發表於 2018-08-02

同事发了下面一个错误, 让我复现并找到解决的办法。错误原因是www.example.com的前端页面访问后端api.example.com出错。

{
    "detail":"CSRF Failed: Referer checking failed - 
    https://www.example.com/ does not match any trusted origins."
    
}

在CSRF validation does not work on Django using HTTPS中找到类似的错误，但是不知道怎么复现，在Issue with CsrfViewMiddleware and “referer” same_origin checking for secure (https) subdomains中发现有可能是CsrfViewMiddleware检测的原因。

于是才想起来可以用将”does not match any trusted origins”放到Django源码中搜索下，果然是在CsrfViewMiddleware里，于是将一些代码注释掉，知道在settings里配置一下CSRF_TRUSTED_ORIGINS即可，于是添加CSRF_TRUSTED_ORIGINS = [‘example.com’], 问题解决。

整个解决过程现在回想起来有些浪费时间，最有效的方法还是拿关键字到源码中找到对应代码，看看报错原因。

联系作者

Vue单文件组件

By robinjia

發表於 2018-07-13

实现文章列表时，写了如下组件

const axios = require('axios');
var ComponentBlog = {
  props: ['post'],
  template: `
    <div class="blog-post">
      <h3>{{ post.title }}</h3>
      <div v-html="post.content"></div>
    </div>
  `
  }
export default {
  components: {
    'blog-post': ComponentBlog 
  },

但是希望组件能够在其它页面复用，于是放在一个文件中，然后导入进来。在这里，我放在BlogPost.vue中，文件内容如下

<template>
  <div class="blog-post">
    <h3>{{ post.title }}</h3>
    <div v-html="post.content"></div>
  </div>
</template>

然后编写如下代码使用组件

<template>
  <div>
    <blog-post v-for="post in posts" :key="post.id" :post="post"></blog-post>
  </div>
</template>

<script>
import BlogPost from '@/components/BlogPost'
const axios = require('axios');
export default {
  components: {
    BlogPost
  },
  data () {
    return {
      posts: [],
    }
  },
  created() {
      this.fetchPost();
  },
  methods: {
    fetchPost() {
      axios.get('http://127.0.0.1:7001/api/blog/posts/')
        .then(response => {
          console.log(response)
          console.log(this)
          this.posts = response.data.results
        })
        .catch(error => {
          // handle error
          console.log(error);
        })
    }
  }
}
</script>

但是一直报post是未定义的。问过同事后，才知道在Vue文档中，有介绍单文件组件的使用方法。于是将BlogPost.vue改成如下内容

<template>
  <div class="blog-post">
    <h3>{{ post.title }}</h3>
    <div v-html="post.content"></div>
  </div>
</template>

<script type="text/javascript">

export default{
  props: {
    post: Object
  },
  data(){
    return {
    }
  },
  created(){
  },
  methods: {
  },
}
</script>

这样之后，组件就可以正常使用了。

联系作者

vue-router去除#

By robinjia

發表於 2018-07-12

在使用vue-router时，URL中总会有多了个#, 看着总是不爽，而且多了这个符号，以前被搜索引擎收录的页面就无法访问了，于是想办法去除。在Vue的文档中HTML5 History 模式找到了解答，也就是添加history模式即可。

const router = new VueRouter({
  mode: 'history',
  routes: [...]
})

看到警告中说，这么做以后，服务器就不再返回 404 错误页面，因为对于所有路径都会返回 index.html 文件。为了避免这种情况，你应该在 Vue 应用里面覆盖所有的路由情况，然后在给出一个 404 页面。

const router = new VueRouter({
  mode: 'history',
  routes: [
    { path: '*', component: NotFoundComponent }
  ]
})

阿龙的学习笔记

兼济天下则达,独善其身则穷

C语言名题精选百则之最长平台

联系作者

加德纳之无解的难题

联系作者

show processlist 过滤

参考资料

联系作者

无法导入DerBitString错误

联系作者

Django-REST-framework嵌套序列化过滤

联系作者

在命令行打开html文件

联系作者

一个错误的邮箱匹配正则表达式

联系作者

CSRF匹配失败错误查找

联系作者

Vue单文件组件

联系作者

vue-router去除#

联系作者