算法

一、五大算法思想

1、分治法

将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之

适用于二分搜索、大整数乘法、Strassen矩阵乘法、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔

2、动态规划法

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划

适用于矩阵连乘、走金字塔、最长公共子序列(LCS)、最长递增子序列(LIS)、凸多边形最优三角剖分、背包问题、双调欧几里得旅行商问题

将一个问题拆成几个子问题，分别求解这些问题，即可推断出大问题的解

public String longestPalindrome(String s) {
    // 特判
    int len = s.length();
    if (len < 2) {
        return s;
    }

    int maxLen = 1;
    int begin = 0;

    // dp[i][j] 表示 s[i, j] 是否是回文串
    boolean[][] dp = new boolean[len][len];
    char[] charArray = s.toCharArray();

    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (charArray[i] != charArray[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

            // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    return s.substring(begin, begin + maxLen);
}

求最长回文子串，解题核心思路：dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]，从回文长度2开始慢慢加长，每次计算依赖之前的结果

3、贪心法

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解

适用于活动选择问题、钱币找零问题、再论背包问题、小船过河问题、区间覆盖问题、销售比赛、Huffman编码、Dijkstra算法（求解最短路径）、最小生成树算法

4、回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称

适用于八皇后问题、图的着色问题、装载问题、批处理作业调度问题、再再论背包问题、最大团问题、连续邮资问题、符号三角形问题

5、分支界限法

类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解

转自https://blog.csdn.net/ght886/article/details/80289142

二、排序

三、查找

1、哈希映射

通过空间换取时间的方式，可以将查找时间从O(n)降低到O(1)

public int[] twoSum(int[] nums, int target) {  
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0; i<nums.length; i++) {
        if(map.containsKey(target - nums[i])) {
            return new int[]{map.get(target - nums[i]), i};
        }
        map.put(nums[i], i);
    }
    return null;
}

比如这道从数组中找出和为目标值的那两个整数，通过一次哈希遍历解决，而暴力算法要用2个for循环

2、二分查找

public static int binarySearch(Integer[] srcArray, int des) {
    //定义初始最小、最大索引
    int start = 0;
    int end = srcArray.length - 1;
    //确保不会出现重复查找，越界
    while (start <= end) {
        //计算出中间索引值
        int middle = (end + start)>>>1 ;//防止溢出
        if (des == srcArray[middle]) {
            return middle;
        //判断下限
        } else if (des < srcArray[middle]) {
            end = middle - 1;
        //判断上限
        } else {
            start = middle + 1;
        }
    }
    //若没有，则返回-1
    return -1;
}

时间复杂度O(logn)，暴力的话是O(n²)，相比好了很多

四、双指针

1、快慢指针

2、左右指针

3、滑动窗口

双指针模拟滑动窗口

public int lengthOfLongestSubstring(String s) {
    if(s == null || s.length() == 0) {
        return 0;
    }
    Map<Character, Integer> map = new HashMap<>();
    int max = 0;
    for(int i = 0, j = 0; i < s.length(); i++) {
        if(map.containsKey(s.charAt(i))) {
            int index = map.get(s.charAt(i));
            if(index >= j) {
                j = index + 1;
            }
        }
        max = Math.max(max, i - j + 1);
        map.put(s.charAt(i), i);
    }
    return max;
}

找出其中不含有重复字符的最长子串的长度

滑窗框架

public String slidingWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    //将需要的字符串加入need
    for(int i=0; i<t.length(); i++) {
        need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
    }
    int left = 0, right = 0; //左右指针
    int valid = 0; //判断窗口满足need的个数

    //自定义一些参数
    
    while(right < s.length()) {
        //右移窗口
        char c = s.charAt(right);
        right++;

        //更新窗口数据window等

        //判断左窗口是否需要收缩
        while(window needs shrink) {
            char d = s.charAt(left);
            left++;

            //更新窗口数据window等
            
        }
    }
    return
}

五、单调栈

解柱状图相关题利器，接雨水..

算法