菜单 学习猿地 - LMONKEY

ARTS-WEEK-019

sinchang profile image sinchang ・1 min read

Algorithm:

53: Maximum Subarray

对无后效性的理解:逻辑、条件和限制都要体现在某种设计的状态中,并且后续的状态都从前面已有状态中转换得出,不能依赖其他内容(如果依赖也要设计到状态中),已经有的状态不会被后面的状态所改变(后面的会用前面的但不会改变前面的),有时存在状态压缩技巧,看似会改变前面的状态,但是其实是因为前面的不需要复用,在用后用完即弃,只保留了最后状态,也不是改变前面的导致重新推导等情况。

这一题一开始尝试设计状态dp[n]是截止n的最大和,写出 dp[n] = max(dp[n-1], dp[n-1] + nums[n]),但是这是错误的,它把连续这一条件破坏了,结果是不连续的最大和。重新思考把 dp[n] 设计为截止并且包含n的最大和,这时方程如下,这里面表达出了 dp[n] 可能以当前点重新开始,当前点必须包括,连续性在这里体现。

if dp[n-1] > 0
 dp[n] = dp[n-1] + nums[n]
else
 dp[n] = nums[n]

152: Maximum Product Subarray

这题状态定义为包含nums[i]的最大(和最小)的数,这里有三个关键:

  1. 是必须包含当前这个数
  2. 并且可以不包含前面的数
  3. 同时有两个状态最大值和最小值(而不是正负)

因为(1)如果可以不包含当前这个数,那就等同于nums[i-1]了,该状态就没有意义了,而(2)可以不包含前面的数则没有这个问题,体现了该dp定义的最大和最小概念,最后(3)dp中不需要考虑正负,是数学知识,不管正负只管大小就够用了。

空间优化的技巧总结,也叫表格复用,包括滚动数组(只用一行或两行)、滚动变量(一行也不用),不同题目用到的不同,注意不要提前覆盖还需要使用的状态。

120: Triangle

空间优化部分很典型,滚动数组的关键是识别不再需要的状态以及避免需要的状态被覆盖,因此倒着遍历就是这时的一个重要手段(两种都能用到但实施点不同),最后做完两种做法后可以看出一种更加简洁,即三角形从大的向小的方向转移,状态天然越来越少,更易处理。

Review:

Paper: The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform

京东图片搜索系统的工程论文,主要介绍了图片搜索系统设计和实时性能优化方面的内容,比较重点的有全量索引(按周进行近期图片补充)和增量索引(实时消息触发)流程、正排索引(图片编号到商品属性的索引)、倒排索引(图片特征到图片编号列表的索引列表 inverted list,图片提取出的特征用近邻算法属于哪一个类别或中心点)、三层架构(请求处理和结果排序返回、图片分区并行搜索、中间代理层)。

Tip:

如何避免文件名中的空格影响?

比如下面前者会因为空格失败,后者就可以避免

find . -type f | xargs md5
find . -type f -print0 | xargs -0 md5

因为xargs默认使用空格TAB换行分割记录,有空格会被当作两个文件,find的-print0可以让find在打印文件名后用NULL字符取代换行符分割,xargs的-0也是用NULL取代换行符分割,这样就不会被空格困扰。

其他需要注意的还有常用的循环处理中,也会出现该问题,这时最好使用 IFS 变量,替换分隔符。

SAVEIFS=$IFS
IFS=$(echo -en "\n\b")
for f in `ls .`
do
  echo $f
done
IFS=$SAVEIFS

Share:

如何独立思考

http://www.paulgraham.com/think.html

作者首先给出了关于一些独立思考的有趣现象,比如不同的工作对独立思考有着显著不同的需求、独立思考难以培养、容易高估自己的独立思考的倾向性等。

第二部分作者提出一些改善手段,比如减少了解常规的信念和思维、和有独立思想的人做朋友、和不同思想的人交流、阅读历史和将自己代入其中、培养质疑的态度、寻找错误观点的游戏、避免未经检查的想法等,还提到了有趣的一点,流行的知识(intellectual fashions)就像流行时装一样,要去寻找未经发现的观点。

最后从另一角度分析了独立思考的三个要素,对真相(truth)洁癖、抗拒被指手画脚(told what to think)、好奇心(curiosity),而这些更多是一种本能和习惯方面的内容。

评论 (0)