• Home
  • About
    • Sybil photo

      Sybil

      Sybil's blog.

    • Learn More
    • Email
    • Github
    • Weibo
  • Posts
    • All Posts
    • All Tags
  • Projects

All Posts

  • 151. 翻转字符串里的单词,O(1)空间

    解题思路

    方法一(用 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 写出来应该会快不少

    Read More 10 Apr 2020
  • 面试题 01.07. 旋转矩阵,递归,不使用额外空间

    解题思路

    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°,更新完矩阵最外圈的数据。 这样就留下了内层的 大小的矩阵待处理。

    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 的方法递归处理。 ( 的矩阵比较特殊,不用旋转,但不影响结果。)

    Read More 07 Apr 2020
  • 460. LFU缓存,hash+双向链表 O(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) 的操作。

    Read More 06 Apr 2020
  • 945. 使数组唯一的最小增量,贪心 O(max(A_i))

    解题思路

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

    Read More 22 Mar 2020
  • 365. 水壶问题,BFS O(XY)

    解题思路

    Read More 21 Mar 2020
  • 面试题40. 最小的k个数, 快排|大根堆

    解题思路

    快排

    区间[l, r], 按照pivot 的值分割成两部分。

    Read More 20 Mar 2020
  • 1103. 分糖果,一元二次方程O(num_people)

    解题思路

    由于糖果分配符合 的规律

    Read More 18 Mar 2020
  • 面试题57 - II. 和为s的连续正数序列, 暴力枚举+滑动窗口

    解题思路

    N为枚举的边界,因为最少2个连续整数的和为target,所以N最大为, 最大枚举区间为

    Read More 18 Mar 2020
  • 229. 求众数II,摩尔投票O(n)

    摩尔投票算法

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

    Read More 18 Mar 2020
  • 309. 最佳买卖股票时机含冷冻期,动态规划O(N)

    解题思路

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

    Read More 17 Mar 2020
  • 322. 零钱兑换,动态规划

    解题思路

    : 前n-1种硬币组成sum的最少硬币数

    Read More 17 Mar 2020
  • 搭建maven repo私服

    关于Maven

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

    Read More 19 Nov 2012
  • 新玩具

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

    Read More 21 May 2012
  • 适可而止

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

    Read More 17 May 2012
  • 西藏四月

    行程:

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

    Read More 23 Apr 2012
  • 我的ACM回忆录

    前言

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

    Read More 18 Apr 2012