解题思路

方法一（用 C 写可以 O(1) 空间，原地翻转）

1、去掉 s 头尾和中间多余的空格

"  hello world!  " -> "hello world!"
"a good   example" -> "a good example"

2、反转整个字符串 s，得到字符串 s1

"hello world!" -> "!dlrow olleh"
"a good example" -> "elpmaxe doog a"

3、依次反转 s1 的每个单词

 "!dlrow olleh" -> "world! hello"
"elpmaxe doog a" -> "example good a"

用 char[] 处理。(4ms C风格)，但因为 java 的 s.toCharArray() 会拷贝一份，所以有点慢。用 C 写出来应该会快不少

解题思路

1、对于每个格子 (i, j)，它旋转 4 次 90°以后回到原来的位置。所以可以把(i, j)旋转4次，依次更新4个位置的旋转数据。

1, x, x      x, x, 1      x, x, x      x, x, x     1, x, 1
x, x, x  ->  x, x, x  ->  x, x, x  ->  x, x, x  -> x, x, x
x, x, x      x, x, x      x, x, 1      1, x, x     1, x, 1

2、那么对于第一列，也可以把它旋转 4 次 90°，更新完矩阵最外圈的数据。 这样就留下了内层的 $(N-2)*(N-2)$ 大小的矩阵待处理。

1, 2, x      x, x, 1      x, x, x      x, x, x     1, 2, 1
x, x, x  ->  x, x, 2  ->  x, x, x  ->  2, x, x  -> 2, x, 2
x, x, x      x, x, x      x, 2, 1      1, x, x     1, 2, 1

3、显然，步骤2 留下的内层矩阵可以接着按照 步骤2 的方法递归处理。 （$1*1$ 的矩阵比较特殊，不用旋转，但不影响结果。）

解题思路

思路和数据结构

由于要求 O(1) 的复杂度，那么只有用 hash 才能满足条件。 双向链表usedSeq 按照使用频率存储所有缓存元素，哈希表frequencyMap 快速查找 usedSeq 里的元素。

• DoubleLinkedList usedSeq ： 按照使用频率从低到高存储所有元素，当缓存满了以后，删除这个表的表头元素。保证 put 操作能在 O(1) 的时间内完成。
• private Map<Integer, Node> map： key-value 的缓存，value 存在 Node.value 里。保证 get 操作能在 O(1) 的时间内完成。
• private Map<Integer, Node> frequencyMap： 按照使用频率存储缓存里的元素，指向最后一个频率为 cnt 的节点。加快 get 操作，保证其能在 O(1) 的时间内完成。如果没有这个 hash，那么更新 usedSeq 可能会变成一个 O(N) 的操作。

解题思路

观察可发现，此题的A[i]范围极小（0 <= A[i] < 40000）， 所以可以用一个Hash记录数组里每个元素出现的次数，如果有重复的元素，那么就是需要处理的。

解题思路

解题思路

快排

区间[l, r], 按照pivot 的值分割成两部分。$values_{i-1}=pivot$

解题思路

由于糖果分配符合 $a_{i} = 1,2,3,..., a_{i-1}, a_{i}, a_{i+1}$ 的规律

解题思路

N为枚举的边界，因为最少2个连续整数的和为target，所以N最大为$\frac{target}{2} + 1$， 最大枚举区间为 $[\frac{target}{2}, \frac{target}{2}+1]$

摩尔投票算法

作者：喝七喜 链接：https://www.zhihu.com/question/49973163/answer/235921864 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路

profit[i][stat]： 表示在第i天，状态为 stat 的时候所能获得的最大收益。

解题思路

$F_{sum,n-1}$： 前n-1种硬币组成sum的最少硬币数

关于Maven

最近几天开始看hadoop的代码，hadoop使用maven构建项目，所以顺便看了下maven。感觉这个东西对于开源的项目来说，确实是很有意义的。

5.15暴雪又出现在这个世界祸害人间。至从高三彻夜不眠玩大航海ONLINE以后，我已经快5年没有碰过大型游戏了。但是暴雪的诱惑实在是太大，禁不住引诱，又准备下海了>_<。

有些想法闪过，不记录下来就忘记了，或者激动的想了很久，然后夜不能寐。既然如此，那么就把想法从内存里持久化下来，记录到文字里，然后丢弃出内存，释放宝贵的资源。 又突然想到，这就是所谓的不要过早优化啊。不要一直想着一件事情，如果这件事情发生了会怎么样，如果这样如果那样，简直是杞人忧天。这个世界的变化太快，可变的选择又太多。当然如果可以预见，也就是根据经验这个很大概率发生的事情，那么做好预备措施，其他的事情就留白好了。天要塌下来又如何呢？大不了一死。

行程：

• D1：北京——西宁
• D2：益鑫羊肉午饭——东关大清真寺——西宁——拉萨
• D3：1点到达拉萨——闲逛——某甜茶馆晚饭——闲逛——回旅社和穿珠子的小光头聊天
• D4：布达拉宫——午饭——大昭寺——见驴友——光明甜茶馆——尼泊尔餐——闲逛——楼顶看布达拉宫聊天
• D5：拉萨——八一——石锅鸡——门巴族的故事
• D6：八一——派镇——午饭——徒步——直白村——晚饭——和店主一家唱歌喝酒
• D7：直白村——徒步——派镇——午饭——江边散步——八一——路管局——晚饭
• D8：八一——拉萨——色拉寺——八廓街——烤肉——冈拉梅朵——不知名小酒吧
• D9：拉萨——西宁
• D10：西宁——北京

前言

杨哲已经多次催着我写回忆录了，但是一直都没有时间好好写以下，这次趁着对Blog的兴趣补上。