前言

这是用来记录在刷LeetCode时遇到的一些问题的技巧，因只记录一些技巧或优化方案故不一定全部记录，自认为的最佳方案已添加+前缀。另可通过搜索题号查看相关问题。

---

题表

【1】. 两数相加
简要介绍：给定一个数组与一个目标数字，在该数组中寻找两个数，使其和等于目标，返回其下标数组
给定条件：题目必定有解，且每个数至多使用一次

• 暴力遍历：两重循环，简单不解释。时间复杂度O(n^2)，空间复杂度O(1)
• 排序二分：第一遍排序，第二遍二分查找，实现复杂。时间复杂度O(nlogn)，空间复杂度依赖于排序算法。
• +哈希索引：借助哈希表，可一次遍历解析，实现简单。假设哈希效率高，单次查找为O(1)，则时间复杂度可视为O(n)，空间复杂度O(n)

【28】. 实现经典的strstr()方法
简要介绍：给定base字符串以及need字符串，要求在前者中找到后者的第一次出现的下标
给定条件：题目不一定有解，找不到时返回-1

• 暴力遍历：两重循环对比搜索，简单不解释。时间复杂度O(m*n)，空间复杂度O(1)。
• 暴力遍历优化方案：两重循环，减少第一重循环的长度为base.length-need.length。时间复杂度O((m-n)*n)，空间复杂度O(1)。
• +KMP算法：第一步（核心），线性遍历need字符串，得到前缀匹配数量数组next[]，该数组每个位置的整数表示need字符串对应位的字符最长公共前缀的位数，换个角度思考呢，就是最长公共前缀的匹配下标；第二步，线性遍历base字符串，按暴力遍历进行匹配，如果未匹配上则根据need数组对base指针i进行跳转。时间复杂度O(m+n)，空间复杂度O(n)。
  代码直通车：

class KMPSolution {
    private int[] next(String needle) {
        if (needle.length() <= 0) {
            throw new RuntimeException("KMP does not support empty string.");
        }
        int next[] = new int[needle.length() + 1];
        next[0] = -1;
        for (int i = 0, j = -1; i < needle.length(); ) {
            if (j == -1 || needle.charAt(i) == needle.charAt(j)) {
                ++i;
                ++j;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = next(needle);
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }

        if (j == needle.length()) {
            return i - j;
        }
        return -1;
    }
}

• ++积累哈希【线性空间优化完毕】：我们以ababacadc为例，在该串中找aca，那么将被寻找串分为多个三个字母的子串也就是aba, bab...对每个串进行哈希，并将哈希值与寻找串进行对比，若相等则进行匹配。
  那么问题来了，这里的关键是如何取寻找一个o(1)的哈希算法，来对子串求哈希，按理说如果你需要去对每个子串求其哈希，必定需要考虑每个字符所以至少复杂度应该为o(n)。想到这里，本应该是难以进行下去了的。但考虑一下子串的序列构成，每个相邻的子串其实只相差第一个与最后一个字符，不妨尝试预求值+积累序列的方式：对第一个子串求字母和，然后后面每个新串的处理方案为减去第一个字母加上最后一个字母。来了，o(1)的哈希算法。
  后面的详细方案就不需要说了，但是这个算法有个问题就是对于边界情况效率可能较低，如和哈希大量重复，如子串长度几乎等于母串长度。至少这个方案如果不特意为难，应该是最佳的方案。
  时间复杂度o(m)，空间复杂度o(1)【进行了线性空间优化】
  代码直通车：

class HashSolution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0) return 0;
        if(haystack.length() < needle.length()) return -1;
        int needleHash = 0, hayHash = 0;
        int nl = needle.length(), hl = haystack.length(), del = hl - nl;
        for(int i = 0 ; i < nl ; ++i){
            needleHash += needle.charAt(i);
            hayHash += haystack.charAt(i);
        }
        for(int i = 0 ; i <= del ; ++i){
            if(i != 0){
                hayHash -= haystack.charAt(i - 1);
                hayHash += haystack.charAt(i + nl - 1);
            }
            if(hayHash == needleHash){
                int j = 0;
                for(; j < nl ; ++j){
                    if(haystack.charAt(i+j) != needle.charAt(j)){
                        break;
                    }
                }
                if(j == nl){
                    return i;
                }
            }
        }
        return -1;
    }
}

【53】. 最大子数组
简要介绍：给定一个整型数组，要求寻找到和最大的连续子数组，并返回其最大和

