fvdcx's blog


  • 首页

  • 分类

  • 关于

  • 归档

  • 标签

leetcode-group-anagrams

发表于 2016-12-12   |   分类于 算法 , leetcode   |  

题目大意

  https://leetcode.com/problems/anagrams/

  给你字符串数组,我们规定字符顺序变换的字符串为一组,输出所有组。

题目分析

  利用HashMap,key为字符串排序后的结果(这样才能字符顺序不同的字符串的key值相同),value就是字符串数组就行。因此计算key的开销就是len * log(len),len为字符串的长度。看了disscuss区最优解法,由于字母只有26个,因此映射成26个素数,用素数的乘积做为key,也可以保证key的唯一合理性。下面贴出了我的原始的做法。

阅读全文 »

优先级队列

发表于 2016-12-11   |  

优先队列

参考了《挑战程序设计竞赛》 第二版 P71 2.4.2 优先队列和堆的部分

概念

  能高效地完成下列操作的数据结构叫优先队列

  • 插入一个值
  • 取出最小值(获得数值,并删除)

  能够利用二叉树满足上述问题,通常也叫堆,堆是一颗二叉树,满足子节点的值不小于父节点的值。在堆中插入一个数值,可以简单的证明,上述两种操作的时间复杂度都是跟树的高度成正比,简略证明如下

  • 插入一个值:将插入的值放在堆的最后节点上,该节点不断的与父节点调整(如果需要的话),直至树根
  • 取出最小值:最小值即为树根,取出以后,将堆的最后一个节点放在树根,此时有可能不是堆了,因此从树根元素开始不断交换(如果需要的话),直至最底层
阅读全文 »

leetcode-unique-substrings-in-wraparoud-string

发表于 2016-12-11   |   分类于 算法 , leetcode   |  

题目大意

  https://leetcode.com/problems/unique-substrings-in-wraparound-string

  字符串s可以认为“a……za……”的无限循环,给你一个字符串p,问p中有多少个子串也是s的子串

题目分析

  思路参考了这里https://discuss.leetcode.com/topic/70658/concise-java-solution-using-dp。动态规划,注意到字母个数一共就26个,想求总和,可以求以每个字符‘a’-‘z’结尾的字符串的个数(一定没有重复),求其总和即为所求。其实求以’a’-‘z’开头的也可以。

阅读全文 »

leetcode-kth-smallest-element-in-a-sorted-matrix

发表于 2016-12-11   |   分类于 算法 , leetcode   |  

题目大意

  https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

  矩阵每行和每列都是从小到大排好序的,求第k小的元素

题目分析

  本题可以使用堆,但是最优的方法是二分答案法,答案的区间就是在matrix[0][0]到matrix[n-1][n-1]之间,本题等价于求matrix中排序小于等于k的最大值,因此check方法就是求:如果v在matrix排序小于等于k就返回true,否则返回false。注意check方法中v和matrix[i][j]比较的处理,三种情况都要分别算,还有matrix中实际上会有重复的元素,check检测的是值为v的元素在matrix中排序以后的最小排名小于等于k就返回true

阅读全文 »
1…222324…38
fvdcx

fvdcx

149 日志
14 分类
20 标签
GitHub
© 2015 - 2017 fvdcx
由 Hexo 强力驱动
主题 - NexT.Pisces