[关闭]
@natsumi 2017-04-01T07:15:26.000000Z 字数 5380 阅读 1353

LeetCode中神奇的算法

Algorithms


1. 找Majority element的Moore voting算法

Moore的主页上有这个算法的介绍:
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
Moore's voting algorithm:
http://blog.csdn.net/chfe007/article/details/42919017

【注意】最后剩下的元素也可能并没有出现半数以上。比如说数组是[1, 2, 3],最后剩下的3显然只出现了1次,并不到半数。排除这种情况的方法也很简单,只要保存下原始数组,最后扫描一遍验证一下就可以了。

2. Bit Manipulation

n = n & (n-1)
这个运算可以将n中最低的“1”bit变为0

3. in-place的数组标记

problem 448: Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

思路是建立一个可逆的映射函数f,且定义域和值域不相交。
当数字x出现时,令nums[x-1] = f(x)
经过一轮遍历后,nums数组中超出定义域范围的元素的index+1就是消失的元素
下面是top solution中的两种不同的映射方法~
一个是给元素+n,一个是取反~

  1. public List<Integer> findDisappearedNumbers(int[] nums) {//15ms beat 85.16%
  2. List<Integer> res = new ArrayList<>();
  3. int n = nums.length;
  4. for (int i = 0; i < nums.length; i ++) nums[(nums[i]-1) % n] += n;
  5. for (int i = 0; i < nums.length; i ++) if (nums[i] <= n) res.add(i+1);
  6. return res;
  7. }
  1. public List<Integer> findDisappearedNumbers(int[] nums) {
  2. //传说中2ms的方法~跑了一次23ms一次19ms~leetcode的运行时间真是玄学~
  3. List<Integer> result = new ArrayList<Integer>();
  4. for( int i=0;i< nums.length; i++){
  5. int index = nums[i];
  6. if(nums[Math.abs(index)-1] > 0){
  7. nums[Math.abs(index)-1]= -nums[Math.abs(index)-1];
  8. }
  9. }
  10. for(int j =1 ;j <= nums.length ; j++){
  11. if(nums[j-1] > 0){
  12. result.add(j);
  13. }
  14. }
  15. return result;
  16. }

4. count primes

Problem 204 count primes
Count the number of prime numbers less than a non-negative number, n.

原题后面给了Hint
https://leetcode.com/problems/count-primes/?tab=Description

最高效的筛选质数的方法是埃拉托色尼筛选法the Sieve of Eratosthenes

埃拉托色尼筛选法 from 百度百科
(1)先把1删除(现今数学界1既不是质数也不是合数)
(2)读取队列中当前最小的数2,然后把2的倍数删去
(3)读取队列中当前最小的数3,然后把3的倍数删去
(4)读取队列中当前最小的数5,然后把5的倍数删去
(5)如上所述直到需求的范围内所有的数均删除或读取
注:此处的队列并非数据结构队列,如需保留运算结果,处于存储空间的充分利用以及大量删除操作的实施,建议采用链表的数据结构。

埃拉托色尼筛选法图解

如果读取的当前队列中最小的数是p,则我们找p的倍数的时候从开始找起就可以了。因为小于的p的倍数(其中),都已经再我们读取q(或q的因子)并删除q(或q的因子)的倍数时被删去了。

注意题目中要找所有小于n的质数个数,也就是说队列中最大的数是n-1
同理当我们读取到第一个大于的数m后,由于,队列中已经没有可以删的m的倍数了。于是m以及所有大于m且未被删除的数字就都是质数了。

  1. public class Solution {
  2. public int countPrimes(int n) {//23ms beats 92.51%
  3. if(n<3){
  4. return 0;
  5. }
  6. boolean[] notPrime = new boolean[n];
  7. int count = 0;
  8. int limit = (int)Math.sqrt(n-1);
  9. int i,j;
  10. for(i = 2; i<=limit;i++){
  11. if(!notPrime[i]){
  12. count++;
  13. for (j = i * i; j <= n; j += i)
  14. notPrime[j] = true;
  15. }
  16. }
  17. }
  18. while(i<n){
  19. if(!notPrime[i]){
  20. count++;
  21. }
  22. i++;
  23. }
  24. return count;
  25. }
  26. }

5. 回文链表