• 线性DP：记给定数组为n，建立与该数组长度一致的数组m，记录以对应位置的整型数为终点的最大和，得到递归方程m[i]=max{m[i-1]+n[i], n[i]}，并维持返回值max=max{m[i], max}即可。时间复杂度O(n)，空间复杂度O(n)。
• +线性DP优化：发现递归方程与m[0...i-2]无关，故可优化空间复杂度，仅记录当前位的最大值为cur，修改递归方程为cur=max{cur+n[i], n[i]}，并维持返回值max=max{cur, max}。时间复杂度O(n)，空间复杂度O(1)。

【69】. 整数平方根
简要介绍：求一个整数的平方根，小数部分截取

• 递增遍历：一重递增循环，简单不解释。时间复杂度O(val(i))
• +二分查找：左为0右为i二分查找，考虑的要多一些。时间复杂度O(log(val(i)))，空间复杂度O(1)。（LeetCode上时间效率已经100%了）
  以下为蛇皮鬼神估算解决方法
• ++牛顿迭代法：对于f(x)=x^2-a，出于其导数f'(x)=2x，可利用切线切于(m, f(m))时与x轴的交点t更逼近于a，由等式2m(m-t)=m^2-a得解t=(m^2+a)/(2m)，对t进行迭代得t=(t^2+a)/(2t)。于是在给定精确度下，给出以下代码（emm，出于一些原因，在高精度上有一定的问题，无法通过LeetCode）：

public int mySqrt(float x)
{
    final float precision = 0.1f;
    float res = x, pre;
    do
    {
        pre = res;
        res = (res + x/res) / 2;
    }while(Math.abs(res-pre) > precision);
    return (int)res;
}

• +++++Quake-III鬼数迭代法：神级鬼数迭代计算平方根的方法，反正俺看不懂，且因为同时运用了指针，故只能贴C++代码。带个鬼数，少量运算高精度结果，大神的想法我也只能是贴贴而已。

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y   = number;
    i   = * ( long * ) &y;   // evil floating point bit level hacking
    i   = 0x5f3759df - ( i >> 1 ); // what the fuck?
    y   = * ( float * ) &i;
    y   = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
    // y   = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

    return y;
}  

【70】. 爬楼梯
简要介绍：给定一个数字表示有几阶楼梯，并一次只能爬1或者2阶楼梯，求有几种爬法。

• 线性DP：假定需要爬第i阶阶梯，则其爬法等于爬i-1阶的方法数量加上爬i-2阶的方法数量，递归方程m[i]=1,i=0 & m[i]=1,i=1 & m[i]=m[i-1]+m[i-2], i>=2。时间复杂度O(n)，空间复杂度O(n)
• +线性DP优化：同题【53】一样的DP优化方法，进行空间优化，不赘述。

【136】. 出现一次的数字
简要介绍：给定一个数组，要求找出其中只出现一次的数字
给定条件：其他的出现的数字必定出现两次，出现一次的数字只有一个

• 暴力遍历：简单不优雅不说，也懒得分析。
• 哈希索引：一遍循环，第一次出现插入哈希表，第二次出现移出哈希表，最后找到该哈希表中唯一的数字。假设哈希效率高，单次查找为O(1)，则时间复杂度可视为O(n)，空间复杂度O(n)
• 集合运算：第一遍循环，将数组中数字添加进入集合，并同时计算总和sum1；第二遍对集合循环，求其和sum2；出现一次的数字值=2*sum2-sum1，时间复杂度确定性的O(n)，空间复杂度O(n)
• +异或运算：基础公式a^b^b=a，一边循环，初值0对每个数字进行异或，最后该值即为只出现一次的值。

【141】. 链表环判定
简要介绍：给定一个链表，判断其是否有环

• 暴力遍历：暴暴暴暴力，别了吧。。。
• 哈希索引：一遍循环，每次到一个节点，先检查是否在哈希表里，如果不在，则添加进去；如果在，则说明遇环；遍历至尾说明无环。时间复杂度O(n)，空间复杂度O(n)
• +快慢指针：一遍循环，一个指针一次走一格，一个指针一次走两格，若两个指针发生相遇说明存在环；若两个指针不发生相遇且快指针到尾，说明不存在环。

【142】. 链表环节点寻找
简要介绍：给定一个链表，判断其是否有环并找出环节点
改进自：【141】

• 哈希索引：一遍循环，每次到一个节点，先检查是否在哈希表里，如果不在，则添加进去；如果在，则说明遇环，返回该节点即可；遍历至尾说明无环。时间复杂度O(n)，空间复杂度O(n)
• +快慢指针： 一遍循环，一个指针一次走一格，一个指针一次走两格，若两个指针发生相遇说明存在环。以下分析基于有环，沿链表方向将链表分为三个部分：第一段为头到环点记长度为a；第二段为环点到相遇点记长度为b；第三段为相遇点到环点记长度为c，并记环长度为r，有等式r=b+c
  1. s=a+b & 2s=s+n*r
  2. =>s=a+b & s=n*r
  3. =>a=n*r-b
  4. =>a=(n-1)*r+c
  5. =>a-c=(n-1)*r
     这个结果意味着什么呢，也就是从起始点到环点的距离之差等于相遇点到环点的距离之差。则给出以下算法：
     快慢指针相遇时，同时从起点与相遇点发出两个慢指针，该两个慢指针第一次相遇的点即为环点。
     时间复杂度O(n)，空间复杂度O(n)

【155】. 最小栈
简要介绍：设计一个栈，其提供一个方法，能获取当前栈中的最小值

• 遍历栈：普通设计该栈，当调用getMin()时，遍历栈空间取最小值。时间复杂度O(n)，空间复杂度O(1)
• 辅助空间：普通设计该栈，同时建立辅助栈储存最小值，每次压栈比较其顶端数据与压栈数据，压入最小值即可。时间复杂度O(1)，空间复杂度O(n)

【160】. 寻找两个链表第一个交点
简要介绍：给定两条链表，寻找这两条链表的第一个交点，如果不相交则返回null

• 暴力遍历：链表双重循环，比较引用是否相等。时间复杂度O(n^m)，空间复杂度O(1)
• 辅助栈：对两个链表建立辅助栈，遍历时将遍历到的节点插入栈中，当遍历结束后开始出栈，寻找到第一个不相等的节点则前一个出栈节点为相交位置。时间复杂度O(m+n)，空间复杂度O(m+n)
• 哈希索引：第一次用很新鲜感觉很棒，然后就熟了。
• +计算长度：第一次分别遍历，对两个链表计算长度；第二次一起遍历，让长的链表先走长度差值，然后开始比较引用是否相等，第一个相等的节点为相交点。时间复杂度O(m+n)，空间复杂度O(1)

【169】. 最常出现的数
简要介绍：给定一个数组，要求在里面找到出现次数大于数组一半大小的数

• 暴力遍历：双重循环，无意义。时间复杂度O(n^2)，空间复杂度O(1)
• 哈希索引：key存值，value存出现次数，每次迭代查看value值是否大于n/2。依然是假设哈希效率高，时间复杂度O(n)，空间复杂度O(n)
• 排序中分：将数组进行排序，因为这个数字出现的次数大于数组一半大小，所以数组中位数必定是这个数字。时间复杂度与空间复杂度依赖于排序算法。
• +投票算法：描述如下，选定一个候选人，每当有人投他则加票，每当有人投其他人则减票，票数为0时根据下一张票来确定新的候选人。因为该数字出现的次数大于数组一般大小，一遍循环下来必定为该数字。时间复杂度O(n)，空间复杂度O(1)

【203】. 删除链表中的数
简要介绍：给定一个链表以及一个目标数字，要求在里面删除所有值等同于该目标数字的链表节点

• 三行代码：【哈哈哈只是为了记录这三行代码】

  public ListNode removeElements(ListNode head, int val) {
        ListNode node = head, pre = head;
        while (node != null)  node = val == node.val? pre == node ? (head = pre = node.next) : (pre.next = node.next):(pre = node).next;
        return head;
    }

---

解题与优化方案总结

【#】哈希表：将已经遇到过的对象存入哈希表，可进行假设o(1)的时间消耗

【#】双指针：诸如链表环判定，倒数第K个节点balabala

【#】线性空间优化：在题目所需要的额外空间是线性空间时可进行空间优化

• 应用条件：依次进行下标增加的线性位置的值计算，且该值计算不依赖于整体的线性空间，比如计算下标为i时值时，仅需要前一个或两个等固定数目的值，且最后仅需返回最后一个线性位置的值
• 利用变量存储所需要数目的值，在更新目标值后更新变量即可。
• 扩展：多维空间优化，如题【72】编辑距离，该题一般情况下，空间消耗应为o(n^2)，但实际上分析发现，下标为(i,j)的值计算仅依赖于三个位置的值分别是(i-1,j-1), (i-1,j), (i,j-1)，便可同样使用与该优化方案一样的思想来进行空间优化，可达到o(n)，更高维的空间优化仍然可以根据一样的思想进行优化。