Problem234
判断链表的val是不是回文
如何能做到O(n) time和O(1) space呢?
Discuss中有这样一个方法。思路是两链表的前半段翻转,然后前半段和后半段顺序比较。找中点的方法是加一个二倍速移动的指针fastPointer,当fastPointer移动到链表结尾时,正常速度的指针如head2就移动到中间位置。
注意细节:偶数个节点的链表翻转后,以6个节点为例[3,2,1,4,5,6],head1指3,head2指4
奇数个节点的链表翻转后,以5个节点为例[3,2,1,4,5],head1指3,head2指4,需要经head1向后移动一个节点到2处再进行比较。

  1. public boolean isPalindrome(ListNode head) {//2ms beats 36.77%
  2. if(head == null){
  3. return true;
  4. }
  5. ListNode head1 = head;
  6. ListNode head2 = head.next;
  7. ListNode fastPointer = head;
  8. ListNode pre = head;
  9. //find mid pointer, and reverse head half part
  10. while(fastPointer.next!=null && fastPointer.next.next!=null){
  11. head1 = head2;
  12. head2 = head2.next;
  13. fastPointer = fastPointer.next.next;
  14. head1.next = pre;
  15. pre = head1;
  16. }
  17. //odd number of elements, need left move head1 one step
  18. if(fastPointer.next == null){
  19. head1 = head1.next;
  20. }
  21. //compare from mid to head/tail
  22. while(head2!=null){
  23. if(head1.val != head2.val){
  24. return false;
  25. }
  26. head1 = head1.next;
  27. head2 = head2.next;
  28. }
  29. return true;
  30. }

6. 有环链表

判断链表是否有环。要求Space O(1)。思路看注释。
Problem141

  1. /**
  2. * Use two pointers, walker and runner.
  3. * walker moves step by step. runner moves two steps at time.
  4. * if the Linked List has a cycle walker and runner will meet at some
  5. * point.
  6. *
  7. * @param head head of the LinkedList
  8. * @return true if the LinkedList has cycle; false otherwise.
  9. */
  10. public boolean hasCycle(ListNode head) {
  11. if (head == null) return false;
  12. ListNode walker = head;
  13. ListNode runner = head;
  14. while (runner.next != null && runner.next.next != null) {
  15. walker = walker.next;
  16. runner = runner.next.next;
  17. if (walker == runner) return true;
  18. }
  19. return false;
  20. }

7. 模式匹配

Problem28
https://leetcode.com/problems/implement-strstr/?tab=Description

一开始用的BF算法超时了。超时的测试用例是haystack和needle等长而且都巨长,haystack全是'a',needle除了最后一个是'b'其他全是'a'
长度先判断一下比较好

  1. public int strStr1(String haystack, String needle) {//BF 15ms beats 18.53%
  2. for (int i = 0; ; i++) {
  3. for (int j = 0; ; j++) {
  4. if (j == needle.length()) return i;
  5. if (i + j == haystack.length()) return -1;
  6. if (needle.charAt(j) != haystack.charAt(i + j)) break;
  7. }
  8. }
  9. }

本来以为BF根本AC不了。。于是学了学KMP
很多参考了这篇文章。讲的很清楚。代码是JAVA的。
详细解读KMP模式匹配算法
http://blog.csdn.net/fightlei/article/details/52712461

  1. public static int strStr2(String haystack, String needle) {//O(m+n) KMP算法 21ms beats 5.54%
  2. if (needle.length() == 0) {
  3. return 0;
  4. }
  5. int i = 0;
  6. int j = 0;
  7. //得到next数组
  8. int[] next = getNext(needle);
  9. while (i < haystack.length() && j < needle.length()) {
  10. if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
  11. i++;
  12. j++;
  13. } else {
  14. //根据next数组的指示j进行回溯,而i永远不会回溯
  15. j = next[j];
  16. }
  17. }
  18. if (j == needle.length()) {
  19. return i - j;
  20. } else {
  21. return -1;
  22. }
  23. }
  24. public static int[] getNext0(String t) {
  25. int[] next = new int[t.length()];
  26. next[0] = -1;
  27. int suffix = 0; // 后缀
  28. int prefix = -1; // 前缀
  29. while (suffix < t.length() - 1) {
  30. //若前缀索引为-1或相等,则前缀后缀索引均+1
  31. if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
  32. ++prefix;
  33. ++suffix;
  34. // prefix表示对于子串T[0]~T[suffix-1]前面有prefix个字符与
  35. // 后面prefix个字符相等,就是next[suffix]
  36. next[suffix] = prefix;
  37. } else {
  38. prefix = next[prefix]; //2
  39. }
  40. }
  41. return next;
  42. }
  43. public static int[] getNext(String t) {//比getNext0更好
  44. int[] next = new int[t.length()];
  45. next[0] = -1;
  46. int suffix = 0; // 后缀
  47. int prefix = -1; // 前缀
  48. while (suffix < t.length() - 1) {
  49. //若相等或前缀索引为-1,则前缀后缀索引均+1
  50. if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
  51. ++prefix;
  52. ++suffix;
  53. //改进的地方
  54. if (t.charAt(prefix) == t.charAt(suffix)) {
  55. next[suffix] = next[prefix];
  56. } else {
  57. next[suffix] = prefix;
  58. }
  59. } else {
  60. prefix = next[prefix];
  61. }
  62. }
  63. for (int n : next) {
  64. System.out.print(n + " ");
  65. }
  66. return next;
  67. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注